基于PSO自适应双策略的人工鱼群算法

刘志锋,舒志浩,胥越峰,杨舒伊,沈文龙

(1.东华理工大学信息工程学院,江西 南昌 330013;2.东华理工大学江西省放射性地学大数据技术工程实验室,江西 南昌 330013)

0 引 言

人工鱼群算法(Artificial Fish Swarm Algorithm， AFSA)是李晓磊博士等人[1-2]于2002年提出的一种人工智能算法，该算法是通过模拟鱼类的行为，引入动物自治体的概念，实现群智能的一种优化算法。该算法有全局寻优能力强、对初值不敏感且能够和其他算法相结合等优点[3]，目前在参数优化[4]、故障诊断[5]、路径规划[6]、水资源优化配置[7]、系统实时调度[8]等领域取得了良好效果。但人工鱼群算法也存在前期收敛速度快而后期收敛速度慢、求解精度不高、容易陷入局部最优解等缺点[9]。针对上述人工鱼群算法的缺点，目前国内外已有大量研究成果对该算法进行了改进，例如，文献[10]结合人工鱼群算法和捕鱼算法的优势，提出了一种混合优化算法， 改进算法具有更好的优化性能。文献[11]将自适应动态邻域结构引入到人工鱼群算法中，提高其跳出局部最优解的能力，改善了算法的收敛性能。文献[12]将模糊聚类思想引入人工鱼群算法中，提高了其效率。文献[13]引入禁忌搜索思想，改善了鱼群因陷入局部极值而出现寻优停滞不前的状况。文献[14]针对种群初始化随机不均匀的缺陷，引入佳点集理论初始化种群，并引入反向学习机制，加快了算法收敛速度，提高了求解精度。文献[15]采用了一种行为选择的方法，通过log-linear模型计算概率，使人工鱼选择适当的行为，取得了较好的优化效果。

相对于人工鱼群算法，粒子群算法(Particle Swarm Optimization Algorithm, PSO)[16-17]具有收敛速度快、寻优精度高等优点。而在算法迭代过程中，自适应调整某些参数可以提高算法的寻优精度。王联国等人[18]提出一种 PSO 和 AFSA 混合的优化算法，利用PSO 算法追逐当前全局最优点和人工鱼群算法的搜索随机性，并在人工鱼群算法部分自适应调整视野和步长参数，提高了算法的搜索速度与收敛精度。文献[19-20] 自适应调整人工鱼的参数，保证算法前期有较强的全局探索能力，迭代后期有较好的局部寻优能力。文献[21]提出了一种基于 Logistic 模型的可变步长和视野机制的改进人工鱼群算法，使得步长和视野在算法迭代后期逐渐递减到一个固定值，有效提高了算法的求解精度。文献[22]提出了一种反向自适应高斯变异的人工鱼群算法，引入反向解概念对其进行相对质量评价，然后运用自适应视野和步长策略，权衡全局搜索和局部搜索的关系，最后引入高斯变异机制，筛选较优解，寻优精度及鲁棒性得到了一定的提升。

综合以上文献思路，本文提出一种基于粒子群算法自适应双策略的人工鱼群算法(P-ADAFSA)，本文在标准 AFSA基础上进行了如下3个方面的改进：1)改进了鱼群的基本行为，借鉴粒子群算法中粒子移动算子，调整人工鱼的状态，提升人工鱼探索新区域的能力，提高了发掘潜在较优解的机率，避免其陷入局部最优解；2)运用非线性自适应函数，根据迭代进化次数自适应调整人工鱼的视野范围以及惯性权重，均衡全局搜索与局部搜索之间的关系；3)引入反向学习机制[23]和向全局最优位置学习对聚群行为和追尾行为的缺省行为(随机行为)进行了2种不同的改进，避免随机行为的盲目性，增加人工鱼群的多样性，降低早熟的可能性。经7个Benchmark函数的仿真实验证明，P-ADAFSA具有更好的鲁棒性、收敛速度和寻优精度。

1 基本人工鱼群算法(AFSA)

1.1 相关定义

通过观察鱼类的活动发现，鱼群总是聚集在营养物质最丰富的地方，根据鱼类这一特点模拟其基本行为，由此实现全局优化，这就是基本人工鱼群算法[1]。单个人工鱼的状态记为向量X=(x1，x2，…，xn)，其中xi(i=1,2,…,n)为欲寻优变量；当前状态的人工鱼食物浓度记为Y=f(X)，Y为目标函数值；人工鱼之间的距离表示为dij=‖Xi-Xj‖，其他参数有人工鱼的视野visual，步长step，拥挤度因子δ，尝试次数try_number。

