null - 程序员宅基地

TSP+PSO+python_pso 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）
结果路径图如下：
在这里插入图片描述

3. 粒子群算法简介

3.1 粒子群算法基本原理

粒子群算法模仿鸟群觅食行为，核心思想是通过向距离食物最近的鸟集聚，不断更新速度和位置以达到最优解，即表现不好的个体通过向表现好的个体学习使得自身往好的方向转变，这里存在一个前提：所有鸟知道距离食物的远近，距离食物最近包含两部分：当前最近和历史最近。标准粒子群算法适合求解函数极值问题，在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 (xixj) & (yiyj):
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 <= w:
parent2 = [bird[i] for i in range(len(bird)-1,-1,-1)]#bird的逆序
elif randNum <= w+c1:
parent2 = pLine
else:
parent2 = gLine

<span class="token comment">#parent1-&gt; croBird</span>
start_pos <span class="token operator">=</span> random<span class="token punctuation">.</span>randint<span class="token punctuation">(</span><span class="token number">0</span><span class="token punctuation">,</span><span class="token builtin">len</span><span class="token punctuation">(</span>parent1<span class="token punctuation">)</span><span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span>
end_pos <span class="token operator">=</span> random<span class="token punctuation">.</span>randint<span class="token punctuation">(</span><span class="token number">0</span><span class="token punctuation">,</span><span class="token builtin">len</span><span class="token punctuation">(</span>parent1<span class="token punctuation">)</span><span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span>
<span class="token keyword">if</span> start_pos<span class="token operator">&gt;</span>end_pos<span class="token punctuation">:</span>start_pos<span class="token punctuation">,</span>end_pos <span class="token operator">=</span> end_pos<span class="token punctuation">,</span>start_pos
croBird<span class="token punctuation">[</span>start_pos<span class="token punctuation">:</span>end_pos<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">]</span> <span class="token operator">=</span> parent1<span class="token punctuation">[</span>start_pos<span class="token punctuation">:</span>end_pos<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">.</span>copy<span class="token punctuation">(</span><span class="token punctuation">)</span>

<span class="token comment"># parent2 -&gt; croBird</span>
list1 <span class="token operator">=</span> <span class="token builtin">list</span><span class="token punctuation">(</span><span class="token builtin">range</span><span class="token punctuation">(</span><span class="token number">0</span><span class="token punctuation">,</span>start_pos<span class="token punctuation">)</span><span class="token punctuation">)</span>
list2 <span class="token operator">=</span> <span class="token builtin">list</span><span class="token punctuation">(</span><span class="token builtin">range</span><span class="token punctuation">(</span>end_pos<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">,</span><span class="token builtin">len</span><span class="token punctuation">(</span>parent2<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">)</span>
list_index <span class="token operator">=</span> list1<span class="token operator">+</span>list2<span class="token comment">#croBird从后往前填充</span>
j <span class="token operator">=</span> <span class="token operator">-</span><span class="token number">1</span>
<span class="token keyword">for</span> i <span class="token keyword">in</span> list_index<span class="token punctuation">:</span>
    <span class="token keyword">for</span> j <span class="token keyword">in</span> <span class="token builtin">range</span><span class="token punctuation">(</span>j<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">,</span><span class="token builtin">len</span><span class="token punctuation">(</span>parent2<span class="token punctuation">)</span><span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">:</span>
        <span class="token keyword">if</span> parent2<span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">not</span> <span class="token keyword">in</span> croBird<span class="token punctuation">:</span>
            croBird<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> parent2<span class="token punctuation">[</span>j<span class="token punctuation">]</span>
            <span class="token keyword">break</span>
                
<span class="token keyword">return</span> croBird

if name == ‘main’:
#参数
CityNum = 20#城市数量
MinCoordinate = 0#二维坐标最小值
MaxCoordinate = 101#二维坐标最大值
iterMax = 200#迭代次数
iterI = 1#当前迭代次数

<span class="token comment">#PSO参数</span>
birdNum <span class="token operator">=</span> <span class="token number">50</span><span class="token comment">#粒子数量</span>
w <span class="token operator">=</span> <span class="token number">0.2</span><span class="token comment">#惯性因子</span>
c1 <span class="token operator">=</span> <span class="token number">0.4</span><span class="token comment">#自我认知因子</span>
c2 <span class="token operator">=</span> <span class="token number">0.4</span><span class="token comment">#社会认知因子</span>
pBest<span class="token punctuation">,</span>pLine <span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">,</span><span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token comment">#当前最优值、当前最优解，（自我认知部分）</span>
gBest<span class="token punctuation">,</span>gLine <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">,</span><span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token comment">#全局最优值、全局最优解，（社会认知部分）</span>

<span class="token comment">#随机生成城市数据,城市序号为0,1,2,3...</span>
<span class="token comment"># CityCoordinates = [(random.randint(MinCoordinate,MaxCoordinate),random.randint(MinCoordinate,MaxCoordinate)) for i in range(CityNum)]</span>
CityCoordinates <span class="token operator">=</span> <span class="token punctuation">[</span><span class="token punctuation">(</span><span class="token number">88</span><span class="token punctuation">,</span> <span class="token number">16</span><span class="token punctuation">)</span><span class="token punctuation">,</span><span class="token punctuation">(</span><span class="token number">42</span><span class="token punctuation">,</span> <span class="token number">76</span><span class="token punctuation">)</span><span class="token punctuation">,</span><span class="token punctuation">(</span><span class="token number">5</span><span class="token punctuation">,</span> <span class="token number">76</span><span class="token punctuation">)</span><span class="token punctuation">,</span><span class="token punctuation">(</span><span class="token number">69</span><span class="token punctuation">,</span> <span class="token number">13</span><span class="token punctuation">)</span><span class="token punctuation">,</span><span class="token punctuation">(</span><span class="token number">73</span><span class="token punctuation">,</span> <span class="token number">56</span><span class="token punctuation">)</span><span class="token punctuation">,</span><span class="token punctuation">(</span><span class="token number">100</span><span class="token punctuation">,</span> <span class="token number">100</span><span class="token punctuation">)</span><span class="token punctuation">,</span><span class="token punctuation">(</span><span class="token number">22</span><span class="token punctuation">,</span> <span class="token number">92</span><span class="token punctuation">)</span><span class="token punctuation">,</span><span class="token punctuation">(</span><span class="token number">48</span><span class="token punctuation">,</span> <span class="token number">74</span><span class="token punctuation">)</span><span class="token punctuation">,</span><span class="token punctuation">(</span><span class="token number">73</span><span class="token punctuation">,</span> <span class="token number">46</span><span class="token punctuation">)</span><span class="token punctuation">,</span><span class="token punctuation">(</span><span class="token number">39</span><span class="token punctuation">,</span> <span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">,</span><span class="token punctuation">(</span><span class="token number">51</span><span class="token punctuation">,</span> <span class="token number">75</span><span class="token punctuation">)</span><span class="token punctuation">,</span><span class="token punctuation">(</span><span class="token number">92</span><span class="token punctuation">,</span> <span class="token number">2</span><span class="token punctuation">)</span><span class="token punctuation">,</span><span class="token punctuation">(</span><span class="token number">101</span><span class="token punctuation">,</span> <span class="token number">44</span><span class="token punctuation">)</span><span class="token punctuation">,</span><span class="token punctuation">(</span><span class="token number">55</span><span class="token punctuation">,</span> <span class="token number">26</span><span class="token punctuation">)</span><span class="token punctuation">,</span><span class="token punctuation">(</span><span class="token number">71</span><span class="token punctuation">,</span> <span class="token number">27</span><span class="token punctuation">)</span><span class="token punctuation">,</span><span class="token punctuation">(</span><span class="token number">42</span><span class="token punctuation">,</span> <span class="token number">81</span><span class="token punctuation">)</span><span class="token punctuation">,</span><span class="token punctuation">(</span><span class="token number">51</span><span class="token punctuation">,</span> <span class="token number">91</span><span class="token punctuation">)</span><span class="token punctuation">,</span><span class="token punctuation">(</span><span class="token number">89</span><span class="token punctuation">,</span> <span class="token number">54</span><span class="token punctuation">)</span><span class="token punctuation">,</span><span class="token punctuation">(</span><span class="token number">33</span><span class="token punctuation">,</span> <span class="token number">18</span><span class="token punctuation">)</span><span class="token punctuation">,</span><span class="token punctuation">(</span><span class="token number">40</span><span class="token punctuation">,</span> <span class="token number">78</span><span class="token punctuation">)</span><span class="token punctuation">]</span>
dis_matrix <span class="token operator">=</span> calDistance<span class="token punctuation">(</span>CityCoordinates<span class="token punctuation">)</span><span class="token comment">#计算城市间距离,生成矩阵</span>

birdPop <span class="token operator">=</span> <span class="token punctuation">[</span>random<span class="token punctuation">.</span>sample<span class="token punctuation">(</span><span class="token builtin">range</span><span class="token punctuation">(</span><span class="token builtin">len</span><span class="token punctuation">(</span>CityCoordinates<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">,</span><span class="token builtin">len</span><span class="token punctuation">(</span>CityCoordinates<span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token keyword">for</span> i <span class="token keyword">in</span> <span class="token builtin">range</span><span class="token punctuation">(</span>birdNum<span class="token punctuation">)</span><span class="token punctuation">]</span><span class="token comment">#初始化种群，随机生成</span>
fits <span class="token operator">=</span> <span class="token punctuation">[</span>calFitness<span class="token punctuation">(</span>birdPop<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">,</span>dis_matrix<span class="token punctuation">)</span> <span class="token keyword">for</span> i <span class="token keyword">in</span> <span class="token builtin">range</span><span class="token punctuation">(</span>birdNum<span class="token punctuation">)</span><span class="token punctuation">]</span><span class="token comment">#计算种群适应度</span>
gBest <span class="token operator">=</span> pBest <span class="token operator">=</span> <span class="token builtin">min</span><span class="token punctuation">(</span>fits<span class="token punctuation">)</span><span class="token comment">#全局最优值、当前最优值</span>
gLine <span class="token operator">=</span> pLine <span class="token operator">=</span> birdPop<span class="token punctuation">[</span>fits<span class="token punctuation">.</span>index<span class="token punctuation">(</span><span class="token builtin">min</span><span class="token punctuation">(</span>fits<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">]</span><span class="token comment">#全局最优解、当前最优解</span>

<span class="token keyword">while</span> iterI <span class="token operator">&lt;=</span> iterMax<span class="token punctuation">:</span><span class="token comment">#迭代开始</span>
    <span class="token keyword">for</span> i <span class="token keyword">in</span> <span class="token builtin">range</span><span class="token punctuation">(</span><span class="token builtin">len</span><span class="token punctuation">(</span>birdPop<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">:</span>
        birdPop<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> crossover<span class="token punctuation">(</span>birdPop<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">,</span>pLine<span class="token punctuation">,</span>gLine<span class="token punctuation">,</span>w<span class="token punctuation">,</span>c1<span class="token punctuation">,</span>c2<span class="token punctuation">)</span>
        fits<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> calFitness<span class="token punctuation">(</span>birdPop<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">,</span>dis_matrix<span class="token punctuation">)</span>
    
    pBest<span class="token punctuation">,</span>pLine <span class="token operator">=</span>  <span class="token builtin">min</span><span class="token punctuation">(</span>fits<span class="token punctuation">)</span><span class="token punctuation">,</span>birdPop<span class="token punctuation">[</span>fits<span class="token punctuation">.</span>index<span class="token punctuation">(</span><span class="token builtin">min</span><span class="token punctuation">(</span>fits<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">]</span>
    <span class="token keyword">if</span> <span class="token builtin">min</span><span class="token punctuation">(</span>fits<span class="token punctuation">)</span> <span class="token operator">&lt;=</span> gBest<span class="token punctuation">:</span>
        gBest<span class="token punctuation">,</span>gLine <span class="token operator">=</span>  <span class="token builtin">min</span><span class="token punctuation">(</span>fits<span class="token punctuation">)</span><span class="token punctuation">,</span>birdPop<span class="token punctuation">[</span>fits<span class="token punctuation">.</span>index<span class="token punctuation">(</span><span class="token builtin">min</span><span class="token punctuation">(</span>fits<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">]</span>
    
    <span class="token keyword">print</span><span class="token punctuation">(</span>iterI<span class="token punctuation">,</span>gBest<span class="token punctuation">)</span><span class="token comment">#打印当前代数和最佳适应度值</span>
    iterI <span class="token operator">+=</span> <span class="token number">1</span><span class="token comment">#迭代计数加一</span>

<span class="token keyword">print</span><span class="token punctuation">(</span>gLine<span class="token punctuation">)</span><span class="token comment">#路径顺序</span>
draw_path<span class="token punctuation">(</span>gLine<span class="token punctuation">,</span>CityCoordinates<span class="token punctuation">)</span><span class="token comment">#画路径图</span>

TSP系列目录

智能优化算法类别	启发式算法求解TSP问题系列博文
进化算法	遗传算法求解TSP问题
仿人智能优化算法	禁忌搜索算法求解TSP问题
仿自然优化算法	模拟退火算法求解TSP问题
群智能优化算法	蚁群算法求解TSP问题
群智能优化算法	粒子群算法求解TSP问题
总结篇	五种常见启发式算法求解TSP问题
改进篇	遗传-粒子群算法&遗传-禁忌搜索算法求解TSP问题

记录学习过程，欢迎指正

本文链接：https://blog.csdn.net/qq_43585760/article/details/129873366

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

5个超厉害的资源搜索网站，每一款都可以让你的资源满满！_最全资源搜索引擎-程序员宅基地

文章浏览阅读1.6w次，点赞8次，收藏41次。生活中我们无时不刻不都要在网站搜索资源，但就是缺少一个趁手的资源搜索网站，如果有一个比较好的资源搜索网站可以帮助我们节省一大半时间！今天小编在这里为大家分享5款超厉害的资源搜索网站，每一款都可以让你的资源丰富精彩！网盘传奇一款最有效的网盘资源搜索网站你还在为找网站里面的资源而烦恼找不到什么合适的工具而烦恼吗？这款网站传奇网站汇聚了4853w个资源，并且它每一天都会持续更新资源；..._最全资源搜索引擎

Book类的设计(Java)_6-1 book类的设计java-程序员宅基地

文章浏览阅读4.5k次，点赞5次，收藏18次。阅读测试程序，设计一个Book类。函数接口定义：class Book{}该类有四个私有属性分别是书籍名称、价格、作者、出版年份，以及相应的set 与get方法；该类有一个含有四个参数的构造方法，这四个参数依次是书籍名称、价格、作者、出版年份。裁判测试程序样例：import java.util.*;public class Main { public static void main(String[] args) { List <Book>_6-1 book类的设计java

基于微信小程序的校园导航小程序设计与实现_校园导航微信小程序系统的设计与实现-程序员宅基地

文章浏览阅读613次，点赞28次，收藏27次。相比于以前的传统手工管理方式，智能化的管理方式可以大幅降低学校的运营人员成本，实现了校园导航的标准化、制度化、程序化的管理，有效地防止了校园导航的随意管理，提高了信息的处理速度和精确度，能够及时、准确地查询和修正建筑速看等信息。课题主要采用微信小程序、SpringBoot架构技术，前端以小程序页面呈现给学生，结合后台java语言使页面更加完善，后台使用MySQL数据库进行数据存储。微信小程序主要包括学生信息、校园简介、建筑速看、系统信息等功能，从而实现智能化的管理方式，提高工作效率。

有状态和无状态登录

传统上用户登陆状态会以 Session 的形式保存在服务器上，而 Session ID 则保存在前端的 Cookie 中；而使用 JWT 以后，用户的认证信息将会以 Token 的形式保存在前端，服务器不需要保存任何的用户状态，这也就是为什么 JWT 被称为无状态登陆的原因，无状态登陆最大的优势就是完美支持分布式部署，可以使用一个 Token 发送给不同的服务器，而所有的服务器都会返回同样的结果。有状态和无状态最大的区别就是服务端会不会保存客户端的信息。

九大角度全方位对比Android、iOS开发_ios 开发角度-程序员宅基地

文章浏览阅读784次。发表于10小时前| 2674次阅读| 来源TechCrunch| 19 条评论| 作者Jon EvansiOSAndroid应用开发产品编程语言JavaObjective-C摘要：即便Android市场份额已经超过80%，对于开发者来说，使用哪一个平台做开发仍然很难选择。本文从开发环境、配置、UX设计、语言、API、网络、分享、碎片化、发布等九个方面把Android和iOS_ios 开发角度

搜索引擎的发展历史

搜索引擎的发展历史可以追溯到20世纪90年代初，随着互联网的快速发展和信息量的急剧增加，人们开始感受到了获取和管理信息的挑战。这些阶段展示了搜索引擎在技术和商业模式上的不断演进，以满足用户对信息获取的不断增长的需求。

随便推点

控制对象的特性_控制对象特性-程序员宅基地

文章浏览阅读990次。对象特性是指控制对象的输出参数和输入参数之间的相互作用规律。放大系数K描述控制对象特性的静态特性参数。它的意义是：输出量的变化量和输入量的变化量之比。时间常数T当输入量发生变化后，所引起输出量变化的快慢。（动态参数） ..._控制对象特性

FRP搭建内网穿透(亲测有效)_locyanfrp-程序员宅基地

文章浏览阅读5.7w次，点赞50次，收藏276次。FRP搭建内网穿透1.概述：frp可以通过有公网IP的的服务器将内网的主机暴露给互联网，从而实现通过外网能直接访问到内网主机；frp有服务端和客户端，服务端需要装在有公网ip的服务器上，客户端装在内网主机上。2.简单的图解：3.准备工作：1.一个域名（www.test.xyz）2.一台有公网IP的服务器(阿里云、腾讯云等都行)3.一台内网主机4.下载frp，选择适合的版本下载解压如下：我这里服务器端和客户端都放在了/usr/local/frp/目录下4.执行命令# 服务器端给执_locyanfrp