模拟退火之 TSP 问题

Author Avatar
Tr0y 6月 02, 2017 20:46:15 本文共 744 字
  • 文为知己者书
  • 在其它设备中阅读本文章

利用 Python 实现模拟退火算法解决 TSP 问题, 并画出最优路径图与每代适应度曲线图

代码

# -*- coding: cp936 -*-
import math
import random
import time,os
from matplotlib.pyplot import *
import numpy as np

class Metal():
    def __init__(self, data, temperature, descending): 

        self.temperature = temperature
        self.descending = descending
        self.change = range(0, len(data))
        self.data = data
        self.best = [[1,2], float("inf")]
        self.x = self.best[0][:]
        self.y = self.best[1]
        self.HistoryY = []
        self.Cm = cm.get_cmap('Greys')


    def Smelt(self):
        """
        开始冶炼
        """

        NewY = self.Fx(self.change)

        dE = self.y - NewY

        if dE > 0 or math.e ** (dE / self.temperature) > random.uniform(0, 1):

            self.y = NewY
            self.x = self.change[:]

            if self.y < self.best[1]:
                self.best[0] = self.x
                self.best[1] = self.y

                os.system('cls')
                print '当金属温度为', self.temperature, '℃时达到历史最佳路径, 长度为', self.best[1], '\n 路线为\n', self.best[0], '\n', '-'*100

        self.HistoryY += [NewY]

        self.temperature -= self.descending
        self.RandX()


    def Fx(self, xi):
        """
        计算冶炼的程度
        """
        start = 0
        distance = 0.0
        Xi=xi+[xi[0]]
        #print len(Xi)
        for end in range(1, len(Xi)):
            distance += ((self.data[Xi[start]][1][0] * 1.0 - self.data[Xi[end]][1][0]) ** 2 + (self.data[Xi[start]][1][1] * 1.0 - self.data[Xi[end]][1][1]) ** 2) ** 0.5  #如果 data 的格式有变这里要改
            start = end

        return distance


    def RandX(self):
        """
        随机产生 2 个点,
        一个为起点,一个为终点,
        将这 2 点之间的路径倒置
        """

        self.change = self.x[:]

        start = random.randint(0, len(self.change))
        end = random.randint(start, len(self.change))

        self.change[start:end] = self.change[start:end][::-1]

        #random.shuffle(self.change)


    def PlotAndSave(self):
        """
        冶炼结束时画出每温度下的 x 与 y
        """

        plot(range(1, len(self.HistoryY) + 1), self.HistoryY)
        title(str(self.x) + '\n\n' + str(self.y), fontsize = 7)

        savefig('Max.jpg')

        close('all')

        xr = []
        yr = []
        for i in self.x:
            xr += [self.data[i][1][0]]
            yr += [self.data[i][1][1]]

        xr = np.array(xr + [xr[0]])
        yr = np.array(yr + [yr[0]])

        x0 = xr[:2]
        y0 = yr[:2]
        xr = xr[1:]
        yr = yr[1:]

        quiver(x0[:-1], y0[:-1], x0[1:] - x0[:-1], y0[1:] - y0[:-1], scale_units = 'xy', angles = 'xy', scale = 1, color='r')
        quiver(xr[:-1], yr[:-1], xr[1:] - xr[:-1], yr[1:] - yr[:-1], scale_units = 'xy', angles = 'xy', scale = 1)

        savefig('Max_Road.jpg')
        close('all')


time.clock()
#------------------------------------------------------------------参数设置------------------------------------------------------------------

data = [["*", [37, 52]],..., ["*", [30,40]]] #数据在这
temperature     = 100   #金属初始温度
descending      = 0.001   #降温幅度, 不是按百分比

#------------------------------------------------------------------参数设置------------------------------------------------------------------


metal = Metal(data, temperature, descending)
while metal.temperature > 1:

    t = time.clock()
    minute, second = divmod(t, 60)
    hour, minute = divmod(minute, 60)

    metal.Smelt()
    print '当前金属温度为', metal.temperature, '℃', '此温度下最优路径长度为', metal.y, ' 花费时间 %02d:%02d:%02d' %(hour, minute, second), ' '*5,'\r',

print '\n路线为\n', metal.x
metal.PlotAndSave()
print 
os.system('pause')

注意

  • 双击运行
  • 降温幅度较小, 会有更大概率得到较优值, 但是相应花费的时间也就越长.
  • Eil 51, 为例, 此网站给出的最优解为 426, 而我求出来的是 438.13.
  • 结果截图
    运行结果
    每温度最值
    最佳路径

所以, 代码的算法还是比较合理的.

End

What do you think?

本文标题: 模拟退火之 TSP 问题
原始链接: http://www.tr0y.wang/2017/06/02/FireTSP/
发布时间: 2017.06.02-20:46
最后更新: 2019.05.31-16:36
版权声明: 本站文章均采用CC BY-NC-SA 4.0协议进行许可。转载请注明出处!