Evolutionary Computation in Combinatorial Optimization

Frontmatter

Dual Sequence Simulated Annealing with Round-Robin Approach for University Course Timetabling

Abstract

The university course timetabling problem involves assigning a given number of events into a limited number of timeslots and rooms under a given set of constraints; the objective is to satisfy the hard constraints (essential requirements) and minimize the violation of soft constraints (desirable requirements). In this study we employed a Dual-sequence Simulated Annealing (DSA) algorithm as an improvement algorithm. The Round Robin (RR) algorithm is used to control the selection of neighbourhood structures within DSA. The performance of our approach is tested over eleven benchmark datasets. Experimental results show that our approach is able to generate competitive results when compared with other state-of-the-art techniques.

Salwani Abdullah, Khalid Shaker, Barry McCollum, Paul McMullan

Heuristic and Exact Methods for the Discrete (r |p)-Centroid Problem

Abstract

In the discrete (r |p)-centroid problem two decision makers, a leader and a follower, compete to attract clients from a given market. The leader opens p facilities, anticipating that the follower will react to the decision by opening his own r facilities. The decision makers try to maximize their own profits. This Stackelberg game is \(\Sigma_2^P\)-hard. So, we develop a hybrid memetic algorithm for it. A probabilistic tabu search heuristic is applied for improving the offspring. To obtain an upper bound, we reformulate the problem as a mixed integer program with an exponential number of constraints and variables. Selecting some of them, we get the desired upper bound. To find optimal solutions, we iteratively modify the subset of the constraints and variables. This approach is tested on the benchmarks from the library Discrete Location Problems. The optimal solutions are found for r = p = 5, 100 clients, and 100 facilities.

Ekaterina Alekseeva, Nina Kochetova, Yury Kochetov, Alexandr Plyasunov

On the Benefit of Sub-optimality within the Divide-and-Evolve Scheme

Abstract

Divide-and-Evolve (DaE) is an original “memeticization” of Evolutionary Computation and Artificial Intelligence Planning. DaE optimizes either the number of actions, or the total cost of actions, or the total makespan, by generating ordered sequences of intermediate goals via artificial evolution, and calling an external planner to solve each subproblem in turn. DaE can theoretically use any embedded planner. However, since the introduction of this approach only one embedded planner had been used: the temporal optimal planner CPT. In this paper, we propose a new version of DaE, using time-based Atom Choice and embarking the sub-optimal planner YAHSP in order to test the robustness of the approach and to evaluate the impact of using a sub-optimal planner rather than an optimal one, depending on the type of planning problem.

Jacques Bibai, Pierre Savéant, Marc Schoenauer, Vincent Vidal

A Real-Integer-Discrete-Coded Differential Evolution Algorithm: A Preliminary Study

Abstract

The successful application of differential evolution (DE) algorithms to various real-valued problems encourages to develop some integer-coded versions of DE for working directly with integer and discrete variables of a problem. However, in most of those works, actually a real-valued solution is just converted into a desired integer-valued solution by applying some decoding mechanisms. Only a limited number of works are found, in which attempts are made for developing an actual integer-coded DE. In this article, a novel version of DE is proposed which can work directly with real, integer and discrete variables of a problem without any conversion. Applying to two non-linear real-integer-discrete-valued engineering design problems, the proposed DE is found successful in obtaining the known best solutions of the problems.

Dilip Datta, José Rui Figueira

Fitness Distance Correlation and Search Space Analysis for Permutation Based Problems

Abstract

The fitness distance correlation (FDC) as a measure for problem difficulty was first introduced by Forrest and Jones. It was applied to many binary coded problems. This method is now applied to permutation based problems. As demanded by Schiavinotto and Stützle, the distance in a search space is calculated by regarding the steps of the (neighborhood) operator. In this paper the five most common operators for permutations are analyzed on symmetric and asymmetric TSP instances. In addition a local quality measure, the point quality (PQ) is proposed as a supplement to the global FDC. With this local measure more characteristics and differences can be investigated. Some experimental results are illustrating these concepts.

Botond Draskoczy

A Genetic Algorithm to Minimize Chromatic Entropy

Abstract

We present an algorithmic approach to solving the problem of chromatic entropy, a combinatorial optimization problem related to graph coloring. This problem is a component in algorithms for optimizing data compression when computing a function of two correlated sources at a receiver. Our genetic algorithm for minimizing chromatic entropy uses an order-based genome inspired by graph coloring genetic algorithms, as well as some problem-specific heuristics. It performs consistently well on synthetic instances, and for an expositional set of functional compression problems, the GA routinely finds a compression scheme that is 20-30% more efficient than that given by a reference compression algorithm.

