Search

The Traveling Thief Problem (TTP) is a relatively new benchmark problem created to study problems which consist of interdependent subproblems. In this paper we investigate what the fitness landscape characteristics are of some smaller instances of the TTP with commonly used local search operators in the context of metaheuristics that uses local search. The local search operators include: 2-opt, Insertion, Bitflip and Exchange and metaheuristics include: multi-start local search, iterated local search and genetic local search. Fitness landscape analysis shows among other things that TTP instances contain a lot of local optima but their distance to the global optimum is correlated with its fitness. Local optima networks with respect to an iterated local search reveals that TTP has a multi-funnel structure. Other experiments show that a steady state genetic algorithm with edge assembly crossover outperforms multi-start local search, iterated local search and genetic algorithms with different tour crossovers. At last we performed a comparative study using the genetic algorithm with edge assembly crossover on relatively larger instances of the commonly used benchmark suite. As a result we found new best solutions to almost all studied instances.

Bayesian networks (BNs) are probabilistic graphical models which are widely used for knowledge representation and decision making tasks, especially in the presence of uncertainty. Finding or learning the structure of BNs from data is an NP-hard problem. Evolutionary algorithms (EAs) have been extensively used to automate the learning process. In this paper, we consider the use of the Gene-Pool Optimal Mixing Evolutionary Algorithm (GOMEA). GOMEA is a relatively new type of EA that belongs to the class of model-based EAs. The model used in GOMEA is aimed at modeling the dependency structure between problem variables, so as to improve the efficiency and effectiveness of variation. This paper shows that the excellent performance of GOMEA transfers from well-known academic benchmark problems to the specific case of learning BNs from data due to its model-building capacities and the potential to compute partial evaluations when learning BNs. On commonly-used datasets of varying size, we find that GOMEA outperforms standard algorithms such as Order-based search (OBS), as well as other EAs, such as Genetic Algorithms (GAs) and Estimation of Distribution algorithms (EDAs), even when efficient local search techniques are added.

Genetic algorithms (GAs) are powerful combinatorial optimizers that are able to find close-to-optimal solutions for difficult problems by applying the paradigm of adaptation through Darwinian evolution. We describe a framework for GAs capable of solving certain optimization problems encountered in geographical information systems (GISs). The framework is especially suited for geographical problems since it is able to exploit their geometrical structure with a novel operator called the geometrically local optimizer. Three such problems are presented as case studies: map labeling, generalization while preserving structure, and line simplification. Experiments show that the GAs give good results and are flexible as well.

Genepool Optimal Mixing Evolutionary Algorithms (GOMEAs) were recently proposed as a new way of designing linkage-friendly, efficiently-scalable evolutionary algorithms (EAs). GOMEAs combine the building of linkage models with an intensive, greedy mixing procedure. Recent results indicate that the use of hierarchical linkage models in GOMEAs lead to the most robust and efficient performance. Two of such GOMEA instances are the Linkage Tree Genetic Algorithm (LTGA) and the Multi-scale Linkage Neighbors Genetic Algorithm (MLNGA). The linkage models in these GOMEAs have their individual merits and drawbacks. In this paper, we propose enhancement techniques targeted at filtering out superfluous linkage sets from hierarchical linkage models and we consider a way to construct a linkage model that combines the strengths of different linkage models. We then propose a new GOMEA instance, called the Linkage Trees and Neighbors Genetic Algorithm (LTNGA), that combines the models of LTGA and MLNGA. LTNGA performs comparable or better than the best of either LTGA or MLNGA on various problems, including typical linkage benchmark problems and instances of the well-known combinatorial problem MAXCUT, especially when the proposed filtering techniques are used.

