Fitness landscape analysis provides insights into optimization problems, informing algorithms' design and identifying properties that influence performance. While understanding global landscape structure is critical, tools for analyzing and visualizing multi-objective, high-dimensional optimization problems remain limited. Recent models, such as Pareto local optima solution networks (PLOS-nets), primarily focus on small instances and binary representations, posing challenges for extension to more complex domains. To address this gap, we introduce mo-LON/D, a decomposition-based local optima network model for multi-objective landscapes. This model partitions a multi-objective problem into scalar sub-problems, constructs standard single-objective local optima networks (LONs) for each, and integrates them via a graph union. We validate mo-LON/D on fully enumerated bi-objective ρmnk-landscapes and contrast its structural features against PLOS-nets both visually and quantitatively. Despite the inherent sampling involved in scalarization, our results indicate that mo-LON/D offers comparable explanatory power (and even higher correlations) with respect to the performance of state-of-the-art algorithms. By harnessing established sampling techniques from single-objective research, mo-LON/D could potentially provide a scalable framework for characterizing complex multi-objective landscapes.

We demonstrate that there are strong patterns of periodicity in terms of how local optima are distributed across search spaces that can help to explain the "Big Valley" distribution of local optima. Examples of periodicity can be found by looking at several Partition Crossover events simultaneously and grouping together those that are nearer to each other in Hamming space. All of the local optima associated with one Partition Crossover event can be evaluated using a single linear equation. When looking at many Partition Crossover events simultaneously, linearity is preserved over complete and partially preserved recombining components.

Neutrality, characterized by pathways in the genotype space that do not alter the phenotype or fitness, enables a broad exploration of evolutionary search. Simplicity bias describes the tendency of evolutionary systems to favor low-complexity solutions. This study investigates how neutrality contributes to simplicity bias in evolutionary systems using a Boolean Linear Genetic Programming framework. We introduce two fitness functions that utilize symmetry in solutions to promote neutrality, to analyze their effects on neutral network connectivity and search dynamics. Our results demonstrate that simpler phenotypes, characterized by lower Kolmogorov complexity, exhibit greater redundancy and connectivity, making them more accessible during neutral exploration. In addition, the proposed fitness functions significantly improve search success rates, especially for complex target phenotypes, by expanding neutral pathways. These findings shed light on the role of neutrality in shaping simplicity bias and provide practical insights to improve the effectiveness of evolutionary algorithms.

We present an analysis of landscape features for predicting the performance of multi-objective combinatorial optimization algorithms. We consider features from the recently proposed compressed Pareto Local Optimal Solutions Networks (C-PLOS-net) model of combinatorial landscapes. The benchmark instances are a set of ρmnk-landscapes with 2 and 3 objectives and various levels of ruggedness and objective correlation. We consider the performance of three algorithms - Pareto Local Search (PLS), Global Simple EMO Optimizer (GSEMO), and Non-dominated Sorting Genetic Algorithm (NSGA-II) - using the resolution and hypervolume metrics. Our tailored analysis reveals feature combinations that influence algorithm performance specific to certain landscapes. This study provides deeper insights into feature importance, tailored to specific ρmnk-landscapes and algorithms.

A combination of recombination and local search can expose the existence of an exponential number of parallel lattices that span the search space for all classes of k-bounded pseudo-Boolean functions, including MAX-kSAT problems. These "parallel" lattices sometimes have identical evaluations shifted by a constant. We use Partition Crossover to aid in the discovery of lattices, which are sets of 2q possible offspring from recombination events, organized into q-dimensional hypercubes, where q is the number of recombining components given two parents. Finally, we show that recursively embedded subspace lattices display a fractal structure, which can be captured using rewrite rules based on a Lindenmayer system that accurately model how local optima are distributed across different size lattices.

The search for proper parameter values is a key process for applying metaheuristic algorithms to solving complex optimization problems. Several specialized tuning methods have been proposed in the literature. One of the main difficulties when tuning parameters is the stochastic nature of metaheuristic algorithms and their requirement to solve problem instances with different features. In this work, we are interested in understanding different tuning process features using the Search Trajectory Networks approach. Here, a network of search processes can be constructed based on the solutions visited and the sequences of visits performed. Here, we extend the definitions of Search Trajectory Networks to tuning processes using two tuning methods from the literature: ParamILS and Evoca. We analyze the differences between the parameter tuning processes they perform and the incidence of their main hyper-parameters in these processes. From our results, we conclude the relevance of the number of pairs seed/instance for the search performed by ParamILS but not for Evoca regarding the number of visited configurations and the network's connectivity. Moreover, the evolutionary nature of Evoca promotes an exploratory behavior, traversing trajectories with fewer nodes in common compared to ParamILS.

Search Trajectory Networks (STNs) serve as a tool for visualizing algorithm behavior within the realm of optimization problems. Despite their user-friendly nature, challenges arise in obtaining interpretable plots, for example, in the case of optimization problems with large solutions or many dimensions. To address this, we have introduced a new search space partitioning strategy utilizing hierarchical agglomerative clustering. This enhanced strategy, now available in STNWeb, the web version of STNs, produces plots that are easier to interpret than those produced by existing search space partitioning strategies. This facilitates an improved understanding of algorithm performance in complex scenarios.

The ability of Large Language Models (LLMs) to generate high-quality text and code has fuelled their rise in popularity. In this paper, we aim to demonstrate the potential of LLMs within the realm of optimization algorithms by integrating them into STNWeb. This is a web-based tool for the generation of Search Trajectory Networks (STNs), which are visualizations of optimization algorithm behavior. Although visualizations produced by STNWeb can be very informative for algorithm designers, they often require a certain level of prior knowledge to be interpreted. In an attempt to bridge this knowledge gap, we have incorporated LLMs, specifically GPT-4, into STNWeb to produce extensive written reports, complemented by automatically generated plots, thereby enhancing the user experience and reducing the barriers to the adoption of this tool by the research community. Moreover, our approach can be expanded to other tools from the optimization community, showcasing the versatility and potential of LLMs in this field.

The design of automated landscape-aware techniques requires low-cost features that characterize the structure of the target optimization problem. This paper approximates network-based landscape models of multi-objective optimization problems, which were constructed by full search space enumeration in previous studies. Specifically, we propose a sampling method using dominance-based local search for constructing an approximation of the Pareto local optimal solution network (PLOS-net) and its variant, the compressed PLOS-net. Both models are valuable to visualize and compute features on the distribution of Pareto local optima. We conduct experiments with multi-objective nk-landscapes and compare the features of full-enumerated PLOS-nets with that of approximate PLOS-nets. We analyze the correlation between landscape features and the performance of well-established multi-objective evolutionary and local search algorithms. Our results show that approximated networks can predict algorithm performance and provide recommendation for algorithm selection with the same level of accuracy, even though they are much more computationally affordable compared to full-enumerated networks. We finally illustrate how the approximate PLOS-net scale to large-size instances.

