如何使用Python轻松解决TSP问题(PSO算法)

您所在的位置:网站首页 tsp问题python实现 如何使用Python轻松解决TSP问题(PSO算法)

如何使用Python轻松解决TSP问题(PSO算法)

2023-07-12 23:02| 来源: 网络整理| 查看: 265

持续创作,加速成长!这是我参与「掘金日新计划 · 10 月更文挑战」的第14天,点击查看活动详情

前言

先前我们给出了遗传算法的解决方案,那么同样的我们,给出使用PSO的解决方案。其实对PSO算法比较了解的小伙伴应该是知道的,这个PSO其实是比较适合解决连续问题的。而我们的TSP问题显然是一个离散的问题。那么如何将连续问题转化为离散问题呢,那么这个时候其实有一个方案就是使用广义PSO算法。其实除了这个方案,我自己其实也有一个方案,这个方案基本上应该是通用的可以将连续问题转化为离散问题。这个方案的话,咱们在使用强化学习解决TSP问题的时候来搞定,值得一提的是,我也没有查阅相关文献,是我的一个改动吧,如果有,可以后面call我,拿出对应文献,我可以将这些东西进行优化。

PSO算法

那么开始之前,我们还是来聊聊基本的PSO算法。这个我写的非常多了,在这方面,因为暑假做的也是这方面的优化。核心就一个: 在这里插入图片描述 在这里插入图片描述 来我们来解释一下这个公式,你就懂了。

老规矩我们假设有一个方程 y=sin(x1)+cos(x2) PSO算法通过模拟鸟类迁移来实现咱们的优化,这个怎么来的,就不说了,就说说这个核心。 我们刚刚的方程当中,有两个变量,x1,x2。由于是模拟鸟儿,所有为了实现瞎蒙大法,这里引入了速度的概念,x自然就是咱们的可行域,也就是解的空间。通过改变速度,来让x进行移动,也就是改变x的值。其中Pbest,表示这个鸟自己走过的位置里面最优的解,Gbest表示整个种群的最优解。什么意思,也就是说随着移动,这个鸟可能会走到更差的位置,因为和遗传不一样,他是不好的就被干掉了,而这个不会。当然这里面涉及到很多局部问题,咱们这里都不讨论,没有哪一个算法是完美的,这个就对了。

算法流程

算法的主要流程:

第一步:对粒子群的随机位置和速度进行初始设定,同时设定迭代次数。 第二步:计算每个粒子的适应度值。 第三步:对每个粒子,将其适应度值与所经历的最好位置pbest i的适应度值进行比较,若较好,则将其作为当前的个体最优位置。 第四步:对每个粒子,将其适应度值与全局所经历的最好位置gbestg的适应度值进行比较,若较好,则将其作为当前的全局最优位置。 第五步:根据速度、位置公式对粒子的速度和位置进行优化,从而更新粒子位置。 第六步:如未达到结束条件(通常为最大循环数或最小误差要求),则返回第二步

在这里插入图片描述

优点:

PSO算法没有交叉和变异运算,依靠粒子速度完成搜索,并且在迭代进化中只有最优的粒子把信息传递给其它粒子,搜索速度快。

PSO算法具有记忆性,粒子群体的历史最好位置可以记忆并传递给其它粒子。 需调整的参数较少,结构简单,易于工程实现。

采用实数编码,直接由问题的解决定,问题解的变量数直接作为粒子的维数。

缺点:

缺乏速度的动态调节,容易陷入局部最优,导致收敛精度低和不易收敛。

不能有效解决离散及组合优化问题。

参数控制,对于不同的问题,如何选择合适的参数来达到最优效果。 不能有效求解一些非直角坐标系描述问题,

简单实现

ok,我们来看一下最简单的实现:

