论文部分内容阅读
摘 要：为解决传统人工鱼群算法在求解高维问题时候，存在收敛速度慢且收敛精度不高的问题，提出一种多算法融合的改进人工鱼群算法。通过引入粒子群优化算法的学习机制和遗传算法的交叉变异迭代，提升算法的收敛速度和收敛精度。最后通过仿真实验，验证了PSO-GA-AFSA算法在高纬度寻优中具有更优的性能，同时又具有与传统方法相融合的基础，有着良好的应用前景。
关键词：粒子群优化算法;人工鱼群算法;遗传算法;混合算法;算法融合
Abstract：In order to solve the problem of slow convergence speed and low convergence accuracy in solving high-dimensional problems of traditional artificial fish swarm calculations，an improved artificial fish swarm algorithm（PSO-GA-AFSA）with multiple algorithms fusion is proposed. By introducing the learning mechanism of PSO and the cross mutation iteration of GA，the convergence speed and accuracy of the algorithm are improved. Finally，through simulation experiments，it is verified that the PSO-GA-AFSA algorithm has better performance in high-latitude optimization，and at the same time has the basis of fusion with traditional methods，and has a good application prospect.
Keywords：PSO;AFSA;GA;hybrid algorithm;algorithm fusion
0 引 言
最优化问题涉及国民经济的各个领域，例如：工业、农业、通信、化工、交通、国防等诸多领域，其对于推动社会经济发展的重要性不言而喻。根据作者多年从事的兴趣爱好研究得出：传统的优化方法如黄金分割法、梯度下降法、拟牛顿法等，在面对这些复杂性高、非线性、变量维度高、多约束条件的项目问题时，不管在计算速度、结果的精度、鲁棒性等方面远远不能满足解决当前问题的需求。传统智能算法如遗传算法，模拟退火算法等虽然能较好解决优化问题，但也存在收敛速度慢，收敛精度低的问题。基于此，本文提出了以人工魚群算法（Artificial Fish Swarms Algorithm，AFSA）为框架，融合粒子群算法和遗传算法的新型算法，同时解决收敛速度慢和精度低的问题。
1 粒子群优化算法
粒子群优化（Particle Swarm Optimization，PSO）是Kennedy和Eberhart受人工生命研究结果的启发、通过模拟鸟群觅食过程中的迁徙和群聚行为而提出的一种基于群体智能的全局随机搜索算法。
在算法的进化过程中，粒子需要一直向两个极值进行学习：一个是到个体历史最优位置，即粒子自身迭代到当前位置时最优的位置记录;另一个是种群历史最优位置，即整个种群发展到当前出现过的全局最优位置。粒子通过这两个“经验”进行学习，不断的改变自身的飞行方向和飞行速度，其速度和位置更新公式为：
其中， 为第t次迭代时候第id个粒子的速度，pid为第id个粒子的历史最优位置，pgd为当前全局最优的位置， 为第t次迭代时候第id个粒子的位置信息，r1，r2为（0，1）之间的随机数，c1和c2统称为学习因子，c1学习因子主要负责该粒子向过去学习的权重，c2主要负责该粒子向全部他人学习的权重，其值一般取值为c1+c2=2。
2 遗传算法
遗传算法（Genetic Algorithm，GA）是以达尔文的进化论和孟德尔的遗传变异理论为科学理论依据的算法。
基础遗传算法的遗传操作主要有三种：选择操作、杂交操作和变异操作。接下来分别对这三种操作进行详细介绍，以下的方法都在实数编码的方式下进行。
2.1 选择操作
选择操作（selection）提供了遗传算法种群进化的驱动力，其作用是保证种群中的优良基因能延续遗传给下一代，提高后代的适应能力，从而提高遗传算法的全局收敛性，使算法收敛于全局最优解。
2.2 交叉操作
交叉操作（crossover）通常先按照一定的选择机制从群体中选择两个优秀的父辈个体，然后按照一定交叉策略来交换两个个体的某个或某些位的基因信息。交叉算子的设计对遗传算法的影响非常大，如果交叉算子涉及的基因位数太小，即基因重组减少，就不利于较优后代的产生，如果交叉算子太过于单一，也会造成算法搜索能力的减弱。因此交叉算子的制定需要根据实际问题来进行调整。
2.3 变异操作
变异操作（mutation）可以增强算法的局部搜索能力并且也能很好的维持群体的多样性，帮助算法逃离局部极值点。交叉和变异相互配合，共同完成对搜索空间的全局搜索和局部搜索，从而使遗传算法能够以良好的搜索性能完成最优化问题的寻优过程。
3 AFSA原理
在AFSA中，人工鱼有3种基本行为：觅食、聚群、追尾。
3.1 觅食行为 在求极大值问题中，设第i条人工鱼在当前环境位置状态向量为Xi，适应度值为Yi，在视野范围Visual范围内随机选择下一个位置的状态向量为Xj，适应度值为Yj，若Yj>Yi，则该条人工鱼朝着食物浓度更多（即可行解空间较优）的方向游动一步;如若Yj 3.2 聚群行为
设第i只人工鱼在当前环境状态向量为Xi，适应度值为Yi，其视野范围内（即di，jδYi（δ为拥挤度因子），表明鱼群中央食物较丰富并且视野范围内的群体不太拥挤，此时该条人工鱼朝鱼群中央位置方向游动，否则执行觅食行为。
3.3 追尾行为
设第i只人工鱼在当前状态为Xi，适应度值为Yi，其视觉范围内（即di，jδYi（δ为拥挤度因子），表明人工鱼Xj在该环境位置状态下食物浓度较为丰盛并且该最优个体鱼周边不太拥挤，此时该人工鱼朝Xj的方向前进一步;否则执行觅食行为。
4 多算法融合人工鱼群算法
结合上面对各项算法的优劣势的分析，本文提出了一种基于PSO和GA多算法融合的人工鱼群智能优化算法（PSO-GA-AFSA）。为进一步提高算法的收敛速度，将PSO算法中的“社学认知”这一特点，引入到人工鱼群中，让鱼群在每次做完行为选择之后，同步向种群全体中最优个体进行学习，让鱼群中的所有个体都具有朝最优解方向的趋向性;为进一步克服算法陷入局部极值并增加算法的探索能力，将遗传算法引入到人工鱼群当中，并将该算法作为鱼群的一个算子，鱼群的繁殖遵循“精英繁殖策略”，即每一次迭代只有种群中适应度最高的个体，才有机会和其他人工鱼进行交叉变异，即增强种群的多样性也将上一代种群最优良个体的基因保留了下来;最后为了增加算法的收敛精度，为人工鱼群引入依赖于迭代情况的自适应算子，让算法在前期能以较大的步长和视野进行探索，在后期以很小的步长和视野进行探索，以增加收敛精度。PSO-GA-AFSA算法流程为：
（1）设定算法参数包括人工鱼条数为N，视野为V，步长为S，拥挤度因子为δ，最大尝试次数为try_number，最大迭代次数为Tmax，学习参数为c1、c2;
（2）计算适应度值，选出最优个体，并将最优个体更新到公告板上;
（3）鱼群模拟进行觅食，聚群，追尾行为，选择最优行为后，结合PSO进行行为更新;
（4）最优个体和其他个体进行交叉变异并更新种群;
（5）更新种群适应度值并更新公告板;
（6）所有人工鱼新型更新完成之后，判断是否达到最大迭代次数，如果否，则转到（3）继续，否则结束算法。
5 仿真结果与分析
本文分别用4个多维度函数Sphere、Ackley、Levy、Griewank在20维的高维条件下测试算法的性能，并与自适应人工鱼群和粒子群算法进行性能比较。表1展示了本文算法和AAFAS算法，PSO算法在4个测试函数下的最好，平均和最坏的变现情况。图1展示了本文算法和其他算法的迭代速度对比。
从表1可以看出，本文提出的算法在收敛精度上面高于其他两个算法很多个数量级，同时通过图1可以明显看出，混合算法在收敛的速度上面均优于或者等于其他两个算法。
6 结 论
针对AFSA全局寻优能力不足，最后寻优精度低的问题，本文通过引入PSO的“自我认知”和“社会认知”来提升AFSA的全局寻优能力，同时引入遗传算法的概念让鱼群能一直保持较高的多样性，并且让算法具有较好的性能稳定性。
参考文献：
[1] 吴爱燕.人工智能的未来与挑战 [J].唐山学院学报，2009，22（6）：69-71+100.
[2] BONABEAU E，DORIGO M，THERAULAZ G.Inspiration for optimization from social insect behavior [J].Nature，2000，406（6791）：39-42.
[3] 张梅凤.人工鱼群智能优化算法的改进及应用研究 [D].大连：大连理工大学，2008.
[4] 陈斐.改进的人工鱼群算法分析与研究 [D].西安：西安电子科技大学，2012.
[5] 李晓磊.一种新型的智能优化方法-人工魚群算法 [D].杭州：浙江大学，2003.
[6] 范玉军，王冬冬，孙明明.改进的人工鱼群算法 [J].重庆师范大学学报（自然科学版），2007，24（3）：23-26.
[7] 张梅凤.人工鱼群智能优化算法的改进及应用研究 [D].大连：大连理工大学，2008.
[8] 王培崇，雷凤君，钱旭.改进人工鱼群算法及其收敛性分析 [J].科学技术与工程，2013，13（3）：616-620.
[9] 葛君伟，郭强，方义秋.一种基于改进蚁群算法的多目标优化云计算任务调度策略 [J].微电子学与计算机，2017，34（11）：63-67.
作者简介：金晓波（1992—），男，汉族，浙江台州人，硕士研究生，研究方向：大数据和智能优化算法。
关键词：粒子群优化算法;人工鱼群算法;遗传算法;混合算法;算法融合
Abstract：In order to solve the problem of slow convergence speed and low convergence accuracy in solving high-dimensional problems of traditional artificial fish swarm calculations，an improved artificial fish swarm algorithm（PSO-GA-AFSA）with multiple algorithms fusion is proposed. By introducing the learning mechanism of PSO and the cross mutation iteration of GA，the convergence speed and accuracy of the algorithm are improved. Finally，through simulation experiments，it is verified that the PSO-GA-AFSA algorithm has better performance in high-latitude optimization，and at the same time has the basis of fusion with traditional methods，and has a good application prospect.
Keywords：PSO;AFSA;GA;hybrid algorithm;algorithm fusion
0 引 言
最优化问题涉及国民经济的各个领域，例如：工业、农业、通信、化工、交通、国防等诸多领域，其对于推动社会经济发展的重要性不言而喻。根据作者多年从事的兴趣爱好研究得出：传统的优化方法如黄金分割法、梯度下降法、拟牛顿法等，在面对这些复杂性高、非线性、变量维度高、多约束条件的项目问题时，不管在计算速度、结果的精度、鲁棒性等方面远远不能满足解决当前问题的需求。传统智能算法如遗传算法，模拟退火算法等虽然能较好解决优化问题，但也存在收敛速度慢，收敛精度低的问题。基于此，本文提出了以人工魚群算法（Artificial Fish Swarms Algorithm，AFSA）为框架，融合粒子群算法和遗传算法的新型算法，同时解决收敛速度慢和精度低的问题。
1 粒子群优化算法
粒子群优化（Particle Swarm Optimization，PSO）是Kennedy和Eberhart受人工生命研究结果的启发、通过模拟鸟群觅食过程中的迁徙和群聚行为而提出的一种基于群体智能的全局随机搜索算法。
在算法的进化过程中，粒子需要一直向两个极值进行学习：一个是到个体历史最优位置，即粒子自身迭代到当前位置时最优的位置记录;另一个是种群历史最优位置，即整个种群发展到当前出现过的全局最优位置。粒子通过这两个“经验”进行学习，不断的改变自身的飞行方向和飞行速度，其速度和位置更新公式为：
其中， 为第t次迭代时候第id个粒子的速度，pid为第id个粒子的历史最优位置，pgd为当前全局最优的位置， 为第t次迭代时候第id个粒子的位置信息，r1，r2为（0，1）之间的随机数，c1和c2统称为学习因子，c1学习因子主要负责该粒子向过去学习的权重，c2主要负责该粒子向全部他人学习的权重，其值一般取值为c1+c2=2。
2 遗传算法
遗传算法（Genetic Algorithm，GA）是以达尔文的进化论和孟德尔的遗传变异理论为科学理论依据的算法。
基础遗传算法的遗传操作主要有三种：选择操作、杂交操作和变异操作。接下来分别对这三种操作进行详细介绍，以下的方法都在实数编码的方式下进行。
2.1 选择操作
选择操作（selection）提供了遗传算法种群进化的驱动力，其作用是保证种群中的优良基因能延续遗传给下一代，提高后代的适应能力，从而提高遗传算法的全局收敛性，使算法收敛于全局最优解。
2.2 交叉操作
交叉操作（crossover）通常先按照一定的选择机制从群体中选择两个优秀的父辈个体，然后按照一定交叉策略来交换两个个体的某个或某些位的基因信息。交叉算子的设计对遗传算法的影响非常大，如果交叉算子涉及的基因位数太小，即基因重组减少，就不利于较优后代的产生，如果交叉算子太过于单一，也会造成算法搜索能力的减弱。因此交叉算子的制定需要根据实际问题来进行调整。
2.3 变异操作
变异操作（mutation）可以增强算法的局部搜索能力并且也能很好的维持群体的多样性，帮助算法逃离局部极值点。交叉和变异相互配合，共同完成对搜索空间的全局搜索和局部搜索，从而使遗传算法能够以良好的搜索性能完成最优化问题的寻优过程。
3 AFSA原理
在AFSA中，人工鱼有3种基本行为：觅食、聚群、追尾。
3.1 觅食行为 在求极大值问题中，设第i条人工鱼在当前环境位置状态向量为Xi，适应度值为Yi，在视野范围Visual范围内随机选择下一个位置的状态向量为Xj，适应度值为Yj，若Yj>Yi，则该条人工鱼朝着食物浓度更多（即可行解空间较优）的方向游动一步;如若Yj
设第i只人工鱼在当前环境状态向量为Xi，适应度值为Yi，其视野范围内（即di，j
3.3 追尾行为
设第i只人工鱼在当前状态为Xi，适应度值为Yi，其视觉范围内（即di，j
4 多算法融合人工鱼群算法
结合上面对各项算法的优劣势的分析，本文提出了一种基于PSO和GA多算法融合的人工鱼群智能优化算法（PSO-GA-AFSA）。为进一步提高算法的收敛速度，将PSO算法中的“社学认知”这一特点，引入到人工鱼群中，让鱼群在每次做完行为选择之后，同步向种群全体中最优个体进行学习，让鱼群中的所有个体都具有朝最优解方向的趋向性;为进一步克服算法陷入局部极值并增加算法的探索能力，将遗传算法引入到人工鱼群当中，并将该算法作为鱼群的一个算子，鱼群的繁殖遵循“精英繁殖策略”，即每一次迭代只有种群中适应度最高的个体，才有机会和其他人工鱼进行交叉变异，即增强种群的多样性也将上一代种群最优良个体的基因保留了下来;最后为了增加算法的收敛精度，为人工鱼群引入依赖于迭代情况的自适应算子，让算法在前期能以较大的步长和视野进行探索，在后期以很小的步长和视野进行探索，以增加收敛精度。PSO-GA-AFSA算法流程为：
（1）设定算法参数包括人工鱼条数为N，视野为V，步长为S，拥挤度因子为δ，最大尝试次数为try_number，最大迭代次数为Tmax，学习参数为c1、c2;
（2）计算适应度值，选出最优个体，并将最优个体更新到公告板上;
（3）鱼群模拟进行觅食，聚群，追尾行为，选择最优行为后，结合PSO进行行为更新;
（4）最优个体和其他个体进行交叉变异并更新种群;
（5）更新种群适应度值并更新公告板;
（6）所有人工鱼新型更新完成之后，判断是否达到最大迭代次数，如果否，则转到（3）继续，否则结束算法。
5 仿真结果与分析
本文分别用4个多维度函数Sphere、Ackley、Levy、Griewank在20维的高维条件下测试算法的性能，并与自适应人工鱼群和粒子群算法进行性能比较。表1展示了本文算法和AAFAS算法，PSO算法在4个测试函数下的最好，平均和最坏的变现情况。图1展示了本文算法和其他算法的迭代速度对比。
从表1可以看出，本文提出的算法在收敛精度上面高于其他两个算法很多个数量级，同时通过图1可以明显看出，混合算法在收敛的速度上面均优于或者等于其他两个算法。
6 结 论
针对AFSA全局寻优能力不足，最后寻优精度低的问题，本文通过引入PSO的“自我认知”和“社会认知”来提升AFSA的全局寻优能力，同时引入遗传算法的概念让鱼群能一直保持较高的多样性，并且让算法具有较好的性能稳定性。
参考文献：
[1] 吴爱燕.人工智能的未来与挑战 [J].唐山学院学报，2009，22（6）：69-71+100.
[2] BONABEAU E，DORIGO M，THERAULAZ G.Inspiration for optimization from social insect behavior [J].Nature，2000，406（6791）：39-42.
[3] 张梅凤.人工鱼群智能优化算法的改进及应用研究 [D].大连：大连理工大学，2008.
[4] 陈斐.改进的人工鱼群算法分析与研究 [D].西安：西安电子科技大学，2012.
[5] 李晓磊.一种新型的智能优化方法-人工魚群算法 [D].杭州：浙江大学，2003.
[6] 范玉军，王冬冬，孙明明.改进的人工鱼群算法 [J].重庆师范大学学报（自然科学版），2007，24（3）：23-26.
[7] 张梅凤.人工鱼群智能优化算法的改进及应用研究 [D].大连：大连理工大学，2008.
[8] 王培崇，雷凤君，钱旭.改进人工鱼群算法及其收敛性分析 [J].科学技术与工程，2013，13（3）：616-620.
[9] 葛君伟，郭强，方义秋.一种基于改进蚁群算法的多目标优化云计算任务调度策略 [J].微电子学与计算机，2017，34（11）：63-67.
作者简介：金晓波（1992—），男，汉族，浙江台州人，硕士研究生，研究方向：大数据和智能优化算法。