The performance of multiobjective evolutionary algorithms (MOEAs) varies across problems, making it hard to develop new algorithms or apply existing ones to new problems. To simplify the development and application of new multiobjective algorithms, there has been an increasing interest in their automatic design from their components. These automatically designed metaheuristics can outperform their human-developed counterparts. However, it is still unknown what are the most influential components that lead to performance improvements. This study specifies a new methodology to investigate the effects of the final configuration of an automatically designed algorithm. We apply this methodology to a tuned Multiobjective Evolutionary Algorithm based on Decomposition (MOEA/D) designed by the iterated racing (irace) configuration package on constrained problems of 3 groups: (1) analytical real-world problems, (2) analytical artificial problems and (3) simulated real-world. We then compare the impact of the algorithm components in terms of their Search Trajectory Networks (STNs), the diversity of the population, and the anytime hypervolume values. Looking at the objective space behavior, the MOEAs studied converged before half of the search to generally good HV values in the analytical artificial problems and the analytical real-world problems. For the simulated problems, the HV values are still improving at the end of the run. In terms of decision space behavior, we see a diverse set of the trajectories of the STNs in the analytical artificial problems. These trajectories are more similar and frequently reach optimal solutions in the other problems.

When Partition Crossover is used to recombine two parents which are local optima, the offspring are all local optima in the smallest hyperplane subspace that contains the two parents. The offspring can also be organized into a non-planar hypercube "lattice." Furthermore, all of the offspring can be evaluated using a simple linear equation. When a child of Partition Crossover is a local optimum in the full search space, the linear equation exactly determines its evaluation. When a child of Partition Crossover can be improved by local search, the linear equation is an upper bound on the evaluation of the associated local optimum when minimizing. This theoretical result holds for all k-bounded Pseudo-Boolean optimization problems, including MAX-kSAT, QUBO problems, as well as random and adjacent NK landscapes. These linear equations provide a stronger explanation as to why the "Big Valley" distribution of local optima exists. We fully enumerate a sample of NK landscapes to collect frequency information to complement our theoretical results. We also introduce new algorithmic contributions that can 1) expand smaller lattices in order to find larger lattices that contain additional local optima, and 2) introduce an efficient method to find new improving moves in lattices using score vectors.

Specialized graybox local search and crossover have been successfully combined within the framework of the so-called Drils (Deterministic recombination and iterated local search) algorithm. As for any evolutionary algorithm, the initial design framework, and the underlying high-level choices and parameters, are crucially important. The Drils algorithm is no exception, and recent enhanced variants exist in the literature. In this paper, we aim at: (i) improving the performance of the latest variants of Drils, and (ii) providing a better principled understanding of graybox search behavior and dynamics. On the basis of a preliminary analysis using Local Optima Networks of small-size NKQ-landscapes, we first highlight the difference of using local search with and without crossover. We then propose to pipeline these two techniques in a simple two-phase like iterated local search scheme which is shown to provide substantial improvements over the latest Drils+ variant for large-size NKQ-landscapes. We further report a dedicated analysis in an attempt to provide new insights into the impact of local search and crossover on the phenotype and the genotype of the local optima encountered in the search trajectory.

Landscape analysis is a very useful tool in optimization to understand the structure of the search space of a problem when there is some kind of distance or neighborhood defined over the solutions. Local Optima Networks (LON) have been proposed to serve as a summary of the landscape of a problem. LONs are graphs where the nodes are the local optima of the search space according to a particular neighborhood and edges join local optima when one can be reached from the other using some kind of perturbation followed by hill climbing. In this paper we enhance local optima networks to include precise information on the transition probabilities among local optima, yielding a Markov Chain for the visited local optima during the search. The new analysis tool, called Local Optima Markov Chain (LOMA), is built on top of the static landscape information depending on the problem and includes information about algorithm dynamics. We show how LOMAs can be used to compute metrics that are out of the reach of other landscape-aware tools, thus offering more information to understand algorithm dynamics.

The structure of local optima in multi-objective combinatorial optimization and their impact on algorithm performance are not yet properly understood. In this paper, we are interested in the representation of multi-objective landscapes and their multi-modality. More specifically, we revise and extend the network of Pareto local optimal solutions (PLOS-net), inspired by the well-established local optima network from single-objective optimization. We first define a compressed PLOS-net which allows us to enhance its perception while preserving the important notion of connectedness between local optima. We then study an alternative visualization of the (compressed) PLOS-net that focuses on good-quality solutions, improves the distinction between connected components in the network, and generalizes well to landscapes with more than 2 objectives. We finally define a number of network metrics that characterize the PLOS-net, some of them being strongly correlated with search performance. We visualize and experiment with small-size multiobjective nk-landscapes, and we disclose the effect of PLOS-net metrics against well-established multi-objective local search and evolutionary algorithms.

We consider search spaces associated with neural network channel configuration. Architectures and their accuracy are visualised using low-dimensional Euclidean embedding (LDEE). Optimisation dynamics are captured using local optima networks (LONs). LONs are a compression of a fitness landscape: the nodes are local optima and the edges are search transitions between them. Several neural architecture search algorithms are tested on the search space and we discover that iterated local search (ILS) is a competitive algorithm for neural channel configuration. We additionally implement a landscape-aware ILS which performs well. Observations from the search and landscape space analyses bring visual clarity and insight to the science of neural network channel design: the results indicate that a high number of channels, kept constant throughout the network, is beneficial.

The performance of multiobjective algorithms varies across problems, making it hard to develop new algorithms or apply existing ones to new problems. To simplify the development and application of new multiobjective algorithms, there has been an increasing interest in their automatic design from component parts. These automatically designed metaheuristics can outperform their human-developed counterparts. However, it is still uncertain what are the most influential components leading to their performance improvement. This study introduces a new methodology to investigate the effects of the final configuration of an automatically designed algorithm. We apply this methodology to a well-performing Multiobjective Evolutionary Algorithm Based on Decomposition (MOEA/D) designed by the irace package on nine constrained problems. We then contrast the impact of the algorithm components in terms of their Search Trajectory Networks (STNs), the diversity of the population, and the hypervolume. Our results indicate that the most influential components were the restart and update strategies, with higher increments in performance and more distinct metric values. Also, their relative influence depends on the problem difficulty: not using the restart strategy was more influential in problems where MOEA/D performs better; while the update strategy was more influential in problems where MOEA/D performs the worst.

We propose looking at the phenomenon of fitness landscape funnels in terms of their depth. In particular, we examine how the depth of funnels in Local Optima Networks (LONs) of benchmark Quadratic Assignment Problem instances relate to metaheuristic performance. Three distinct iterated local search (ILS) acceptance strategies are considered: better-or-equal (standard), annealing-like, and restart. Funnel measurements are analysed for their connection to ILS performance on the underlying combinatorial problems. We communicate the findings through hierarchical clustering of LONs, network visualisations, subgroup analysis, correlation analysis, and Random Forest regression models. The results show that funnel depth is associated with search difficulty, and that there is an interplay between funnel structure and acceptance strategy. Standard and annealing acceptance work better than restart on both deep-funnel and shallow-funnel problems; standard acceptance is the best strategy when optimal funnel(s) are deep, while annealing acceptance is superior when they are shallow. Regression models including funnel depth measurements could explain up to 96% of ILS runtime variance (with annealing-like acceptance). The runtime of ILS with restarts was less explainable using funnel features.

