Applications of Evolutionary Computing

The term hyperheuristic was introduced by the authors as a high-level heuristic that adaptively controls several low-level knowledgepoor heuristics so that while using only cheap, easy-to-implement low-level heuristics, we may achieve solution quality approaching that of an expensive knowledge-rich approach. For certain classes of problems, this allows us to rapidly produce effective solutions, in a fraction of the time needed for other approaches, and using a level of expertise common among non-academic IT professionals. Hyperheuristics have been successfully applied by the authors to a real-world problem of personnel scheduling. In this paper, the authors report another successful application of hyperheuristics to a rather different real-world problem of personnel scheduling occuring at a UK academic institution. Not only did the hyperheuristics produce results of a quality much superior to that of a manual solution but also these results were produced within a period of only three weeks due to the savings resulting from using the existing hyperheuristic software framework.

In this paper we propose a hybrid approach for solving vehicle routing problems. The main idea is to combine an Ant System (AS) with a problem specific constructive heuristic, namely the well known Savings algorithm. This difiers from previous approaches, where the subordinate heuristic was the Nearest Neighbor algorithm initially proposed for the TSP. We compare our approach with some other classic, powerful meta-heuristics and showthat our results are competitive.

In this paper we introduce two systematic approaches, based on the stochastic gradient ascent algorithm and the cross-entropy method, for deriving the pheromone update rules in the Ant colony optimization metaheuristic. We discuss the relationships between the two methods as well as connections to the update rules previously proposed in the literature.

Earlier papers [1],[2] introduced some statistical estimation methods for measuring certain properties of landscapes induced by heuristic search methods: in particular, the number of optima. In this paper we extendthis approach to non-parametric methods which allow us to relax a critical assumption of the earlier approach. Two techniques are described—the jackknife and the bootstrap—based on statistical ideas of resampling, and the results of some empirical studies are presented and analysed.

Task scheduling is known to be NP-complete in its general form as well as in many restricted cases. Thus to find a near optimal solution in, at most, polynomial time different heuristics were proposed. The basic Grahamś task graph model [1] was extended to other list-based priority schedulers [2] where increased levels of communication overhead were included [3]. Evolutionary Algorithms (EAs) have been used in the past to implement the allocation of the components (tasks) of a parallel program to processors [4], [5]. In this paper five evolutionary algorithms are compared. All of them use the conventional Single Crossover Per Couple (SCPC) approach but they differ in what is represented by the chromosome: processor dispatching priorities, tasks priority lists, or both priority policies described in a bipartite chromosome. Chromosome structure, genetic operators, experiments and results are discussed.

Determining an optimal schedule to minimise the completion time of the last job abandoning the system (makespan) become a very difficult problem when there are more than two machines in the flow shop. Due, both to its economical impact and complexity, attention to solve this problem has been paid by many researchers. Starting with the Johnson’s exact algorithm for the twomachine makespan problem [1], over the past three decades extensive search have been done on pure m-machine flow shop problems. Many researchers faced the Flow Shop Scheduling (FSSP) by means of well-known heuristics which, are successfully used for certain instances of the problem and providing a single acceptable solution. Current trends to solve the FSSP involve Evolutionary Computation and Ant Colony paradigms. This work shows different bio-inspired heuristics for the FSSP, including hybrid versions of enhanced multirecombined evolutionary algorithms and ant colony algorithms [2], on a set of flow shop scheduling instances. A discussion on implementation details, analysis and a comparison of different approaches to the problem is shown.

The set covering problem is an NP-hard combinatorial optimization problem that arises in applications ranging from crew scheduling in airlines to driver scheduling in public mass transport. In this paper we analyze search space characteristics of a widely used set of benchmark instances through an analysis of the fitness-distance correlation. This analysis shows that there exist several classes of set covering instances that show a largely different behavior. For instances with high fitness distance correlation, we propose new ways of generating core problems and analyze the performance of algorithms exploiting these core problems.

A population based ACO (Ant Colony Optimization) algorithm is proposed where (nearly) all pheromone information corresponds to solutions that are members of the actual population. Advantages of the population based approach are that it seems promising for solving dynamic optimization problems, its finite state space and the chances it offers for designing new metaheuristics. We compare the behavior of the new approach to the standard ACO approach for several instances of the TSP and the QAP problem. The results show that the new approach is competitive.

Constraint Satisfaction Problems form a class of problems that are generally computationally dificult and have been addressed with many complete and heuristic algorithms. We present two complete algorithms, as well as two evolutionary algorithms, and compare them on randomly generated instances of binary constraint satisfaction problems. We find that the evolutionary algorithms are less effective than the classical techniques.

An account is presented of the design and application of Genetic Algorithms for the geometry optimization (energy minimization) of clusters and nanoparticles, where the interactions between atoms, ions or molecules are described by a variety of potential energy functions (force fields). Adetailed description is presented of the Birmingham Cluster Genetic Algorithm Program, developed in our group, and two specific applications are highlighted: the use of a GAto optimize the geometry and atom distribution in mixed Cu-Au clusters; and the use of an energy predator in an attempt to identify the lowest six isomers of C₄₀.

This paper considers the problem of augmenting a given graph by a cheapest possible set of additional edges in order to make the graph vertex-biconnected. A real-world instance of this problem is the enhancement of an already established computer network to become robust against single node failures. The presented memetic algorithm includes an effective preprocessing of problem data and a fast local improvement strategy which is applied during initialization, mutation, and recombination. Only feasible, locally optimal solutions are created as candidates. Empirical results indicate the superiority of the new approach over two previous heuristics and an earlier evolutionary method.

This paper compares experimentally three heuristic algorithms for the maximum clique problem obtained as instances of an evolutionary algorithm scheme. The algorithms use three popular heuristic methods for combinatorial optimization problems, known as genetic, iterated and multistart local search, respectively.

Graph coloring is a well known problem from graph theory that, when attacking it with local search algorithms, is typically treated as a series of constraint satisfaction problems: for a given number of colors k one has to find a feasible coloring; once such a coloring is found, the number of colors is decreased and the local search starts again. Here we explore the application of Iterated Local Search on the graph coloring problem. Iterated Local Search is a simple and powerful metaheuristic that has shown very good results for a variety of optimization problems. In our research we investigated several perturbation schemes and present computational results on a widely used set of benchmarks problems, a sub-set of those available from the DIMACS benchmark suite. Our results suggest that Iterated Local Search is particularly promising on hard, structured graphs.

Real-world car sequencingproblems deal with lots of constraints, which differ in their types and priorities. We evaluate three permutation-based local search algorithms that use different acceptance criteria for moves. The algorithms meet industrial requirements to obtain acceptable solutions in a rather short time. It is essential to employ move operators which can be evaluated quite fast. Further, using different move types enlarges the neighbourhood, thereby decreasing the total number of local optima in the search space. The comparison of the acceptance criteria shows that the greedy approach is inferior to two variants of threshold acceptingthat allow escapingfrom local optima.

Evolution strategies (ES)are efficient optimization methods for continuous problems. However, many combinatorial optimization methods can not be represented by using continuous representations. The development of the network random key representation which represents trees by using real numbers allows one to use ES for combinatorial tree problems.In this paper we apply ES to tree problems using the network random key representation. We examine whether existing recommendations regarding optimal parameter settings for ES, which were developed for the easy sphere and corridor model, are also valid for the easy one-max tree problem.The results show that the $$ \frac{1} {5} $$-success rule for the (1+1)-ES results in low performance because the standard deviation is continuously reduced and we get early convergence. However, for the (μ+λ)-ES and the (μ, λ)-ES the recommendations from the literature are confirmed for the parameters of mutation $$ \tau _1 $$ and $$ \tau _2 $$ and the ratio μ/λ. This paper illustrates how existing theory about ES is helpful in finding good parameter settings for new problems like the one-max tree problem.

This paper presents a variation of the Euclidean Traveling Salesman Problem (TSP), the Multiple Traveling Salesman Problem (MTSP), and compares a variety of evolutionary computation algorithms and paradigms for solving it. Techniques implemented, analyzed, and discussed herein with regard to MTSP include use of a neighborhood attractor schema (a variation on k-means clustering), the “shrink-wrap” algorithm for local neighborhood optimization, particle swarm optimization, Monte-Carlo optimization, and a range of genetic algorithms and evolutionary strategies.

