ニューラルネットワークを用いて組合せ最適化問題を解く

　２０１７年１２月１７日に人工知能の学習方法に関するブログを公開した後、いわゆる人工知能ではないが、ニューラルネットワークの様式を用いて組合せ最適化問題が解けることを確認しておこうと考えた。

　巡回セールスマン問題とよばれるものは、組合せ最適化の代表的な例とされている。ｎ個の都市を巡回しながら訪問するとき、多くの巡回経路がある中で、移動距離が最小となる（コストが最小となる）経路を最適解として見つける問題である。

　一般にｎ個の都市を訪問する巡回路の数は（ｎ－１）！個であり、都市間の移動距離が行きと帰りが同じであるから、距離の合計を計算しなければならない巡回路の総数は（ｎ－１）！／２個になる。しかし、ｎが大きくなると、計算時間が爆発的に増加するので、現行の計算機では現実的な時間内では解けないことになる。

　一方、この問題を解くために必要なアルゴリズムは、実行可能な巡回経路の組合せを列挙し、各組合せについて移動距離を集計し、移動距離が最小となる組合せを抽出するというきわめてシンプルなものである。

　そこで、参考文献が紹介するｎが小さい場合の例題について、Ｅｘｃｅｌを用いて計算してみることにした。このとき、計算のための装備としてニューラルネットワーク的な構成手段が扱い易いことに気がついたのである。

　例題は、チューリッヒ（Ｚ）の自宅を出て、ベルリン（Ｂ）、ロンドン（Ｌ）、マドリッド（Ｍ）、ローマ（Ｒ）を可能な順序で巡回し、チューリッヒの自宅に戻るというものである。

　この場合、ｎ＝５であるから、可能な巡回路の数は、４！＝２４であり、計算の必要があるケースの数はその半分の１２である。

　まず、Ｅｘｃｅｌの表上に、都市間の移動距離を設定するためのテーブルを設け、データを入力する。

　次に、可能な巡回路のケースを都市間の経路のシーケンスで表現することにする。一つのケースは、５つの経路のシーケンスとなる。各経路を上記テーブル上のセル番号で表す。このセル番号によって間接的に設定されたデータを参照できるように、＝＄Ｄ＄２のように数式として記述する。このようにして、例えば、Ｉ，Ｋ，Ｍ，．．．，ＡＥ列のように１２ケースの経路シーケンスを各々設定する。

　この経路シーケンスは、ニューラルネットワークへの入力データであるから、各シーケンスに対応して中間層のユニットとなる一つのセル、例えばＩ８、を設ける。このセルに、対応するシーケンスの移動距離を合計する計算式を設定する。例えば、Ｉ列のシーケンスに対応して＝Ｉ２＋Ｉ３＋Ｉ４＋Ｉ５＋Ｉ６を設定するなどである。

　次に、Ｉ列の合計セルの数式をＫ，Ｍ，．．．，ＡＥ列の該当する同行セルに数式コピーする。

　これによって、各経路シーケンスの合計移動距離が計算できるので、最後に、同行セルに空白以外の最小値を求める関数＝ＭＩＮＡ（Ｉ８：ＡＥ８）を設定すれば、移動距離の最小値が求められるから、対応する経路シーケンスが最適解となる。このセルが出力層のユニットに相当する。



　参考文献
　久保幹雄など著「インターネット時代の数学――離散数学と組合せ最適化」（共立出版）