How to Choose Solutions for Local Search in Multiobjective Combinatorial Memetic Algorithms

This paper demonstrates that the performance of multiobjective memetic algorithms (MOMAs) for combinatorial optimization strongly depends on the choice of solutions to which local search is applied. We first examine the effect of the tournament size to choose good solutions for local search on the performance of MOMAs. Next we examine the effectiveness of an idea of applying local search only to non-dominated solutions in the offspring population. We show that this idea has almost the same effect as the use of a large tournament size because both of them lead to high selection pressures. Then we examine different configurations of genetic operators and local search in MOMAs. For example, we examine the use of genetic operators after local search. In this case, improved solutions by local search are used as parents for recombination while local search is applied to the current population after generation update.