Mixing of partial solutions is a key mechanism used for creating new solutions in many Genetic Algorithms (GAs). However, this mixing can be disruptive and generate improved solutions inefficiently. Exploring a problem's structure can help in establishing less disruptive operators, leading to more efficient mixing. One way of using a problem's structure is to consider variable linkage information. Once a proper linkage model for a problem is obtained, mixing becomes more efficient.This paper focuses on exploring different methods of building family of subsets (FOS) linkage models, which are then used with the Gene-pool Optimal Mixing Evolutionary Algorithm (GOMEA) to solve MAX-SAT problems. Individual algorithms from the GOMEA family are distinguished by how the FOS linkage models are constructed. The Linkage Tree Genetic Algorithm (LTGA) is a GOMEA instance which learns the linkage between problem variables by building a linkage tree in every generation. In this paper, we introduce SAT-GOMEA. This algorithm uses a predetermined FOS linkage model based on the SAT-problem's definition. Both algorithms use linkage information. We show that because of this information they are capable of performing significantly better than other algorithms from the GOMEA family which do not explore linkage. In a black-box (BBO) setting, LTGA performs well. We further study the use of linkage models outside of the typical BBO approach by examining the behavior of LTGA and the problem-specific SAT-GOMEA in a white-box setting, where more of the problem information is known. We show that with this white-box optimization (WBO) approach, exploring linkage information can still be beneficial.We further compare the performance of these algorithms with a selection of non-GOMEA based algorithms. From the BBO perspective, we compare LTGA with the well-known hBOA. In the WBO setting, many very efficient problem-specific local search (LS) algorithm exist. We specifically consider Walksat and GSAT and show that combining LS with LTGA or SAT-GOMEA increases their performance.

For an evolutionary algorithm (EA) to be efficiently scalable, variation must be linkage friendly. For this reason many EAs have been introduced that build and exploit linkage models, amongst which are estimation-of-distribution algorithms (EDAs). Although various models have been empirically evaluated, it remains of key importance to better understand the conditions under which model building is successful. In this paper, we consider the linkage tree genetic algorithm (LTGA). LTGA is a recent powerful linkage-learning EA that builds a hierarchical linkage model known as the linkage tree (LT). LTGA exploits this model using an intensive mixing procedure aimed at optimally exchanging building blocks. Empirical evaluation studies of LTGA have appeared in literature using different entropy-based measures for building the LT, but with comparable results. We study the differences in these measures to better understand the requirements for detecting important linkage information and point out why some measures are more successful than others.

We define the linkage model evolvability and the evolvability-based fitness distance correlation. These measures give an insight in the search characteristics of linkage model building genetic algorithms. We apply them on the linkage tree genetic algorithm for deceptive trap functions and the nearest-neighbor NK-landscape problem. Comparisons are made between linkage trees, based on mutual information, and random trees which ignore similarity in the population. On a deceptive trap function, the measures clearly show that by learning the linkage tree the problem becomes easy for the LTGA. On the nearest-neighbor NK-landscape the evolvability analysis shows that the LTGA does capture enough of the structure of the problem to solve it reliably and efficiently even though the linkage tree cannot represent the overlapping epistatic information in the NK-problem. The linkage model evolvability measure and the evolvability-based fitness distance correlation prove to be useful tools to get an insight into the search properties of linkage model building genetic algorithms.

We discuss the use of online learning of the local search neighborhood. Specifically, we consider the Linkage Tree Genetic Algorithm (LTGA), a population-based, stochastic local search algorithm that learns the neighborhood by identifying the problem variables that have a high mutual information in a population of good solutions. The LTGA builds each generation a linkage tree using a hierarchical clustering algorithm. This bottom-up hierarchical clustering is computationally very efficient and runs in O(n2). Each node in the tree represents a specific cluster of problem variables. When generating new solutions, these linked variables specify the neighborhood where the LTGA searches for better solutions by sampling values for these problem variables from the current population. To demonstrate the use of learning the neighborhood we experimentally compare iterated local search (ILS) with the LTGA on a hard discrete problem, the nearest-neighbor NK-landscape problem with maximal overlap. Results show that the LTGA is significantly superior to the ILS, proving that learning the neighborhood during the search can lead to a considerable gain in search performance.

