Catálogo de publicaciones - libros

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.