Skip to main content
main-content

Über dieses Buch

This book constitutes the refereed proceedings of the 12th European Conference on Evolutionary Computation in Combinatorial Optimization, EvoCOP 2012, held in Málaga, Spain, in April 2012, colocated with the Evo* 2012 events EuroGP, EvoBIO, EvoMUSART, and EvoApplications. . The 22 revised full papers presented were carefully reviewed and selected from 48 submissions. The papers present the latest research and discuss current developments and applications in metaheuristics - a paradigm to effectively solve difficult combinatorial optimization problems appearing in various industrial, economic, and scientific domains. Prominent examples of metaheuristics are evolutionary algorithms, simulated annealing, tabu search, scatter search, memetic algorithms, variable neighborhood search, iterated local search, greedy randomized adaptive search procedures, estimation of distribution algorithms, and ant colony optimization.

Inhaltsverzeichnis

Frontmatter

A Methodology for Comparing the Execution Time of Metaheuristics Running on Different Hardware

Abstract
In optimization, search, and learning, it is very common to compare our new results with previous works but, sometimes, we can find some troubles: it is not easy to reproduce the results or to obtain an exact implementation of the original work, or we do not have access to the same processor where the original algorithm was tested for running our own algorithm. With the present work we try to provide the basis for a methodology to characterize the execution time of an algorithm in a processor, given its execution time in another one, so that we could fairly compare algorithms running in different processors. In this paper, we present a proposal for such a methodology, as well as an example of its use applied to two well-known algorithms (Genetic Algorithms and Simulated Annealing) and solving the MAXSAT problem.
Julián Domínguez, Enrique Alba

A Variable Neighborhood Search Approach for the Two-Echelon Location-Routing Problem

Abstract
We consider the two-echelon location-routing problem (2E-LRP), a well-known problem in freight distribution arising when establishing a two-level transport system with limited capacities. The problem is a generalization of the location routing problem (LRP), involving strategic (location), tactical (allocation) and operational (routing) decisions at the same time. We present a variable neighborhood search (VNS) based on a previous successful VNS for the LRP, accordingly adapted as well as extended. The proposed algorithm provides solutions of high quality in short time, making use of seven different basic neighborhood structures parameterized with different perturbation size leading to a total of 21 specific neighborhood structures. For intensification, two consecutive local search methods are applied, optimizing the transport costs efficiently by considering only recently changed solution parts. Experimental results clearly show that our method is at least competitive regarding runtime and solution quality to other leading approaches, also improving upon several best known solutions.
Martin Schwengerer, Sandro Pirkwieser, Günther R. Raidl

An ILS-Based Metaheuristic for the Stacker Crane Problem

Abstract
In this paper we propose a metaheuristic algorithm for the Stacker Crane Problem. This is an NP-hard arc routing problem whose name derives from the practical problem of operating a crane. Here we present a formulation and a lower bound for this problem and propose a metaheuristic algorithm based on the combination of a Multi-start and an Iterated Local Search procedures. Computational results on a large set of instances are presented.
Thais Ávila, Ángel Corberán, Isaac Plana, José M. Sanchis

An NSGA-II Algorithm for the Green Vehicle Routing Problem

Abstract
In this paper, we present and define the bi-objective Green Vehicle Routing Problem GVRP in the context of green logistics. The bi-objective GVRP states for the problem of finding routes for vehicles to serve a set of customers while minimizing the total traveled distance and the co 2 emissions. We review emission factors and techniques employed to estimate co 2 emissions and integrate them into the GVRP definition and model. We apply the NSGA-II evolutionary algorithm to solve GVRP benchmarks and perform statistical analysis to evaluate and validate the obtained results. The results show that the algorithm obtain good results and prove the explicit interest grant to emission minimization objective.
Jaber Jemai, Manel Zekri, Khaled Mellouli

Clustering Search Heuristic for Solving a Continuous Berth Allocation Problem

Abstract
Due to the increasing demand for ships carrying containers, the Berth Allocation Problem (BAP) can be considered as a major optimization problem in marine terminals. In this context, we propose a heuristic to solve a continuous case of the BAP. This heuristic is based on the application of the Clustering Search (CS) method with the Simulated Annealing (SA) metaheuristic. The results obtained by CS are compared to other methods found in the literature and its competitiveness is verified.
Rudinei Martins de Oliveira, Geraldo Regis Mauri, Luiz Antonio Nogueira Lorena

Combining Heuristic and Exact Methods to Solve the Vehicle Routing Problem with Pickups, Deliveries and Time Windows

Abstract
The vehicle routing problem with pickups, deliveries and time windows (PDPTW) is an important member in the class of vehicle routing problems. In this paper a general heuristic to construct an initial feasible solution is proposed and compared with other construction methods. New route reconstruction heuristics are then shown to improve on this. These reconstruction heuristics look to reorder individual routes and recombine multiple routes to decrease the number of vehicles used in the solution. A tabu search scheme where the attribute to be recorded has been specifically adapted to the PDPTW is proposed. A new method based on branch and bound optimisation attempts to optimise the final ordering of requests in routes to further improve the solutions. Results are analysed for a standard set of benchmark instances and are shown to be competitive with the state of the art.
Penny L. Holborn, Jonathan M. Thompson, Rhyd Lewis

D 2 MOPSO: Multi-Objective Particle Swarm Optimizer Based on Decomposition and Dominance

Abstract
D 2 MOPSO is a multi-objective particle swarm optimizer that incorporates the dominance concept with the decomposition approach. Whilst decomposition simplifies the multi-objective problem (MOP) by rewriting it as a set of aggregation problems, solving these problems simultaneously, within the PSO framework, might lead to premature convergence because of the leader selection process which uses the aggregation value as a criterion. Dominance plays a major role in building the leader’s archive allowing the selected leaders to cover less dense regions avoiding local optima and resulting in a more diverse approximated Pareto front. Results from 10 standard MOPs show D 2 MOPSO outperforms two state-of-the-art decomposition based evolutionary methods.
Noura Al Moubayed, Andrei Petrovski, John McCall

Domain Reduction Using GRASP Construction Phase for Transmission Expansion Planning Problem

Abstract
This paper proposes a new strategy to reduce the combinatorial search space of a mixed integer linear programming (MILP) problem. The construction phase of greedy randomized adaptive search procedure (GRASP-CP) is employed to reduce the domain of the integer variables of the transportation model of the transmission expansion planning (TM-TEP) problem. This problem is a MILP and very difficult to solve specially for large scale systems. The branch and bound (BB) algorithm is used to solve the problem in both full and the reduced search space. The proposed method might be useful to reduce the search space of those kinds of MILP problems that a fast heuristic algorithm is available for finding local optimal solutions. The obtained results using some real test systems show the efficiency of the proposed method.
Mohsen Rahmani, Ruben A. Romero, Marcos J. Rider, Miguel Paredes

Electrical Load Management in Smart Homes Using Evolutionary Algorithms

Abstract
In this paper, we focus on a real world scenario of energy management of a smart home. External variable signals, reflecting the low voltage grid’s state, are used to address the challenge of balancing energy demand and supply. The problem is formulated as a nonlinear integer programming problem and a load management system, based on a customized evolutionary algorithm with local search, is proposed to control intelligent appliances, decentralized power plants and electrical storages in an optimized way with respect to the given external signals. The nonlinearities present in the integer programming problem makes it difficult for exact solvers. The results of this paper show the efficacy of evolutionary algorithms for solving such combinatorial problems.
Florian Allerding, Marc Premm, Pradyumn Kumar Shukla, Hartmut Schmeck

Exact Computation of the Fitness-Distance Correlation for Pseudoboolean Functions with One Global Optimum

Abstract
Landscape theory provides a formal framework in which combinatorial optimization problems can be theoretically characterized as a sum of a special kind of landscapes called elementary landscapes. The decomposition of the objective function of a problem into its elementary components can be exploited to compute summary statistics. We present closed-form expressions for the fitness-distance correlation (FDC) based on the elementary landscape decomposition of the problems defined over binary strings in which the objective function has one global optimum. We present some theoretical results that raise some doubts on using FDC as a measure of problem difficulty.
Francisco Chicano, Enrique Alba

Genetic Algorithms for Scheduling Devices Operation in a Water Distribution System in Response to Contamination Events

Abstract
This paper heuristically tackles a challenging scheduling problem arising in the field of hydraulic distribution systems in case of a contamination event, that is, optimizing the scheduling of a set of tasks so that the consumed volume of contaminated water is minimized. Each task consists of manually activating a given device, located on the hydraulic network of the water distribution system. In practice, once contamination has been detected, a given number of response teams move along the network to operate each device on site. The consumed volume of contaminated water depends on the time at which each device is operated, according to complex hydraulic laws, so that the value associated to each schedule must be evaluated by a hydraulic simulation.
We explore the potentials of Genetic Algorithms as a viable tool for tackling this optimization-simulation problem. We compare different encodings and propose ad hoc crossover operators that exploit the combinatorial structure of the feasible region, featuring hybridization with Mixed Integer Linear Programming.
Computational results are provided for a real life hydraulic network of average size, showing the effectiveness of the approach. Indeed, we greatly improve upon common sense inspired solutions which are commonly adopted in practice.
Marco Gavanelli, Maddalena Nonato, Andrea Peano, Stefano Alvisi, Marco Franchini

