交差が上手く行かなかったので、交差を利用しないことにしよう。
巡回セールスマン問題で、ちゃんと交差を利用して行う方法は存在する(ネット上にも解説があるはず)のだが、説明するとちょっと長くなりそうで面倒なので省略する。プログラマの最大の美徳は怠惰なので、この場合、交差をやめてしまうのは妥当だろう。
突然変異
進化計算は、交差と突然変異で行うのだが、突然変異の方法も色々考えられる。
ここでは、次図に示す方法で都市の並びを入れ替えることにした。
１つの個体（都市の並びの配列）を取り出し、部分配列（空色部分）を適当に指定して、この範囲の並びを、逆順に並べただけである。
左側に、巡路がどう変わったかを示している。配列上の隣接は、都市間の道を示すことになり、上図の場合、DーCがDーFに、EーFがEーCに変わっただけである。
別の言い方をすれば、部分的に逆順にしたことは、経路をひねった（あるいはひねりを取り除いた）ことになる。
なお、実際には配列ではなく、リストで実装してある。
このような処理も、一種の突然変異である。そして、新しい個体の元になった親は１つだけである。
これを以下のようにコーディングしてみた。
## 指定された個体の内容を、突然変異の染色体にする
def setMutationIndividual( self ):
global generation, ga
idv = ga.selectRandomfromPool() # 親
self.born_generation = generation # 誕生世代を記録
x0 = int(random.randrange(path_length))
x1 = int(random.randrange(path_length))
if x0 > x1:
x0,x1 = x1,x0ts
self.journey = copy.copy(idv.journey)
rev = idv.journey[x0:x1]
rev.reverse()
self.journey[x0:x1] = rev
self.setDistance( self.journey )ウイルスに学ぼう
全世界がコロナウイルスに翻弄されたわけだが、ウイルスの遺伝情報は非常に変わりやすく、次々と別種のウイルスを作って人間の対策をかいくぐった訳である。
通常のDNAによる遺伝の場合、２つの親の遺伝情報から子の遺伝情報を作り上げるのだが、ウイルスはRNAしか持っておらず、それをいろいろな方法で変更して進化するのであった。
だから、ここでは、ウイルスを真似て、１つの親から適当に情報を変更して子を作ったのである。
１世代の処理
１世代分の処理は、以下のようになっている。
## 1世代分の処理
def oneGeneration(self):
global pool, pool_size
nextpool = pool
for i in range(pool_size): ## 突然変異
k = 0
while True:
newidv = Individual()
newidv.setMutationIndividual()
if not self.findSameLength( nextpool, newidv ):
break
nextpool.append(newidv)
pool = nextpool
self.sortPool()
pool = pool[:pool_size]Individual()で個体を生成し、setMutationIndividual()の中で適当な親個体を元に突然変異個体を作成している。つまり、親個体の巡路の一部を逆順にした巡路を持たせる処理をしている。
新しい突然変異個体を、元の個体と同じ数だけ作り、プール内の新旧ごちゃまぜの個体をソーティングして、元のプールサイズだけ残している。つまり、距離の短い順にならべて、上位半分だけを残している。
その他については、あまり本質的なことはないので、省略する。
巡回セールスマン問題・遺伝的アルゴリズムについては、大量の情報がネット上に溢れているので、探して勉強しよう。
実行
プログラム TSP_Twist_MPI.py を引数なしで実行すると、引数の形式を示す。
pi@RP0:/beta/TSP/Twist $ python3 TSP_Twist.py
usage: python3 TSP_Twist.py 都市数 個体数 世代数 表示間隔
pi@RP0:/beta/TSP/Twist $都市数=100, 個体数=100, 世代数=1000, 表示間隔=100 として実行してみた。
pi@RP0:/beta/TSP/Twist $ python3 TSP_Twist.py 100 100 1000 100
G:0 len=20041.209 ave=22113.650
G:100 len=8593.999 ave=8925.084
G:200 len=6529.089 ave=6742.948
G:300 len=5528.650 ave=5755.334
G:400 len=4984.056 ave=5113.132
G:500 len=4865.126 ave=4932.015
G:600 len=4677.533 ave=4760.629
G:700 len=4485.826 ave=4578.021
G:800 len=4397.176 ave=4481.990
G:900 len=4363.987 ave=4416.083
G:1000 len=4262.800 ave=4326.002
pi@RP0:/beta/TSP/Twist $lenが、その世代の個体の中での最短距離を示し、aveがプール内の全個体の平均距離を示す。
縦横400の正方形内に100点をランダムに打ち、この全点を巡回する最短の巡路を求める。
走らす毎に異なる位置に点を打たれると比較検討に困るので、点を決めるとき、乱数の初期化を固定で指定する。
1000世代の実行が終わると、最短距離がどのように減っていったかをグラフで示す。また、そのときの経路も示す。
グラフから、世代数と共に、最短距離が短くなっていることがわかる。1000世代ではまだ進化の途中であることも読み取れよう。線が交わっている場合は、より短くすることができる（証明略）。
さて、1000世代では、進化を早く切り上げ過ぎたようなので、10000世代まで進化させてみた。
pi@RP0:/beta/TSP/Twist $ python3 TSP_Twist.py 100 100 10000 100
G:0 len=20041.209 ave=22113.650
G:100 len=8428.298 ave=8808.898
G:200 len=6451.194 ave=6590.301
G:9800 len=4010.862 ave=4018.644
G:9900 len=4010.862 ave=4018.644
G:10000 len=4010.862 ave=4018.644
ここで示した図は、いずれもmatplotlib.pyplotで表示したものである。
進化計算・巡回セールスマン問題において、まだまだ考慮すべきことは多数ある。特に、個体の多様性は重要である。多様性に欠けた生物種の場合、病気が蔓延すると全滅してしまうことがある。あまり繁殖していない種でも、病気に強ければ、一気に繁殖が進むこともあるが、ここではこれ以上の説明はしない。
以上で、巡回セールスマン問題を、１台のコンピュータで実行する場合の説明を終える。
巡回セールスマン問題は、点数や個体数を増加すると非常に時間がかかってしまう。ここで示した単純な巡回セールスマン問題の場合、直線距離を求めているだけの簡単なものだが、遺伝的プログラムで最適化を行う場合、個体の評価を行うのに相当の時間がかかることが多く、マルチスレッド化、さらにはマシンの分散化に等により時間を押さえることが行われる。
では、次回から、MPIを利用して、複数のRaspberry Piで処理する方法を示す。
＃人気の記事
＃タグ
