超平面処理に基づく集団型探索アルゴリズムの研究

基于超平面处理的集体搜索算法研究

基本信息

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

项目摘要

本研究は平成6年度の単年度で,柔らかい最適化手法として注目される集団型探索法に関する基礎的な検討を行うものであり,解空間上で定義される超平面の統計モデルに基づく新しい解探索アルゴリズムの提案および評価を目的としている.1年間の研究活動による本研究の成果は以下のとおりである.まず,集団型探索法における局所処理の考案では,超平面で表現された部分空間上での解探索を正規分布からのサンプリングとしてモデル化して,「スキーマ貧欲」(schemata expliting)と呼ぶ局所探索メカニズムを定義した.そして,この「スキーマ貧欲」な局所探索を,解候補の集団から優れた部分集合を選択する問題に対応づけ,「確率的スキーマ貧欲法」(stochastic schemata exploiter,以下SSE)と呼ぶ新しい解探索アルゴリズムを提案した.次に,集団型探索法における最適化問題の分析では,超平面内に存在する解の平均および分散の観測値に基づき優れた超平面の選択の容易性を予測し,与えられた問題の容易/困難性を判断する方法を提案した.この分析法は最適解が既知であることを必要とするが,分析の結果を視覚的に把握でき大規模な問題に適用可能な点が特徴である.さらに,容易/困難なテスト問題を用いた評価では,提案したSSEと代表的な集団型探索アルゴリズムである遺伝的アルゴリズムの性能を比較した.実験の結果,SSEが局所探索に優れ,はやい収束特性を持つこと,および大域探索に関してはほぼ同等の能力を持つことを示した.また,ランダム探索とのハイブリッド化によるだまし問題の克服,ヒューリスティク探索とのハイブリッド化による近傍探索の改善,の2つについて両者の適性を評価し,SSEのはやい収束特性が他の探索手法とのハイブリッド化において有利であることを示した.本研究で提案した手法は,超平面上の処理を部分集合の選択問題に還元して領域に依存しない効率的な探索法を提供するものである.選択確率の計算法の検討などにより,さらに新しいアルゴリズムへと発展することが期待される.

这项研究于 1994 年进行，是作为一种软优化方法而受到关注的集体搜索方法的基础研究，其目的是提出和评估搜索算法。1。经过多年的研究活动，本研究的结果如下：首先，在集体搜索方法中设计局部处理时，将超平面表示的子空间上的解决方案搜索建模为从“贪图式”中采样。 '（图式贪婪）我们定义了一种称为“模式贪婪”的本地搜索机制，我们称之为“概率模式贪婪”（随机模式）我们提出了一种新的解决方案搜索算法，称为exploiter（SSE）。接下来，在分析集体搜索方法中的优化问题时，我们提出了一种预测选择难易程度并确定给定问题的难易程度的方法。虽然该分析方法要求已知最优解，但其特点是分析结果可以直观地掌握，并且可以应用于大规模问题。在评估中，我们比较了所提出的SSE的性能。遗传算法是典型的集体搜索算法。已经表明它具有优异的搜索和快速收敛特性，并且在全局搜索方面具有几乎相同的能力。还表明它具有通过将其与随机搜索混合以及将其混合来克服欺骗问题的能力我们评估了两种方法改进邻域搜索的适用性，并评估了 SSE 的快速收敛特性。本研究提出的方法将超平面上的处理简化为子集选择问题，并且是一种不依赖于区域的有效搜索方法，预计通过考虑计算选择概率的方法可以进一步开发新算法。。