权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

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

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

基本信息

批准号：
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と同等の性能を実現することができた。

This year's research topics include: (1) methods for maintaining diversity of clusters in genetic diversity;(2) methods for exploring efficiency of clusters in appropriate genetic diversity; and (3) research on genetic diversity. (1)In this study, we propose ways to improve GA's ability to explore new technologies. GA Generations Select, Explore Groups Select, Intersect Solutions Select, Duplicate Options Select, Intersect New Discovery Points Select, Explore Groups Select, Survive Options Select Usually, this is the case when the search point is generated and the evaluation value is used. The diversity of groups in survival selection tends to be lost, and ultimately the diversity of groups ends in exploration. This study proposes a method for evaluating the diversity of candidates in the selection process. The proposed method is applied to the problem, and the proposed method is applied to the optimal solution. 4461 Urban problems, research rooms, and the use of time, 90% of the accuracy of the optimal solution. For the same problem, the optimal solution rate is 30% when the method is used and the calculation time is the same. (2)In this study, we propose a method to explore the group's status and to explore the appropriate resources. The shape of the exploration space has a plurality of valleys, and in general, the exploration set has a method for determining whether the exploration space has a plurality of valleys.(i) The number of solid elements contained in each exploration space has a certain value or more.(ii) The density of the exploration space has a certain value. The result, the combination optimization problem, the most difficult problem, the proposal method, the optimization problem, the GA equivalent performance, the optimization problem.

项目成果

期刊论文数量（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算法的镜头设计