1.2 行为描述

1.2.1 觅食行为

设人工鱼当前状态为Xi，在其视野 visual 范围内即(dij

(1)

1.2.2 聚群行为

计算当前人工鱼视野范围内的个体鱼的数目nf及邻域内人工鱼群的中心位置Xc，若YC/nf>δYi，则说明中心位置处食物浓度较高且附近的人工鱼不拥挤，此时人工鱼按照公式(2)向此方向移动一步。否则，执行觅食行为。

(2)

1.2.3 追尾行为

寻找当前人工鱼视野范围内食物浓度为最大值Ymax时的人工鱼Xmax，如果Ymax/nf>δYi，则表明此时人工鱼Xmax处不拥挤，故人工鱼Xi可根据公式(3)向此方向移动一步。否则，执行觅食行为。

(3)

1.2.4 随机行为

随机行为是当前人工鱼邻域内即(dij< visual)随机选择一个位置并向该方向移动，如公式(4)所示。它是觅食行为的一个缺省行为，而觅食行为是聚群行为和追尾行为的缺省行为，所以最终随机行为是聚群行为和追尾行为的缺省行为。

Xi|next=Xi+step×rand()

(4)

2 粒子群算法(PSO)的移动算子

标准粒子群算法[16～17]的粒子移动算子主要由3个部分决定：

1)惯性部分。它是指粒子当前运动状态的惯性，使单个粒子具有连续的当前运动方向和速度趋势，使优化过程不会因迭代次数的增加而缩小搜索范围，增强粒子全局搜索能力。

2)群体部分。它是指单个粒子有向全局最优位置学习交流的能力，是粒子群内部信息共享的表现，有利于粒子在全局范围内的寻优。

3)记忆认知部分。是指单个粒子受粒子个体历史最优位置的影响，根据自身的位置经验移动，有利于粒子的局部优化。

上述3个部分共同影响粒子的位置更新，不断调整粒子的位置状态[24]。

标准粒子群算法的速度和位置更新公式为：

vid=wvid+c1r1[gbest-xid]+c2r2[pbestid-xid]

(5)

xid=xid+vid

(6)

其中，xi=(xi,1,xi,2,…,xi,D)为粒子i的当前位置，vi=(vi,1,vi,2,…,vi,D) 为粒子(下文为人工鱼)i的速度，pbesti=(pbesti,1,pbesti,2,…,pbesti,D)为粒子i的历史最优位置，gbest为粒子群(下文为人工鱼群)的全局历史最优位置。w为惯性权重，c1、c2为加速因子，r1、r2为[0,1]之间均匀分布的随机数(下同)。

3 改进的人工鱼群算法

3.1 基于粒子群移动算子改进人工鱼基本行为

在标准的人工鱼群算法中，人工鱼在领域内搜索能力很强，人工鱼运动的方向主要由人工鱼在领域内搜索到的较优位置决定，和全局历史最优位置方向与自主意识并无关系，向全局最优位置学习交流能力较弱，自主意识差，导致算法易陷入局部最优解，寻优精度不高。本文模仿粒子群算法中粒子搜索方式对人工鱼群算法3个基本行为进行改进，使人工鱼具有PSO算法中的惯性机制，加强了人工鱼的自主意识，一旦算法暂时陷入局部最优解，也能够因惯性机制，继续探索新区域，提高了发掘潜在较优解的机率，同时具有向全局最优位置和搜索到的较优位置进行学习交流的能力，减小了鱼群搜索的盲目性，保证了算法的收敛。最后类似粒子群算法的粒子记忆机制，人工鱼要记忆个人历史最优位置，在下一步位置更新时要先和个体历史最优位置进行优劣对比，再决定是否进行移动，进一步减小了鱼群游动的盲目性。人工鱼位置更新如图1所示。

图1 人工鱼位置更新示意图

图1中V1代表人工鱼目前保持的速度，让单个人工鱼有持续当前移动速度的能力，使寻优区域不会在迭代的过程中缩小，增强了人工鱼全局寻优的能力；V2代表群体部分产生的速度，是优质位置同伴信息共享产生的向全局历史最优位置游动的速度，有利于人工鱼在全局范围寻优；V3代表认知部分产生的速度，是向搜索到的较优位置的游动速度，有利于人工鱼进行局部寻优。在3个部分速度的影响下，粒子的最终速度为V4。

