数学建模

 

模型知识点

优化模型-优化算法-多种启发式算法

 

Wang Haihua

🚅 🚋😜 🚑 🚔

粒子群算法

# -*- coding: utf-8 -*-
"""
粒子群算法求解TSP问题
随机在（0,101）二维平面生成20个点
距离最小化
"""
import math
import random
import pandas as pd
import matplotlib.pyplot as plt
from matplotlib.pylab import mpl
mpl.rcParams['font.sans-serif'] = ['SimHei']  # 添加这条可以让图形显示中文

def calDistance(CityCoordinates):
    ''' 
    计算城市间距离
    输入：CityCoordinates-城市坐标；
    输出：城市间距离矩阵-dis_matrix
    '''
    dis_matrix = pd.DataFrame(data=None,columns=range(len(CityCoordinates)),index=range(len(CityCoordinates)))
    for i in range(len(CityCoordinates)):
        xi,yi = CityCoordinates[i][0],CityCoordinates[i][1]
        for j in range(len(CityCoordinates)):
            xj,yj = CityCoordinates[j][0],CityCoordinates[j][1]
            if (xi==xj) & (yi==yj):
                dis_matrix.iloc[i,j] = round(math.pow(10,10))
            else:
                dis_matrix.iloc[i,j] = round(math.sqrt((xi-xj)**2+(yi-yj)**2),2)
    return dis_matrix  

def calFitness(line,dis_matrix):
    '''
    计算路径距离，即评价函数
    输入：line-路径，dis_matrix-城市间距离矩阵；
    输出：路径距离-dis_sum
    '''
    dis_sum = 0
    dis = 0
    for i in range(len(line)-1):
        dis = dis_matrix.loc[line[i],line[i+1]]#计算距离
        dis_sum = dis_sum+dis
    dis = dis_matrix.loc[line[-1],line[0]]
    dis_sum = dis_sum+dis
    return round(dis_sum,1)

def draw_path(line,CityCoordinates):
    '''
    #画路径图
    输入：line-路径，CityCoordinates-城市坐标；
    输出：路径图
    '''
    x,y= [],[]
    for i in line:
        Coordinate = CityCoordinates[i]
        x.append(Coordinate[0])
        y.append(Coordinate[1])
    x.append(x[0])
    y.append(y[0])
    plt.plot(x, y,'-', color='#4169E1', alpha=0.8, linewidth=0.8)
    plt.xlabel('x')
    plt.ylabel('y')
    plt.show()

def crossover(bird,pLine,gLine,w,c1,c2):
    '''
    采用顺序交叉方式；交叉的parent1为粒子本身，分别以w/(w+c1+c2),c1/(w+c1+c2),c2/(w+c1+c2)
    的概率接受粒子本身逆序、当前最优解、全局最优解作为parent2,只选择其中一个作为parent2；
    输入：bird-粒子,pLine-当前最优解,gLine-全局最优解,w-惯性因子,c1-自我认知因子,c2-社会认知因子；
    输出：交叉后的粒子-croBird；
    '''
    croBird = [None]*len(bird)#初始化
    parent1 = bird#选择parent1
    #选择parent2（轮盘赌操作）
    randNum = random.uniform(0, sum([w,c1,c2]))
    if randNum <= w:
        parent2 = [bird[i] for i in range(len(bird)-1,-1,-1)] # bird的逆序
    elif randNum <= w+c1:
        parent2 = pLine
    else:
        parent2 = gLine
    
    #parent1-> croBird
    start_pos = random.randint(0,len(parent1)-1)
    end_pos = random.randint(0,len(parent1)-1)
    if start_pos>end_pos:
        start_pos,end_pos = end_pos,start_pos
    croBird[start_pos:end_pos+1] = parent1[start_pos:end_pos+1].copy()
    
    # parent2 -> croBird
    list1 = list(range(0,start_pos))
    list2 = list(range(end_pos+1,len(parent2)))
    list_index = list1+list2#croBird从后往前填充
    #j = -1
    for i in list_index:
        for j in range(0,len(parent2)+1):
            if parent2[j] not in croBird:
                croBird[i] = parent2[j]
                break
                    
    return croBird