The linkage tree genetic algorithm (LTGA) identifies linkages between problem variables using an agglomerative hierarchical clustering algorithm and linkage trees. This enables LTGA to solve many decomposable problems that are difficult with more conventional genetic algorithms. The goal of this paper is two-fold: (1) Present a thorough empirical evaluation of LTGA on a large set of problem instances of additively decomposable problems and (2) speed up the clustering algorithm used to build the linkage trees in LTGA by using a pairwise and a problem-specific metric.

The inclusion of local search (LS) techniques in evolutionary algorithms (EAs) is known to be very important in order to obtain competitive results on combinatorial and real-world optimization problems. Often however, an important source of the added value of LS is an understanding of the problem that allows performing a partial evaluation to compute the change in quality after only small changes were made to a solution. This is not possible in a Black-Box Optimization (BBO) setting. Here we take a closer look at the added value of LS when combined with EAs in a BBO setting. Moreover, we consider the interplay with model building, a technique commonly used in Estimation-of-Distribution Algorithms (EDAs) in order to increase robustness by statistically detecting and exploiting regularities in the optimization problem. We find, using two standardized hard BBO problems from EA literature, that LS can play an important role, especially in the interplay with model building in the form of what has become known as substructural LS. However, we also find that optimal mixing (OM), which indicates that operations in a variation operator are directly checked whether they lead to an improvement, is a superior combination of LS and EA.

Stochastic Pareto local search (SPLS) methods are local search algorithms for multi-objective combinatorial optimization problems that restart local search from points generated using a stochastic process. Examples of such stochastic processes are Brownian motion (or random processes), and the ones resulting from the use of mutation and recombination operators. We propose a path-guided mutation operator for SPLS where an individual solution is mutated in the direction of the path to another individual solution in order to restart a PLS.We study the exploration of the landscape of the bi-objective Quadratic assignment problem (bQAP) using SPLSs that restart the PLSs from: i) uniform randomly generated solutions, ii) solutions generated from best-so-far local optimal solutions with uniform random mutation and iii) with path-guided mutation. Experiments on a bQAP with a large number of facilities and high correlation between the flow matrices show that using mutation, and especially path-guided mutation, is beneficial for performance of SPLS. The performance of SPLSs is partially explained using their dynamical behavior like the probability of escaping the local optima and the speed of enhancing the Pareto front.

For most combinatorial optimization problems the computational complexity of evaluating a single solution is much higher than the cost of evaluating an incremental change made by a local search operator. To benefit from this computational gain crossover can be implemented as a path–following algorithm. As a result crossover becomes more similar to path relinking. In this paper we compare the search bias of crossover and path relinking for permutation problems where the absolute position of the elements is decisive. Calculations show that uniform permutation crossover (UPX) can reach many more permutations from a given parent couple than path relinking. UPX is therefore more exploratory than random path relinking, which is itself more exploratory than greedy path relinking. It is important for users to understand the differences in search bias of the operators so they can choose the exploration operator which they deem most fit for their problem. We conclude with a small experiment on an instance of the quadratic assignment problem.

In this chapter we survey a type of evolutionary algorithm (EA) in which the main operator of variation is based on the learning of and sampling from probabilistic models. The main contribution of these probabilistic model—building EAs resides in the fact that by learning a probabilistic model from selected solutions and subsequently drawing new solutions from the probability distribution represented by the probabilistic model, an inductive tool is provided for online identification of features of the problem’s structure. These features are then used to guide the search more efficiently towards the promising regions of the search space. Probabilistic model—building EAs are relatively new to the field of evolutionary computation. In this chapter we briefly motivate their use. Through different classes of probability distribution, different types of dependency can be expressed, resulting in different types of induction. We review the literature on related work by discussing different classes of probability distribution that have been used so far in probabilistic model—building EAs. We conclude this chapter by reflecting on the use and applicability of learning probabilistic models for enhanced evolutionary computation, as well as on future perspectives.

