大规模优化问题的改进花朵授粉算法

doi:10.3778/j.issn.1673-9418.1909043

摘要/Abstract

摘要：

花朵授粉算法（FPA）寻优结构新颖，寻优能力良好，但求解高维优化问题易陷入“维数灾难”。为提高FPA求解大规模优化问题的性能，提出一种改进花朵授粉算法（IFPA）。采用反向学习策略增加种群多样性，充分搜索解空间，提高初始种群质量；在自花授粉阶段，发挥当代最优位置的牵引作用，减少算法迭代代价，提高搜索效率，提出避免维间干扰的方法，采用逐维随机扰动策略对花粉个体进行更新，整体评价后接受更优解，提高了算法局部迭代质量。IFPA仅需3~5个种群个体即可达到满意的优化效果，15个测试函数在100、1 000和5 000维下的仿真结果表明：IFPA的求解精度大幅提高，收敛速度明显加快，鲁棒性强，与FPA、PSO和BA的对比表明，改进算法在处理不同类型大规模优化问题上是具有竞争力的。

关键词: 花朵授粉算法, 反向学习, 逐维随机扰动, 维间干扰, 大规模优化

Abstract:

Flower pollination algorithm (FPA) has a novel optimization structure and good optimization ability, but it is easy to fall into “dimension disaster” when solving high-dimensional optimization problems. In order to improve the performance of FPA in solving large-scale optimization problems, an improved flower pollination algorithm (IFPA) is proposed. The opposition-based learning strategy is adopted to increase the diversity of population and search the solution space sufficiently to improve the quality of the initial population. In the stage of self-pollination, the traction effect of contemporary optimal position is exerted to reduce the iterative cost of the algorithm and the search efficiency is improved. And this paper proposes a new method to avoid interference phenomena among dimensions to improve the local iteration quality. The pollen individual is updated with the strategy of dimension- by-dimension random disturbance, and the better solution is accepted after the overall evaluation. IFPA only needs 3 to 5 population individuals to achieve satisfactory optimization effect. The simulation results of 15 test functions at the dimensions of 100, 1000 and 5000 show that the solution accuracy of IFPA is greatly improved, the convergence speed is obviously accelerated, and the robustness is strong. Meanwhile, the results also reveal the proposed algorithm is competitive for different types of large scale optimization problems compared with FPA, PSO and BA.

Key words: flower pollination algorithm, opposition-based learning, dimension-by-dimension random disturbance, interference among dimensions, large scale optimization

李煜，郑娟，刘景森. 大规模优化问题的改进花朵授粉算法[J]. 计算机科学与探索, 2020, 14(8): 1427-1440.

LI Yu, ZHENG Juan, LIU Jingsen. Improved Flower Pollination Algorithm for Large Scale Optimization Problems[J]. Journal of Frontiers of Computer Science and Technology, 2020, 14(8): 1427-1440.

参考文献