if __name__ == '__main__':
    #参数
    CityNum = 20#城市数量
    MinCoordinate = 0#二维坐标最小值
    MaxCoordinate = 101#二维坐标最大值
    iterMax = 200#迭代次数
    iterI = 1#当前迭代次数
    
    #PSO参数
    birdNum = 100#粒子数量
    w = 0.2#惯性因子
    c1 = 0.4#自我认知因子
    c2 = 0.4#社会认知因子
    pBest,pLine =0,[]#当前最优值、当前最优解，（自我认知部分）
    gBest,gLine = 0,[]#全局最优值、全局最优解，（社会认知部分）
    
    #随机生成城市数据,城市序号为0,1,2,3...
    # CityCoordinates = [(random.randint(MinCoordinate,MaxCoordinate),random.randint(MinCoordinate,MaxCoordinate)) for i in range(CityNum)]
    CityCoordinates = [(88, 16),(42, 76),(5, 76),(69, 13),(73, 56),(100, 100),(22, 92),(48, 74),(73, 46),(39, 1),(51, 75),(92, 2),(101, 44),(55, 26),(71, 27),(42, 81),(51, 91),(89, 54),(33, 18),(40, 78)]
    dis_matrix = calDistance(CityCoordinates)#计算城市间距离,生成矩阵
    
    birdPop = [random.sample(range(len(CityCoordinates)),len(CityCoordinates)) for i in range(birdNum)]#初始化种群，随机生成
    fits = [calFitness(birdPop[i],dis_matrix) for i in range(birdNum)]#计算种群适应度
    gBest = pBest = min(fits)#全局最优值、当前最优值
    gLine = pLine = birdPop[fits.index(min(fits))]#全局最优解、当前最优解
    
    while iterI <= iterMax:#迭代开始
        for i in range(len(birdPop)):
            birdPop[i] = crossover(birdPop[i],pLine,gLine,w,c1,c2)
            fits[i] = calFitness(birdPop[i],dis_matrix)
        
        pBest,pLine =  min(fits),birdPop[fits.index(min(fits))]
        if min(fits) <= gBest:
            gBest,gLine =  min(fits),birdPop[fits.index(min(fits))]
        
        #print(iterI,gBest)#打印当前代数和最佳适应度值
        iterI += 1#迭代计数加一
    
    print(gLine)#路径顺序
    print(gBest)
    draw_path(gLine,CityCoordinates)#画路径图

[12, 17, 5, 16, 6, 2, 19, 15, 1, 7, 10, 4, 8, 14, 13, 18, 9, 3, 11, 0]
437.1

遗传算法

def calFitness(line,dis_matrix):
    dis_sum = 0
    dis = 0
    for i in range(len(line)):
        if i<len(line)-1:
            dis = dis_matrix.loc[line[i],line[i+1]]#计算距离
            dis_sum = dis_sum+dis
        else:
            dis = dis_matrix.loc[line[i],line[0]]
            dis_sum = dis_sum+dis
    return round(dis_sum,1)

def tournament_select(pops,popsize,fits,tournament_size):
    new_pops,new_fits = [],[]
    while len(new_pops)<len(pops):
        tournament_list = random.sample(range(0,popsize),tournament_size)
        tournament_fit = [fits[i] for i in tournament_list]
        #转化为df方便索引
        tournament_df = pd.DataFrame([tournament_list,tournament_fit]).transpose().sort_values(by=1).reset_index(drop=True)
        #选出获胜者
        fit = tournament_df.iloc[0,1]
        pop = pops[int(tournament_df.iloc[0,0])]
        new_pops.append(pop)
        new_fits.append(fit)
    return new_pops,new_fits

def crossover(popsize,parent1_pops,parent2_pops,pc):
    child_pops = []
    for i in range(popsize):
        #初始化
        child = [None]*len(parent1_pops[i])
        parent1 = parent1_pops[i]
        parent2 = parent2_pops[i]
        if random.random() >= pc:
            child = parent1.copy()#随机生成一个（或者随机保留父代中的一个）
            random.shuffle(child)
        else:
            #parent1
            start_pos = random.randint(0,len(parent1)-1)
            end_pos = random.randint(0,len(parent1)-1)
            if start_pos>end_pos:
                tem_pop = start_pos
                start_pos = end_pos
                end_pos = tem_pop
            child[start_pos:end_pos+1] = parent1[start_pos:end_pos+1].copy()
            # parent2 -> child
            list1 = list(range(end_pos+1,len(parent2)))
            list2 = list(range(0,start_pos))
            list_index = list1+list2
            #j = -1
            for i in list_index:
                for j in range(0,len(parent2)):
                    if parent2[j] not in child:
                        child[i] = parent2[j]
                        break
        child_pops.append(child)
    return child_pops

def mutate(pops,pm):
    pops_mutate = []
    for i in range(len(pops)):
        pop = pops[i].copy()
        #随机多次成对变异
        t = random.randint(1,5)
        count = 0
        while count < t:
            if random.random() < pm: 
                    mut_pos1 = random.randint(0,len(pop)-1)  
                    mut_pos2 = random.randint(0,len(pop)-1)
                    if mut_pos1 != mut_pos2:
                        tem = pop[mut_pos1]
                        pop[mut_pos1] = pop[mut_pos2]
                        pop[mut_pos2] = tem
            pops_mutate.append(pop)
            count +=1
    return pops_mutate

#另一种实现方式
# def mutate(pops,pm):
#     pops_mutate = []
#     for i in range(len(pops)):
#         pop = pops[i].copy()
#         for j in range(len(pop)):
#             if random.random() < pm: 
#                     mut_pos = random.randint(0,len(pop)-1)  
#                     if j != mut_pos:
#                         tem = pop[j]
#                         pop[j] = pop[mut_pos]
#                         pop[mut_pos] = tem
#         pops_mutate.append(pop)
            
