PARALLEL BIASED SEARCH FOR COMBINATORIAL OPTIMIZATION - GENETIC ALGORITHMS AND TABU

Combinatorial optimization problems arise in different fields and require computing resources that grow very rapidly with the problem dimension. Therefore the use of massively parallel architectures represents an opportunity to be considered, characterized by very large speed-ups for significant applications. In this paper we consider some relatively general techniques that are paradigmatic of different parallel approaches, ranging from the concurrent execution of independent searches to a fully interacting 'population' of candidate solutions. In particular, we briefly summarize the TABU and GA algorithms, discuss their parallel implementation and present some experimental results on two benchmark problems: QAP and the N-k model. A new 'reactive' TABU scheme based on the 'open hashing' technique is also presented.