一种基于Levy飞行的改进蝗虫优化算法

doi:10.3969/j.issn.1006-2475.2020.01.020

计算机与现代化

一种基于Levy飞行的改进蝗虫优化算法

(1.中国科学院声学研究所国家网络新媒体工程技术研究中心，北京100190；2.中国科学院大学,北京100049)

收稿日期:2019-05-10 出版日期:2020-02-13 发布日期:2020-02-13
作者简介:赵然(1992-),男（蒙古族）,内蒙古通辽人,博士研究生,研究方向：边缘计算，嵌入式虚拟化，E-mail: zhaor@dsp.ac.cn；郭志川(1975-),男,研究员,博士,研究方向：网络虚拟化技术，SDN/NFV，FPGA加速卡，E-mail: guozc@dsp.ac.cn；朱小勇(1982-),男,副研究员,博士,研究方向：嵌入式系统，多媒体技术，E-mail: zhuxy@dsp.ac.cn。
基金资助:
中国科学院战略性科技先导专项基金资助项目（XDC02010701）

An Improved Grasshopper Optimization Algorithm Based on Levy Flight

(1. National Network New Media Engineering Technology Research Center, Institute of Acoustics, Chinese Academy of
Sciences, Beijing 100190, China； 2. University of Chinese Academy of Sciences, Beijing 100049, China)

Received:2019-05-10 Online:2020-02-13 Published:2020-02-13

摘要/Abstract

摘要： 蝗虫优化算法是一种元启发式优化算法，能够用于解决任务调度问题。已有的改进蝗虫优化算法缺乏随机性，跳出局部最优的能力较弱，改进效果不够显著。针对这一问题，本文提出一种基于Levy飞行的改进蝗虫优化算法（LBGOA）。该算法引入基于Levy飞行的局部搜索机制增强算法的随机性，并采用基于线性递减参数的随机跳出策略来提高算法跳出局部最优的能力。CEC测试实验结果表明，所提出的算法拥有较强的搜索能力，在30个测试函数结果中能够获得17个最优解和6个次优解。将所提出的改进算法应用于边缘计算中的任务调度问题。任务调度仿真实验结果表明，所提出的算法能够有效提高搜索效果，相比GOA、OBLGOA、WOA、ALO、DA和PSO算法，LBGOA的搜索效果分别提升7.4%、7.5%、4.8%、27.7%、29.9%和20.7%。

关键词: 元启发式算法, 蝗虫优化算法；莱维飞行；任务调度

Abstract: Grasshopper optimization algorithm is a meta-heuristic optimization algorithm that can be used to solve task scheduling problems. The existing improved grasshopper optimization algorithm lacks randomness, and its ability to jump out of local optimum is weak. The improvement effect is not obvious enough. To solve this problem, this paper proposes an improved Grasshopper Optimization Algorithm Based on Levy flight（LBGOA）. The algorithm introduces a local search mechanism based on Levy flight to enhance the randomness of the algorithm and adopts a random jumping strategy based on linear decreasing parameters to improve the ability of the algorithm to jump out of local optimum. The experimental results of the CEC test show that the proposed algorithm has strong search ability, and 17 optimal solutions and 6 suboptimal solutions are obtained by LBGOA in the results of 30 test functions. The proposed improved algorithm is applied to the task scheduling problem in edge computing. The results of task scheduling simulation experiments show that the proposed algorithm can effectively improve the search results. Compared with GOA, OBLGOA, WOA, ALO, DA and PSO algorithms, the search results by LBGOA are promoted by 7.4%, 7.5%, 4.8%, 27.7%, 29.9%, and 20.7%respectively.

Key words: meta-heuristic algorithm, grasshopper optimization algorithm, Levy flight, task scheduling

中图分类号:

TP301.6

赵然1,2，郭志川1,2,朱小勇1,2. 一种基于Levy飞行的改进蝗虫优化算法[J]. 计算机与现代化, doi: 10.3969/j.issn.1006-2475.2020.01.020.

ZHAO Ran1,2, GUO Zhi-chuan1,2, ZHU Xiao-yong1,2. An Improved Grasshopper Optimization Algorithm Based on Levy Flight[J]. Computer and Modernization, doi: 10.3969/j.issn.1006-2475.2020.01.020.

参考文献

