Evolutionary Computation in Combinatorial Optimization

Frontmatter

A Hyper-heuristic with a Round Robin Neighbourhood Selection

Abstract

An iterative selection hyper-heuristic passes a solution through a heuristic selection process to decide on a heuristic to apply from a fixed set of low level heuristics and then a move acceptance process to accept or reject the newly created solution at each step. In this study, we introduce Robinhood hyper-heuristic whose heuristic selection component allocates equal share from the overall execution time for each low level heuristic, while the move acceptance component enables partial restarts when the search process stagnates. The proposed hyper-heuristic is implemented as an extension to a public software used for benchmarking of hyper-heuristics, namely HyFlex. The empirical results indicate that Robinhood hyper-heuristic is a simple, yet powerful and general multistage algorithm performing better than most of the previously proposed selection hyper-heuristics across six different Hyflex problem domains.

Ahmed Kheiri, Ender Özcan

A Multiobjective Approach Based on the Law of Gravity and Mass Interactions for Optimizing Networks

Abstract

In this work, we tackle a real-world telecommunication problem by using Evolutionary Computation and Multiobjective Optimization jointly. This problem is known in the literature as the Traffic Grooming problem and consists on multiplexing or grooming a set of low-speed traffic requests (Mbps) onto high-speed channels (Gbps) over an optical network with wavelength division multiplexing facility. We propose a multiobjective version of an algorithm based on the laws of motions and mass interactions (Gravitational Search Algorithm, GSA) for solving this NP-hard optimization problem. After carrying out several comparisons with other approaches published in the literature for this optical problem, we can conclude that the multiobjective GSA (MO-GSA) is able to obtain very promising results.

Álvaro Rubio-Largo, Miguel A. Vega-Rodríguez

A Multi-objective Feature Selection Approach Based on Binary PSO and Rough Set Theory

Abstract

Feature selection has two main objectives of maximising the classification performance and minimising the number of features. However, most existing feature selection algorithms are single objective wrapper approaches. In this work, we propose a multi-objective filter feature selection algorithm based on binary particle swarm optimisation (PSO) and probabilistic rough set theory. The proposed algorithm is compared with other five feature selection methods, including three PSO based single objective methods and two traditional methods. Three classification algorithms (naïve bayes, decision trees and k-nearest neighbours) are used to test the generality of the proposed filter algorithm. Experiments have been conducted on six datasets of varying difficulty. Experimental results show that the proposed algorithm can automatically evolve a set of non-dominated feature subsets. In almost all cases, the proposed algorithm outperforms the other five algorithms in terms of both the number of features and the classification performance (evaluated by all the three classification algorithms). This paper presents the first study on using PSO and rough set theory for multi-objective feature selection.

Liam Cervante, Bing Xue, Lin Shang, Mengjie Zhang

A New Crossover for Solving Constraint Satisfaction Problems

Abstract

In this paper we investigate the applicability of Genetic Algorithms (GAs) for solving Constraint Satisfaction Problems (CSPs). Despite some success of GAs when tackling CSPs, they generally suffer from poor crossover operators. In order to overcome this limitation in practice, we propose a novel crossover specifically designed for solving CSPs. Together with a variable ordering heuristic and an integration into a parallel architecture, this proposed crossover enables the solving of large and hard problem instances as demonstrated by the experimental tests conducted on randomly generated CSPs based on the model RB. We will indeed demonstrate, through these tests, that our proposed method is superior to the known GA based techniques for CSPs. In addition, we will show that we are able to compete with the efficient MAC-based Abscon 109 solver for random problem instances.

Reza Abbasian, Malek Mouhoub

A Population-Based Strategic Oscillation Algorithm for Linear Ordering Problem with Cumulative Costs

Abstract

