Metaheuristics 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 metaheuristics, 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 to crossovers, (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.

Key Words: 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.

PS file


Back to the Paper List