求解高維函數優化的反饋多智能體遺傳算法

楊超 石連栓 施承堯 武琴

摘? 要： 針對多智能體遺傳算法收斂速度慢，求解精度有待提高的問題，提出一種新的反饋多智能體遺傳算法。該算法融合了均勻設計思想，豐富了初始種群的多樣性并予以驗證;添加反饋算子，提升了算法的收斂速度，大大降低了函數評價次數。同時，對鄰域競爭，變異和自學習算子大幅改進，結合算術交叉，以及二進制競爭的方式保留精英個體。高維函數優化實驗表明，改進后的算法在很大程度上能避免陷入局部極值窘境，具有很好的全局尋優能力和更高的求解精度。

關鍵詞： 反饋算子;多智能體;均勻設計;高維函數優化;遺傳算法

中圖分類號： 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.