求解高維函數(shù)優(yōu)化的反饋多智能體遺傳算法

楊超 石連栓 施承堯 武琴

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

關(guān)鍵詞： 反饋算子;多智能體;均勻設(shè)計(jì);高維函數(shù)優(yōu)化;遺傳算法

中圖分類號： TP301.6 ???文獻(xiàn)標(biāo)識碼： A??? DOI：10.3969/j.issn.1003-6970.2020.07.016

本文著錄格式：楊超，石連栓，施承堯，等. 求解高維函數(shù)優(yōu)化的反饋多智能體遺傳算法[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]較其他傳統(tǒng)優(yōu)化算法具有較強(qiáng)的魯棒性和自適應(yīng)性，被廣泛應(yīng)用于現(xiàn)實(shí)世界中非線性復(fù)雜優(yōu)化問題的求解，例如函數(shù)優(yōu)化，組合優(yōu)化，自動控制，生產(chǎn)調(diào)度問題，圖像處理，機(jī)器檢測診斷優(yōu)化等。自遺傳算法被提出以來，雖然算法在理論研究取得了長足的發(fā)展，在實(shí)踐應(yīng)用中也獲得了一定的成功，但遺傳算法仍然存在一些不足，例如局部搜索能力差、收斂速度慢或易于陷入局部極優(yōu)，隨著待優(yōu)化問題維度的拓展，這些不足愈發(fā)地突出。

人工智能的不斷發(fā)展，鐘偉才等人^[5-7]提出多智能體遺傳算法，將智能體對環(huán)境的感知和反作用的能力與遺傳算法的搜索方式相結(jié)合，提高算法的局部搜索能力和全局收斂能力。在此基礎(chǔ)上，許多學(xué)者對其進(jìn)行研究并推廣其應(yīng)用，但在算法的收斂速度上沒有太大的提升，陳曉燕^[8]等人提出在農(nóng)作物區(qū)放置無線傳感器，傳感器節(jié)點(diǎn)定位直接影響數(shù)據(jù)的采集，通過設(shè)計(jì)節(jié)點(diǎn)定位模型，將遺傳算法引入到定位技術(shù)中，能更精確計(jì)算未知節(jié)點(diǎn)的坐標(biāo)，更好的為農(nóng)業(yè)服務(wù);Qiongbing Zhang等人^[9]提出了一種針對MANET的穩(wěn)定的服務(wù)質(zhì)量（QoS）組播模型，并引入一種新的葉交叉的交叉機(jī)制，算法可以獲得更好的QoS路由，并且執(zhí)行時(shí)間大大減少;黃仙等人^[10]引入多智能體技術(shù)對電源進(jìn)行合理的配置規(guī)劃;Kaizhou Gao 等人^[11]給出了靈活的作業(yè)車間調(diào)度問題（FJSP）的數(shù)學(xué)模型，并提出了一種經(jīng)典的混合遺傳算法（GA）和一種最新的帶有變量鄰域搜索（VNS）的帝國主義競爭算法（ICA）求解FJSP;聶敬云^[12]等人提出了一種基于遺傳算法（GA）優(yōu)化的最小二乘支持向量機(jī)（LSSVM）的MBR膜通量預(yù)測算法，算法采用GA對LSSVM模型的懲罰因子和核函數(shù)參數(shù)進(jìn)行優(yōu)化，提高預(yù)測精度;楊從銳^[13]根據(jù)進(jìn)化中種群適應(yīng)度的集中分散的程度非線性地自適應(yīng)調(diào)節(jié)遺傳進(jìn)化的運(yùn)算流程和交叉概率Pc、變異概率 Pm 的值，提高收斂速度與求解精度;梁昌勇等人^[14]設(shè)計(jì)了基于均勻設(shè)計(jì)表的均勻種群初始化方法和均勻交叉算子，在一定程度上避免算法陷入局部極值，提高了全局搜索能力和收斂速度;閆春等人^[15]提出一種非線性地自適應(yīng)調(diào)節(jié)交叉概率與變異概率和保留親本的策略，提高算法收斂速度與精準(zhǔn)度;陸遠(yuǎn)等人^[16]遺傳算法用來解決中小型柔性制造系統(tǒng)（FMS）加工中心數(shù)量少的問題，為單輛AGV的調(diào)度問題提供了有效的解決方案;潘曉英^[17]構(gòu)造了啟發(fā)式搜索和混合交叉策略完成智能體之間的競爭與合作，綜合凸變異以及局部搜索來完成智能體所具有的自學(xué)習(xí)行為，提高了智能體之間的相互作用，加快算法的收斂。