We study the impact of the choice of search space for a GA that learns Bayesian networks from data. The most convenient search space is redundant and therefore allows for multiple representations of the same solution and possibly disruption during crossover. An alternative search space eliminates this redundancy, and potentially allows a more efficient search to be conducted. On the other hand, a non-redundant encoding requires a more complicated implementation. We experimentally compare several plausible approaches (GAs) to study the impact of this and other design decisions.

Iterated local search (ILS) is a powerful meta-heuristic algorithm applied to a large variety of combinatorial optimization problems. Contrary to evolutionary algorithms (EAs) ILS focuses only on a single solution during its search. EAs have shown however that there can be a substantial gain in search quality when exploiting the information present in a population of solutions. In this paper we propose the use of a population for ILS. We define the general form of the resulting meta-heuristic, called population-based iterated local search (PILS). PILS is a minimal extension of ILS that uses previously generated solutions in the neighborhood of the current solution to restrict the neighborhood search by ILS. This neighborhood restriction is analogous to the way crossover preserves common substructures between parents when generating offspring. To keep the discussion concrete, we discuss a specific instantiation of the PILS algorithm on a binary trap function.

Recent developments in GA theory have given rise to a number of design principles that serve to guide the construction of selecto-recombinative GAs from which good performance can be expected. In this paper, we demonstrate their application to the design of a GA for a well-known hard problem in machine learning: the construction of a Bayesian network from data. We show that the resulting GA is able to efficiently and reliably find good solutions. Comparisons against state-of-the-art learning algorithms, moreover, are favorable.

Various different algorithms for learning Bayesian networks from data have been proposed to date. In this paper, we adopt a novel approach that combines the main advantages of these algorithms yet avoids their difficulties. In our approach, first an undirected graph, termed the skeleton, is constructed from the data, using zero- and first-order dependence tests. Then, a search algorithm is employed that builds upon a quality measure to find the best network from the search space that is defined by the skeleton. To corroborate the feasibility of our approach, we present the experimental results that we obtained on various different datasets generated from real-world networks. Within the experimental setting, we further study the reduction of the search space that is achieved by the skeleton.

We present a multiobjective genetic algorithm that incorporates various genetic algorithm techniques that have been proven to be efficient and robust in their problem domain. More specifically, we integrate rank based selection, adaptive niching through coevolutionary sharing, elitist recombination, and non-dominated sorting into a multiobjective genetic algorithm called ERMOCS. As a proof of concept we test the algorithm on a softkill-scheduling problem.

The optimization of the weights of a feedforward neural network with a genetic algorithm is discussed. The search by the recombination operator is hampered by the existence of two functional equivalent symmetries in feedforward neural networks. To sidestep these representation redundancies we reorder the hidden neurons on the genotype before recombination according to a weight sign matching criterion, and flip the weight signs of a hidden neuron’s connections whenever there are more inhibitory than excitatory incoming and outgoing links. As an example we optimize a feedforward neural network that implements a nonlinear optimal control law. The neural controller has to swing up the inverted pendulum from its lower equilibrium point to its upper equilibrium point and stabilize it there. Finding the weights of the network represents a nonlinear optimization problem which is solved by the genetic algorithm.

Evolutionary Learning proceeds by evolving a population of classifiers, from which it generally returns (with some notable exceptions) the single best-of-run classifier as final result. In the meanwhile, Ensemble Learning, one of the most efficient approaches in supervised Machine Learning for the last decade, proceeds by building a population of diverse classifiers. Ensemble Learning with Evolutionary Computation thus receives increasing attention. The Evolutionary Ensemble Lear\-ning (EEL) approach presented in this paper features two contributions. First, a new fitness function, inspired by co-evolution and enforcing the classifier diversity, is presented. Further, a new selection criterion based on the classification margin is proposed. This criterion is used to extract the classifier ensemble from the final population only (Off-line) or incrementally along evolution (On-line). Experiments on a set of benchmark problems show that Off-line outperforms single-hypothesis evolutionary learning and state-of-art Boosting and generates smaller classifier ensembles.