中文版 | English
Title

Approximately optimal construction of parallel algorithm portfolios by evolutionary intelligence

Author
Corresponding AuthorKe TANG
Publication Years
2022-08
DOI
Source Title
Abstract

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.

Keywords
Indexed By
Language
Chinese
SUSTech Authorship
First ; Corresponding
Data Source
人工提交
Citation statistics
Cited Times [WOS]:0
Document TypeJournal Article
Identifierhttp://kc.sustech.edu.cn/handle/2SGJ60CL/416236
DepartmentDepartment of Computer Science and Engineering
理学院_统计与数据科学系
Affiliation
1.Department of Computer Science and Engineering, Southern University of Science and Technology, Shenzhen 518055, China;
2.Guangdong Key Laboratory of Brain-Inspired Intelligent Computation, Shenzhen 518055, China
First Author AffilicationDepartment of Computer Science and Engineering
Corresponding Author AffilicationDepartment of Computer Science and Engineering
First Author's First AffilicationDepartment of Computer Science and Engineering
Recommended Citation
GB/T 7714
ShengCai LIU,Peng YANG,Ke TANG. Approximately optimal construction of parallel algorithm portfolios by evolutionary intelligence[J]. SCIENTIA SINICA Technologica,2022.
APA
ShengCai LIU,Peng YANG,&Ke TANG.(2022).Approximately optimal construction of parallel algorithm portfolios by evolutionary intelligence.SCIENTIA SINICA Technologica.
MLA
ShengCai LIU,et al."Approximately optimal construction of parallel algorithm portfolios by evolutionary intelligence".SCIENTIA SINICA Technologica (2022).
Files in This Item:
File Name/Size DocType Version Access License
1557C31578A94436A53D(1717KB) Restricted Access--
Related Services
Recommend this item
Bookmark
Usage statistics
Export to Endnote
Export to Excel
Export to Csv
Altmetrics Score
Google Scholar
Similar articles in Google Scholar
[ShengCai LIU]'s Articles
[Peng YANG]'s Articles
[Ke TANG]'s Articles
Baidu Scholar
Similar articles in Baidu Scholar
[ShengCai LIU]'s Articles
[Peng YANG]'s Articles
[Ke TANG]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[ShengCai LIU]'s Articles
[Peng YANG]'s Articles
[Ke TANG]'s Articles
Terms of Use
No data!
Social Bookmark/Share
No comment.

Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.