巡回セールスマン問題を遺伝的アルゴリズムを使ってLabVIEWでプログラミングしてみた

遺伝的アルゴリズムについて興味が湧いてきたので、勉強も兼ねてプログラミングしてみることにしました。
最適化する題材として、とてもポピュラーな巡回セールスマン問題を選びました。

----------------------

セールスマンが複数個所を巡回する際に、どういう経路を通れば最短距離で移動することができるか？という問題です。

プログラミングで総当たりで計算をすればいいのですが、全経路は順列（n!）の数だけありますので、巡回する箇所が増えれば、それだけ求めるのが大変になります。
例えば、
6箇所を巡回するのであれば6!=720通り、
10箇所を巡回するのであれば10!=3,628,800通り、
の経路があります。

左の図では、50箇所をランダムに選んだ順番で巡回しています。
総当たりだと「3.0414093e+64通り」です。
いくらPCでも、これは計算が大変です。

ということで、遺伝的アルゴリズムを使って、効率的に近似解を求めようということです。
右の図は、実際にプログラミングをした結果です。
↓にあるように、1735世代で近似解（距離=1535.79）が求まっています。
----------------------

----------------------

「突然変異のサブvi」です。
※こちらの記事を参考にして、LabVIEWでプログラミングしてみました。

単純な処理なのですが、結構考え込んでしまい、時間が掛かってしまいました。
でも、それがまた楽しくもありました。
プログラミングは楽しい！
----------------------

巡回25箇所での解析の様子（YouTube）です。
----------------------
遺伝的アルゴリズムは、このようにシラミ潰しに探索するような処理を効率的に行うことができます。
品質工学においては、MT法で項目選択（波形解析の際の標本線の最適化）をする際に活用されています。
面白そうなので、他にも応用できないか検討してみたいと思います。