Local optima networks (LONs) model the global distribution and connectivity pattern of local optima under given search operators. Recent research has looked at how recombination operators can jump from a pair of parents that are locally optimal to a new child that is either a local optimum, or is guaranteed to be in a new basin of attraction. Recombination can therefore also induce a local optima network which maps how crossover moves between local optima. In this paper, we prove that recombination induces a LON which is actually a network of overlapping hypercube lattices. Given two or more samples from any lattice, we can also infer the existence of additional local optima that have not previously been reached by sampling. We prove that these lattices can be exponentially large. Finally, we prove that there exists TSP instances can be solved in polynomial time by exploiting Partition Crossover; these same instances are not solved by local search.

Antimicrobial resistance is one of the biggest threats to global health, food security, and development. Antibiotic overuse and misuse are the main drivers for the emergence of resistance. It is crucial to optimise the use of existing antibiotics in order to improve medical outcomes, decrease toxicity and reduce the emergence of resistance. We formulate the design of antibiotic dosing regimens as an optimisation problem, and use an evolutionary algorithm suited to continuous optimisation (differential evolution) to solve it. Regimens are represented as vectors of real numbers encoding daily doses, which can vary across the treatment duration. A stochastic mathematical model of bacterial infections with tuneable resistance levels is used to evaluate the effectiveness of evolved regimens. The objective is to minimise the treatment failure rate, subject to a constraint on the maximum total antibiotic used. We consider simulations with different levels of bacterial resistance, two ways of administering the drug (orally and intravenously), as well as coinfections with two strains of bacteria. Our approach produced effective dosing regimens, with an average improvement in lowering the failure rate 30%, when compared with standard fixed-daily-dose regimens with the same total amount of antibiotic.

An optimal recombination operator for two-parent solutions provides the best solution among those that take the value for each variable from one of the parents (gene transmission property). If the solutions are bit strings, the offspring of an optimal recombination operator is optimal in the smallest hyperplane containing the two parent solutions. Exploring this hyperplane is computationally costly, in general, requiring exponential time in the worst case. However, when the variable interaction graph of the objective function is sparse, exploration can be done in polynomial time. In this article, we present a recombination operator, called Dynastic Potential Crossover (DPX), that runs in polynomial time and behaves like an optimal recombination operator for low-epistasis combinatorial problems. We compare this operator, both theoretically and experimentally, with traditional crossover operators, like uniform crossover and network crossover, and with two recently defined efficient recombination operators: partition crossover and articulation points partition crossover. The empirical comparison uses NKQ Landscapes and MAX-SAT instances. DPX outperforms the other crossover operators in terms of quality of the offspring and provides better results included in a trajectory and a population-based metaheuristic, but it requires more time and memory to compute the offspring.

The global structure of the hyperparameter spaces of neural networks is not well understood and it is therefore not clear which hyperparameter search algorithm will be most effective. In this paper we analyze the landscapes of convolutional neural network architecture search spaces to provide insight into appropriate search algorithms for these spaces. Using a classical fitness landscape analysis approach (fitness distance correlation) and a more recent tool (local optima networks) we study the global structure of these spaces. Our analysis on six image classification datasets reveals that the landscapes are multi-modal, but with relatively few local optima from which it is not hard to escape with a simple perturbation operator. This led us to explore the performance of iterated local search, which we found to more effectively search the training landscapes than three evolutionary algorithm variants. Evolutionary algorithms, however, outperformed iterated local search in terms of generalization on problems with larger discrepancies between the training and testing landscapes.

Abstract A local optima network (LON) encodes local optima connectivity in the fitness landscape of a combinatorial optimisation problem. Recently, LONs have been studied for their fractal dimension. Fractal dimension is a complexity index where a non-integer dimension can be assigned to a pattern. This paper investigates the fractal nature of LONs and how that nature relates to metaheuristic performance on the underlying problem. We use visual analysis, correlation analysis, and machine learning techniques to demonstrate that relationships exist and that fractal features of LONs can contribute to explaining and predicting algorithm performance. The results show that the extent of multifractality and high fractal dimensions in the LON can contribute in this way when placed in regression models with other predictors. Features are also individually correlated with search performance, and visual analysis of LONs shows insight into this relationship.

In contrast with random uniform instances, industrial SAT instances of large size are solvable today by state-of-the-art algorithms. It is believed that this is the consequence of the non-random structure of the distribution of variables into clauses. In order to produce benchmark instances resembling those of real-world formulas with a given structure, generative models have been proposed. In this paper we study the MAX-3SAT problem with model-generated instances having a power-law distribution. Specifically, we target the regions in which computational difficulty undergoes an easy/hard phase transition as a function of clause density and of the power-law exponent. Our approach makes use of a sampling technique to build a graph model (a local optima network) in which nodes are local optima and directed edges are transitions between optima basins. The objective is to relate the structure of the instance fitness landscape with problem difficulty through the transition. We succeed in associating the transition with straightforward network metrics, thus providing a novel and original fitness landscape view of the computational features of the power-law model and its phase transition.

In local search algorithms, the pivoting rule determines which neighboring solution to select and thus strongly influences the behavior of the algorithm and its capacity to sample good-quality local optima. The classical pivoting rules are first and best improvement, with alternative rules such as worst improvement and maximum expansion recently studied on hill-climbing algorithms. This article conducts a thorough empirical comparison of five pivoting rules (best, first, worst, approximated worst and maximum expansion) on two benchmark combinatorial problems, NK landscapes and the unconstrained binary quadratic problem (UBQP), with varied sizes and ruggedness. We present both a performance analysis of the alternative pivoting rules within an iterated local search (ILS) framework and a fitness landscape analysis and visualization using local optima networks. Our results reveal that the performance of the pivoting rules within an ILS framework may differ from their performance as single climbers and that worst improvement and maximum expansion can outperform classical pivoting rules.

Partition crossover (PX) is an efficient recombination operator for gray-box optimization. PX is applied in problems where the objective function can be written as a sum of subfunctions fl(.). In PX, the variable interaction graph (VIG) is decomposed by removing vertices with common variables. Parent variables are inherited together during recombination if they are part of the same connected recombining component of the decomposed VIG. A new way of generating the recombination graph is proposed here. The VIG is decomposed by removing edges associated with subfunctions fl(.) that have similar evaluation for combinations of variables inherited from the parents. By doing so, the partial evaluations of fl(.) are taken into account when decomposing the VIG. This allows the use of partition crossover in continuous optimization. Results of experiments where local optima are recombined indicate that more recombining components are found. When the proposed epsilon-PX (ePX) is compared with other recombination operators in Genetic Algorithms and Differential Evolution, better performance is obtained when the epistasis degree is low.

