nach oben

2005 | Buch

Kapitel lesen Erstes Kapitel lesen

Hybrid Metaheuristics

Second International Workshop, HM 2005, Barcelona, Spain, August 29-30, 2005. Proceedings

herausgegeben von: María J. Blesa, Christian Blum, Andrea Roli, Michael Sampels

Verlag: Springer Berlin Heidelberg

Buchreihe : Lecture Notes in Computer Science

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten

Inhaltsverzeichnis

Frontmatter

Comparing Parallelization of an ACO: Message Passing vs. Shared Memory

Abstract

We present a shared memory approach to the parallelization of the Ant Colony Optimization (ACO) metaheuristic and a performance comparison with an existing message passing implementation. Our aim is to show that the shared memory approach is a competitive strategy for the parallelization of ACO algorithms. The sequential ACO algorithm on which are based both parallelization schemes is first described, followed by the parallelization strategies themselves. Through experiments, we compare speedup and efficiency measures on four TSP problems varying from 318 to 657 cities. We then discuss factors that explain the difference in performance of the two approaches. Further experiments are presented to show the performance of the shared memory implementation when varying numbers of ants are distributed among the available processors. In this last set of experiments, the solution quality obtained is taken into account when analyzing speedup and efficiency measures.

Pierre Delisle, Marc Gravel, Michaël Krajecki, Caroline Gagné, Wilson L. Price

An LP-Based Hybrid Heuristic Procedure for the Generalized Assignment Problem with Special Ordered Sets

Abstract

The generalized assignment problem with special ordered sets (GAPS2), is the problem of allocating n tasks to m time-periods, where each task must be assigned to a time-period, or shared between two consecutive time-periods. For large values of m and n the NP-hard combinatorial problem GAPS2 becomes intractable for standard mathematical programming software such as CPLEX or XPRESS^MP and it is unlikely that a proven optimal solution can be obtained. There is thus a need for heuristic algorithms to solve such problems. It will be shown how a combination of linear programming techniques and two heuristics forming a hybrid can be used to solve GAPS2. Good results, in terms of speed and accuracy, on large problem instances have been obtained. In particular when compared to an existing heuristic for GAPS2, the results look particularly promising.

Alan P. French, John M. Wilson

Parametrized Greedy Heuristics in Theory and Practice

Abstract

A parametrized greedy heuristic (pgreedy) is a hybridization of a classical greedy construction heuristic with a parametrized scoring function and improving hit-and-run, a concept from the field of Global Optimization for automated parameter selection. In this article we introduce this new metaheuristic concept and apply it to a real-world planning problem: the integrated coordination of school starting times and public transport in rural areas.

Armin Fügenschuh

A Taxonomy of Cooperative Search Algorithms

Abstract

A lot of heuristic approaches have been explored in the last two decades in order to tackle large size optimization problems. These areas include parallel meta-heuristics, hybrid meta-heuristic, and cooperative search algorithms. Different taxonomies have been proposed in the literature for parallel and hybrid meta-heuristics. In these taxonomies, one can realize that cooperative search algorithms lie somewhere in between. This paper looks at cooperative search algorithms as a stand alone area. Two different taxonomies of cooperative search algorithm are proposed based on two different criteria. Different implementations in this area are reported and classified using these taxonomies.

Mohammed El-Abd, Mohamed Kamel

A Hybrid Genetic and Variable Neighborhood Descent for Probabilistic SAT Problem

Abstract

In this paper we develop a satisfiability checker for probabilistic logic. Our approach is based on a hybrid algorithm which combines genetic algorithm approach with variable neighborhood descent. Our hybrid compares favorable with previous pure genetic algorithm. Computational experiences show that problems with 200 propositional letters can be solved. They are, to the best of our knowledge, the largest PSAT-problems reported in the literature.

Zoran Ognjanović, Uroš Midić, Nenad Mladenović

A Hybrid Meta-heuristic Approach for Natural Gas Pipeline Network Optimization

Abstract

In this paper we propose a hybrid heuristic solution procedure for fuel cost minimization on gas transmission systems with a cyclic network topology, that is, networks with at least one cycle containing two or more compressor station arcs. Our heuristic solution methodology is based on a two-stage iterative procedure. In a particular iteration, at a first stage, gas flow variables are fixed in each network arc and optimal pressure variables in each network node are found via non-sequential dynamic programming. At a second stage, pressure variables are fixed and a short-term memory Tabu Search procedure is used for guiding the search in the flow variable space. Empirical evidence supports the effectiviness of the proposed procedure outperforming the best existing approach to the best of our knowledge.

Conrado Borraz-Sánchez, Roger Z. Ríos-Mercado

Hybrid Tabu Search for Lot Sizing Problems

Abstract

This paper presents a hybrid tabu search strategy for lot sizing problems. This strategy allows the exploitation of the quality of the well-known relax-and-fix heuristic, inside a tabu search framework which enforces diversity.

The computational results show an advantage of this strategy when compared to a version of the relax-and-fix heuristic and to time constrained branch-and-bound.

João Pedro Pedroso, Mikio Kubo

Fast Ejection Chain Algorithms for Vehicle Routing with Time Windows

Abstract

