Wednesday 27 April, room 2: Aristotele, Scheduling
Chair: Peter Merz
11:30-13:00 A Hybrid Dual-Population Genetic Algorithm for the Single Machine Maximum Lateness Problem Veronique Sels, Mario Vanhoucke
We consider the problem of scheduling a number of jobs, each job having a release time, a processing time and a due date, on a single machine with the objective of minimizing the maximum lateness. We developed a dual-population genetic algorithm and compared its performance with alternative methods on a new diverse data set. Extensions from a single to a dual population by taking problem specific characteristics into account can be seen as a stimulator to add diversity in the search process, which has a positive influence on the important balance between intensification and diversification. Based on a comprehensive literature study on genetic algorithms in single machine scheduling, a fair comparison of genetic operators was made.
11:30-13:00 A Matheuristic Approach For The Total Completion Time Two-Machines Permutation Flow Shop Problem Federico Della Croce, Andrea Grosso, Fabio Salassa
This paper deals with the total completion time 2-machines flow shop problem. We present a so-called matheuristic post processing procedure that improves the objective function value with respect to the solutions provided by state of the art procedures. The proposed procedure is based on the positional completion times integer programming formulation of the problem with O(n2) variables and O(n) constraints.
11:30-13:00 NILS: a Neutrality-based Iterated Local Search and its application to Flowshop Scheduling Marie-Eleonore Marmion, Clarisse Dhaenens, Laetitia Jourdan, Arnaud Liefooghe, Sebastien Verel
This paper presents a new methodology that exploits specific characteristics given from the fitness landscape. In particular, we are interested in the property of neutrality that deals with the fact that the same fitness value is assigned to numerous solutions from the search space. Many combinatorial optimization problems share this property that is generally very inhibiting for local search algorithms. A neutrality-based iterated local search, that allows neutral walks to move on the plateaus, is proposed and experimented on a permutation flowshop scheduling problem with the aim of minimizing the makespan. Our experiments show that the proposed approach allows to find improving solutions compared with a classical iterated local search. Moreover, the tradeoff between the exploitation of neutrality and the exploration of new parts of the search space is deeply analyzed.
Wednesday 27 April, room 2: Aristotele, Multi-objective optimisation
Chair: Clarisse Dhaenens
14:30-16:00 A Guided Search Non-dominated Sorting Genetic Algorithm for the Multi-Objective University Course Timetabling Problem Sadaf Naseem Jat, hengxiang Yang
The university course timetabling problem is a typical combinatorial optimization problem. This paper tackles the multi-objective university course timetabling problem (MOUCTP) and proposes a guided search non-dominated sorting genetic algorithm to solve the MOUCTP. The proposed algorithm integrates a guided search technique, which uses a memory to store useful information extracted from previous good solutions to guide the generation of new solutions, and two local search schemes to enhance its performance for the MOUCTP. The experimental results based on a set of test problems show that the proposed algorithm is efficient for solving the MOUCTP.
14:30-16:00 Evolutionary Multiobjective Route Planning in Dynamic Multi-hop Ridesharing Wesam Herbawi, Michael Weber
Ridesharing is considered as one of the promising solutions for dropping the consumption of fuel and reducing the congestion in urban cities, hence reducing the environmental pollution. In this work, we present an evolutionary multiobjective route planning algorithm for solving the route planning problem in the dynamic multi-hop ridesharing. The experiments indicate that the evolutionary approach is able to provide a good quality set of route plans and outperforms the generalized label correcting algorithm in term of runtime.
14:30-16:00 GPU-based Approaches for Multiobjective Local Search Algorithms. A Case Study: the Flowshop Scheduling Problem Thé Van Luong, Nouredine Melab, El-Ghazali Talbi
GPU-based Approaches for Multiobjective Local Search Algorithms. A Case Study: the Flowshop Scheduling Problem. Multiobjective local search algorithms are efficient methods to solve complex problems in science and industry. Even if these heuristics allow to significantly reduce the computational time of the solution search space exploration, this latter cost remains exorbitant when very large problem instances are to be solved. As a result, the use of graphics processing units (GPU) has been recently revealed as an efficient way to accelerate the search process. This paper presents a new methodology to design and implement efficiently GPU-based multiobjective local search algorithms. The experimental results show that the approach is promising especially for large problem instances.
Wednesday 27 April, room 2: Aristotele, Tour Planning/Vehicle Routing
Chair: Frédéric Gardi
16:20-17:50 Multi-start heuristics for the Two-Echelon Vehicle Routing Problem Teodor Gabriel Crainic, Simona Mancini, Guido Perboli, Roberto Tadei
In this paper we address the Two-Echelon Vehicle Routing Problem, an extension of the classical Capacitated VRP, where the delivery from a single depot to the customers is managed by routing and consolidating the freight through intermediate depots called satellites. We present a family of Multi-Start heuristics based on separating the depot-to-satellite transfer and the satellite-to-customer delivery by iteratively solving the two resulting routing subproblems, while adjusting the satellite workloads that link them. The common scheme on which all the heuristics are based consists in, after having found an initial solution, applying a local search phase, followed by a diversification; if the new obtained solutions are feasible, then local search is applied again, otherwise a feasibility search procedure is applied, and if it successful, the local search is applied on the newfound solution. Different diversification strategies and feasibility search rules are proposed. We present computational results on a wide set of instances up to 50 customers and 5 satellites and compare them with results from the literature, showing how the new methods outperform previous existent methods, both in efficiency and accuracy.
16:20-17:50 Quick-ACO: Accelerating Ant Decisions and Pheromone Updates in ACO Wei Cheng, Bernd Scheuermann, Martin Middendorf
In Ant Colony Optimization (ACO) algorithms, solutions are constructed through a sequence of probabilistic decisions by artificial ants. These decisions are guided by information stored in a pheromone matrix which is repeatedly updated in two ways: Pheromone values in the matrix are increased by the ants to mark preferable decisions (probabilistic selection of items) whereas evaporation reduces each pheromone value by a certain percentage to weaken the relevance of former, potentially unfavorable, decisions. This paper introduces novel methods for expedited ant decisions and pheromone update for ACO. It is proposed to speedup decisions of ants by temporarily allowing them to select any item. If this item has already been chosen before (which would result in an inadmissible solution), the ant repeats its decision until an admissible item has been chosen. This method avoids to continuously determine the probability distributions over the yet admissible items which otherwise would require frequent expensive pre x sum calculations. The procedure of pheromone matrix updates is accelerated by entirely abandoning evaporation while re-scaling pheromone values and update increments. It should be emphasized that both new methods do not change the optimization behavior compared to standard ACO. In experimental evaluations with a range of benchmark instances of the Traveling Salesman Problem, the new methods were able to save up to 90% computation time compared to a ACO algorithm which uses standard procedures for pheromone update and decision making.
Thursday 28 April, room 2: Aristotele, Methods and measures
Chair: Anton Eremeev
9:30-11:00 A Kolmogorov-Type Stability Measure for Evolutionary Algorithms Matthew Craven, Henri Jimbo
In previous work, EAs were shown to efficiently solve certain equations over partially commutative groups. The EAs depend on the values of several control parameters for success. Generally these values must be tuned to the structure of the equation or problem to be solved. Supposing suitable values are found, a natural concern is stability of the EA under random perturbation of its parameters. This work considers such a model of EA stability by defining neighbourhoods over EA parameter space and examining their properties. We define stability based upon Kolmogorov distance and analyse that distance between repeated random perturbations of parameters, forming a statistical indication of EA stability under parameter perturbation. We then analyse the model for the wider class of general EAs, meaning our model may serve as a framework for parameter optimisation and stability analysis.
9:30-11:00 Fitness-Probability Cloud and a Measure of Problem Hardness for Evolutionary Algorithms Guanzhou Lu, Jinlong Li, Xin Yao
Evolvability is an important feature directly related to problem hardness for Evolutionary Algorithms (EAs). A general relationship holds for Evolvability and problem hardness is the higher the degree of evolvability, the easier the problem is for EAs. This paper presents, for the first time, the concept of Fitness-Probability Cloud (fpc) to characterise evolvability from the point of view of escape probability and fitness correlation. Furthermore, a numerical measure called Accumulated Escape Probability (aep) based on fpc is proposed to quantify this feature, and therefore problem difficulty. To illustrate the effectiveness of our approach, we apply it to four test problems: OneMax, Trap, OneMix and Subset Sum. We then contrast the predictions made by the aep to the actual performance measured using the number of fitness evaluations. The results suggest that the new measure can reliably indicate problem-hardness for EAs.
9:30-11:00 Geometric Generalisation of Surrogate Model Based Optimisation to Combinatorial Spaces Alberto Moraglio, Ahmed Kattan
In continuous optimisation, Surrogate Models (SMs) are often indispensable components of optimisation algorithms aimed at tackling real-world problems whose candidate solutions are very expensive to evaluate. Because of the inherent spatial intuition behind these models, they are naturally suited to continuous problems but they do not seem applicable to combinatorial problems except for the special case when solutions are naturally encoded as integer vectors. In this paper, we show that SMs can be naturally generalised to encompass combinatorial spaces based in principle on any arbitrarily complex underlying solution representation by generalising their geometric interpretation from continuous to general metric spaces. As an initial illustrative example, we show how Radial Basis Function Networks (RBFNs) can be used successfully as surrogate models to optimise combinatorial problems defined on the Hamming space associated with binary strings.
Thursday 28 April, room 2: Aristotele, Local search
Chair: Philippe Codognet
11:30-13:00 Effective Variable Fixing and Scoring Strategies for Binary Quadratic Programming Yang Wang, Zhipeng Lu, Fred Glover, Jin-Kao Hao
We investigate two variable fixing strategies and two variable scoring strategies within a tabu search algorithm, using the unconstrained binary quadratic programming (UBQP) problem as a case study. In particular, we provide insights as to why one particular variable fixing and scoring strategy leads to better computational results than another one. For this purpose, we perform two investigations, the first analyzing deviations from the best known solution and the second analyzing the correlations between the fitness distances of high-quality solutions. We find that one of our strategies obtains the best solutions in the literature for all of the test problems examined.
11:30-13:00 Experiments in Parallel Constraint-Based Local Search Yves Caniou, Philippe Codognet, Daniel Diaz, Salvador Abreu
We present a parallel implementation of a constraint-based local search algorithm and investigate its performance results on hardware with several hundreds of processors. We choose as basic constraint solving algorithm for these experiments the “adaptive search” method, an efficient sequential local search method for CSPs. The implemented algorithm is a parallel version of adaptive search in a multiple independent-walk manner, that is, each process is an independent search engine and there is no communication between the simultaneous computations. Preliminary performance evaluation on a variety of classical CSPs benchmarks shows that speedups are very good for a few tens of processors, and good up to a few hundreds of processors.
11:30-13:00 Local Search for Mixed-Integer Nonlinear Optimization: a Methodology and an Application Frédéric Gardi, Karim Nouioua
A methodology is presented for tackling mixed-integer nonlinear optimization problems by local search, in particular large-scale real-life problems. This methodology is illustrated through the local-search heuristic implemented for solving an energy management problem posed by the EDF company in the context of the ROADEF/EURO Challenge 2010, an international competition of applied optimization. Our local-search approach is pure and direct: the problem is tackled frontally, without decomposition nor hybridization. In this way, both combinatorial and continuous decisions can be modified by a move during the search. Then, our work focuses on the diversification by the moves and on the performance of the incremental evaluation machinery. Exploring millions of feasible solutions within one hour of running time, the resulting local search allows us to obtain among the best results of the competition, in which 44 teams from 25 countries were engaged.
Thursday 28 April, room 2: Aristotele, Cutting and packing
Chair: Elena Marchiori
14:30-16:00 Cutting Graphs Using Competing Ant Colonies and an Edge Clustering Heuristic Max Hinne, Elena Marchiori
We investigate the usage of Ant Colony Optimization to detect balanced graph cuts. In order to do so we develop an algorithm based on competing ant colonies. We use a heuristic from social network analysis called the edge clustering coefficient, which greatly helps our colonies in local search. The algorithm is able to detect cuts that correspond very well to known cuts on small real-world networks. Also, with the correct parameter balance, our algorithm often outperforms the traditional Kernighan-Lin algorithm for graph partitioning with equal running time complexity. On larger networks, our algorithm is able to obtain low cut sizes, but at the cost of a balanced partition.
14:30-16:00 Frequency Distribution based Hyper-Heuristic for the Bin-Packing Problem He Jiang, Shuyan Zhang, Jifeng Xuan, Youxi Wu
In the paper, we investigate the pair frequency of low-level heuristics for the bin packing problem and propose a Frequency Distribution based Hyper-Heuristic (FDHH). FDHH generates the heuristic sequences based on a pair of low-level heuristics rather than an individual low-level heuristic. An existing Simulated Annealing Hyper-Heuristic (SAHH) is employed to form the pair frequencies and is extended to guide the further selection of low-level heuristics. To represent the frequency distribution, a frequency matrix is built to collect the pair frequencies while a reverse-frequency matrix is generated to avoid getting trapped into the local optima. The experimental results on the bin-packing problems show that FDHH can obtain optimal solutions on more instances than the original hyper-heuristic.
14:30-16:00 Two Iterative Metaheuristic Approaches to Dynamic Memory Allocation for Embedded Systems Maria Soto, André Rossi, Marc Sevaux
Electronic embedded systems designers aim at finding a trade-off between cost and power consumption. As cache memory management has been shown to have a significant impact on power consumption, this paper addresses dynamic memory allocation for embedded systems with a special emphasis on time performance. In this work, time is split into time intervals, into which the application to be implemented by the embedded system requires accessing to data structures. The proposed iterative metaheuristics aim at determining which data structure should be stored in cache memory at each time interval in order to minimize reallocation and conflict costs. These approaches take advantage of metaheuristics previously designed for a static memory allocation problem version.
Thursday 28 April, room 2: Aristotele, Parameter tuning and dynamic adpatation
Chair: Gusz Eiben
16:20-17:50 From Adaptive to More Dynamic Control in Evolutionary Algorithms Giacomo Di Tollo, Frédéric Lardeux, Jorge Maturana, Frédéric Saubion
Adaptive evolutionary algorithms have been widely developed to improve the management of the balance between intensification and diversification during the search. Nevertheless, this balance may need to be dynamically adjust over time. Based on previous works on adaptive operator selection, we investigate in this paper how an adaptive controller can be used to achieve more dynamic search scenarios and what is the real impact of possible combinations of control components. This study may thus be helpful for the development of more autonomous and efficient evolutionary algorithms.
16:20-17:50 Off-line and On-line Tuning: A Study on Operator Selection for a Memetic Algorithm Applied to the QAP Gianpiero Francesca, Paola Pellegrini, Thomas Stützle, Mauro Birattari
Tuning methods for selecting appropriate parameter configurations of optimization algorithms have been the object of several recent studies. The selection of the appropriate configuration may strongly impact on the performance of evolutionary algorithms. In this paper, we study the performance of three memetic algorithms for the quadratic assignment problem when their parameters are tuned either off-line or on-line. Off-line tuning selects a priori one configuration to be used throughout the whole run for all the instances to be tackled. On-line tuning selects the configuration during the solution process, adapting parameter settings on an instance-per-instance basis, and possibly to each phase of the search. The results suggest that off-line tuning achieves a better performance than on-line tuning.
Friday 29 April, room 2: Aristotele, Best paper nominations
Peter Merz
9:30-11:00 On Complexity of Optimal Recombination for the Travelling Salesman Problem (Best Paper Nomination) Anton Eremeev
The computational complexity of the optimal recombination for the Travelling Salesman Problem is considered both in the symmetric and in the general cases. Strong NP-hardness of these optimal recombination problems is proven and solving approaches are considered.
9:30-11:00 Connectedness and Local Search for Bicriteria Knapsack Problems (Best Paper Nomination) Arnaud Liefooghe, Luís Paquete, Marco Simões, José R. Figueira
This article reports an experimental study on a given structural property of connectedness of optimal solutions for two variants of the bicriteria knapsack problem. A local search algorithm that explores this property is then proposed and its performance is compared against exact algorithms in terms of running time and number of optimal solutions found. The experimental results indicate that this simple local search algorithm is able to find a representative set of optimal solutions in most of the cases, and in much less time than exact approaches.
9:30-11:00 Pareto Local Optima of Multiobjective NK-Landscapes with Correlated Objectives (Best Paper Nomination) Sebastien Verel, Arnaud Liefooghe, Laetitia Jourdan, Clarisse Dhaenens
In this paper, we conduct a fitness landscape analysis for multiobjective combinatorial optimization based on the local optima of multiobjective NK-landscapes with objective correlation. In single-objective optimization, it has become clear that the local optima have a strong impact on the performance of metaheuristics. Here, we propose an extension to the multiobjective case, based on Pareto-dominance. We study the co-influence of the problem dimension, the degree of non-linearity, the number of objectives and the correlation degree between objective functions on the number of Pareto local optima.
Talks
Wednesday 27 April, room 2: Aristotele, Scheduling
Chair: Peter Merz
11:30-13:00 A Hybrid Dual-Population Genetic Algorithm for the Single Machine Maximum Lateness Problem
Veronique Sels, Mario Vanhoucke
We consider the problem of scheduling a number of jobs, each job having a release time, a processing time and a due date, on a single machine with the objective of minimizing the maximum lateness. We developed a dual-population genetic algorithm and compared its performance with alternative methods on a new diverse data set. Extensions from a single to a dual population by taking problem specific characteristics into account can be seen as a stimulator to add diversity in the search process, which has a positive influence on the important balance between intensification and diversification. Based on a comprehensive literature study on genetic algorithms in single machine scheduling, a fair comparison of genetic operators was made.
11:30-13:00 A Matheuristic Approach For The Total Completion Time Two-Machines Permutation Flow Shop Problem
Federico Della Croce, Andrea Grosso, Fabio Salassa
This paper deals with the total completion time 2-machines flow shop problem. We present a so-called matheuristic post processing procedure that improves the objective function value with respect to the solutions provided by state of the art procedures. The proposed procedure is based on the positional completion times integer programming formulation of the problem with O(n2) variables and O(n) constraints.
11:30-13:00 NILS: a Neutrality-based Iterated Local Search and its application to Flowshop Scheduling
Marie-Eleonore Marmion, Clarisse Dhaenens, Laetitia Jourdan, Arnaud Liefooghe, Sebastien Verel
This paper presents a new methodology that exploits specific characteristics given from the fitness landscape. In particular, we are interested in the property of neutrality that deals with the fact that the same fitness value is assigned to numerous solutions from the search space. Many combinatorial optimization problems share this property that is generally very inhibiting for local search algorithms. A neutrality-based iterated local search, that allows neutral walks to move on the plateaus, is proposed and experimented on a permutation flowshop scheduling problem with the aim of minimizing the makespan. Our experiments show that the proposed approach allows to find improving solutions compared with a classical iterated local search. Moreover, the tradeoff between the exploitation of neutrality and the exploration of new parts of the search space is deeply analyzed.
Wednesday 27 April, room 2: Aristotele, Multi-objective optimisation
Chair: Clarisse Dhaenens
14:30-16:00 A Guided Search Non-dominated Sorting Genetic Algorithm for the Multi-Objective University Course Timetabling Problem
Sadaf Naseem Jat, hengxiang Yang
The university course timetabling problem is a typical combinatorial optimization problem. This paper tackles the multi-objective university course timetabling problem (MOUCTP) and proposes a guided search non-dominated sorting genetic algorithm to solve the MOUCTP. The proposed algorithm integrates a guided search technique, which uses a memory to store useful information extracted from previous good solutions to guide the generation of new solutions, and two local search schemes to enhance its performance for the MOUCTP. The experimental results based on a set of test problems show that the proposed algorithm is efficient for solving the MOUCTP.
14:30-16:00 Evolutionary Multiobjective Route Planning in Dynamic Multi-hop Ridesharing
Wesam Herbawi, Michael Weber
Ridesharing is considered as one of the promising solutions for dropping the consumption of fuel and reducing the congestion in urban cities, hence reducing the environmental pollution. In this work, we present an evolutionary multiobjective route planning algorithm for solving the route planning problem in the dynamic multi-hop ridesharing. The experiments indicate that the evolutionary approach is able to provide a good quality set of route plans and outperforms the generalized label correcting algorithm in term of runtime.
14:30-16:00 GPU-based Approaches for Multiobjective Local Search Algorithms. A Case Study: the Flowshop Scheduling Problem
Thé Van Luong, Nouredine Melab, El-Ghazali Talbi
GPU-based Approaches for Multiobjective Local Search Algorithms. A Case Study: the Flowshop Scheduling Problem. Multiobjective local search algorithms are efficient methods to solve complex problems in science and industry. Even if these heuristics allow to significantly reduce the computational time of the solution search space exploration, this latter cost remains exorbitant when very large problem instances are to be solved. As a result, the use of graphics processing units (GPU) has been recently revealed as an efficient way to accelerate the search process. This paper presents a new methodology to design and implement efficiently GPU-based multiobjective local search algorithms. The experimental results show that the approach is promising especially for large problem instances.
Wednesday 27 April, room 2: Aristotele, Tour Planning/Vehicle Routing
Chair: Frédéric Gardi
16:20-17:50 Multi-start heuristics for the Two-Echelon Vehicle Routing Problem
Teodor Gabriel Crainic, Simona Mancini, Guido Perboli, Roberto Tadei
In this paper we address the Two-Echelon Vehicle Routing Problem, an extension of the classical Capacitated VRP, where the delivery from a single depot to the customers is managed by routing and consolidating the freight through intermediate depots called satellites. We present a family of Multi-Start heuristics based on separating the depot-to-satellite transfer and the satellite-to-customer delivery by iteratively solving the two resulting routing subproblems, while adjusting the satellite workloads that link them. The common scheme on which all the heuristics are based consists in, after having found an initial solution, applying a local search phase, followed by a diversification; if the new obtained solutions are feasible, then local search is applied again, otherwise a feasibility search procedure is applied, and if it successful, the local search is applied on the newfound solution. Different diversification strategies and feasibility search rules are proposed. We present computational results on a wide set of instances up to 50 customers and 5 satellites and compare them with results from the literature, showing how the new methods outperform previous existent methods, both in efficiency and accuracy.
16:20-17:50 Quick-ACO: Accelerating Ant Decisions and Pheromone Updates in ACO
Wei Cheng, Bernd Scheuermann, Martin Middendorf
In Ant Colony Optimization (ACO) algorithms, solutions are constructed through a sequence of probabilistic decisions by artificial ants. These decisions are guided by information stored in a pheromone matrix which is repeatedly updated in two ways: Pheromone values in the matrix are increased by the ants to mark preferable decisions (probabilistic selection of items) whereas evaporation reduces each pheromone value by a certain percentage to weaken the relevance of former, potentially unfavorable, decisions. This paper introduces novel methods for expedited ant decisions and pheromone update for ACO. It is proposed to speedup decisions of ants by temporarily allowing them to select any item. If this item has already been chosen before (which would result in an inadmissible solution), the ant repeats its decision until an admissible item has been chosen. This method avoids to continuously determine the probability distributions over the yet admissible items which otherwise would require frequent expensive pre x sum calculations. The procedure of pheromone matrix updates is accelerated by entirely abandoning evaporation while re-scaling pheromone values and update increments. It should be emphasized that both new methods do not change the optimization behavior compared to standard ACO. In experimental evaluations with a range of benchmark instances of the Traveling Salesman Problem, the new methods were able to save up to 90% computation time compared to a ACO algorithm which uses standard procedures for pheromone update and decision making.
Thursday 28 April, room 2: Aristotele, Methods and measures
Chair: Anton Eremeev
9:30-11:00 A Kolmogorov-Type Stability Measure for Evolutionary Algorithms
Matthew Craven, Henri Jimbo
In previous work, EAs were shown to efficiently solve certain equations over partially commutative groups. The EAs depend on the values of several control parameters for success. Generally these values must be tuned to the structure of the equation or problem to be solved. Supposing suitable values are found, a natural concern is stability of the EA under random perturbation of its parameters. This work considers such a model of EA stability by defining neighbourhoods over EA parameter space and examining their properties. We define stability based upon Kolmogorov distance and analyse that distance between repeated random perturbations of parameters, forming a statistical indication of EA stability under parameter perturbation. We then analyse the model for the wider class of general EAs, meaning our model may serve as a framework for parameter optimisation and stability analysis.
9:30-11:00 Fitness-Probability Cloud and a Measure of Problem Hardness for Evolutionary Algorithms
Guanzhou Lu, Jinlong Li, Xin Yao
Evolvability is an important feature directly related to problem hardness for Evolutionary Algorithms (EAs). A general relationship holds for Evolvability and problem hardness is the higher the degree of evolvability, the easier the problem is for EAs. This paper presents, for the first time, the concept of Fitness-Probability Cloud (fpc) to characterise evolvability from the point of view of escape probability and fitness correlation. Furthermore, a numerical measure called Accumulated Escape Probability (aep) based on fpc is proposed to quantify this feature, and therefore problem difficulty. To illustrate the effectiveness of our approach, we apply it to four test problems: OneMax, Trap, OneMix and Subset Sum. We then contrast the predictions made by the aep to the actual performance measured using the number of fitness evaluations. The results suggest that the new measure can reliably indicate problem-hardness for EAs.
9:30-11:00 Geometric Generalisation of Surrogate Model Based Optimisation to Combinatorial Spaces
Alberto Moraglio, Ahmed Kattan
In continuous optimisation, Surrogate Models (SMs) are often indispensable components of optimisation algorithms aimed at tackling real-world problems whose candidate solutions are very expensive to evaluate. Because of the inherent spatial intuition behind these models, they are naturally suited to continuous problems but they do not seem applicable to combinatorial problems except for the special case when solutions are naturally encoded as integer vectors. In this paper, we show that SMs can be naturally generalised to encompass combinatorial spaces based in principle on any arbitrarily complex underlying solution representation by generalising their geometric interpretation from continuous to general metric spaces. As an initial illustrative example, we show how Radial Basis Function Networks (RBFNs) can be used successfully as surrogate models to optimise combinatorial problems defined on the Hamming space associated with binary strings.
Thursday 28 April, room 2: Aristotele, Local search
Chair: Philippe Codognet
11:30-13:00 Effective Variable Fixing and Scoring Strategies for Binary Quadratic Programming
Yang Wang, Zhipeng Lu, Fred Glover, Jin-Kao Hao
We investigate two variable fixing strategies and two variable scoring strategies within a tabu search algorithm, using the unconstrained binary quadratic programming (UBQP) problem as a case study. In particular, we provide insights as to why one particular variable fixing and scoring strategy leads to better computational results than another one. For this purpose, we perform two investigations, the first analyzing deviations from the best known solution and the second analyzing the correlations between the fitness distances of high-quality solutions. We find that one of our strategies obtains the best solutions in the literature for all of the test problems examined.
11:30-13:00 Experiments in Parallel Constraint-Based Local Search
Yves Caniou, Philippe Codognet, Daniel Diaz, Salvador Abreu
We present a parallel implementation of a constraint-based local search algorithm and investigate its performance results on hardware with several hundreds of processors. We choose as basic constraint solving algorithm for these experiments the “adaptive search” method, an efficient sequential local search method for CSPs. The implemented algorithm is a parallel version of adaptive search in a multiple independent-walk manner, that is, each process is an independent search engine and there is no communication between the simultaneous computations. Preliminary performance evaluation on a variety of classical CSPs benchmarks shows that speedups are very good for a few tens of processors, and good up to a few hundreds of processors.
11:30-13:00 Local Search for Mixed-Integer Nonlinear Optimization: a Methodology and an Application
Frédéric Gardi, Karim Nouioua
A methodology is presented for tackling mixed-integer nonlinear optimization problems by local search, in particular large-scale real-life problems. This methodology is illustrated through the local-search heuristic implemented for solving an energy management problem posed by the EDF company in the context of the ROADEF/EURO Challenge 2010, an international competition of applied optimization. Our local-search approach is pure and direct: the problem is tackled frontally, without decomposition nor hybridization. In this way, both combinatorial and continuous decisions can be modified by a move during the search. Then, our work focuses on the diversification by the moves and on the performance of the incremental evaluation machinery. Exploring millions of feasible solutions within one hour of running time, the resulting local search allows us to obtain among the best results of the competition, in which 44 teams from 25 countries were engaged.
Thursday 28 April, room 2: Aristotele, Cutting and packing
Chair: Elena Marchiori
14:30-16:00 Cutting Graphs Using Competing Ant Colonies and an Edge Clustering Heuristic
Max Hinne, Elena Marchiori
We investigate the usage of Ant Colony Optimization to detect balanced graph cuts. In order to do so we develop an algorithm based on competing ant colonies. We use a heuristic from social network analysis called the edge clustering coefficient, which greatly helps our colonies in local search. The algorithm is able to detect cuts that correspond very well to known cuts on small real-world networks. Also, with the correct parameter balance, our algorithm often outperforms the traditional Kernighan-Lin algorithm for graph partitioning with equal running time complexity. On larger networks, our algorithm is able to obtain low cut sizes, but at the cost of a balanced partition.
14:30-16:00 Frequency Distribution based Hyper-Heuristic for the Bin-Packing Problem
He Jiang, Shuyan Zhang, Jifeng Xuan, Youxi Wu
In the paper, we investigate the pair frequency of low-level heuristics for the bin packing problem and propose a Frequency Distribution based Hyper-Heuristic (FDHH). FDHH generates the heuristic sequences based on a pair of low-level heuristics rather than an individual low-level heuristic. An existing Simulated Annealing Hyper-Heuristic (SAHH) is employed to form the pair frequencies and is extended to guide the further selection of low-level heuristics. To represent the frequency distribution, a frequency matrix is built to collect the pair frequencies while a reverse-frequency matrix is generated to avoid getting trapped into the local optima. The experimental results on the bin-packing problems show that FDHH can obtain optimal solutions on more instances than the original hyper-heuristic.
14:30-16:00 Two Iterative Metaheuristic Approaches to Dynamic Memory Allocation for Embedded Systems
Maria Soto, André Rossi, Marc Sevaux
Electronic embedded systems designers aim at finding a trade-off between cost and power consumption. As cache memory management has been shown to have a significant impact on power consumption, this paper addresses dynamic memory allocation for embedded systems with a special emphasis on time performance. In this work, time is split into time intervals, into which the application to be implemented by the embedded system requires accessing to data structures. The proposed iterative metaheuristics aim at determining which data structure should be stored in cache memory at each time interval in order to minimize reallocation and conflict costs. These approaches take advantage of metaheuristics previously designed for a static memory allocation problem version.
Thursday 28 April, room 2: Aristotele, Parameter tuning and dynamic adpatation
Chair: Gusz Eiben
16:20-17:50 From Adaptive to More Dynamic Control in Evolutionary Algorithms
Giacomo Di Tollo, Frédéric Lardeux, Jorge Maturana, Frédéric Saubion
Adaptive evolutionary algorithms have been widely developed to improve the management of the balance between intensification and diversification during the search. Nevertheless, this balance may need to be dynamically adjust over time. Based on previous works on adaptive operator selection, we investigate in this paper how an adaptive controller can be used to achieve more dynamic search scenarios and what is the real impact of possible combinations of control components. This study may thus be helpful for the development of more autonomous and efficient evolutionary algorithms.
16:20-17:50 Off-line and On-line Tuning: A Study on Operator Selection for a Memetic Algorithm Applied to the QAP
Gianpiero Francesca, Paola Pellegrini, Thomas Stützle, Mauro Birattari
Tuning methods for selecting appropriate parameter configurations of optimization algorithms have been the object of several recent studies. The selection of the appropriate configuration may strongly impact on the performance of evolutionary algorithms. In this paper, we study the performance of three memetic algorithms for the quadratic assignment problem when their parameters are tuned either off-line or on-line. Off-line tuning selects a priori one configuration to be used throughout the whole run for all the instances to be tackled. On-line tuning selects the configuration during the solution process, adapting parameter settings on an instance-per-instance basis, and possibly to each phase of the search. The results suggest that off-line tuning achieves a better performance than on-line tuning.
Friday 29 April, room 2: Aristotele, Best paper nominations
Peter Merz
9:30-11:00 On Complexity of Optimal Recombination for the Travelling Salesman Problem (Best Paper Nomination)
Anton Eremeev
The computational complexity of the optimal recombination for the Travelling Salesman Problem is considered both in the symmetric and in the general cases. Strong NP-hardness of these optimal recombination problems is proven and solving approaches are considered.
9:30-11:00 Connectedness and Local Search for Bicriteria Knapsack Problems (Best Paper Nomination)
Arnaud Liefooghe, Luís Paquete, Marco Simões, José R. Figueira
This article reports an experimental study on a given structural property of connectedness of optimal solutions for two variants of the bicriteria knapsack problem. A local search algorithm that explores this property is then proposed and its performance is compared against exact algorithms in terms of running time and number of optimal solutions found. The experimental results indicate that this simple local search algorithm is able to find a representative set of optimal solutions in most of the cases, and in much less time than exact approaches.
9:30-11:00 Pareto Local Optima of Multiobjective NK-Landscapes with Correlated Objectives (Best Paper Nomination)
Sebastien Verel, Arnaud Liefooghe, Laetitia Jourdan, Clarisse Dhaenens
In this paper, we conduct a fitness landscape analysis for multiobjective combinatorial optimization based on the local optima of multiobjective NK-landscapes with objective correlation. In single-objective optimization, it has become clear that the local optima have a strong impact on the performance of metaheuristics. Here, we propose an extension to the multiobjective case, based on Pareto-dominance. We study the co-influence of the problem dimension, the degree of non-linearity, the number of objectives and the correlation degree between objective functions on the number of Pareto local optima.