HyFlex: A Benchmark Framework for Cross-Domain Heuristic Search

Abstract
This paper presents HyFlex, a software framework for the development of cross-domain search methodologies. The framework features a common software interface for dealing with different combinatorial optimisation problems and provides the algorithm components that are problem specific. In this way, the algorithm designer does not require a detailed knowledge of the problem domains and thus can concentrate his/her efforts on designing adaptive general-purpose optimisation algorithms. Six hard combinatorial problems are fully implemented: maximum satisfiability, one dimensional bin packing, permutation flow shop, personnel scheduling, traveling salesman and vehicle routing. Each domain contains a varied set of instances, including real-world industrial data and an extensive set of state-of-the-art problem specific heuristics and search operators. HyFlex represents a valuable new benchmark of heuristic search generality, with which adaptive cross-domain algorithms are being easily developed and reliably compared.This article serves both as a tutorial and a as survey of the research achievements and publications so far using HyFlex.
Gabriela Ochoa, Matthew Hyde, Tim Curtois, Jose A. Vazquez-Rodriguez, James Walker, Michel Gendreau, Graham Kendall, Barry McCollum, Andrew J. Parkes, Sanja Petrovic, Edmund K. Burke

Hyper-Heuristic Based on Iterated Local Search Driven by Evolutionary Algorithm

Abstract
This paper proposes an evolutionary-based iterative local search hyper-heuristic approach called Iterated Search Driven by Evolutionary Algorithm Hyper-Heuristic (ISEA). Two versions of this algorithm, ISEA-chesc and ISEA-adaptive, that differ in the re-initialization scheme are presented. The performance of the two algorithms was experimentally evaluated on six hard optimization problems using the HyFlex experimental framework and the algorithms were compared with algorithms that took part in the CHeSC 2011 challenge. Achieved results are very promising, the ISEA-adaptive would take the second place in the competition. It shows how important for good performance of this iterated local search hyper-heuristic is the re-initialization strategy.
Jiří Kubalík

Intensification/Diversification-Driven ILS for a Graph Coloring Problem

Abstract
This paper presents an extension of the ILS algorithm, called ID-ILS, by introducing new local search devices that enforce an efficient tradeoff of intensification and diversification. Experiments performed on the DIMACS benchmarks show that our method is competitive with the best coloring algorithms.
Samir Loudni

Iterated Greedy Algorithms for the Maximal Covering Location Problem

Abstract
The problem of allocating a set of facilities in order to maximise the sum of the demands of the covered clients is known as the maximal covering location problem. In this work we tackle this problem by means of iterated greedy algorithms. These algorithms iteratively refine a solution by partial destruction and reconstruction, using a greedy constructive procedure. Iterated greedy algorithms have been applied successfully to solve a considerable number of problems. With the aim of providing additional results and insights along this line of research, this paper proposes two new iterated greedy algorithms that incorporate two innovative components: a population of solutions optimised in parallel by the iterated greedy algorithm, and an improvement procedure that explores a large neighbourhood by means of an exact solver. The benefits of the proposal in comparison to a recently proposed decomposition heuristic and a standalone exact solver are experimentally shown.
Francisco J. Rodriguez, Christian Blum, Manuel Lozano, Carlos García-Martínez

Multiobjectivizing the HP Model for Protein Structure Prediction

Abstract
The hydrophobic-polar (HP) model for protein structure prediction abstracts the fact that hydrophobic interactions are a dominant force in the protein folding process. This model represents a hard combinatorial optimization problem, which has been widely addressed using evolutionary algorithms and other metaheuristics. In this paper, the multiobjectivization of the HP model is proposed. This originally single-objective problem is restated as a multiobjective one by decomposing the conventional objective function into two independent objectives. By using different evolutionary algorithms and a large set of test cases, the new alternative formulation was compared against the conventional single-objective problem formulation. As a result, the proposed formulation increased the search performance of the implemented algorithms in most of the cases. Both two- and three-dimensional lattices are considered. To the best of authors’ knowledge, this is the first study where multiobjective optimization methods are used for solving the HP model.
Mario Garza-Fabre, Eduardo Rodriguez-Tello, Gregorio Toscano-Pulido

Multi-Pareto-Ranking Evolutionary Algorithm

Abstract
This paper proposes a new multi-objective genetic algorithm, called GAME, to solve constrained optimization problems. GAME uses an elitist archive, but it ranks the population in several Pareto fronts. Then, three types of fitness assignment methods are defined: the fitness of individuals depends on the front they belong to. The crowding distance is also used to preserve diversity. Selection is based on two steps: a Pareto front is first selected, before choosing an individual among the solutions it contains. The probability to choose a given front is computed using three parameters which are tuned using the design of experiments. The influence of the number of Pareto fronts is studied experimentally. Finally GAME’s performance is assessed and compared with three other algorithms according to the conditions of the CEC 2009 competition.
Wahabou Abdou, Christelle Bloch, Damien Charlet, François Spies

Pareto Local Search Algorithms for Anytime Bi-objective Optimization

Abstract
Pareto local search (PLS) is an extension of iterative improvement methods for multi-objective combinatorial optimization problems and an important part of several state-of-the-art multi-objective optimizers. PLS stops when all neighbors of the solutions in its solution archive are dominated. If terminated before completion, it may produce a poor approximation to the Pareto front. This paper proposes variants of PLS that improve its anytime behavior, that is, they aim to maximize the quality of the Pareto front at each time step. Experimental results on the bi-objective traveling salesman problem show a large improvement of the proposed anytime PLS algorithm over the classical one.
Jérémie Dubois-Lacoste, Manuel López-Ibáñez, Thomas Stützle

Pure Strategy or Mixed Strategy?

An Initial Comparison of Their Asymptotic Convergence Rate and Asymptotic Hitting Time
Abstract
Mixed strategy evolutionary algorithms (EAs) aim at integrating several mutation operators into a single algorithm. However no analysis has been made to answer the theoretical question: whether and when is the performance of mixed strategy EAs better than that of pure strategy EAs? In this paper, asymptotic convergence rate and asymptotic hitting time are proposed to measure the performance of EAs. It is proven that the asymptotic convergence rate and asymptotic hitting time of any mixed strategy (1+1) EA consisting of several mutation operators is not worse than that of the worst pure strategy (1+1) EA using only one mutation operator. Furthermore it is proven that if these mutation operators are mutually complementary, then it is possible to design a mixed strategy (1+1) EA whose performance is better than that of any pure strategy (1+1) EA using only one mutation operator.
Jun He, Feidun He, Hongbin Dong

Recurrent Genetic Algorithms: Sustaining Evolvability

Abstract
This paper proposes a new paradigm, referred to as Recurrent Genetic Algorithms (RGA), to sustain Genetic Algorithm (GA) evolvability and effectively improves its ability to find superior solutions. RGA attempts to continually recover evolvability loss caused by the canonical GA iteration process. It borrows the term Recurrent from the taxonomy of Neural Networks (NN), in which a Recurrent NN (RNN) is a special type of network that uses a feedback loop, usually to account for temporal information embedded in the sequence of data points presented to the network. Unlike RNN, the temporal dimension in our algorithm pertains to the sequential nature of the evolution process itself; and not to the data sampled from the problem solution space. Empirical evidence shows that the new algorithm better preserves the population’s diversity, higher number of constructive crossovers and mutations. Furthermore, evidence shows that the RGA outperforms the standard GA on two NP problems and does the same on three continuous optimisation problems when aided by problem encoding information.
Adnan Fakeih, Ahmed Kattan

Splitting Method for Spatio-temporal Sensors Deployment in Underwater Systems

Abstract
In this paper, we present a novel stochastic optimization algorithm based on the rare events simulation framework for sensors deployment in underwater systems. More precisely, we focus on finding the best spatio-temporal deployment of a set of sensors in order to maximize the detection probability of an intelligent and randomly moving target in an area under surveillance. Based on generalized splitting technique with a dedicated Gibbs sampler, our approach does not require any state-space discretization and rely on the evolutionary framework.
Mathieu Chouchane, Sébastien Paris, François Le Gland, Mustapha Ouladsine

The Vehicle Routing Problem with Backhauls: A Multi-objective Evolutionary Approach

Abstract
In the Vehicle Routing Problem with Backhauls there are linehaul customers, who demand products, and backhaul customers, who supply products, and there is a fleet of vehicles available for servicing customers. The problem consists in finding a set of routes with the minimum cost, such that all customers are serviced. A generalization of this problem considers the collection from the backhaul customers optional. If the number of vehicles, the cost, and the uncollected demand are assumed to be equally important objectives, the problem can be tackled as a multi-objective optimization problem. In this paper, we solve these as multi-objective problems with an adapted previously proposed evolutionary algorithm and evaluate its performance with proper tools.
Abel Garcia-Najera

Backmatter

Weitere Informationen

Premium Partner

    Bildnachweise