樊友洪, 邓 韧, 李生林, 罗凯文, 郭宇栋



基于混沌遗传算子的人工鱼群算法①

樊友洪, 邓 韧, 李生林, 罗凯文, 郭宇栋

(中国人民解放军后勤工程学院, 重庆 401331)

为提高人工鱼群算法的计算精度和收敛速度, 在全局版人工鱼群算法的基础上, 利用混沌遗传算子, 增加鱼群迭代的混沌扰动以避免局部极值陷阱的同时较大提高了鱼群整体的优化效果和计算精度, 加快了算法收敛速度. 仿真结果表明, 该算法有效可行.

人工鱼群; 混沌; 遗传算法

人工鱼群算法是由李晓磊[1]等人提出的一种群智能随机全局优化技术, 它模拟自然界中鱼的集群游弋觅食行为, 通过群鱼相互间的自治协作完成全局寻优的过程, 具有算法简单易实现, 可全局寻优, 并具有初值不敏感, 鲁棒性强的特点. 但AFSA 算法搜索效率较低, 原因有: 一是人工鱼群可视域的限制使算法易于进入局部陷阱; 二是当寻优的区域较大或处于变化平坦的区域时收敛于全局最优解的速度减慢、搜索性能劣化, 甚至会陷入局部最优; 三是算法一般在优化初期收敛快, 后期因步长等原因收敛往往较慢, 有时求解精度不高[2,3]. 本文提出一种基于混沌遗传算子的人工鱼群算法来提高收敛速度和计算精度.

1　基本人工鱼群算法精度与效率

AFSA中, 算法精度和算法效率是一对矛盾体, 其关键在于人工鱼的视野和步长的设定. 基本人工鱼群算法中, 人工鱼的视野和步长是固定值, 如果视野和步长设定较大, 算法全局搜索能力强并能快速收敛, 但在收敛后期则会出现人工鱼在最优值附近来回振荡的现象; 如果视野和步长设定较小, 算法收敛速度慢, 虽然可以提高收敛精度, 但在多峰极值的情况下, 很容易陷入局部极值而难以获得真正的最优解[4]. 为此, 一些研究学者针对这些缺陷做出了改进, 如张梅凤[5]等提出了基于生境的人工鱼群算法, 较好解决了多峰问题, 但步骤比较繁琐; 刘彦君[6]、许恒迎[7]等通过自适应地改变人工鱼的视野和步长提高了寻优精度, 但是易陷入局部极值; 王联国[8]提出了全局版人工鱼群算法, 提高了运算速度, 但目标的寻优精度有待提高; 祁俊[9]等提出基于双混沌映射改进的人工鱼群算法, 利用混沌搜索的遍历性和初值敏感性, 使得陷入局部极值的人工鱼群跳出陷阱, 但运算速度较慢; M Tuba[10]等尝试利用多线程技术提高人工鱼群算法精度, 但多线程协调和任务分配增加了算法的复杂度; Y. Y. Wang[11]等将人工鱼群算法与群搜索优化算法结合, 提高了寻优精度, 但收敛速度有待提高.

本文在这些学者的研究成果之上, 结合混沌遗传算子和自适应视野步长改变算法, 提出一种基于混沌遗传算子的人工鱼群算法(Chaotic Genetic Artificial Fish Swarm Algorithm——CGAFSA)来提高收敛速度和计算精度. 该算法一方面结合遗传算法, 保留和繁殖人工鱼群中优秀的人工鱼, 使得最终整个鱼群的优良率得到大幅提高; 另一方面采用混沌算法提高人工鱼群初始化的均布性和遗传变异的随机性, 可以增强算法全局寻优的能力.

2　基于混沌遗传算子的人工鱼群算法

2.1混沌遗传算子

混沌遗传算子是遗传算法中加入混沌变量进行变异以获取子代的算子, 本文在基本人工鱼群算法的基础上引入遗传算法和混沌遗传算子, 目的是在不影响收敛性的基础上, 增加鱼群迭代的混沌扰动, 尽量避免局部极值陷阱, 加快寻优速度.

2.2基于混沌遗传算子的人工鱼行为描述

2.2.1混沌初始化行为

基本人工鱼群算法虽然具有初值不敏感, 鲁棒性强的特点, 但是如果人工鱼群初始化尽量的均匀化的分布在可能的解空间, 可以有效地提高寻找最优解的效率. 利用混沌算法的遍历性产生分布均匀的人工鱼群, 可以得到质量较好的初始解群, 较大提高人工鱼群寻优的计算效率. 本文采用Tent映射产生初始的人工鱼群, 其映射方程为:

2.2.2聚群行为

2.2.3追尾行为

2.2.4觅食行为

2.2.5遗传行为

基本人工鱼群算法并不模拟鱼群的生态遗传行为, 但生物遗传是物竞天择、适者生存的重要因素, 遗传算法在最优化问题上的广泛应用说明遗传行为的独特性和可行性; 因此本文纳入遗传算子等来模拟鱼群的遗传行为. 设,为人工鱼群遗传迭代次数,为第代人工鱼群总体食物浓度,为第代人工鱼群平均食物浓度, 第代人工鱼单体获取食物浓度水平为. 第代人工鱼群以单体获取食物浓度水平高的前条人工鱼复制产生其子代, 用以进行聚群和追尾等行为.的计算方式, 最大化问题时如式(6):

