手法としてはいろいろあると思うのですが，今回は遺伝的アルゴリズム(GA)と蟻コロニー最適化(ACO)の2つを実装・比較しました．
1.巡回セールスマン問題
よく出される例としてはゴミ収集車の経路でしょうか．ゴミ収集所から出発して，100軒の家を最短で全て回ってゴミ収集所にまた戻ってくるまでの経路を求める話です．
まぁ僕がここで云々説明せずともネット上には沢山関連するサイトが有りますからそちらを参照してください．とりあえずWikipediaと検索したらトップに出てきたサイトのURLを貼っときます．
真ん中のサイトは手法について非常に詳しく解説されている上，Pythonで実装されたソースコードがありますのでそちらもごらんになると良いかと思います．
一番下のサイトは巡回セールスマンについての説明が詳しく，フリーソフトの紹介もされています．
この問題はまだ多項式時間で最適解を解くことができるアルゴリズムが無く，うちの大学でも研究してる研究室がたしかあった気がします．
2.蟻コロニー最適化による実装
蟻コロニー最適化に関する数式は今回全てWikipediaに載っていたものを利用しました（蟻コロニー最適化 - Wikipedia）．
一応『心はプログラムできるか』という本を読んだ時に出てきてまして非常にわかりやすい解説がなされていましたので読んでみると良いかと思います．
以下ソースコード
とりあえず評価のちゃんとした結果は遺伝的アルゴリズムの実装の後に書きます．
3.遺伝的アルゴリズムによる実装
ぶっちゃけ蟻コロニー最適化よりも精度低いです．30個点でさえも蟻コロニー最適化に負けています．1000個ぐらいの点になるともう最適解求めるなんて夢のまた夢でした．原因としては恐らく突然変異がランダムすぎて，ほとんど改悪になるばかりという結果でしょうか．遺伝子は巡回経路の順番を表した変数(5つの点なら[2,4,3,1,0]という配列)です．突然変異で中身を入れ替えてます．
※追記：先日図書館にてほかの人の実装例を見ましたがこれとは異なる手法を用いていました．それを踏まえるとこのプログラムは一般的な実装例とは異なると思われますので注意してください．
ソースコード
4.評価
一応同じデータを用いてやった結果です．30個の[0,1)のランダムな二次元の点について行いました．パラメータはデフォルトです．まずは遺伝的アルゴリズム．
直線が交差してますね．コストは6.056765でした．続いて蟻コロニー最適化．
とりあえず今回の実装では蟻コロニー最適化のほうが早かったですが，遺伝的アルゴリズムも突然変異をもう少し工夫してやればもっと良い結果が出るような気がします．いつか焼きなまし法とかやってみたいです．
0 件のコメント:
コメントを投稿