近似最优并行算法组智能汇聚构造

作     者：刘晟材 杨鹏 唐珂 LIU ShengCai;YANG Peng;TANG Ke

作者机构：南方科技大学计算机科学与工程系深圳518055 广东省类脑智能计算重点实验室深圳518055 

出 版 物：《中国科学：技术科学》 (Scientia Sinica(Technologica))

年 卷 期：2023年第53卷第2期

页      面：280-290页

核心收录：

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 081104[工学-模式识别与智能系统] 08[工学] 0835[工学-软件工程] 0701[理学-数学] 0811[工学-控制科学与工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：广东省类脑智能计算重点实验室(编号:2020B121201001) 国家自然科学基金青年科学基金(批准号:61806090)资助项目 

主　　题：求解器 并行算法组 演化计算 自动算法设计 旅行商问题 组合优化 

摘      要：作为一种高性能通用并行求解器,并行算法组(parallel algorithm portfolios, PAPs)近年来在判定、计数以及连续、离散优化等问题上取得了突出的求解效果.传统人工构造PAP的方式依赖于大量领域知识,门槛极高.为了解决这一问题,本文提出了一种基于演化优化的PAP智能汇聚自动构造方法AutoPAP.整体上, AutoPAP遵循(n+1)演化优化框架,即在每一代生成n个候选算法,并保留最优算法加入到PAP中.考虑到算法配置空间往往非常巨大且涉及混合变量,本文设计了专用变异算子以提升AutoPAP的实际性能,并证明了AutoPAP在理论上可以达到(1-1/e)近似最优构造效果.最后,本文以旅行商问题(traveling salesman problems, TSP)为例,使用AutoPAP构造得到TSP_PAP.实验结果表明,在主流TSP测试集上, TSP_PAP的求解效率和效果均显著好于当前TSP上公认性能最佳的求解器EAX和LKH.在128个规模1000~30000的TSP测试样例上,相比于EAX和LKH, TSP_PAP可以将平均求解时间缩短至少45.71%,并将平均误差率降低至少87.50%,这体现出AutoPAP在算法自动设计与演化方面的巨大潜力.