GA solve TSP—— A simple python code

AngelNH

发布于 2020-04-29 16:12:48

1.3K0

发布于 2020-04-29 16:12:48

文章被收录于专栏：AngelNIAngelNI

一、Genetic Algorithm

1、Introduction

遗传算法（GeneticAlgorithm）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，通过模拟自然进化过程搜索最优解。遗传算法是从代表问题可能潜在的解集的一个种群（population）开始的，初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代（generation）演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度（fitness）大小选择个体，并借助于自然遗传学的遗传算子（genetic operators）进行组合交叉（crossover）和变异（mutation），产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码（decoding），可以作为问题近似最优解。

2、GA Function

（1）Population selection

根据生物进化论，适者生存，优胜劣汰的规则，每个种群中的个体都有自己适应生存条件的能力，往往那些适应力能力强的个体容易生存下来，而那些适应力弱的个体，则被自然所淘汰。

GA中的适应度是根据不同的问题来设定的，比如解决TSP问题，这里的适应度是路线距离的倒数，路线距离越短，适应度越大。根据适应度对种群进行选择。

（2）Genetic crossover

种群内的基因交叉，是指种群产生后代的过程。从种群中选择优秀的父母，携带优秀的基因，那么他们的孩子的基因也可能是非常优秀的，要注意，是可能。

在这里基因交叉的方法有六种方法，可以参考下面这篇博客。我采用的是方法6

基因交叉的六种方法

第一步，在某个父代上选择1组基因，在另一父代上找到这些基因的位置，如下图：

第二步，保持未选中基因不变，按选中基因的出现顺序，交换两父代染色体中基因的位置，一次生成两个子代：

（3）Genetic mutation

我们都知道，个体在进化的过程中，存在基因变异的可能，基因变异有好有坏，但是不能忽略基因突变的重要性。

基因突变是指一段基因碱基序列中的某个碱基可能会突变为其他的碱基，模仿生物基因的特点，我们可以自定义基因序列进行基因突变。例如，TSP中的基因编码是路线label

二、TSP

1、Problem

一个商品推销员要去若干个城市推销商品，该推销员从一个城市出发，需要经过所有城市后，回到出发地。应如何选择行进路线，以使总的行程最短。

2、Flow chart

3、Solve

自我吐槽中：写了这么久的遗传算法中终于完工了，前前后后删了、重写、修改了好多次，功夫不负有心人终于用遗传算法解决了旅行商的问题。和第一次的A星算法一样，在代码中做了详细的注释，最后奉上我这个菜鸡的代码，大佬们勿喷啊。

import numpy as np
import copy
from time import time
import matplotlib.pyplot as plt
#随机数种子
np.random.seed(114514)
#遗传算法
class Genetic_Algorithm():
    def __init__(self,pop,pop_size,DNA_size,distance,city_position,crossover_rate = 0.1555,mutation_rate=0.025):
        #交叉概率
        self.crossover_rate = crossover_rate
        #变异概率
        self.mutation_rate = mutation_rate
        #种群
        self.pop = pop
        #种群大小
        self.pop_size = pop_size
        #DNA大小
        self.DNA_size = DNA_size
        #城市坐标
        self.city_position = city_position
        #城市间距离矩阵
        self.distance = distance    
        pass
    #计算种群个体适应度
    def compute_fitness(self,pop):
        #初始化一个空表
        fitness = np.zeros(self.pop_size,dtype= np.float32)
        #枚举每个个体
        for i,e in enumerate(pop):
            #print(e)
            for j in range(self.DNA_size-1):
                #计算个体i的适应度
                fitness[i] += self.distance[int(e[j])][int(e[j+1])]
        #记录距离
        dis = copy.copy(fitness)
        #适应度等于距离的倒数
        fitness = np.reciprocal(fitness)        
        return fitness,dis
    #轮盘赌，选择种群中的个体
    def select_population(self,fitness):
        #从种群中选择，pop_size个个体，每个个体被选择的概率为fitness / fitness.sum()
        indx = np.random.choice(np.arange(self.pop_size),size = self.pop_size,replace = True,p = fitness / fitness.sum())
        #print(indx)
        #花式索引，更新种群
        self.pop = self.pop[indx]
    #对新种群中的所有个体进行基因交叉
    def genetic_crossover(self):
        #遍历种群每个个体
        for parent1 in self.pop:
            #判断是否会基因交叉
            if np.random.rand() <self.crossover_rate:
                #### Subtour Exchange Crossover
                #### 基因交换方法参考6
                #####基因交叉参考https://blog.csdn.net/ztf312/article/details/82793295
                #寻找父代2
                n = np.random.randint(self.pop_size)
                parent2 = self.pop[n,:]
                #随机产生基因交换片段
                pos = np.random.randint(self.DNA_size,size = 2)
                #区间左右端点
                l = min(pos)
                r = max(pos)
                #记录区间
                seq = copy.copy(parent1[l:r])
                poss = []
                #交换
                for i in range(self.DNA_size):
                    if parent2[i] in seq:
                        poss.append(i)
                a = 0
                for i in seq:
                    parent2[poss[a]] = i
                    a+=1
                b = 0
                for i in range(l,r):
                    parent1[i] = parent2[poss[b]]
                    b+=1
                #print(parent1)
                #break   
    #种群中的所有个体基因突变
    def genetic_mutation(self):
        #枚举个体
        for e in self.pop:
            #变异的可能
            if np.random.rand() < self.mutation_rate:
                #随机变异交换点
                position = np.random.randint(self.DNA_size,size = 2)
                e[position[0]],e[position[1]] = e[position[1]] , e[position[0]]
        pass
