遗传算法之 TSP 问题

Author Avatar
Tr0y 5月 29, 2017 16:08:18 本文共 1.2k 字
  • 文为知己者书
  • 在其它设备中阅读本文章

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

代码

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

class Evolution():
    def __init__(self, population, mutation_rate, add, retain_rate, data): 

        self.num = population
        self.mutation_rate = mutation_rate
        self.add = add
        self.retain_rate = retain_rate
        self.best = [[1,2],float("inf")]
        self.data = data
        self.mutationnum = 0
        self.insert = range(0, len(self.data))
        self.AllMaxy = []
        self.d = 0
        # 随机生成初始种群
        self.population = self.Gene_population()

        matplotlib.use('Agg')

    def Gene_population(self):
        """
        获取初始种群(一个含有 self.num 个长度为 self.chromosome_size 的染色体的列表)
        """
        x = []
        newx = range(0, len(self.data))

        while len(x) < self.num:
            if newx not in x:
                x += [newx[:]]

            random.shuffle(newx)

        return x[:]

    def Evolve(self):
        """
        进化
        对当前一代种群依次进行选择、交叉并生成新一代种群,然后对新一代种群进行变异
        """

        self.Selection()
        result = '目前第 ' + str(self.d) + ' 代, 此代最优为 ' + str(1 / self.Fitness(self.population[0])) +  ' , 变异次数为 ' + str(self.mutationnum)
        #self.Destroy()
        self.Crossover()
        self.Force_Insert()
        self.Mutation()

        self.d += 1
        return result

    def Fitness(self, xi):
        """
        计算适应度,将染色体解码为定义域之间的数字,代入函数计算
        因为是求最大值,所以数值越大,适应度越高
        """
        start = 0
        distance = 0.0

        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 1 / distance

    def Selection(self):
        """
        选择
        先对适应度从大到小排序,选出存活的染色体
        再进行随机选择,选出适应度虽然小,但是幸存下来的个体
        """
        xy = sorted([(i, j) for i, j in [(self.Fitness(xi), xi) for xi in self.population]], reverse = True)
        x = [x1 for y1, x1 in xy]
        y = [y1 for y1, x1 in xy]

        eMaxy = 1 / y[0] #此代最佳
        self.AllMaxy += [eMaxy]

        self.population = x[:int(self.num * self.retain_rate)] #精英策略

        if eMaxy < self.best[1]:
            self.PlotAndSave(x[0], y[0], 1) 
            os.system('cls')
            print x[0], '\n', '最佳第', self.d, '代', '最优路径长度为', eMaxy
            self.best = [x[0][:],eMaxy]

    def Crossover(self):
        """
        染色体的交叉、繁殖,生成新一代的种群
        新出生的孩子,最终会被加入存活下来的父母之中,形成新一代的种群。
        """
        length = len(self.population)
        for i in range(length):
            father= random.choice(self.population)
            mother = random.choice(self.population)

            r1 = np.random.random_integers(0, len(father) - 1)
            r2 = np.random.random_integers(1, len(mother) - r1)

            DNA1 = father[r1:r1 + r2]

            DNA2 = []
            for i in range(len(mother)):
                if mother[i] not in DNA1:
                    DNA2 += [mother[i]]

            child = []
            for i in range(r1):
                child += [DNA2[i]]

            child += DNA1 + DNA2[r1:]

            self.population += [child[:]]


    def Force_Insert(self):

        while len(self.population) < self.num:
            self.population += [self.insert[:]]
            random.shuffle(self.insert)


    def Mutation(self):
        """
        变异
        对种群中的所有个体,随机改变某个个体中的某个基因
        """
        each_mutation_rate = self.mutation_rate

        for i in range(len(self.population)):
            if random.uniform(0,1) < each_mutation_rate:
                r = np.random.randint(0, len(self.population[i]))
                self.population[i][r], self.population[i][len(self.population[i]) - r - 1] = self.population[i][len(self.population[i]) - r - 1], self.population[i][r]
                self.mutationnum += 1

            each_mutation_rate += self.add


    def PlotAndSave(self, x, y, f):

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

        if f:
            savefig('Max.jpg')
        else:

            savefig('%d_Max.jpg' %self.d)

        close('all')

        xr = []
        yr = []
        for i in 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)

        if f:
            savefig('Max_Road.jpg')
        else:
            savefig('%d_Road.jpg' %self.d)

        close('all')


time.clock()

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

population      = 1000    #种群数量
mutation_rate   = 0.001   #变异概率
add             = 0.05   #变异概率随着精英程度递减而增大,0.001
retain_rate      = 0.5   #种群筛选时保留 20% 的精英
data = [["*", [37, 52]], ["*", [49, 49]], ... ,["*", [30,40]]]

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

gene = Evolution(population, mutation_rate, add, retain_rate, data)
while 1:
    t = time.clock()
    minute, second = divmod(t, 60)
    hour, minute = divmod(minute, 60)
    try:
        print '\r', gene.Evolve(), " 花费时间 %02d:%02d:%02d" %(hour, minute, second),
    except:
        gene.PlotAndSave(gene.population[:][0], gene.Fitness(gene.population[0]), 0)

注意

  • 历史最优路径图为 Max.jpg, 曲线图以及路径图均保存在运行目录下.
  • 双击运行, 不要用 IDE 运行.
  • 针对不同问题可以对参数进行优化, 以得到更好的结果.
  • 按 Ctrl + C 可以实时保存曲线图以及路径图.

运行结果

  • Eil 51, 为例, 此网站给出的最优解为 426, 而我求出来的是 425.252657142
  • 结果截图
    运行结果
    适应度曲线图

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

End

What do you think?

本文标题: 遗传算法之 TSP 问题
原始链接: http://www.tr0y.wang/2017/05/29/GA_TSP/
发布时间: 2017.05.29-16:08
最后更新: 2019.05.31-16:36
版权声明: 本站文章均采用CC BY-NC-SA 4.0协议进行许可。转载请注明出处!