［1］ SAREMI S, MIRJALILI S, LEWIS. A Grasshopper optimisation algorithm: Theory and application［J］. Advances in Engineering Software, 2017,105:30-47.
［2］ GUO J F, SONG Z Z, CUI Y, et al. Energy-efficient resource allocation for multi-user mobile edge computing［C］// 2017 IEEE Global Communications Conference. 2017:1-7.
［3］ KRISHNASAMY K. Task scheduling algorithm based on hybrid particle swarm optimization in cloud computing environment［J］. Journal of Theoretical & Applied Information Technology, 2013,55(1)：33-38.
［4］ TAWFEEK M A, EL-SISI A, KESHK A E, et al. Cloud task scheduling based on ant colony optimization［C］// 2013 8th IEEE International Conference on Computer Engineering & Systems. 2013:64-69.
［5］ LIU X F, ZHAN Z H, DENG J D, et al. An energy efficient ant colony system for virtual machine placement in cloud computing［J］. IEEE Transactions on Evolutionary Computation, 2016,22(1):113-128.
［6］ XUE B, ZHANG M J, BROWNE W N, et al. A survey on evolutionary computation approaches to feature selection［J］. IEEE Transactions on Evolutionary Computation, 2015,20(4):606-626.
［7］ COELLO C A C, PULIDO G T, LECHUGA M S. Handling multiple objectives with particle swarm optimization［J］. IEEE Transactions on Evolutionary Computation, 2004,8(3):256-279.
［8］乔楠楠, 尤佳莉. 一种面向网络边缘任务调度问题的多方向粒子群优化算法［J］. 计算机应用与软件, 2017,34(4):309-315.
［9］ KENNEDY D J, EBERHART R. Particle swarm optimization［C］// Proceedings of IEEE International Conference on Neural Networks. 1995:1942-1948.
［10］LIAO C J, TSENG C T, LUARN P. A discrete version of particle swarm optimization for flowshop scheduling problems［J］. Computers & Operations Research, 2007,34(10):3099-3111.
［11］DEL VALLE Y, VENAYAGAMOORTHY G K, MOHA-GHEGHI S, et al. Particle swarm optimization: Basic concepts, variants and applications in power systems［J］. IEEE Transactions on Evolutionary Computation, 2008,12(2):171-195.
［12］MIRJALILI S. The ant lion optimizer［J］. Advances in Engineering Software, 2015,83:80-98.
［13］MIRJALILI S, LEWIS A. The whale optimization algorithm［J］. Advances in Engineering Software, 2016,95:51-67.
［14］HU H P, BAI Y P, XU T. A whale optimization algorithm with inertia weight［J］. WSEAS Transactions on Computers, 2016,15:319-326.
［15］MIRJALILI S. Dragonfly algorithm: A new meta-heuristic optimization technique for solving single-objective, discrete, and multi-objective problems［J］. Neural Computing and Applications, 2016,27(4):1053-1073.
［16］ABDEL-BASSET M, LUO Q F, MIAO F H, et al. Solving 0-1 knapsack problems by binary dragonfly algorithm［C］// International Conference on Intelligent Computing. 2017:491-502.
［17］SONG J M, LI S P. Elite opposition learning and exponential function steps-based dragonfly algorithm for global optimization［C］// 2017 IEEE International Conference on Information and Automation. 2017:1178-1183.
［18］DORIGO M, DI CARO G. Ant colony optimization: A new meta-heuristic［C］// Proceedings of 1999 IEEE Congress on Evolutionary Computation. 1999,2:1470-1477.
［19］YANG Q, CHEN W N, YU Z T, et al. Adaptive multimodal continuous ant colony optimization［J］. IEEE Transactions on Evolutionary Computation, 2016,21(2):191-205.
［20］郝航,金跃辉,杨谈. 基于并行化蚁群算法的网络测量节点选取算法［J］. 网络新媒体技术, 2018,7(1):7-15.
［21］EWEES A A, ELAZIZ M A, Houssein E H. Improved grasshopper optimization algorithm using opposition-based learning［J］. Expert Systems with Applications, 2018,112:156-172.
［22］ARORA S, ANAND P. Chaotic grasshopper optimization algorithm for global optimization［J］. Neural Computing and Applications, 2019,31(8):4385-4405.
［23］QIAO N N, YOU J L, SHENG Y Q, et al. An efficient algorithm of discrete particle swarm optimization for multi-objective task assignment［J］. IEICE Transactions on Information and Systems, 2016,99(12):2968-2977.
［24］桓自强,倪宏,胡琳琳,等. AAFSA-RA: 一种采用高级人工鱼群算法的多资源分配方法［J］. 西安交通大学学报, 2014,48(10):120-125.

一种基于Levy飞行的改进蝗虫优化算法

An Improved Grasshopper Optimization Algorithm Based on Levy Flight

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 1

编辑推荐

Metrics

本文评价