1. SIS Lab
  2. >
  3. Blog
  4. >
  5. Competitive Coevolutionary Algorithms can Solve Function Optimization Problems

Competitive Coevolutionary Algorithms can Solve Function Optimization Problems

更新日:2018.05.09 作成日:2009.05.17

ポイント

共進化

  • 同種・他種間の相互作用によって現れる作用

  • 進化集団を複数用意してその集団中の個体間の相互作用

  • 協調型

  • 競合型 適応度において、一方の増加が他方の減少に繋がる。

競合型共進化アルゴリズム

メリット

  • 両集団が互いに適切な選択圧をかけることで、局所解に陥りにくい。
  • 解の完全な評価が難しい問題に対しても、部分的な評価によって適用可能である。

デメリット(問題点)

  • 勾配の喪失
  • 相対主義
  • 相手集団の弱点へのフォーカシング(過度の特殊化)

研究背景

従来の進化アルゴリズムと比べ,共進化アルゴリズムは適応度評価の方法において異なります. 従来は,個体の情報のみで適応度を決定する適応度評価関数を用いますが, 共進化アルゴリズムは,集団を複数用意し,それら集団中の個体間の相互作用によって適応度を評価します.

相互作用の定義により,協調型と,本研究で取り扱っている競合型とに分類できます.

競合型では,一方の個体の適応度の利益が他方にとって損失に繋がるような相互作用をいいます.共進化アルゴリズムは,相互作用する他個体によって適応度が決まるため,相対的評価といえます. 対して,従来の進化アルゴリズムは,個体に対して適応度がユニークに決まるため,絶対的評価といえます.評価方法が異なるため,競合型共進化アルゴリズムが対象としていた問題も従来とは異なります.それは,解の評価に他の解候補やテストデータなどが必要な問題です.

例えば,・・・ このような問題は絶対的な適応度評価の設計が困難なため,従来の進化アルゴリズムの適用が困難です.競合型共進化アルゴリズムは,例えばアルゴリズムの自動設計においては,テストデータとアルゴリズムの集団を競わせることで適用ができます.実際に,ソーティングネットワーク設計問題において,GAよりも良い解を発見したことが報告されています. このような問題を対象として,競合型共進化アルゴリズムは発展してきました.

研究目的

評価方法が異なることから,それぞれ問題を対象としてきました.従来の進化アルゴリズムは,TSPやナーススケジューリングなど,一般的な最適化問題を主に対象としており,競合型共進化アルゴリズムは,相対的な評価が必要な問題を対象としています.この相対的評価が必要な問題に対して,従来の進化アルゴリズムは適用が困難なため,共進化アルゴリズムの実用化が期待されています. しかし,競合型共進化アルゴリズムは,一般的な最適化問題を対象とした研究はほとんどなされてきませんでした.そこで,本研究では,競合型共進化アルゴリズムの適用範囲の飛躍的拡大を目的とし,適用方法の提案とその評価を行っています.

研究内容

改善策:Stop&Go

Competitive Coevolutionary Algorithms can Solve Function Optimization Problems https://cdn-ak.f.st-hatena.com/images/fotolife/m/meganii/20090517/20090517112611.jpg

仕組み  遅れている世代が追いつくまで、先行する世代の進化を止めるGo:  Stop : 実験1  1-D Function Maximization Problem:この関数は、たくさんの局所解を持っている。 実験2  10-D Rastringin minimization problem:

スポンサーリンク

Related contents

TECH

2009.12.09

あるB4のボロボロな発表を見て一言

TECH

2009.08.02

Stochastic universal sampling

TECH

2009.07.08

gnuplotをループさせる

TECH

2009.06.02

研究室ミーティング090602

TECH

2009.05.29

ミーティング090528

TECH

2009.05.26

ミーティング090526

TECH

2009.05.25

遺伝的アルゴリズム

TECH

2009.05.21

研究室ミーティング090521