This paper presents a Population-based Strategic Oscillation (denoted by PBSO) algorithm for solving the linear ordering problem with cumulative costs (denoted by LOPCC). The proposed algorithm integrates several distinguished features, such as an adaptive strategic oscillation local search procedure and an effective population updating strategy. The proposed PBSO algorithm is compared with several state-of-the-art algorithms on a set of public instances up to 100 vertices, showing its efficacy in terms of both solution quality and efficiency. Moreover, several important ingredients of the PBSO algorithm are analyzed.

Wei Xiao, Wenqing Chu, Zhipeng Lü, Tao Ye, Guang Liu, Shanshan Cui

A Study of Adaptive Perturbation Strategy for Iterated Local Search

Abstract

We investigate the contribution of a recently proposed adaptive diversification strategy (ADS) to the performance of an iterated local search (ILS) algorithm. ADS is used as a diversification mechanism by breakout local search (BLS), which is a new variant of the ILS metaheuristic. The proposed perturbation strategy adaptively selects between two types of perturbations (directed or random moves) of different intensities, depending on the current state of search. We experimentally evaluate the performance of ADS on the quadratic assignment problem (QAP) and the maximum clique problem (MAX-CLQ). Computational results accentuate the benefit of combining adaptively multiple perturbation types of different intensities. Moreover, we provide some guidance on when to introduce a weaker and when to introduce a stronger diversification into the search.

Una Benlic, Jin-Kao Hao

Adaptive MOEA/D for QoS-Based Web Service Composition

Abstract

QoS aware service composition is one of the main research problem related to Service Oriented Computing (SOC). A certain functionality may be offered by several services having different Quality of Service (QoS) attributes. Although the QoS optimization problem is multiobjective by its nature, most approaches are based on single-objective optimization. Compared to single-objective algorithms, multiobjective evolutionary algorithms have the main advantage that the user has the possibility to select a posteriori one of the Pareto optimal solutions. A major challenge that arises is the dynamic nature of the problem of composing web services. The algorithms performance is highly influenced by the parameter settings. Manual tuning of these parameters is not feasible. An evolutionary multiobjective algorithm based on decomposition for solving this problem is proposed. To address the dynamic nature of this problem we consider the hybridization between an adaptive heuristics and the multiobjective algorithm. The proposed approach outperforms state of the art algorithms.

Mihai Suciu, Denis Pallez, Marcel Cremene, Dumitru Dumitrescu

An Analysis of Local Search for the Bi-objective Bidimensional Knapsack Problem

Abstract

Local search techniques are increasingly often used in multi-objective combinatorial optimization due to their ability to improve the performance of metaheuristics. The efficiency of multi-objective local search techniques heavily depends on factors such as (i) neighborhood operators, (ii) pivoting rules and (iii) bias towards good regions of the objective space. In this work, we conduct an extensive experimental campaign to analyze such factors in a Pareto local search (PLS) algorithm for the bi-objective bidimensional knapsack problem (bBKP). In the first set of experiments, we investigate PLS as a stand-alone algorithm, starting from random and greedy solutions. In the second set, we analyze PLS as a post-optimization procedure.

Leonardo C. T. Bezerra, Manuel López-Ibáñez, Thomas Stützle

An Artificial Immune System Based Approach for Solving the Nurse Re-rostering Problem

Abstract

Personnel resources can introduce uncertainty in the operational processes. Constructed personnel rosters can be disrupted and render infeasible rosters. Feasibility has to be restored by adapting the original announced personnel rosters. In this paper, an Artificial Immune System for the nurse re-rostering problem is presented. The proposed algorithm uses problem-specific and even roster-specific mechanisms which are inspired on the vertebrate immune system. We observe the performance of the different algorithmic components and compare the proposed procedure with the existing literature.

Broos Maenhout, Mario Vanhoucke

Automatic Algorithm Selection for the Quadratic Assignment Problem Using Fitness Landscape Analysis

Abstract