When solving a combinatorial optimization problem with the Ant Colony Optimization (ACO) metaheuristic, one usually has to find a compromise between guiding or diversifying the search. Indeed, ACO uses pheromone to attract ants. When increasing the sensibility of ants to pheromone, they converge quicker towards a solution but, as a counterpart, they usually find worse solutions. In this paper, we first study the influence of ACO parameters on the exploratory ability of ants. We then study the evolution of the impact of pheromone during the solution process with respect to its cost’s management. We finally propose to introduce a preprocessing step that actually favors a larger exploration of the search space at the beginning of the search at low cost. We illustrate our approach on Ant-Solver, an ACO algorithm that has been designed to solve Constraint Satisfaction Problems, and we show on random binary problems that it allows to find better solutions more than twice quicker.

Sorting algorithms define paths in the search space of n! permutations based on the information provided by a comparison predicate. We guide a Memetic Algorithm with a new mutation operator. Our mutation operator performs local search following the path traced by the Quicksort mechanism. The comparison predicate and the evaluation function are made to correspond and guide the evolutionary search. Our approach improves previous results for a benchmark of experiments of the Error-Correcting Graph Isomorphism. For this case study, our new Memetic Algorithm achieves a better quality vs effort trade-off and remains highly effective even when the size of the problem grows.

Reducing production-test application time is a key problem for modern industries. Several different hardware solutions have been proposed in the literature to ease such process. However, each hardware architecture must be coupled with an effective test signals generation algorithm. This paper propose an evolutionary approach for minimizing the application time of a test set by opportunely extending it and exploiting a new hardware architecture, named interleaved scan. The peculiarities of the problem suggest the use of a slightly modified genetic algorithm with concurrent populations. Experimental results show the effectiveness of the approach against the traditional ones.

Genetic Programming (GP) is an evolutionary method that creates computer programs that represent approximate or exact solutions to a problem. This paper proposes an application of GP in hydrology, namely for modelling the effect of rain on the run-off flow in a typical urban basin. The ultimate goal of this research is to design a real time alarm system to warn of floods or subsidence in various types of urban basin. Results look promising and appear to offer some improvement over stochastic methods for analysing river basin systems such as unitary radiographs.

This paper presents an evolutionary approach to estimate the sugar concentration inside compound bodies based on spectroscopy measurements. New European regulation will shortly forbid the use of established chemical methods based on mercury to estimate the sugar concentration in sugar beet. Spectroscopy with a powerful regression technique called PLS (Partial Least Squares) may be used instead. We show that an evolutionary approach for selecting relevant wavelengths before applying PLS can lower the error and decrease the computation time. It is submitted that the results support the argument for replacing the PLS scheme with a GP technique.

Considered is the problem of reliably predicting motorway journey times for the purpose of providing accurate information to drivers. This proof of concept experiment investigates:(a) the practicalities of using a Genetic Programming (GP) method to model/forecast motorway journey times; and (b) different ways of obtaining a journey time predictor. Predictions are compared with known times and are also judged against a collection of naive prediction formulae. A journey time formula discovered by GP is analysed to determine its structure, demonstrating that GP can indeed discover compact formulae for different trafic situations and associated insights. GP’s felxibility allows it to self-determine the required level of modelling complexity.

A’ data crawler’ is allowed to meander around an image deciding what it considers to be interesting and laying down flags in areas where its interest has been aroused. These flags can be analysed statistically as if the image was being viewed from afar to achieve object recognition. The guidance program for the crawler, the program which excites it to deposit a flag and how the flags are combined statistically, are driven by an evolutionary process which has as objective the minimisation of misses and false alarms. The crawler is represented by a tree-based Genetic Programming (GP) method with fixed architecture Automatically Defined Functions (ADFs). The crawler was used as a post-processor to the object detection obtained by a Staged GP method, and it managed to appreciably reduce the number of false alarms on a real-world application of vehicle detection in infrared imagery.

We present a study of rough surface inverse scattering problems using evolutionary strategies. The input data consists of far-field angle-resolved scattered intensity data, and the objective is to reconstruct the surface profile function that produced the data. To simplify the problem, the random surface is assumed to be one-dimensional and perfectly conducting. The optimum of the fitness function is searched using the evolutionary strategies (μ, λ) and (μ + λ). On the assumption that some knowledge about the statistical properties of the unknown surface profile is given or can be obtained, the search space is restricted to surfaces that belong to that particular class. In our case, as the original surface, the trial surfaces constitute realizations of a stationary zeromean Gaussian random process with a Gaussian correlation function. We find that, for the conditions and parameters employed, the surface profile can be retrieved with high degree of confidence. Some aspects of the convergence and the lack of uniqueness of the solution are also discussed.

