Discovery Sagaサイレントキーワード俯瞰

遺伝的アルゴリズム / 実数値GA / 関数最適化 / 変数間の依存関係 / 多峰性関数 / EN-GHC / マスターワーカー / PCクラスタ / UNDX / MGG

遺伝的アルゴリズム(GA)は,多くの局所解をもつ多峰性の探索空間において大域的に良好な解を発見できる強力な近似解法として注目を集めている.GAによる関数最適化への接近においては,特に,UNDX+MGGが,変数間に強い依存関係をもつ多峰性のベンチマーク関数において良好な性能を示している.UNDX+MGGは,全ての変数間に強い依存関係が存在すると仮定して,全ての変数を同時にサンプリングしている.そのため,一部の変数間にしか依存関係をもたない高次元の関数において,UNDX+MGGの探索はかなりの無駄を含んでいると考えられる.特に,多峰性関数においては,同時に探索する変数の数に対して局所解の数が指数関数的に増加するため,問題はさらに深刻になると考えられる.
本研究では,各変数の依存関係をなるべく正確に推定し,その情報を用いることにより,従来手法であるUNDX+MGGよりも,効率よく探索を行うことができる実数値GAを提案することを目的としている.本年度の研究成果は以下のようにまとめられる:
・昨年度,提案したEpistasis-Neighborhood Genetic Hill Climbing (EN-GHC)を困難な大規模実問題へ適用するため,EN-GHCがPCクラスタ上で効率よく計算資源を利用できるような並列モデル(並列EN-GHC)の提案を行った.本モデルは,EN-GHCをマスターワーカー方式に基づき並列化したモデルであり,直接依存関係を持たない変数群の探索を複数のワーカーへ振り分けることにより,並列化効率を向上させている.
・並列EN-GHCの並列化効率を調査するため,PCクラスタ上で,昨年度整備したベンチマーク関数へ適用し,良好な結果を得ることに成功した.
・現在,EN-GHCとその並列化に関する研究成果に関する論文の投稿へ向けて準備中である.

遺伝的アルゴリズム / 実数値GA / UNDX / 関数最適化 / 棲み分け / 騙し関数 / 並列分散化 / P2Pモデル / MGG / 多峰性関数 / 種の棲み分け

関数最適化問題を解決するための強力な最適化手法として,実数値遺伝的アルゴリズムUNDX+MGGがある.しかし,UNDX+MGGは,多様性を十分に保つために集団サイズを十分に大きくとったとしても,1)探索空間が有界な多峰性関数において最適解が探索空間の境界付近に存在する場合,2)多峰性関数において有望な局所解の存在する大谷の間口が最適解の存在する大谷の間口よりも広い場合に,最適解領域を十分にサンプリングする前に集団を局所解に収束させてしまうという問題点がある.これに対し,昨年度,隔離された複数の部分集団がそれぞれの存在する探索領域を独立に探索を行う「種の棲み分け」の概念を導入した新しい探索モデルを提案し,UNDX+MGGで解決可能な関数に加え,UNDX+MGGでは探索に失敗する上述の性質を持つ関数も解決可能であることを実験により確認した.
しかし,上述の手法は,部分集団の探索範囲をランダムに生成していたため,探索効率が悪いという問題点があった.また,大規模な実問題への適用において探索時間の観点から問題があり,並列分散化実装が望まれていた.そこで,本年度は,部分集団の探索範囲が広すぎる場合に広い間口の大谷に収束する確率が高くなることに着目し,探索範囲を広い範囲からはじめて,同じ大谷に収束した場合に徐々に探索範囲を縮小していく方法を提案し,その有効性を確認した.また,大規模な実問題への適用の観点から,提案手法の並列分散実装を提案した.本実装は,サーバーへの負荷の集中を回避するために,ピア・ツー・ピア(Peer to Peer ; P2P)モデルを採用し,計算時間を大幅に削減することに成功した.本成果を,計測自動制御学会システムインテグレーション部門講演会にて発表した.