遺伝的アルゴリズムの最適化問題への適用に関する基礎研究

遗传算法在优化问题中的应用基础研究

基本信息

批准号：
05750385
负责人：
相澤彰子
金额：
$ 0.58万
依托单位：
National Institute of Informatics
依托单位国家：
日本
项目类别：
Grant-in-Aid for Encouragement of Young Scientists (A)
财政年份：
1993
资助国家：
日本
起止时间：
1993 至无数据
项目状态：
已结题

项目摘要

本研究は平成5年度の単年度計画で,柔らかい最適化手法として近年注目される遺伝的アルゴリズムに関する新しいテーマに取り組むものであり,今年度内で,複雑な系の最適化に遺伝的な解法を適用する上での問題点を明らかにし,拡張した解探索アルゴリズムの提案を行うことを目的としていた.1年間の研究活動による本研究の成果は以下のとおりである.大規模で複雑なシステムの最適化では一般に,システム性能を解析的に求めることは困難で,シミュレーションあるいは実際の動作を通した性能評価が必要である.本研究ではまず,これら現実の最適化問題の特徴を考察し,(1)観測される評価量に雑音(たとえばシミュレーションの乱数による評価量の変分など)が含まれること,(2)評価に時間がかかるため計算資源の有効な配分が性能向上の鍵となること,の2点を重要な問題点として指摘した.次に上記の性質を扱うため,(i)評価量の誤差,および,(ii)探索空間上での評価量の分布,をダイナミックに推定しながら探索過程を制御し,限られた時間の中で効率的に良い解を求める適応的な探索法を開発した.また代表的なベンチマーク問題を用いて従来の方法との性能比較を行い,雑音のある探索問題における提案手法の優位性を示した.本研究の成果である新手法は,統計学の逐次決定理論を応用しており,遺伝的アルゴリズムだけではなく一般の生成検査法(Generate and Test Method)においても適用可能である.また本研究のもう1つの成果として,遺伝的アルゴリズムが行う超平面上での探索処理に関して有用な知見が得られたことがあげられ,今後の研究指針として役立てる予定である.

这项研究是1993年的单年度计划，旨在解决与遗传算法相关的新主题，遗传算法作为一种软优化方法近年来引起了人们的关注。在本财政年度内，我们将把遗传解决方案应用于优化这项研究的目的是澄清解决问题的问题并提出一种扩展的解决方案搜索算法。本研究的结果如下。在优化大规模、复杂系统时，一般很难通过分析确定系统性能，需要通过仿真或实际运行来评估性能。本书在研究中首先考虑了系统的特点这些现实世界的优化问题，并考虑（1）观察到的评估量中的噪声（例如，由于模拟中的随机数）；（2）由于评估需要时间，计算资源的有效分配是提高性能的关键为了处理上述特性，我们在动态估计（i）评估量的误差和（ii）的同时控制搜索过程。评估量在搜索空间上的分布，以及我们开发了一种自适应搜索方法来有效地找到好的解决方案。我们还使用典型的基准问题将所提出的方法与传统方法的性能进行了比较，并证明了所提出的方法在噪声搜索问题中的优越性。这项研究的成果，应用了统计学的顺序决策理论，不仅使用了遗传算法，还使用了通用的生成测试方法。这项研究的另一个结果是，我们获得了有关遗传算法在超平面上执行搜索处理的有用知识，这将指导我们未来的研究。