#     return pops_mutate

import math
import random
import pandas as pd
import matplotlib.pyplot as plt
from matplotlib.pylab import mpl
mpl.rcParams['font.sans-serif'] = ['SimHei']  # 添加这条可以让图形显示中文

#画路径图
def draw_path(line,CityCoordinates):
    x,y= [],[]
    for i in line:
        Coordinate = CityCoordinates[i]
        x.append(Coordinate[0])
        y.append(Coordinate[1])
    x.append(x[0])
    y.append(y[0])
    plt.plot(x, y,'-', color='#4169E1', alpha=0.8, linewidth=0.8)
    plt.xlabel('x')
    plt.ylabel('y')
    plt.show()
 

   
if __name__ == '__main__':
    #参数
    CityNum = 20#城市数量
    MinCoordinate = 0#二维坐标最小值
    MaxCoordinate = 101#二维坐标最大值
    #GA参数
    generation = 100  #迭代次数
    popsize = 100   #种群大小
    tournament_size = 5 #锦标赛小组大小
    pc = 0.95   #交叉概率
    pm = 0.1    #变异概率

    #随机生成城市数据,城市序号为0,1,2,3...
    CityCoordinates = [(random.randint(MinCoordinate,MaxCoordinate),random.randint(MinCoordinate,MaxCoordinate)) for i in range(CityNum)]
    # CityCoordinates = [(88, 16),(42, 76),(5, 76),(69, 13),(73, 56),(100, 100),(22, 92),(48, 74),(73, 46),(39, 1),(51, 75),(92, 2),(101, 44),(55, 26),(71, 27),(42, 81),(51, 91),(89, 54),(33, 18),(40, 78)]#随机生成的例子
    #计算城市之间的距离
    dis_matrix = pd.DataFrame(data=None,columns=range(len(CityCoordinates)),index=range(len(CityCoordinates)))
    for i in range(len(CityCoordinates)):
        xi,yi = CityCoordinates[i][0],CityCoordinates[i][1]
        for j in range(len(CityCoordinates)):
            xj,yj = CityCoordinates[j][0],CityCoordinates[j][1]
            dis_matrix.iloc[i,j] = round(math.sqrt((xi-xj)**2+(yi-yj)**2),2)
    
    iteration = 0
    #初始化,随机构造
    pops = [random.sample([i for i in list(range(len(CityCoordinates)))],len(CityCoordinates)) for j in range(popsize)]
    
    #计算适应度
    fits = [None]*popsize
    for i in range(popsize):
        fits[i] = calFitness(pops[i],dis_matrix)
    #保留当前最优
    best_fit = min(fits)
    best_pop = pops[fits.index(best_fit)]
    print('初代最优值 %.1f' % (best_fit))
    best_fit_list = []
    best_fit_list.append(best_fit)
    
    while iteration <= generation:
        #锦标赛赛选择
        pop1,fits1 = tournament_select(pops,popsize,fits,tournament_size)
        pop2,fits2 = tournament_select(pops,popsize,fits,tournament_size)
        #交叉
        child_pops = crossover(popsize,pop1,pop2,pc)
        #变异
        child_pops = mutate(child_pops,pm)
        #计算子代适应度
        child_fits = [None]*popsize
        for i in range(popsize):
            child_fits[i] = calFitness(child_pops[i],dis_matrix) 
        #一对一生存者竞争
        for i in range(popsize):
            if fits[i] > child_fits[i]:
                fits[i] = child_fits[i]
                pops[i] = child_pops[i]
        
        if best_fit>min(fits):
            best_fit = min(fits)
            best_pop = pops[fits.index(best_fit)]
        
        best_fit_list.append(best_fit)
        
        #print('第%d代最优值 %.1f' % (iteration, best_fit))
        iteration += 1
    
    #路径顺序
    print(best_pop)
    print(best_fit)
    #路径图
    draw_path(best_pop,CityCoordinates)
    #迭代图
    iters = list(range(len(best_fit_list)))
    plt.plot(iters, best_fit_list, '-', color='#4169E1', alpha=0.8, linewidth=0.8)
    plt.xlabel('迭代次数')
    

#show

初代最优值 899.9
[18, 6, 19, 12, 2, 9, 0, 15, 17, 3, 8, 13, 16, 7, 4, 11, 5, 1, 10, 14]
510.2

禁忌算法

# -*- coding: utf-8 -*-
"""
禁忌搜索算法求解TSP问题
随机在（0,101）二维平面生成20个点
距离最小化
"""
import math
import random
import pandas as pd
import matplotlib.pyplot as plt
from matplotlib.pylab import mpl
mpl.rcParams['font.sans-serif'] = ['SimHei']  # 添加这条可以让图形显示中文

#计算路径距离，即评价函数
def calFitness(line,dis_matrix):
    dis_sum = 0
    dis = 0
    for i in range(len(line)):
        if i<len(line)-1:
            dis = dis_matrix.loc[line[i],line[i+1]]#计算距离
            dis_sum = dis_sum+dis
        else:
            dis = dis_matrix.loc[line[i],line[0]]
            dis_sum = dis_sum+dis
    return round(dis_sum,1)

def traversal_search(line,dis_matrix,tabu_list):
    #邻域随机遍历搜索
    traversal = 0#搜索次数
    traversal_list = []#存储局部搜索生成的解,也充当局部禁忌表
    traversal_value = []#存储局部解对应路径距离
    while traversal <= traversalMax:
        pos1,pos2 = random.randint(0,len(line)-1),random.randint(0,len(line)-1)#交换点
        #复制当前路径，并交换生成新路径
        new_line = line.copy()
        new_line[pos1],new_line[pos2]=new_line[pos2],new_line[pos1]
        new_value = calFitness(new_line,dis_matrix)#当前路径距离
        #新生成路径不在全局禁忌表和局部禁忌表中，为有效搜索，否则继续搜索
        if (new_line not in traversal_list) & (new_line not in tabu_list):
            traversal_list.append(new_line)
            traversal_value.append(new_value)
            traversal += 1
            
    return min(traversal_value),traversal_list[traversal_value.index(min(traversal_value))]

def greedy(CityCoordinates,dis_matrix):
    '''贪婪策略构造初始解'''
    #出来dis_matrix
    dis_matrix = dis_matrix.astype('float64')
    for i in range(len(CityCoordinates)):
        dis_matrix.loc[i,i]=math.pow(10,10)
    line = []#初始化
    now_city = random.randint(0,len(CityCoordinates)-1)#随机生成出发城市
    line.append(now_city)#添加当前城市到路径
    dis_matrix.loc[:,now_city] = math.pow(10,10)#更新距离矩阵，已经过城市不再被取出
    for i in range(len(CityCoordinates)-1):
        next_city = dis_matrix.loc[now_city,:].idxmin()#距离最近的城市
        line.append(next_city)#添加进路径
        dis_matrix.loc[:,next_city] = math.pow(10,10)#更新距离矩阵
        now_city = next_city#更新当前城市
        
    return line
    
   

 
#画路径图
def draw_path(line,CityCoordinates):
    x,y= [],[]
    for i in line:
        Coordinate = CityCoordinates[i]
        x.append(Coordinate[0])
        y.append(Coordinate[1])
    x.append(x[0])
    y.append(y[0])
    
    plt.plot(x, y,'-', color='#4169E1', alpha=0.8, linewidth=0.8)
    plt.xlabel('x')
    plt.ylabel('y')
    plt.show()

if __name__ == '__main__':
    #参数
    CityNum = 20#城市数量
    MinCoordinate = 0#二维坐标最小值
    MaxCoordinate = 101#二维坐标最大值
    
    #TS参数
    tabu_limit = 50 #禁忌长度，该值应小于(CityNum*(CityNum-1)/2）
    iterMax = 200#迭代次数
    traversalMax = 100#每一代局部搜索次数
    
    tabu_list = [] #禁忌表
    tabu_time = [] #禁忌次数
    best_value = math.pow(10,10)#较大的初始值，存储最优解
    best_line = []#存储最优路径
    
    
    #随机生成城市数据,城市序号为0,1，2,3...
    #CityCoordinates = [(random.randint(MinCoordinate,MaxCoordinate),random.randint(MinCoordinate,MaxCoordinate)) for i in range(CityNum)]
    CityCoordinates = [(88, 16),(42, 76),(5, 76),(69, 13),(73, 56),(100, 100),(22, 92),(48, 74),(73, 46),(39, 1),(51, 75),(92, 2),(101, 44),(55, 26),(71, 27),(42, 81),(51, 91),(89, 54),(33, 18),(40, 78)]
    #计算城市之间的距离
    dis_matrix = pd.DataFrame(data=None,columns=range(len(CityCoordinates)),index=range(len(CityCoordinates)))
    for i in range(len(CityCoordinates)):
        xi,yi = CityCoordinates[i][0],CityCoordinates[i][1]
        for j in range(len(CityCoordinates)):
            xj,yj = CityCoordinates[j][0],CityCoordinates[j][1]
            dis_matrix.iloc[i,j] = round(math.sqrt((xi-xj)**2+(yi-yj)**2),2)
    
    # #初始化,随机构造
    # line = list(range(len(CityCoordinates)));random.shuffle(line)
    # value = calFitness(line,dis_matrix)#初始路径距离
    # 贪婪构造
    line = greedy(CityCoordinates,dis_matrix)
    value = calFitness(line,dis_matrix)#初始路径距离
    
    
    #存储当前最优
    best_value,best_line = value,line
    draw_path(best_line,CityCoordinates)
    best_value_list = []
    best_value_list.append(best_value)
    #更新禁忌表
    tabu_list.append(line)
    tabu_time.append(tabu_limit)
    
    itera = 0
    while itera <= iterMax:
        new_value,new_line = traversal_search(line,dis_matrix,tabu_list)
        if new_value < best_value:#优于最优解
            best_value,best_line = new_value,new_line#更新最优解
            best_value_list.append(best_value)
        line,value = new_line,new_value#更新当前解
        
        #更新禁忌表
        tabu_time = [x-1 for x in tabu_time]
        if 0 in tabu_time:
            tabu_list.remove(tabu_list[tabu_time.index(0)])
            tabu_time.remove(0)
        
        tabu_list.append(line)
        tabu_time.append(tabu_limit)
        itera +=1
    
    #路径顺序
    print(best_line)
    #画路径图
    draw_path(best_line,CityCoordinates)
    print(best_value)

# show

[4, 0, 11, 3, 9, 18, 13, 14, 8, 17, 12, 5, 16, 6, 2, 19, 15, 1, 7, 10]

465.6

模拟退火

# -*- coding: utf-8 -*-
"""
模拟退火算法法求解TSP问题
随机在（0,101）二维平面生成20个点
距离最小化
"""
import math
import random
import pandas as pd
import matplotlib.pyplot as plt
from matplotlib.pylab import mpl
mpl.rcParams['font.sans-serif'] = ['SimHei']  # 添加这条可以让图形显示中文

#计算路径距离，即评价函数
def calFitness(line,dis_matrix):
    dis_sum = 0
    dis = 0
    for i in range(len(line)):
        if i<len(line)-1:
            dis = dis_matrix.loc[line[i],line[i+1]]#计算距离
            dis_sum = dis_sum+dis
        else:
            dis = dis_matrix.loc[line[i],line[0]]
            dis_sum = dis_sum+dis
    return round(dis_sum,1)

def traversal_search(line,dis_matrix):
    #随机交换生成100个个体，选择其中表现最好的返回
    i = 0#生成个体计数
    line_value,line_list = [],[]
    while i<=100:
        new_line = line.copy()#复制当前路径
        exchange_max = random.randint(1,5)#随机生成交换次数,城市数量较多时增加随机数上限效果较好
        exchange_time = 0#当前交换次数
        while exchange_time <= exchange_max:
            pos1,pos2 = random.randint(0,len(line)-1),random.randint(0,len(line)-1)#交换点
            new_line[pos1],new_line[pos2]=new_line[pos2],new_line[pos1]#交换生成新路径
            exchange_time += 1#更新交换次数
            
        new_value = calFitness(new_line,dis_matrix)#当前路径距离
        line_list.append(new_line)
        line_value.append(new_value)
        i+=1
        
    return min(line_value),line_list[line_value.index(min(line_value))]#返回表现最好的个体

def greedy(CityCoordinates,dis_matrix):
    '''贪婪策略构造初始解'''
    #转换格式—dis_matrix
    dis_matrix = dis_matrix.astype('float64')
    for i in range(len(CityCoordinates)):
        dis_matrix.loc[i,i]=math.pow(10,10)
    line = []#初始化
    now_city = random.randint(0,len(CityCoordinates)-1)#随机生成出发城市
    line.append(now_city)#添加当前城市到路径
    dis_matrix.loc[:,now_city] = math.pow(10,10)#更新距离矩阵，已经过城市不再被取出
    for i in range(len(CityCoordinates)-1):
        next_city = dis_matrix.loc[now_city,:].idxmin()#距离最近的城市
        line.append(next_city)#添加进路径
        dis_matrix.loc[:,next_city] = math.pow(10,10)#更新距离矩阵
        now_city = next_city#更新当前城市
        
    return line
  

  
    
#画路径图
def draw_path(line,CityCoordinates):
    x,y= [],[]
    for i in line:
        Coordinate = CityCoordinates[i]
        x.append(Coordinate[0])
        y.append(Coordinate[1])
    x.append(x[0])
    y.append(y[0])
    
    plt.plot(x, y,'-', color='#4169E1', alpha=0.8, linewidth=0.8)
    plt.xlabel('x')
    plt.ylabel('y')
    plt.show()

if __name__ == '__main__':
    #参数
    CityNum = 20#城市数量
    MinCoordinate = 0#二维坐标最小值
    MaxCoordinate = 101#二维坐标最大值
    
    #SA参数
    Tend = 0.1#终止温度
    T = 100#初温
    beta = 0.99#退火步长
    
    
    best_value = math.pow(10,10)#较大的初始值，存储最优解
    best_line = []#存储最优路径
    
    #随机生成城市数据,城市序号为0,1，2,3...
    # CityCoordinates = [(random.randint(MinCoordinate,MaxCoordinate),random.randint(MinCoordinate,MaxCoordinate)) for i in range(CityNum)]
    CityCoordinates = [(88, 16),(42, 76),(5, 76),(69, 13),(73, 56),(100, 100),(22, 92),(48, 74),(73, 46),(39, 1),(51, 75),(92, 2),(101, 44),(55, 26),(71, 27),(42, 81),(51, 91),(89, 54),(33, 18),(40, 78)]
   
    #计算城市之间的距离
    dis_matrix = pd.DataFrame(data=None,columns=range(len(CityCoordinates)),index=range(len(CityCoordinates)))
    for i in range(len(CityCoordinates)):
        xi,yi = CityCoordinates[i][0],CityCoordinates[i][1]
        for j in range(len(CityCoordinates)):
            xj,yj = CityCoordinates[j][0],CityCoordinates[j][1]
            dis_matrix.iloc[i,j] = round(math.sqrt((xi-xj)**2+(yi-yj)**2),2)
    
    
    # 随机构造初始解
    # line = list(range(len(CityCoordinates)));random.shuffle(line)
    # value = calFitness(line,dis_matrix)#初始路径距离
    
    # 贪婪构造初始解
    line = greedy(CityCoordinates,dis_matrix)
    value = calFitness(line,dis_matrix)#初始路径距离
    
    
    #存储当前最优
    best_value,best_line = value,line
    draw_path(best_line,CityCoordinates)#初始路径
    
    while T >= Tend:
        new_value,new_line = traversal_search(line,dis_matrix)
        # print(random.random(),math.exp(-(new_value-value)/T))
        
        if new_value <= best_value:#优于最优解
            best_value,best_line = new_value,new_line#更新最优解
            line,value = new_line,new_value#更新当前解
        elif random.random() < math.exp(-(new_value-value)/T):
            line,value = new_line,new_value#更新当前解
        #print('当前最优值 %.1f' % (best_value))
        T *= beta
    
    #路径顺序
    print('当前最优值 %.1f' % (best_value))
    print(best_line)
    #画图
    draw_path(best_line,CityCoordinates)

#show

当前最优值 438.6
[16, 15, 6, 2, 19, 1, 7, 10, 4, 8, 14, 13, 18, 9, 3, 11, 0, 12, 17, 5]

模拟退火算法

# -*- coding: utf-8 -*-
"""
模拟退火算法法求解TSP问题
随机在（0,101）二维平面生成20个点
距离最小化
"""
import math
import random
import pandas as pd
import matplotlib.pyplot as plt
from matplotlib.pylab import mpl
mpl.rcParams['font.sans-serif'] = ['SimHei']  # 添加这条可以让图形显示中文

#计算路径距离，即评价函数
def calFitness(line,dis_matrix):
    dis_sum = 0
    dis = 0
    for i in range(len(line)):
        if i<len(line)-1:
            dis = dis_matrix.loc[line[i],line[i+1]]#计算距离
            dis_sum = dis_sum+dis
        else:
            dis = dis_matrix.loc[line[i],line[0]]
            dis_sum = dis_sum+dis
    return round(dis_sum,1)

def greedy(CityCoordinates,dis_matrix,p):
    '''贪婪策略构造初始解，基于概率扰动'''
    #更改dis_matrix格式
    dis_matrix = dis_matrix.astype('float64')
    for i in range(len(CityCoordinates)):
        dis_matrix.loc[i,i]=math.pow(10,10)
    line = []#初始化，存放路径
    now_city = random.randint(0,len(CityCoordinates)-1)#随机生成出发城市
    line.append(now_city)#添加当前城市到路径
    dis_matrix.loc[:,now_city] = math.pow(10,10)#更新距离矩阵，已途径城市不再被取出
    
    i = 1#当前已排好城市个数
    j = 0#记录当前城市已遍历临近城市次数
    while len(CityCoordinates)-i>0:
        next_city = dis_matrix.loc[now_city,:].idxmin()#距离该城市最近的城市
        j += 1
        if j == len(CityCoordinates)-i:#是否为当前可遍历最后一个城市,是则直接添加——防止所有城市都不被取出的情况
            line.append(next_city)#添加进路径
            dis_matrix.loc[:,next_city] = math.pow(10,10)#更新距离矩阵
            now_city = next_city#更新当前城市
            i += 1
            j = 0#重置
        else:
            if random.random() < p:
                line.append(next_city)#添加进路径
                dis_matrix.loc[:,next_city] = math.pow(10,10)#更新距离矩阵
                now_city = next_city#更新当前城市
                i += 1
                j = 0#重置
            else:
                #不接受当前城市作为下一个城市
                dis_matrix.loc[now_city,next_city] = math.pow(10,10)#更新距离矩阵
    return line
    

    
#画路径图
def draw_path(line,CityCoordinates):
    x,y= [],[]
    for i in line:
        Coordinate = CityCoordinates[i]
        x.append(Coordinate[0])
        y.append(Coordinate[1])
    x.append(x[0])
    y.append(y[0])
    plt.plot(x, y,'-', color='#4169E1', alpha=0.8, linewidth=0.8)
    plt.xlabel('x')
    plt.ylabel('y')
    plt.show()


if __name__ == '__main__':
    #参数
    CityNum = 20#城市数量
    MinCoordinate = 0#二维坐标最小值
    MaxCoordinate = 101#二维坐标最大值
    
    #SA参数
    Tend = 0.1
    T = 100
    beta = 0.98
    #p = 1/(1+math.exp(-0.03*T)) #S型曲线
    
    best_value = math.pow(10,10)#较大的初始值，存储最优解
    best_line = []#存储最优路径
    
    #随机生成城市数据,城市序号为0,1，2,3...
    # CityCoordinates = [(random.randint(MinCoordinate,MaxCoordinate),random.randint(MinCoordinate,MaxCoordinate)) for i in range(CityNum)]
    CityCoordinates = [(88, 16),(42, 76),(5, 76),(69, 13),(73, 56),(100, 100),(22, 92),(48, 74),(73, 46),(39, 1),(51, 75),(92, 2),(101, 44),(55, 26),(71, 27),(42, 81),(51, 91),(89, 54),(33, 18),(40, 78)]

    #计算城市间距离
    dis_matrix = pd.DataFrame(data=None,columns=range(len(CityCoordinates)),index=range(len(CityCoordinates)))
    for i in range(len(CityCoordinates)):
        xi,yi = CityCoordinates[i][0],CityCoordinates[i][1]
        for j in range(len(CityCoordinates)):
            xj,yj = CityCoordinates[j][0],CityCoordinates[j][1]
            dis_matrix.iloc[i,j] = round(math.sqrt((xi-xj)**2+(yi-yj)**2),2)
    
    #循环
    while T >= Tend:
        p = 1/(1+math.exp(-0.03*T))#概率
        line = greedy(CityCoordinates,dis_matrix,p)#路径
        value = calFitness(line,dis_matrix)#路径距离
        if value < best_value:#优于最优解
            best_value,best_line = value,line#更新最优解
            print("当前最优解%.1f" % (best_value))
        T *= beta#更新T
    
    #路径顺序
    print(best_line)
    #画路径图
    draw_path(best_line,CityCoordinates)

#show

当前最优解647.2
当前最优解503.2
当前最优解478.4
当前最优解476.5
当前最优解457.9
[10, 7, 1, 19, 15, 16, 6, 2, 18, 9, 13, 14, 3, 0, 11, 12, 17, 4, 8, 5]

蚁群算法

# -*- coding: utf-8 -*-
"""
蚁群算法求解TSP问题
随机在（0,101）二维平面生成20个点
距离最小化
"""
import math
import random
import pandas as pd
import matplotlib.pyplot as plt
from matplotlib.pylab import mpl
mpl.rcParams['font.sans-serif'] = ['SimHei']  # 添加这条可以让图形显示中文

#计算路径距离，即评价函数
def calFitness(line,dis_matrix):
    dis_sum = 0
    dis = 0
    for i in range(len(line)-1):
        dis = dis_matrix.loc[line[i],line[i+1]]#计算距离
        dis_sum = dis_sum+dis
    dis = dis_matrix.loc[line[-1],line[0]]
    dis_sum = dis_sum+dis
    
    return round(dis_sum,1)

def intialize(CityCoordinates,antNum):
    """
    初始化，为蚂蚁分配初始城市
    输入：CityCoordinates-城市坐标;antNum-蚂蚁数量
    输出：cityList-蚂蚁初始城市列表，记录蚂蚁初始城市;cityTabu-蚂蚁城市禁忌列表，记录蚂蚁未经过城市
    """
    cityList,cityTabu = [None]*antNum,[None]*antNum#初始化
    for i in range(len(cityList)):
        city = random.randint(0, len(CityCoordinates)-1)#初始城市，默认城市序号为0开始计算
        cityList[i] = [city]
        cityTabu[i] = list(range(len(CityCoordinates)))
        cityTabu[i].remove(city)
    
    return cityList,cityTabu

def select(antCityList,antCityTabu,trans_p):
    '''
    轮盘赌选择，根据出发城市选出途径所有城市
    输入：trans_p-概率矩阵;antCityTabu-城市禁忌表，即未经过城市;
    输出：完整城市路径-antCityList;
    '''
    while len(antCityTabu) > 0:  
        if len(antCityTabu) == 1:
            nextCity = antCityTabu[0]
        else:
            fitness = []
            for i in antCityTabu:
                fitness.append(trans_p.loc[antCityList[-1],i])#取出antCityTabu对应的城市转移概率
            sumFitness = sum(fitness)
            randNum = random.uniform(0, sumFitness)
            accumulator = 0.0
            for i, ele in enumerate(fitness):
                accumulator += ele
                if accumulator >= randNum:
                    nextCity = antCityTabu[i]
                    break
        antCityList.append(nextCity)
        antCityTabu.remove(nextCity)
    
    return antCityList

def calTrans_p(pheromone,alpha,beta,dis_matrix,Q):
    '''
    根据信息素计算转移概率
    输入：pheromone-当前信息素；alpha-信息素重要程度因子；beta-启发函数重要程度因子；dis_matrix-城市间距离矩阵；Q-信息素常量；
    输出：当前信息素+增量-transProb
    '''
    transProb = Q/dis_matrix # 初始化transProb存储转移概率，同时计算增量
    for i in range(len(transProb)):
        for j in range(len(transProb)):
            transProb.iloc[i,j] = pow(pheromone.iloc[i,j], alpha) * pow(transProb.iloc[i,j], beta)
    
    return transProb

def updatePheromone(pheromone,fit,antCity,rho,Q):
    '''
    更新信息素，蚁周算法
    输入：pheromone-当前信息素；fit-路径长度；antCity-路径；rho-信息素挥发因子；Q-信息素常量
    输出：更新后信息素-pheromone
    '''
    for i in range(len(antCity)-1):
        pheromone.iloc[antCity[i],antCity[i+1]] += Q/fit
    pheromone.iloc[antCity[-1],antCity[0]] += Q/fit
    
    return pheromone

#画路径图
def draw_path(line,CityCoordinates):
    x,y= [],[]
    for i in line:
        Coordinate = CityCoordinates[i]
        x.append(Coordinate[0])
        y.append(Coordinate[1])
    x.append(x[0])
    y.append(y[0])
    
    plt.plot(x, y,'-', color='#4169E1', alpha=0.8, linewidth=0.8)
    plt.xlabel('x')
    plt.ylabel('y')
    plt.show()

if __name__ == '__main__':
    #参数
    CityNum = 20#城市数量
    MinCoordinate = 0#二维坐标最小值
    MaxCoordinate = 101#二维坐标最大值
    iterMax = 100#迭代次数
    iterI = 1#当前迭代次数
    #ACO参数
    antNum = 50#蚂蚁数量
    alpha = 2#信息素重要程度因子
    beta = 1#启发函数重要程度因子
    rho = 0.2#信息素挥发因子
    Q = 100.0#常数
    
    best_fit = math.pow(10,10)#较大的初始值，存储最优解
    best_line = []#存储最优路径
    
    #随机生成城市数据,城市序号为0,1,2,3...
    # CityCoordinates = [(random.randint(MinCoordinate,MaxCoordinate),random.randint(MinCoordinate,MaxCoordinate)) for i in range(CityNum)]
    CityCoordinates = [(88, 16),(42, 76),(5, 76),(69, 13),(73, 56),(100, 100),(22, 92),(48, 74),(73, 46),(39, 1),(51, 75),(92, 2),(101, 44),(55, 26),(71, 27),(42, 81),(51, 91),(89, 54),(33, 18),(40, 78)]
    
    #计算城市间距离,生成矩阵
    dis_matrix = pd.DataFrame(data=None,columns=range(len(CityCoordinates)),index=range(len(CityCoordinates)))
    for i in range(len(CityCoordinates)):
        xi,yi = CityCoordinates[i][0],CityCoordinates[i][1]
        for j in range(len(CityCoordinates)):
            xj,yj = CityCoordinates[j][0],CityCoordinates[j][1]
            if (xi==xj) & (yi==yj):
                dis_matrix.iloc[i,j] = round(math.pow(10,10))
            else:
                dis_matrix.iloc[i,j] = round(math.sqrt((xi-xj)**2+(yi-yj)**2),2)
    
    pheromone = pd.DataFrame(data=Q,columns=range(len(CityCoordinates)),index=range(len(CityCoordinates)))#初始化信息素，所有路径都为Q
    trans_p = calTrans_p(pheromone,alpha,beta,dis_matrix,Q)#计算初始转移概率
    
    while iterI <= iterMax:
        '''
        每一代更新一次环境因素导致的信息素减少，每一代中的每一个蚂蚁完成路径后，都进行信息素增量更新（采用蚁周模型）和转移概率更新；
        每一代开始都先初始化蚂蚁出发城市；
        '''
        antCityList,antCityTabu = intialize(CityCoordinates,antNum)#初始化城市
        fitList = [None]*antNum#适应值列表
        
        for i in range(antNum):#根据转移概率选择后续途径城市，并计算适应值
            antCityList[i] = select(antCityList[i],antCityTabu[i],trans_p)
            fitList[i] = calFitness(antCityList[i],dis_matrix)#适应度，即路径长度
            pheromone = updatePheromone(pheromone,fitList[i],antCityList[i],rho,Q)#更新当前蚂蚁信息素增量
            trans_p = calTrans_p(pheromone,alpha,beta,dis_matrix,Q)
        
        if best_fit >= min(fitList):
            best_fit = min(fitList)
            best_line = antCityList[fitList.index(min(fitList))]
            
        #print(iterI,best_fit)#打印当前代数和最佳适应度值
        iterI += 1#迭代计数加一
        pheromone = pheromone*(1-rho)#信息素挥发更新
    
    print(best_line)#路径顺序
    print(best_fit)
    draw_path(best_line,CityCoordinates)#画路径图
    

#show

[8, 4, 17, 12, 5, 16, 10, 7, 1, 19, 15, 6, 2, 18, 9, 13, 3, 0, 11, 14]

References

https://blog.csdn.net/tangshishe/article/details/115420035