【研究分野】感性情報学・ソフトコンピューティング

【研究領域課題番号】23500273 (KAKENデータベースで見る）

【研究キーワード】

大域的最適化 / 進化計算 / 大域的多峰性 / 大谷構造 / 関数最適化 / 実数値進化計算 / 実数値GA / 自然進化戦略 / 大谷内探索 / 遺伝的アルゴリズム

【研究成果の概要】

本研究では，大域的多峰性を有する探索空間において効率よく良好な解を発見するため，新たな探索アルゴリズムを提案した．大域的多峰性を有する探索空間においては，有力な大谷を効率よく発見し，発見された大谷において最良解を効率よく探索することが求められる．そこで，本研究では，大谷を想定して設計された実数値進化計算を繰り返し実行し，過去の探索履歴を用いることにより，新たな大谷を発見する探査の枠組みを提案し，既存の実数値進化計算手法では発見することができなかった最適解を発見することに成功した．また，大谷内の探索のための新たな実数値進化計算手法を提案し，既存手法をよりも効率よく最適解を発見することに成功した．

【研究種目】基盤研究(C)

【研究期間】2011 - 2013

【配分額】5,200千円 (直接経費: 4,000千円、間接経費: 1,200千円)

【研究分野】知能情報学

【研究領域課題番号】17700154 (KAKENデータベースで見る）

【研究キーワード】

遺伝的アルゴリズム / 実数値GA / UNDX+MGG / ISM / 大谷構造 / UV構造 / 関数最適化 / ズームレンズ設計 / 騙し問題 / UNDX / MGG

【研究成果の概要】

遺伝的アルゴリズム(Genetic Algorithm ; GA)による関数最適化への接近においては,実数値GAのUNDX+MGGが,変数間に強い依存関係をもつ多峰性の大谷関数において良好な性能を示している.しかし,UNDX+MGGは,池田らの提唱するUV構造をもつ多峰性の関数においては最適解の探索に失敗するという問題点をもつ.昨年度,本問題を克服するため,UNDX+MGGを複数回実行する過程において,それまでに十分に探索を行った領域を推定し,その領域を探索領域から除外することにより,最終的に間口の狭いV谷に初期集団を生成する方法を提案し,その有効性を確認した.本年度の研究成果は以下のとおりである:
1.提案手法が効率よくV谷領域を発見するためには,初期集団が分布している大谷の最良解を効率よく発見できることが必要である.しかし,初期集団が分布している領域の大谷が多峰性であり,かつ,大谷の最良解がオフセットしている場合,UNDX+MGGは最良解の探索に失敗する.本研究では,大谷の最良解がオフセットしている場合,集団分布の重心が移動することに着目し,初期集団を再初期化する方法を提案し,その有効性を確認した.
2.困難な実問題であるズームレンズ設計へ提案手法を適用するための予備的な研究を行った.本研究では,ズームレンズ設計を,レンズ面の曲率,間隔,群間隔を決定変数とし,歪曲,解像度,焦点距離の誤差の重み付和を評価値とする最小化問題としてモデル化した.2群7枚ズームレンズ設計問題にUNDX+MGGを適用したところ,集団サイズを大きくしても評価値の悪い同じ型の局所解が発見され,本問題がUV構造を有していることが示唆された.ISMを適用した場合,UNDX+MGGよりは良好な解が得られたものの専門家による特許解の発見には至らなかった.現在,提案手法の適用を行っているところである.

【研究種目】若手研究(B)

【研究期間】2005 - 2006

【配分額】3,600千円 (直接経費: 3,600千円)

【研究分野】知能情報学

【研究領域課題番号】16300040 (KAKENデータベースで見る）

【研究キーワード】

進化計算 / 遺伝アルゴリズム / 実数値GA / 強化学習 / 重点サンプリング / インスタンスベース政策 / 多目的最適化 / ハイブリッドGA / 政策形成 / 大域的最適化 / パレート降下法 / 遺伝的アルゴリズム / Actor-Critic / 政策学習 / 政策勾配法 / 確率的傾斜法

【研究成果の概要】

重点サンプリングの考え方をベースに、進化計算と強化学習の高速化を図るとともに、両者の相補性に着目し、両者を適切に融合する手法を構築することを目的に研究を行い、以下の成果を得た。
(1)重点サンプリングを用いたGAによる強化学習
強化学習において過去の経験を有効に利用するために重点サンプリングと呼ばれる統計的手法に着目し、大域的最適政策を効率良く求める手法を提案した。重点サンプリングを用いてGAの親集団の経験を再利用することにより、子個体の政策評価を推定する方法を提案し、環境とのインタラクションを削減できることを示した。さらに、子個体の生成に交叉と政策勾配を用いた局所探索を併用することで、多峰性への対応が可能になり、かつ学習が高速化されることを確認した。
(2)ハイブリッドGAによるインスタンスベース政策学習
インスタンスの集合で強化学習の政策を表現し、GAによって最適化する直接探索法を提案した。インスタンスは連続状態・連続行動の対で表される。インスタンスベース政策の最適化には組み合わせ最適化と関数最適化の側面があることに着目し、インスタンス集合を最適化するための2項分布交叉BDX、インスタンスのパラメータを最適化するための突然変異交叉INDX、およびこれらを統合したハイブリッドGAを提案し、並列二重倒立振子振り上げ安定化問題などで妥当性と有効性を確認した。
(3)多目的関数最適化のためのパレート降下法とその応用
多目的関数最適化問題の解概念であるパレート解は一般に集合をなす。集団で解を探索するGAはパレート解集合の近似解集合を一度の探索で求める点で効率的であるが、探索終盤に進化的停滞が生じ、精度において問題がある。本研究では、多目的GAが探索終盤で進化的停滞を生じる原因を解明し、高精度の解を得るためには局所探索の導入が必要不可欠であることを指摘し、高性能な局所探索法としてパレート降下法を提案した。さらに、多目的GAによる探索の後でパレート降下法を適用するGA then LSの枠組みが推奨されることを性能比較実験により示した。

【研究種目】基盤研究(B)

【研究期間】2004 - 2006

【配分額】15,000千円 (直接経費: 15,000千円)

【研究分野】知能情報学

【研究領域課題番号】15700135 (KAKENデータベースで見る）

【研究キーワード】

遺伝的アルゴリズム / 実数値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とその並列化に関する研究成果に関する論文の投稿へ向けて準備中である.

【研究種目】若手研究(B)

【研究期間】2003 - 2004

【配分額】3,400千円 (直接経費: 3,400千円)

【研究分野】知能情報学

【研究領域課題番号】13780287 (KAKENデータベースで見る）

【研究キーワード】

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

【研究成果の概要】

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

【研究種目】若手研究(B)

【研究期間】2001 - 2002

【配分額】2,000千円 (直接経費: 2,000千円)

【研究分野】知能情報学

【研究領域課題番号】13480089 (KAKENデータベースで見る）

【研究キーワード】

進化計算 / 実数値GA / UV構造 / k-tablet構造 / 強化学習 / Actor-Critic / 4足歩行ロボット / 分散強化学習 / α-domination戦略 / Profit Sharing / 粉末X線解析 / 蛋白質構造決定 / UV構造仮説 / actor-critic / マルチエージェントシステム / 進化システム / 遺伝的アルゴリズム / 多目的GA / 適応システム / マルチエージェント強化学習 / 報酬共有の合理性

【研究成果の概要】

1.進化計算に関する研究成果
(1)非線形性・悪スケール性・多峰性をもった関数最適化問題に対してロバストな実数値GAとして,外挿的交叉EDX,交叉的突然変異ANSを提案した.(2)探索空間に大きな谷が複数存在して各谷に有力な局所解が存在する大域的多峰性下でGAが探索に失敗する現象を説明するUV構造仮説を提唱し,UV現象を回避する世代交代モデルISMを提案した.(3)稜構造に代表される悪スケール構造の一般化であるk-tablet構造に対応できる交叉LUNDX-mを提案した.(4)クラスタリング手法をベースにk-tablet構造を同定する方法を提案した.
2.強化学習に関する研究成果
(1)マルチエージェント強化学習における報酬共有の合理性について理論的に考察し,不合理な挙動を回避するための条件を明らかにした.(2)多数の行動を扱う強化学習の性能向上を図るために,確率的2分木の行動選択を用いたActor-Criticアルゴリズムを提案した.(3)actorの行動選択に正規分布を用いるアルゴリズムを提案し,8次元連続状態・連続行動の4足ロボットの歩行動作獲得問題に適用して,適切な歩行を効率よく学習できることを示した.(4)多段フローシステムを分散強化学習の枠組みで定式化したとき直面する2種類のトレードオフ(利己と利他,制約と性能)を適応的に調整する共有意思決定を提案した.

【研究種目】基盤研究(B)

【研究期間】2001 - 2003

【配分額】13,600千円 (直接経費: 13,600千円)