求解高维函数优化的反馈多智能体遗传算法

杨超 石连栓 施承尧 武琴

摘  要： 针对多智能体遗传算法收敛速度慢，求解精度有待提高的问题，提出一种新的反馈多智能体遗传算法。该算法融合了均匀设计思想，丰富了初始种群的多样性并予以验证;添加反馈算子，提升了算法的收敛速度，大大降低了函数评价次数。同时，对邻域竞争，变异和自学习算子大幅改进，结合算术交叉，以及二进制竞争的方式保留精英个体。高维函数优化实验表明，改进后的算法在很大程度上能避免陷入局部极值窘境，具有很好的全局寻优能力和更高的求解精度。

关键词： 反馈算子;多智能体;均匀设计;高维函数优化;遗传算法

中图分类号： TP301.6    文献标识码： A    DOI：10.3969/j.issn.1003-6970.2020.07.016

本文著录格式：杨超，石连栓，施承尧，等. 求解高维函数优化的反馈多智能体遗传算法[J]. 软件，2020，41（07）：81-90

Feedback Multi-agent Genetic Algorithm For High Dimensional Function Optimization

YANG Chao， SHI Lian-shuan， SHI Cheng-yao， WU Qin

（Institute of Information Technology Engineering， Tianjin University of Technology and Education， Tianjin 300222， China）

【Abstract】： Aiming at the problem that the multi-agent genetic algorithm has slow convergence speed and low accuracy， an improved multi-agent genetic algorithm is proposed. The algorithm combines the idea of uniform design， increase the diversity of the initial population of the algorithm， and adds feedback operator to accelerate the convergence speed of the algorithm and greatly improve the neighborhood competition， mutation and self-learning operators. Using arithmetic crossover， and the way parents and children compete to retain the best individual， and the algorithm largely avoids the algorithm falling into local excellent or The dilemma of non-global optimal values. The high-dimensional function optimization experiments show that the algorithm has good global search ability and fast convergence speed， and avoids the algorithm being trapped in local excellent.

【Key words】： Feedback operator; Multi-agent; Uniform design; High-dimensional function optimization; Genetic algorithm

0  引言

遺传算法（Genetic Algorithm）^[1-4]较其他传统优化算法具有较强的鲁棒性和自适应性，被广泛应用于现实世界中非线性复杂优化问题的求解，例如函数优化，组合优化，自动控制，生产调度问题，图像处理，机器检测诊断优化等。自遗传算法被提出以来，虽然算法在理论研究取得了长足的发展，在实践应用中也获得了一定的成功，但遗传算法仍然存在一些不足，例如局部搜索能力差、收敛速度慢或易于陷入局部极优，随着待优化问题维度的拓展，这些不足愈发地突出。

人工智能的不断发展，钟伟才等人^[5-7]提出多智能体遗传算法，将智能体对环境的感知和反作用的能力与遗传算法的搜索方式相结合，提高算法的局部搜索能力和全局收敛能力。在此基础上，许多学者对其进行研究并推广其应用，但在算法的收敛速度上没有太大的提升，陈晓燕^[8]等人提出在农作物区放置无线传感器，传感器节点定位直接影响数据的采集，通过设计节点定位模型，将遗传算法引入到定位技术中，能更精确计算未知节点的坐标，更好的为农业服务;Qiongbing Zhang等人^[9]提出了一种针对MANET的稳定的服务质量（QoS）组播模型，并引入一种新的叶交叉的交叉机制，算法可以获得更好的QoS路由，并且执行时间大大减少;黄仙等人^[10]引入多智能体技术对电源进行合理的配置规划;Kaizhou Gao 等人^[11]给出了灵活的作业车间调度问题（FJSP）的数学模型，并提出了一种经典的混合遗传算法（GA）和一种最新的带有变量邻域搜索（VNS）的帝国主义竞争算法（ICA）求解FJSP;聂敬云^[12]等人提出了一种基于遗传算法（GA）优化的最小二乘支持向量机（LSSVM）的MBR膜通量预测算法，算法采用GA对LSSVM模型的惩罚因子和核函数参数进行优化，提高预测精度;杨从锐^[13]根据进化中种群适应度的集中分散的程度非线性地自适应调节遗传进化的运算流程和交叉概率Pc、变异概率 Pm 的值，提高收敛速度与求解精度;梁昌勇等人^[14]设计了基于均匀设计表的均匀种群初始化方法和均匀交叉算子，在一定程度上避免算法陷入局部极值，提高了全局搜索能力和收敛速度;闫春等人^[15]提出一种非线性地自适应调节交叉概率与变异概率和保留亲本的策略，提高算法收敛速度与精准度;陆远等人^[16]遗传算法用来解决中小型柔性制造系统（FMS）加工中心数量少的问题，为单辆AGV的调度问题提供了有效的解决方案;潘晓英^[17]构造了启发式搜索和混合交叉策略完成智能体之间的竞争与合作，综合凸变异以及局部搜索来完成智能体所具有的自学习行为，提高了智能体之间的相互作用，加快算法的收敛。

