As demand for high-speed telecommunication increases, automating the design of fibre networks is critical for minimising deployment costs and ensuring consistent service. However, existing search strategies within British Telecom’s (BT) design software struggle to consistently locate near-global optima as network scale increases, and the hard-coded definition of network domains limits flexibility for non-developers. To address these challenges, this paper proposes a novel framework with two key contributions: a Prolog Advisory System (PAS) for modular domain definition and a sequence-based selection hyper-heuristic for enhanced optimisation. The PAS utilises logic programming to decouple constraint checking and cost calculation from the core framework, enabling rapid domain modification. For optimisation, we introduce intelligent move sequencing using Luby-based and Hidden Markov Model approaches, augmented by a continuous pivot strategy that increases the exploration of constraint-breaking moves. Experimental results on real-world case studies illustrate the robustness and effectiveness of our method to obtain high-quality solutions, regardless of the size of the network. Specifically, on large-scale instances, the proposed method outperforms BT’s current approach, reducing average design cost by approximately 3.8% and decreasing the required evaluations by up to 65%. This work offers vital efficiency gains for BT’s multi-billion pound fibre roll-out program, one of the UK’s largest infrastructure investments, where even small design improvements yield substantial financial savings.

Hyper-heuristics are general purpose search methods for solving computationally difficult problems. A selection hyper-heuristic is composed of two key components: a heuristic selection method and move acceptance criterion. Under an iterative single-point search framework, a solution is modified by selecting and applying a predefined low-level heuristic, with a decision then taken to accept or reject the resulting solution. Designing a selection hyper-heuristic is an extremely challenging task. In this study, we investigate computer-aided design of a selection hyper-heuristic for the open vehicle routing problem. A time delay neural network is used as an offline apprenticeship learning method. Our approach first observes the search behavior of multiple expert human-designed selection hyper-heuristics on a selected sample of training instances, before automatically generating a selection hyper-heuristic capable of solving unseen instances effectively. The proposed approach is tested on open vehicle routing problem instances of different sizes to examine the performance and generality of the selection hyper-heuristics generated. Improved performance is demonstrated over a set of well-known benchmarks from the literature when compared to using the existing expert systems directly.

Parameter tuning is a challenging and time-consuming task, crucial to obtaining improved metaheuristic performance. There is growing interest in cross-domain search methods, which consider a range of optimisation problems rather than being specialised for a single domain. Metaheuristics and hyper-heuristics are typically used as high-level cross-domain search methods, utilising problem-specific low-level heuristics for each problem domain to modify a solution. Such methods have a number of parameters to control their behaviour, whose initial settings can influence their search behaviour significantly. Previous methods in the literature either fix these parameters based on previous experience, or set them specifically for particular problem instances. There is a lack of extensive research investigating the tuning of these parameters systematically. In this paper, F-Race is deployed as an automated cross-domain parameter tuning approach. The parameters of a steady-state memetic algorithm and the low-level heuristics used by this algorithm are tuned across nine single-objective problem domains, using different training strategies and budgets to investigate whether F-Race is capable of effectively tuning parameters for cross-domain search. The empirical results show that the proposed methods manage to find good parameter settings, outperforming many methods from the literature, with different configurations identified as the best depending upon the training approach used.

Selection hyper-heuristics have emerged as high level general-purpose search methodologies that mix and control a set of low-level (meta)heuristics. Previous empirical studies over a range of single objective optimisation problems have shown that the number and type of low-level (meta)heuristics used are influential to the performance of selection hyper-heuristics. In addition, move acceptance strategies play an important role and can significantly affect the overall performance of a hyper-heuristic. In this paper, we introduce an adapted variant of an existing learning automata based multiobjective hyper-heuristic from the literature. We investigate the performance and generality level of the proposed method, and another learning automata based selection hyper-heuristic, operating over a search space of multiobjective evolutionary algorithms (MOEAs) across two well-known multiobjective optimisation benchmarks. The experimental results demonstrate that, regardless of the number and type of low-level metaheuristics available, the learning automata based hyper-heuristics outperform each constituent MOEA individually, and an online learning and random choice selection hyper-heuristic from the literature. This performance and generality is shown to be consistent across a number of different move acceptance strategies.

In light of increased demand for streaming services, the need for more cost-effective network services is pressing. The telecommunication industry is facing tight budgets and severe competition. Therefore, reducing the cost of designing a fibre network via automation and optimisation has become critical. In order to automate and optimise network designs, British Telecom (BT) have developed a network design software, BT NetDesign, which includes a number of heuristics to search the design space of networks using a simulated annealing (SA) search strategy. Although NetDesign's current SA-based method is able to provide exploration and exploitation via different move heuristics, it cannot consistently reach the near-global optimum as the search space grows exponentially with the size of the network. To deal with larger networks, this study implements sequence-based hyper-heuristics utilising a hidden Markov model (HMM) with different acceptance strategies. The proposed methods have been rigorously analysed and compared using real-world network instances of different sizes. Results showed that HMM with a longer learning period and threshold acceptance strategy has promising ability to reach high quality solutions for large real-world problem instances.