本文提出了一種反饋多智能體遺傳算法，該算法結(jié)合了均勻設(shè)計(jì)思想，使得初始化種群在搜索空間中均勻分布以增加初始種群的多樣性。此外，該算法又設(shè)計(jì)了反饋算子，用來控制算法的全局搜索和種群進(jìn)化的方向，從而加快算法的收斂速度、提高算法的求解精度和降低函數(shù)的評價(jià)次數(shù)。同時(shí)，該算法完善了鄰域競爭算子、變異算子、自學(xué)習(xí)算子，因此，它在一定程度上提高了算法的全局搜索能力和局部搜索能力。除此之外，該算法還采用了二進(jìn)制競爭的方法，使得它在不同時(shí)期，不同階段的優(yōu)良個(gè)體得以保存。最后，該算法對多個(gè)測試函數(shù)的有效性進(jìn)行了仿真驗(yàn)證，證實(shí)上述方法能極大地提升算法的收斂速度和求解精度。

4 ?結(jié)論

本文提出一種求解高維函數(shù)優(yōu)化的反饋多智能體遺傳算法，融入均勻設(shè)計(jì)思想，豐富初始種群的多樣性，使初始種群個(gè)體充分分布到可行解空間;添加反饋算子，掌控種群進(jìn)化方向，加速算法收斂速度，提高求解精度;同時(shí)對鄰域競爭、變異、自學(xué)習(xí)算子做出改進(jìn)，一定程度上增強(qiáng)算法的局部搜索能力，并與其他算法相比較，平均評價(jià)次數(shù)遠(yuǎn)遠(yuǎn)少于其他算法，解的精度也有所提高，對單峰函數(shù)和多峰函數(shù)算法收斂效果相近，對于高維函數(shù)優(yōu)化問題具有較強(qiáng)的全局搜索和跳出局部極值的能力，高維函數(shù)優(yōu)化實(shí)驗(yàn)表明，算法在處理高維函數(shù)優(yōu)化問題時(shí)使用較少的評價(jià)次數(shù)，能夠較快的搜索到全局最優(yōu)解，并且解的精確度也略有提高。本文是針對高維單目標(biāo)函數(shù)優(yōu)化，今后將利用智能體與遺傳算法結(jié)合處理多目標(biāo)問題，以得到分布較為均勻與廣泛的Pareto解。

1. 參考文獻(xiàn)
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. 王小平， 曹立明. 遺傳算法——理論， 應(yīng)用與軟件實(shí)現(xiàn)[M]. 西安： 西安交通大學(xué)出版社， 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. 鐘偉才， 薛明志， 劉靜， 焦李成. 多智能體遺傳算法用于超高維函數(shù)優(yōu)化[J]. 自然科學(xué)進(jìn)展， 2003（10）： 72-77.
8. 鐘偉才. 多智能體進(jìn)化模型和算法研究[D]. 西安電子科技大學(xué)， 2004.
9. 陳曉燕， 姚高偉， 張鯤， 等. 基于遺傳算法的無線傳感器節(jié)點(diǎn)定位在農(nóng)業(yè)的應(yīng)用[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. 黃仙， 呂晨. 電力市場環(huán)境下基于多智能體的電源規(guī)劃研究[J]. 科學(xué)技術(shù)創(chuàng)新， 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. 聶敬云， 李春青， 李威威， 等. 關(guān)于遺傳算法優(yōu)化的最小二乘支持向量機(jī)在MBR 仿真預(yù)測中的研究[J]. 軟件， 2015， 36（5）： 40-44.
14. 楊從銳. 改進(jìn)的自適應(yīng)遺傳算法在函數(shù)優(yōu)化中的應(yīng)用[D]. 昆明理工大學(xué)， 2018.
15. 梁昌勇， 陸青， 張恩橋， 等. 基于均勻設(shè)計(jì)的多智能體遺傳算法研究[J]. 系統(tǒng)工程學(xué)報(bào)， 2009， 24（01）： 109-113.
16. 閆春， 厲美璇， 周瀟. 基于改進(jìn)的遺傳算法在函數(shù)優(yōu)化中的應(yīng)用[J]. 計(jì)算機(jī)應(yīng)用研究， 2019， 36（10）： 2982-2985.
17. 陸遠(yuǎn)， 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]. 計(jì)算機(jī)工程與應(yīng)用， 2010， 46（03）： 9-12.
    1. 方開泰. 均勻設(shè)計(jì)及其應(yīng)用（Ⅲ）[J]. 數(shù)理統(tǒng)計(jì)與管理， 1994（03）： 52-55.
19. 曹慧榮， 李莉. 均勻設(shè)計(jì)表的MATLAB實(shí)現(xiàn)[J]. 統(tǒng)計(jì)與決策， 2008（06）： 144-146.
20. 徐宗本， 聶贊坎， 張文修. 父代種群參與競爭遺傳算法幾乎必然收斂[J]. 應(yīng)用數(shù)學(xué)學(xué)報(bào)， 2002（01）： 167-175.
21. 鐘偉才， 薛明志， 劉靜， 等. 基于AER模型的Multi-Agent遺傳算法[J]. 模式識別與人工智能， 2003， 16（04）： 390- 396.