まだ完成形ではないようですが、面白いと思って紹介させていただきます。
URL:http://mosirobo.blogspot.com/2014/12/blog-post.html
# -+- coding: utf-8 -*-
import random #ランダムモジュール
import math
import copy
import numpy as np
import pylab
import matplotlib.pyplot as plt
import matplotlib.animation as animation
def city_init():
#都市座標(30個）
citylist_x = [2,10,7,32,35,9,28,3,8,5,13,45,63,11,17,34,55,38,41,15,6,53,46,18,23,16,19,27,42,12]
citylist_y = [36,22,47,41,32,24,15,2,25,28,48,5,11,16,27,8,46,35,58,14,26,21,49,34,1,7,19,43,29,39]
return [citylist_x,citylist_y]
##評価関数
def eval_func(gean):
x,y =city_init()
x_cp = list(x)
y_cp = list(y)
## print x
#a,b,c,d,e,f,のうち行った都市は消していく
#c,e,a,f,d,bの順で回る場合は
#[2,3,0,2,1,0]となる
##gean = [2, 3, 1, 1, 0]
##gean = [2,4,1,3,0]
gean_decode = []
geannum = 0
while geannum<=len(gean)-1:
num = x.index(x_cp[gean[geannum]])
gean_decode.append(num)
del x_cp[gean[geannum]]
geannum +=1
#評価の基準は距離が短いことである。
dist_stok = []
geannum = 0
while geannum<=len(gean)-2:
dist = (x[gean_decode[geannum+1]]-x[gean_decode[geannum]])**2 + (y[gean_decode[geannum+1]]-y[gean_decode[geannum]])**2
dist_stok.append(dist)
geannum +=1
alldistance = sum(dist_stok)
last_dist = (x[gean_decode[len(gean)-1]]-x[gean_decode[0]])**2 + (y[gean_decode[len(gean)-1]]-y[gean_decode[0]])**2
alldistance = alldistance + last_dist
## print(alldistance)
return alldistance
def geneticoptimize(maxiter = 100,maximize = False,popsize = 50,popnum = 30,elite = 0.99,mutprob =0.2):
"""
maxiter = 1, 繰り返し数
maximize = False, スコアを最小化する
popsize = 50, 個体数
popnum = 30, 遺伝子数（長さ）都市の数
elite = 0.2, 生き残る遺伝子の割合
mutprob =0.2 突然変異のおこる確立
"""
# 突然変異
def mutate(vec):
i = random.SystemRandom().randint(0,popnum-1)
after_mut = random.randint(0,popnum-i-1)
return vec[:i] + [after_mut]+vec[i+1:]
# 1点交叉 非推奨
def one_point_crossover(r1,r2):
i = random.SystemRandom().randint(1,popnum-2)
return random.SystemRandom().choice((r1[0:i] + r2[i:], r2[0:i] + r1[i:]))
# 2点交叉
def two_point_crossover(r1,r2):
i, j = sorted(random.SystemRandom().sample(range(popnum),2))
return random.SystemRandom().choice((r1[0:i] + r2[i:j] + r1[j:] , r2[0:i] + r1[i:j] + r2[j:]))
# 一様交叉
def uniform_crossover(r1, r2):
q1 = copy.copy(r1)
q2 = copy.copy(r2)
for i in range(len(r1)):
if random.SystemRandom().random() < 0.5:
q1[i], q2[i] = q2[i], q1[i]
return random.SystemRandom().choice([q1,q2])
def anime_flam(gean):
copy_x = list(citylist_x)
copy_y = list(citylist_y)
ordercity_x =[]
ordercity_y =[]
for i in gean[0][1]:
ordercity_x.append(copy_x[i])
ordercity_y.append(copy_y[i])
del copy_x[i],copy_y[i]
return ordercity_x,ordercity_y
#遺伝子の初期化
pop = []
vec = []
for i in range(popsize):
selected_city = 1
while selected_city <= popnum:
vec_vec = random.SystemRandom().randint(0,popnum-selected_city)
vec.append(vec_vec)
selected_city +=1
pop.append(list(vec)) #listはコピーを渡さないと変更元まで変更される
del vec[:]
# 交叉アルゴリズムの選択（2点交差を選択）
crossover = two_point_crossover
#crossover = uniform_crossover
#メインループ
topelite = int(elite * popsize)
score_stoc = []
citylist_x,citylist_y = city_init()
fig = plt.figure(figsize=(8, 5))
ax1=fig.add_subplot(1,2,1)
ax2=fig.add_subplot(1,2,2)
ims = []
im2_pointset =[]
for i in range(maxiter):
scores=[(eval_func(v),v) for v in pop]
scores.sort()
if maximize:
scores.reverse()
ranked = [v for (s,v) in scores]
# 弱い遺伝子は淘汰される
## pop = ranked[0:topelite]
eliminate_cycle = 0
while eliminate_cycle < popsize:
if eliminate_cycle == 0:
pop = ranked[:1]
else:
if random.SystemRandom().random() < elite**eliminate_cycle:
pop.append(ranked[eliminate_cycle])
eliminate_cycle +=1
topelite = len(pop)
# 生き残った遺伝子同士で交叉したり突然変異したり
while len(pop) < popsize:
if random.SystemRandom().random() < mutprob:
# 突然変異
c = random.SystemRandom().randint(0,topelite)
pop.append(mutate(ranked[c]))
if random.SystemRandom().random() < mutprob:
selected_city = 1
while selected_city <= popnum:
vec_vec = random.SystemRandom().randint(0,popnum-selected_city)
vec.append(vec_vec)
selected_city +=1
pop.append(list(vec))
del vec[:]
else:
# 交叉
c1 = random.SystemRandom().randint(0,topelite)
c2 = random.SystemRandom().randint(0,topelite)
pop.append(crossover(ranked[c1],ranked[c2]))
# 暫定の値を出力
score_stoc.append(scores[0][0])
#scores[0]はスコアと遺伝子（トップの）
#scores[0][0]はスコア
#scores[0][1]は遺伝子
x,y = anime_flam(scores)
#ordercityは暫定での訪問順
im, = ax1.plot(x,y,'o-m')
im2, = ax2.plot(score_stoc[0:i],'o-c')
#plotの場合は変数にカンマを付ける
ims.append([im,im2])
ani = animation.ArtistAnimation(fig, ims, interval=1,blit=True, repeat_delay=0)
plt.show()
return scores[0]
def main():
x,y =city_init()
ans = geneticoptimize()
ans_x = []
ans_y = []
print("Ans:",ans)
for i in ans[1]:
ans_x.append(x[i])
ans_y.append(y[i])
del x[i],y[i]
if __name__ == '__main__':
main()
================================================================================
途中で中断してしまったのですが
Ans: (17960, [20, 17, 12, 14, 0, 9, 10, 10, 21, 7, 19, 2, 12, 12, 11, 7, 4, 10, 5, 10, 1, 5, 4, 1, 3, 0, 0, 2, 1, 0])