In the last few years, fitness landscape analysis has seen an increase in interest due to the availability of large problem collections and research groups focusing on the development of a wide array of different optimization algorithms for diverse tasks. Instead of being able to rely on a single trusted method that is tuned and tweaked to the application more and more, new problems are investigated, where little or no experience has been collected. In an attempt to provide a more general criterion for algorithm and parameter selection other than “it works better than something else we tried”, sophisticated problem analysis and classification schemes are employed. In this work, we combine several of these analysis methods and evaluate the suitability of fitness landscape analysis for the task of algorithm selection.

Erik Pitzer, Andreas Beham, Michael Affenzeller

Balancing Bicycle Sharing Systems: A Variable Neighborhood Search Approach

Abstract

We consider the necessary redistribution of bicycles in public bicycle sharing systems in order to avoid rental stations to run empty or entirely full. For this purpose we propose a general Variable Neighborhood Search (VNS) with an embedded Variable Neighborhood Descent (VND) that exploits a series of neighborhood structures. While this metaheuristic generates candidate routes for vehicles to visit unbalanced rental stations, the numbers of bikes to be loaded or unloaded at each stop are efficiently derived by one of three alternative methods based on a greedy heuristic, a maximum flow calculation, and linear programming, respectively. Tests are performed on instances derived from real-world data and indicate that the VNS based on a greedy heuristic represents the best compromise for practice. In general the VNS yields good solutions and scales much better to larger instances than two mixed integer programming approaches.

Marian Rainer-Harbach, Petrina Papazek, Bin Hu, Günther R. Raidl

Combinatorial Neighborhood Topology Particle Swarm Optimization Algorithm for the Vehicle Routing Problem

Abstract

One of the main problems in the application of a Particle Swarm Optimization in combinatorial optimization problems, especially in routing type problems like the Traveling Salesman Problem, the Vehicle Routing Problem, etc., is the fact that the basic equation of the Particle Swarm Optimization algorithm is suitable for continuous optimization problems and the transformation of this equation in the discrete space may cause loose of information and may simultaneously need a large number of iterations and the addition of a powerful local search algorithm in order to find an optimum solution. In this paper, we propose a different way to calculate the position of each particle which will not lead to any loose of information and will speed up the whole procedure. This was achieved by replacing the equation of positions with a novel procedure that includes a Path Relinking Strategy and a different correspondence of the velocities with the path that will follow each particle. The algorithm is used for the solution of the Capacitated Vehicle Routing Problem and is tested in the two classic set of benchmark instances from the literature with very good results.

Yannis Marinakis, Magdalene Marinaki

Dynamic Evolutionary Membrane Algorithm in Dynamic Environments

Abstract

Several problems that we face in real word are dynamic in nature. For solving these problems, a novel dynamic evolutionary algorithm based on membrane computing is proposed. In this paper, the partitioning strategy is employed to divide the search space to improve the search efficiency of the algorithm. Furthermore, the four kinds of evolutionary rules are introduced to maintain the diversity of solutions found by the proposed algorithm. The performance of the proposed algorithm has been evaluated over the standard moving peaks benchmark. The simulation results indicate that the proposed algorithm is feasible and effective for solving dynamic optimization problems.

Chuang Liu, Min Han

From Sequential to Parallel Local Search for SAT

Abstract

In the domain of propositional Satisfiability Problem (SAT), parallel portfolio-based algorithms have become a standard methodology for both complete and incomplete solvers. In this methodology several algorithms explore the search space in parallel, either independently or cooperatively with some communication between the solvers. We conducted a study of the scalability of several SAT solvers in different application domains (crafted, verification, quasigroups and random instances) when drastically increasing the number of cores in the portfolio, up to 512 cores. Our experiments show that on different problem families the behaviors of different solvers vary greatly. We present an empirical study that suggests that the best sequential solver is not necessary the one with the overall best parallel speedup.

Alejandro Arbelaez, Philippe Codognet

Generalizing Hyper-heuristics via Apprenticeship Learning

Abstract

