Self-adaptive Decomposition and Incremental Hyperparameter Tuning Across Multiple Problems

Liu, Jialin; Yao, Xin

10.1109/SSCI44817.2019.9002966

2019

978-1-7281-2486-5

2019 IEEE Symposium Series on Computational Intelligence, SSCI 2019

1590-1597

6-9 Dec. 2019

Xiamen, China

345 E 47TH ST, NEW YORK, NY 10017 USA

Institute of Electrical and Electronics Engineers Inc.

The Capacitated Arc Routing Problem (CARP) is a NP-hard combinatorial optimisation problem with numerous real-world applications. Several divide-and-conquer approaches, controlled by one or more hyperparameters, have been proposed to tackle large-scale CARPs. The tuning of hyperparameters can be computationally expensive due to the lack of priori knowledge, the size of the configuration space, and the time required for solving a CARP instance. Motivated by this time consuming task, we propose a scalable approach based on self-adaptive hierarchical decomposition (SASAHiD) to scale up existing methods. We take a state-of-the-art decomposition method for large-scale CARPs called SAHiD as an example to carry out experiments on two sets of real-world CARP instances with hundreds to thousands of tasks. The results demonstrate that SASAHiD outperforms SAHiD significantly with fewer hyperparameters, thus the dimension of associated configuration space is reduced. Moreover, we propose an incremental hyperparameter tuning approach across multiple problem instances to learn the hyperparameters of SASAHiD on a set of instances with different sizes. SASAHiD with optimised hyperparameters achieves better or competitive results with the SASAHiD using default hyperparameters when solving problem instances that it has never seen in the training set.
© 2019 IEEE.

Capacitated arc routing problem self-adaptive decomposition incremental hyperparameter tuning permutationbased optimisation

第一

英语

EI ; CPCI-S

[2017YFC0804003]

Computer Science

Computer Science, Artificial Intelligence

WOS:000555467201103

20201108276672

Artificial intelligence ; Combinatorial optimization ; Network routing ; Wave functions

Artificial Intelligence:723.4 ; Mathematics:921 ; Optimization Techniques:921.5

EV Compendex

Southern University of Science and Technology, Shenzhen Key Laboratory of Computational Intelligence, University Key Laboratory of Evolving, Intelligent Systems of Guangdong Province, Shenzhen; 518055, China

Liu, Jialin,Yao, Xin. Self-adaptive Decomposition and Incremental Hyperparameter Tuning Across Multiple Problems[C]. 345 E 47TH ST, NEW YORK, NY 10017 USA:Institute of Electrical and Electronics Engineers Inc.,2019:1590-1597.