The Capacitated Arc Routing Problem (CARP) is a general and challenging arc routing problem. As the problem size increasing, exact methods are not applicable, and heuristic and meta-heuristic algorithms are promising approaches to solve it. To obtain good performance, parameter values of heuristics or meta-heuristics should be properly set. In recent years, automatic parameter tuning, which includes off-line and online parameter tuning, has attracted considerable attention in the evolutionary computation community. At present, parameters are usually determined through simple off-line parameter tuning, such as empirical analysis or grid search, when designing algorithms for CARP. However, using off-line parameter tuning on CARP has some disadvantages, among which the computational cost is the serious one. This work proposed an online parameter tuning approach using exponential recency-weighted kernel density estimation (ERW-KDE), and combines it with the SAHiD algorithm, which is an hierarchical decomposition based algorithm for CARP, to constitute the online parameter tuned SAHiD (OPT-SAHiD) algorithm. The experimental results show that OPT-SAHiD significantly outperforms the compared algorithms on two CARP benchmark sets owing to the proposed online automatic parameter tuning approach. The proposed online automatic parameter tuning approach based on ERW-KDE not only improves the performance of SAHiD algorithm, but also removes the additional computational overhead required for offline parameter tuning. © 2020 IEEE.
|Title of host publication
|2020 IEEE Congress on Evolutionary Computation, CEC 2020 - Conference Proceedings
|Institute of Electrical and Electronics Engineers Inc.
|Published - Jul 2020
Bibliographical noteThis work was supported by Guangdong Basic and Applied Basic Research Foundation (Grant No. 2019A1515110575), Guangdong Provincial Key Laboratory (Grant No. 2020B121201001), the Program for Guangdong Introducing Innovative and Enterpreneurial Teams (Grant No. 2017ZT07X386), Shenzhen Science and Technology Program (Grant No. KQTD2016112514355531), the Program for University Key Laboratory of Guangdong Province (Grant No. 2017KSYS008).
- automatic parameter tuning
- Capacitated arc routing problem
- kernel density estimation
- online parameter tuning