#初始化种群
def init_pop(pop_size,DNA_size):
    #初始化一个种群 大小为pop_size*DNA_size
    pop = np.zeros((pop_size,DNA_size))
    #DNA编码
    code = np.arange(DNA_size)
    for i in range(pop_size):
        pop[i] = copy.deepcopy(code)
        #随机打乱函数
        np.random.shuffle(pop[i])
    #返回种群
    return pop       
#画图
def show(lx, ly,city_position,dis):
    plt.cla()   # 清除键
    #画点
    plt.scatter(city_position[0],city_position[1],color = 'r')
    #画线
    plt.plot(lx,ly)
    #不显示坐标轴
    plt.xticks([])
    plt.yticks([])
    #文本注释
    plt.text(-5.25, -14.05, "Total distance=%.2f" % dis, fontdict={'size': 20, 'color': 'red'})
    #暂停时间
    plt.pause(0.01)
def best_show(x,y,city_position,best_fitness,dis):
    #定义两个子图
    fig,ax=plt.subplots(1,2,figsize=(12,5),facecolor='#ccddef')
    #定义子图1标题
    ax[0].set_title("Best route")
    #定义子图2标题
    ax[1].set_title("Fitness Change Procession")
    #画线
    ax[0].plot(x,y)
    #画点
    ax[0].scatter(city_position[0],city_position[1],color = 'r')
    #画线
    ax[1].plot(range(len(best_fitness)),best_fitness)
    plt.show()
    pass

#解决旅行商问题
def TSP(city_position,pop_size,DNA_size,distance,t):
    #初始化一个种群
    pop = init_pop(pop_size,DNA_size)
    #调用遗传算法类
    GA = Genetic_Algorithm(pop,pop_size,DNA_size,distance,city_position)
    #保存最佳距离
    best_distance = 1e6
    #保存最佳路线
    route = None
    #保存最佳x坐标
    x = None
    #保存最佳y坐标
    y = None
    #保存适应度变化曲线
    fitness_process = []
    for i in range(t):
        #t-=1
        #返回适应度，和距离函数
        fitness ,dis= GA.compute_fitness(GA.pop)
        #选择新的种群
        GA.select_population(fitness)
        #基因交叉
        GA.genetic_crossover()
        #基因突变
        GA.genetic_mutation()
        ####################
        #记录当前状态最优解
        #返回最优解索引
        num = np.argmax(fitness)
        #记录DNA
        DNA = GA.pop[num,:]
        #打印当前状态
        print(f"The step is {i} ,the current best distance is {min(dis)} ,fitness is {max(fitness)}")
        lx = []
        ly = []
        #DNA转化为记录坐标
        fitness_process.append(max(fitness))
        for i in DNA:
            i = int(i) 
            lx.append(city_position[0][i])
            ly.append(city_position[1][i])
        #保存最佳方案
        if best_distance > min(dis):
            best_distance = min(dis)
            route = DNA = GA.pop[num,:]
            x = copy.copy(lx)
            y = copy.copy(ly)
        show(lx,ly,city_position,min(dis))
    #打印最终结果
    print(f"The best route is {route}")
    print(f"The route distance is {best_distance}")
    best_show(x,y,city_position,fitness_process,best_distance)


if __name__ == "__main__":
    #数据
    x = [ 178,272,176,171,650,499,267,703,408,437,491,74,532,416,626,42,271,359,163,508,229,576,147,560,35,714,757,517,64,314,675,690,391,628,87,240,705,699,258,428,614,36,360,482,666,597,209,201,492,294]
    y = [ 170,395,198,151,242,556,57,401,305,421,267,105,525,381,244,330,395,169,141,380,153,442,528,329,232,48,498,265,343,120,165,50,433,63,491,275,348,222,288,490,213,524,244,114,104,552,70,425,227,331]
    #从起点到终点
    x.append(x[0])
    y.append(y[0])
    #初始化一个全0矩阵
    distance = np.zeros((len(x),len(x)))
    #计算距离矩阵,distance[i][j]表示 i to j 的距离
    for i in range(len(x)):
        for j in range(len(x)):
            distance[i][j] = np.sqrt(np.square(x[i]-x[j])+np.square(y[i]-y[j]))
    #转换成一个矩阵
    city_position = np.array([x,y])
    #种群大小
    pop_size = 400
    #DNA大小也是城市大小
    DNA_size = 51
    #迭代次数
    t = 10000
    #sovle problem
    TSP(city_position,pop_size,DNA_size,distance,t)

3、Answer

GA中有四个参数，分别是种群大小。迭代次数，基因交叉概率，基因突变概率——一个好的算法要有适应算法本身的参数。（调参真真真的好累！！）

下面是迭代10000次的结果

The best route is [42.  8. 27. 10. 48. 43. 33. 31. 25. 44. 30. 37. 36.  7. 26.  4. 40. 14.
 23. 19. 21. 45. 12.  5.  9. 13. 32. 39. 22. 41. 34. 47. 16.  1. 49. 38.
 35. 28. 15. 24. 11.  3. 18.  2. 50.  0. 20. 46.  6. 29. 17.]
The route distance is 4065.84765625

路线动态更新视频

document.getElementById("spkj").style.height=document.getElementById("spkj").scrollWidth*0.76+"px";

最后的结果