|
|
|
| Modified Moth Search Algorithm Based on Adaptive ε-Constrained Method |
| FENG Yanhong1,2,3, WANG Gaige4, LI Mingliang1,2, LI Xi1 |
1. School of Information Engineering, Hebei GEO University, Shijiazhuang 050031;
2. Intelligent Sensor Network Engineering Research Center of Hebei Province, Hebei GEO University, Shijiazhuang 050031;
3. Hebei Key Laboratory of Optoelectronic Information and Geo-detection Technology, Hebei GEO University, Shijiazhuang 050031;
4. School of Computer Science and Technology, Ocean University of China, Qingdao 266100 |
|
|
|
|
Abstract The multidemand multidimensional knapsack problem includes two types of inequality constraints with conflicts, making the search for the feasible solution region exceptionally difficult. Therefore, a modified moth search algorithm(MMS) based on adaptive ε-constrained method is proposed in this paper. In the Lévy flight phase, the step is adjusted according to the current iteration. In the straight flight phase, the mutation rate is introduced to increase the diversity of the population. Finally, the uniform mutation operator is applied to the whole population to improve the global search capability of the algorithm. The space mapping method is utilized to transfer the search space to the problem space, and the adaptive ε-constrained method is adopted. Experiments on classic 96 benchmark instances show that adaptive lévy flight operator, mutation straight flight operator and uniform mutation operator contribute significantly to the solution accuracy of the algorithm and the proposed algorithm performs better on the majority of instances. Furthermore, orthogonal experimental design method is utilized to analyze the influence of parameters on the ε-constrained method.
|
|
Received: 10 April 2023
|
|
|
| Fund:National Natural Science Foundation of China(No.61806069), Key Research and Development Plan Project of Hebei Province(No.22375415D), Science and Technology Project of Hebei Education Department(No.ZD2022083) |
|
Corresponding Authors:
WANG Gaige, Ph.D., associate professor. His research interests include evolutionary computing and scheduling optimization.
|
| About author:: About Author:FENG Yanhong, master, professor. Her research interests include evolutionary computing and combinatorial optimization.Li Mingliang, Ph.D., professor. His research interests include Internet of things technology and applications.LI Xi, Ph.D., associate professor. Her research interests include evolutionary computing and machine learning. |
|
|
|
[1] 姚友杰,钱斌,董钰明,等.基于EDA的绿色零等待作业车间调度问题求解.电子学报, 2021, 49(2): 225-233.
(YAO Y J, QIAN B, DONG Y M, et al. EDA-Based for the Green No-wait Job Shop Scheduling Problem. Acta Electronica Sinica, 2021, 49(2): 225-232.)
[2] 陈广锋,韩玮.基于最小负荷初始化的改进遗传算法求解柔性作业车间调度问题.信息与控制, 2021, 50(3): 374-384.
(CHEN G F, HAN W.Improved Genetic Algorithm Based on Minimum-Load Initialization to Solve Flexible Job-Shop Scheduling Pro-blem. Information and Control, 2021, 50(3): 374-384.)
[3] GOUDET O, GRELIER C, HAO J K.A Deep Learning Guided Memetic Framework for Graph Coloring Problems. Knowledge-Based Systems, 2022, 258(22). DOI: 10.1016/j.knosys.2022.109986.
[4] 蒋华伟,郭陶,杨震.车辆路径问题研究进展.电子学报, 2022, 50(2): 480-492.
(JIANG H W, GUO T, YANG Z.Research Progress of Vehicle Routing Problem. Acta Electronica Sinica, 2022, 50(2): 480-492.)
[5] 韩伟,张子成.求解旅行商问题的离散型贝壳漫步优化算法.模式识别与人工智能, 2016, 29(7): 650-657.
(HAN W, ZHANG Z C.Discrete Mussels Wandering Optimization Algorithm for Solving Traveling Salesman Problem. Pattern Recognition and Artificial Intelligence, 2016, 29(7): 650-657.)
[6] WANG L, ZHENG X L, WANG S Y.A Novel Binary Fruit Fly Optimization Algorithm for Solving the Multidimensional Knapsack Problem. Knowledge-Based Systems, 2013, 48: 17-23.
[7] CAPPANERA P, TRUBIAN M.A Local-Search-Based Heuristic for the Demand-Constrained Multidimensional Knapsack Problem. INFORMS Journal on Computing, 2005, 17(1): 82-98.
[8] GORTÁZAR F, DUARTE A, LAGUNA M, et al. Black Box Scatter Search for General Classes of Binary Optimization Problems. Computers and Operations Research, 2010, 37(11): 1977-1986.
[9] ARNTZEN H, HVATTUM L M, LØKKETANGEN A. Adaptive Me-mory Search for Multidemand Multidimensional Knapsack Problems. Computers and Operations Research, 2006, 33(9): 2508-2525.
[10] LAI X J, HAO J K, YUE D.Two-Stage Solution-Based Tabu Search for the Multidemand Multidimensional Knapsack Problem. European Journal of Operational Research, 2019, 274(1): 35-48.
[11] AL-SHIHABI S.A Novel Core-Based Optimization Framework for Binary Integer Programs-The Multidemand Multidimensional Knapsack Problem as a Test Problem. Operations Research Perspectives, 2021, 8. DOI: 10.1016/j.orp.2021.100182.
[12] 刘生建,杨艳,周永权.一种群体智能算法——狮群算法.模式识别与人工智能, 2018, 31(5): 431-441.
(LIU S J, YANG Y, ZHOU Y Q.A Swarm Intelligence Algorithm-Lion Swarm Optimization. Pattern Recognition and Artificial Intelligence, 2018, 31(5): 431-441.)
[13] 刘宝,张月,杨金莹.智能人工蜂群改进算法及其在油田注采优化中的应用.信息与控制, 2023, 52(2): 245-256.
(LIU B, ZHANG Y, YANG J Y.Improved Intelligent Artificial Bee Colony Algorithm and Its Application to Optimization of Injection and Production in Oilfield. Information and Control, 2023, 52(2): 245-256.)
[14] WANG G G.Moth Search Algorithm: A Bio-Inspired Metaheuristic Algorithm for Global Optimization Problems. Memetic Computing, 2018, 10(2): 151-164.
[15] LI J, YANG Y H, AN Q, et al. Moth Search: Variants, Hybrids, and Applications. Mathematics, 2022, 10(21). DOI: 10.3390/math10214162.
[16] FENG Y H, WANG G G.A Binary Moth Search Algorithm Based on Self-Learning for Multidimensional Knapsack Problems. Future Generation Computer Systems, 2022, 126: 48-64.
[17] 孙林,赵婧,徐久成,等.基于邻域粗糙集和帝王蝶优化的特征选择算法.计算机应用, 2022, 42(5): 1355-1366.
(SUN L, ZHAO J, XU J C, et al. Feature Selection Algorithm Based on Neighborhood Rough Set and Monarch Butterfly Optimization. Journal of Computer Applications, 2022, 42(5): 1355-1366.)
[18] FENG Y H, AN H Z, GAO X Y.The Importance of Transfer Function in Solving Set-Union Knapsack Problem Based on Discrete Moth Search Algorithm. Mathematics, 2019, 7(1). DOI: 10.3390/math7010017.
[19] 陈少淼,陈瑞,梁伟,等.面向复杂约束优化问题的进化算法综述.软件学报, 2023, 34(2): 565-581.
(CHEN S M, CHEN R, LIANG W, et al. Overview of Evolutio-nary Algorithms for Complex Constrained Optimization Problems. Journal of Software, 2023, 34(2): 565-581.)
[20] 李智勇,黄滔,陈少淼,等.约束优化进化算法综述.软件学报,2017, 28(6): 1529-1546.
(LI Z Y, HUANG T, CHEN S M, et al. Overview of Constrained Optimization Evolutionary Algorithms. Journal of Software, 2017, 28(6): 1529-1546.)
[21] ZHANG C J, QIN A K, SHEN W M, et al. ε-Constrained Diffe-rential Evolution Using an Adaptive ε-Level Control Method. IEEE Transactions on Systems, Man, and Cybernetics(Systems), 2020, 52(2): 769-785.
[22] 龚文引,蔡之华.基于ε占优的正交多目标差分演化算法研究.计算机研究与发展, 2009, 46(4): 655-666.
(GONG W Y, CAI Z H.Research on an ε-Domination Based Orthogonal Differential Evolution Algorithm for Multi-objective Opti-mization. Journal of Computer Research and Development, 2009, 46(4): 655-666.) |
|
|
|
2023, Vol. 36 
