A multi-objective optimization method based on genetic algorithm and local search with applications to scheduling

Traditional multi-objective genetic algorithms are more concerned with how to achieve a uniformly distributed non-inferior solution frontier In many problems with highly discrete solution space, however there is not a smooth and uniformly distributed non-inferior frontier in nature. Hence for these cases, it is more significant to find non-inferior solutions of better performance with high efficiency. In this paper, an algorithm is proposed to deal with such problems, which enhances the ability of genetic algorithms in searching non-inferior solutions in an effective and efficient manner by introducing proper local search strategies into the evolution process. In addition, a kind of fitness evaluation scheme is recommended for multi-objective genetic algorithms. A typical permutation flow shop problem is studied for illustration, and the results of numerical experiments have demonstrated the effectiveness and efficiency of the algorithm.