Development of an Evolutionary Multiobjective Local Search Algorithm and Its Application to Scheduling Problems

点击翻译按钮获取中文摘要

In this research, we proposed an evolutionary multiobjective genetic local search algorithm called a S-MOGLS (simple multiobjective genetic local search) algorithm. The proposed S-MOGLS algorithm uses both the weighted sum-based scalar fitness function and the Pareto ranking. The weighted sum-based scalar fitness function is used in the selection of parent solutions and the local search for their offspring solutions. It is also used in the selection of start solutions for local search from offspring solutions. On the other hand, the Pareto ranking is used in the generation update phase where the next population is constructed from the current population, the offspring population generated by genetic operations, and the improved population by local search. We achieved the simplification and the speedup of the S-MOGLS algorithm by the use of both the weighted sum-based scalar fitness function and the Pareto ranking. Through computational experiments on multiobjective 0/1 knapsack problem … More s, we demonstrated the necessity to use the three populations (i.e., current, offspring and improved populations) in the generation update phase. We also demonstrated the validity of the use of the weighted sum-based scalar fitness function for the selection of parent solutions from the current population and the selection of start solutions from the offspring population.In addition to the proposal of the S-MOGLS algorithm, we proposed several ideas to improve the performance of evolutionary multiobjective optimization algorithms. One is the selection of extreme solutions as parents in order to increase the diversity of solutions. Another is the recombination of similar parents in order to increase both the diversity and the convergence of solutions. These two ideas were combined into a similarity-based mating scheme where an extreme solution is combined with a similar solution. The other idea proposed in this research is the removal of overlapping solutions in the objective space in order to increase the diversity of solutions. We also examined two repair schemes (Lamarckian and Baldwinian) and their hybrid version (partial Lamarckian) in this research. Less