求解0-1二次规划问题的迭代禁忌搜索算法

求解求解求解求解0-1二次规划问题的迭代禁忌二次规划问题的迭代禁忌二次规划问题的迭代禁忌二次规划问题的迭代禁忌搜索搜索搜索搜索算法算法算法算法张爱君张爱君张爱君张爱君，，，，秦新强秦新强秦新强秦新强，，，，龚春琼龚春琼龚春琼龚春琼(西安理工大学应用数学系，西安710048)摘摘摘摘要要要要：：：：提出迭代禁忌算法求解0-1二次规划问题。在局部搜索过程中，使用禁忌搜索贪心跳坑策略，能够使算法有效跳出局部最优值的陷阱。采用国际上公认的30个算例作为算法测试实验集，与传统的禁忌搜索、模拟退火算法以及混合算法进行比较。实验结果表明，该算法在所有算例上都能够得到文献中报告的最优解，且计算效率明显优于其他算法。关键词关键词关键词关键词：：：：启发式算法；0-1二次规划；局部搜索；禁忌搜索；跳坑策略IteratedTabuSearchAlgorithmforSolving0-1BinaryQuadraticProgrammingProblemZHANGAi-jun,QINXin-qiang,GONGChun-qiong(DepartmentofAppliedMathematics,Xi’anUniversityofTechnology,Xi’an710048,China)【【【【Abstract】】】】ThispaperpresentsaniteratedTabuSearch(TS)algorithmfortheBinaryQuadraticProgramming(BQP)problem.TheTSastheLocalSearch(LS)andanewperturbationstrategymakesthesearchjumpintoamorepromisingareawhenTSfallingintothelocaloptimum.Experimentalresultsshowthattheproposedalgorithmcanreachthebestknownsolutiononallthe30largeOR-libraryinstancesandcomparisonswithTS.SimulatedAnnealing(SA)andMemeticAlgorithm(MA)demonstratethecompetitivenessoftheproposedalgorithm.【【【【Keywords】】】】HeuristicsAlgorithm(HA);0-1BinaryQuadraticProgramming(BQP);LocalSearch(LS);TabuSearch(TS);perturbationstrategyDOI:10.3969/j.issn.1000-3428.2012.01.043计算机工程ComputerEngineering第38卷第1期Vol.38No.12012年1月January2012····人工智能及识别技术人工智能及识别技术人工智能及识别技术人工智能及识别技术····文章编号文章编号文章编号文章编号：：：：1000————3428(2012)01————0140————03文献标识码文献标识码文献标识码文献标识码：：：：A中图分类号中图分类号中图分类号中图分类号：：：：TP301.61概述概述概述概述0-1二次规划(BinaryQuadraticProgramming,BQP)问题是一类选取合适的二进制决策变量，使得二次目标函数值极大化的优化问题。这是一个典型的NP难问题，它有许多方面的应用，如计算机辅助设计、社会心理学、交通管理、金融分析等。同时，BQP问题是组合优化问题的一种通用模型，大多数组合优化问题都能够转化成该问题后进行求解[1]，如图着色问题[2]、多维背包问题等。对这一问题，学者们提出了多种求解算法，这些算法大致可以归结为2大类：完整算法和启发式算法。早期较成功的完整算法有分支定界法和分支切割法，这些算法在当变量个数超过100时，无法在一个合理的时间求得优化解。一些学者提出求解此问题的启发式算法，如混合算法[3](MemeticAlgorithm,MA)、进化论算法[4](EvolutionaryAlgorithm,EA)、禁忌搜索算法[5](TabuSearch,TS)、模拟退火算法[5](SimulatedAnnealing,SA)、局部搜索算法[6](LocalSearch,LS)等，这些算法在求解规模较大的问题时能够在可接受的时间求得问题的近似优化解。禁忌搜索已在许多组合优化问题上被证明是一种非常高效的搜索算法[7]。但是，同其他局部搜索算法一样，禁忌搜索也难以避免落入局部最优值的陷阱。针对这个缺陷，需要设计一种有效的跳坑策略使其逃离该局部最优值区域，找到更高优度的解。基于以上研究，本文设计求解BQP问题的迭代禁忌搜索(IteratedTabuSearch,ITS)算法。该算法首先利用禁忌搜索得到一个局部最优解，然后合理扰动该局部最优解得到一个新的起始解，也就是跳坑过程，之后对新生成的解应用禁忌搜索优化。禁忌搜索与跳坑迭代若干步后，就可以得到问题的最优解。同时，本文提出一个针对UBQP问题的贪心跳坑策略。跳坑的思想是：如果翻转局部最优解中的某些变量使得到的邻域解的目标函数值与局部最优解的目标函数值差值较小，那么优先翻转这些变量。利用本文提出的ITS算法，对国际上公认的OR-library中的3组共30个最大的算例(beas500、beas1000、beas2500)进行实验，并与禁忌搜索、模拟退火算法[3]和混合算法[3]进行比较。2问题描述问题描述问题描述问题描述BQP问题是选取合适的二进制决策变量，使得二次目标函数值极大化的优化问题，可用如下公式描述：,11maximize()'{0,1},1,2,,nnijijiijfqxxxin====∈∀=∑∑xxQx⋯(1)其中，x是行向量；x’是x的转置；Q是一个n维对称矩阵；qij为Q中第i行第j列的元素值。3迭代禁忌算法迭代禁忌算法迭代禁忌算法迭代禁忌算法对BQP问题，迭代禁忌算法会不断地在禁忌搜索与跳坑之间交替进行。首先，从一个随机构造的初始解出发，经过合适步长禁忌搜索后得到一个局部最优解；然后，应用跳坑策略对该局部最优解进行扰动，扰动后的解作为下次禁忌搜索的初始解；不断重复这样的过程直到停机条件到来。3.1邻域结构邻域结构邻域结构邻域结构对于任意一个解x=(x1,x2,…,xi,…,xn)，其中，xi∈{0,1}，翻转任一变量xi到它的补值1–x，即得到它的一个邻居解基金项目基金项目基金项目基金项目：：：：国家自然科学基金资助项目(50879069)作者简介作者简介作者简介作者简介：：：：张爱君(1979－)，女，讲师、硕士，主研方向：人工智能，应用数学；秦新强，教授、博士；龚春琼，讲师、硕士收稿日期收稿日期收稿日期收稿日期：：：：2011-06-20E-mail：：：：[e-mail]第38卷第1期141张爱君，秦新强，龚春琼：求解0-1二次规划问题的迭代禁忌搜索算法Ni=(xi,…,(1–xi),…,xn)。得到的所有n个邻居解构成的集合作为解x的邻域结构N(x)={N1,N2,…,Nn}。这种邻域结构在0-1优化问题，如UBQP、多维背包以及SAT问题中应用非常普遍，邻域搜索的算法复杂度是O(n)。3.2禁忌搜索禁忌搜索禁忌搜索禁忌搜索禁忌搜索过程从随机生成的一个初始解x=(x1,x2,…,xi,…,xn)出发，邻域搜索总是选择不出现在禁忌表中且最优的邻域解作为新的当前解。接受新解后，算法按一定方式更新禁忌表。同时，当翻转禁忌表中的某个变量能产生比当前最优解更优的解时，则接受禁忌表中的此候选解。按照以上规则迭代合适的步长后，禁忌搜索过程终止。对于任意一个解x，它的邻居解的目标函数值不必根据式(1)重新计算，本文使用文献[8]中的流线型更新策略。该策略使用一个长度为n的数组记录当前解x的所有邻居解与目标函数值的差值，将该内存称为Delta表。它的初始化根据式(2)计算。当翻转了某个变量xi后，依据式(3)更新Delta表。,,1(12)((,))jiiiijNjixxqqij∈≠=Δ=−+∑(2)其中，{1,2,,}in∈⋯。(,)(,)jjjjijjijiqijjixxqijjixx−Δ=Δ=Δ+≠≠Δ−≠=且且(3)其中，{1,2,,}jn∈⋯。令()ijijjiqqqij=+且0jiq=，将对角矩阵Q转化为下三角阵。(,)qij表示ijq或jiq。若ij，(,)ijqijq=；若ij，(,)jiqijq=。当禁忌某个变量xi时，设置禁忌表位置i处的值为iter+tt，其中，iter是当前禁忌搜索的迭代步长；tt是禁忌长度。判断某个变量是否被禁忌，只需要比较此时的迭代步长iter与该变量在禁忌表中对应的值，若是小于等于关系，则该变量处于禁忌状态；否则，变量未被禁忌。通过大量的实验得出，依照式(4)设置禁忌长度tt是合适的，其中，n是算例中变量个数；rand(10)随机返回集合{1,2,…,10}的一个整数。/150(10)ttnrand=+(4)3.3贪心跳坑策略贪心跳坑策略贪心跳坑策略贪心跳坑策略禁忌搜索算法是求解BQP问题的高效算法，但是很可能会陷入局部最优值的陷阱。本文提出了一种贪心跳坑策略，以进一步提高算法的效率。跳坑策略的思想是：如果翻转局部最优解中的某些变量会使得到的邻域解的目标函数值与局部最优解的差值较小，那么这些变量应该被优先翻转。原因在于当禁忌搜索陷入局部最优值陷阱时，它的邻域解不可能优于该局部最优解。邻域解的目标函数值较大意味着翻转该局部最优解的相关变量对目标函数值损伤较小。根据贪心思想，跳坑时应该优先翻转这些变量。3.4算法描述算法描述算法描述算法描述有了禁忌搜索和跳坑策略，本文算法可以描述如下：(1)随机化初始解x=(x1,x2,…,xn)，其中，xi∈{0,1}。(2)计算x的目标函数值f(x)，令{f*=f(x),x*=x}，初始化delta表和禁忌表，迭代次数iter=0。(3)查询禁忌表，构造禁忌变量集合VT和非禁忌变量集合V。(4)查询delta表，分别记录VT和V集合中delta值最大的变量下标，分别记作i、j。(5)若ΔxiΔxj并且f(x)+Δxif(x*)，k=i；否则，k=j。(6)赋值xk=1–xk，得到新解x=(x1,x2,…,xk,…,xn)，f(x)=f(x)+Δxk，更新delta表以及禁忌表，iter++；若f(x)f*，{f*=f(x)，x*=x，记录x*的delta表Δ*}。(7)若iter≤MaxIters，转入步骤(3)；否则，转入步骤(8)。(8)使用快速排序方法对Δ*从小到大排序，对于排名前1/3的变量，分别跳变其值到它对应的补值，其他变量的值保持与x*中对应的值一致，得到新解x。(9)若停机条件满足，输出x*、f(x*)，算法终止；否则，转入步骤(2)。对迭代步长MaxIters设置，可选取一些样本算例进行小规模测试实验，从而对迭代的规模进行预估，然后从中选取相对合适的迭代步长即可。本实验采用线性预估方案，通过实验得出迭代步长，MaxIters设置为5n左右时(4n~7n均可)得出的结果较好，其中，n为算例中变量的个数。当算例规模有变化时，可以适当向左或向右微调MaxIters值。根据邻域搜索以及实验中设置的迭代步长，不难得出，本文算法的时间复杂度为O(n2)。4实实实实验验验验结果与分析结果与分析结果与分析结果与分析本文提出的ITS算法用C语言编程实现，并对OR-library中的3组(beas500、beas1000、beas2500)共30个最大算例在Intel(R)Xeon(R)E5440(2GBRAM/2.83GHzCPU)微机上进行了计算测试。考虑到算法有随机因素，每个测试算例被计算30次。表1~表3分别给出了ITS算法的实验结果以及和禁忌搜索TS、模拟退火算法(SA-KN)[3]、混