由于引入拥挤因子，算法的收敛性能并没有很好的改善，在某些情况下，其收敛性能反而会有所下降，且算法复杂度更高[25]，所以本文忽略掉拥挤度因子。

3.1.1 改进的觅食行为

标准觅食行为在当前人工鱼领域内尝试try_number次后，未能找到比当前位置Xi更好的新位置Xj，则随机移动一步。本文算法对此改进是在当前人工鱼领域内尝试try_number次，寻找比个体历史最优位置pbest更好的新位置Xj，即Yj>Ypbest，直至成功，则利用公式(7)、公式(8)进行移动；如果仍不满足，则执行对应的改进随机行为。

Xpreg(i|next)=Xi+vi

(7)

vi=wvi+c1r1[gbest-Xi]+c2r2[Xj-Xi]

(8)

3.1.2 改进的聚群行为

寻找当前人工鱼领域内中心位置处Xc，当Xc比个体历史最优位置pbest更好时，即Yc>Ypbest，则利用公式(9)、公式(10)进行移动，更新人工鱼位置，否则执行改进的觅食行为。

Xswarm(i|next)=Xi+vi

(9)

vi=wvi+c1r1[gbest-Xi]+c2r2[Xc-Xi]

(10)

3.1.3 改进的追尾行为

寻找当前人工鱼领域内最优人工鱼位置Xmax，当Xmax比个体历史最优位置pbest更好时，即Ymax>Ypbest，则利用公式(11)、公式(12)进行移动，更新人工鱼位置；否则执行改进的觅食行为。

Xfollow(i|next)=Xi+vi

(11)

vi=wvi+c1r1[gbest-Xi]+c2r2[Xmax-Xi]

(12)

经过上述基本行为，每条人工鱼会比较“追尾或觅食”“聚群或觅食”这2种组合行为模式更新后函数值大小，较优的则为潜在的较优解作为更新结果。人工鱼群会逐渐向全局最优位置方向移动，而全局最优位置的就是最优解的位置。

3.2 自适应视野和惯性权值

在标准AFSA 中，所有人工鱼的视野 visual 和步长 step都是固定不变的值，这是直接决定算法寻优精度的2个十分重要的参数。在全局探索较优解时，可利用较大的视野和步长充分开拓搜索空间，提高人工鱼的多样性，同时避免陷入局部最优解。然而，步长过大则可能会错过最优解所在区域，同理，在局部搜索时，应缩短步长及视野的大小，加强搜索能力，提高寻优精度[26]。由于本文采用了模拟粒子群移动方式更新鱼群，步长step参数不存在，基本行为移动算子中继承了粒子群算法中的惯性权值w，文献[27]指出，惯性权值w较大有助于全局寻优，反之，则能加强局部寻优能力。因此，本文提出一种非线性自适应视野和惯性权值的策略，进化前期以较大的视野和惯性权值，使算法有较强的全局搜索能力，后期则以较小的视野和惯性权值，使算法增强局部搜索能力以加速收敛到已搜索到的最优解。其中，非线性自适应函数如公式(13)所示，自适应视野及惯性权值分别如公式(14)、公式(15)所示。

(13)

visual=a-a×r+visualmin

(14)

w=b-b×r+wmin

(15)

其中，t为当前迭代次数，T为最大迭代次数，r随着迭代次数t的增加而逐渐变大，k为(0,1)的常数，可通过调整k值大小改变r的变化速率，权衡全局搜索与局部高精度搜索的关系，本文k=0.01,a=10,b=1,visualmin=3,wmin=0.01。

3.3 双策略——2种不同的随机行为

3.3.1 反向学习

反向学习机制由Tizhoosh[23]在2005年提出，是一种应用于群智能算法中的搜索模式，反向学习的基本思想是若一个随机个体较系统最优解的距离偏远，那么这个个体的反向个体离最优解距离较近的概率会大大增加[28]。

基本定义：设x是一个区间[a,b]的实数，则其反向数定义为x′=(a+b)-x。

扩展到鱼群算法反向学习定义：设在D维搜索空间中人工鱼位置信息为x=(x1,x2,…,xD)，其中xi∈[ai,bi],则其反向位置可以表示为x′=(x′1,x′2,…,x′D),其中x′i=(ai+bi)-xi。

3.3.2 改进的随机行为

