遗传算法解决TSP(34个省会城市)问题
本代码可以完善的功能有1、选择算⼦⽅⾯,轮盘赌误差⽐较⼤,可以采取最优保存和排序选择策略。2、交叉和突变算⼦⽅⾯可以采取其
他⽅法3、绘图⽅⾯只是简单的描点连线
importrandom
importmath
frommathimportradians,cos,sin,asin,sqrt
asplt
#计算两省会城市之间的距离x经度y维度
defDistance(x1,y1,x2,y2):
x1,y1,x2,y2=map(radians,[x1,y1,x2,y2])
disx=x1-x2
disy=y1-y2
a=sin(disy/2)**2+cos(y1)*cos(y2)*sin(disx/2)**2
dis=2*asin(sqrt(a))*6371
returndis
SCORE_NONE=-1
#单个城市个体信息
classLife(object):
def__init__(lf,aGene=None):
=aGene
=SCORE_NONE
#遗传算法
classGA(object):
def__init__(lf,aCrossRate,aMutationRate,aLifeCount,aGeneLength,aMatchFun):
#交叉概率
ate=aCrossRate
#突变概率
onrate=aMutationRate
#种群⼤⼩
unt=aLifeCount
#基因长度
ngth=aGeneLength
#适应度函数
un=aMatchFun
#种群数组
=[]
#最优个体选择
=None
#代数
tion=1
#交叉计数
ount=0
#变异计数
oncount=0
#适应度之和判定选择概率
=0.0
#适应度平均值
=1.0
pulation()
#初始化种群
definitPopulation(lf):
=[]
#对序列随机排序
foriinrange(unt):
gene=[xforxinrange(ngth)]
e(gene)
life=Life(gene)
(life)
#适应度函数
defjudge(lf):
#计算每⼀个个体的适应度
=0.0
=[0]
:
=un(life)
+=
<:
=life
=/unt
#交叉算⼦
defcross(lf,dad,mom):
n=0
while1:
newGene=[]
#⽣成交叉范围
index1=t(0,ngth-1)
index2=t(index1,ngth-1)
tempGene=[index1:index2]
#交叉
p1len=0
:
ifp1len==index1:
(tempGene)
p1len+=1
ifgnotintempGene:
(g)
p1len+=1
if(un(Life(newGene))>max(un(dad),un(mom))):
ount+=1
returnnewGene
if(n>100):
ount+=1
returnnewGene
n+=1
#突变算⼦
defmutation(lf,wang):
#产⽣新的基因序列
index1=t(0,ngth-1)
index2=t(0,ngth-1)
newGene=[:]
newGene[index1],newGene[index2]=newGene[index2],newGene[index1]
un(Life(newGene))>un(wang):
oncount+=1
returnnewGene
el:
rate=()
ifrate<(-10/(tion)):
oncount+=1
returnnewGene
#选择某个体
defchoo(lf):
#随机采样
r=m(0,)
#轮盘赌⽅法
:
r-=
ifr<=0:
returnlife
raiException("选择错误",)
#产⽣后代
defchild(lf):
dad=()
#概率交叉
rate=()
ifrate
mom=()
gene=(dad,mom)
el:
gene=
#概率突变
rate=()
ifrate
gene=on(Life(gene))
returnLife(gene)
#产⽣下⼀代
defnext(lf):
()
newLives=[]
#把最好的加⼊下⼀代
()
whilelen(newLives)
(())
=newLives
tion+=1
#TSP类
classTSP(object):
def__init__(lf,aLifeCount=100):
tys()
unt=aLifeCount
=GA(aCrossRate=CROSSRATE,
aMutationRate=MUTATIONRATE,
aLifeCount=unt,
aGeneLength=len(),
aMatchFun=un())
#省会城市经纬度
definitCitys(lf):
=[]
((116.46,39.92))
((117.2,39.13))
((121.48,31.22))
((106.54,29.59))
((91.11,29.97))
((87.68,43.77))
((106.27,38.47))
((111.65,40.82))
((108.33,22.84))
((126.63,45.75))
((125.35,43.88))
((125.35,43.88))
((123.38,41.8))
((114.48,38.03))
((112.53,37.87))
((101.74,36.56))
((117,36.65))
((113.65,34.76))
((118.78,32.04))
((117.27,31.86))
((120.19,30.26))
((119.3,26.08))
((115.89,28.68))
((113,28.21))
((114.31,30.52))
((113.23,23.16))
((121.5,25.05))
((110.35,20.02))
((103.73,36.03))
((108.95,34.27))
((104.06,30.67))
((106.71,26.57))
((102.73,25.04))
((114.1,22.2))
((113.33,22.13))
#计算总⾥程
defdistance(lf,order):
distance=0.0
foriinrange(-1,len()-1):
index1,index2=order[i],order[i+1]
city1,city2=[index1],[index2]
distance+=Distance(city1[0],city1[1],city2[0],city2[1])
returndistance
#适应度函数距离的倒数
defmatchFun(lf):
returnlambdalife:1.0/ce()
#主函数
defmain(lf,n=0):
whilen>0:
()
distance=ce()
#输出当前代数和路径长度
print(("Generation:%4dttDistance:%f")%(tion-1,distance))
#输出最佳路径
([0])
print("Path:",)
()
n-=1
#绘图
defdraw(bestPath,cities):
ax=t(111,aspect='equal')
x=[]
y=[]
foriinrange(-1,len(cities)-1):
index=bestPath[i]
city=cities[index]
(city[0])
(city[1])
(x[0])
(y[0])
(x,y)
(x,y)
()
#主函数
if__name__=='__main__':
#迭代次数
num=input("请输⼊迭代次数:")
num=int(num)
#交叉与突变概率
globalCROSSRATE
globalMUTATIONRATE
CROSSRATE=input("请输⼊交叉概率:")
CROSSRATE=float(CROSSRATE)
MUTATIONRATE=input("请输⼊突变概率:")
MUTATIONRATE=float(MUTATIONRATE)
#初始序列
bp=[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33]
tsp=TSP()
print("初始路径长度:",ce(bp))
(num)
draw(,)
本文发布于:2022-11-26 05:40:26,感谢您对本站的认可!
本文链接:http://www.wtabcd.cn/fanwen/fan/90/23198.html
版权声明:本站内容均来自互联网,仅供演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,我们将在24小时内删除。
留言与评论(共有 0 条评论) |