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

计 算 机 工 程 第卷 第1期 38

Computer Engineering V ol.38 No.1

文章编号：文章编号：1000—3428(2012)01—0140—03 ·人工智能及识别技术·人工智能及识别技术·

2012年1月

January 2012

文献标识码：文献标识码：A

中图分类号：中图分类号：TP301.6

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

张爱君，张爱君，秦新强，秦新强，龚春琼

(西安理工大学应用数学系，西安 710048)

摘 要：提出迭代禁忌算法求解0-1二次规划问题。在局部搜索过程中，使用禁忌搜索贪心跳坑策略，能够使算法有效跳出局部最优值的陷阱。采用国际上公认的30个算例作为算法测试实验集，与传统的禁忌搜索、模拟退火算法以及混合算法进行比较。实验结果表明，该算法在所有算例上都能够得到文献中报告的最优解，且计算效率明显优于其他算法。 关键词：关键词：启发式算法；0-1二次规划；局部搜索；禁忌搜索；跳坑策略

Iterated Tabu Search Algorithm

for Solving 0-1 Binary Quadratic Programming Problem

ZHANG Ai-jun, QIN Xin-qiang, GONG Chun-qiong

(Department of Applied Mathematics, Xi’an University of Technology, Xi’an 710048, China)

【Abstract 】This paper presents an iterated Tabu Search(TS) algorithm for the Binary Quadratic Programming(BQP) problem. The TS as the Local Search(LS) and a new perturbation strategy makes the search jump into a more promising area when TS falling into the local optimum. Experimental results show that the proposed algorithm can reach the best known solution on all the 30 large OR-library instances and comparisons with TS. Simulated Annealing(SA) and Memetic Algorithm(MA) demonstrate the competitiveness of the proposed algorithm.

【Key words】Heuristics Algorithm(HA); 0-1 Binary Quadratic Programming(BQP); Local Search(LS); Tabu Search(TS); perturbation strategy DOI: 10.3969/j.issn.1000-3428.2012.01.043

1 概述

0-1二次规划(Binary Quadratic Programming, BQP) 问题是一类选取合适的二进制决策变量，使得二次目标函数值极大化的优化问题。这是一个典型的NP 难问题，它有许多方面的应用，如计算机辅助设计、社会心理学、交通管理、金融分析等。同时，BQP 问题是组合优化问题的一种通用模型，大多数组合优化问题都能够转化成该问题后进行求解[1]，如图着色问题[2]、多维背包问题等。

对这一问题，学者们提出了多种求解算法，这些算法大致可以归结为2大类：完整算法和启发式算法。早期较成功的完整算法有分支定界法和分支切割法，这些算法在当变量个数超过100时，无法在一个合理的时间求得优化解。一些学者提出求解此问题的启发式算法，如混合算法[3](Memetic Algorithm, MA)、进化论算法[4](Evolutionary Algorithm, EA)、禁忌搜索算法[5](Tabu Search, TS)、模拟退火算法[5](Simulated Annealing, SA) 、局部搜索算法[6](Local Search, LS) 等，这些算法在求解规模较大的问题时能够在可接受的时间求得问题的近似优化解。

禁忌搜索已在许多组合优化问题上被证明是一种非常高效的搜索算法[7]。但是，同其他局部搜索算法一样，禁忌搜索也难以避免落入局部最优值的陷阱。针对这个缺陷，需要设计一种有效的跳坑策略使其逃离该局部最优值区域，找到更高优度的解。基于以上研究，本文设计求解BQP 问题的迭代禁忌搜索(Iterated Tabu Search, ITS)算法。该算法首先利用禁忌搜索得到一个局部最优解，然后合理扰动该局部最优解得到一个新的起始解，也就是跳坑过程，之后对新生成的解应用禁忌搜索优化。禁忌搜索与跳坑迭代若干步后，就可以得到问题的最优解。同时，本文提出一个针对UBQP 问题的

贪心跳坑策略。跳坑的思想是：如果翻转局部最优解中的某些变量使得到的邻域解的目标函数值与局部最优解的目标函数值差值较小，那么优先翻转这些变量。

利用本文提出的ITS 算法，对国际上公认的OR-library 中的3组共30个最大的算例(beas500、beas1000、beas2500) 进行实验，并与禁忌搜索、模拟退火算法[3]和混合算法[3]进行比较。

2 问题描述

BQP 问题是选取合适的二进制决策变量，使得二次目标函数值极大化的优化问题，可用如下公式描述：

maximize f (x ) =xQx ' =∑∑q ij x i x j , x i ∈{0,1}, ∀i =1,2, ⋯, n (1)