Traditional algorithms which set a lower speed limit on a motorway to protect the trafic against collision with a queue are not successful at detecting isolated incidents late at night, in low flow high speed conditions. The Staged Genetic Programming method is used to detect an incident in this trafic regime. The evolutionary engine automatically decides the time duration for the onset of an incident. This method successfully combines trafic readings from the MIDAS system to predict a variety of late night incidents on the M25 motorway.

The paper introduces a new approach to automatic design of image filters for a given type of noise. The approach employs evolvable hardware at simplified functional level and produces circuits that outperform conventional designs. If an image is available both with and without noise, the whole process of filter design can be done automatically, without influence of a designer.

Evolvable Hardware (EHW) has been proposed as a new method for designing electronic circuits. In this paper it is applied for evolving a prosthetic hand controller. The novel controller architecture is based on digital logic gates. A set of new methods to incrementally evolve the system is described. This includes several different variants of the fitness function being used. By applying the proposed schemes, the generalisation of the system is improved.

There are applications where a binary image is given and a shape is to be reconstructed from it with some kind of evolutionary algorithms. A solution for this problem usually highly depends on the fitness function. On the one hand fitness function influences the convergence speed of the EA. On the other hand, fitness computation is done many times, therefore the fitness computation itself has to be reasonably fast. This paper tries to define what “reasonably fast” means, by giving a definition for the efficiency. A definition alone is however not enough, therefore several fitness functions and function classes are defined, and their efficiencies are examined.

We describe a new method of achieving autocalibration that uses a stochastic optimization approach taken from the field of evolutionary computing and we perform a number of experiments on standardized data sets that show the effectiveness of the approach. The basic assumption of this method is that the internal (intrinsic) camera parameters remain constant throughout the image sequence, i.e. they are taken from the same camera without varying the focal length. We show that for the autocalibration of focal length and aspect ratio, the evolutionary method achieves comparable results without the implementation complexity of other methods. Autocalibrating from the fundamental matrix is simply transformed into a global minimization problem utilizing a cost function based on the properties of the fundamental matrix and the essential matrix.

Registration of medical image data of different modalities and multiple times is an important component of medical image analysis. A variety of robust and accurate voxel-based approaches have been proposed, and mathematically almost all of them are associated with optimization problems that are highly non-linear and non-convex. This article presents a parallel genetic strategy to attack mutual information based registration. The experimental results show robust registration with high speedup achieved. Furthermore, this method is readily applicable for other voxel-based registration methods.

The Aircraft Recovery Problem (ARP) involves decisions concerning aircraft to flight assignments in situations where unforeseen events have disrupted the existing flight schedule, e.g. bad weather causing flight delays. The aircraft recovery problem aims to recover these flight schedules through a series of reassignments of aircraft to flights, delaying of flights and cancellations of flights. This article demonstrates an effective method to solve ARP. A heuristic is implemented, which is able to generate feasible revised flight schedules of a good quality in less than 10 seconds. This article is a product of the DESCARTES project, a project funded by the European Union between the Technical University of Denmark, British Airways and Carmen (see [1]).

In this paper the relative pheromone evaluation method for Ant Colony Optimization is investigated. We compare this method to the standard pheromone method and the summation method. Moreover we propose a new variant of the relative pheromone evaluation method. Experiments performed for various instances of the single machine scheduling problems with earliness costs and multiple due dates show the potential of the relative pheromone evaluation method.

Street based routing (SBR) is a real-world inspired routing problem that builds routes within an urban area for mail deliveries. The authors have previously attempted to solve this problem using an Evolutionary Algorithm (EA). In this paper the authors examine a heuristic mutation based on concept of building blocks. In this case a building block is defined as a group of genes, which when placed together within a genotype result in a useful feature within the phenotype. After evaluation on three test data sets our experiments conclude that the explicit use of heuristic building blocks makes a significant improvement to the SBR algorithms results.