進化的探索の理論

进化搜索理论

• 批准号: 07243104
• 负责人: 小林 重信
• 金额: $ 39.1万
• 依托单位: Tokyo Institute of Technology
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research on Priority Areas
• 财政年份: 1995
• 资助国家: 日本
• 起止时间: 1995 至 1997
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-07243104/
• 关键词: 進化的計算; 遺伝的アルゴリズム; 形質遺伝と多様性維持; 枝組み立て交叉(EAX); Job-based Order Crossover; 正規分布交叉; Minimal Generation Gap(MGG)モデル; レンズ設計の自動化; 形質遺伝過程の可視化; 進化的探索; 創発的探索; コード化; 交叉; 騙し(だまし)問題解析; SXX(Subtour Exchange Crossover); TSP; JSP; 多目的最適化

進化的計算では,コード化/交叉の設計および世代交代モデルの設計が基本となり,前者は形質遺伝という視点,後者は多様性維持という視点が重要である.本年度は,過去2年間の実績を踏まえて,工学的応用可能性を意識しつつ研究を進め,下記の点において大きな研究成果を得た.(1)コード化/交叉の設計:巡回セールスマン問題(Traveling Salesman Problem:TSP)を対象に枝交換交叉(Edge Assembly Crossover)を考案し,1万都市規模の問題Pの最適解を効率よく見いだすことに成功した.また,ジョブショップスケジューリング問題(Job Shop Scheduling Problem)を対象にIntermachine Job-based Order Crossoverを考案し,ベンチマークFT10×10,FT20×5に適用して,最適解を非常に高い確率で見いだすことに成功した.さらに,関数最適化を対象に正規分布交叉(Normal Distribution Crossover)を考案し,従来法と比べて,多峰性関数に対して頑健な性能を示すことを確認した.(2)多様性維持に優れた世代交代モデルについて:多様性維持に優れた世代交代モデルとして提案したMGG(Minimal Generation Gap)について,最小騙し問題を用いてその有用性を解析した.(3)工学的設計問題への応用:進化的計算の工学的設計問題への応用として,レンズ設計,並列機械スケジューリング,VLSIフロアプラン設計,プリント基板設計への適用を試み,有用性を確認した.特に,レンズ設計においては,従来の最適化手法では設計が不可能とされていた3枚以上のレンズ系の設計自動化に成功した.本研究の成果は100年以上の歴史のある光学設計の分野にブレークスルーをもたらすものと産業界からも高く評価されている.

在进化计算中，编码/交叉的设计和世代变化模型的设计是基础，前者是性状遗传学的观点，后者是维持多样性的观点。在今年，考虑了过去两年的成就，研究了工程应用的可能性，并在以下几点中获得了出色的研究结果。 （1）编码/交叉设计：Edge Assembly跨界车（TSP），我们成功地有效地找到了10,000个城市问题的最佳解决方案P。此外，对于车间调度问题的基于车间的工作订单（工作购物商店调度问题）。我们已经设计了交叉，并通过将其应用于基准FT10×10和FT20×5，成功地找到了具有很高概率的最佳解决方案。此外，我们已经设计了一个正态分布跨界，以进行功能优化，并确认它与常规方法相比具有强大的多模式函数性能。 （2）在维持多样性方面非常出色的世代变化模型中：提议作为一个世代变化模型的MGG（最小生成）用于维持多样性差距非常好）来使用最小欺骗问题来分析其实用性。 （3）应用于工程设计问题：我们试图将其应用于镜头设计，并行机器调度，VLSI平面图设计和印刷电路板设计，以作为进化计算工程问题的应用，并确认其有用性。特别是在镜头设计中，我们成功地自动化了三个或更多镜头系统的设计，这些系统被认为是不可能使用常规优化方法设计的。这项研究的结果受到行业的高度赞扬，这是光学设计领域的突破，该领域的历史超过100年。

项目成果

S.Tsutsui, Y.Fujimoto and A.Ghosh: "Forking GAs:GAs with Search Space Division Schemes" Evolutionary Computation,MIT Press. 5. 61-80 (1997)

S.Ttsutsui、Y.Fujimoto 和 A.Ghosh：“分叉 GA：具有搜索空间划分方案的 GA”进化计算，麻省理工学院出版社。

小圷成一,漆田裕司,平田廣則: "状態空間の階層構造を考慮した遺伝的アルゴリズムによるVLSI配置手法" 電気学会論文誌C. 118-C(掲載予定). (1998)

Seiichi Kotono、Yuji Urushita、Hironori Hirata：“考虑状态空间层次结构的使用遗传算法的 VLSI 放置方法”，日本电气工程师学会会刊 C. 118-C（待出版）。

H.Tamaki and E.Nishino: "A Genetic Algorithm Approach to Multi-Objective Scheduling Problems with Regular and Non-Regular Objective Functions" Proc.of 8th IFAC/IFORS/IMACS/IFIP Symp.on Large Scale Systems. to be appeared (1998)

H.Tamaki 和 E.Nishino：“具有规则和非规则目标函数的多目标调度问题的遗传算法方法”Proc.of 8th IFAC/IFORS/IMACS/IFIP Symp.on Large Scale Systems。

Terano, T., Ishino, Y.: "Data Analysis Using Simulated Breeding and Inductive Learning Methods" IJCAI'95 Workshop on Data Engineering and Inductive Learning. 60-69 (1995)

Terano, T.、Ishino, Y.：“使用模拟育种和归纳学习方法进行数据分析”IJCAI95 数据工程和归纳学习研讨会。

山村雅幸,佐藤浩,小林重信: "最小騙し問題を用いた世代交代モデルの解析" 人工知能学会誌. 13. 掲載予定 (1998)

Masayuki Yamamura、Hiroshi Sato、Shigenobu Kobayashi：“利用最小欺骗问题分析代际变化模型”日本人工智能学会杂志 13。预定出版（1998 年）。