共進化にる問題生成を用いた遺伝的アルゴリズムの有効性検証

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

自然の進化様式を模倣した遺伝的アルゴリズム(以下GAと略す)は,近年様々な分野における最適化問題に応用研究がなされている。しかしながら,GAの有効性はいまだ明らかではない点が多い。本研究は共進化的枠組みを利用することによってGAが最適化できないような問題空間をGAによって求めることを通して,GAの探索能力を検証する事を目的とした。具体的なアプローチとして,(1)問題生成空間として1次元関数空間を設定した。(2)問題を生成するGAに探索対象となる関数形状を最適値を固定した遺伝子として持たせ,探索を行うGAは生成される関数を逐次解かせるものとした。(3)生成された問題の難しさとして,探索側GAの遺伝子集団をどれほど最適解から遠い局所解に収束させる度合いと設定した。以上の設定下では,GAの理論的考察から騙し関数と呼ばれている問題形式が,問題生成側の一つの解であることが自明である。しかしながら,実験を行った結果からは明白な騙し関数が生成される前に,探索側GAの最適解探索力が失われてしまうことが明らかとなった。このとき得られた問題空間は多峰性関数であり,探索側GAの初期集団をいち早く局所解にトラップし,その後最適解から離れた局所解に向かわせるような性質を持っていた。実際,得られ関数に集団数を増やした単純GAを適用しても,最適解を発見することができないものであった。以上のことから,GAの理論の一つであるビルディングブロック仮説に基づいて作られた騙し関数以前に,断続的なビルディングブロック生成が行われることによって,基本的なGAの最適化能力が失われる問題が存在することが明らかとなった。以上の詳細については,第4回インテリジェントシステムシンポジウムおよび日本機械学会第72期通常総会講演会にて報告を行っている。