As a NP-hard problem, the resource allocation problem is a common mathematical problem in cloud computing, radio, satellite scheduling, multi-UAV collaborative task allocation, and many other fields. As an intelligent optimization algorithm, the fireworks algorithm has the ability to solve large-scale resource allocation problems, but also has some problems, such as low solving precision and probability to fall into locally optimal solution. To improve the computational efficiency and global optimization ability of the traditional fireworks algorithm, this paper proposes an improved fireworks algorithm, which uses the mutation operator in genetic algorithm to replace Gaussian mutation operation in the traditional fireworks algorithm and adds the simulated annealing process in each iteration. Finally, the performance of the algorithm is verified by simulation on a mathematical model for multi-UAV cooperative task assignment, and the results show that the algorithm is superior to other three fireworks algorithms in terms of convergence speed and solving precision.
ZOU Shiyu
,
LI Fuming
,
XIE Aiping
,
ZHOU Tao
,
LIU Peng
. Resource allocation based on improved fireworks algorithm[J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2021
, 42(12)
: 324716
-324716
.
DOI: 10.7527/S1000-6893.2020.24716
[1] 吴栋. 基于机器学习的多任务多设备匹配算法研究[D]. 杭州:浙江大学, 2019. WU D. Research on multi-task multi-device matching algorithm based on machine learning[D]. Hangzhou:Zhejiang University, 2019(in Chinese).
[2] MAVROTAS G. Effective implementation of the ε-constraint method in multi-objective mathematical programming problems[J]. Applied Mathematics and Computation, 2009, 213(2):455-465.
[3] 张昀普, 单甘霖. 面向空中目标威胁评估的多传感器管理方法[J].航空学报, 2019, 40(11):323218. ZHANG Y P, SHAN G L. Multi-sensor management method for air target threat assessment[J]. Acta Aeronautica et Astronautica Sinica, 2019, 40(11):323218(in Chinese).
[4] 傅英定, 成孝予, 唐应辉. 最优化理论与方法[M]. 北京:国防工业出版社,2007:120-247. FU Y D, CHENG X Y, TANG Y H. Theory and methods of optimization[M].Beijing:National Defense Industry Press, 2007:120-247(in Chinese).
[5] RIOS L M, SAHINIDIS N V. Derivative-free optimization:A review of algorithms and comparison of software implementations[J]. Journal of Global Optimization, 2013, 56(3):1247-1293.
[6] WANG Z, LIU L, LONG T, et al. Multi-UAV reconnaissance task allocation for heterogeneous targets using an opposition-based genetic algorithm with double-chromosome encoding[J]. Chinese Journal of Aeronautics, 2018, 31(2):339-350.
[7] GAO Y, TIAN Y L, LIU H, et al. Gaussian fitting based optimal design of aircraft mission success space using multi-objective genetic algorithm[J]. Chinese Journal of Aeronautics, 2020, 33(12):3318-3330.
[8] CHEN J, YE F, JIANG T. Path planning under obstacle-avoidance constraints based on ant colony optimization algorithm[C]//2017 IEEE 17th International Conference on Communication Technology (ICCT). Piscataway:IEEE Press, 2017:1434-1438.
[9] LIAN Q P, WANG H J, YUAN J Y. Particle swarm optimization based collaborative collision avoidance method for USV clusters[J]. Systems Engineering and Electronic Technology, 2019, 41(9):2034-2040.
[10] TAN Y, ZHU Y C. Fireworks algorithm for optimization[M]//Lecture Notes in Computer Science. Berlin:Springer, 2010:355-364.
[11] LI J Z, TAN Y. The bare bones fireworks algorithm:A minimalist global optimizer[J]. Applied Soft Computing, 2018, 62:454-462.
[12] 汪菊琴, 史荧中, 彭力, 等. 带有灰色关联算子的烟花算法[J]. 计算机工程与应用, 2018, 54(20):145-151, 158. WANG J Q, SHI Y Z, PENG L, et al. Fireworks algorithm with grey correlation operator[J]. Computer Engineering and Applications, 2018, 54(20):145-151, 158(in Chinese).
[13] 郭京蕾, 赵孝豪, 郭亚军. 基于差分变异算子的烟花算法[J]. 计算机工程与科学, 2020, 42(1):178-184. GUO J L, ZHAO X H, GUO Y J. A fireworks algorithm based on differential mutant operator[J]. Computer Engineering & Science, 2020, 42(1):178-184(in Chinese).
[14] 张水平, 李殷俊, 高栋, 等. 带有动态爆炸半径的增强型烟花算法[J]. 计算机工程与应用, 2020, 56(18):50-57. ZHANG S P, LI Y J, GAO D, et al. Enhanced fireworks algorithm with dynamic explosion radius[J]. Computer Engineering and Applications, 2020, 56(18):50-57(in Chinese).
[15] ZHANG B, ZHANG M X, ZHENG Y J. A hybrid biogeography-based optimization and fireworks algorithm[J]. Proceedings of the 2014 IEEE Congress on Evolutionary Computation, 2014:3200-3206.
[16] 宋江迪. 群智能算法及其在全局函数优化中的应用研究[D]. 鞍山:辽宁科技大学, 2016. SONG J D. Swarm intelligence algorithm and its research with application in the global function optimization[D]. Anshan:University of Science and Technology Liaoning, 2016(in Chinese).
[17] 韩守飞, 李席广, 拱长青. 基于模拟退火与高斯扰动的烟花优化算法[J]. 计算机科学, 2017, 44(5):257-262. HAN S F, LI X G, GONG C Q. Fireworks optimization algorithm based on simulated annealing and Gaussian perturbations[J]. Computer Science, 2017, 44(5):257-262(in Chinese).
[18] 齐小刚, 李博, 范英盛, 等. 多约束下多无人机的任务规划研究综述[J]. 智能系统学报, 2020, 15(2):204-217. QI X G, LI B, FAN Y S, et al. A survey of mission planning on UAVs systems based on multiple constraints[J]. CAAI Transactions on Intelligent Systems, 2020, 15(2):204-217(in Chinese).
[19] 苏析超,韩维,张勇, 等.考虑人机匹配模式的舰载机甲板机务勤务保障调度算法[J]. 航空学报, 2018, 39(12):222314. SU X C, HAN W, ZHANG Y, et al. Carrier-based aircraft deck maintenance support scheduling algorithm considering man-machine matching model[J]. Acta Aeronautica et Astronautica Sinica, 2018, 39(12):222314(in Chinese).
[20] KIRKPATRICK S, GELATT C D, VECCHI M P. Optimization by simulated annealing[J]. Science, 1983, 220(4598):671-680.
[21] 庞润娟. 求解0-1背包问题的烟花算法[D]. 西安:西安理工大学, 2019. PANG R J. Fireworks algorithm for solving 0-1 knapsack problem[D]. Xi'an:Xi'an University of Technology, 2019(in Chinese).
CJA