Recent Advances in Evolutionary Computation for Combinatorial Optimization

We describe an implementation of an evolutionary algorithm on partially commutative groups and apply it to solve certain two-variable word equations on a subclass of these groups, transforming a problem in combinatorial group theory into one of combinatorial optimisation. We give results which indicate efficient and successful behaviour of the evolutionary algorithm, hinting at the presence of a new degenerate deterministic solution and a framework for further results in similar group-theoretic problems. This paper is an expanded and updated version of [14], presented at EvoCOP 2007.

This chapter presents a rigorous Design of Experiments (DOE) approach for determining whether a problem characteristic affects the performance of a heuristic. Specifically, it reports a study on the effect of the cost matrix standard deviation of symmetric Travelling Salesman Problem (TSP) instances on the performance of Ant Colony Optimisation (ACO) heuristics. Results demonstrate that for a given instance size, an increase in the standard deviation of the cost matrix of instances results in an increase in the difficulty of the instances. This implies that for ACO, it is insufficient to report results on problems classified only by problem size, as has been commonly done in most ACO research to date. Some description of the cost matrix distribution is also required when attempting to explain and predict the performance of these heuristics on the TSP. The study should serve as a template for similar investigations with other problems and other heuristics.

This work studies the working principles, performance, and scalability of genetic algorithms on NK-landscapes varying the degree of epistasis interactions. Previous works that have focused mostly on recombination have shown that simple genetic algorithms, and some improved ones, perform worse than random bit climbers and not better than random search on landscapes of increased epistasis. In our work, in addition to recombination, we also study the effects on performance of selection, mutation, and drift. We show that an appropriate selection pressure and postponing drift make genetic algorithms quite robust on NK-landscapes, outperforming random bit climber on a broad range of classes of problems. We also show that the interaction of parallel varying-mutation with crossover improves further the reliability of the genetic algorithm.

In this article, we describe the steps that have been followed in the development of a high performing stochastic local search algorithm for the probabilistic travelling salesman problem, a paradigmatic combinatorial stochastic optimization problem. In fact, we have followed a bottom-up algorithm engineering process that starts from basic algorithms (here, iterative improvement) and adds complexity step-by-step. An extensive experimental campaign has given insight into the advantages and disadvantages of the prototype algorithms obtained at the various steps and directed the further algorithm development. The final stochastic local search algorithm was shown to substantially outperform the previous best algorithms known for this problem. Besides the systematic engineering process for the development of stochastic local search algorithms followed here, the main reason for the high performance of our final algorithm is the innovative adoption of techniques for the estimation of the cost of neighboring solutions using delta evaluation.

We present a Lagrangian decomposition approach for the Knapsack Constrained Maximum Spanning Tree problem yielding upper bounds as well as heuristic solutions. This method is further combined with an evolutionary algorithm to a sequential hybrid approach. Thorough experimental investigations, including a comparison to a previously suggested simpler Lagrangian relaxation based method, document the advantages of our approach. Most of the upper bounds derived by Lagrangian decomposition are optimal, and when additionally applying local search (LS) and combining it with the evolutionary algorithm, large and supposedly hard instances can be either solved to provable optimality or with a very small remaining gap in reasonable time.

This work presents a hybrid optimization framework for tackling cutting and packing problems, which is based upon a particular combination scheme between heuristic and exact methods. A metaheuristic engine works as a generator of reduced instances for the original optimization problem, which are formulated as mathematical programming models. These instances, in turn, are solved by an exact optimization technique (solver), and the performance measures accomplished by the respective models are interpreted as score (fitness) values by the metaheuristic, thus guiding its search process. As a means to assess the potentialities behind the novel approach, we provide an instantiation of the framework for dealing specifically with the constrained two-dimensional non-guillotine cutting problem. Computational experiments performed over standard benchmark problems are reported and discussed here, evidencing the effectiveness of the novel approach.

In this paper we propose and study the behavior of a new hybrid heuristic algorithm for the DNA fragment assembly problem. The DNA fragment assembly is a problem solved in the early phases of the genome project and thus very important, since the other steps depend on its accuracy. This is an NP-hard combinatorial optimization problem which is growing in importance and complexity as more research centers become involved on sequencing new genomes. Our contribution is a hybrid method that combines a promising heuristic, PALS, with a well-know metaheuristic, a genetic algorithm, obtaining as result a very efficient assembler that allows to find optimal solutions for large instances of this problem.

This chapter proposes a neural network based approach for solving the resource discovery problem in Peer to Peer (P2P) networks and an Adaptive Global Local Memetic Algorithm (AGLMA) for performing in training of the neural network. The neural network, which is a multi-layer perceptron neural network, allows the P2P nodes to efficiently locate resources desired by the user. The necessity of testing the network in various working conditions, aiming to obtain a robust neural network, introduces noise in the objective function. The AGLMA is a memetic algorithm which employs two local search algorithms adaptively activated by an evolutionary framework. These local searchers, having different features according to the exploration logic and the pivot rule, have the role of exploring decision space from different and complementary perspectives. Furthermore, the AGLMA makes an adaptive noise compensation by means of explicit averaging on the fitness values and a dynamic population sizing which aims to follow the necessity of the optimization process. The numerical results demonstrate that the proposed computational intelligence approach leads to an efficient resource discovery strategy and that the AGLMA outperforms an algorithm classically employed for executing the neural network training.