import numpy as np import random class PSO_model: def __init__(self,w,c1,c2,r1,r2,N,D,M): self.w = w # 惯性权值 self.c1=c1 self.c2=c2 self.r1=r1 self.r2=r2 self.N=N # 初始化种群数量个数 self.D=D # 搜索空间维度 self.M=M # 迭代的最大次数 self.x=np.zeros((self.N,self.D)) #粒子的初始位置 self.v=np.zeros((self.N,self.D)) #粒子的初始速度 self.pbest=np.zeros((self.N,self.D)) #个体最优值初始化 self.gbest=np.zeros((1,self.D)) #种群最优值 self.p_fit=np.zeros(self.N) self.fit=1e8 #初始化全局最优适应度 # 目标函数,也是适应度函数(求最小化问题) def function(self,x): A = 10 x1=x[0] x2=x[1] Z = 2 * A + x1 ** 2 - A * np.cos(2 * np.pi * x1) + x2 ** 2 - A * np.cos(2 * np.pi * x2) return Z # 初始化种群 def init_pop(self): for i in range(self.N): for j in range(self.D): self.x[i][j] = random.random() self.v[i][j] = random.random() self.pbest[i] = self.x[i] # 初始化个体的最优值 aim=self.function(self.x[i]) # 计算个体的适应度值 self.p_fit[i]=aim # 初始化个体的最优位置 if aim < self.fit: # 对个体适应度进行比较,计算出最优的种群适应度 self.fit = aim self.gbest = self.x[i] # 更新粒子的位置与速度 def update(self): for t in range(self.M): # 在迭代次数M内进行循环 for i in range(self.N): # 对所有种群进行一次循环 aim=self.function(self.x[i]) # 计算一次目标函数的适应度 if aim1-->2-->14-->3-->4-->5-->6-->12-->7-->13-->8-->11-->9 第40步后的最短的路程: 29.340520066994223 第40步后的最优路径: 9-->10-->1-->2-->14-->3-->4-->5-->6-->12-->7-->13-->8-->11-->9 第60步后的最短的路程: 29.340520066994223 第60步后的最优路径: 9-->10-->1-->2-->14-->3-->4-->5-->6-->12-->7-->13-->8-->11-->9 第80步后的最短的路程: 29.340520066994223 第80步后的最优路径: 9-->10-->1-->2-->14-->3-->4-->5-->6-->12-->7-->13-->8-->11-->9 第100步后的最短的路程: 29.340520066994223 第100步后的最优路径: 9-->10-->1-->2-->14-->3-->4-->5-->6-->12-->7-->13-->8-->11-->9 第120步后的最短的路程: 29.340520066994223 第120步后的最优路径: 9-->10-->1-->2-->14-->3-->4-->5-->6-->12-->7-->13-->8-->11-->9 第140步后的最短的路程: 29.340520066994223 第140步后的最优路径: 9-->10-->1-->2-->14-->3-->4-->5-->6-->12-->7-->13-->8-->11-->9 第160步后的最短的路程: 29.340520066994223 第160步后的最优路径: 9-->10-->1-->2-->14-->3-->4-->5-->6-->12-->7-->13-->8-->11-->9 第180步后的最短的路程: 29.340520066994223 第180步后的最优路径: 9-->10-->1-->2-->14-->3-->4-->5-->6-->12-->7-->13-->8-->11-->9 第200步后的最短的路程: 29.340520066994223 第200步后的最优路径: 9-->10-->1-->2-->14-->3-->4-->5-->6-->12-->7-->13-->8-->11-->9 复制代码

可以看到收敛速度还是很快的。

特点分析

ok,到目前为止的话,我们介绍了两个算法去解决TSP或者是优化问题。我们来分析一下,这些算法有什么特点,为啥可以达到我们需要的优化效果。其实不管是遗传还是PSO,你其实都可以发现,有一个东西,我们可以暂且叫它环境压力。我们通过物竞天择,或者鸟类迁移,进行模拟寻优。而之所以需要这样做,是因为我们指定了一个规则,在我们的规则之下。我们让模拟的种群有一种压力去靠拢,其中物竞天择和鸟类迁移只是我们的一种手段,去应对这样的“压力”。所以的对于这种算法而言,最核心的点就两个:

设计环境压力

我们需要做优化问题,所以我们必须要能够让我们的解往那个方向走,需要一个驱动,需要一个压力。因此我们需要设计这样的一个环境,在遗传算法,粒子群算法是通过种群当中的生存,来进行设计的它的压力是我们的目标函数。由种群和目标函数(目标指标)构成了一个环境和压力。

设计压力策略

之后的话,我们设计好了一个环境和压力,那么未来应对这种压力,我们需要去设计一种策略,来应付这种压力。遗传算法是通过PUA自己,也就是种群的优胜略汰。PSO是通过学习,学习种群的优秀粒子和过去自己家的优秀“祖先”来应对这种压力的。

强化学习

所以的话,我们是否可以使用别的方案来实现这种优化效果。,在强化学习的算法框架里面的话,我们明确的知道了为什么他们可以实现优化,是环境压力+压力策略。恰好咱们强化学习是有环境的,适应函数和环境恰好可以组成环境+压力。本身的算法收敛过程就是我们的压力策略。所以我们完全是可以直接使用强化学习进行这个处理的。那么在这里咱们就来使用强化学习在下一篇文章当中。



【本文地址】


今日新闻


推荐新闻


CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3