Antibiotic resistance is one of the major challenges that we are facing today. The frequent overuse of antibiotics is one of the main reasons for the development of resistance. A mathematical model of bacterial population dynamics is used, where drug administration and absorption mechanics are implemented to evaluate the fitness of automatically designed treatments. To maximise the probability of curing the host while minimising the total drug used we have explored treatments with different daily dosages and lengths. Two multi-objective population-based methods, a well-known evolutionary algorithm and a particle swarm optimisation algorithm are tuned and contrasted when solving the posed treatment design problem. The best solutions found by our approach suggest treatments ranging from five to seven days with a high initial dose, followed by lower doses, use lower amounts of the drug than the standard common practice of fixed daily dosages over ten days.

Most algorithms proposed for solving complex problems require the definition of some parameter values. The process of finding suitable parameter values is an optimization problem by itself. Understanding the global structure of search spaces of complex optimization problems remains a challenge. Moreover, understanding the relationship between parameter values and the performance of metaheuristics is a key issue on their development. Local optima networks propose a scheme to model search spaces as networks whose nodes represent local optima and edges represent transitions between them. In this work, we adapt the local optima network model to analyze and visualize the global structure of parameter configuration spaces. Our main objectives are to understand the structure of these networks and explore the difficulty of different tuning scenarios using common indicators previously proposed in local optima networks studies (e.g. number of local optima, number of global optima and presence of local and global funnels). For this, we use the well-known tuning method ParamILS to analyze configuration search spaces of a standard genetic algorithm that solves continuous optimization problems.

While there are many inexact heuristics for generating high quality solutions to the Travelling Salesman Problem, our understanding of why these methods are effective and efficient is still limited. This paper looks at two population based heuristics: the EAX algorithm and the Mixing GA using partition crossover. We show that the local optima used to construct the initial population are also sampling edges found in the global optimum at an extremely high rate: in the majority of TSP instances, the number of global edges in the initial population is more than 73%. Next, we look at how recombination operators increase the representation of edges from the global optimum in the population, or increase the number of global edges in the best solutions in the population. We also look at TSP instances that are more difficult to solve, and again we find that edge frequency information can help to explain algorithm performance. Finally we use these result to suggest new strategies for generating high quality solutions for Travelling Salesman Problems.

Connection patterns among Local Optima Networks (LONs) can inform heuristic design for optimisation. LON research has predominantly required complete enumeration of a fitness landscape, thereby restricting analysis to problems diminutive in size compared to real-life situations. LON sampling algorithms are therefore important. In this article, we study LON construction algorithms for the Quadratic Assignment Problem (QAP). Using machine learning, we use estimated LON features to predict search performance for competitive heuristics used in the QAP domain. The results show that by using random forest regression, LON construction algorithms produce fitness landscape features which can explain almost all search variance. We find that LON samples better relate to search than enumerated LONs do. The importance of fitness levels of sampled LONs in search predictions is crystallised. Features from LONs produced by different algorithms are combined in predictions for the first time, with promising results for this “super-sampling”: a model to predict tabu search success explained 99% of variance. Arguments are made for the use-case of each LON algorithm and for combining the exploitative process of one with the exploratory optimisation of the other.

Generalized Partition Crossover (GPX) is a deterministic recombination operator developed for the Traveling Salesman Problem. Partition crossover operators return the best of [Formula: see text] reachable offspring, where [Formula: see text] is the number of recombining components. This article introduces a new GPX2 operator, which finds more recombining components than GPX or Iterative Partial Transcription (IPT). We also show that GPX2 has O([Formula: see text]) runtime complexity, while also introducing new enhancements to reduce the execution time of GPX2. Finally, we experimentally demonstrate the efficiency of GPX2 when it is used to improve solutions found by the multitrial Lin-Kernighan-Helsgaum (LKH) algorithm. Significant improvements in performance are documented on large ([Formula: see text]) and very large ([Formula: see text]) instances of the Traveling Salesman Problem.

Mass production and use of antibiotics has led to the rise of resistant bacteria, a problem possibly exacerbated by inappropriate and non-optimal application. Antibiotic treatment often follows fixed-dose regimens, with a standard dose of antibiotic administered equally spaced in time. But are such fixed-dose regimens optimal or can alternative regimens be designed to increase efficacy? Yet, few mathematical models have aimed to identify optimal treatments based on biological data of infections inside a living host. In addition, assumptions to make the mathematical models analytically tractable limit the search space of possible treatment regimens (e.g. to fixed-dose treatments). Here, we aimed to address these limitations by using experiments in a Galleria mellonella (insect) model of bacterial infection to create a fully parametrised mathematical model of a systemic Vibrio infection. We successfully validated this model with biological experiments, including treatments unseen by the mathematical model. Then, by applying artificial intelligence, this model was used to determine optimal antibiotic dosage regimens to treat the host to maximise survival while minimising total antibiotic used. As expected, host survival increased as total quantity of antibiotic applied during the course of treatment increased. However, many of the optimal regimens tended to follow a large initial 'loading' dose followed by doses of incremental reductions in antibiotic quantity (dose 'tapering'). Moreover, application of the entire antibiotic in a single dose at the start of treatment was never optimal, except when the total quantity of antibiotic was very low. Importantly, the range of optimal regimens identified was broad enough to allow the antibiotic prescriber to choose a regimen based on additional criteria or preferences. Our findings demonstrate the utility of an insect host to model antibiotic therapies in vivo and the approach lays a foundation for future regimen optimisation for patient and societal benefits.

Partition Crossover is a recombination operator for pseudo-Boolean optimization with the ability to explore an exponential number of solutions in linear or square time. It decomposes the objective function as a sum of subfunctions, each one depending on a different set of variables. The decomposition makes it possible to select the best parent for each subfunction independently and the operator provides the best out of 2q solutions, where q is the number of sub-functions in the decomposition. These subfunctions are defined over the connected components of the recombination graph: a subgraph of the objective function variable interaction graph containing only the differing variables in the two parents. In this paper, we advance further and propose a new way to increase the number of linearly independent subfunctions by analyzing the articulation points of the recombination graph. These points correspond to variables that, once flipped, increase the number of connected components. The presence of a connected component with an articulation point increases the number of explored solutions by a factor of, at least, 4. We evaluate the new operator using Iterated Local Search combined with Partition Crossover to solve NK Landscapes and MAX-SAT.

We conduct a study of local optima networks (LONs) in a search space using fractal dimensions. The fractal dimension (FD) of these networks is a complexity index which assigns a non-integer dimension to an object. We propose a fine-grained approach to obtaining the FD of LONs, using the probabilistic search transitions encoded in LON edge weights. We then apply multi-fractal calculations to LONs for the first time, comparing with mono-fractal analysis. For complex systems such as LONs, the dimensionality may be different between two sub-systems and multi-fractal analysis is needed. Here we focus on the Quadratic Assignment Problem (QAP), conducting fractal analyses on sampled LONs of reasonable size for the first time. We also include fully enumerated LONs of smaller size. Our results show that local optima spaces can be multi-fractal and that valuable information regarding probabilistic self-similarity is encoded in the edge weights of local optima networks. Links are drawn between these phenomena and the performance of two competitive metaheuristic algorithms.

