计算智能 | 蚁群算法——旅行商问题（TSP）python

目录

一、求解TSP（city31）问题的python代码 

二、python运行结果

一、求解TSP（city31）问题的python代码 

import numpy as npimport randomimport matplotlib.pyplot as pltplt.rcParams['font.sans-serif']=['SimHei']plt.rcParams['axes.unicode_minus']=Falseclass ACA_TSP:    def __init__(self,n,X,Y,m,N,Q,P,alpha,beta):        '''        :param n: 城市数量        :param X: 城市的横坐标        :param Y: 城市的纵坐标        :param m: 蚁群规模        :param N: 最大迭代步数        :param Q: 蚂蚁循环一周或一个过程在经过的路径上所释放的信息素总量        :param P: 信息素挥发系数        :param alpha: 信息启发式因子        :param beta: 期望启发式因子        '''        self.n=n        self.X=X        self.Y=Y        self.m=m        self.N=N        self.Q=Q        self.P=P        self.alpha=alpha        self.beta=beta    def distance(self):        '''        return: 所有城市之间的距离矩阵        '''        D=np.zeros((self.n,self.n))        for i in range(self.n):            for j in range(self.n):                D[i][j]=np.sqrt((self.X[i]-self.X[j])**2+(self.Y[i]-self.Y[j])**2)        return D    def initial_X(self):        #随机生成初始路径        X0=random.sample(range(self.n),self.n)        return X0    def initial_tao(self,X0,D):        '''        :param X0: 初始路径        :param D: 距离矩阵        :return: 初始信息素浓度        '''        #计算初始路径长度        S=0        for i in range(self.n):            if i!=self.n-1:                S=S+D[X0[i]][X0[i+1]]            else:                S=S+D[X0[i]][X0[0]]        #计算初始信息素浓度        tao_00=self.m/S        tao_0=np.zeros((self.n,self.n))        tao_0=tao_0+tao_00        return tao_0    def initial_city(self):        #为每只蚂蚁随机选择出发城市        initial=[random.randint(0,self.n-1) for i in range(self.m)]        return initial    '''一只蚂蚁在一次周期内选择路径的过程'''    def seek(self,initial,tao,D):        '''        :param initial: 蚂蚁出发的城市序号        :param tao: 信息素浓度矩阵        :param D: 距离矩阵        :return: 蚂蚁最终选择的路径        '''        #存储已经遍历的城市        ls=[]        ls.append(initial)        for i in range(self.n-1):            #蚂蚁未经过的城市序号            l=[]            for j in range(self.n):                if j not in ls:                    l.append(j)            if len(l)==1:                ls.append(l[-1])            else:                #计算蚂蚁下一次访问某个城市的概率                ratio_l0=[]                for j in range(len(l)):                    r=(tao[ls[-1]][l[j]]**self.alpha)*((1/D[ls[-1]][l[j]])**self.beta)                    ratio_l0.append(r)                #得到概率                ratio_l=[ratio_l0[j]/sum(ratio_l0) for j in range(len(ratio_l0))]                #计算累计概率                ratio_cum=[0]                for j in range(len(ratio_l)):                    cum=ratio_cum[-1]+ratio_l[j]                    ratio_cum.append(cum)                #用轮盘赌选择算法选择下一个访问城市                q=random.uniform(0,1)                for j in range(1,len(ratio_cum)):                    if q>=ratio_cum[j-1] and q