TSPをGAで解いてみようという話
TSP(Traveling Salesman Problem)とは
・日本語で「巡回セールスマン問題」
・N個の都市と都市間の距離が与えられ，それぞれの都市を一回訪れ最初の都市に帰ってきたときの移動距離を最小化する問題
・全巡回経路を列挙して距離を計算して...とやっていると人生が終わってしまう(たしかそこらのpcだと13都市が限界)
wikipedia:巡回セールスマン問題
GA(Genetic Algorithm)とは
・日本語で「遺伝的アルゴリズム」
・解の候補を遺伝子に見立てて操作する手法で，ナップサック問題であればあるものを入れるときは"1"入れない時は"0"としてこれらの組み合わせで解を探す．TSPでは都市に通し番号(激ウマギャグ)をつけて(0,1,...,N)これらの順列を考えることで探索をする．
・あくまで近似解が得られるアルゴリズム
wikipedia:遺伝的アルゴリズム
GAの手順
1．初期化(現世代，次世代)
while(指定回数 or (最適解-近似解)<閾値 or 時間)
2．現世代を評価，近似解を更新
3．現世代から次世代を作成
4．次世代を現世代に代入
5.出力
・現世代から次世代を作成する方法は選択(淘汰)や親それぞれから遺伝子(経路)を引き継ぐ"交叉"，突然変異がある
今回の形式
・ファイルから都市の個数とそれぞれの距離を入力する
・評価の方法
-単純に巡回距離
・選択の方法(未定)
・交叉の方法(未定)
・GAの終了条件(未定)
コード
※ファイル入力からグラフ作成，ランダムで現世代を作成，現世代の評価とsortまで実装済み
github.com
※追記：全列挙探索のソース書きました
おわりに
・これから頑張っていきます
