启发式寻解
附件
【码】遗传算法求解TSP.py
作者 : 老饼 日期 : 2022-09-14 19:24:27 更新 : 2022-09-14 19:26:03


遗传算法求解TSP(python)

# -*- coding: utf-8 -*-
"""
遗传算法求解TSP旅行商问题
"""
import numpy as np
import matplotlib.pyplot as plt
import time
global cityLoc 
cityLoc = np.array([[3.64,2.68 ]  #beijing
,[4.18,1.76 ]  #shanghai
,[3.71,2.60 ]  #tianjin
,[1.33,3.30 ]  #wulumuqi
,[4.20,2.96 ]  #shenyang
,[3.92,1.82 ]  #nanjing
,[2.55,1.64 ]  #chengdu
,[2.37,1.02 ]  #kunming
,[3.43,2.09 ]  #zhengzhou
,[3.54,0.70 ]  #xianggang
,[3.51,1.62 ]  #wuhan
,[3.44,0.80 ]  #guangzhou
,[3.24,2.77 ]  #huhehaote
,[2.38,2.32 ]  #xiling
,[2.56,2.24 ]  #lanzhou
,[3.01,2.03 ]  #xian
,[2.79,2.51 ]  #yinchuan
,[4.03,1.16 ]  #fuzhou
,[3.47,0.70 ]  #aomen
,[1.30,1.69]]); #lasha
cityN= cityLoc.shape[0]

#------------目标函数值计算方法------------------------------------------
def calF(x):
   loc = cityLoc[x] 
   E = np.sqrt(((loc[1:]-loc[0:-1])*(loc[1:]-loc[0:-1])).sum(1)).sum()
   E = E+np.sqrt(((loc[0]-loc[-1])*(loc[0]-loc[-1])).sum()) 
   return E

#------------获取种群中目标函数值最好的一个-------------------------------
def getBest(xg):
     F_list = np.array([calF(cur_x)  for cur_x in xg ])
     best_index =np.argmin(F_list)
     x = xg[best_index].copy()
     F = F_list[best_index]
     return x,F
 
#------------计算种群进入下一代的概率轮盘-------------------------------
def getPPan(xg):
    acp_list = np.array([ 10/(calF(cur_x)+1) for cur_x in xg ])
    PPan = (acp_list/acp_list.sum()).cumsum()
    return PPan

#------------染色体交换-------------------------------    
def exPart(xg):
     [m,n]= xg.shape
     ex_list = np.random.choice(np.arange(m), size=m, replace=False)
     for i in range(0,m,2):
         ex_part = np.random.choice(np.arange(n), size=2, replace=False)
         a = xg[ex_list[i]]
         b= xg[ex_list[i+1]]
         a_piece = a[ex_part.min():ex_part.max()+1].copy()
         b_piece = b[np.in1d(b, a_piece)].copy()
         a[ex_part.min():ex_part.max()+1]=b_piece
         b[np.in1d(b, a_piece)]=a_piece
         
#------------基因变异-------------------------------
def genVar(xg,var_rate):
    [m,n]= xg.shape
    for i in range(m):
        if(np.random.rand()<var_rate):
            flip_part = np.random.choice(np.arange(n), size=2, replace=False)
            flip_piece = xg[i,flip_part.min():flip_part.max()+1]
            xg[i,flip_part.min():flip_part.max()+1]=np.flip(flip_piece)
            
            
#------------生子下代种群-------------------------------
def genChildGroup(xg,PPan,best_x):
    [m,n]= xg.shape
    child_xg=np.zeros(xg.shape,dtype=int)   
    child_xg[0]=best_x.copy()
    for i in range(1,m):
        select_idx = (np.argwhere(PPan>np.random.rand())).min()
        child_xg[i]=xg[select_idx].copy()
    return child_xg


#----------------迭代主流程-------------------------------------------
#----------------参数初始化-----------------------
m = 30    #种群规模
t = 5000  #迭代次数
var_rate = 0.2   #变异概率

#--------------初始化种群-------------------------
xg=np.zeros([m,cityN],dtype=int)
for i in range(m):       
    xg[i] = np.random.choice(np.arange(cityN), size=cityN, replace=False)

h_best_x = xg[0]           # 初始化历史最优个体
h_best_F = calF(h_best_x)  # 初始化历史最优个体的目标函数值

F_list=np.array([])               # 每代最优函数值记录列表
for i in range(t):
    exPart(xg)                    # 交换染色体
    genVar(xg,var_rate)           # 基因变异
    best_x,best_F =  getBest(xg)  # 获取本代最佳个体
    
    if(best_F<h_best_F):          # 更新历史最优个体
        h_best_F= best_F
        h_best_x = best_x

    print("第"+str(i)+"代:最优F="+str(best_F))
    
    F_list = np.append(F_list,best_F)    # 记录历代最优个体
    
    # 退出条件:近10代最优个体变化不大,则退出
    last_F = F_list[max(0,F_list.shape[0]-10):]   
    if((i>10) & ((last_F.max()-last_F.min())/last_F.mean()<0.001)):
        break
    
    #-------------赌轮盘生成下一代-----------------------------------------
    PPan = getPPan(xg)
    xg = genChildGroup(xg,PPan,h_best_x)
    
    #------------------画图------------------------------------
    plt.clf()
    plt.plot(cityLoc[h_best_x,0],cityLoc[h_best_x,1],  color='r', marker='o', markerfacecolor='r', markersize=5)
    plt.scatter(cityLoc[:,0],cityLoc[:,1], marker='o', color='none',edgecolors='b',s=60)
    plt.draw() 
    plt.pause(0.01)

# 打印最终结果(历史最优)
print("h_best_F=",h_best_F)
print("h_best_x=",h_best_x)




联系小饼