Greg Durrett, Muriel Médard, Una-May O’Reilly

Evolutionary Approaches to the Three-dimensional Multi-pipe Routing Problem: A Comparative Study Using Direct Encodings

Abstract

In this study, three Genetic Algorithms (GAs) are applied to the Three-dimensional Multi-pipe Routing problem. A Standard GA, an Incremental GA, and a Coevolutionary GA are compared. Variable length pipelines are built by letting a virtual robot move in space according to evolved, fixed length command lines and allocate pipe segments along its route. A relative and an absolute encoding of the command lines are compared. Experiments on three proposed benchmark problems show that the GAs taking advantage of the natural problem decomposition; Coevolutionary GA, and Incremental GA outperform Standard GA, and that the relative encoding works better than the absolute encoding. The methods, the results, and the relevant parameter settings are discussed.

Marcus Furuholmen, Kyrre Glette, Mats Hovin, Jim Torresen

A Tabu Search Heuristic for Point Coverage, Sink Location, and Data Routing in Wireless Sensor Networks

Abstract

The point coverage, sink location, and data routing problems are considered in an integrated way and two new mixed-integer programming formulations are proposed. As these models are difficult to solve, a nested solution procedure is proposed. The best sensor locations are sought by tabu search in the upper level. For the fixed sensor locations, the remaining problem of determining sink locations and data routes are solved efficiently in the lower level. According to the experimental results performed on a number of test instances, the performance of the nested solution approach is quite satisfactory, and the proposed heuristic method brings considerable improvements over a two-stage solution approach.

Evren Güney, İ. Kuban Altınel, Necati Aras, Cem Ersoy

Ant Colony Optimization for Tree Decompositions

Abstract

Instances of constraint satisfaction problems can be solved efficiently if they are representable as a tree decomposition of small width. Unfortunately, the task of finding a decomposition of minimum width is NP-complete itself. Therefore, several heuristic and metaheuristic methods have been developed for this problem. In this paper we investigate the application of different variants of Ant Colony Optimization algorithms for the generation of tree decompositions. Furthermore, we extend these implementations with two local search methods and we compare two heuristics that guide the ACO algorithms. Our computational results for selected instances of the DIMACS graph coloring library show that the ACO metaheuristic gives results comparable to those of other decomposition methods such as branch and bound and tabu search for many problem instances. One of the proposed algorithms was even able to improve the best known upper bound for one problem instance. Nonetheless, for some larger problems the best existing methods outperform our algorithms.

Thomas Hammerl, Nysret Musliu

Iterated Local Search with Path Relinking for Solving Parallel Machines Scheduling Problem with Resource-Assignable Sequence Dependent Setup Times

Abstract

This paper addresses the unrelated parallel machine problem with machine and job sequence dependent setup. In this problem, the amount of the setup time does not only depend on the machine and job sequence, but also on a number of resources assigned, which can vary between a minimum and a maximum. The goal is to find a schedule that minimizes the linear combination of the total resources assigned and the total completion time. The problem is NP-hard in the strong sense. The NP-hardness of the problem motivates us to develop a new Iterated Local Search (ILS) heuristic to obtain near-optimal solutions. The heuristic uses an intensification strategy based on the Path Relinking technique which generates new solutions by exploring trajectories that connect high-quality solutions. Computational tests are carried out on a set of benchmark instances and the results obtained by the proposed ILS improve the best known results from the literature by a significant margin.

Edmar Hell Kampke, José Elias Claudio Arroyo, André Gustavo Santos

Enhancing a Tabu Algorithm for Approximate Graph Matching by Using Similarity Measures

Abstract

In this paper, we investigate heuristics in order to solve the Approximated Matching Problem (AGM). We propose a tabu search algorithm which exploits a simple neighborhood but is initialized by a greedy procedure which uses a measure of similarity between the vertices of the two graphs. The algorithm is tested on a large collection of graphs of various sizes (from 300 vertices and up to 3000 vertices) and densities. Computing times range from less than 1 second up to a few minutes. The algorithm obtains consistently very good results, especially on labeled graphs. The results obtained by the tabu algorithm alone (without the greedy procedure) were very poor, illustrating the importance of using vertex similarity during the early steps of the search process.

Segla Kpodjedo, Philippe Galinier, Giulio Antoniol

Characterizing Fault-Tolerance of Genetic Algorithms in Desktop Grid Systems

Abstract

