Genetic and Local Search Algorithms
as Robust and Simple Optimization Tools
Mutsunori Yagiura and Toshihide Ibaraki
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,
(4) GA combined with local search is quite effective
if longer computational time is allowed.
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.
Back to the Paper List