This paper introduces a new algorithm, based on the concept of ejection chains, to effectively target vehicle routing problems with time window constraints (VRPTW). Ejection chains create powerful compound moves within Local Search algorithms. Their potential to yield state of the art algorithms has been validated for the traveling salesman problem (TSP), for example. We show how ejection chains can be used to tackle the more general VRPTW as well. The yardstick behind ejection chain procedures is the underlying reference structure; it is used to coordinate the moves that are available for the Local Search algorithm via a given set of transition rules. Our main contribution is the introduction of a new reference structure, generalizing reference structures previously suggested for the TSP. The new reference structure, together with a set of simple transition rules, is tailored to handle the asymmetric aspects in a VRPTW. We use Tabu Search for the generation of the ejection chains, and on a higher algorithmic level, the ejection chain process is embedded into an Iterated Local Search algorithm. Computational results confirm that this approach leads to very fast algorithms, showing that ejection chain algorithms have the potential to compete with state of the art algorithms for the VRPTW.

Herman Sontrop, Pieter van der Horn, Marc Uetz

3D Inter-subject Medical Image Registration by Scatter Search

Abstract

Image registration is a very active research area in computer vision, namely it is used to find a transformation between two images taken under different conditions. Point matching is an image registration approach based on searching for the right pairing of points between the two images. From this matching, the registration transformation we are searching, can be inferred by means of numerical methods.

In this paper, we propose a scatter search (SS) algorithm to solve the matching problem. SS is a hybrid metaheuristic with a good trade-off between search space diversification and intensification. On the one hand, diversity is basically introduced from a population-based approach where systematic combinations of subsets of solutions are performed. On the other hand, intensification is achieved with a local search procedure, to ensure the local improvement of promising solutions. Our computational experimentation in a real-world inter-subject medical registration environment establishes the effectiveness of our procedure in relation to different approaches usually applied to solve the problem.

Oscar Cordón, Sergio Damas, J. Santamaría, Rafael Martí

Evolution Strategies and Threshold Selection

Abstract

A hybrid approach that combines the (1+1)-ES and threshold selection methods is developed. The framework of the new experimentalism is used to perform a detailed statistical analysis of the effects that are caused by this hybridization. Experimental results on the sphere function indicate that hybridization worsens the performance of the evolution strategy, because evolution strategies are well-scaled hill-climbers: the additional threshold disturbs the self-adaptation process of the evolution strategy. Theory predicts that the hybrid approach might be advantageous in the presence of noise. This effect could be observed—however, a proper fine tuning of the algorithm’s parameters appears to be advantageous.

Thomas Bartz-Beielstein

A Hybrid GRASP with Data Mining for the Maximum Diversity Problem

Abstract

The maximum diversity problem (MDP) consists in identifying, in a population, a subset of elements, characterized by a set of attributes, that present the most diverse characteristics among themselves. The identification of such solution is an NP-hard problem. In this work, we propose a hybrid GRASP metaheuristic for the MDP that incorporates a data mining process. Data mining refers to the extraction of new and potentially useful knowledge from datasets in terms of patterns and rules. We believe that data mining techniques can be used to extract patterns that represent characteristics of sub-optimal solutions of a combinatorial optimization problem. Therefore these patterns can be used to guide the search for better solutions in metaheuristics procedures. Performance comparison between related work and the proposed hybrid heuristics is provided. Experimental results show that the new hybrid GRASP is quite robust and, mainly, this strategy is able to find high-quality solutions in less computational time.

L. F. Santos, M. H. Ribeiro, A. Plastino, S. L. Martins

A New Multi-objective Particle Swarm Optimization Algorithm Using Clustering Applied to Automated Docking

Abstract

In this paper we introduce the new hybrid Particle Swarm Optimization algorithm for multi-objective optimization ClustMPSO. We combined the PSO algorithm with clustering techniques to divide all particles into several subswarms. Strategies for updating the personal best position of a particle, for selection of the neighbourhood best and for swarm dominance are proposed. The algorithm is analyzed on both artificial optimization functions and on an important real world problem from biochemistry. The molecule docking problem is to predict the three dimensional structure and the affinity of a binding of a target receptor and a ligand. ClustMPSO clearly outperforms a well-known Lamarckian Genetic Algorithm for the problem.

Stefan Janson, Daniel Merkle

A Hybrid GRASP-Path Relinking Algorithm for the Capacitated p – hub Median Problem

Abstract

The p – hub median problem is an NP hard location – allocation problem, that consists of finding p points to establish facilities and the assignment of the users to these points. In the capacitated version of this problem, each hub has got a maximum capacity limiting the traffic to be assigned. A new evolutionary approach that has been very effective for solving optimization problems is Path Relinking, an extension of Scatter Search that links solutions over neighborhood spaces. GRASP is a well-known randomized multistart metaheuristic. In this paper, we present a hybrid GRASP-Path Relinking for the capacitated p – hub median problem where the GRASP is used to construct the population of the Path Relinking. Computational results demonstrate that the hybrid GRASP-Path Relinking provides better solutions, in terms of both running times and solution quality.

Melquíades Pérez, Francisco Almeida, J. Marcos Moreno-Vega

Backmatter

Titel: Hybrid Metaheuristics
herausgegeben von: María J. Blesa
Christian Blum
Andrea Roli
Michael Sampels
Verlag: Springer Berlin Heidelberg
Electronic ISBN: 978-3-540-31898-9
Print ISBN: 978-3-540-28535-9
DOI: https://doi.org/10.1007/11546245