EVOLUT IONARY SCHEDUL ING AND ROUT ING Edmund Burke, cha i r Balance between Genetic Search and Local Search in Hybrid Evolutionary Multi-Criterion Optimization Algorithms

The aim of this paper is to clearly demonstrate the importance of finding a good balance between genetic search and local search in the implementation of hybrid evolutionary multi-criterion optimization (EMO) algorithms. We first modify the local search part of an existing multi-objective genetic local search (MOGLS) algorithm. In the modified MOGLS algorithm, the computation time spent by local search can be decreased by two tricks: to apply local search to only selected solutions (not all solutions) and to terminate local search before all neighbors of the current solution are examined. Next we show that the local search part of the modified MOGLS algorithm can be combined with other EMO algorithms. We implement a hybrid version of a strength Pareto evolutionary algorithm (SPEA). Using the modified MOGLS algorithm and the hybrid SPEA algorithm, we examine the balance between genetic search and local search through computer simulations on a two-objective flowshop scheduling problem. Computer simulations are performed using various specifications of parameter values that control the computation time spent by local search. 1