本文提出了一种反馈多智能体遗传算法，该算法结合了均匀设计思想，使得初始化种群在搜索空间中均匀分布以增加初始种群的多样性。此外，该算法又设计了反馈算子，用来控制算法的全局搜索和种群进化的方向，从而加快算法的收敛速度、提高算法的求解精度和降低函数的评价次数。同时，该算法完善了邻域竞争算子、变异算子、自学习算子，因此，它在一定程度上提高了算法的全局搜索能力和局部搜索能力。除此之外，该算法还采用了二进制竞争的方法，使得它在不同时期，不同阶段的优良个体得以保存。最后，该算法对多个测试函数的有效性进行了仿真验证，证实上述方法能极大地提升算法的收敛速度和求解精度。

4  结论

本文提出一种求解高维函数优化的反馈多智能体遗传算法，融入均匀设计思想，丰富初始种群的多样性，使初始种群个体充分分布到可行解空间;添加反馈算子，掌控种群进化方向，加速算法收敛速度，提高求解精度;同时对邻域竞争、变异、自学习算子做出改进，一定程度上增强算法的局部搜索能力，并与其他算法相比较，平均评价次数远远少于其他算法，解的精度也有所提高，对单峰函数和多峰函数算法收敛效果相近，对于高维函数优化问题具有较强的全局搜索和跳出局部极值的能力，高维函数优化实验表明，算法在处理高维函数优化问题时使用较少的评价次数，能够较快的搜索到全局最优解，并且解的精确度也略有提高。本文是针对高维单目标函数优化，今后将利用智能体与遗传算法结合处理多目标问题，以得到分布较为均匀与广泛的Pareto解。

1. 参考文献
2. HOLLAND J H. Adaptation in natural and artificial systems[M]. Ann Arbor： University of Michigan Press， 1975.
3. DeJONG K A. The analysis of the behavior of a class of genetic adaptive systems[D]. Ann Arbor： University of Michigan， 1975.
4. GOLDBERG D E. Genetic algorithms in search， optimization and ma-chine learning[M]. Boston： Addison-Wesley Longman Press， 1989.
5. 王小平， 曹立明. 遗传算法——理论， 应用与软件实现[M]. 西安： 西安交通大学出版社， 2005.
6. Zhong Weicai， Liu Jing， Xue Mingzhi， et al. A multiagent genetic algorithm for global numerical optimization [J]. IEEE Transactions on Systems， Man， and Cybernetics- part B： Cybernetics， 2004， 34（2） ： 1128- 1141.
7. 钟伟才， 薛明志， 刘静， 焦李成. 多智能体遗传算法用于超高维函数优化[J]. 自然科学进展， 2003（10）： 72-77.
8. 钟伟才. 多智能体进化模型和算法研究[D]. 西安电子科技大学， 2004.
9. 陈晓燕， 姚高伟， 张鲲， 等. 基于遗传算法的无线传感器节点定位在农业的应用[J]. 软件， 2015， 36（4）： 1-5.
10. Qiongbing Zhang， Lixin Ding， Zhuhua Liao. A Novel Genetic Algorithm for Stable Multicast Routing in Mobile Ad Hoc Networks[J]. 中国通信， 2019， 16（08）： 24-37.
11. 黄仙， 吕晨. 电力市场环境下基于多智能体的电源规划研究[J]. 科学技术创新， 2018（36）： 90-91.
12. Kaizhou Gao， Zhiguang Cao， Le Zhang， Zhenghua Chen， Yuyan Han， Quanke Pan. A Review on Swarm Intelligence and Evolutionary Algorithms for Solving Flexible Job Shop Scheduling Problems[J]. IEEE/CAA Journal of Automatica Sinica， 2019， 6（04）： 904-916.
13. 聂敬云， 李春青， 李威威， 等. 關于遗传算法优化的最小二乘支持向量机在MBR 仿真预测中的研究[J]. 软件， 2015， 36（5）： 40-44.
14. 杨从锐. 改进的自适应遗传算法在函数优化中的应用[D]. 昆明理工大学， 2018.
15. 梁昌勇， 陆青， 张恩桥， 等. 基于均匀设计的多智能体遗传算法研究[J]. 系统工程学报， 2009， 24（01）： 109-113.
16. 闫春， 厉美璇， 周潇. 基于改进的遗传算法在函数优化中的应用[J]. 计算机应用研究， 2019， 36（10）： 2982-2985.
17. 陆远， Feng Kuikui， Hu Ying. Study on scheduling algorithm for multiple handling requests of single automated guided vehicles[J]. High Technology Letters， 2019， 25（03）： 334-339.
18. 潘晓英. 混合多智能体遗传算法[J]. 计算机工程与应用， 2010， 46（03）： 9-12.
    1. 方开泰. 均匀设计及其应用（Ⅲ）[J]. 数理统计与管理， 1994（03）： 52-55.
19. 曹慧荣， 李莉. 均匀设计表的MATLAB实现[J]. 统计与决策， 2008（06）： 144-146.
20. 徐宗本， 聂赞坎， 张文修. 父代种群参与竞争遗传算法几乎必然收敛[J]. 应用数学学报， 2002（01）： 167-175.
21. 钟伟才， 薛明志， 刘静， 等. 基于AER模型的Multi-Agent遗传算法[J]. 模式识别与人工智能， 2003， 16（04）： 390- 396.