遺伝的アルゴリズムを用いた近似最適化手法の一般的設計指針と応用のための基礎的研究

通用设计准则的基础研究以及使用遗传算法的近似优化方法的应用

• 批准号: 14780266
• 负责人: 永田 裕一
• 金额: $ 1.09万
• 依托单位: Japan Advanced Institute of Science and Technology
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Young Scientists (B)
• 财政年份: 2002
• 资助国家: 日本
• 起止时间: 2002 至 2004
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-14780266/
• 关键词: 遺伝的アルゴリズム; 集団の多様性; 巡回セールスマン問題; 交叉設計; ジョブショップスケジューリング問題; クラスタリング; Evolution Strategy; 交叉; 実数値関数最適化; カメラレンズ設計; 遺伝的アルゴリズム; 集団の多様性; 巡回セールスマン問題; 交叉設計; ジョブショップスケジューリング問題; クラスタリング; Evolution Strategy; 交叉; 実数値関数最適化; カメラレンズ設計

今年度の本研究課題において、(1)遺伝的アルゴリズムにおける集団の多様性を低コストで維持する方法、(2)集団を適切にクラスタリングして探索を効率化する方法、について研究を行った。(1)に関して、本研究ではGAの世代モデルに着目して探索能力を改善する手法を提案した。GAの世代モデルは、探索集団から交叉オペレーターを適用するための解候補を選択する複製選択と、交叉で生成された新たな探索点のうちどれを選択して集団に残すかを決定する生存選択からなる。通常これらは交叉によって生成された探索点の評価値のみを用いて行い、高い評価値を持つものが次世代の集団として選択される。生存選択によって集団の多様性は失われる傾向にあり、最終的には集団が収束して探索が終了する。本研究では生存選択において解候補の評価値だけでなく、選択による多様性の損失量を局所的に考慮する方法を提案した。提案手法を巡回セールスマン問題へ適用した結果、これまでに他の研究者によって提案されている最も優れている近似解法の性能を大きく上回る性能を得ることに成功した。たとえば、ベンチマーク問題のひとつである4461都市問題であれば、研究室のパソコンを用いて3時間程度で90%の確率で最適解を見つけることができる。同じ問題に対し従来手法を用いた場合、同様の計算時間において最適解発見率は30%程度である。(2)に関して、本研究ではGAの探索集団を探索状況に応じて適応的にクラスタリングする手法を提案した。探索空間の形状が複数の谷を持つ場合、一般にGAの探索集団を何らかの方法でクラスタリングするのが有効であると考えられているが、提案手法ではクラスタリングの規範として、(i)各クラスターに含まれる固体の要素数がある一定値以上になる(ii)探索空間内で集団の密度がある一定値を越えてはならない、という制約を導入した。その結果、組合せ最適化問題の中では最も困難な問題のひとつであるジョブショップスケジューリング問題において、提案手法により従来この問題に対して最も優れているとされるGAと同等の性能を実現することができた。

在今年的研究主题中，我们对（1）如何以低成本维持遗传算法的人口多样性，以及（2）如何适当聚类以提高搜索效率。关于（1），这项研究集中在GA的生成模型上，并提出了一种提高搜索能力的方法。 GA生成模型由副本选择组成，该模型选择了用于从搜索人群中应用交叉操作员的解决方案候选者，以及一个生存选择，该选择确定了在十字架上选择的哪些新搜索点保留在人群中。这些通常仅使用交叉生成的搜索点的评估值进行，而评估值较高的搜索点作为下一代组。生存选择往往会失去人口多样性，最终人口汇聚和搜索结束。在这项研究中，我们提出了一种方法，不仅在局部考虑候选解决方案的评估值，而且还考虑了选择在生存选择中造成的多样性损失量。由于将拟议的方法应用于旅行社问题，我们成功地实现了绩效，远远超过了其他研究人员提出的最佳近似解决方案的性能。例如，如果它是基准问题之一，即4461个城市问题，则可以在大约三个小时内使用实验室计算机找到最佳解决方案。当常规方法用于相同问题时，在相同的计算时间内，最佳解决方案发现率约为30％。关于（2），本研究提出了一种根据搜索情况适应群集搜索群体的方法。当搜索空间的形状具有多个阀门时，通常认为以某种方式将GA搜索人群聚集是有效的，但是所提出的方法将约束作为聚类的限制（i）每个集群中包含的固体元素的数量大于一定值，并且（II）在搜索空间内不得超过一定值。结果，在组合优化问题中，这是最困难的问题之一，能够达到与GA相等的绩效，这是以前认为在此问题中是最好的。