Approximately optimal construction of parallel algorithm portfolios by evolutionary intelligence
Shengcai Liu, Peng Yang, Ke Tang · Scientia Sinica Technologica · 2022
As a high-performance general-purpose form of parallel solvers, parallel algorithm portfolios (PAPs) have recently shown great performance for solving decision, counting, continuous, and discrete optimization problems. However, the manual construction of PAPs is laborious work, which typically requires substantial domain knowledge and human effort. To address this issue, this paper proposes AutoPAP, an evolutionary intelligence-based method for PAP construction. Overall, AutoPAP follows the (n+1) evolutionary framework, i.e., in each generation, n candidate algorithms are generated, and the best one among them is retained in the PAP. Considering that the algorithm configuration space is typically very large, this study designs a highly effective mutation operator to improve the practical performance of AutoPAP and further theoretically proves that AutoPAP can achieve (1−1/e) approximation. Finally, to validate the effectiveness of AutoPAP, this study uses it to build a PAP, namely, TSP_PAP, for traveling salesman problems (TSPs). The test results show that TSP_PAP significantly outperforms state-of-the-art TSP solvers EAX and LKH in terms of efficiency (runtime) and effectiveness (solution quality). On 128 TSP instances of sizes ranging from 1000 to 30000, compared with LKH and EAX, TSP_PAP can reduce the average runtime by at least 45.71% and lower the average deviation ratio by at least 87.50%, indicating the huge potential of AutoPAP in automatic algorithm design and evolution.