论文部分内容阅读
【摘 要】针对标准人工鱼群优化算法在迭代过程中易陷入局部最优和后期收敛速度慢的问题，提出一种基于混沌改进的自适应人工鱼群算法。该算法利用混沌序列获得均匀初始化的种群，并在人工鱼群陷入局部极值时对其进行混沌变异操作，增加鱼群的多样性，同时根据食物浓度自适应调节人工鱼步长，提高收敛速度。仿真实验表明，该算法能够有效避免早熟问题，并且具有较快的收敛速度。
【关键词】混沌 局部最优 人工鱼群算法 早熟收敛
人工鱼群算法（Artificial Fish School Algorithm， AFSA）是由李晓磊等人在2002年提出的一种模拟鱼群在自然环境中的生态行为的随机搜索优化算法[1]。该算法通过鱼群的一系列行为找到最优解。由于其算法易实现、可并行处理、鲁棒性好等特点，因而已经成功应用在函数极值估计、神经网络训练、人脸检测与识别等领域[2]。
本文提出一种基于混沌变异的自适应人工鱼群优化算法（Adaptive Artificial Fish Optimization Algorithm Based on Chaotic Mutation， ACMAFO）。该算法利用混沌序列获得均匀初始化的种群，并在人工鱼群陷入局部极值时对其进行混沌变异操作，增加鱼群的多样性，同时根据食物浓度自适应调节人工鱼步长，提高收敛速度。仿真实验结果表明，该算法能够有效避免早熟问题，并且具有较快的收敛速度。
一、基本人工鱼群算法流程
在基本人工鱼群算法中，每条人工鱼都在自己的视野内探索自己的位置状况与其它人工鱼位置状况，通过比较从而选择一种行为。通过一段时间的寻优，人工鱼最终集结在一些局部极值的周围，根据所要解决的问题以及适应函数对人工鱼当前所处的环境进行评价。该算法中的人工鱼首先模拟聚群和追尾行为，通过适应函数的评价更新公告板，人工鱼缺省行为为觅食行为，基本人工鱼群算法的具体描述如下：
Step l：根据所要解决的问题建立搜索域，然后在搜索域内随机产生M个人工鱼个体，然后挑选均匀分布的N个人工鱼个体组成初始群体，初始化人工鱼群规模、每条人工鱼的初始位置、视野和步长、最大试探次数、拥挤度因子、最大迭代次数等参数。
Step 2：计算鱼群中各人工鱼所处状态的食物浓度状况，然后选择浓度最大的个体状态记录到公告板内。
Step 3：各人工鱼通过聚群行为和追尾行为来搜寻最佳食物，人工鱼的缺省行为是觅食行为，通过之间比较选择最优的行为，与公告板中最优记录状态进行比较，如果执行行为后的状态较优则更新公告板记录。
Step 4：判断是否满足终止条件若满足则把最优值输出到公告板记录，算法终止，若不满足则执行Step3。
二、自适应混沌人工鱼群算法
（一）混沌初始化和混沌变异策略
基本的人工鱼群算法虽然具有较好的全局寻优特性，但是面对复杂的问题，易陷入局部最优。针对这种情况，本文提出采用遍历均匀性好的Chen混沌系统，利用其遍历性和初值敏感性的特点，保证人工鱼能够均匀分布在解空间，扩大搜索空间，克服随机序列产生初始种群的不均匀性。
该算法从以下两个方面进行了改进：
1.利用Chen映射初始化人工鱼群，通过Chen映射产生分布均匀的序列和序列，对其反馈进行微小控制，使其在空间上具有互补特性，然后分别初始化鱼群A和鱼群B，提高了计算效率。
2.利用Chen映射分别对陷入局部极值的人工鱼A和B进行混沌变异。当鱼群陷入局部极值时，调用Chen映射，利用和序列分别对鱼群A和B中陷入局部极值的部分个体（一般取10%左右）进行混沌变异。通过混沌变异，陷入局部极值的人工鱼个体有可能得到更好的优秀个体，从而有效避免基本人工鱼群算法易陷入局部极值的问题。
（二） 改进后ACMPSO算法流程
ACMPSO算法流程如下：
Step 1：把人工鱼群均匀的分成两部分A和B，利用混沌系统的x和y序列分别初始化A和B中每条人工鱼的初始位置。然后设置视野和步长、拥挤度因子、最大试探次数、最大迭代次数等参数。
Step 2：分别计算各人工鱼状态的食物浓度，选择最大食物浓度的人工鱼个体状态记录到公告板内。
Step 3：各人工鱼分别模拟改进聚群行为和追尾行为，缺省行为为觅食行为，然后选择最优的行为作为实际执行行为并与公告板记录进行比较，若优于公告板记录则以自身替换公告板记录。
Step 4：检查算法是否停滞，若是，则产生新的混沌序列，替代处于最优值及其附近的部分人工鱼（一般取10%左右）。
Step 5：判断是否满足终止条件若满足则输出公告板记录，算法终止，若不满足则执行 Step3。
三、仿真实验结果及分析
本实验是以求2个测试函数的最小值为例。两个测试函数为：
（一）Rastrigin函数：
，其中，，该函数是个多峰值的函数，在处取得全局最小值0。在范围内大约有个局部极小点，此函数同Griewank函数类似，也是一种典型的非线性的多模态函数，峰形呈高低起伏不定跳跃性的出现，所以很难优化查找到全局最优值。
（二） Shubert函数：
，其中，，。该函数是二维的复杂函数，有18个全局最小值。
Chen混沌系统的初值为x=5，y=-5，z=1。人工鱼群规模为50，鱼群A和B规模分别为25，觅食行为中重复次数。表3.1列出了基本人工鱼群（AFSA） 和 基于Chen 混沌的人工鱼群（ACMPSO）求解函数所得的寻优结果。
表3.1 两种算法对和函数
函数 参数及说明 项目 AFSA ACMPSO 人工鱼数50 最优值 3.83E-07 1.40E-17
极小值0 均值 8.13E-03 7.94E-08
人工鱼数50 最优值 -186.6102 -186.7309
极小值-186.7309 均值 -186.5258 -186.7309
由表3.1可知，ACMPSO算法无论在最优值还是平均值上都比AFSA算法法性能优，且改进后的算法收敛速度也比改进前加快。
四、结 语
针对基本人工鱼群算法易陷入局部极值的问题，本文提出了一种基于Chen映射的混沌人工鱼群算法ACMPSO。该算法首先利用混沌序列均匀地初始化人工鱼群，然后通过混沌变异使得陷入局部极值的人工鱼进行混沌扰动，从而向全局最优值移动。本文把人工鱼群分为两部分A和B，利用Chen映射的和序列同时对人工鱼群进行初始化，在陷入局部极值时利用Chen映射进行混沌变异，并通过仿真实验验证了所提出算法的正确性和有效性。
参考文献：
[1]R.Hua. Study of adaptive chaos embedded particle swarm optimiza tion algorithm based on skew tent map[C]// Proceedings of Intelligent Control and Information Processing（ICICIP），2010：316-321.
[2]祈俊，赵慧雅，李明.基于双混沌映射改进的人工鱼群算法[J].计算机应用与软件，2012，29（9）：230-233.
[3]Y. Q. Zhou， Z. C. Xie. Improved artificial fish-school swarm algorithm for solving TSP[J]. Systems Engineering and Electronics， 2009， 31： 1458-1461.
[4]Y. Cai. Artificial fish school algorithm applied in a combinatorial optimization problem[J]. Intelligent Systems and Applications， 2010， 2（1）：37-43.
[5]于海涛，贾美娟，王慧强等.基于人工鱼群的优化K-means聚类算法[J].计算机科学，2012，39（12）：60-64.
[6]B. Alatas， E. Akin， A. B. Ozer. Chaos embedded particle swarm optimization algorithms[J]. Chaos， Solitons & Fractals， 2009， 40（4）：1715-1734.
[7]曲良东，何登旭.一种混沌人工鱼群优化算法[J].计算机工程与应用，2010，46（22）：40-42.
[8]陈建荣， 王勇. 一种人工鱼算法与捕鱼算法相结合的优化方法[J]. 计算机应用与软件， 2011， 28（4）：196-1
【关键词】混沌 局部最优 人工鱼群算法 早熟收敛
人工鱼群算法（Artificial Fish School Algorithm， AFSA）是由李晓磊等人在2002年提出的一种模拟鱼群在自然环境中的生态行为的随机搜索优化算法[1]。该算法通过鱼群的一系列行为找到最优解。由于其算法易实现、可并行处理、鲁棒性好等特点，因而已经成功应用在函数极值估计、神经网络训练、人脸检测与识别等领域[2]。
本文提出一种基于混沌变异的自适应人工鱼群优化算法（Adaptive Artificial Fish Optimization Algorithm Based on Chaotic Mutation， ACMAFO）。该算法利用混沌序列获得均匀初始化的种群，并在人工鱼群陷入局部极值时对其进行混沌变异操作，增加鱼群的多样性，同时根据食物浓度自适应调节人工鱼步长，提高收敛速度。仿真实验结果表明，该算法能够有效避免早熟问题，并且具有较快的收敛速度。
一、基本人工鱼群算法流程
在基本人工鱼群算法中，每条人工鱼都在自己的视野内探索自己的位置状况与其它人工鱼位置状况，通过比较从而选择一种行为。通过一段时间的寻优，人工鱼最终集结在一些局部极值的周围，根据所要解决的问题以及适应函数对人工鱼当前所处的环境进行评价。该算法中的人工鱼首先模拟聚群和追尾行为，通过适应函数的评价更新公告板，人工鱼缺省行为为觅食行为，基本人工鱼群算法的具体描述如下：
Step l：根据所要解决的问题建立搜索域，然后在搜索域内随机产生M个人工鱼个体，然后挑选均匀分布的N个人工鱼个体组成初始群体，初始化人工鱼群规模、每条人工鱼的初始位置、视野和步长、最大试探次数、拥挤度因子、最大迭代次数等参数。
Step 2：计算鱼群中各人工鱼所处状态的食物浓度状况，然后选择浓度最大的个体状态记录到公告板内。
Step 3：各人工鱼通过聚群行为和追尾行为来搜寻最佳食物，人工鱼的缺省行为是觅食行为，通过之间比较选择最优的行为，与公告板中最优记录状态进行比较，如果执行行为后的状态较优则更新公告板记录。
Step 4：判断是否满足终止条件若满足则把最优值输出到公告板记录，算法终止，若不满足则执行Step3。
二、自适应混沌人工鱼群算法
（一）混沌初始化和混沌变异策略
基本的人工鱼群算法虽然具有较好的全局寻优特性，但是面对复杂的问题，易陷入局部最优。针对这种情况，本文提出采用遍历均匀性好的Chen混沌系统，利用其遍历性和初值敏感性的特点，保证人工鱼能够均匀分布在解空间，扩大搜索空间，克服随机序列产生初始种群的不均匀性。
该算法从以下两个方面进行了改进：
1.利用Chen映射初始化人工鱼群，通过Chen映射产生分布均匀的序列和序列，对其反馈进行微小控制，使其在空间上具有互补特性，然后分别初始化鱼群A和鱼群B，提高了计算效率。
2.利用Chen映射分别对陷入局部极值的人工鱼A和B进行混沌变异。当鱼群陷入局部极值时，调用Chen映射，利用和序列分别对鱼群A和B中陷入局部极值的部分个体（一般取10%左右）进行混沌变异。通过混沌变异，陷入局部极值的人工鱼个体有可能得到更好的优秀个体，从而有效避免基本人工鱼群算法易陷入局部极值的问题。
（二） 改进后ACMPSO算法流程
ACMPSO算法流程如下：
Step 1：把人工鱼群均匀的分成两部分A和B，利用混沌系统的x和y序列分别初始化A和B中每条人工鱼的初始位置。然后设置视野和步长、拥挤度因子、最大试探次数、最大迭代次数等参数。
Step 2：分别计算各人工鱼状态的食物浓度，选择最大食物浓度的人工鱼个体状态记录到公告板内。
Step 3：各人工鱼分别模拟改进聚群行为和追尾行为，缺省行为为觅食行为，然后选择最优的行为作为实际执行行为并与公告板记录进行比较，若优于公告板记录则以自身替换公告板记录。
Step 4：检查算法是否停滞，若是，则产生新的混沌序列，替代处于最优值及其附近的部分人工鱼（一般取10%左右）。
Step 5：判断是否满足终止条件若满足则输出公告板记录，算法终止，若不满足则执行 Step3。
三、仿真实验结果及分析
本实验是以求2个测试函数的最小值为例。两个测试函数为：
（一）Rastrigin函数：
，其中，，该函数是个多峰值的函数，在处取得全局最小值0。在范围内大约有个局部极小点，此函数同Griewank函数类似，也是一种典型的非线性的多模态函数，峰形呈高低起伏不定跳跃性的出现，所以很难优化查找到全局最优值。
（二） Shubert函数：
，其中，，。该函数是二维的复杂函数，有18个全局最小值。
Chen混沌系统的初值为x=5，y=-5，z=1。人工鱼群规模为50，鱼群A和B规模分别为25，觅食行为中重复次数。表3.1列出了基本人工鱼群（AFSA） 和 基于Chen 混沌的人工鱼群（ACMPSO）求解函数所得的寻优结果。
表3.1 两种算法对和函数
函数 参数及说明 项目 AFSA ACMPSO 人工鱼数50 最优值 3.83E-07 1.40E-17
极小值0 均值 8.13E-03 7.94E-08
人工鱼数50 最优值 -186.6102 -186.7309
极小值-186.7309 均值 -186.5258 -186.7309
由表3.1可知，ACMPSO算法无论在最优值还是平均值上都比AFSA算法法性能优，且改进后的算法收敛速度也比改进前加快。
四、结 语
针对基本人工鱼群算法易陷入局部极值的问题，本文提出了一种基于Chen映射的混沌人工鱼群算法ACMPSO。该算法首先利用混沌序列均匀地初始化人工鱼群，然后通过混沌变异使得陷入局部极值的人工鱼进行混沌扰动，从而向全局最优值移动。本文把人工鱼群分为两部分A和B，利用Chen映射的和序列同时对人工鱼群进行初始化，在陷入局部极值时利用Chen映射进行混沌变异，并通过仿真实验验证了所提出算法的正确性和有效性。
参考文献：
[1]R.Hua. Study of adaptive chaos embedded particle swarm optimiza tion algorithm based on skew tent map[C]// Proceedings of Intelligent Control and Information Processing（ICICIP），2010：316-321.
[2]祈俊，赵慧雅，李明.基于双混沌映射改进的人工鱼群算法[J].计算机应用与软件，2012，29（9）：230-233.
[3]Y. Q. Zhou， Z. C. Xie. Improved artificial fish-school swarm algorithm for solving TSP[J]. Systems Engineering and Electronics， 2009， 31： 1458-1461.
[4]Y. Cai. Artificial fish school algorithm applied in a combinatorial optimization problem[J]. Intelligent Systems and Applications， 2010， 2（1）：37-43.
[5]于海涛，贾美娟，王慧强等.基于人工鱼群的优化K-means聚类算法[J].计算机科学，2012，39（12）：60-64.
[6]B. Alatas， E. Akin， A. B. Ozer. Chaos embedded particle swarm optimization algorithms[J]. Chaos， Solitons & Fractals， 2009， 40（4）：1715-1734.
[7]曲良东，何登旭.一种混沌人工鱼群优化算法[J].计算机工程与应用，2010，46（22）：40-42.
[8]陈建荣， 王勇. 一种人工鱼算法与捕鱼算法相结合的优化方法[J]. 计算机应用与软件， 2011， 28（4）：196-1