基于改进烟花算法的资源分配

doi:10.7527/S1000-6893.2020.24716

Abstract

Abstract: 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.

Key words: resource allocation, intelligent optimization algorithm, fireworks algorithm, simulated annealing, genetic algorithm

CLC Number:

V279

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.

References

[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).

Resource allocation based on improved fireworks algorithm

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

Comments

[1]	HAN Kai, DONG Richang, SHAO Fengwei, GONG Wenbin, CHANG Jiachao. Dynamic topology optimization of navigation satellite inter-satellite links network based on improved genetic algorithm [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2022, 43(9): 326095-326095.
[2]	HU Jiaxin, RUI Shu, GAO Ruichao, GOU Jianjun, GONG Chunlin. Hybrid optimization method for structural layout and size of flight vehicles [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2022, 43(5): 225363-225363.
[3]	WU Baohai, ZHANG Yang, ZHENG Zhiyang, ZHANG Ying, ZHANG Siqi. Review and prospects of feedrate optimization in CNC machining [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2022, 43(4): 525467-525467.
[4]	DUAN Yanhui, ZHOU Xin, GAO Shijiexi, LIN Jinxing, ZHANG Huaibao, WANG Guangxue. Two-step optimal strategy for load balancing of structured grid [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2021, 42(9): 625751-625751.
[5]	LUO Qing, ZHANG Tao, SHAN Peng, ZHANG Wentao, LIU Zihao. Generating reconfiguration blueprints for IMA systems based on improved Q-learning [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2021, 42(8): 525792-525792.
[6]	ZHONG Yun, WAN Lujun, ZHANG Jieyong. Optimized selection method for air combat course of action with interval uncertainty [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2021, 42(2): 324282-324282.
[7]	LIU Jixin, JIANG Hao, DONG Xinfang, LAN Sijie, WANG Haozhe. Dynamic collaborative sequencing method for arrival flights based on air traffic density [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2020, 41(7): 323717-323717.
[8]	LIU Bingyan, YE Xiongbing, ZHOU Chifei, LIU Biliu. Allocation of composite mode on-orbit service resource based on improved DQN [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2020, 41(5): 323630-323630.
[9]	PAN Chengsheng, XING Guixuan, QI Yaowen, YANG Li. Topological generation and optimization method in multi-state space information network [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2020, 41(4): 323546-323546.
[10]	GU Wenting, ZHAO Zhenshan, ZHOU Hanwei, FENG Jian, TAN Zhaoguang, LI Dong. Powered-on nacelle design on blended-wing-body configuration with podded engines [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2019, 40(9): 623047-623047.
[11]	WU Ke, ZHANG Huazhen, LAN Lan, ZHOU Yang. Shape active control of a CFRP reflector and placement optimization of actuator [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2019, 40(7): 222751-222751.
[12]	ZHANG Jing, HE You, PENG Yingning, LI Gang. Neural network and artificial potential field based cooperative and adversarial path planning [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2019, 40(3): 322493-322493.
[13]	PI Jun, MA Sheng, HE Jiacheng, KONG Qingguo, LIN Jiaquan, LIU Guangcai. Rolling bearing fault diagnosis based on IGA-ELM network [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2018, 39(9): 422025-422036.
[14]	AN Hai, YAN Zhaoyi, SUN Peng, YIN Guiqiao. Hybrid reliability optimization model based on new adaptive genetic algorithm [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2018, 39(7): 322084-322084.
[15]	SU Xichao, HAN Wei, ZHANG Yong, SONG Jingyu, ZHAO Zhenyu. Scheduling algorithm for maintenance and service support of carrier-based aircraft on flight deck with different man-aircraft matching patterns [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2018, 39(12): 222314-222314.