A variety of meta-heuristic search algorithms have been introduced for optimising software release planning. However, there has been no comprehensive empirical study of different search algorithms across multiple different real-world datasets. In this article, we present an empirical study of global, local, and hybrid meta- and hyper-heuristic search-based algorithms on 10 real-world datasets. We find that the hyper-heuristics are particularly effective. For example, the hyper-heuristic genetic algorithm significantly outperformed the other six approaches (and with high effect size) for solution quality 85% of the time, and was also faster than all others 70% of the time. Furthermore, correlation analysis reveals that it scales well as the number of requirements increases.

Local Optima Networks were proposed to understand the structure of combinatorial landscapes at a coarse-grained level. We consider a compressed variant of such networks with features that are meaningful for the study of search difficulty in the context of local search. In particular, we investigate different landscapes of the Permutation Flowshop Scheduling Problem. The insert and 2-exchange neighbourhoods are considered, and two different objective functions are taken into account: the makespan and the total flow time. The aim is to analyse the network features in order to find differences between the landscape structures, giving insights about which features impact algorithm performance. We evaluate the correlation between landscape properties and the performance of an Iterated Local Search algorithm. Visualisation of the network structure is also given, where evident differences between the makespan and total flow time are observed.

In gray-box optimization, the search algorithms have access to the variable interaction graph (VIG) of the optimization problem. For Mk Landscapes (and NK Landscapes) we can use the VIG to identify an improving solution in the Hamming neighborhood in constant time. In addition, using the VIG, deterministic Partition Crossover is able to explore an exponential number of solutions in a time that is linear in the size of the problem. Both methods have been used in isolation in previous search algorithms. We present two new gray-box algorithms that combine Partition Crossover with highly efficient local search. The best algorithms are able to locate the global optimum on Adjacent NK Landscape instances with one million variables. The algorithms are compared with a state-of-the-art algorithm for pseudo-Boolean optimization: Gray-Box Parameterless Population Pyramid. The results show that the best algorithm is always one combining Partition Crossover and highly efficient local search. But the results also illustrate that the best optimizer differs on Adjacent and Random NK Landscapes.

Recent work discovered that fitness landscapes induced by Iterated Local Search (ILS) may consist of multiple clusters, denoted as funnels or communities of local optima. Such studies exist only for perturbation operators (kicks) with low strength. We examine how different strengths of the ILS perturbation operator affect the number and size of clusters. We present an empirical study based on local optima networks from NK fitness landscapes. Our results show that a properly selected perturbation strength can help overcome the effect of ILS getting trapped in clusters of local optima. This has implications for designing effective ILS approaches in practice, where traditionally only small perturbations or complete restarts are applied, with the middle ground of intermediate perturbation strengths largely unexplored.

The existence of sub-optimal funnels in combinatorial fitness landscapes has been linked to search difficulty. The exact nature of these structures --- and how commonly they appear --- is not yet fully understood. Improving our understanding of funnels could help with designing effective diversification mechanisms for a 'smoothing' effect, making optimisation easier. We model fitness landscapes as local optima networks. The relationship between communities of local optima found by network clustering algorithms and funnels is explored. Funnels are identified using the notion of monotonic sequences from the study of energy landscapes in theoretical chemistry. NK Landscapes and the Quadratic Assignment Problem are used as case studies. Our results show that communities are linked to funnels. The analysis exhibits relationships between these landscape structures and the performance of trajectory-based metaheuristics such as Simulated Annealing (SA) and Iterated Local Search (ILS). In particular, ILS gets trapped in funnels, and modular communities of optima slow it down. The funnels contribute to lower success for SA. We show that increasing the strength of ILS perturbation helps to 'smooth' the funnels and improves performance in multi-funnel landscapes.

Automatic Programming has long been a sub-goal of Artificial Intelligence (AI). It is feasible in limited domains. Genetic Improvement (GI) has expanded these dramatically to more than 100 000 lines of code by building on human written applications. Further scaling may need key advances in both Search Based Software Engineering (SBSE) and Evolutionary Computation (EC) research, particularly on representations, genetic operations, fitness landscapes, fitness surrogates, multi objective search and co-evolution.

We conduct an analysis of local optima networks extracted from fitness landscapes of the Kauffman NK model under iterated local search. Applying the Markov Cluster Algorithm for community detection to the local optima networks, we find that the landscapes consist of multiple clusters. This result complements recent findings in the literature that landscapes often decompose into multiple funnels, which increases their difficulty for iterated local search. Our results suggest that the number of clusters as well as the size of the cluster in which the global optimum is located are correlated to the search difficulty of landscapes. We conclude that clusters found by community detection in local optima networks offer a new way to characterize the multi-funnel structure of fitness landscapes.

