cross gene

更新时间:2022-11-26 05:40:26 阅读: 评论:0


2022年11月26日发(作者:umbrella)

遗传算法解决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小时内删除。

上一篇:lighter
标签:cross gene
相关文章
留言与评论(共有 0 条评论)
   
验证码:
Copyright ©2019-2022 Comsenz Inc.Powered by © 专利检索| 网站地图