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

点击翻译按钮获取中文摘要

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