The global structure of travelling salesman's fitness landscapes has recently revealed the presence of multiple 'funnels'. This implies that local optima are organised into several clusters, so that a particular local optimum largely belongs to a particular funnel. Such a global structure can increase search difficulty, especially, when the global optimum is located in a deep, narrow funnel. Our study brings more precision (and dimensions) to the notion of funnels with a data-driven approach using Local Optima Networks and the Chained Lin-Kernighan heuristic. We start by exploring the funnel `floors', characterising them using the notion of communities from complex networks. We then analyse the more complex funnel `basins'. Since their depth is relevant to search, we visualise them in 3D. Our study, across a set of TSP instances, reveals a multi-funnel structure in most of them. However, the specific topology varies across instances and relates to search difficulty. Finally, including a stronger perturbation into Chained Lin-Kernighan proved to smooth the funnel structure, reducing the number of funnels and enlarging the valley leading to global optima.

First paragraph: In combinatorial optimization, the goal is to find an optimal solution, according to some objective function, from a discrete search space. These problems arise widely in industry and academia and, unfortunately, many of them are NP-hard and no polynomial time algorithm can guarantee their solution to a certified optimality unless. Therefore, in the last decades researchers have investigated the use of stochastic search algorithms to find near optimal solutions to these problems. In particular, great research efforts have been devoted to the development and application of metaheuristic algorithms to solve combinatorial optimization problems.

In this work we conduct a comparative study of several publicly available, state-of-the-art hyper-heuristics for HyFlex in order to assess their generality across domains. To this purpose we extend the HyFlex benchmark set with 3 new problem domains: The 0-1 Knap Sack, Quadratic Assignment and Max-Cut Problem. To our knowledge, this is the first public extension of the benchmark since the CHeSC 2011 competition. In addition, this is the first study testing the Fair-Share Iterated Local Search (FS-ILS) method, designed in prior research, using a semi-automated design approach, on new unseen problem domains. We show that, of the methods compared, Adap-HH (CHeSC 2011 winner) clearly perfoms the most consistently, overall. In addition, we identify a weakness of, as well as a way to further simplify the FS-ILS method. Finally, we found that, overall, the state-of-the-art methods compared, generalized much better than a naive baseline.

Local optima networks are a recent model of fitness landscapes. They compress the landscape by representing local optima as nodes, and search transitions among them as edges. Previous local optima networks considered transitions based on mutation; this study looks instead at transitions based on deterministic recombination. We define and analyse networks based on the recently proposed partition crossover for k-bounded pseudo-Boolean functions, using NKq landscapes as a case study. Partition crossover was initially proposed for the travelling salesman problem, where it was found to ``tunnel" between local optima, i.e., jump from local optimum to local optimum. Our network analysis shows that this also happens for NK landscapes: local optima are densely connected via partition crossover. We found marked differences between the adjacent and random interaction NK models. Surprisingly, with the random model, instances have a lower number of local optima on average, but their networks are more sparse and decompose into several clusters. There is also large variability in the size and pattern of connectivity of instances coming from the same landscape parameter values. These network features offer new insight informing why some instances are harder to solve than others.

The Next Release Problem involves determining the set of requirements to implement in the next release of a software project. When the problem was first formulated in 2001, Integer Linear Programming, an exact method, was found to be impractical because of large execution times. Since then, the problem has mainly been addressed by employing metaheuristic techniques. In this paper, we investigate if the single-objective and bi-objective Next Release Problem can be solved exactly and how to better approximate the results when exact resolution is costly. We revisit Integer Linear Programming for the single-objective version of the problem. In addition, we integrate it within the Epsilon-constraint method to address the bi-objective problem. We also investigate how the Pareto front of the bi-objective problem can be approximated through an anytime deterministic Integer Linear Programming-based algorithm when results are required within strict runtime constraints. Comparisons are carried out against NSGA-II. Experiments are performed on a combination of synthetic and real-world datasets. We show that a modern Integer Linear Programming solver is now a viable method for this problem. Large single objective instances and small bi-objective instances can be solved exactly very quickly. On large bi-objective instances, execution times can be significant when calculating the complete Pareto front. However, good approximations can be found effectively. This study suggests that (1) approximation algorithms can be discarded in favor of the exact method for the single-objective instances and small bi-objective instances, (2) the Integer Linear Programming-based approximate algorithm outperforms the NSGA-II genetic approach on large bi-objective instances, and (3) the run times for both methods are low enough to be used in real-world situations.

Evolvability metrics gauge the potential for fitness of an individual rather than fitness itself. They measure the local characteristics of the fitness landscape surrounding a solution. In adaptive operator selection the goal is to dynamically select from a given pool the operator to apply next during the search process. An important component of these adaptive schemes is credit assignment, whereby operators are rewarded according to their observed performance. This article brings the notion of evolvability to adaptive operator selection, by proposing an autonomous search algorithm that rewards operators according to their potential for fitness rather than their immediate fitness improvement. The approach is tested within an evolutionary algorithm framework featuring several mutation operators on binary strings. Three benchmark problems of increasing difficulty, Onemax, Royal Staircase and Multiple Knapsack are considered. Experiments reveal that evolvability metrics significantly improve the performance of adaptive operator selection, when compared against standard fitness improvement metrics.The main contribution is to effectively use fitness landscape metrics to guide a self-configuring algorithm.

The Generalized Partition Crossover (GPX) constructs new solutions for the Traveling Salesman Problem (TSP) by finding recombining partitions with one entry and one exit in the graph composed by the union of two parent solutions. If there are k recombining partitions in the union graph, 2^k-2 solutions are simultaneously exploited by GPX. Generalized Asymmetric Partition Crossover (GAPX) is introduced; it finds more recombining partitions and can also find partitions for the asymmetric TSP. GAPX does this by locating partitions that cut vertices of degree 4 in the union graph and by finding partitions with multiple entry and exit points, both in O(n) time. GAPX can improve the quality of solutions generated by the Lin-Kernighan-Helsgaun heuristic and improve the state of the art for the asymmetric TSP.

Local Optima Networks (LONs) have been recently proposed as an alternative model of combinatorial fitness landscapes. The model compresses the information given by the whole search space into a smaller mathematical object that is the graph having as vertices the local optima and as edges the possible weighted transitions between them. A new set of metrics can be derived from this model that capture the distribution and connectivity of the local optima in the underlying configuration space. This paper departs from the descriptive analysis of local optima networks, and actively studies the correlation between network features and the performance of a local search heuristic. The NK family of landscapes and the Iterated Local Search metaheuristic are considered. With a statistically-sound approach based on multiple linear regression, it is shown that some LONs' features strongly influence and can even partly predict the performance of a heuristic search algorithm. This study validates the expressive power of LONs as a model of combinatorial fitness landscapes.

Heuristic search algorithms have been successfully applied to solve many problems in practice. Their design, however, has increased in complexity as the number of parameters and choices for operators and algorithmic components is also expanding. There is clearly the need for providing the final user with automated tools to assist the tuning, design and assessment of heuristic optimisation methods. In recent years a growing number workshops and tracks has been held to address these issues. In 2010, the Parallel Problem Solving from Nature (PPSN) conference hosted two workshops, which decided to joint efforts to organise this journal special issue. The workshop “Self-Tuning, Self-Configuring and Self-Generating Search Heuristics,” distinguished three general processes in automated heuristic design: 1) tuning: the process of adjusting the algorithm's control parameters, 2) configuring: the process of selecting and using existing algorithmic components such as search operators, construction heuristics or acceptance criteria, and 3) generating: the process of creating altogether new heuristics (or heuristic components) from the basic sub-components of previously existing methods. Machine learning, meta-modelling and multilevel search approaches can and have been applied to automate these three processes. The workshop introduced the term ‘Self-* Search’, which is now the name of a track in GECCO, which started in 2011 and is also being held this year. The other workshop “Methods for the Assessment of Computational Systems” stressed the idea that the experimental analysis of computational systems inspired by nature can be made more sound and effective by the use of appropriate experimental methods. More severe requirements have been transmitted to draw objective conclusions from computational experiments, while at the same time the design and configuration of the computational systems can be improved by profitable ways of looking into the data collected.The quest for methods to automate the design and assessment of heuristic search methods is spawning a considerable amount of interdisciplinary research, mainly between the fields of computer science, artificial intelligence, optimization, statistics and machine learning. This special issue gathers contributions at the interface of these topics. It comprises five high quality papers that were selected after a rigorous reviewing process.The first two articles are related to the automatic, online configuration of heuristic search methods. Adaptive memetic algorithms (Ong et al., 2006) and selective hyper-heuristics (Burke et al., 2010) have developed separately. However, they share key research issues. In particular, they need to provide adaptive mechanisms to autonomously guide the choice of operators during the search. In the case of memetic algorithms, the choice is among a set of memes, which are generally local search heuristics. In the case of hyper-heuristics, the choice may involve different types of heuristics, such as constructive heuristics, mutational heuristics or neighborhood moves, crossovers and local search heuristics. Both algorithmic schemes require mechanisms for assigning rewards to operators according to their past performance and select which operator to apply at each decision point according to the computed qualities. These mechanisms have been also studied within the evolutionary computation community using the term Adaptive Operator Selection (Fialho et al., 2010).The first paper, “Estimating Meme Fitness in Adaptive Memetic Algorithms for Combinatorial Problems” by J. Smith studies two fundamental issues when assigning credit to search operators. First, whether it is better to assign credit to a meme based on an estimate of the extreme, or the mean benefit it causes. It has been found that, when the operator choice is related to mutation in a standard evolutionary algorithm, “extremal” versions that reward occasional large jumps rather than small steady improvements, produce better results. However, in the case of memes, which by design cause local improvement, the opposite was found in this study. The second issue concerns whether the aggregation of feedback from the search process should be global or local to some part of the solution space. Results suggest that local reward schemes outperform their global counterparts in combinatorial spaces, in contrast to continuous spaces. This study therefore confirms that the performance of credit assignment mechanisms depends on both the nature of the search space and the type of search operator.The paper “Hyper-Heuristics with Low Level Parameter Adaptation” by Z. Ren, H. Jiang, J. Xuan, and Z. Luo incorporates a search-based mechanism for adapting the parameters of the low-level heuristics in a hyper-heuristic framework. Traditionally, selective hyper-heuristics adaptively select the choice of fixed low-level heuristics. But clearly, some of these heuristics are parameterised (for example, the rate of a mutation operator). The proposed framework, then, simultaneously adapt the choice of low-level heuristics and their parameters, with improved results. It also proposes a mechanisms to separate the low-level heuristics into intensification and diversification heuristics, which helps to reduce the heuristic search space and improves efficiency.Parameter tuning of evolutionary algorithms is attracting more and more interest. In particular, the Sequential Parameter Optimization (SPO) is an established parameter tuning framework (Bartz-Beielstein et al., 2005). It uses the available budget (e.g., number of function evaluations) sequentially. Information from the exploration of the search space guides the search by building meta models. New design points are determined based on predictions from these meta models. The meta models are refined stepwise to improve knowledge about the search space. SPO provides techniques to cope with noise and guarantees comparable confidence for search points. It collects information to learn from this tuning process, e.g., integrated exploratory data analysis and provides mechanisms both for interactive and automated tuning. The following two papers discuss essential ways to improve SPO related algorithms by embedding transformations and resampling techniques. Their results are in no way restricted to parameter tuning or SPO.Since data from optimization runs are non-normal, transformations are tools of choice. The paper “On the Effect of Response Transformations in Sequential Parameter Optimization,” by T. Wagner and S. Wessing enhances the SPO framework by introducing transformation steps before the actual modeling. Based on design-of-experiments techniques, they analyze the effect of integrating different transformations. They demonstrate that in particular a rank transformation of the responses provides significant improvements. A deeper analysis of the resulting models and additional experiments with adaptive procedures indicate that the rank and the Box-Cox transformation are able to improve the properties of the result distributions with respect to symmetry and normality of the residuals.The paper “Resampling Methods for Meta-Model Validation, with Recommendations for Evolutionary Computation” by B. Bischl, O. Mersmann, H. Trautmann, and C. Weihs summarizes basic resampling methods from statistics, puts them into the context of meta-model validation and extensively discusses their advantages and disadvantages together with common pitfalls users shall avoid. Meta-model validation is then discussed as a supportive technique within evolutionary algorithms, also providing some concrete examples.Finally, the paper “An Experimental Approach to the Comparison of Continuous Metaheuristics Based on Landscape Topology” by R. Morgan and M. Gallagher extends previous work of the authors on Max-Set of Gaussians (MSG) problem generators. Two Estimation of Distribution type Evolutionary Algorithms (EDA) with different abilities to adapt to problem properties are compared on various randomly determined ridge landscapes, which are constructed by means of a modification of the MSG generator. The article also suggests two visualization tools that shall be helpful for the experimental analysis of non-deterministic optimization algorithms: heatmaps and parameterized difference plots. After detecting typical landscapes that favor either one or the other algorithm, the authors undertake a meta-search in the problem parameter space, maximizing the performance difference of the algorithms, thereby further enhancing the algorithm-problem interaction knowledge for this case.The guest editors wish to thank the contributing authors for their interesting submissions and the reviewers for their constructive feedback and detailed comments. We hope this special issue will promote the cross-fertilisation of ideas in assessing the performance and designing more autonomous and user-friendly heuristic search algorithms.

We propose two adaptive variants of a multiple neighborhood iterated local search algorithm. These variants employ online learning techniques, also called adaptive operation selection, in order to select which perturbation to apply at each iteration step from a set of available move operators. Using a common software interface (the HyFlex framework), the proposed algorithms are tested across four hard combinatorial optimisation problems: permutation flow shop, 1D bin packing, maximum satisfiability, and personnel scheduling (including instance data from real-world industrial applications). Using the HyFlex framework, exactly the same high level search strategy can be applied to all the domains and instances. Our results confirm that the adaptive variants outperform a baseline iterated local search with uniform random selection of the move operators. We argue that the adaptive algorithms proposed are general yet powerful, and contribute to the goal of increasing the generality and applicability of heuristic search.

The Traveling Salesman Problem (TSP) is known to display an elementary landscape under all k-opt move operators. Previous work has also shown that partial neighborhoods may exist that retain some properties characteristic of elementary landscapes. For a tour of n cities, we show that the 2-opt neighborhood can be decomposed into n/2-1 partial neighborhoods. While this paper focuses on the TSP, it also introduces a more formal treatment of partial neighborhoods which applies to all elementary landscapes. Tracking partial neighborhood averages in elementary landscapes requires partitioning the cost matrix. After every move in the search space, the relevant partitions must be updated. However, just as the evaluation function allows a partial update for the TSP, there also exists a partial update for the cost matrix partitions. By only looking at a subset of the partial neighborhoods we can further reduce the cost of updating the cost matrix partitions.

In previous work, we have introduced a network based model that abstracts many details of the underlying landscape and compresses the landscape information into a weighted, oriented graph which we call the local optima network. The vertices of this graph are the local optima of the given fitness landscape, while the arcs are transition probabilities between local optima basins. Here, we extend this formalism to neutral fitness landscapes, which are common in difficult combinatorial search spaces. The study is based on two neutral variants of the well-known NK family of landscapes (where N stands for the chromosome length, and K for the number of gene epistatic interactions within the chromosome). By using these two NK variants, probabilistic (NKp), and quantified NK (NKq), in which the amount of neutrality can be tuned by a parameter, we show that our new definitions of the optima networks and the associated basins are consistent with the previous definitions for the non-neutral case. Moreover, our empirical study and statistical analysis show that the features of neutral landscapes interpolate smoothly between landscapes with maximum neutrality and non-neutral ones. We found some unknown structural differences between the two studied families of neutral landscapes. But overall, the network features studied confirmed that neutrality, in landscapes with percolating neutral networks, may enhance heuristic search. Our current methodology requires the exhaustive enumeration of the underlying search space. Therefore, sampling techniques should be developed before this analysis can have practical implications. We argue, however, that the proposed model offers a new perspective into the problem difficulty of combinatorial optimization problems and may inspire the design of more effective search heuristics.

An important challenge within hyper-heuristic research is to design search methodologies that work well, not only across different instances of the same problem, but also across different problem domains. This article conducts an empirical study involving three different domains in combinatorial optimisation: bin packing, permutation flow shop and personnel scheduling. Using a common software interface (HyFlex), the same algorithms (high-level strategies or hyper-heuristics) can be readily run on all of them. The study is intended as a proof of concept of the proposed interface and domain modules, as a benchmark for testing the generalisation abilities of heuristic search algorithms. Several algorithms and variants from the literature were implemented and tested. From them, the implementation of iterated local search produced the best overall performance. Interestingly, this is one of the most conceptually simple competing algorithms, its advantage as a robust algorithm is probably due to two factors: (i) the simple yet powerful exploration/exploitation balance achieved by systematically combining a perturbation followed by local search; and (ii) its parameter-less nature. We believe that the challenge is still open for the design of robust algorithms that can learn and adapt to the available low-level heuristics, and thus select and apply them accordingly.

Using a recently proposed model for combinatorial landscapes, Local Optima Networks (LON), we conduct a thorough analysis of two types of instances of the Quadratic Assignment Problem (QAP). This network model is a reduction of the landscape in which the nodes correspond to the local optima, and the edges account for the notion of adjacency between their basins of attraction. The model was inspired by the notion of `inherent network' of potential energy surfaces proposed in physical-chemistry. The local optima networks extracted from the so called uniform and real-like QAP instances, show features clearly distinguishing these two types of instances. Apart from a clear confirmation that the search difficulty increases with the problem dimension, the analysis provides new confirming evidence explaining why the real-like instances are easier to solve exactly using heuristic search, while the uniform instances are easier to solve approximately. Although the local optima network model is still under development, we argue that it provides a novel view of combinatorial landscapes, opening up the possibilities for new analytical tools and understanding of problem difficulty in combinatorial optimization.