Many instances of NP-hard problems can be solved efficiently if the treewidth of their corresponding graph is small. Finding the optimal tree decompositions is an NP-hard problem and different algorithms have been proposed in the literature for generation of tree decompositions of small width. In this chapter we present a new iterated local search algorithm to find good upper bounds for treewidth of an undirected graph. The iterated local search algorithm consists from the construction phase, and includes the mechanism for perturbation of solutions, and the mechanism for accepting of solutions for the next iteration. In the construction phase the solutions are generated by the heuristics which search for good elimination ordering of nodes of graph based on moving of only vertices that produce the largest clique in the elimination process. We proposed and evaluated different perturbation mechanisms and acceptance criteria. The proposed algorithm is tested on DIMACS instances for vertex colouring, and is compared with the existing approaches in the literature. The described algorithm has a good time performance and for several instances improves the best existing upper bounds for the treewidth.

Graph vertex colouring can be defined in such a way where colour assignments are substituted by vertex contractions. We present various hypergraph representations for the graph colouring problem all based on the approach where vertices are merged into groups. In this paper, we explain this approach and identify three reasons that make it useful. First, generally, this approach provides a potential decrease in computational complexity. Second, it provides a uniform and compact way in which algorithms, be it of a complete or a heuristic nature, can be defined and progress toward a colouring. Last, it opens the way to novel applications that extract information useful to guide algorithms during their search. These approaches can be useful in the design of an algorithm.

Most work in project scheduling problems has been done with so-called regular objective functions, where a solution S never dominates another solution S’ if no activity is scheduled earlier in S than in S’. This has provided with techniques and metaheuristic frameworks to create heuristic algorithms for these kinds of problems, something which does not exist in the nonregular case. One of these problems is the Resource Renting Problem, which models the renting of resources. In this paper we compare the quality of three algorithms for this problem, one adapted from the regular case, another specially designed for the problem and a third that might be adapted for other problems. We will also show that two of these algorithms are capable of outperforming a branch-and-bound procedure that exists for the problem.

This paper presents a simple Optimised Search Heuristic for the Job Shop Scheduling problem that combines a GRASP heuristic with a branch-and-bound algorithm. The proposed method is compared with similar approaches and leads to better results in terms of solution quality and computing times.

In this chapter we present parallel implementations of Memetic Algorithms (MAs) for the problem of scheduling independent jobs in computational grids. The problem of scheduling in computational grids is known for its high demanding computational time. In this work we exploit the intrinsic parallel nature of MAs as well as the fact that computational grids offer large amount of resources, a part of which could be used to compute the efficient allocation of jobs to grid resources.

The parallel models exploited in this work for MAs include both fine-grained and coarse-grained parallelization and their hybridization. The resulting schedulers have been tested through different grid scenarios generated by a grid simulator to match different possible configurations of computational grids in terms of size (number of jobs and resources) and computational characteristics of resources. All in all, the result of this work showed that Parallel MAs are very good alternatives in order to match different performance requirement on fast scheduling of jobs to grid resources.

The Travelling Salesman Problem (TSP) is a well-known NP-hard combinatorial optimization problem, for which a large variety of evolutionary algorithms are known. However, with instance size the effort to find good solutions increases considerably. Here, we discuss a set of eight edge fixing heuristics to transform large TSP problems into smaller problems, which can be solved easily with existing algorithms. The edge fixing heuristics exploit properties of the TSP such as nearest neighbour relations or relative edge length. We argue, that after expanding a reduced tour back to the original instance, the result is nearly as good as applying the used solver to the original problem instance, but requires significantly less time to be achieved.

Solid waste collection in urban areas is a central topic for local environmental agencies. The operational problem, the definition of collection routes given the vehicle fleet, can greatly benefit of computerized support already for medium sized town. While the operational constraints can vary, the core problem can be identified as a capacitated arc routing problem on large directed graphs (DCARP). This paper reports about the effectiveness of different metaheuristics on large DCARP instances derived from real-world applications.

This chapter deals with the Split Delivery Capacitated Arc Routing Problem or SDCARP. Contrary to the classical Capacitated Arc Routing Problem or CARP, an edge may be serviced by more than one vehicle. An integer linear program, an insertion heuristic and a memetic algorithm with population management are proposed for this problem seldom studied. The algorithm calls an effective local search procedure, which contains new moves able to split demands. Compared to one of the best metaheuristics for the CARP, we show that splitting demands can bring important savings and reduce significantly the number of required vehicles.

Given a collection of warehouse locations, each with a fixed cost, and customers to be served from those warehouses, each with a cost associated with both the customer and the one warehouse from which the customer is served, the uncapacitated facility location problem seeks to identify a subset of the warehouse locations that minimizes the total cost. A genetic algorithm for this NP-hard problem encodes candidate subsets of the warehouse locations as permutations of all the available locations; a greedy decoder identifies the subset that such a chromosome represents. Three heuristic extensions reorder chromosomes so that they list included locations before excluded; mutate chromosomes by always swapping an included location with an arbitrary one; and re-scan the included locations to exclude any whose exclusion reduces the total cost. Four versions of the GA implement none, one, two, or all of these extensions. In tests on 235 publicly available problem instances whose optimum solutions are known, all the versions outperform a straightforward binary-coded GA, and the heuristic extensions enable the version that uses them all to find optimum solutions very quickly on almost every trial on the test instances. The heuristic techniques should be effective in permutation-coded evolutionary algorithms for other problems that seek subsets of initially unknown sizes.