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

在这项研究中，我们提出了一个进化的多目标遗传局部搜索算法称为S-MOGLS（简单多目标遗传局部搜索）算法。建议S-MOGLS算法同时使用基于加权和的标量适应度函数和Pareto排序。基于加权和的标量适应度函数用于父解的选择和子解的局部搜索。它也用于从后代解中选择局部搜索的起始解。另一方面，Pareto排序被用于世代更新阶段，其中下一个群体是由当前群体、通过遗传操作产生的后代群体和通过局部搜索产生的改进群体构造的。通过使用基于加权和的标量适应度函数和Pareto排序，实现了S-MOGLS算法的简化和加速。通过对多目标0/1背包问题的计算实验， 关于我们 s，我们证明了使用三个群体的必要性（即，当前、后代和改进的群体）。我们还证明了使用基于加权和的标量适应度函数从当前种群中选择父解和从后代种群中选择起始解的有效性。除了提出S-MOGLS算法外，我们还提出了几种改进进化多目标优化算法性能的思想。一种是选择极端解作为父解，以增加解的多样性。另一种方法是相似亲本的重组，以增加解的多样性和收敛性。这两个想法结合成一个基于相似性的交配方案，其中极端的解决方案与类似的解决方案相结合。在本研究中提出的另一个想法是消除重叠的解决方案在目标空间，以增加解决方案的多样性。在这项研究中，我们还研究了两个修复方案（拉马克和鲍德温）和他们的混合版本（部分拉马克）。少

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