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

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

基本信息

批准号：
14780266
负责人：
永田裕一
金额：
$ 1.09万
依托单位：
Japan Advanced Institute of Science and Technology
依托单位国家：
日本
项目类别：
Grant-in-Aid for Young Scientists (B)
财政年份：
2002
资助国家：
日本
起止时间：
2002 至 2004
项目状态：
已结题

项目摘要

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

在今年的研究项目中，我们研究了（1）一种在遗传算法中以低成本维持种群多样性的方法，以及（2）一种对种群进行适当聚类以提高搜索效率的方法。针对（1），本研究提出了一种通过关注遗传算法的生成模型来提高搜索能力的方法。 GA生成模型由复制选择和生存选择组成，复制选择从搜索群体中选择应用交叉算子的候选解，生存选择决定应选择交叉生成的哪些新搜索点并将其保留在群体中。通常，这些仅使用交叉生成的搜索点的评估值来执行，并且选择评估值高的那些作为下一代组。由于生存选择，种群多样性往往会丧失，最终种群收敛，搜索结束。在本研究中，我们提出了一种方法，该方法不仅局部考虑候选解的评估值，还考虑由于生存选择中的选择而导致的多样性损失。将所提出的方法应用于旅行商问题的结果是，我们成功地获得了大大超过迄今为止其他研究人员提出的最佳近似解决方案的性能。例如，对于基准问题之一的4461城市问题，使用实验室的计算机可以在大约三个小时内以90%的概率找到最优解。当使用常规方法处理同一问题时，相同计算时间内最优解的发现率约为30%。针对(2)，本研究提出了一种根据搜索情况自适应聚类遗传算法搜索组的方法。当搜索空间的形状有多个山谷时，通常认为以某种方式对 GA 的搜索群体进行聚类是有效的，但在所提出的方法中，作为聚类的标准，（i）我们引入了一个约束，即要搜索的实体元素必须超过某个值 (ii) 搜索空间中的总体密度不得超过某个值。结果，对于最困难的组合优化问题之一的作业车间调度问题，所提出的方法能够达到与遗传算法相当的性能，这被认为是我能够做到的最好的方法。它。

项目成果

期刊论文数量（5）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

Yuichi Nagata: "The Criteria for Designing Crossovers for TSP"The 2004 Congress on Evolutionary Computation (CEC2004). (To be appeared). (2004)

Yuichi Nagata：“The Criteria for Design Crossovers for TSP”2004 年进化计算大会 (CEC2004)。

DOI：
发表时间：
期刊：
影响因子：
0
作者：
通讯作者：

The Criteria for Designing Crossovers for TSP

TSP 交叉设计标准

DOI：
发表时间：
2004
期刊：
The 2004 Congress on Evolutionary Computation (CEC2004)
影响因子：
0
作者：
Yuichi Nagata
通讯作者：
Yuichi Nagata

The EAX algorithm considering diversity loss

考虑多样性损失的EAX算法

DOI：
发表时间：
2004
期刊：
The 8th International Conference on Parallel Problem Solving from Nature (PPSN VIII)
影响因子：
0
作者：
Yuichi Nagata;Yuichi Nagata;Yuichi Nagata
通讯作者：
Yuichi Nagata

The Lens Design using the CMA-ES Algorithm

使用CMA-ES算法的镜头设计