This paper presents a study of the fault-tolerant nature of Genetic Algorithms (GAs) on a real-world Desktop Grid System, without implementing any kind of fault-tolerance mechanism. The aim is to extend to parallel GAs previous works tackling fault-tolerance characterization in Genetic Programming. The results show that GAs are able to achieve a similar quality in results in comparison with a failure-free system in three of the six scenarios under study despite the system degradation. Additionally, we show that a small increase on the initial population size is a successful method to provide resilience to system failures in five of the scenarios. Such results suggest that Paralle GAs are inherently and naturally fault-tolerant.

Daniel Lombraña González, Juan Luís Jiménez Laredo, Francisco Fernández de Vega, Juan Julián Merelo Guervós

The Office-Space-Allocation Problem in Strongly Hierarchized Organizations

Abstract

The office-space-allocation (OSA) problem will be introduced for strongly hierarchized organizations. In several organizations the relation between the entities is strongly hierarchized, affecting the design and handling of constraints and algorithms used to solve the problem. Moreover there is also an increase in the constraint number when compared to the common test instances. Several well known meta-heuristics were used, new constraints developed, and some variations to the local search algorithms were studied. This article describes the work done and its application to a particular case study, the European Space Research and Technology Center (ESTEC).

Rui Lopes, Daniela Girimonte

A Study of Memetic Search with Multi-parent Combination for UBQP

Abstract

We present a multi-parent hybrid genetic–tabu algorithm (denoted by GTA) for the Unconstrained Binary Quadratic Programming (UBQP) problem, by incorporating tabu search into the framework of genetic algorithm. In this paper, we propose a new multi-parent combination operator for generating offspring solutions. A pool updating strategy based on a quality-and-distance criterion is used to manage the population. Experimental comparisons with leading methods for the UBQP problem on 25 large public instances demonstrate the efficacy of our proposed algorithm in terms of both solution quality and computational efficiency.

Zhipeng Lü, Jin-Kao Hao, Fred Glover

Bicriteria Scheduling Problem on the Two-Machine Flowshop Using Simulated Annealing

Abstract

Real life scheduling problems require the decision maker to consider a number of criteria before arriving at any decision. The trade-offs involved in considering several different criteria provide useful insights for the decision maker. Surprisingly, research in the field of multi-objective scheduling has been quite limited when compared to research in single criterion scheduling. The subject of this paper is the bicriteria scheduling problem in a two-machine flowshop. The objective is to find a job sequence that minimizes sum of weighted total flowtime and total tardiness. Based on the problem characteristics, a Simulated Annealing algorithm is developed. The proposed metaheuristic is compared with the branch and bound enumeration algorithm of the integer programming model as well as a modified version of the well-known NEH algorithm. During these evaluations, the experimental design approach and careful statistical analysis have been used to validate the effectiveness of the simulated annealing approach.

Mohammad Mesgarpour, Nureddin Kirkavak, Hakan Ozaktas

A Memetic Algorithm for Workforce Distribution in Dynamic Multi-Skill Call Centres

Abstract

In this paper, we describe a novel approach for workforce distribution in dynamic multi-skill call centres. Dynamic multi-skill call centres require quick adaptations to a changing environment that only fast greedy heuristics can handle. The use of memetic algorithms, which are more complex than ad-hoc heuristics, can guide us to more accurate solutions. In order to apply memetic algorithms to such a dynamic environment, we propose a reformulation of the traditional problem, which combines predictions of future situations with a precise search mechanism, by enlarging the time-frame considered. Concretely, we propose a neural network for predicting call arrivals and the number of available agents, and a memetic algorithm to carry out the assignment of incoming calls to agents, which outperforms classical approaches to this dynamic environment. We also test our method on a real-world environment within a large multinational telephone operator.

David Millán-Ruiz, J. Ignacio Hidalgo

Geometric Generalization of the Nelder-Mead Algorithm

Abstract

The Nelder-Mead Algorithm (NMA) is an almost half-century old method for numerical optimization, and it is a close relative of Particle Swarm Optimization (PSO) and Differential Evolution (DE). Geometric Particle Swarm Optimization (GPSO) and Geometric Differential Evolution (GDE) are recently introduced formal generalization of traditional PSO and DE that apply naturally to both continuous and combinatorial spaces. In this paper, we generalize NMA to combinatorial search spaces by naturally extending its geometric interpretation to these spaces, analogously as what was done for the traditional PSO and DE algorithms, obtaining the Geometric Nelder-Mead Algorithm (GNMA).

Alberto Moraglio, Colin G. Johnson

Guided Ejection Search for the Pickup and Delivery Problem with Time Windows

Abstract

This paper presents an efficient route minimization heuristic for the pickup and delivery problem with time windows (PDPTW) based on guided ejection search (GES). GES is a recently proposed metaheuristc framework and was first applied to the vehicle routing problem with time windows. The existence of the pickup and delivery constraint makes the feasible solution space tightly constrained and then makes the design of effective metaheuristics more difficult. We demonstrate that GES can be successfully applied to such an complicated problem. Experimental results on the Li and Lim’s benchmarks demonstrate that the proposed GES algorithm outperforms existing algorithms and is able to improve 105 best-known solutions out of 298 instances.

