論文#1

移転しました。

解の絶対的評価が可能な問題に対する競合型共進化アルゴリズムの適用


いままで、競合型共進化アルゴリズムは、実問題にはあまり適用されてこなかった。
適用例としては、

  • ソーティングネットワーク設計問題
  • セルオートマトン密度分類問題
  • ゲームプレーヤーの戦略進化

解候補の評価に、解候補自身だけでなくテストデータや他の解候補などを必要とする問題に適用されてきた。
なぜなら、従来の進化アルゴリズムの適用が困難であったから。

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

  1. 表集団が互いに適度な選択圧をかけあうことにより、局所解に陥りにくい
  2. 解候補の解としての良さを正確に評価することが困難な問題において、テストデータや他の解候補と共進化することで、部分的な評価により探索可能となることが挙げられる。


競合型共進化アルゴリズムにおける解候補の評価
→相対的評価

目的関数を用いた解候補の評価
→解候補のみで一意に評価できる絶対的評価

よーするに

競合型共進化アルゴリズムっていうのは、何かと何かをお互いに競合させながら進化させる方法みたい。この場合だと、パラメータkというのがある種のハードルのような存在になっている。そのハードルを越えるものは、適応度が高い、乗り越えられないのものは適応度が低いということになる。しかも、このハードルは進化によってどんどん高くなっていくので、それによって、適応度グラフのより高いところを目指すように進化が進むことになる。だから、局所解に陥りにくいというメリットが出てくる。


現実の問題にも、問題設定によっては局所解が数多く出てくる。その問題設定に、この競合型共進化アルゴリズムを適用することによって、より適切な解が見つかるのでないか?

今後の疑問

実際、現実の問題を定式化するにはどうすればいいのか?どのように遺伝子を定義すればいいのかがまったく見えてこない。