Raspberry Pi スパコン (18)　巡回セールスマン問題

今回から、巡回セールスマン問題に関する並列処理の説明をする。

最適化問題という広大な分野があり、その中に普通の方法では最適解を見つけるのが困難な問題を、生物の進化の仕組みと同じ方法で見つけようというのが進化計算である。環境により適応したものが残り、子孫を生み、進化していったわけである。その中で、特に有名なのが、遺伝的アルゴリズム(G.A. :Genetic Algorithm)という方法である。

しかし、ここで延々と遺伝的アルゴリズムを説明すると、並列処理に至るまでの話が長くなるので、思い切り端折る。遺伝的アルゴリズムに関しては、多数の説明がネット上にあるので、ここでさらに増やす必要もないだろう。

掲載するプログラムも、複数のコンピュータに分散して処理するMPIに関連する部分に限定する。

遺伝的アルゴリズムを適応する課題として、とても有名な巡回セールスマン問題(TSP: Traveling Salesman Problem)を取り上げる。セールスマンが、決まった訪問先を巡回するのに、最短なコースを見つける問題である。

ここでの計算は、次の図のようなことを行う。

基本手順

以下に基本的な手順を示す

1. 訪問個所を決める。外部から与えられることもある。

2. 最初、でたらめな巡回路を作る。１つの巡回路が生物の個体に対応し、指定した個体数分のでたらめな巡回路を作って、個体プールに入れる。

3. 次を、指定世代数だけ繰り返す。

   • 個体プールから適当に選んだ個体（親個体）を元にして、子個体を誕生させ、新しい個体プールに蓄える。これを指定個数になるまで子個体を作りつづける。

   • 個体プールの中から、比較的良い個体を、指定個体数だけ選び、残りの個体は捨てる。

   • １世代前のプールを捨て、新しいプールを個体プールとする。（世代交代処理）

4. プールの中から、もっとも巡回路の短い個体を選び、その経路を取り出す。

これに対応する部分のPythonの関数stepForward()を以下に示す。

これで、n世代だけ進化したときの最短距離のルートが求まる。この中で、１世代分の進化だけを行うのが、self.oneGeneration()である。

    ## 進化を進める
    def stepForward( self, n, pgap ):       	# ( n=世代数、pgap=スナップショットの世代間隔)
    	global  generation, pool, x_gen, y_len

    	generation = 0
    	self.printInfo()                    	# 0世代のプリント
   	 
    	self.snap_gap = pgap
    	for generation in range(1,n+1):             # 第ｎ世代までループする
        		self.oneGeneration()                	# 1世代だけ進める
        		self.best_individual = pool[0]

        	    if generation % 10 == 0:            	# 10世代毎に、進化のグラフ作成のために
            	    x_gen.append(generation)        	  # 世代と
            	    y_len.append(self.getMinLength())   # 巡回路の最短距離　を記録しておく

        	    if generation % self.snap_gap == 0: 	# 指定の世代間隔で
            	    self.printInfo()                	# 個体プールの情報をプリント
                    	 
    	if generation % self.snap_gap != 0:
        		self.printInfo()

１世代の処理の中で子個体を作るのだが、その方法はいろいろ提案されていて、今回は巡回セールスマン問題や遺伝的アルゴリズムの詳細を説明するのが目的ではなく、あくまでも並列処理を説明するための材料としての利用なので、詳細は省き、非常に横着に実装できる、あまり紹介されていない方法のみを紹介するに留める。

交差

多くの解説では、個体プールから２個体を選び、それら２個体を親として、子個体を作る方法を紹介している。

生物の遺伝のように、両親の遺伝情報を組み合わせて子個体を作る場合、巡回セールスマン問題では次に示す不都合が発生する。

A〜Hの８都市の場合の例で、ここでは８都市がほぼ円周上に配置している。
これら８都市を全部めぐる最短ルートは円周に沿って順番にめぐることになるのだが、都市の配置は実際はもっとバラバラである。

めぐる順序を都市の並びの配列(リスト)で示す。
左図の太い青線が巡る順序であり、それを右の対応する配列で示している。
上と下のルートを元に、それら両方の性質を持ったルートを作ろうと考えると、２つの配列を適当な箇所で切断し、２つの配列の切れ端を組み合わせると、下の配列ができあがる。これが、交差という方法であり、遺伝における染色体の交差をモデルにした方法である。

しかし、この配列にはまずい現象が発生している。
都市をめぐる配列なので、すべての都市が１回現れなければいけないのだが、AとDが２回現れ、BとCは消えている。

さて、どうしよう。

遺伝的アルゴリズムの本には、この交差と突然変異の２つの方法を組み合わせるようにと書かれていることが多いのだが、交差で行き詰まってしまった。次回までには何とかしよう。