PARALLEL GENETIC ALGORITHMS WITH LOCAL SEARCH

This paper presents methods of applying local search to global optimiz ation problems. The most common approach, multistart, selects the best solution from restarts of local search from random starting points. P artitional methods augment local search with general principles concer ning the location of global optima in real space, significantly improv ing the effectiveness of local search in function optimization problem s. Standard partitional methods, however, are not directly applicable to combinatorial optimization problems. We describe a genetic algorith m, GALO, that is similar to the partitional methods, but can be applie d to combinatorial problems. Empirical results are presented for a par allel implementation of GALO that show it to be effective for the quad ratic assignment problem. Copyright (C) 1996 Elsevier Science Ltd