旅行商路径优化问题的遗传算法程序

编制旅行商路径优化问题的遗传算法程序，并计算一个实例。(以不超过10个城市为例,给出初始种群规模、交叉概率、变异概率在不同设置情况下的总结分析)。
要求：遗传算法路径结果图，适应函数自选（标明），附上全部代码。
旅行商问题：

从北京（B）乘飞机到威海(W)、贵阳(G)、上海(S)、昆明(K)、拉萨(L)
五城市做旅游，每城市恰去一次再回北京，应如何安排旅游线，使旅程最短？各城市之间的航线距离如表7。
表7 六城市间的距离
L B W G S K
L 0 38 42 27 41 24
B 38 0 8 21 13 22
W42 8 0 26 10 29
G 27 21 26 0 18 5
S 41 13 10 18 0 25
K 24 22 29 5 25 0

以下是代码

import random as rd

minimum=999999  #初始化minimum为一个很大的值 保证任何结果都小于该值
result =""  #全局最小路径结果

pathLen=[[0,38,42,27,41,24],[38,0,8,21,13,22],[42,8,0,26,10,29],[27,21,26,0,18,5],[41,13,10,18,0,25],[24,22,29,5,25,0]] #各个城市的距离表

class path():
    def __init__(self,p1,p2,n=5): #类型初始化,p1为交叉概率,p2为变异概率,n为城市数 本例为5（北京先后到5个城市）
        self.path=[i for i in range(n)]
        self.p1=p1
        self.p2=p2
        self.n=n
    def init(self): #用于第一代的基因生成
        for i in range(self.n):
            self.path[i]=rd.randint(0,self.n)

    def exchange(self): #交叉
        if rd.randint(1,100)>(100-self.p1):   #有概率交叉
            while 1:
                position1=rd.randint(0,self.n-1)   #随机生成交叉位置
                position2=rd.randint(0,self.n-1)
                if position1 != position2:  #判断交叉位置非同一位置
                    self.path[position1],self.path[position2]=self.path[position2],self.path[position1]
                    break
                else:
                    continue
    def change(self):
        if rd.randint(1,100)>(100-self.p2):     #有概率变异
            self.path[rd.randint(0,self.n-1)]=rd.randint(0,self.n)
    def calculate(self):    #计算路径总长度
        count=pathLen[1][self.path[0]]   #北京至第一个城市的路程
        for i in range(self.n-1):
            count+=pathLen[self.path[i]][self.path[i+1]]   #中途各个城市间的路程
        count+=pathLen[self.path[-1]][1]  #最后一个城市到北京的路程
        return count
    def parity(self):   #校验是否为每个城市去一次且不包含北京
        count=0
        path=self.path.copy()
        path.sort()
        for i in range(len(path)-1):
            if path[i]==path[i+1]:
                count+=1
            if path[i]==1:
                count+=1
        if count==0:
            return 1
        else:
            return 0

    def nxt(self,other): #产生子代
        p=path(self.p1,self.p2)
        for i in range(self.n):
            if rd.randint(1,100)>50:
                p.path[i]=self.path[i]
            else:
                p.path[i]=other.path[i]
        return p


def generate(n,p1,p2):  #生成种群 n为规模 p1为交叉概率 p2为变异概率
    t=[]
    for i in range(n):
        father=path(p1,p2)
        father.init()
        t.append(father)
    return t


def allChange(t):    #进行繁殖、变异、交换、淘汰
    global minimum
    global result
    l=len(t)
    print("本轮父代个数为:",l)
    if l>100:   #如果父代个数大于100则开始父代淘汰机制
        path=[]
        for i in t:
            path.append(i.calculate())   #计算各个个体的路径长度
        path.sort()  #路径长度排序
        tt=[]
        j=0
        while len(tt)<100:
            for i in t:
                if i.calculate()==path[j]:
                    tt.append(i)
            j+=1
        t=tt
    l=len(t)
    for i in range(l):   
        for j in range(l-1-i):
            child=t[i].nxt(t[j]) #两两交配产生子代
            child.exchange()     #子代交换
            child.change()      #子代变异
            t.append(child)          #向种群添加子代
    count=0
    for i in range(len(t)):  #去除不符合的成员
        if t[i-count].parity()==0: #杀死不符合要求的子代 （每个城市去一次且不包含北京）
            del(t[i-count])
            count+=1
    print("本轮产生子代后总数:",len(t))
    result1=t[-1].path
    mini=t[-1].calculate()
    for i in range(len(t)-1):   #获得各个个体的路程长度
        tt=t[i].calculate()     
        if mini>tt:             #比较是否是新的最小路径
            mini=tt
            result1=t[i].path
    print("本轮最小路径长度:",mini)
    print("本轮最小路径结果:",result1)
    if mini<minimum:
        minimum=mini
        result=result1




zq=generate(30,10,10) #generate(30,10,10)表示 初始种群30，交换概率10%，变异概率10%
for i in range(6):  #range(n) 标识迭代n代
    allChange(zq)
print("最后最小路径长度为:",minimum)
print("最后最小路径为:",result)

运行结果
图片说明