Metaheuristics 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
such as random multi-start local search (MLS),
genetic algorithm (GA),
simulated annealing (SA) and
tabu search (TS),
using rather simple inside operators.
The results indicate that:
(1) simple implementation of MLS is usually competitive with
(or even better than) GA,
(2) GA combined with local search is quite effective
if longer computational time is allowed, and its
performance is not sensitive
(3) SA is also quite effective if longer computational time is allowed,
and its performance is not much dependent on parameter values,
(4) there are cases in which TS is more effective than MLS;
however, its performance depends on how to define
the tabu list and parameter values and
(5) the definition of neighborhood is very important
for all of MLS, SA and TS.
combinatorial optimization, metaheuristics,
local search, GRASP, genetic algorithm, simulated annealing,
tabu search, single machine scheduling.
Proceedings of 1996 IEEE International Conference
on Evolutionary Computation (ICEC '96),
(Institute of Electrical and Electronics Engineers, 1996) 541-546.
Back to the Paper List