粒子群算法求解TSP问题 |
您所在的位置：网站首页 › 基于遗传算法的tsp算法伪代码 › 粒子群算法求解TSP问题 |
粒子群算法求解TSP问题
|
粒子群算法求解TSP问题
1. TSP问题简介
旅行商人要拜访n个城市，并最终回到出发城市，要求每个城市只能拜访一次，优化目标是最小化路程之和。 2. 例子求解结果20个城市坐标：(88, 16),(42, 76),(5, 76),(69, 13),(73, 56),(100, 100),(22, 92),(48, 74),(73, 46),(39, 1),(51, 75),(92, 2),(101, 44),(55, 26),(71, 27),(42, 81),(51, 91),(89, 54),(33, 18),(40, 78） 结果路径图如下： 粒子群算法模仿鸟群觅食行为，核心思想是通过向距离食物最近的鸟集聚，不断更新速度和位置以达到最优解，即表现不好的个体通过向表现好的个体学习使得自身往好的方向转变，这里存在一个前提：所有鸟知道距离食物的远近，距离食物最近包含两部分：当前最近和历史最近。标准粒子群算法适合求解函数极值问题，在TSP、背包问题上多用混合型粒子群算法。详细介绍可参考[粒子群算法研究] 3.2 粒子群算法设计算法设计的关键在于如何向表现较好的个体学习，标准粒子群算法引入惯性因子w、自我认知因子c1、社会认知因子c2分别作为自身、当代最优解和历史最优解的权重，指导粒子速度和位置的更新，这在求解函数极值问题时比较容易实现，而在TSP问题上，速度位置的更新则难以直接采用加权的方式进行，一个常见的方法是采用基于遗传算法交叉算子的混合型粒子群算法进行求解，这里采用顺序交叉算子，对惯性因子w、自我认知因子c1、社会认知因子c2则以w/(w+c1+c2)，c1/(w+c1+c2)，c2/(w+c1+c2)的概率接受粒子本身、当前最优解、全局最优解交叉的父代之一（即按概率选择其中一个作为父代，不加权），具体算法实现如下。 # -*- coding: utf-8 -*- """ 粒子群算法求解TSP问题 随机在（0,101）二维平面生成20个点 距离最小化 """ import math import random import pandas as pd import matplotlib.pyplot as plt from matplotlib.pylab import mpl mpl.rcParams['font.sans-serif'] = ['SimHei'] # 添加这条可以让图形显示中文 def calDistance(CityCoordinates): ''' 计算城市间距离 输入：CityCoordinates-城市坐标； 输出：城市间距离矩阵-dis_matrix ''' dis_matrix = pd.DataFrame(data=None,columns=range(len(CityCoordinates)),index=range(len(CityCoordinates))) for i in range(len(CityCoordinates)): xi,yi = CityCoordinates[i][0],CityCoordinates[i][1] for j in range(len(CityCoordinates)): xj,yj = CityCoordinates[j][0],CityCoordinates[j][1] if (xi==xj) & (yi==yj): dis_matrix.iloc[i,j] = round(math.pow(10,10)) else: dis_matrix.iloc[i,j] = round(math.sqrt((xi-xj)**2+(yi-yj)**2),2) return dis_matrix def calFitness(line,dis_matrix): ''' 计算路径距离，即评价函数 输入：line-路径，dis_matrix-城市间距离矩阵； 输出：路径距离-dis_sum ''' dis_sum = 0 dis = 0 for i in range(len(line)-1): dis = dis_matrix.loc[line[i],line[i+1]]#计算距离 dis_sum = dis_sum+dis dis = dis_matrix.loc[line[-1],line[0]] dis_sum = dis_sum+dis return round(dis_sum,1) def draw_path(line,CityCoordinates): ''' #画路径图 输入：line-路径，CityCoordinates-城市坐标； 输出：路径图 ''' x,y= [],[] for i in line: Coordinate = CityCoordinates[i] x.append(Coordinate[0]) y.append(Coordinate[1]) x.append(x[0]) y.append(y[0]) plt.plot(x, y,'r-', color='#4169E1', alpha=0.8, linewidth=0.8) plt.xlabel('x') plt.ylabel('y') plt.show() def crossover(bird,pLine,gLine,w,c1,c2): ''' 采用顺序交叉方式；交叉的parent1为粒子本身，分别以w/(w+c1+c2),c1/(w+c1+c2),c2/(w+c1+c2) 的概率接受粒子本身逆序、当前最优解、全局最优解作为parent2,只选择其中一个作为parent2； 输入：bird-粒子,pLine-当前最优解,gLine-全局最优解,w-惯性因子,c1-自我认知因子,c2-社会认知因子； 输出：交叉后的粒子-croBird； ''' croBird = [None]*len(bird)#初始化 parent1 = bird#选择parent1 #选择parent2（轮盘赌操作） randNum = random.uniform(0, sum([w,c1,c2])) if randNum end_pos:start_pos,end_pos = end_pos,start_pos croBird[start_pos:end_pos+1] = parent1[start_pos:end_pos+1].copy() # parent2 -> croBird list1 = list(range(0,start_pos)) list2 = list(range(end_pos+1,len(parent2))) list_index = list1+list2#croBird从后往前填充 j = -1 for i in list_index: for j in range(j+1,len(parent2)+1): if parent2[j] not in croBird: croBird[i] = parent2[j] break return croBird if __name__ == '__main__': #参数 CityNum = 20#城市数量 MinCoordinate = 0#二维坐标最小值 MaxCoordinate = 101#二维坐标最大值 iterMax = 200#迭代次数 iterI = 1#当前迭代次数 #PSO参数 birdNum = 50#粒子数量 w = 0.2#惯性因子 c1 = 0.4#自我认知因子 c2 = 0.4#社会认知因子 pBest,pLine =0,[]#当前最优值、当前最优解，（自我认知部分） gBest,gLine = 0,[]#全局最优值、全局最优解，（社会认知部分） #随机生成城市数据,城市序号为0,1,2,3... # CityCoordinates = [(random.randint(MinCoordinate,MaxCoordinate),random.randint(MinCoordinate,MaxCoordinate)) for i in range(CityNum)] CityCoordinates = [(88, 16),(42, 76),(5, 76),(69, 13),(73, 56),(100, 100),(22, 92),(48, 74),(73, 46),(39, 1),(51, 75),(92, 2),(101, 44),(55, 26),(71, 27),(42, 81),(51, 91),(89, 54),(33, 18),(40, 78)] dis_matrix = calDistance(CityCoordinates)#计算城市间距离,生成矩阵 birdPop = [random.sample(range(len(CityCoordinates)),len(CityCoordinates)) for i in range(birdNum)]#初始化种群，随机生成 fits = [calFitness(birdPop[i],dis_matrix) for i in range(birdNum)]#计算种群适应度 gBest = pBest = min(fits)#全局最优值、当前最优值 gLine = pLine = birdPop[fits.index(min(fits))]#全局最优解、当前最优解 while iterI |
【本文地址】
今日新闻 |
推荐新闻 |