Python手把手构建粒子群算法(PSO)实现最优化搜索

《Python手把手构建粒子群算法(PSO)实现最优化搜索》

简介

粒子群算法(Particle Swarm optimization,简称PSO)是由Eberhart博士和kennedy博士发明的一种启发式算法,是通过模拟鸟群觅食行为而发展起来的一种基于群体协作的随机搜索算法。通常认为它是群集智能 (Swarm intelligence, SI) 的一种。

算法思想

通过模拟鸟群的捕食过程,把每只鸟看成PSO算法中的一个粒子,也就是我们需要求解问题的可行解。整个种群中的鸟在搜寻食物的过程中,会根据条件不断地改变自己的位置和速度。这个条件就是根据个体(可以看成一只叫“我”的鸟)的历史最优p_best和整个种群中全局最优g_best来进行改变下一时刻的位置。可以想象成,每只鸟会一定程度上追随该时刻找食物最厉害的那只鸟所在的位置,这里的位置就是指目标函数的极值点位置。

核心算子

v[i](t+1)表示一个i粒子下一时刻的速度,它是通过计算该粒子历史最优值pbest[i]和全部粒子全局最优值gbest与该时刻当前位置present[i](t)的差值得到的。其中w是惯性权值,c1c2表示学习参数。有了下一时刻的速度后,就能得到下一时刻的位置present[i](t+1)

示例

我们还是以一个简单的例子来介绍算法的流程。假设我们需要寻找函数y=x12+x22+x33+x44[1,30]之间的最大值。我们很容易就知道,当x1=x2=x3=x4=30时,该函数能取到最大值。

构建一个叫PSO的类,这个类包括算法的所有操作方法:

使用__init__()方法初始化参数,包括自变量可取的最大值,最小值,种群大小,迭代代数;使用fitness()方法作为适应度函数评估该个体的函数值,在这里就是函数y的值;使用update_operator()方法根据位置和速度更新粒子下一时刻的位置,挑选出当前代该粒子和种群中所有粒子的最好位置作为历史记录;使用main()方法实现整个算法的循环。

__init__()方法

__init__()方法的代码如下:

初始化方法接受传入的参数,包括最大值,最小值,种群大小和迭代代数。通过这些参数初始化产生一个粒子种群,并记录个体最优和全局最优位置。

fitness()方法

fitness()方法用来评估该位置的函数值,代码如下:

update_operator()方法

update_operator()方法里包含核心算子,根据速度和位置更新下一时刻的速度,代码如下:

需要注意的是,在更新位置的过程中有可能超过了我们定义的定义域范围,因此需要进行越界保护,强行将位置拉进定义域内,最后更新个体最好位置和全局最好位置。

main()方法

PSO算法所有的轮子都写好后,我们接下来将它们整合到流程中。代码实现如下:

传入循环迭代指定代数,输出目前找到的最好的位置和函数值,并画图得到整个迭代过程。

完整代码

if __name__ == "__main__":语句后面,我们设定所有的参数。总共跑NGEN=100代,每代的种群大小为100。

最后得到以下结果:

《Python手把手构建粒子群算法(PSO)实现最优化搜索》

迭代过程如下:

《Python手把手构建粒子群算法(PSO)实现最优化搜索》

总结

粒子群PSO算法相比遗传算法实现会简单一点,需要设置的参数也少,它的核心就是根据算子更新个体历史最优和全局最优值。寻优效果上比遗传算法更快,但是也不能保证一定能找到全局极值点。本文的代码能够快速运用到其他问题中,可供借鉴和参考。

点赞
  1. fsg说道:

    请问是不是有bug,按道理不需要self.ng_best这个参数,因为g_best根据代码逻辑会获取最优值,但是我实验一下,一步一步对比,如果没有self.ng_best参数,在运行过程中会把pop_x[i]无理由赋值到g_best,导致g_best变为不是最优解。

发表评论

邮箱地址不会被公开。 必填项已用*标注