i =1j =1n n

其中，x 是行向量；x ’是x 的转置；Q 是一个n 维对称矩阵；q ij 为Q 中第i 行第j 列的元素值。

3 迭代禁忌算法

对BQP 问题，迭代禁忌算法会不断地在禁忌搜索与跳坑之间交替进行。首先，从一个随机构造的初始解出发，经过合适步长禁忌搜索后得到一个局部最优解；然后，应用跳坑策略对该局部最优解进行扰动，扰动后的解作为下次禁忌搜索的初始解；不断重复这样的过程直到停机条件到来。 3.1 邻域结构

对于任意一个解x =(x 1, x 2,…, x i , …, x n ) ，其中，x i ∈{0,1}，翻转任一变量x i 到它的补值1–x，即得到它的一个邻居解

基金项目：基金项目：国家自然科学基金资助项目(50879069)

作者简介：作者简介：张爱君(1979－) ，女，讲师、硕士，主研方向：人工智能，应用数学；秦新强，教授、博士；龚春琼，讲师、硕士 收稿日期：收稿日期：2011-06-20 E-mail ：[email protected]

第38卷 第1期 张爱君，秦新强，龚春琼：求解 0-1 二次规划问题的迭代禁忌搜索算法 141 N i =(x i ,…,(1–xi ), …, x n ) 。得到的所有n 个邻居解构成的集合作为解x 的邻域结构N (x )={N 1, N 2,…, N n }。这种邻域结构在0-1优化问题，如UBQP 、多维背包以及SAT 问题中应用非常普遍，邻域搜索的算法复杂度是O (n ) 。

3.2 禁忌搜索

禁忌搜索过程从随机生成的一个初始解x =(x 1, x 2,…, x i , …, x n ) 出发，邻域搜索总是选择不出现在禁忌表中且最优的邻域解作为新的当前解。接受新解后，算法按一定方式更新禁忌表。同时，当翻转禁忌表中的某个变量能产生比当前最优解更优的解时，则接受禁忌表中的此候选解。按照以上规则迭代合适的步长后，禁忌搜索过程终止。

对于任意一个解x ，它的邻居解的目标函数值不必根据式(1)重新计算，本文使用文献[8]中的流线型更新策略。该策略使用一个长度为n 的数组记录当前解x 的所有邻居解与目标函数值的差值，将该内存称为Delta 表。它的初始化根据式(2)计算。当翻转了某个变量x i 后，依据式(3)更新Delta 表。

∆i =(1−2x i )(q ii +∑q (i , j )) (2)

j ∈N , j ≠i , x j =1

其中，i ∈{1,2, ⋯, n }。

−∆j j =∆=

i j ∆j +q (i , j ) j ≠i 且x j ≠x i (3)

∆j

−q (i , j ) j ≠i 且x j =x

i 其中，j ∈{1,2, ⋯, n }。

令q ij =q ij +q ji (i >j ) 且q ji =0，将对角矩阵Q 转化为下三角阵。q (i , j ) 表示q ij 或q ji 。若i >j ，q (i , j ) =q ij ；若i

q (i , j ) =q ji 。

当禁忌某个变量x i 时，设置禁忌表位置i 处的值为iter + tt ，其中，iter 是当前禁忌搜索的迭代步长；tt 是禁忌长度。判断某个变量是否被禁忌，只需要比较此时的迭代步长iter 与该变量在禁忌表中对应的值，若是小于等于关系，则该变量处于禁忌状态；否则，变量未被禁忌。通过大量的实验得出，依照式(4)设置禁忌长度tt 是合适的，其中，n 是算例中变量个数；rand (10)随机返回集合{1,2,…,10}的一个整数。

tt =n /150+rand (10) (4) 3.3 贪心跳坑策略

禁忌搜索算法是求解BQP 问题的高效算法，但是很可能会陷入局部最优值的陷阱。本文提出了一种贪心跳坑策略，以进一步提高算法的效率。跳坑策略的思想是：如果翻转局部最优解中的某些变量会使得到的邻域解的目标函数值与局部最优解的差值较小，那么这些变量应该被优先翻转。原因在于当禁忌搜索陷入局部最优值陷阱时，它的邻域解不可能优于该局部最优解。邻域解的目标函数值较大意味着翻转该局部最优解的相关变量对目标函数值损伤较小。根据贪心思想，跳坑时应该优先翻转这些变量。

3.4 算法描述

有了禁忌搜索和跳坑策略，本文算法可以描述如下： (1)随机化初始解x =(x 1, x 2, …, x n ) ，其中，x i ∈{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)若∆x i >∆x j 并且f (x )+∆x i >f (x*) ，k=i；否则，k=j。

