全 文 ：　　收稿日期 : 2001211201
基金项目 : 本研究得到德意志学术交流中心 (DAAD)资助
作者简介 : 陈伯望 (1965 —) ,男 ,福建古田人 ,副研究员.
　　文章编号 : 100121498 (2003) 0026206
Tabu 搜索法在森林采伐量优化问题中的应用
陈伯望1 , 惠刚盈1 , Klaus von Gadow2
(11 中国林业科学研究院林业研究所 ,北京　100091 ; 21 德国哥廷根大学森林
资源经营研究所 ,德国 哥廷根　37075)
摘要 : 介绍了一种新颖高效的启迪式搜索方式 ———Tabu 搜索法。以一个杉木人工林采伐量方案的优
化为例 ,介绍了 Tabu 搜索法的基本原理和应用方法 ,并把 Tabu 搜索法与线性规划、模拟退火和遗传
算法处理同一森林采伐量优化方案例子获得的结果进行了比较。结果表明 ,禁忌搜索法在解决一般
森林采伐量优化问题时有快速高效的特点 ,尤其是在移动产生的相邻解数目有限且差异较大的情况
下 ,可以很快获得模拟退火和遗传算法多次重复计算也较难达到的高目标方程值。禁忌周期对 Tabu
搜索法的影响比较小 ,寻找好的移动方式和排序方式是影响 Tabu 搜索法效率的关键。
关键词 : Tabu 搜索法 ;线性规划 ;模拟退火 ;遗传算法 ;杉木林 ;采伐量优化问题
中图分类号 : S75317 　　　　　文献标识码 :A
Tabu 搜索法 (Tabu search ,TS) 是最近 10 年左右发展起来的解决优化组合问题决策的方
法[1 ,2 ] 。Tabu (或 Taboo)一词的含义是“禁忌”,具体来说就是在搜索过程中一部分组合方案在
一定的期限内暂时不可用。为了避免陷入局部最优解 ,禁忌搜索法记住搜索过程走过的最近
若干步骤 ,这样就强迫去搜寻其他区域 ,因而增加了获得更好的解决方案的机会。最近几年 ,
Tabu 搜索法开始在林业方面得到应用 ,尤其是在森林采伐量优化方案方面 ,取得令人满意的
结果[3 　9 ] 。本文通过杉木人工林森林采伐量的优化问题的解决 ,来介绍 Tabu 搜索法的基本应
用方法。把获得的结果与模拟退火和遗传算法的结果进行比较 ,提出了 Tabu 搜索法应用于森
林采伐量优化方案方面的建议。
1 　Tabu 搜索法的基本原理和方法
Tabu 搜索法和模拟退火法 (Simulated annealing ,SA) 一样 ,都是蒙特卡罗方法 (Monte Carlo
Method)的具体变种方法 ,即都是属于邻域搜索法 (Neighborhood search method) [10 ] 。
设若有最大化问题目标函数 f ( x) ,满足约束条件 gi ( x) Ε bi ( i = 1 , . . . , m) 和 hi ( x) = cj ( j
= 1 , . . . n) ,其中 x 是决策变量矢量 , f ( x) 、g ( x) 和 h ( x) 是一般函数。如果 X 是本问题的一
个当前的解决方案 ,那么 N ( X ,σ) 就是 X 的一组相邻解的集合 ,这些相邻解都可以由 X 通过
一次简单的操作σ而获得。对于 Tabu 搜索法和模拟退火法 ,这个简单的操作σ可以称为移
动。
如果把邻域搜索法比喻成攀登一座有多个小山头的山脉时 ,那么山脉的任何一个地点都
林业科学研究　2003 ,16 (1) :26 　31
Forest Research
是一个解 ,主峰的顶点坐标就是全局最优解 ,其高程是目标方程值 ,相应地 ,每个小山头都是一
个局部最优解。邻域搜索过程就是每次在当前点上只考虑周围一步范围内的各个点 (相邻解)
的高程 ,通过比较决定下一步的前进点 :向更高的方向移动一步。整个优化过程从一个随机选
定的起点开始移动 ,重复这个过程 ,直到获得全局性 (或接近的)最优解。如果在一步范围内没
有更高的点可以移动 ,当前点之外的 (可能劣于当前点的)最高点将被采纳。
模拟退火法的迭代特点是在每个当前方案的邻域方案中随机选择一个比较好的方案作为
搜索前进的下一步。模拟退火法要避免陷入局部最优的陷阱所采用的方法是 :不排除在一定
条件下接受比当前方案更差的方案 ,目的是放弃局部最优。具体来说 ,目标方程值高的方案具
有较高的接受概率 ,而目标方程值低的方案具有较低的接受概率。而 Tabu 搜索法的迭代特点
是对当前方案的所有邻域方案进行排序比较 ,从中选择目标方程值最优的方案作为下一步的
搜索基础。很明显 ,这样的方法向上前进的速度很快 ,但也很容易陷入局部最优并使搜索过程
结束。
　　表 1 　林区中 1480 个林分中的前 10 个林分的基本情况
林分
编号
面积/
hm2
立地指数/
m
年龄/
a
密度/
(株·hm - 2)
胸高断面积/
(m2·hm - 2)
1 1012 14 6 3333 6129
2 2510 16 8 2 500 15138
3 513 18 12 1 667 30117
4 1316 16 15 2 420 34150
5 1218 20 18 2 330 48170
6 815 16 13 2 410 31151
7 411 18 9 1 670 20113
8 715 18 7 1 666 13112
9 412 16 11 2 450 25180
10 1810 20 14 1 650 39182
为了避免陷入局部最优的陷阱 ,给 Tabu 搜索法设定一个禁忌周期 ,这是一个正整数。凡
是在最近若干次走过的搜索移动都被设置一个禁忌周期 ,在后面的若干次移动中不再被采纳 ,
每次移动时都把各个其它移动的禁忌周期值减 1 ,直至各移动的禁忌周期结束。一个例外情
况是 ,如果禁忌周期内的移动能够使目标方程值超过历史上的最高值 ,那么这个移动将被采
纳 ,这样做的目的是增加优化的效率。当一个移动的禁忌周期递减为零时 ,它又可以作为候选
移动参加评选了。Tabu 搜索法的流程图见图 1。
遗传算法的原理与模拟退火法和 Tabu 搜索法的原理不同 ,它属于一种仿生学的算法 ,方
法详见文献[11 ]。
2 　例子 :森林采伐量优化问题
模拟林区的总面积为 9 81513 hm2 ,有 1 480 个杉木人工林中幼龄林分 ,已知各林分面积、立地
指数、年龄、优势高和密度等基本条件 ,年龄为 5 　18 a ,立地指数 14 　20 ,表 1 为前 10 个林分的
基本情况 (限于篇幅未能全部列出) 。每个林分各有 5 类可能的经营措施 :A1 无任何措施 ,计划
期内无木材产出 ;B1 无间伐 ,在特定的年龄主伐 ;C11 次间伐 (特定年龄、特定强度) ,在特定的年
龄主伐 ;D12 次间伐 (特定年龄、特定强度) ,在特定的年龄主伐 ; E13 次间伐 (特定年龄、特定强
度) ,在特定的年龄主伐。
计划周期为 10 a ,主伐年龄为 20
a ,并假设如果在计划期内达到主伐
年龄则进行主伐 ,次年春天以同质量
苗木 3 000 株·hm - 2的造林密度更
新。要求在计划期结束时各年采伐
量 (包括间伐和主伐) 与当时林分立
木蓄积量 (包括更新的) 的总和达到
最大 ,同时约束条件要求每年的采伐
量 (包括间伐和主伐) 不少于 10 000
m
3。生长量的估算采用惠刚盈[12 ]的
72第 1 期 陈伯望等 :Tabu 搜索法在森林采伐量优化问题中的应用
图 1 　Tabu 搜索法的流程图
方法。本问题的可能解有 51 480 个 ,采用通常的方法难以解决 ,虽然可以用线性规划来求算
1 480 ×5 = 7 400个变量的问题 ,但是恰好得到的整数解的可能性极小。
Tabu 搜索法应用于森林采伐量优化中的优化问题时 ,需要解决的是对移动的定义和理
解。一开始可以为各个林分随机选择 5 个可能措施中的一个 ,作为起始的方案。对于一个特
定的方案 ,可以把移动定义成对当前方案的一个最小的改动 ,比如对1 480个林分的其中一个
林分的措施进行变化 ,改为另外 4 个措施的 1 个 ,而其它所有1 479个林分的措施保持不变 ,这
个改动就是一个移动 ,新产生的方案就是原方案的一个相邻解。
显然 ,任何一个方案都有1 480 ×(5 - 1) = 5 920个相邻解 ,模拟退火法就是在每次迭代时
82　 林 　业 　科 　学 　研 　究 第 16 卷
随机选取一个比较好的相邻解作为入选者 ,而 Tabu 搜索法是选取最好的 (通常不在禁忌周期
内)相邻解作为入选者。
与模拟退火法相比 ,Tabu 搜索法的参数数量少 ,需要调节的除了迭代次数外 ,就是禁忌周
期。为了比较 Tabu 搜索法与其它启迪优化方法的搜索质量 ,以线性规划解得的目标方程值作
为标准来比较各种方法以及不同参数配置的求解效率 :
E =
VX
VL P
×100 %
　　这里 E 是相对效率 , VL P是线性规划求得的目标方程值 , VX 是其它方法求得的目标方程
值。因为线性规划允许把同一林分按面积分割成采用不同经营措施的几个部分 ,其获得的目
标方程值可以作为评判整数组合问题效率的上界。
把迭代次数设置得足够长 ,使各种优化方法都有足够的收敛时间 ,使它们的目标方程值尽量
趋近线性规划解得的目标方程值。不同禁忌周期的 Tabu 搜索法获得目标方程值、耗费的时间以
及与其方法中参数设置效果较好的几个例子 (表 2) ,并计算各例的相对于线性规划的效率。
表 2 　不同禁忌周期的 Tabu搜索法结果与线性规划、遗传算法和模拟退火结果的比较
Tabu
搜索法
禁忌周期/
次
最大迭代次数/
次
目标方程值
×0101 耗时/(h. min. s) 相对效率/%
TS1 10 500 33 79911 0129130 9914
TS2 20 500 33 79311 0129107 9914
TS3 30 500 33 81416 0128139 9915
TS4 40 500 33 81615 0129152 9915
TS5 50 500 33 78613 0129110 9914
TS6 100 500 33 77215 0129120 9913
TS7 200 500 33 83018 0128120 9915
TS8 300 500 33 77312 0130134 9913
TS9 400 500 33 79814 0130103 9914
TS10 500 500 33 78511 0129139 9914
TS11 1 000 500 33 78212 0130145 9914
TS12 2 000 500 33 78216 0129114 9914
TS13 3 000 500 33 83012 0129144 9915
TS14 4 000 500 33 77914 0130132 9914
TS15 5 000 500 33 78912 0129159 9914
遗传
算法
群体大
小/ 个
交换率/
%
突变率/
% 繁殖代数/ 代
目标方程值
×0101 耗时/(h. min. s) 相对效率/%
GA4 10 015 015 5 000 33 73210 0139156 9912
GA5 10 011 019 5 000 33 74812 0127123 9913
GA6 10 019 019 5 000 33 72613 0150141 9912
GA9 20 011 019 5 000 33 75211 0141109 9913
GA17 50 011 011 10 000 33 75213 1127138 9913
模拟
退火
初始温
度/ ℃
波尔兹曼
常数 k
外循环
次数/ 次
内循环
次数/ 次
目标方程值
×0101 耗时/ (h. min. s) 相对效率/ %
SA 100 019 50 2 000 33 73616 2100117 9912
LP 线性规划 33 99816 14152133 10010
　　注 :计算环境是 pentium Ⅲ2500/ 128M/ 12G/ MS2Windows 98 SE/ Visual Basic 610
在表 2 中 ,Tabu 搜索法对于不同的禁忌周期反应不明显 ,大约在 015 h 都收敛到相当于线
92第 1 期 陈伯望等 :Tabu 搜索法在森林采伐量优化问题中的应用
性规划目标方程值 9914 %左右的程度。遗传算法和模拟退火的效果受到本身参数设置的影
响比较大 ,表 2 列出的算例只是效率比较好、耗时比较短的部分 ,即使如此 ,两者的效率和耗时
表现综合起来都要比 Tabu 搜索法的所有算例稍差一点。线性规划耗时约 15 h 获得非整数解 ,
如第 36 号林分的面积是 1510 hm2 ,被分割为 8132 hm2 (采用 A 措施) 、6168 hm2 (采用 B 措施) 。
表 3 列出了这些不同参数的优化方法对前 10 个林分提出的具体经营措施。
表 3 　不同优化方法对前 10 个林分的具体措施
方法
林　　分
1 2 3 4 5 6 7 8 9 10
方法
林　　分
1 2 3 4 5 6 7 8 9 10
TS1 A D E D A C A C C A TS12 D D C C A C C C C A
TS2 D D A D A C C C C A TS13 D D D D A C A C C A
TS3 C D D D A C A C E A TS14 E D A D A C A C C A
TS4 A D C E A C A C D A TS15 A D E E A C A C C A
TS5 A D D D A E A C C A GA4 E D C D A C A C E A
TS6 D D C C A C C C C A GA5 A D C D C D A C A A
TS7 C D D D A C A C C A GA6 D D A C A E C C C C
TS8 D D C C A C C C C A GA9 C D D C A C A C C A
TS9 C D C E A E A C C A GA17 E D C E A C A C C A
TS10 E D A D A C A C C A SA A D C D A E D C C A
TS11 A D E E A C A C C A LP B B A A A A B B D A
　　注 :A1 无任何措施 ,计划期内无木材产出 ;B1 无间伐 ,在特定的年龄主伐 ;C11 次间伐 (特定年龄、特定强度) ,在特定的
年龄主伐 ;D12 次间伐 (特定年龄、特定强度) ,在特定的年龄主伐 ; E13 次间伐 (特定年龄、特定强度) ,在特定的年龄主伐。
3 　讨论与结论
Tabu 搜索法的参数数量比模拟退火和遗传算法都少 ,除了迭代次数外就是禁忌周期了 ,
而禁忌周期对 Tabu 搜索法结果的影响一般很小 ,在本文的两个例子中不同禁忌周期对 Tabu
搜索法的过程和结果影响都不太大。通常禁忌周期大有利于强迫 Tabu 搜索法有更多的机会
去搜寻未搜寻过的空间 ,这有利于获得 (接近)全局最优解。如果禁忌周期设置过大 ,比如接近
整个相邻解的数目时 ,在迭代一定次数之后 ,由于大量移动尚未解放出来 ,可以采用的移动数
目越来越少时 ,Tabu 搜索法将被迫暂时接受比较差甚至很差的解 ,而一旦有一部分移动的禁
忌周期结束时 ,Tabu 搜索法很快又会找到目标方程值较高的解。在极端的情形下 ,如果禁忌
周期超过了整个相邻解的数目时 ,Tabu 搜索法将在一定迭代次数后被迫中断 ,因为这时所有
的移动都处在禁忌周期内。
一般来说 ,如果有比较好的移动方法 ,即能够产生数目有限而又具有与当前有很大差异的
相邻解的集合 ,那么 Tabu 搜索法应该优于模拟退火和遗传算法 ,其主要优点是收敛速度快 ,获
得的目标方程值高。
如果移动的方式所产生相邻解的目标方程值差异都不大 ,Tabu 搜索法的收敛速度必然受
到影响 ,同时 ,如果移动的方式所产生相邻解数目太多 ,也会给 Tabu 搜索法带来沉重的排序负
担 ,这时 Tabu 搜索法的效果可能不如模拟退火或遗传算法的好。
对于这个问题 ,应该是有改进空间的 ,一是找到比较好的移动方式 ,这是决定 Tabu 搜索法
效率的主要因素 ;二是改进排序方法 (本文采用的是最简单的排序方法 ,未作改进) ;三是充分
利用邻域搜索法每次只修改当前解一小部分的特点 ,不必每次迭代都完全重新计算每个目标
03　 林 　业 　科 　学 　研 　究 第 16 卷
方程值和排序 ,而是修改部分起变化的地方 ,这个方法可以节省大量的计算和排序时间并在本
文的模拟退火计算中得到很好的应用。
参考文献 :
[1 ] Glover F. Tabu search2Part I. ORSA J [J ] . Computer ,1989 ,1∶190 　206
[2 ] Glover F , Laguna M. Tabu search[ A] . In ∶Reeves C R. Modern heuristic techniques for combinatorial problems[ C] . Wiley , New
York : Blackwell scientific publications , 1993. 70 　150
[3 ] Bettinger P , Sessions J , Boston K. Using Tabu search to schedule timber harvests subject to spatial wildlife goals for big game[J ] . Eco2
logical Modelling , 1997 ,94∶111 　123
[4 ] Bettinger P , Johnson K, Sessions J . Improving aquatic habitat conditions over time while producing wood products : an examination of
options[J ] . Journal of the American Water Resources Association , 1998 ,34 (4)∶891 　907
[5 ] Bettinger P , Sessions J , Johnson K. Ensuring the compatibility of aquatic habitat and commodity production goals in eastern Oregon with
a Tabu search procedure[J ] . Forest Science. 1998 ,44 (1)∶96 　112
[6 ] Boston K, Bettinger P. An analysis of Monte Carlo integer programming , simulated annealing , and tabu search heuristics for solving spa2
tial harvest scheduling problems[J ] . Forest Science ,1999 ,45 (2)∶292 　301
[7 ] Laroze A J , Greber B J . Using Tabu Search to generate stand2level ,Rule2based bucking patterns[J ] . Forest Science ,1997 ,43 (2)∶157
　169
[8 ] Laroze A. Linear programming , Tabu search method for solving forest2level bucking optimization problems[J ] . Forest Science ,1999 ,45
(1)∶108 　116
[9 ] Murphy G. Allocation of stands and cutting patterns to logging crews using a tabu search heuristic [J ] . Journal of Forest Engineering ,
1998 ,9 (1)∶31 　37
[10 ] Reeves C R. Modern heuristic techniques for combinatorial [M] . Oxford : Blackwell , 1993. 735
[11 ] Holland ,John H. Adaptation in Natural and Artificial Systems[M] . Ann Arbor : University of Michigan Press ,1975
[12 ] Hui G Y. Wuchsmodelle für die Baumart Cunninghamia lanceolata[D] . GÊttingen : Cuvillier Verlag GÊttingen ,1997
Tabu Search and Its Application in Sustainable Forest Management
CHEN Bo2wang1 , HUI Gang2ying1 , Klaus von Gadow2
(1. Research Institute Forestry ,CAF ,Beijing 　100091 , China ; 2. Institute of Forest Resource Management ,
Georg2August2University ,GÊttingen 　37075 , Germany)
Abstract :The principle and methods of a new and high efficient heuristic method , Tabu search (TS) ,is
introduced in this paper with a optimization example of forest harvesting problem of Chinese fir. The re2
sults of Tabu search are compared with those of linear programming(LP) , simulated annealing (SA) and
genetic algorithm ( GA) . It is indicated that Tabu search is of high efficiency in resolving general forest
harvesting problems , especially when the number of neighbourhood generated by move is limited and the
variation among them is great . Its objective function values are higher than those of simulated annealing
and genetic algorithm from multiple running. Tabu tenure has no significant influence on Tabu search ef2
ficiency while a good move method and sort method are essential to Tabu search.
Keywords :Tabu seach ; linear programming ; simulated annealing ; genetic algorithm ; Cunninghamia
lanceolata ; forest harvesting problem
13第 1 期 陈伯望等 :Tabu 搜索法在森林采伐量优化问题中的应用