本日第2論文読了
- 作者: W. D. Hamilton,Mark Ridley
- 出版社/メーカー: OUP Oxford
- 発売日: 2006/01/12
- メディア: ペーパーバック
- クリック: 34回
- この商品を含むブログ (40件) を見る
Both Wrightian and 'Parasite' Peak Shifts Enhance Genetic Algorithm Performance in the Traveling Salesman Probles
Brian H. Sumida and William D. Hamilton 1994
引き続き遺伝的アルゴリズムの論文.前回の論文がGAにデームストラクチャーを導入して適応地形の谷を越えさせようとしたものに対して本論文はデーム構造に加えてパラサイトを導入して,さらに谷を越えやすくさせようというもの.
応用例はNP困難問題として知られる巡回セールスマン問題.これはサブ構造の道順をどう組み込むかが全体の戦略に大きく関わることから典型的に複数ピーク適応地形問題となる.
前置きの後モデルの説明があるのだが,ここがはしょってあってどうもよくわからない.特に対立遺伝子に何をおくかとか,パラサイトが入ってきた場合にどのような相互作用があって,その結果パラサイトの適応度とホストの適応度をどうはじくのかということがよくわからない.
直感的には大体わかるので読み進めるのに支障はないがここは不満の残るところ.
ホストが局所的な解に止まった場合にデーム内でユニフォーム化することからパラサイトがそのユニフォーム構造に適応して収奪する.すると局所解のホストの適応度が下がって谷に向かう変異体に有利となる
論文の結論としては遺伝的アルゴリズム方を複数ピークのある問題に適用する際にはデーム構造とともにパラサイトを組み込むと谷をわたりやすくすることができるというもの.
やはり今日的にはこういうものはシミュレーションを動的にプレゼンしてもらわないと満足できない気持ちがします.特に問題が純粋に数学的な問題なのでなおさらそう.