最小化问题时如式(7):

2.2.6变异行为

生物基因的变异行为是造就生物多样性的重要因素, 人工鱼群利用变异行为可以对寻优过程实施扰动, 可以更好地逃离局部最优解, 达到全局寻优的目的. 第代人工鱼群, 对于单体获取食物浓度水平较低的后条人工鱼, 利用混沌变异算子获取子代.的计算方式, 最大化问题时如式(8):

最小化问题时如式(9):

混沌变异算子如式(10):

2.2.7对人工鱼群视野和步长的改变

根据文献[12]方法对人工鱼的视野和步长进行调整:

2.2.8公告板

算法中定义了公告板, 用来记录最优人工鱼个体的状态. 每条人工鱼在寻优过程中, 行动完毕将自身的当前状态与公告板的状态进行比较, 如果优于公告板状态, 就用自身状态更新公告板的状态, 否则公告板的状态保持不变, 这样当整个算法迭代结束后, 公告板中记录的状态就是最优个体的状态.

2.2.9算法流程

Step2: 利用Tent映射混沌初始化人工鱼群;

Step3: 计算人工鱼个体食物浓度, 以最优个体状态更新公告板;

Step5: 计算人工鱼群总体食物浓度, 平均食物浓度水平及人工鱼个体食物浓度水平并排序;

3　仿真试验及分析

本文实验环境为Windows 7, Matlab R, 6.55a, 实验硬件平台采用Intel Core2 CPU, 主频为2.10GHz, 内存2GB. 选用三个经典测试函数进行实验:

Square Sum Function:

Rastrigin Function:

Griewank Function:

本文主要采用文献[4]中的GAFSA和CGAFSA两种算法进行对比实验.

3.1参数给定

3.2 实验结果

表1 两种优化算法计算结果

图1 函数平均最小值的进化曲线

图2 函数最小值的进化曲线

图3 函数平均最小值的进化曲线

图4 函数最小值的进化曲线

图5 函数平均最小值的进化曲线

图6 函数最小值的进化曲线

4　结语

为提高人工鱼群算法的计算精度和收敛速度, 本文在全局版人工鱼群算法的基础上, 利用混沌遗传算子, 增加鱼群迭代的混沌扰动, 尽量避免局部极值陷阱; 并利用遗传算法的寻优特性, 极大提高了鱼群整体的优化效果和计算精度, 加快了算法收敛速度. 仿真结果表明, 该算法有效可行.

1 李晓磊,邵之江,钱积薪.一种基于动物自治体的寻优模式:鱼群算法.系统工程理论与实践,2002,22(11):32–38.

2 Cai Y. Artificial fish school algorithm applied in a combinatorial optimization problem. Intelligent Systems and Applications, 2010, 2(1): 37–43.

3 Zhou YQ, Xie ZC. Improved artificial fish-school swarm algorithm for solving TSP. Systems Engineering and Electronics, 2009, 31: 1458–1461.

4 王联国,施秋红.人工鱼群算法的参数分析.计算机工程, 2010,36(24):169–171.

5 王联国,洪毅,施秋红.全局版人工鱼群算法.系统仿真学报, 2009,21(23):7483–7486.

6 张梅凤,邵诚.多峰函数优化的生境人工鱼群算法.控制理论与应用,2008,4(25):773–776.

7 刘彦君,江铭炎.自适应视野和步长的改进人工鱼群算法.计算机工程与应用,2009,45(25):35–37.

8 许恒迎,孙伟斌,张霞,等.自适应视野和步长的局部领域人工鱼群算法.计算机工程与设计,2012,33(7):2815–2820.

9 祁俊,赵慧雅,李明.基于双混沌映射改进的人工鱼群算法.计算机应用与软件,2012,29(9):230–233.

10 Tuba M, Bacanin N, Stanarevic N. Multithreaded implementation and performance of a modified artificial fish swarm algorithm for unconstrained optimization. International Journal of Mathematics & Computers in Simulation, 2013, 7(3): 215–222.

11 Wang YY, Li LJ. An improved intelligent algorithm based on the group search algorithm and the artificial fish swarm algorithm. Int. J. Optim. Civil Eng., 2015, 5(1): 37–52.

12 王联国,洪毅,赵付青,等.基于邻域正交交叉算子的人工鱼群算法.农业机械学报,2008,39(8):140–144.

Artificial Fish Swarm Algorithm Based on Chaotic Genetic Operation

FAN You-Hong, DENG Ren, LI Sheng-Lin, LUO Kai-Wen, GUO Yu-Dong

(Logistic Engineering University of PLA, Chongqing 401331, China)

A novel algorithm based on chaotic genetic operation is presented in this article to improve computation precision and convergence rate of original artificial fish swarm algorithm. With the chaotic disturbance increasing in fish swarm genetic iteration, the trap of local extremum is avoided, while the optimization effect, computation precision and convergence rate are also improved. Simulation result shows it works well and plays the specialties of genetic algorithm and fish swam algorithm.

artificial fish swarm algorithm; chaos; genetic algorithm

2016-06-22;

2016-08-08

[10.15888/j.cnki.csa.005664]