智能算法-粒子群算法(2)

语言: CN / TW / HK

theme: scrolls-light

一起养成写作习惯!这是我参与「掘金日新计划 · 4 月更文挑战」的第16天,点击查看活动详情

1. 粒子群算法

本节主要介绍粒子群算法的改进思路及策略,首先回顾一下粒子群算法:一群分散的鸟儿在随机地飞行觅食,它们不知道食物所在的具体位置,在觅食过程中,每只小鸟都会记录自己飞行位置。突然,其中某一只小鸟$A$发现好多玉米,于是就喊:“快来,我这里有好多食物!”,然而,其他小鸟都只发现了零零星星的几个玉米粒。于是,每个小鸟在飞行的时候就有了一个指导的方向(往小鸟A的位置飞),但是,每个小鸟都有不忍心放弃当前努力搜寻过的位置(小鸟们心想:我这里刚才也找到点玉米粒,再继续找找说不定比你还要多)。因此,它们最终决定结合自身的经验整个群体的经验,调整自己的飞行速度和所在位置,不断地寻找更加接近食物的位置,最终使得群体聚集到食物位置。

粒子群算法介绍以及实例详解请参考智能算法-粒子群算法 - 掘金 (juejin.cn)

2. 粒子群算法改进策略

2.1 选择思想

从种群中选择出一个个体,将该个体的适应度与其它个体的适应度进行比较,若优于某个体,则每次给该个体记一分。对每个个体重复这个过程。根据每个个体的分数,对所有个体进行排列。选择较好的前半部分个体,并复制它们,替代种群中较差的后半部分个体。在此过程中,最佳个体的适应度并未发生改变。

评价:此种改进策略收敛速度缓慢,相当于把差的粒子都替换了成优秀的粒子,导致所有粒子都很优秀,都比较相似,大家朝着最优秀的粒子进步速度就缓慢了。越是差距大,越知道自己的努力方向,越是都很优秀,大家差距越小,提升空间过小,进步缓慢。

2.2 杂交微粒群思想

微粒群中的每个微粒被赋予一个杂交概率,由用户给定,与适应值无关。 在每次迭代时,依据杂交概率选择一定数量的微粒进入杂交池,池内的微粒随机地两两杂交,产生相同数目的子代,并用子代微粒取代父代微粒,以保持种群的微粒数目不变

微粒杂交计算方式请参考如下公式:

image.png

2.3 变异思想

测试所有粒子与当前最优的距离,当距离小于一定的数值的时候,可以拿出所有粒子的一个百分比(如10%,需根据题目自行确定)的粒子进行随机初始化,让这些粒子重新寻找最优值(给一些粒子随机赋予新的位置,丰富粒子群)。

评价:此改进思想可以克服“早熟”(防止收敛过快而陷入局部最优解)

2.4 小生境改进思想

小生境的简单概述,自然界中往往特征、性状相似的物种相聚在一起,并在同类中交配繁衍后代。遗传算法中的小生境思想主要是将每一代个体划分为若干类,每类选出优秀个体组成一个种群;

基于动态邻域的改进微粒群算法。 根据微粒的下标将微粒群体分割成若干个相邻的区域,而不管它们在空间位置上如何。每次迭代时,种群中一个微粒到其它微粒之间的距离可以被算出来,并记录下最大距离$dmax$,然后计算每一个粒子的 $‖𝑥𝑎−𝑥𝑏‖/𝑑max$,根据计算出的结果选择相邻的微粒,利用较小比值和较大比值作为选择依据。公式中的$‖𝑥𝑎−𝑥𝑏‖$表示粒子$a$与粒子$b$的距离。