Genetic and Local Search Algorithms as Robust and Simple Optimization Tools

Mutsunori Yagiura and Toshihide Ibaraki

Abstract:
One of the attractive features of recent metaheuristics is in its robustness and simplicity. To investigate this direction, the single machine scheduling problem is solved by various genetic algorithms (GA) and random multi-start local search algorithms (MLS), using rather simple definitions of neighbors, mutations and crossovers. The results indicate that: (1) the performance of GA is not sensitive about crossovers if implemented with mutations, (2) simple implementation of MLS is usually competitive with (or even better than) GA, (3) GRASP type modification of MLS improves its performance to some extent, and (4) GA combined with local search is quite effective if longer computational time is allowed.

Key Words: combinatorial optimization, metaheuristics, genetic algorithm, local search, GRASP, single machine scheduling.

Meta-Heuristics: Theory and Applications, eds. I.H. Osman and J.P. Kelly, (Kluwer Academic Publishers, Boston, 1996) pp. 63-82.

PS file

Back to the Paper List