Yuichi Nagata, Shigenobu Kobayashi

An Evolutionary Algorithm Guided by Preferences Elicited According to the ELECTRE TRI Method Principles

Abstract

The resolution of a multi-objective optimization problem involves not just a search and computation phase, capable of providing a representative sample of the Pareto-optimal front, but also a decision support process to aid the Decision Maker (DM) to progress in the learning of the trade-offs at stake in different regions of the search space. This is accomplished by integrating in the search process the DM’s preferences to guide the search and limit both the cognitive effort, in assessing Pareto-optimal solutions with distinct characteristics, and the computational effort, by reducing the scope of the search according to the preferences expressed by the DM. The introduction of meaningful preference expression parameters used in the ELECTRE TRI method for sorting problems in the framework of an evolutionary algorithm is proposed. Illustrative results in an operational planning problem in electricity networks are reported.

Eunice Oliveira, Carlos Henggeler Antunes

Multilevel Variable Neighborhood Search for Periodic Routing Problems

Abstract

In this work we present the extension of a variable neighborhood search (VNS) with the multilevel refinement strategy for periodic routing problems. The underlying VNS was recently proposed and performs already well on these problems. We apply a path based coarsening scheme by building fixed (route) segments of customers accounting for the periodicity. Starting at the coarsest level the problem is iteratively refined until the original problem is reached again. This refinement is smoothly integrated into the VNS. Further a suitable solution-based recoarsening is proposed. Results on available benchmark test data as well as on newly generated larger instances show the advantage of the multilevel VNS compared to the standard VNS, yielding better results in usually less CPU time. This new approach is especially appealing for large instances.

Sandro Pirkwieser, Günther R. Raidl

Enhancing Genetic Algorithms by a Trie-Based Complete Solution Archive

Abstract

Genetic algorithms (GAs) share a common weakness with most other metaheuristics: Candidate solutions are in general revisited multiple times, lowering diversity and wasting precious CPU time. We propose a complete solution archive based on a special binary trie structure for GAs with binary representations that efficiently stores all evaluated solutions during the heuristic search. Solutions that would later be revisited are detected and effectively transformed into similar yet unconsidered candidate solutions. The archive’s relevant insert, find, and transform operations all run in time O(l) where l is the length of the solution representation. From a theoretical point of view, the archive turns the GA into a complete algorithm with a clear termination condition and bounded run time. Computational results are presented for Royal Road functions and NK landscapes, indicating the practical advantages.

Günther R. Raidl, Bin Hu

A New Primal-Dual Genetic Algorithm: Case Study for the Winner Determination Problem

Abstract

This paper presents a new evolutionary computing strategy which uses the linear programming duality information to help the search for optimum solutions of hard optimization problems. The algorithm is restarted several times when it is stuck into a local optima. At each restart, the appropriate dual space is constructed. A new population of primal individuals is generated using the information from dual solutions and is considered for next iterations. The pursued goal was not to find the best algorithm for solving winner determination problem, but to prove the method’s viability using the problem as a case study. Experiments on realistic instances were performed.

Madalina Raschip, Cornelius Croitoru

Local Search Algorithms on Graphics Processing Units. A Case Study: The Permutation Perceptron Problem

Abstract

Optimization problems are more and more complex and their resource requirements are ever increasing. Although metaheuristics allow to significantly reduce the computational complexity of the search process, the latter remains time-consuming for many problems in diverse domains of application. As a result, the use of GPU has been recently revealed as an efficient way to speed up the search. In this paper, we provide a new methodology to design and implement efficiently local search methods on GPU. The work has been experimented on the permuted perceptron problem and the experimental results show that the approach is very efficient especially for large problem instances.

Thé Van Luong, Nouredine Melab, El-Ghazali Talbi

Efficient Cycle Search for the Minimum Routing Cost Spanning Tree Problem

Abstract

The Minimum Routing Cost Spanning Tree problem is an optimization problem that strongly benefits from local search. Well-established approaches are the Ahuja-Murty local search and a weaker subtree search used in an evolutionary framework. We present a new and efficient cycle search that has a lower time complexity but achieves the same results as the strong but slow Ahuja-Murty local search. Moreover, we show that an evolutionary framework using this cycle search outperforms previous approaches regarding both quality and time. Our approach is able to find (near-)optimal solutions in all runs for all tested instances.

Steffen Wolf, Peter Merz

Backmatter