International Journal of Metaheuristics (5 papers in press)
Solution attractor of local search in traveling salesman problem (part 2): computational study
by Weiqi Li, Xue Li
Abstract: This paper is the second part of our study. In the first part, we introduce the concept of solution attractor of local search system for the Traveling Salesman Problem (TSP), describe a procedure for constructing the solution attractor, and present an attractor-based search system to solve the dynamic multi-objective TSP. In this paper, we report the results of our recent empirical study on some important properties of the solution attractor of local search system for the TSP. These properties include the nature of convergence of local search trajectories, the size of the constructed solution attractor, the relationship between the size of the problem and the size of the constructed solution attractor, the best tour in the solution attractor, and computational complexity in the attractor-based search system.
Keywords: traveling salesman problem; global optimization; analysis of heuristics; convergence of local search; solution attractor.
A Structural Taxonomy for Metaheuristic Optimization Search Methods
by Raymond R. Hill, Edward Pohl
Abstract: Metaheuristic search algorithms have become ubiquitous in the applied optimization world. Various works have appeared classifying and improving these algorithms and the particular processes embedded within the algorithms. Successful metaheuristic approaches have a common general structure to their search processes. To this end, we offer a structural taxonomy of metaheuristic search methods. This taxonomy serves as a framework for constructing and evaluating metaheuristic approaches from a general structural perspective as well as for conducting empirical research regarding the effectiveness of more detailed structural components. Implementation mechanisms of the detailed components within each structural component is left for future taxonomy research and development.
Keywords: heuristic optimization; taxonomy; metaheuristics; intensification; diversification; adaptive memory.
Solving the maximum clique problem with a hybrid algorithm
by Derek Smith, Stephanie Perkins, Roberto Montemanni
Abstract: A hybrid algorithm for the maximum clique problem is presented. A heuristic is used to generate cliques and these are improved by some simple optimizations and tabu search. All components of the algorithm make use of a pseudoexact algorithm, which is an exact algorithm with some specialized pruning. Preprocessing is useful for some instances. The algorithm is shown to be successful using standard and new benchmarks.
Keywords: combinatorial optimization; maximum clique; hybrid algorithm; tabu search; pseudoexact algorithm; preprocessing; benchmarks.
Bio-inspired Metaheuristics for the Generalized Discrete Cost Multicommodity Network Design Problem
by SONIA KHATROUCH, SAFA BHAR LAYEB, JOUHAINA CHAOUACHI SIALA
Abstract: We investigate a new variant of Network Design Problems (NDPs) called the Generalized Discrete Cost Multicommodity Network Design Problem (GDCMNDP) that arises in a wide variety of real-life situations such as transportation, telecommunication and logistics. The problem consists on identifying the optimal capacitated network by choosing the connections to be installed in order to satisfy partially or totally the multicommodity demands. The objective is to minimize the total system cost, computed as the sum of fixed network costs and penalty costs due to the unrouted demands while installing at most one facility/connection on each edge. For the GDCMNDP, we propose a compact mixed integer linear programming formulation that we solve exactly by a commercial MIP solver. Moreover, we develop three basic greedy heuristics and tow bio-inspired metaheuristics: a basic genetic algorithm, a hybrid genetic algorithm via a variable neighbourhood search procedure and a biogeography-based optimization heuristic. To assess the performance of the proposed approaches, computational results are reported using real-world and benchmark instances from the literature. Computational results show that our hybrid genetic algorithm performs well by obtaining very good final solutions in reasonable times.
Keywords: Network Design Problems; Metaheuristics; Hybrid Genetic Algorithm; Biogeography-Based Optimization.
Special Issue on: Randomised Heuristics for Communication Networks
A Tabu Search Approach for a Virtual Networks Splitting Strategy Across Multiple Cloud Providers
by Marieme Diallo, Alejandro Quintero, Samuel Pierre
Abstract: This paper addresses the problem of computational and networking resources embedding across multiple independent cloud providers (CPs). We focus on the splitting phase problem by proposing a virtual network requests (VNRs) splitting strategy, which aims at improving the performance and the quality of service (QoS) of resulting mapped VNR segments. We formalize our splitting strategy as a mathematical maximization problem with constraints by using an Integer Linear Program (ILP). Since the VNRs splitting process is classified as an NP-hard problem, we propose a metaheuristic approach based on the Tabu Search (TS), in order to find good feasible solutions in polynomial solving time. The simulations results obtained show the efficiency of the proposed algorithm, in comparison with the exact method and an other baseline approach. Solution costs are on average close to the upper bounds, with an average gap ranging from 0% to a maximum of 2.97%, performed in a highly reduced computing time.
Keywords: Cloud computing; virtualized network infrastructures; resource splitting; optimization; metaheuristics; Tabu Search.