根据上文人工鱼群算法描述可知，随机行为是人工鱼在视野内随机寻优 try_number 次失败后，执行的缺省行为。因此当随机行为需要被执行时，则说明人工鱼在当前区域陷入局部最优解的可能性较大。而原始随机行为是当前人工鱼在visual 范围内随机选择一个位置并向该方向移动，盲目性较大，本文对此进行了2种改进：1)对聚群行为的缺省行为(随机行为)进行改进，使当前人工鱼进行反向学习，改进后如公式(16)所示；2)对追尾行为的缺省行为(随机行为)进行改进，使当前人工鱼向全局历史最优位置进行学习，改进后如公式(17)所示。改进后的随机行为避免了原始随机行为的盲目性，大大增加了种群的多样性，提升了人工鱼跳出局部最优解的能力，同时提高了算法的稳定性。

(16)

Xi|next=Xi+c1r1[gbest-Xi]

(17)

3.4 P-ADAFSA 算法步骤描述

Step1参数初始化，在解空间随机初始化人工鱼群，并计算每条人工鱼目标函数值。

Step2记录各条鱼当前状态，比较每条人工鱼的函数值大小，选取函数值最优的作为当前最优解记录公告板。

Step3按公式(16)、公式(17)计算人工鱼群视野和惯性权值。

Step4对每条人工鱼依次执行改进的聚群行为和追尾行为，比较两者函数值大小，取使函数值较优的作为更新结果。

Step5计算每条人工鱼的目标函数值，更新个体历史最优解和全局历史最优位置，并将全局历史最优位置的函数值作为最优解记录公告板。

Step6判断是否满足结束条件。若满足，将全局历史最优位置以及最优解输出，否则，跳转到Step3继续。

4 仿真实验与结果分析

4.1 实验设计

为了测试P-ADAFSA的性能，选取了7个典型的连续函数作为测试函数[29]，分别测试算法在15 维及50维情况下的求解能力，仿真实验在Matlab2016b 环境下进行。表1为7个Benchmark测试函数。

表1 7个典型的 Benchmark 函数

表1中，f1是单锋函数，f2是阶跃函数，f3、f4、f5是多峰函数,f6是有无数极值点的函数，f7是一个随机噪声函数。

实验中，为了保证实验结果可靠性，防止实验结果受随机性的影响，每个测试函数都分别独立运行 30次。其中对比算法为 AFSA[1]、IAFSA[19]和OAGMAFSA[22]。对比算法的相关参数设置分别参照对应文献。本文人工鱼群的数量为20，try_number =10，k=0.01，c1=2.005,c2=2.005，初始速度vi为(0,2)的随机数。表2为P-ADAFSA与AFSA、IAFSA、OAGMAFSA算法在15维和50维下的2000次迭代的实验结果。

表2 本文算法与其他算法的性能比较

为了更好地表现P-ADAFSA在7个测试函数进化过程中的收敛情况，本文将P-ADAFSA和其他几种算法在测试函数进化过程的收敛情况进行比较。图2～图8为P-ADAFSA、AFSA、IAFSA与OAGMAFSA 算法在 15 维下的进化曲线对比图。

图2 f1函数进化过程曲线图

图3 f2函数进化过程曲线图

图4 f3函数进化过程曲线图

图5 f4函数进化过程曲线图

图6 f5函数进化过程曲线图

图7 f6函数进化过程曲线图

图8 f7函数进化过程曲线图

4.2 实验结果分析

由表2中数据可知，P-ADAFSA相比较其他算法，有着明显的改进效果，对于单峰函数和多峰函数以及阶跃函数都有着绝对的优势。P-ADAFSA算法在15维和50维度下f1～f6函数求解均能找到全局最优值。其他算法只有在f2函数的测试中，AFSA和OAGMAFSA这2个算法在15维和50维的情况下均能找到全局最优值，IAFSA只在15维的情况下能达到最优值。在f7函数求解中，P-ADAFSA虽未找到理论全局最优值，是因为该函数为随机噪声函数，寻优难度较大，而其中P-ADAFSA的最佳优化值和平均优化值较其他几种算法最小，说明P-ADAFSA寻优精度更高。P-ADAFSA的标准差在7个测试函数中均为最小，说明P-ADAFSA算法的鲁棒性最好。

