遗传算法求解TSP问题

参考博客参考的代码和详解

根据老师的数据把其中一些代码修改了很小一部分：

```python

import numpy as np
import math
import random

# 適應度
def fitnessFunction(pop,num,city_num,distance):
    length=city_num
    for i in range(num):
        dis=0
        for j in range(length-1):
            dis+=distance[int(pop[i][j])][int(pop[i][j+1])]
        dis+=distance[int(pop[i][j+1])][int(pop[i][0])]
        pop[i][-1]=20000/dis

# 選擇
def choiceFuction(pop):
    numlist=[0]
    length=len(pop)
    allnum=0
    for i in range(0,length):
        allnum+=pop[i][-1]
        numlist.append(allnum)

    temppop=[]                                                      #用于临时的种群数据
    max = pop[np.argmax(pop[:, -1])]                                #最优的一个个体
    for i in range(0,length):
        rannum=random.random()*numlist[-1]                          #0~1的小数乘上最大的数字，得到[0，max]上的一个点
        ranIndex=InsertionSearch(numlist,rannum,0,length-1)         #调用搜索函数
        temppop.append(pop[ranIndex-1])                             #将一个个的数据添加到
    pop=np.array(temppop)                                           #将pop索引指向临时数据，并且此处应该清理原来的pop空间才对
    pop[0]=max.copy()                                               #保证第一个元素就是最优的元素
    
    return pop
    
# 插值搜索
# 输入：列表，要搜索的值，最低索引，最高索引
# 输出：相等时的索引，或者接近该值左侧的索引
# 备注：Python里面的递归有次数限制(99次)
def InsertionSearch(list,value,low,high):
    mid=low+int((value-list[low])/(list[high]-list[low])*(high-low))
    if list[mid]==value:
        return mid
    if list[mid]>value:
        if list[mid-1]<value:
            return mid-1
        else:
            return InsertionSearch(list,value,low,mid-1)
    if list[mid]<value:
        if list[mid+1]>value:
            return mid
        else:
            return InsertionSearch(list,value,mid+1,high)

# 交叉变异(此处的交叉有两种情况)
# 输入：种群，交叉概率，城市数量(列)，变异概率，种群数量(行)
# 输出：无输出，是一个过程(先交叉，再变异)
# 备注：不同的交叉策略，相邻，随机，配对
def matuingFuction(pop, pc, city_num, pm, num):
    #产生两个不同的索引
    rancon=True
    while rancon :
        p1=random.randint(1,city_num-1)
        p2=random.randint(0,city_num-2)
        if p1==p2:
            rancon=True
        elif p1<p2:
            rancon=False
        else:
            temp=p1
            p1=p2
            p2=temp
        pass

    # 交叉,變異(每一对交换，1 and 2, 3 and 4, and so on)
    # for i in range(1,num-1,2):
    #     # for j in range(0,num-1):
    #     #     if i!=j:
    #     #         pc2=random.random()
    #     #         if(pc2<pc):
    #     #             matuting(pop[i],pop[j],p1,p2)
    #     pc2=random.random()
    #     if pc2<pc:
    #         matuting(pop[i],pop[i+1],p1,p2)
    #     # print("poobefore:",pop[i])
    #     variationFunction(pop[i],pm,city_num)
    #     # print("pooend:",pop[i])
    #     variationFunction(pop[i+1],pm,city_num)

    # 交叉,變異(相邻两个进行交换)
    for i in range(1,num-1):
        pc2=random.random()
        if pc2<pc:
            matuting(pop[i],pop[i+1],p1,p2)
        variationFunction(pop[i],pm,city_num)

# 交叉过程
# 输入：第一行数据x1，第二行数据x2，左侧断点，右侧断点
# 输出：惊醒过交叉的两行数据
# 备注：由于函数是单次检测，所以需要调用两次内部函数
def matuting(x1, x2, p1, p2):
    length=len(x1)-1
    temp=x1[p1:p2].copy()
    x1[p1:p2]=x2[p1:p2]
    x2[p1:p2]=temp

    #自定義交換函數，需要調用兩次才能夠將其完全的排列好
    def change(x1,x2,p1,p2):
        #检查元素
        isrepeat=True
        while isrepeat:
            countTrue=0
            for i in range(p1,p2):
                for j in range(0,p1):
                    if int(x1[j])==int(x1[i]):
                        isrepeat=True
                        countTrue+=1
                        x1[j]=x2[i]
                for k in range(p2,length):
                    if int(x1[k])==int(x1[i]):
                        isrepeat=True
                        countTrue+=1
                        x1[k]=x2[i]
            if countTrue==0:
                isrepeat=False
    
    #調用交換函數，兩次
    change(x1,x2,p1,p2)
    change(x2,x1,p1,p2)   

# 变异过程
# 输入：一行数据，变异概率，城市数量
# 输出：行内交换元素的一行数据
# 备注：似乎数据交换不需要定义临时变量
def variationFunction(list_a, pm, city_num):
    if random.random()<pm:
        i=random.randint(0,city_num-1)
        isequal=True
        while isequal:
            j=random.randint(0,city_num-1)
            if(j==i):   isequal=True
            else:       isequal=False
            pass
        #交换两个数据
        list_a[i],list_a[j]=list_a[j],list_a[i]         

# 主函数
def main():
    # 初始化
    pop = []                      # 存放访问顺序和每个个体适应度@
    num = 700                     # 初始化群体的数目@
    city_num = 5                # 城市数目@
    pc = 0.9                      # 每个个体的交配概率S@
    pm = 0.3                      # 每个个体的变异概率@
    dis="0,3,1,5,8,3,0,6,7,9,1,6,0,4,2,5,7,4,0,3,8,9,2,3,0"
    # #获取输入的十个城市之间距离，并将它们转化为numpy的array，并重新reshape成10*10的二维数组distance@
    # distance1 =  input().split(",")
    distance1=dis.split(",")
    distance2 = np.array(distance1,dtype=np.int)
    distance = distance2.reshape((5, 5))    

    for i in range(num):
        pop.append(np.random.permutation(np.arange(0,city_num)))    # 假设有10个城市，初始群体的数目500个@

    zero = np.zeros((num,1))                                        # 返回给定形状和类型的新数组，用零填充。二维数组，num行2列@
    pop = np.column_stack((pop, zero))                              # 矩阵的拼接@
    fitnessFunction(pop, num, city_num, distance)                   # 为初始种群赋予自适应度@
    pop=choiceFuction(pop)

    # 遗传算法迭代，250为迭代次数，同学们可以对其进行调整@
    for i in range(250):
        matuingFuction(pop,pc,city_num,pm,num)                      # 交叉變異
        fitnessFunction(pop,num,city_num,distance)                  # 計算適應度
        pop=choiceFuction(pop)                                      # 選擇

    #输出自适应度最大解个体并计算其路径长度@
    max = pop[np.argmax(pop[:, -1])]
    sum = 0
    for x2 in range(city_num - 1):
       sum += distance[int(max[x2])][int(max[x2 + 1])]
    sum += distance[int(max[4])][int(max[0])]
    print(sum)

# 运行函数
if __name__=="__main__":
    main()

# 值类型：int, float, bool, str, tuple
# 引用类型：list, dict, set