1、近似最优并行算法组智能汇聚构造刘晟材1,2,杨鹏1,2,唐珂1,2*1.南方科技大学计算机科学与工程系,深圳 518055;2.广东省类脑智能计算重点实验室,深圳 518055*E-mail:收稿日期:2021-08-14;接受日期:2021-10-14;网络版发表日期:2022-08-03广东省类脑智能计算重点实验室(编号:2020B121201001)和国家自然科学基金青年科学基金(批准号:61806090)资助项目摘要作为一种高性能通用并行求解器,并行算法组(parallel algorithm portfolios,PAPs)近年来在判定、计数以及连续、离散优化等问题上取得了突出的求解
2、效果.传统人工构造PAP的方式依赖于大量领域知识,门槛极高.为了解决这一问题,本文提出了一种基于演化优化的PAP智能汇聚自动构造方法AutoPAP.整体上,AutoPAP遵循(n+1)演化优化框架,即在每一代生成n个候选算法,并保留最优算法加入到PAP中.考虑到算法配置空间往往非常巨大且涉及混合变量,本文设计了专用变异算子以提升AutoPAP的实际性能,并证明了AutoPAP在理论上可以达到(11/e)近似最优构造效果.最后,本文以旅行商问题(traveling salesman problems,TSP)为例,使用AutoPAP构造得到TSP_PAP.实验结果表明,在主流TSP测试集上,TS
3、P_PAP的求解效率和效果均显著好于当前TSP上公认性能最佳的求解器EAX和LKH.在128个规模100030000的TSP测试样例上,相比于EAX和LKH,TSP_PAP可以将平均求解时间缩短至少45.71%,并将平均误差率降低至少87.50%,这体现出AutoPAP在算法自动设计与演化方面的巨大潜力.关键词求解器,并行算法组,演化计算,自动算法设计,旅行商问题,组合优化1引言过去20年间,并行计算架构得到了巨大发展1.现如今多核中央处理器(central processing unit,CPU)已然成为个人计算机的标准配置,而在那些专为科学计算而搭建的计算平台如工作站和服务器上,CPU核数
4、动辄几十上百.如此丰富的计算资源也给算法/求解器设计者们提出了新的挑战:如何有效利用并行计算平台以更好地解决实际应用中的复杂问题?事实上,无论是学术界还是工业界,对于并行求解器的研究已持续多年.例如,在一些重要的基本计算问题如布尔可满足性问题(boolean satisfiability problem,SAT)、约束满足问题(constraint satisfaction problem,CSP)、回答集编程问题(answer set programming,ASP)、混合线性整数规划问题(mixed integer linear programming,MILP)和黑箱连续优化问题(bla
5、ck-box continuous opti-mization,BO)上,并行求解器26已经成为主流.此外,在很多基础工业软件如数学规划求解器CPLEX引用格式:刘晟材,杨鹏,唐珂.近似最优并行算法组智能汇聚构造.中国科学:技术科学,2023,53:280290Liu S C,Yang P,Tang K.Approximately optimal construction of parallel algorithm portfolios by evolutionary intelligence(in Chinese).Sci Sin Tech,2023,53:280290,doi:10.136
6、0/SST-2021-0372 2022 中国科学杂志社中国科学:技术科学2023 年第 53 卷第 2 期:280 290SCIENTIA SINICA T群体智能激发汇聚及应用专辑论 文(https:/ algorithm portfolios,PAP),在判定8、计数以及连续6、离散优化810等问题上取得了突出的求解效果,逐渐成为了研究热点.本质上PAP是一个包含若干算法的集合,其中每个算法都被称作该PAP的成员算法.当PAP被用于求解某个问题样例时,其所有成员算法都将在该问题样例上相互独立地并行运行,且在达到停止条件时同时终止.可以看到,在PAP运行过程中,各个成员算法之间不涉及任何信
7、息交互,因而PAP的结构复杂度相比于传统并行求解器要低得多.另一方面,构造高性能PAP并不容易.假设一个PAP的某个成员算法 在任何问题样例上的性能都超过了其他成员算法,那么该PAP的性能实际上仅等价于算法 的性能.换言之,除 之外的成员算法虽然使用了与 相同的计算资源,却并未给PAP带来任何性能增益.因此,直观上而言,一个高性能PAP所包含的成员算法在性能上应具备差异性,即各个成员算法都应该有自身最为擅长解决的问题样例类型.可以说,认识到这种差异性是构造高性能PAP的前提条件.然而,在实际应用中找到符合以上条件的算法并不容易,这要求研发人员对各种算法的优势以及短板有充分认识,且需耗费大量时间
8、进行后续调整.这不仅带来了高昂的人力成本,也在无形中提高了PAP的研发门槛,阻碍其进一步发展.为了解决以上问题,本文提出了一种基于n(+1)演化优化框架的PAP智能汇聚构造方法AutoPAP,其接受一个算法配置空间和一个问题样例集合作为输入,从前者中自动为PAP选择成员算法,以使得PAP在后者上的性能达到最优.为了提升AutoPAP的实际应用效果,本文结合自动算法配置技术和分而治之策略设计了可以高效搜索算法配置空间的变异算子.进一步地,本文从理论上证明了AutoPAP可以达到e(11/)的近似最优比.最后,本文以旅行商问题(traveling salesman pro-blems,TSP)为例
9、,验证AutoPAP的有效性.具体而言,本文使用AutoPAP构造得到TSP_PAP,并将其和当前TSP上性能最佳的求解器LKH11以及EAX12作对比.实验结果表明,在主流TSP测试集上,TSP_PAP无论是在求解效率还是在求解效果上均显著好于LKH和EAX.在128个规模100030000的TSP测试样例上,相比于LKH和EAX,TSP_PAP可以将平均求解时间缩短至少45.71%,并将平均误差率降低至少87.50%.可以说,TSP_PAP是当前综合性能最强的TSP求解器,这体现出AutoPAP在算法自动设计与演化方面的巨大潜力.本文的后续章节安排如下.第二节分别给出PAP以及PAP自动构
10、建问题的形式化定义.第三节首先描述AutoPAP框架以及变异算子,然后证明AutoPAP的近似最优性.第四节以TSP问题为例,验证AutoPAP的有效性.第五节对全文进行总结.2问题定义2.1PAP形式化定义令P表示PAP,令k表示P的规模,即成员算法的数量,P的形式化定义如下:P=,.,(1)k12式中,i表示P中第i个成员算法.为 了 避 免 引 入 过 多 的 数 学 符 号,本 文 以m(solver,instances)表示在性能指标m下,求解器“sol-ver”在问题样例集合“instances”上的性能.注意“sol-ver”可以是单个算法,也可以是一个PAP,而“instanc
11、es”既可以是单个问题样例(此时可以看作只含有一个样例的集合),也可以是包含多个问题样例的集合.当使用P来求解给定问题样例z时,P中所有成员算法,即,.,k12,都将在z上相互独立地并行运行,直到达到终止条件.这里的终止条件依赖于待求解的问题和感兴趣的性能指标m.具体而言,假设待求解的问题为判定类(decision)问题(如SAT问题),那么在PAP中国科学:技术科学2023 年第 53 卷第 2 期281运行过程中只要任何一个成员算法率先输出了对z的判定结果,即“是”或“否”,所有成员算法都会立即被终止.因此求解z所需的运行时间就是其最佳成员算法求解z所需的运行时间.此外,在这种情况下,通常
12、会引入一个最长运行时间(又称截止时间,Tmax)以防止PAP运行时间过长.如果在Tmax时间内,没有任何成员算法输出判定答案,那么所有成员算法也会被立即终止,且此次求解被判定为超时(Timeout)或失败(Failure).另一方面,假设待求解的问题为优化问题(如TSP问题),终止条件则依赖于感兴趣的性能指标m.如果m是“找到一个近似最优解(如与最优解的差距不超过预先给定的阈值)所需的运行时间”,那么只要任何一个成员算法率先找到了这类解,所有成员算法都会立即被终止.与考虑决策问题时一样,在这种情况下可以引入最长运行时间Tmax以防止PAP运行时间过长.如果m是“在给定时间Tmax内找到的解的质
13、量”,那么每个成员算法都将在运行Tmax时间后终止,最后P将成员算法找到的所有解中最好的那个作为输出.可以看到,无论考虑何种问题类型和何种性能指标,P在问题样例z上的性能P zm(,)总是其成员算法,.,k12在z上取得的最好性能,即P zzm(,)=maxm(,).(2)P不失一般性,假设对性能指标m而言,值越大越好.值得注意的是,实际中考虑优化问题且m是“找到一个近似最优解所需的运行时间”时,我们往往并不知道待求解问题的真正最优解,也就无法计算成员算法找到的解与最优解的距离,从而无法判断是否是近似最优解,最终导致无法测量算法的运行时间.但是,这也不会影响式(2)的成立.进一步地,P在问题样
14、例集合I上的性能是P在I中各个问题样例上的性能的平均值:P IIP zm(,)=1m(,),(3)zI式中,I表示集合I的势.2.2PAP自动构建问题为了将PAP构建过程自动化,本文考虑如下的优化问题:从给定算法配置空间 中选择k个成员算法组成P,以使得后者在给定问题样例集合I上的性能达到最优.其中,I被称作训练集,其应当充分代表P的目标使用场景.换言之,如果P在I上性能良好,那么可以推断P在实际使用时也具有良好的性能.算法配置空间 由一组参数化算法B BB,.,c12所定义,方便起见,我们称这类算法为基础算法.其中每个基础算法Bi都有若干参数,参数的取值控制着Bi方方面面的行为,进而对Bi的
15、性能有着巨大的影响.因此,当Bi的参数取不同值时,可以认为得到了不同的算法;在此基础上,对Bi的参数取遍所有可能的值,最终得到的所有独一无二的算法所组成的集合,就是Bi的算法配置空间,记为i.例如,假设B1有两个参数和,其各有两种取值,0,1,0,1;那么1一共包含4个不同的算法,即=(:0,:0),(:0,:1),1(:1,:0),(:1,:1),其中:0表示参数的取值为0.如图1所示,多个基础算法B BB,.,c12所定义的算法配置空间=.c12.例如,假设现在除了上面例子中的B1,还考虑另一个基础算法B2,其有一个参数0,1,因此=(:0),(:1)2,最终=12.如前所述,P中每个成员
16、算法i都是从 中选择得到,因此i的搜索空间大小为.此外,由等式(2)可知,假设P已经包含成员算法i,那么再将同样的算法i加入到P则不会带来任何性能增益.因此,在为P寻找新成员算法时,可以简单地先将P已包含的成员算法排除掉,这可以保证最终得到的P中各个成员算法互不相同.实际上,P可以看作 的子集,那么P的整体搜索空间大小为iO(+1)=()ikk=1.综上所述,PAP自动构建问题的形式化定义如下:PP I=argmaxm(,),(4)PPk*=式中,P*表示最优PAP.图 1基础算法B1,B2,.,Bc所定义的算法配置空间Figure 1Algorithm configuration space defined by base algorithmsB1,B2,.,Bc.刘晟材等:近似最优并行算法组智能汇聚构造2823PAP智能汇聚构造方法3.1AutoPAP框架本文提出了一种基于演化优化的方法AutoPAP来解决上文中的PAP自动构建问题.演化算法是一类具有广泛适用性的全局优化方法13,其通过将种群进行交叉(crossover)、变异(mutation)等操作,并在一定的控制参数(如演化