[1] Liang J, Liu R, Yu K J, et al. Dynamic multi-swarm particle swarm optimization with cooperative coevolution for large scale global optimization[J]. Journal of Software, 2018, 29(9): 2595-2605. 梁静, 刘睿, 于坤杰, 等. 求解大规模问题协同进化动态粒子群优化算法[J]. 软件学报, 2018, 29(9): 2595-2605.
[2] Mahdavi S, Shiri M E, Rahnamayan S. Metaheuristics in large-scale global continues optimization: a survey[J]. Information Sciences, 2015, 295: 407-428.
[3] Mohapatra P, Das K N, Roy S. A modified competitive swarm optimizer for large scale optimization problems[J]. Applied Soft Computing, 2017, 59: 340-362.
[4] Omidvar M N, Li X D, Mei Y, et al. Cooperative co-evolution with differential grouping for large scale optimization[J]. IEEE Transactions on Evolutionary Computation, 2014, 18(3): 378-393.
[5] Long W, Cai S H, Jiao J J, et al. Improved whale optimization algorithm for large scale optimization problems[J]. Systems Engineering-Theory & Practice, 2017, 37(11): 2983-2994. 龙文, 蔡绍洪, 焦建军, 等. 求解大规模优化问题的改进鲸鱼优化算法[J]. 系统工程理论与实践, 2017, 37(11): 2983-2994.
[6] Li Y, Pei Y H, Liu J S. Bat optimal algorithm combined uniform mutation with Gaussian mutation[J]. Control and Decision, 2017, 32(10): 1775-1781. 李煜, 裴宇航, 刘景森. 融合均匀变异与高斯变异的蝙蝠优化算法[J]. 控制与决策, 2017, 32(10): 1775-1781.
[7] Zheng F F, Mei Q H, Liu M, et al. Research on genetic algorithm and greedy method of stowage planning in multiple ports[J]. Operations Research and Management Science, 2018, 27(5): 1-7. 郑斐峰, 梅启煌, 刘明, 等. 基于遗传算法与贪婪策略的多港口集装箱配载研究[J]. 运筹与管理, 2018, 27(5): 1-7.
[8] He G J, Zhou S L, Feng D Q. Improved artificial bee algorithm for high dimensional complex optimization problems[J]. Computer Engineering and Applications, 2018, 54(12): 126-132. 贺桂娇, 周树亮, 冯冬青. 求解高维复杂优化问题的改进人工蜂群算法[J]. 计算机工程与应用, 2018, 54(12): 126-132.
[9] Binh H T T, Hanh N T, Van Quan L, et al. Improved cuckoo search and chaotic flower pollination optimization algorithm for maximizing area coverage in wireless sensor networks[J]. Neural Computing & Applications, 2018, 30(7): 2305-2317.
[10] Huang G Q, Zhao W J, Lu Q Q. Bat algorithm with global convergence for solving large-scale optimization problem[J]. Application Research of Computers, 2013, 30(5): 1323-1328. 黄光球, 赵魏娟, 陆秋琴. 求解大规模优化问题的可全局收敛蝙蝠算法[J]. 计算机应用研究, 2013, 30(5): 1323-1328.
[11] Yang X S. Flower pollination algorithm for global optimization [C]//LNCS 7445: Proceedings of the 11th International Conference on Unconventional Computing and Natural Computation, Orléans, Sep 3-7, 2012. Berlin, Heidelberg: Springer, 2012: 240-249.
[12] Yang X S, Karamanoglu M, He X S. Multi-objective flower algorithm for optimization[J]. Procedia Computer Science, 2013, 18(1): 861-868.
[13] Peesapati R, Yadav V K, Kumar N. Flower pollination algorithm based multi-objective congestion management considering optimal capacities of distributed generations[J]. Energy, 2018, 147: 980-994.
[14] Xu W H, Wang Y, Yan D H, et al. Flower pollination algorithm for multi-objective fuzzy flexible job shop scheduling[J]. Journal of System Simulation, 2018, 30(11): 4403-4412.徐文豪, 王艳, 严大虎, 等. 花授粉算法求解多目标模糊柔性作业车间调度[J]. 系统仿真学报, 2018, 30(11): 4403-4412.
[15] Zhou Y Q, Zhang S, Luo Q F, et al. Using flower pollination algorithm and atomic potential function for shape matching[J]. Neural Computing & Applications, 2018, 29(6): 21-40.
[16] Abdel-Basset M, El-Shahat D, El-Henawy I. Solving 0-1 knapsack problem by binary flower pollination algorithm[J]. Neural Computing & Applications, 2019, 31(9): 5477-5495.
[17] Abdel-Raouf O, Abdel-Baset M, El-Henawy I. A new hybrid flower pollination algorithm for solving constrained global optimization problems[J]. International Journal of Applied Operational Research, 2014, 4(2): 1-13.
[18] Lenin K, Reddy B R, Kalavathi M S. Shrinkage of active power loss by hybridization of flower pollination algorithm with chaotic harmony search algorithm[J]. Control Theory and Informatics, 2014, 4(8): 31-38.
[19] Salgotra R, Singh U. A novel bat flower pollination algorithm for synthesis of linear antenna arrays[J]. Neural Computing & Applications, 2018, 30(7): 2269-2282.
[20] Wang R, Zhou Y Q. Flower pollination algorithm with dimension by dimension improvement[J]. Mathematical Problems in Engineering, 2014, 4: 1-9.
[21] Xiao H H, Wan C X, Duan Y M, et al. Flower pollination algorithm combination with Gauss mutation and Powell search method[J]. Journal of Frontiers of Computer Science and Technology, 2017, 11(3): 478-490. 肖辉辉, 万常选, 段艳明, 等. 融合高斯变异和Powell法的花朵授粉优化算法[J]. 计算机科学与探索, 2017, 11(3): 478-490.
[22] Shi Y, Eberhart R. A modified particle swarm optimizer [C]//Proceedings of the 1998 IEEE International Conference on Evolutionary Computation, IEEE World Congress on Computational Intelligence, Anchorage, May 4-9, 1998. Piscataway: IEEE, 1998: 69-73.
[23] Draa A. On the performances of the flower pollination algorithm-Qualitative and quantitative analyses[J]. Applied Soft Computing, 2015, 34(C): 349-371.
[24] Tizhoosh H R. Opposition-based learning: a new scheme for machine intelligence[C]//Proceedings of the 2005 IEEE International Conference on Intelligent Agents, Vienna, Nov 28-30, 2005. Piscataway: IEEE, 2005: 695-701.
[25] Zhou X Y, Wu Z J, Wang H, et al. Elite opposition-based particle swarm optimization[J]. Acta Electronica Sinica, 2013, 41(8): 1647-1652. 周新宇, 吴志健, 王晖, 等. 一种精英反向学习的粒子群优化算法[J]. 电子学报, 2013, 41(8): 1647-1652.
[26] Alamri H S, Alsariera Y A, Zamli K Z. Opposition-based whale optimization algorithm[J]. Advanced Science Letters, 2018, 24(10): 7461-7464.
[27] Zhai J C, Qin Y P. Opposition-based learning in global harmony search algorithm[J]. Control and Decision, 2019, 34(7): 1449-1455. 翟军昌, 秦玉平. 反向学习全局和声搜索算法[J]. 控制与决策, 2019, 34(7): 1449-1455.
[28] Yu F, Li Y X, Wei B, et al. The application of a novel OBL based on lens imaging principle in PSO[J]. Acta Electronica Sinica, 2014, 42(2): 230-235. 喻飞, 李元香, 魏波, 等. 透镜成像反学习策略在粒子群算法中的应用[J]. 电子学报, 2014, 42(2): 230-235.
[29] Zhou L Y, Ding L X, Ma M D, et al. Orthogonal opposition based firefly algorithm[J]. Journal of Electronics & Information Technology, 2019, 41(1): 202-209. 周凌云, 丁立新, 马懋德, 等. 一种正交反向学习萤火虫算法[J]. 电子与信息学报, 2019, 41(1): 202-209.
[30] Li Y, Li X T, Liu J S, et al. An improved bat algorithm based on lévy flights and adjustment factors[J]. Symmetry, 2019, 11(7): 925.
[31] Liu J S, Liu L, Li Y. A differential evolution flower pollination algorithm with dynamic switch probability[J]. Chinese Journal of Electronics, 2019, 28(4): 737-747.
[32] Yang X S. Firefly algorithms for multimodal optimization[C]//LNCS 5792: Proceedings of the 5th International Symposium on Stochastic Algorithms: Foundations and Applications, Sapporo, Oct 26-28, 2009. Berlin, Heidelberg: Springer, 2009: 169-178.
[33] Jamil M, Yang X S. A literature survey of benchmark functions for global optimization problems[J]. International Journal of Mathematical Modelling and Numerical Optimisation, 2013, 4(2): 150.