Hyper-heuristics or ldquoheuristics to chose heuristicsrdquo are an emergent search methodology that seeks to automate the process of selecting or combining simpler heuristics in order to solve hard computational search problems. The distinguishing feature of hyper-heuristics, as compared to other heuristic search algorithms, is that they operate on a search space of heuristics rather than directly on the search space of solutions to the underlying problem. Therefore, a detailed understanding of the properties of these heuristic search spaces is of utmost importance for understanding the behaviour and improving the design of hyper-heuristic methods. Heuristics search spaces can be studied using the metaphor of fitness landscapes. This paper formalises the notion of hyper-heuristic landscapes and performs a landscape analysis of the heuristic search space induced by a dispatching-rule-based hyper-heuristic for production scheduling. The studied hyper-heuristic spaces are found to be ldquoeasyrdquo to search. They also exhibit some special features such as positional bias and neutrality. It is argued that search methods that exploit these features may enhance the performance of hyper-heuristics.

We propose a variation of the standard genetic algorithm that incorporates social interaction between the individuals in the population. Our goal is to understand the evolutionary role of social systems and its possible application as a non-genetic new step in evolutionary algorithms. In biological populations, i.e. animals, even human beings and microorganisms, social interactions often affect the fitness of individuals. It is conceivable that the perturbation of the fitness via social interactions is an evolutionary strategy to avoid trapping into local optimum, thus avoiding a fast convergence of the population. We model the social interactions according to Game Theory. The population is, therefore, composed by cooperator and defector individuals whose interactions produce payoffs according to well known game models (prisoner's dilemma, chicken game, and others). Our results on Knapsack problems show, for some game models, a significant performance improvement as compared to a standard genetic algorithm.

Hyper-heuristics can be thought of as "heuristics to choose heuristics". They are concerned with adaptively finding solution methods, rather than directly producing a solution for the particular problem at hand. Hence, an important feature of hyper-heuristics is that they operate on a search space of heuristics rather than directly on a search space of problem solutions. A motivating aim is to build systems which are fundamentally more generic than is possible today. Understanding the structure of these heuristic search spaces is therefore, a research direction worth exploring. In this paper, we use the notion of fitness landscapes in the context of constructive hyper-heuristics. We conduct a landscape analysis on a heuristic search space conformed by sequences of graph coloring heuristics for timetabling. Our study reveals that these landscapes have a high level of neutrality and positional bias. Furthermore, although rugged, they have the encouraging feature of a globally convex or big valley structure, which indicates that an optimal solution would not be isolated but surrounded by many local minima. We suggest that using search methodologies that explicitly exploit these features may enhance the performance of constructive hyper-heuristics.

We propose a network characterization of combinatorial fitness landscapes by adapting the notion of inherent networks proposed for energy surfaces (Doye, 2002). We use the well-known family of $NK$ landscapes as an example. In our case the inherent network is the graph where the vertices are all the local maxima and edges mean basin adjacency between two maxima. We exhaustively extract such networks on representative small NK landscape instances, and show that they are 'small-worlds'. However, the maxima graphs are not random, since their clustering coefficients are much larger than those of corresponding random graphs. Furthermore, the degree distributions are close to exponential instead of Poissonian. We also describe the nature of the basins of attraction and their relationship with the local maxima network.

The error threshold of replication is an important notion in the quasispecies evolution model; it is a critical mutation rate (error rate) beyond which structures obtained by an evolutionary process are destroyed more frequently than selection can reproduce them. With mutation rates above this critical value, an error catastrophe occurs and the genomic information is irretrievably lost. Therefore, studying the factors that alter this magnitude has important implications in the study of evolution. Here we use a genetic algorithm, instead of the quasispecies model, as the underlying model of evolution, and explore whether the phenomenon of error thresholds is found on finite populations of bit strings evolving on complex landscapes. Our empirical results verify the occurrence of error thresholds in genetic algorithms. In this way, this notion is brought from molecular evolution to evolutionary computation. We also study the effect of modifying the most prominent evolutionary parameters on the magnitude of this critical value, and found that error thresholds depend mainly on the selection pressure and genotype length.

A methodology using heuristic search methods is proposed for optimizing cancer chemotherapies with drugs acting on a specific phase of the cell cycle. Specifically, two evolutionary algorithms, and a simulated annealing method are considered. The methodology relies on an underlying mathematical model for tumor growth that includes cycle phase specificity, and multiple applications of a single cytotoxic agent. The goal is to determine effective protocols for administering the agent, so that the tumor is eradicated, while the immune system remains above a given threshold. Results confirm that modern heuristic methods are a good choice for optimizing complex systems. The three algorithms considered produced effective solutions, and provided drug schedules suitable for practice, although some methods excelled others in performance. A discussion of comparative results is presented.