An apprenticeship-learning-based technique is used as a hyper-heuristic to generate heuristics for an online combinatorial problem. It observes and learns from the actions of a known-expert heuristic on small instances, but has the advantage of producing a general heuristic that works well on other larger instances. Specifically, we generate heuristic policies for online bin packing problem by using expert near-optimal policies produced by a hyper-heuristic on small instances, where learning is fast. The ”expert” is a policy matrix that defines an index policy, and the apprenticeship learning is based on observation of the action of the expert policy together with a range of features of the bin being considered, and then applying a k-means classification. We show that the generated policy often performs better than the standard best-fit heuristic even when applied to instances much larger than the training set.

Shahriar Asta, Ender Özcan, Andrew J. Parkes, A. Şima Etaner-Uyar

High-Order Sequence Entropies for Measuring Population Diversity in the Traveling Salesman Problem

Abstract

We propose two entropy-based diversity measures for evaluating population diversity in a genetic algorithm (GA) applied to the traveling salesman problem (TSP). In contrast to a commonly used entropy-based diversity measure, the proposed ones take into account high-order dependencies between the elements of individuals in the population. More precisely, the proposed ones capture dependencies in the sequences of up to m + 1 vertices included in the population (tours), whereas the commonly used one is the special case of the proposed ones with m = 1. We demonstrate that the proposed entropy-based diversity measures with appropriate values of m evaluate population diversity more appropriately than does the commonly used one.

Yuichi Nagata, Isao Ono

Investigating Monte-Carlo Methods on the Weak Schur Problem

Abstract

Nested Monte-Carlo Search (NMC) and Nested Rollout Policy Adaptation (NRPA) are Monte-Carlo tree search algorithms that have proved their efficiency at solving one-player game problems, such as morpion solitaire or sudoku 16x16, showing that these heuristics could potentially be applied to constraint problems. In the field of Ramsey theory, the weak Schur number WS(k) is the largest integer n for which their exists a partition into k subsets of the integers [1,n] such that there is no x < y < z all in the same subset with x + y = z. Several studies have tackled the search for better lower bounds for the Weak Schur numbers WS(k), k ≥ 4. In this paper we investigate this problem using NMC and NRPA, and obtain a new lower bound for WS(6), namely WS(6) ≥ 582.

Shalom Eliahou, Cyril Fonlupt, Jean Fromentin, Virginie Marion-Poty, Denis Robilliard, Fabien Teytaud

Multi-objective AI Planning: Comparing Aggregation and Pareto Approaches

Abstract

Most real-world Planning problems are multi-objective, trying to minimize both the makespan of the solution plan, and some cost of the actions involved in the plan. But most, if not all existing approaches are based on single-objective planners, and use an aggregation of the objectives to remain in the single-objective context. Divide-and-Evolve is an evolutionary planner that won the temporal deterministic satisficing track at the last International Planning Competitions (IPC). Like all Evolutionary Algorithms (EA), it can easily be turned into a Pareto-based Multi-Objective EA. It is however important to validate the resulting algorithm by comparing it with the aggregation approach: this is the goal of this paper. The comparative experiments on a recently proposed benchmark set that are reported here demonstrate the usefulness of going Pareto-based in AI Planning.

Mostepha R. Khouadjia, Marc Schoenauer, Vincent Vidal, Johann Dréo, Pierre Savéant

Predicting Genetic Algorithm Performance on the Vehicle Routing Problem Using Information Theoretic Landscape Measures

Abstract

In this paper we examine the predictability of genetic algorithm (GA) performance using information-theoretic fitness landscape measures. The outcome of a GA is largely based on the choice of search operator, problem representation and tunable parameters (crossover and mutation rates, etc). In particular, given a problem representation the choice of search operator will determine, along with the fitness function, the structure of the landscape that the GA will search upon. Statistical and information theoretic measures have been proposed that aim to quantify properties (ruggedness, smoothness, etc) of this landscape. In this paper we concentrate on the utility of information theoretic measures to predict algorithm output for various instances of the capacitated and time-windowed vehicle routing problem. Using a clustering-based approach we identify similar landscape structures within these problems and propose to compare GA results to these clusters using performance profiles. These results highlight the potential for predicting GA performance, and providing insight self-configurable search operator design.

