draft programme evocop 2012
please note that the final order of presentations may change
Wednesday 11 April
Opening session, Martin Middendorf and Jin-Kao Hao, (11:20-11:25)
Wednesday 11 April
Multi-objective optimisation, (11:25-13:05)
Chair: Enrique Alba
D^2MOPSO: Multi-Objective Particle Swarm Optimizer based on Decomposition and Dominance
Noura Al Moubayed, Andrei Petrovski, John McCall
D2MOPSO 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. Dom- inance 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 D2MOPSO outperforms two state-of-the-art decomposition based evolutionary methods.
Multiobjectivizing the HP Model for Protein Structure Prediction
Mario Garza-Fabre, Eduardo Rodriguez-Tello, Gregorio Toscano-Pulido
The hydrophobic-polar (HP) model for protein structure prediction abstracts the fact that hydrophobic interac- tions 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.
Multi-Pareto-Ranking Evolutionary Algorithm
Wahabou Abdou, Christelle Bloch, Damien Charlet, Francois Spies
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.
Pareto Local Search Algorithms for Anytime Bi-Objective Optimization
Jérémie Dubois-Lacoste, Manuel López-Ibáñez, Thomas Stützle
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.
Wednesday 11 April
Local search based methods (14:30-16:10)
Chair: Günther Raidl
An ILS-based metaheuristic for the Stacker Crane Problem
Thais Avila, Angel Corberan, Isaac Plana, Jose M. Sanchis
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 formu- lation 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.
A Variable Neighborhood Search Approach for the Two-Echelon Location-Routing Problem
Martin Schwengerer, Sandro Pirkwieser, Günther R. Raidl
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 NP-hard 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 suc- cessful 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.
Hyper-Heuristic Based on Iterated Local Search Driven by Evolutionary Algorithm
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.
Intensification/Diversification-Driven ILS for a Graph Coloring Problem
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.
Wednesday 11 April
Hybrid methods (16:30-18:10)
Chair: Christian Blum
Combining heuristic and exact methods to solve the Vehicle Routing problem with pickups, deliveries and time windows
Penny Holborn, Jonathan Thompson, Rhyd Lewis
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.
Domain Reduction Using GRASP Construction Phase For Transmission Expansion Planning Problem
Mohsen Rahmani, Marcos J. Rider, Ruben A. Romero, Miguel Paredes
This paper proposes a new strategy to reduce the combinatorial search space of a mixed integer linear program- ming (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.
Iterated Greedy Algorithms for the Maximal Covering Location Problem
Francisco J. Rodriguez, Christian Blum, Manuel Lozano, Carlos García-Martínez
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.
Pure Strategy or Mixed Strategy?
Jun He, Feidun He, Hongbin Dong
Mixed strategy evolutionary algorithms (EAs) aim at integrating several mutation operators into a single algo- rithm. 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 asymp- totic 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.
Thursday 12 April
Evolutionary computing (11:20-13:00)
Chair: Ochoa Gabriela
An NSGA-II algorithm for the green vehicle routing problem
Jaber Jemai, Manel Zekri, Khaled Mellouli
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 co2 emissions.We review emission factors and tech- niques employed to estimate co2 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.
Genetic algorithms for scheduling devices operation in a water distribution system in response to contamination events
Marco Gavanelli, Maddalena Nonato, Andrea Peano, Stefano Alvisi, Marco Franchini
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 contam- inated 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 and greatly improve upon common sense inspired solutions which are adopted in practice. In particular, we compare different encodings and propose ad hoc cross over 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.
Recurrent Genetic Algorithms: Sustaining Evolvability
Adnan Fakeih, Ahmed Kattan
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. This is done by a feedback loop that recurrently adjusts the fitness values of individuals in population ti based on the fitness of their offspring in population tˆ. The fitness values of population t are re-calculated by assigning the average fitness values of ii the produced offspring in population tˆ to their parents (using fitness reward function) in population t . Hence, ii population ti+1 is generated from population ti using its newly calculated fitness values. This recurrent process of fitness adjustment reinforces evolvability of subsequent generations by insuring that parents at ti are rewarded for producing fit offspring and then given a second chance at reproduction. 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-hard problems and does the same on three continuous optimisation problems when aided by problem encoding information.
The Vehicle Routing Problem with Backhauls: a Multi-objective Evolutionary Approach
In the Vehicle Routing Problem with Backhauls there are linehaul customers, who demand products, and back- haul 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.
Thursday 12 April
Evaluation and applications (14:30-16:10)
Chair: Rhyd Lewis
A Methodology for Comparing the Execution Time of Metaheuristics Running on Different Hardware
Julián Domínguez, Enrique Alba
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.
Clustering Search Heuristic for Solving a Continuous Berth Allocation Problem
Rudinei Oliveira, Geraldo Mauri, Luiz Lorena
Due to the increasing demand for ships carrying containers, the Berth allocation Problem (BAP) can be con- sidered 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 method Clustering Search (CS) with the meta-heuristic Simulated Annealing (SA). The results obtained by CS are compared to another methods found in the literature, thus verifying its competitiveness.
HyFlex: A Benchmark Framework for Cross-domain Heuristic Search
Gabriela Ochoa, Matthew Hyde, Tim Curtois, Jose A. Vazquez-Rodriguez, James Walker, Michel Gendreau, Graham Kendall, Sanja Petrovic, Edmund K. Burke, Andrew J. Parkes
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 satis- fiability, 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.
Splitting method for spatio-temporal sensors deployment in underwater systems
Mathieu Chouchane, Sébastien Paris, François Le Gland, Mustapha Ouladsine
In this paper, we present a novel stochastic optimization algorithm based on the rare events simulation frame- work 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.
Thursday 12 April
Best paper session (16:30-18:10)
Chair: Martin Middendorf
Electrical Load Management in Smart Homes Using Evolutionary Algorithms
Florian Allerding, Marc Premm, Pradyumn Kumar Shukla, Hartmut Schmeck
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 evolutionary algorithms is proposed to control intelligent appliances, decentralized power plants and elec- trical 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 optimization problems.
Exact Computation of the Fitness-Distance Correlation for Pseudoboolean Functions with One Global Optimum
Francisco Chicano, Enrique Alba
Landscape theory provides a formal framework in which combinatorial optimization problems can be theoreti- cally 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.