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

进化多目标局部搜索算法的发展及其在调度问题中的应用

• 批准号: 14380194
• 负责人: ISHIBUCHI Hisao
• 金额: $ 3.33万
• 依托单位: Osaka Prefecture University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (B)
• 财政年份: 2002
• 资助国家: 日本
• 起止时间: 2002 至 2004
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-14380194/
• 关键词: Evolutionary Computation; Genetic Algorithms; Multiobjective Optimization; Evolutionary Multiobjective Optimization; Genetic Local Search; Hybrid Algorithms; Convergence; Diversity; メメティックアルゴリズム; 選択操作

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

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

项目成果

Some Issues on the Implementation of Local Search in Evolutionary Multiobjective Optimization

• DOI: 10.1007/978-3-540-24854-5_120
• 发表时间: 2004-06
• 作者: H. Ishibuchi;Kaname Narukawa

H.Ishibuchi, T.Yoshida: "Hybrid Evolutionary Multi-Objective Optimization Algorithms"Frontiers in Artificial Intelligence and Applications. Vol.87. 163-172 (2002)

H.Ishibuchi、T.Yoshida：“混合进化多目标优化算法”人工智能及其应用前沿。

Mating Scheme for Controlling the Diversity-Convergence Balance for Multiobjective Optimization

• DOI: 10.1007/978-3-540-24854-5_121
• 发表时间: 2004-06
• 作者: H. Ishibuchi;Youhei Shibata

Effects of Three-Objective Genetic Rule Selection on the Generalization Ability of Fuzzy Rule-Based Systems

• DOI: 10.1007/3-540-36970-8_43
• 发表时间: 2003-04
• 作者: H. Ishibuchi;Takashi Yamamoto

H.Ishibuchi, Y.Shibata: "An Empirical Study on the Effect of Mating Restriction on the Search Ability of EMO Algorithms"Lecture Notes in Computer Science. Vol.2632. 433-447 (2003)

H.Ishibuchi、Y.Shibata：“交配限制对 EMO 算法搜索能力影响的实证研究”计算机科学讲义。