观察图2～图8可知，P-ADAFSA算法在迭代初期进化曲线能够非常快速地下降，说明P-ADAFSA算法对人工鱼群初始位置要求不高。观察图2～图7可知，P-ADAFSA算法能够快速找到全局最优位置，特别是f2、f3、f4、f5函数，进化到200次之内就已经找到全局最优位置，在f1和f6测试函数中进化到1300次左右可以找到全局最优位置，其中f1单峰函数因其全局最优位置附近较为平滑，所以在算法找到全局最优位置附近，需要较长时间能收敛到函数最优值。f2是阶跃函数，相对较容易找到全局最优位置，所以收敛曲线中P-ADAFSA和OAGMAFSA、IAFSA的成功收敛次数相差不大；f3、f4、f5是多峰函数，有很多局部最优点，反映出P-ADAFSA算法在多峰函数寻优能够迅速跳出局部最优值，并且在找到全局最优位置附近时，有很强的局部高精度寻优能力；而f6函数因其有无数个局部极值点，强烈的震荡性，其他算法在寻优过程中较为起伏，P-ADAFSA因其跳出局部最优能力较强，则较平滑，但f6函数相比其他多峰函数，其局部极值点较多，寻优中成功收敛时间相对较长。而其他算法只有在f2函数能够成功收敛到最优解。观察图8可知，对于f7函数由于优化难度较大，P-ADAFSA算法优化效果不如其他函数那样显著，与IAFSA、OAGMAFSA算法在进化过程前期收敛速度相当，比AFSA算法收敛速度快，但在进化过程后期，收敛精度更高。总体上，P-ADAFSA的性能较AFSA、IAFSA、OAGMAFSA有很大提升，收敛速度更快，寻优精度更高，鲁棒性更强，不易过早收敛。其中AFSA没有考虑局部搜索和全局搜索的关系，迭代过程中视野和步长参数都是固定不变的，算法在后期局部寻优能力差，也没有对全局最优位置信息加以学习，仅仅是对搜索到的较优位置方向进行随机移动，且其随机行为具有很大盲目性，无法保证人工鱼向好的方向移动，其性能最差。IAFSA虽然权衡了局部搜索和全局搜索的关系，并且在觅食行为中直接移动到领域内较优位置，在该环节加快了搜索速度，但其他行为行动较缓慢，向全局最优位置方向学习交流能力为零，同理其随机行为的盲目性无法保证人工鱼向好的方向发展，其性能较差。OAGMAFSA算法较前两者寻优精度有所提高，但在人工鱼群基本行为中过于盲目追逐反向解，提升其全局搜索能力，但是没有考虑人工鱼自身惯性因素，导致人工鱼自主意识很差，一旦陷入局部最优解，而其反向解也不乐观时，跳出该区域就较缓慢。P-ADAFSA算法性能最优，在人工鱼领域内搜索能力强的基础上，利用PSO移动算子的向全局最优位置学习交流能力以及惯性机制提升了算法搜索速度与跳出局部最优的能力，引入自适应视野与惯性权值策略权衡局部搜索与全局搜索关系，寻优精度得到了明显的改善，同时引入反向学习机制和向全局最优位置方向学习交流对随机行为做了2种改变，最终行为选择时选择情况较好的一种，避免了原始随机行为的盲目性，保证了人工鱼向好的方向发展，算法的鲁棒性有很大提升。

为了进一步验证P-ADAFSA在高维空间的求解能力，将P-ADAFSA分别在100维和200维空间下进行30次仿真实验，参数不变，迭代次数为2000，对比的项目包括实验结果的最佳优化值、平均值、标准差、平均迭代次数、成功收敛的次数等项目，表3为其实验结果，“”表示没有成功收敛，数值不存在。

表3 P-ADAFSA算法在100维和200维空间的实验结果

结果表明，算法在100维和200维空间情况下有较好的优化效果，在f1～f6函数测试中，算法仍然能够在2000次进化次数内找到全局最优值，且成功率为100%，在从100维增加到200维空间时，其平均成功收敛迭代次数也未发生太多的变化，f1、f3、f6函数仅仅增加不到5%，f4函数则增加了21.04%，f2、f5函数分别下降3.18%和1.80%。而f7函数在100维和200维空间下平均值和标准差也基本没有太大起伏，甚至在200维空间下其最佳优化值精度更高，说明P-ADAFSA算法具有很强的稳定性，在高维空间求解，其收敛速度与性能依然是可靠的。

5 结束语

本文针对传统人工鱼群算法存在的不足，创新性地将粒子群算法的移动算子和自适应视野与惯性权值策略以及反向学习机制引入AFSA算法中，提出了一种基于粒子群算法自适应双策略的人工鱼群算法P-ADAFSA。该算法提升了人工鱼跳出局部最优解的能力，降低了过早收敛的可能性，同时平衡了全局搜索和局部搜索的关系，大大改善了算法的搜索性能。仿真实验结果表明，P-ADAFSA算法在求解精度、收敛速度以及鲁棒性上均有显著性的优势，对高维问题求解有较好的效果，是一种可行的优化算法。