
EvoCOP2002


Hyperheuristics: A Tool for Rapid Prototyping in Scheduling and Optimisation
Cowling P.,
Kendall G.,
Soubeiga S.
Abstract:
The term hyperheuristic was introduced by the authors as a highlevel heuristic that adaptively controls several lowlevel knowledgepoor heuristics so that while using only cheap, easytoimplement lowlevel heuristics, we may achieve solution quality approaching that of an expensive knowledgerich 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 nonacademic IT professionals. Hyperheuristics have been successfully applied by the authors to a realworld problem of personnel scheduling. In this paper, the authors report another successful application of hyperheuristics to a rather different realworld 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.
Session:
EvoCOP Session 6: Scheduling problems: April 5, 09301100
Savings Ants for the Vehicle Routing Problem
Doerner K.,
Gronalt M.,
Hartl R. F.,
Reimann M.,
Strauss C.,
Stummer M.
Abstract:
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 differs 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 metaheuristics and show that our results are competitive.
Session:
EvoCOP Session 5: Ant colony optimization: April 4, 13451545
Updating ACO pheromones using Stochastic Gradient Ascent and CrossEntropy methods
Dorigo M.,
Zlochin M.,
Meuleau N.,
Birattari M.
Abstract:
In this paper we introduce two systematic approaches, based on the stochastic gradient ascent algorithm and the crossentropy 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.
Session:
EvoCOP Session 5: Ant colony optimization: April 4, 13451545
Nonparametric Estimation of Properties of Combinatorial Landscapes
Eremeev A.,
Reeves C. R.
Abstract:
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 extend this approach to nonparametric 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.
Session:
EvoCOP Session 2: Exploiting statistics: April 3, 16301800
Performance of Evolutionary Approaches for Parallel Task Scheduling under Different Representations
Esquivel S.,
Gatica C.,
Gallard R.
Abstract:
Task scheduling is known to be NPcomplete 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´s task graph model [1] was extended to other listbased 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.
Session:
EvoCOP Session 6: Scheduling problems: April 5, 09301100
A Performance Comparison of Alternative Heuristics for the Flow Shop Scheduling Problem
Esquivel S.,
Leguizamón G.,
Zuppa F.,
Gallard R.
Abstract:
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 mmachine flow shop problems. Many researchers faced the Flow Shop Scheduling (FSSP) by means of wellknown 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 bioinspired 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.
Session:
EvoCOP Session 6: Scheduling problems: April 5, 09301100
Exploiting Fitness Distance Correlation of Set Covering Problems
Finger M.,
Stützle T.,
Lourenço H.
Abstract:
The set covering problem is an NPhard 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 fitnessdistance 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.
Session:
EvoCOP Session 2: Exploiting statistics: April 3, 16301800
A Population Based Approach for ACO
Guntsch M.,
Middendorf M.
Abstract:
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.
Session:
EvoCOP Session 5: Ant colony optimization: April 4, 13451545
Application of Genetic Algorithms in Nanoscience: Cluster Geometry Optimization
Johnston R. L.,
MortimerJones T. V.,
Roberts C.,
Darby S.,
Manby F. R.
Abstract:
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). A detailed description is presented of the Birmingham Cluster Genetic Algorithm Program, developed in our group, and two specific applications are highlighted: the use of a GA to optimize the geometry and atom distribution in mixed CuAu clusters; and the use of an energy predator in an attempt to identify the lowest six isomers of C40.
Session:
EvoCOP Session 3: Realvalued representations: April 4, 09301030
A Memetic Algorithm for VertexBiconnectivity Augmentation
Kersting S.,
Raidl G. R.,
Ljubic I.
Abstract:
This paper considers the problem of augmenting a given graph by a cheapest possible set of additional edges in order to make the graph vertexbiconnected. A realworld 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.
Session:
EvoCOP Session 1: Graph problems: April 3, 14001545
Genetic, Iterated and Multistart Local Search for the Maximum Clique Problem
Marchiori E.
Abstract:
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.
Session:
EvoCOP Session 1: Graph problems: April 3, 14001545
An Experimental Investigation of Iterated Local Search for Coloring Graph
Paquete L.,
Stützle T
Abstract:
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 subset of those available from the DIMACS benchmark suite. Our results suggest that Iterated Local Search is particularly promising on hard, structured graphs.
Session:
EvoCOP Session 4: Constrained problems: April 4, 11001230
Solving Car Sequencing Problems by Local Optimization
Puchta M.,
Gottlieb J.
Abstract:
Realworld car sequencing problems deal with lots of constraints, which differ in their types and priorities. We evaluate three permutationbased 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 accepting that allow escaping from local optima.
Session:
EvoCOP Session 4: Constrained problems: April 4, 11001230
Evolution Strategies, Network Random Keys, and the OneMax Tree Problem
Schindler B.,
Rothlauf F.,
Pesch H.J.
Abstract:
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 onemax tree problem.
The results show that the 1/5success 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 (mu+lambda)ES and the (mu,lambda)ES the recommendations from the literature are confirmed for the parameters of mutation tau1 and tau2 and the ratio mu/lambda. This paper illustrates how existing theory about ES is helpful in finding good parameter settings for new problems like the onemax tree problem.
Session:
EvoCOP Session 3: Realvalued representations: April 4, 09301030
Evolutionary Computational Approaches to Solving the Multiple Traveling Salesman Problem using a Neighborhood Attractor Schema
Sofge D.,
Schultz A.,
De Jong K.
Abstract:
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 kmeans clustering), the "shrinkwrap" algorithm for local neighborhood optimization, particle swarm optimization, MonteCarlo optimization, and a range of genetic algorithms and evolutionary strategies.
Session:
EvoCOP Session 2: Exploiting statistics: April 3, 16301800
Boosting ACO with a Preprocessing Step
Solnon C.
Abstract:
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 AntSolver, 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.
Session:
EvoCOP Session 5: Ant colony optimization: April 4, 13451545
A Memetic Algorithm Guided by Quicksort for the ErrorCorrecting Graph Isomorphism Problem
TorresVelázquez R.,
EstivillCastro V.
Abstract:
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 ErrorCorrecting Graph Isomorphism. For this case study, our new Memetic Algorithm achieves a better quality vs effort tradeoff and remains highly effective even when the size of the problem giIle">:h follo"ign="tConstrained problems
Session chair: Elena Marchiori
Comparin1" />