(6)赋值x k =1–xk ，

得到新解x=(x 1, x 2,…, x k ,…, x n ) ，f (x )=f (x )+ ∆x k ，更新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 (n 2) 。

4 实验结果与分析

本文提出的ITS 算法用C 语言编程实现，并对OR-library

中的3组(beas500、beas1000、beas2500) 共30个最大算例在Intel(R) Xeon(R) E5440 (2 GB RAM/2.83 GHz CPU)微机上进行了计算测试。考虑到算法有随机因素，每个测试算例被计算30次。表1~表3分别给出了ITS 算法的实验结果以及和禁忌搜索TS 、模拟退火算法(SA-KN)[3]、混合算法(MA-MF)[3]的比较结果。

表1 ITS 算法的计算结果

算例 f prev f best g best g avr succ t best t avr b500.1 116 586 116 586 0 0.0 30/30 0.00 0.04 b500.2 128 339 128 339 0 0.0 30/30 0.00 0.07 b500.3 130 812 130 812 0 0.0 30/30 0.00 0.01 b500.4 130 097 130 097 0 0.0 30/30 0.01 0.09 b500.5 125 487 125 487 0 0.0 30/30 0.00 0.02 b500.6 121 772 121 772 0 0.0 30/30 0.01 0.11 b500.7 122 201 122 201 0 0.0 30/30 0.03 0.56 b500.8 123 559 123 559 0 0.0 30/30 0.00 0.30 b500.9 120 798 120 798 0 0.0 30/30 0.00 0.06 b500.10 130 619 130 619 0 0.0 30/30 0.00 0.02 b1000.1 371 438 371 438 0 0.0 30/30 0.03 0.29 b1000.2 354 932 354 932 0 0.0 30/30 0.06 0.95 b1000.3 371 236 371 236 0 0.0 30/30 0.03 0.51 b1000.4 370 675 370 675 0 0.0 30/30 0.08 0.37 b1000.5 352 760 352 760 0 0.0 30/30 0.05 0.84 b1000.6 359 629 359 629 0 0.0 30/30 0.07 0.76 b1000.7 371 193 371 193 0 0.0 30/30 0.06 0.59 b1000.8 351 994 351 994 0 0.0 30/30 0.29 1.98 b1000.9 349 337 349337 0 0.0 30/30 0.15 4.09 b1000.10 351 415

351 415

0 0.0 30/30 0.05 0.96 均值

0.0

30/30

0.046

0.631

表1给出了ITS 算法在beas500、beas1000这2组总共20个算例上的计算结果。其中，f prev 是文献[6]中统计的最优目标函数值，也是所有文献中报告的最好记录。f best 是ITS

142 计 算 机 工 程 2012年1月5日 1 s内得到所有20个算例的最优目标函数值f prev ，且在30次算法得到的最好目标函数值，g best 是f prev 与f best 的差值，g avr

是30次计算的平均值与f prev 的差值，succ 是在30次计算中实验中成功率达到百分之百。此外，在20个算例上达到最优达到f prev 的次数(成功率) ，t best 和t avr 分别统计算到f best 的最解的平均最短时间仅为0.046 s。这些充分说明了ITS 算法的好时间以及平均时间。从表1可以看出，ITS 算法能够在 快速性和稳定性。

表2 2种算法对beas2500的比较结果

算例 b2500.1 b2500.2 b2500.3 b2500.4 b2500.5 b2500.6 b2500.7 b2500.8 b2500.9 b2500.10

f prev

f avr

1 515 944 1 471 392 1 414 192 1 507 701 1 491 816 1 469 162 1 479 040 1 484 199 1 482 413 1 483 355

1 515 944 1 471 258 1 414 192 1 507 701 1 491 816 1 469 162 1 479 040 1 484 199 1 482 413 1 483 355

n 30 13 30 30 30 30 27 30 30 29

本文算法

t 1 6.6 49.1 32.9 2.9 7.3

18.4

47.1 15.3 20.1 49.5

t 2 – 120 – – – – 120 – – 120

f avr 1 515 127 1 470 824 1 413 766 1 507 701 1 491 770 1 469 023 1 478 649 1 484 161 1 482 206 1 482 986

禁忌算法 n 20 3 10 30 26 23 18 11 12 11

t 1 7.5 94.3 9.8 8.6 9.8 15.3 29.1 12.2 25.1 60.2

t 2 120 120 120 – 120 120 120 120 120 120

为了验证ITS 算法对更大更难的算例依然有效，表2给5 结束语

