A novel differential evolution mapping technique for generic combinatorial optimization problems

被引:29
作者
Ali, Ismail M. [1 ]
Essam, Daryl [1 ]
Kasmarik, Kathryn [1 ]
机构
[1] Univ New South Wales, SEIT, Canberra, ACT, Australia
关键词
Discrete differential evolution; Combinatorial optimization problems; 0/1 knapsack problems; Traveling salesman problems; Traveling thief problems; PARTICLE SWARM OPTIMIZATION; CUCKOO SEARCH; ALGORITHM;
D O I
10.1016/j.asoc.2019.04.017
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
Differential evolution is primarily designed and used to solve continuous optimization problems. Therefore, it has not been widely considered as applicable for real-world problems that are characterized by permutation-based combinatorial domains. Many algorithms for solving discrete problems using differential evolution have been proposed, some of which have achieved promising results. However, to enhance their performance, they require improvements in many aspects, such as their convergence speeds, computational times and capabilities to solve large discrete problems. In this paper, we present a new mapping method that may be used with differential evolution to solve combinatorial optimization problems. This paper focuses specifically on the mapping component and its effect on the performance of differential evolution. Our method maps continuous variables to discrete ones, while at the same time, it directs the discrete solutions produced towards optimality, by using the best solution in each generation as a guide. To judge its performance, its solutions for instances of well-known discrete problems, namely: 0/1 knapsack, traveling salesman and traveling thief problems, are compared with those obtained by 8 other state-of-the-art mapping techniques. To do this, all mapping techniques are used with the same differential evolution settings. The results demonstrated that our technique significantly outperforms the other mapping methods in terms of the average error from the best-known solution for the traveling salesman problems, and achieves promising results for both the 0/1 knapsack and the traveling thief problems. (C) 2019 Elsevier B.V. All rights reserved.
引用
收藏
页码:297 / 309
页数:13
相关论文
共 43 条
[1]   Model-Based Optimization of an Acetylene Hydrogenation Reactor To Improve Overall Ethylene Plant Economics [J].
Aeowjaroenlap, Hattachai ;
Chotiwiriyakun, Kritsada ;
Tiensai, Nattawat ;
Tanthapanichakoon, Wiwut ;
Spatenka, Stepan ;
Cano, Alejandro .
INDUSTRIAL & ENGINEERING CHEMISTRY RESEARCH, 2018, 57 (30) :9943-9951
[2]   A Differential Evolution Algorithm for Solving Resource Constrained Project Scheduling Problems [J].
Ali, Ismail M. ;
Elsayed, Saber Mohammed ;
Ray, Tapabrata ;
Sarker, Ruhul A. .
ARTIFICIAL LIFE AND COMPUTATIONAL INTELLIGENCE, ACALCI 2016, 2016, 9592 :209-220
[3]  
Alnihoud J, 2010, INT ARAB J INF TECHN, V7, P55
[4]  
[Anonymous], 2018, APPL OPTIMAL CONTROL
[5]  
[Anonymous], 2006, ser. Natural computing
[6]  
[Anonymous], 2004, P 4 INT S INTELLIGEN, DOI DOI 10.1007/978-3-540-28646-2_38
[7]  
[Anonymous], 2015, P 4 INT C SOFT COMP
[8]  
Baghel M., 2012, International Journal of Computer Applications, V58
[9]   A Novel Set-Based Particle Swarm Optimization Method for Discrete Optimization Problems [J].
Chen, Wei-Neng ;
Zhang, Jun ;
Chung, Henry S. H. ;
Zhong, Wen-Liang ;
Wu, Wei-Gang ;
Shi, Yu-hui .
IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, 2010, 14 (02) :278-300
[10]  
Clerc M., 2004, Discrete Particle Swarm Optimization, illustrated by the Traveling Salesman Problem, P219, DOI [DOI 10.1007/978-3-540-39930-8_8, 10.1007/978-3-540-39930-8_8, DOI 10.1007/978-3-540-39930-8]