Evostar 2015

The Leading European Event on Bio-Inspired Computation.

Copenhagen, Denmark, 8-10 April 2015

Call for papers:

EvoCOP

The 15th European Conference on Evolutionary Computation in Combinatorial Optimisation

April 08-10, 2015
Copenhagen, Denmark

Part of Evo* 2015 (http://www.evostar.org) including: EuroGP, EvoCOP, EvoMUSART and EvoApplications

The 15th European Conference on Evolutionary Computation in Combinatorial Optimisation is a multidisciplinary conference that brings together researchers working on metaheuristics for solving difficult combinatorial optimization problems appearing in various industrial, economic, and scientific domains. Prominent examples of metaheuristics include: evolutionary algorithms, simulated annealing, tabu search, scatter search and path relinking, memetic algorithms, ant colony and bee colony optimization, particle swarm optimization, variable neighbourhood search, iterated local search, greedy randomized adaptive search procedures, estimation of distribution algorithms, and hyperheuristics. Successfully solved problems include scheduling, timetabling, network design, transportation and distribution problems, vehicle routing, travelling salesman, graph problems, satisfiability, energy optimization problems, packing problems, planning problems, and general mixed integer programming.

The EvoCOP 2015 conference will be held in the city of Copenhagen, Denmark. It will be held in conjunction with EuroGP (the 18th European Conference on Genetic Programming), EvoMUSART (13th European conference on evolutionary and biologically inspired music, sound, art and design) and EvoApplications (specialist events on a range of evolutionary computation topics and applications), in a joint event collectively known as Evo*.

Areas of Interest and Contributions

Topics of interest include, but are not limited to:

Applications of metaheuristics to combinatorial optimization problems
Novel application domains for metaheuristic optimisation methods
Representation techniques
Neighborhoods and efficient algorithms for searching them
Variation operators for stochastic search methods
Constraint-handling techniques
Hybrid methods and hybridization techniques
Parallelization
Theoretical developments
Search space and landscape analyses
Comparisons between different (also exact) techniques
Metaheuristics and machine learning
Ant colony optimisation
Artificial immune systems
Genetic programming and Genetic algorithms
(Meta-)heuristics
Scatter search
Particle swarm optimisation
Tabu search, iterated local search and variable neighborhood search
Memetic algorithms
Hyper-heuristics and autonomous search
Estimation of distribution algorithms
String processing
Scheduling and timetabling
Network design
Vehicle routing
Graph problems
Satisfiability
Packing and cutting problems
Energy optimization problems
Practical solving of NP-hard problems
Mixed integer programming
Multi-objective optimisation
Grid computing
Combinatorial optimisation
Nature and Bio-inspired methods
Quantum computing and quantum annealing
Optimization in Cloud computing
Search-based software engineering

Publication Details

All accepted papers will be presented orally at the conference and printed in the proceedings published by Springer in the LNCS series (see LNCS volumes 2037, 2279, 2611, 3004, 3448, 3906, 4446, 4972, 5482, 6022, 6622, 7245, 7832 and 8600 for the previous proceedings).

Submission Details

Submissions must be original and not published elsewhere. The submissions will be peer reviewed by members of the program committee. The authors of accepted papers will have to improve their paper on the basis of the reviewers comments and will be asked to send a camera ready version of their manuscripts. At least one author of each accepted work has to register for the conference, attend the conference and present the work.

The reviewing process will be double-blind, please omit information about the authors in the submitted paper. Submit your manuscript in Springer LNCS format.

Page limit: 12 pages

Submission link: http://myreview.csregistry.org/evocop15/

EvoCOP Programme Chairs

  • Gabriela Ochoa
    University of Stirling, Scotland, UK
    gabriela.ochoa(at)cs.stir.ac.uk
  • Francisco Chicano
    University of Malaga, Spain
    chicano(at)lcc.uma.es

EvoCOP Programme Committee

  • Adnan Acan , Eastern Mediterranean University , Turkey
  • Enrique Alba , University of Malaga , Spain
  • Mehmet-Emin Aydin , University of Bedfordshire , UK
  • Ruibin Bai , University of Nottingham , UK
  • Matthieu Basseur , University of Angers , France
  • Thomas Bartz-Beielstein , Cologne University of Applied Sciences, Germany
  • Maria J. Blesa , Technical University of Catalonia , Spain
  • Christian Blum , IKERBASQUE - Basque Foundation for Science , Spain
  • Sandy Brownlee , University of Stirling , Scotland UK
  • Pedro Castillo , Universidad de Granada , Spain
  • Francisco Chicano , Universidad de Malaga , Spain
  • Carlos Coello-Coello , CINVESTAV-IPN , Mexico
  • Peter Cowling , University of York , UK
  • Karl Doerner , Johannes Kepler University Linz , Austria
  • Benjamin Doerr , LIX-Ecole Polytechnique , France
  • Bernd Freisleben , University of Marburg , Germany
  • Adrien Goeffon , University of Angers , France
  • Jens Gottlieb , SAP , Germany
  • Walter Gutjahr , University of Vienna , Austria
  • Jin-Kao Hao , University of Angers , France
  • Emma Hart , Edinburgh Napier University , Scotland UK
  • Richard Hartl , University of Vienna , Austria
  • Geir Hasle , SINTEF Applied Mathematics , Norway
  • Istvan Juhos , University of Szeged , Hungary
  • Graham Kendall , University of Nottingham , UK
  • Joshua Knowles , University of Manchester , UK
  • Mario Koeppen , Kyushu Institute of Technology , Japan
  • Frederic Lardeux , University of Angers , France
  • Rhyd Lewis , Cardiff University , UK
  • Arnaud Liefooghe , University Lille 1 , France
  • Jose Antonio Lozano , University of the Basque Country , Spain
  • Gabriel Luque , University of Malaga , Spain
  • Penousal Machado , University of Coimbra , Portugal
  • Jorge Maturana , Universidad Austral de Chile , Chile
  • Barry McCollum , Queen's University Belfast , UK
  • David Meignan , University of Osnabruck , Germany
  • Juan Julian Merelo , University of Granada , Spain
  • Peter Merz , University of Applied Sciences and Arts Hannover , Germany
  • Martin Middendorf , University of Leipzig , Germany
  • Julian Molina , University of Malaga , Spain
  • Christine L. Mumford , Cardiff University , UK
  • Eric Monfroy , University of Nantes , France
  • Nysret Musliu , Vienna University of Technology , Austria
  • Gabriela Ochoa , University of Stirling , Scotland UK
  • Beatrice Ombuki-Berman , Brock University , Canada
  • Mario Pavone , University of Catania , Italy
  • Francisco J. Pereira , Universidade de Coimbra , Portugal
  • Jakob Puchinger , Austrian Institute of Technology , Austria
  • Günther Raidl , Vienna University of Technology , Austria
  • Marcus Randall , Bond University , Australia
  • Marc Reimann , University of Graz , Austria
  • Eduardo Rodriguez-Tello , Civerstav - Tamaulipas , Mexico
  • Peter Ross , Edinburgh Napier University , UK
  • Frederic Saubion , University of Angers , France
  • Marc Schoenauer , INRIA , France
  • Patrick Siarry , University of Paris 12 , France
  • Kevin Sim , Edinburgh Napier University , UK
  • Jim Smith , University of the West of England , UK
  • Giovanni Squillero , Politecnico di Torino , Italy
  • Thomas Stuetzle , Universite Libre de Bruxelles , Belgium
  • Andrew M. Sutton , Friedrich-Schiller-University Jena , Germany
  • El-ghazali Talbi , Universite des Sciences et Technologies de Lille , France
  • Renato Tinós , University of Sao Paulo , Brasil
  • Jano van Hemert , University of Edinburgh , UK
  • Nadarajen Veerapen , University of Stirling , Scotland UK
  • Sebastien Verel , Universite du Littoral Cote d'Opale , France
  • Takeshi Yamada , NTT Communication Science Laboratories , Kyoto-Japan
  • Shengxiang Yang - De Montfort University, UK

Accepted paper abstracts

  • A Biased Random-Key Genetic Algorithm for the Cloud Resource Management Problem
    • Leonard Heilig, Eduardo Lalla-Ruiz, Stefan Voß
    Flexible use options and associated cost savings of cloud computing are increasingly attracting the interest from both researchers and practitioners. Since cloud providers offer various cloud services in different forms, there is a great potential of optimizing the selection of those services from the consumer perspective. In this paper, we address the Cloud Resource Management Problem that is a recent optimization problem aimed at reducing the payment cost and the execution time of consumer applications. In the related literature, there is one approach that successfully addresses this problem based on a Greedy Randomized Adaptive Search Procedure (GRASP). Due to the fact, that consumers require fast and high-quality solutions to economically automate cloud resource management and deployment processes, we propose an efficient Biased Random-Key Genetic Algorithm (BRKGA-CC). The computational experiments over a benchmark suite generated based on real data indicate that the performance of our approach outperforms the approaches proposed in the literature.
  • A computational comparison of different algorithms for very large p-median problems
    • Pascal Rebreyend, Laurent Lemarchand, Reinhardt Eurler
    In this paper, we propose a new method for solving large-scale p-median problem instances based on real data. We compare different approaches both in terms of runtime, memory footprint and quality of solutions obtained. In order to test the different methods on real data, we introduce a new benchmark for the $p$-median problem based on real Swedish data. Because of the size of the problem addressed, up to 1938 candidate nodes, a number of algorithms, both exact and heuristic, are considered. We also propose an improved hybrid version of a Genetic Algorithm called impGA. Experiments show that impGA behaves as well as other methods for the standard set of medium-size problems taken from Beasley's benchmark, but produces comparatively good results in terms of quality, runtime and memory footprint on our specific benchmark
  • A New Solution Representation for the Firefighter Problem
    • Bin Hu, Andreas Windbichler, Günther Raidl
    The firefighter problem (FFP) is used as a model to simulate how a fire breaks out and spreads to its surroundings over a discrete time period. The goal is to deploy a given number of firefighters on strategic points at each time step to contain the fire in a most efficient way, so that as many areas are saved from the fire as possible. In this paper we introduce a new solution representation for the FFP which can be applied in metaheuristic approaches. Compared to the existing approach in the literature, it is more compact in a sense that the solution space is smaller although the complexity for evaluating a solution remains unchanged. We use this representation in conjunction with a variable neighborhood search (VNS) approach to tackle the FFP. To speed up the optimization process, we propose an incremental evaluation technique that omits unnecessary re-calculations. Computational tests were performed on a benchmark instance set containing 120 random graphs of different size and density. Results indicate that our VNS approach is highly competitive with existing state-of-the-art approaches.
  • A Variable Neighborhood Search Approach for the Interdependent Lock Scheduling Problem
    • Matthias Prandtstetter, Ulrike Ritzinger, Peter Schmidt, Mario Ruthmair
    We investigate a so far not examined problem called the Interdependent Lock Scheduling Problem. A Variable Neighborhood Search approach is proposed for finding lock schedules along the Austrian part of the Danube River in order to minimize the overall ship travel times. In computational experiments the performance of our approach is assessed and compared to real-world ship trajectories. Notable improvements can be achieved. In addition, the number of (empty) lockages can be significantly reduced when taking them into account during optimization without loosing too much of quality in travel time optimization.
  • A Variable Neighborhood Search for the Generalized Vehicle Routing Problem with Stochastic Demands
    • Benjamin Biesinger, Bin Hu, Günther Raidl
    In this work we consider the generalized vehicle routing problem with stochastic demands (GVRPSD) being a combination of the generalized vehicle routing problem, in which the nodes are partitioned into clusters, and the vehicle routing problem with stochastic demands, where the exact demands of the nodes are not known beforehand. It is an NP-hard problem for which we propose a variable neighborhood search (VNS) approach to minimize the expected tour length through all clusters. We use a permutation encoding for the cluster sequence and consider the preventive restocking strategy where the vehicle restocks before it potentially runs out of goods. The exact solution evaluation is based on dynamic programming and is very time-consuming. Therefore we propose a multi-level evaluation scheme to significantly reduce the time needed for solution evaluations. Two different algorithms for finding an initial solution and three well-known neighborhood structures for permutations are used within the VNS. Results show that the multi-level evaluation scheme is able to drastically reduce the overall run-time of the algorithm and that it is essential to be able to tackle larger instances. A comparison to an exact approach shows that the VNS is able to find an optimal or near-optimal solution in much shorter time.
  • An Iterated Local Search Algorithm for Solving the Orienteering Problem with Time Windows
    • Aldy Gunawan, Hoong Chuin Lau, Kun Lu
    The Orienteering Problem with Time Windows (OPTW) is a variant of the Orienteering Problem (OP). Given a set of nodes including their scores, service times and time windows, the goal is to maximize the total of scores collected by a particular route considering a predefined time window during which the service has to start. We propose an Iterated Local Search (ILS) algorithm to solve the OPTW, which is based on several local search operations, such as Swap, 2-opt, Insert and Replace. We also implement the combination between Acceptance Criterion and Perturbation mechanisms to control the balance between diversification and intensification of the search. In Perturbation, Shake strategy is introduced. The computational results obtained by our proposed algorithm are compared against optimal solutions or best-known solution values obtained by state-of-the-art algorithms. We show experimentally that our proposed algorithm is effective on well-known benchmark instances available in the literature. It is also able to improve the best-known solution of some benchmark instances.
  • Analysis of Solution Quality of a Multiobjective Optimization-based Evolutionary Algorithm for Knapsack Problem
    • Jun He, Yong Wang, Yuren Zhou
    Multi-objective optimisation is regarded as one of the most promising ways for dealing with constrained optimisation problems in evolutionary optimisation. This paper presents a theoretical investigation of a multi-objective optimisation evolutionary algorithm for solving the 0-1 knapsack problem. Two initialisation methods are considered in the algorithm: local search initialisation and greedy search initialisation. Then the solution quality of the algorithm is analysed in terms of the approximation ratio.
  • Evolving Deep Recurrent Neural Networks Using Ant Colony Optimization
    • Travis Desell, Sophine Clachar, James Higgins, Brandon Wild
    This paper presents a novel strategy for using ant colony optimization (ACO) to evolve the structure of deep recurrent neural networks. While versions of ACO for continuous parameter optimization have been previously used to train the weights of neural networks, to the authors’ knowledge they have not been used to actually design neural networks. The strategy presented is used to evolve deep neural networks with up to 5 hidden and 5 recurrent layers for the challenging task of predicting general aviation flight data, and is shown to provide improvements of 63% for airspeed, a 97% for altitude and 120% for pitch over previously best published results, while at the same time not requiring additional input neurons for residual values. The strategy presented also has many benefits for neuro-evolution, including the fact that it is easily parallizable and scalable, and can operate using any method for training neural networks. Further, the networks it evolves can typically be trained in fewer iterations than fully connected networks
  • Hyper-heuristic Operator Selection and Acceptance Criteria
    • Richard Marshall, Mark Johnston, Mengjie Zhang
    Earlier research has shown that an adaptive hyper-heuristic can be a successful approach to solving combinatorial optimisation problems. By using a pairing of an operator (low-level heuristic) selection vector and a solution acceptance criterion, an adaptive hyper-heuristic can manage development of a "good" solution within an unseen low-level problem domain in a commercially realistic computational time. However not all selection vectors and solution acceptance criteria pairings deliver competitive results when faced with differing problem instance features and computational time limits. We evaluate pairings of six different operator selection vectors and eight solution acceptance criteria, and monitor the performance of the adaptive hyper-heuristic when applying each pairing to a set of Capacitated Vehicle Routing Problem instances of the same size but with different features. The results show that a few pairings of operator selection vector and acceptance criterion perform consistently well, while others require a longer computational time to deliver competitive results. We also investigate some of the features of a problem instance that may influence the performance of the selection vector and acceptance criterion pairings.
  • Improving the Performance of the Germinal Center Center Artificial Immune System using є-dominance: A Multi-objective Knapsack Problem Case Study
    • Ayush Joshi, Christine Zarges, Jonathan Rowe
    The Germinal center artificial immune system (GC-AIS) is a novel immune algorithm inspired by recent research in immunology, which requires very few parameters to be set by hand. The population of solutions in GC-AIS is dynamic in nature and has no restrictions on its size which can cause problems of population explosion, where the population keeps growing very rapidly, leading to wasteful fitness evaluations. In this paper we try to address this problem in the GC-AIS by incorporating є-dominance, which is a well-known mechanism in multi-objective optimization to regulate population size. The improved variant of GC-AIS is compared with a well-known multi-objective evolutionary algorithm NSGA-II on the multi-objective knapsack problem. We show that our improved GC-AIS performs better than NSGA-II on the instances of the knapsack problem taken from (Zitzler& Thiele, 1999) inheriting the same benefits of having to set fewer parameters manually
  • Mixing Network Extremal Optimization for Community Structure Detection
    • Mihai Suciu, Rodica Ioana Lung, Noemi Gasko
    Mixing Network Extremal Optimization is a new algorithm designed to identify the community structure in networks by using a game theoretic approach and a network mixing mechanism as a diversity preserving method. Numerical experiments performed on synthetic and real networks illustrate the potential of the approach.
  • Multi-Start Iterated Local Search for the Mixed Fleet Vehicle Routing Problem with Heterogenous Electric Vehicles
    • Ons Sassi, Wahiba Ramdane Cherif-Khettaf, Ammar Oulamara
    This paper deals with a real world application that consists in the vehicle routing problem with mixed fleet of conventional and heterogenous electric vehicles including new constraints, denoted VRPHFCC. This problem is defined by a set of customers that have to be served by a mixed fleet of vehicles composed of heterogenous fleet of Electric Vehicles (EVs) with distinct battery capacities and operating costs, and a set of identical Conventional Vehicles (CVs). The EVs could be charged during their trips in the available charging stations, which offer charging with a given technology of chargers and time dependent charging costs. Charging stations are also subject to operating time window constraints. EVs are subject to the compatibility constraints with the available charging technologies and they could be partially charged. Intermittent charging at the depot is also allowed provided that constraints related to the electricity grid are satisfied. The objective is to minimize the number of employed vehicles and to minimize the total travel and charging costs. The developed multi-start algorithm is based on the Iterated Local Search metaheuristic which uses a Large Neighborhood Search with two different insertion strategies in the Local Search procedure. Different implementation schemes of the proposed method are tested on a set of real data instances with up to 550 customers as well as on generalized benchmark instances
  • On the Complexity of Searching the Linear Ordering Problem Neighborhoods
    • Benjamin Correal, Philippe Galinier
    The linear ordering problem is an important and much studied NP-hard problem. The most efficient neighborhood for this problem is the so-called insert neighborhood. According to the literature, the best insert move can be found in O(n^2). In this paper, we present a tree data structure that we name the maximum partial sum data structure. We show that using this data structure makes it possible to find, iteration after iteration, a best insert move in O(n log n) -- after an initialization in O(n^2). We also consider an alternative neighborhood named the interchange neighborhood. We show that this neighborhood can be searched in O(n^2) -- versus O(n^3) in the best existing implementation.
  • Runtime Analysis of (1+1) Evolutionary Algorithm Controlled with Q-learning using Greedy Exploration Strategy on OneMax+ZeroMax Problem
    • Denis Antipov, Maxim Buzdalov, Benjamin Doerr
    The setting is an EA that must contend with more than a single objective, but in contrast to the classical multi-objective setting, the paper deals with a so-called "helper-objective" setting in which a single-objective optimization algorithm needs to switch between multiple objectives from time to time. The EA+RL approach augments a single-objective EA with a reinforcement learning strategy to learn the correct objective for optimization. In this paper, the extra objective function is misleading (indeed it is in some sense the additive inverse of the target objective). Therefore, the runtime of the EA must account for the time that the reinforcement learning procedure takes to learn the extra objective function is worthless
  • The new memetic algorithm HEAD for graph coloring: an easy way for managing diversity
    • Laurent Moalic, Alexandre Gondran
    This paper presents an effective memetic approach HEAD designed for coloring difficult graphs. In this algorithm a powerful tabu search is used inside a very specific population of individuals. Indeed, the main characteristic of HEAD is to work with a population of only two individuals. This provides a very simple algorithm with neither selection operator nor replacement strategy. Because of its simplicity, HEAD allows an easy way for managing the diversity. We focus this work on the impact of this diversity management on well-studied graphs of the DIMACS challenge benchmarks, known to be very difficult to solve. A detailed analysis is provided for three graphs on which HEAD finds a legal coloring with less colors than reference algorithms: DSJC500.5 with 47 colors, DSJC1000.5 with 82 colors and flat1000_76_0 with 81 colors.The analysis performed in this work will allow to improve HEAD efficiency in terms of computation time and maybe to decrease the number of needed colors for other graphs.
  • The Sim-EA Algorithm with Operator Autoadaptation for the Multiobjective Firefighter Problem
    • Krzysztof Michalak
    The firefighter problem is a graph-based optimization problem that can be used for modelling the spread of fires, and also for studying the dynamics of epidemics. Recently, this problem gained interest from the soft computing research community and papers were published on applications of ant colony optimization and evolutionary algorithms to this problem. Also, the multiobjective version of the problem was formulated. In this paper a multipopulation algorithm Sim-EA is applied to the multiobjective version of the firefighter problem. The algorithm optimizes firefighter assignment for a predefined set of weight vectors, which determine the importance of individual objectives. A migration mechanism is used for improving the effectiveness of the algorithm. Obtained results confirm that the multipopulation approach works better than the decomposition approach in which a single specimen is assigned to each direction. Given less computational resources than the decomposition approach, the Sim-EA algorithm produces better results than a decomposition-based algorithm.
  • True Pareto Fronts for Multi-Objective AI Planning Instances
    • Alexandre Quemy, Marc Schoenauer
    Multi-objective AI planning suffers from a lack of benchmarks with known Pareto Fronts. A tunable benchmark generator is proposed, together with a specific solver that provably computes the true Pareto Front of the resulting instances. A wide range of Pareto Front shapes of various difficulties can be obtained by varying the parameters of the generator. The experimental performances of an actual implementation of the exact solver are demonstrated, and some large instances with remarkable Pareto Front shapes are proposed, that will Multi-objective AI planning suffers from a lack of benchmarks with known Pareto Fronts. A tunable benchmark generator is proposed, together with a specific solver that provably computes the true Pareto Front of the resulting instances. A wide range of Pareto Front shapes of various difficulty can be obtained by varying the parameters of the generator. The experimental performances of an actual implementation of the exact solver are demonstrated, and some large instances with remarkable Pareto Front shapes are proposed, that will hopefully become standard benchmarks of the AI planning domain.
  • Upper and Lower Bounds on Unrestricted Black-Box Complexity of Jumpn,l
    • Maxim Buzdalov, Mikhail Kever, Benjamin Doerr We analyse the unrestricted black-box complexity of Jumpn,l functions. For upper bounds, we present three algorithms for small, medium and extreme values of l We present a matrix lower bound theorem which is capable of giving better lower bounds than a general information theory approach if one is able to assign different types to queries and define relationships between them. Using this theorem, we prove lower bounds for Jump separately for odd and even values of n. For several cases, notably for extreme Jump the first terms of lower and upper bounds coincide.
  • Using Local Search to Evaluate Dispatching Rules in Dynamic Job Shop Scheduling
    • Rachel Hunt, Mark Johnston, Mengjie Zhang
    Improving scheduling methods in manufacturing environments such as job shops offers the potential to increase throughput, decrease costs, and therefore increase profit. This makes scheduling an important aspect in the manufacturing industry. Job shop scheduling has been widely studied in the academic literature because of its real-world applicability and difficult nature. Dispatching rules are the most common means of scheduling in dynamic environments. We use genetic programming to search the space of potential dispatching rules. Dispatching rules are often short-sighted as they make one instantaneous decision at each decision point. We incorporate local search into the evaluation of dispatching rules to assess the quality of decisions made by dispatching rules and encourage the dispatching rules to make good local decisions for effective overall performance. Results show that the inclusion of local search in evaluation led to the evolution of DRs which make better decisions over the local time horizon, and attain lower TWT. The advantages of using local search as a tie-breaking mechanism are not so pronounced.

Best Paper Candidates

  • Hyper-heuristic Operator Selection and Acceptance Criteria
    • Richard Marshall, Mark Johnston, Mengjie Zhang
  • On the Complexity of Searching the Linear Ordering Problem Neighborhoods
    • Benjamin Correal, Philippe Galinier
  • Upper and Lower Bounds on Unrestricted Black-Box Complexity of Jumpn,l
    • Maxim Buzdalov, Mikhail Kever, Benjamin Doerr

Important dates:

Submission Deadline: 15 November 2014
Notification: 07 January 2015
Camera-ready: 21 January 2015
Early registration discount:01 March 2015
Registration deadline:31 March 2015
EvoStar dates: 8-10 April 2015

Twitter: