欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

基于模拟退火算法解决旅行商问题(Python代码)

程序员文章站 2022-06-26 17:07:13
大家好!本文为大家提供了模拟退火算法解决TSP的一种python实现...

大家好!本文为大家提供了模拟退火算法解决TSP的一种python实现。有兴趣的同学可以看看“遗传算法解决TSP问题”,你会发现二者产生新解的方式一样,但选择新解的方式不同。

import math
import random
import numpy as np
import matplotlib.pyplot as plt

# 随机生成城市信息
nCity = 10
City = np.random.uniform(-10, 10, [nCity, 2])
Dis = {}
for i in range(nCity):
    for j in range(nCity):
        if i > j:
            dis = ((City[i][0] - City[j][0]) ** 2 + (City[i][1] - City[j][1]) ** 2) ** 0.5
            Dis[(i, j)] = dis
            Dis[(j, i)] = dis

Data_BestFit =[]   #用于保存每一代蚂蚁的最优适应度

#适应度计算函数 适应值 = 路径距离
def Cal_Fit(X):
    total_dis = Dis[(X[-1],X[0])]
    for i in range(nCity-1):
        total_dis += Dis[(X[i],X[i+1])]
    return total_dis

def SAA_TSP():
    # 定义参数
    T0 = 100      # 初始温度
    T1 = 0.1      # 最终温度
    a = 0.99      # 温度衰减系数
    Markov = 100  # 马尔科夫链
    Pm = 0.3      # 变异概率
    Pc = 0.7      # 交叉概率

    # 初始化解
    Best_X = None
    Best_Fit = math.inf
    X = np.zeros([Markov,nCity])
    Fit = np.zeros([Markov])
    for i in range(Markov):
        X[i] = np.random.permutation(nCity)
        Fit[i] = Cal_Fit(X[i])
        if Fit[i] < Best_Fit:
            Best_Fit = Fit[i]
            Best_X = X[i].copy()

    # 降温过程
    T = T0
    while T >= T1:
        for i in range(Markov):
            # 变异、交叉产生新解
            x = X[i].copy()
            if random.random() < Pm:
                point1 = int(random.random() * nCity)
                point2 = int(random.random() * nCity)
                while point1 == point2:
                    point1 = int(random.random() * nCity)
                    point2 = int(random.random() * nCity)
                x[point1],x[point2] = x[point2],x[point1]

            if random.random() < Pc:
                point = int(random.random()*nCity)
                temp1 = list(x[0:point])
                temp2 = list(x[point:nCity])
                temp2.extend(temp1)
                x = np.array(temp2.copy())

            # 计算新解适应值并判断是否接受
            fit = Cal_Fit(x)
            delta = fit - Fit[i]
            if delta <= 0:
                Fit[i] = fit
                X[i] = x
                if Fit[i] < Best_Fit:
                    Best_Fit = Fit[i]
                    Best_X = X[i].copy()
            # 是否接受恶化解
            elif random.random() < math.exp(-delta/T):
                Fit[i] = fit
                X[i] = x.copy()

        Data_BestFit.append(Best_Fit)
        T *= a # 降温
        
    return Best_X, Best_Fit

# 绘制路径与迭代曲线
def Draw_City(City, X ,Best_Fit):
    X = list(X)
    X.append(X[0])
    coor_x = []
    coor_y = []
    for i in X:
        i = int(i)
        coor_x.append(City[i][0])
        coor_y.append(City[i][1])

    plt.plot(coor_x, coor_y, 'r-o')
    plt.title('TSP with Simulated Annealing Algorithm\n'+'total_dis = '+str(round(Best_Fit,3)))
    plt.show()

    plt.plot(range(len(Data_BestFit)), Data_BestFit)
    plt.title('Iteration_BestFit')
    plt.xlabel('iteration')
    plt.ylabel('fitness')
    plt.show()

if __name__ == '__main__':
    Best_X, Best_Fit = SAA_TSP()
    Draw_City(City,Best_X, Best_Fit)




本文地址:https://blog.csdn.net/qq_44936034/article/details/112686933