Genetic programming is an effective technique for inductive synthesis of programs from tests, i.e. training examples of desired input-output behavior. Programs synthesized in this way are not guaranteed to generalize beyond the training set, which is unacceptable in many applications. We present Counterexample-Driven Genetic Programming (CDGP) that employs evolutionary search to synthesize provably correct programs from formal specifications. CDGP employs a Satisfiability Modulo Theories (SMT) solver to formally verify programs in the evaluation phase. A failed verification produces counterexamples that are in turn used to calculate fitness and thereby drive the search process. When compared with a range of approaches on a suite of state-of-the-art specification-based synthesis benchmarks, CDGP systematically outperforms them, typically synthesizing correct programs faster and using fewer tests.

Multi-objective evolutionary algorithms (MOEAs) based on the concept of Pareto-dominance have been successfully applied to many real-world optimisation problems. Recently, research interest has shifted towards indicator-based methods to guide the search process towards a good set of trade-off solutions. One commonly used approach of this nature is the indicator-based evolutionary algorithm (IBEA). In this study, we highlight the solution distribution issues within IBEA and propose a modification of the original approach by embedding an additional Pareto-dominance based component for selection. The improved performance of the proposed modified IBEA (mIBEA) is empirically demonstrated on the well-known DTLZ set of benchmark functions. Our results show that mIBEA achieves comparable or better hypervolume indicator values and epsilon approximation values in the vast majority of our cases (13 out of 14 under the same default settings) on DTLZ1-7. The modification also results in an over 8-fold speed-up for larger populations.

In this study we use Genetic Programming (GP) as an offline hyper-heuristic to evolve a mutation operator for Evolutionary Programming. This is done using the Gaussian and uniform distributions as the terminal set, and arithmetic operators as the function set. The mutation operators are automatically designed for a specific function class. The contribution of this paper is to show that a GP can not only automatically design a mutation operator for Evolutionary Programming (EP) on functions generated from a specific function class, but also can design more general mutation operators on functions generated from groups of function classes. In addition, the automatically designed mutation operators also show good performance on new functions generated from a specific function class or a group of function classes.

Hyper-heuristics are high-level methodologies for solving complex problems that operate on a search space of heuristics. In a selection hyper-heuristic framework, a heuristic is chosen from an existing set of low-level heuristics and applied to the current solution to produce a new solution at each point in the search. The use of crossover low-level heuristics is possible in an increasing number of general-purpose hyper-heuristic tools such as HyFlex and Hyperion. However, little work has been undertaken to assess how best to utilise it. Since a single-point search hyper-heuristic operates on a single candidate solution, and two candidate solutions are required for crossover, a mechanism is required to control the choice of the other solution. The frameworks we propose maintain a list of potential solutions for use in crossover. We investigate the use of such lists at two conceptual levels. First, crossover is controlled at the hyper-heuristic level where no problem-specific information is required. Second, it is controlled at the problem domain level where problem-specific information is used to produce good-quality solutions to use in crossover. A number of selection hyper-heuristics are compared using these frameworks over three benchmark libraries with varying properties for an NP-hard optimisation problem: the multidimensional 0-1 knapsack problem. It is shown that allowing crossover to be managed at the domain level outperforms managing crossover at the hyper-heuristic level in this problem domain.

Hyper-heuristics are search methodologies which operate at a higher level of abstraction than traditional search and optimisation techniques. Rather than operating on a search space of solutions directly, a hyper-heuristic searches a space of low-level heuristics or heuristic components. An iterative selection hyper-heuristic operates on a single solution, selecting and applying a low-level heuristic at each step before deciding whether to accept the resulting solution. Crossover low-level heuristics are often included in modern selection hyper-heuristic frameworks, however as they require multiple solutions to operate, a strategy is required to manage potential solutions to use as input. In this paper we investigate the use of crossover control schemes within two existing selection hyper-heuristics and observe the difference in performance when the method for managing potential solutions for crossover is modified. Firstly, we use the crossover control scheme of AdapHH, the winner of an international competition in heuristic search, in a Modified Choice Function - All Moves selection hyper-heuristic. Secondly, we replace the crossover control scheme within AdapHH with another method taken from the literature. We observe that the performance of selection hyper-heuristics using crossover lowlevel heuristics is not independent of the choice of strategy for managing input solutions to these operators.

Hyper-heuristics are a class of high-level search methodologies which operate on a search space of low-level heuristics or components, rather than on solutions directly. Traditional iterative selection hyper-heuristics rely on two key components, a heuristic selection method and a move acceptance criterion. Choice Function heuristic selection scores heuristics based on a combination of three measures, selecting the heuristic with the highest score. Modified Choice Function heuristic selection is a variant of the Choice Function which emphasises intensification over diversification within the heuristic search process. Previous work has shown that improved results are possible in some problem domains when using Modified Choice Function heuristic selection over the classic Choice Function, however in most of these cases crossover low-level heuristics (operators) are omitted. In this paper, we introduce crossover low-level heuristics into a Modified Choice Function selection hyper-heuristic and present results over six problem domains. It is observed that although on average there is an increase in performance when using crossover low-level heuristics, the benefit of using crossover can vary on a per-domain or per-instance basis.