本文提出的迭代禁忌算法对OR-library 中所有的大算例出了ITS 在beas2500这组算例上的实算结果。同时给出了禁

都达到了最优解，其计算效率也要高于禁忌搜索，模拟退火忌搜索(TS)的比较数据，验证跳坑策略的有效性。其中，f prev

算法和混合算法。同时，提出的贪心跳坑策略在提高算法效是文献[6]中报告的最好解值；f avr 是30次计算的平均值；n

率上的作用非常显著。此外，扰动强度也是影响ITS 算法的表示30次中算到f prev 的次数；t 1是算到f prev 的平均时间；t 2

一个关键参数。 给出了所有计算中没有全部算到f prev 的时间。为了使这2个

总之，ITS 算法中的禁忌搜索具有局部寻优的特点，而算法可比较，ITS 和TS 的停机条件都设为120 s。可以看出，

跳坑策略在算法陷入僵局的情况下跳出陷阱，同时保持着原ITS 和TS 这2个算法在给定的时间内都能算到已知的最好结

果。但是，ITS 在解的优度、成功率上要明显优于TS 。在 有局部最优解的信息以引导算法走向更有希望的区域。两者

结合有效地提高了算法的计算效率。 10个算例上，ITS 能够在7个算例上达到30次实验中均算到最优值，而TS 只能在1个算例上达到这样的结果。在另外

3个算例上，ITS 的成功率和解的优度也要远高于TS 。以上结果说明了ITS 算法以及提出的贪心跳坑策略都非常高效。

表3 4种算法在种算法在beas2500算例上的平均值算例上的平均值比较结果平均值比较结果

算例 b2500.1 b2500.2 b2500.3 b2500.4 b2500.5 b2500.6 b2500.7 b2500.8 b2500.9 b2500.10

本文算法 1 414 192 1 507 701 1 491 816 1 483 343

禁忌搜索算法 模拟退火算法 1 515 127 1 470 824 1 413 766 1 507 701 1 491 770 1 469 023 1 478 649 1 484 161 1 482 206 1 482 986

1 515 828.9 1 470 600.9 1 413 657.1 1 507 630.3 1 491 692.8 1 468 810.3 1 478 397.4 1 483 907.9 1 482 192.0 1 482 522.4

混合算法 1 514 804.6 1 469 721.0 1 412 943.0 1 507 674.2 1 491 623.4 1 467 918.2 1 477 101.7 1 483 226.9 1 481 622.9 1 481 899.2

[3]

参考文献

[1] Kochenberger G A, Glover F, Alidaee B, et al. An Unified

Modeling and Solution Framework for Combinatorial Optimi- zation Problems[J]. OR Spectrum, 2004, 26(2): 229-241

[2] 廖飞雄, 马 良. 图着色问题的启发式搜索蚂蚁算法[J]. 计算

机工程, 2007, 33(16): 191-192, 195.

[3] Merz P, Katayama K. Memetic Algorithms for the Unconstrained

Binary Quadratic Programming Problem[J]. BioSystems, 2004, 78(1-3): 99-118.

[4] Lodi A, Allemand K, Liebling T M. An Evolutionary Heuristic for

Quadratic 0-1 Programming[J]. European Journal of Operational Research, 1999, 119(3): 662-670.

[5] Beasley J E. Heuristic Algorithms for the Unconstrained Binary

Quadratic Programming Problem[D]. London, UK: Imperial College, 1998.

[6] Endre B, Hammer P L, Gabriel T. Local Search Heuristics for

表3给出了ITS 与禁忌搜索(TS)、模拟退火算法Quadratic Unconstrained Binary Optimization[J]. Journal of

[3]

(SA-KN)和混合算法(MA-MF)在30次实验中在最优目标函Heuristics, 2007, 13(2): 99-132. 数值的平均值这一指标上的比较结果，这几个比较算法都是[7] Glover F, Laguna M. Tabu Search[M]. Boston, USA: Kluwer 目前较为先进的算法。下划线表示在该算例上，得到该结果Academic Publishers, 1997. 的算法优于另外3个算法。可以看出，对于所有这10个最难[8] Glover F, Hao Junkao. Efficient Evaluations for Solving Large 0-1

Unconstrained Quadratic Optimization Problems[J]. International 的算例，ITS 解的优度都好于TS 、SA-KN 和MA-MF 这3个

Journal of Metaheuristics, 2010, 1(1): 3-10. 算法。此外，TS 解的优度也要好于SA-KN 和MA-MF 这

编辑 顾逸斐2个著名算法，说明了本文设计的禁忌搜索性能也很高效。