Mario Ventresca, Beatrice Ombuki-Berman, Andrew Runka

Single Line Train Scheduling with ACO

Abstract

In this paper we study a train scheduling problem on a single line that may be traversed in both directions by trains with different priorities travelling with different speeds. We propose an ACO approach to provide decision support for tackling this problem. Our results show the strong performance of ACO when compared to optimal solutions provided by CPLEX for small instances as well as to other heuristics on larger instances.

Marc Reimann, Jose Eugenio Leal

Solving Clique Covering in Very Large Sparse Random Graphs by a Technique Based on k-Fixed Coloring Tabu Search

Abstract

We propose a technique for solving the k-fixed variant of the clique covering problem (k-CCP), where the aim is to determine, whether a graph can be divided into at most k non-overlapping cliques. The approach is based on labeling of the vertices with k available labels and minimizing the number of non-adjacent pairs of vertices with the same label. This is an inverse strategy to k-fixed graph coloring, similar to a tabu search algorithm TabuCol. Thus, we call our method TabuCol-CCP. The technique allowed us to improve the best known results of specialized heuristics for CCP on very large sparse random graphs. Experiments also show a promise in scalability, since a large dense graph does not have to be stored. In addition, we show that Γ function, which is used to evaluate a solution from the neighborhood in graph coloring in \(\mathcal{O}(1)\) time, can be used without modification to do the same in k-CCP. For sparse graphs, direct use of Γ allows a significant decrease in space complexity of TabuCol-CCP to \(\mathcal{O}(|E|)\), with recalculation of fitness possible with small overhead in \(\mathcal{O}(\log \deg(v))\) time, where deg(v) is the degree of the vertex, which is relabeled.

David Chalupa

Solving the Virtual Network Mapping Problem with Construction Heuristics, Local Search and Variable Neighborhood Descent

Abstract

The Virtual Network Mapping Problem arises in the context of Future Internet research. Multiple virtual networks with different characteristics are defined to suit specific applications. These virtual networks, with all of the resources they require, need to be realized in one physical network in a most cost effective way. Two properties make this problem challenging: Already finding any valid mapping of all virtual networks into the physical network without exceeding the resource capacities is NP-hard, and the problem consists of two strongly dependent stages as the implementation of a virtual network’s connections can only be decided once the locations of the virtual nodes in the physical network are fixed. In this work we introduce various construction heuristics, Local Search and Variable Neighborhood Descent approaches and perform an extensive computational study to evaluate the strengths and weaknesses of each proposed solution method.

Johannes Inführ, Günther R. Raidl

The Generate-and-Solve Framework Revisited: Generating by Simulated Annealing

Abstract

The Generate-and-Solve is a hybrid framework to cope with hard combinatorial optimization problems by artificially reducing the search space of solutions. In this framework, a metaheuristic engine works as a generator of reduced instances of the problem. These instances, in turn, can be more easily handled by an exact solver to provide a feasible (optimal) solution to the original problem. This approach has commonly employed genetic algorithms and it has been particularly effective in dealing with cutting and packing problems. In this paper, we present an instantiation of the framework for tackling the constrained two-dimensional non-guillotine cutting problem and the container loading problem using a simulated annealing generator. We conducted computational experiments on a set of difficult benchmark instances. Results show that the simulated annealing implementation overachieves previous versions of the Generate-and-Solve framework. In addition, the framework is shown to be competitive with current state-of-the-art approaches to solve the problems studied here.

Rommel D. Saraiva, Napoleão V. Nepomuceno, Plácido R. Pinheiro

Backmatter