旅行商问题
-
2023年2月26日发(作者：替考拉宁)遗传算法——解决M-TSP多旅⾏商问题（基于python基本实现）
具体的遗传算法详解请看上⼀篇
导读
MTSP_GAMultipleTravelingSalesmenProblem(M-TSP)GeneticAlgorithm(GA).Findsa(near)optimalsolutiontothe
M-TSPbysettingupaGAtosearchfortheshortestroute(leastdistanceneededforthesalesmentotraveltoeach
cityexactlyonceandreturntotheirstartinglocations)
⽬录
初始化城市
defxy():
li=[]
foriinrange(30):
x=t(10,4000)
y=t(10,4000)
(([x,y]))
li=(li)
#(
#[[100,200],[234,1245],[423,124],[123,974],[578,294],[1000,500],[492,2100],[320,418],[836,914]])
returnli
计算城市间距离矩阵
defD(location1,location2):
(pow(location1[0]-location2[0],2)+pow(location1[1]-location2[1],2))
defDMAT(locations):
length=len(locations)
distance=([length,length])
#print()
foriinrange(length):
forjinrange(length):
distance[i,j]=D(locations[i],locations[j])
returndistance
初始化种群
definit_population(length,num):
li=list(range(length))
print(li)
population=[]
foriinrange(num):
e(li)
(py(li))
returnpopulation
适应度计算
defaimFunction(entity,DMAT,break_points):
"""
⽬标函数
:paramentity:个体
:paramDMAT:距离矩阵
:parambreak_points:切断点
:return:
"""
distance=0
break_(0,0)
break_(len(entity))
routes=[]
foriinrange(len(break_points)-1):
(entity[break_points[i]:break_points[i+1]])
#print(routes)
forrouteinroutes:
(route[0])
foriinrange(len(route)-1):
distance+=DMAT[route[i],route[i+1]]
return1.0/distance
deffitness(population,DMAT,break_points,aimFunction):
"""
适应度
:parampopulation:种群
:paramDMAT:距离矩阵
:parambreak_points:切断点
:paramaimFunction:⽬标函数
:return:
"""
value=[]
foriinrange(len(population)):
(aimFunction(population[i],DMAT,py(break_points)))
#weedoutnegativevalue
ifvalue[i]<0:
value[i]=0
returnvalue
选择（物竞天择）
defselection(population,value):
#轮盘赌选择
fitness_sum=[]
foriinrange(len(value)):
ifi==0:
fitness_(value[i])
else:
fitness_(fitness_sum[i-1]+value[i])
foriinrange(len(fitness_sum)):
fitness_sum[i]/=sum(value)
#selectnewpopulation
population_new=[]
foriinrange(len(value)):
rand=m(0,1)
forjinrange(len(value)):
ifj==0:
if0 population_(population[j]) else: iffitness_sum[j-1] population_(population[j]) returnpopulation_new 交叉 defamend(entity,low,high): """ 修正个体 :paramentity:个体 :paramlow:交叉点最低处 :paramhigh:交叉点最⾼处 :return: """ length=len(entity) cross_gene=entity[low:high]#交叉基因 not_in_cross=[]#应交叉基因 raw=entity[0:low]+entity[high:]#⾮交叉基因 foriinrange(length): ifnotiincross_gene: not_in_(i) error_index=[] foriinrange(len(raw)): ifraw[i]innot_in_cross: not_in_(raw[i]) else: error_(i) foriinrange(len(error_index)): raw[error_index[i]]=not_in_cross[i] entity=raw[0:low]+cross_gene+raw[low:] returnentity defcrossover(population_new,pc): """ 交叉 :parampopulation_new:种群 :parampopulation_new:种群 :parampc:交叉概率 :return: """ half=int(len(population_new)/2) father=population_new[:half] mother=population_new[half:] e(father) e(mother) offspring=[] foriinrange(half): m(0,1)<=pc: #cut1=t(0,len(population_new[0])) #ifcut1>len(father[i])-5: #cut2=cut1-5 #else: #cut2=cut1+5 cut1=0 cut2=t(0,len(population_new[0])) ifcut1>cut2: cut1,cut2=cut2,cut1 ifcut1==cut2: son=father[i] daughter=mother[i] else: son=father[i][0:cut1]+mother[i][cut1:cut2]+father[i][cut2:] son=amend(son,cut1,cut2) daughter=mother[i][0:cut1]+father[i][cut1:cut2]+mother[i][cut2:] daughter=amend(daughter,cut1,cut2) else: son=father[i] daughter=mother[i] (son) (daughter) returnoffspring 变异 defmutation(offspring,pm): foriinrange(len(offspring)): m(0,1)<=pm: position1=t(0,len(offspring[i])) position2=t(0,len(offspring[i])) #print(offspring[i]) offspring[i][position1],offspring[i][position2]=offspring[i][position2],offspring[i][position1] #print(offspring[i]) returnoffspring 主逻辑代码 importnumpyasnp frommatplotlibimportpyplotasplt importmath importcopy importrandom defshow_population(population): #x=[i/100foriinrange(900)] x=[i/100foriinrange(-450,450)] y=[0foriinrange(900)] foriinrange(900): y[i]=aimFunction(x[i]) population_10=[decode(p)forpinpopulation] population_10=[decode(p)forpinpopulation] y_population=[aimFunction(p)forpinpopulation_10] (x,y) (population_10,y_population,'ro') () if__name__=='__main__': #x=[i/100foriinrange(900)] #y=[0foriinrange(900)] locations=xy() DMAT=DMAT(locations) break_points=[6,10,16,26] population=init_population(len(locations),90) t=[] foriinrange(4001): #selection value=fitness(population,DMAT,break_points,aimFunction) population_new=selection(population,value) #crossover offspring=crossover(population_new,0.65) #mutation population=mutation(offspring,0.02) #ifi%1==0: #show_population(population) result=[] forjinrange(len(population)): (1.0/aimFunction(population[j],DMAT,py(break_points))) (min(result)) ifi%400==0: min_entity=population[(min(result))] r(locations[:,0],locations[:,1]) routes=[] break_points_plt=py(break_points) break_points_(0,0) break_points_(len(min_entity)) foriinrange(len(break_points_plt)-1): (min_entity[break_points_plt[i]:break_points_plt[i+1]]) forrouteinroutes: (route[0]) forrouteinroutes: x=locations[route,0] y=locations[route,1] (x,y) () #print(min(result)) print(t) (t) #e(max(y),linewidth=1,color='r') ()