柿食えば 屁をしても一人

電気系の学生のブログ。何を書くかも決めていない

GAで巡回セールスマン(TSP)を解く【神饌コード】

こんにちは

ToMです。昨日は寒く、今日はなかなかに暑いという体調を崩しがちな天気ですが皆さんいかがお過ごしでしょうか。 僕はLab.に出勤して趣味コーディング中です。

TSP using GAについて

初音ミク2017誕生祭神饌コード企画で書いていた、GAでTSPを解くプログラムが形になりました。

github.com 初音ミクさんへの言葉が.mdにかかれていますので、それを読んでから使って下さい

SVGで作った、Viewerが内蔵されていますので、進化の過程を見ることができます。 デフォルトではTSPのデータを格納しているサイト*1カタール194というデータセットを使用しています。 何セットかdebug用に落としたデータセットがあるので参照元を書き換えれば動きます。 データセットを公開してくださっているウォータールー大学の担当者様に感謝します。

今後の更新予定

  • 世代数ごとの評価値をcsvで出力する。
  • 進化が遅いのでアルゴリズムを見直す。
  • シミュレーションサーバでもう少し早く実行する

追記

  • 2017/09/03 17:22 debug作業をするのに鬱陶しかったので、.htmlをgitから削除してあります。 10分ぐらい走らせれば何件か表示できます。
  • 2017/09/05 13:22 実装の間違い(アルゴリズムの不理解によるもの)があったため鋭意修復中です。億が一、Cloneしてしまった方がいたらごめんなさい!!!