禁忌搜索算法缺点
‘壹’ 地下水管理模型求解方法研究进展
在通常情况下，无论是地下水系统的状态方程，还是管理模型的目标函数或约束条件，圴常具有非线性、多峰性、不连续等特征，这给求解管理模型带来了困难；而传统的优化方法首先要将非线性问题进行线性近似，使得其解强烈依赖于管理模型目标函数的初值和梯度［52］。当目标函数不连续或不可导时，尤其是在分布参数地下水管理模型中涉及经济或环境因素，会使模型更为庞大而复杂，以致传统的优化方法无法解决［53］。
近年来，最优化技术有了很大的进展，一些基于试探式具有全局寻优特点的求解方法被应用于地下水管理之中，如遗传算法、模拟退火算法、人工神经网络算法、禁忌搜索算法以及一些混合智能算法等。
1.2.3.1 遗传算法（Genetic Algorithm，GA）
遗传算法是20世纪70年代初期由Holland等人创立，并由Goldberg发展完善起来的一种新型寻优方法［54］。遗传算法求解地下水管理模型时，不要求地下水系统必须是线性的，因而更适合求解复杂地下水系统的管理问题。目前，国内外已将遗传算法应用到地下水管理的各个领域。
McKinney等［55］用遗传算法求解了3个地下水管理问题：含水层最大抽水量，最低抽水费用及含水层修复的最低费用；Katsifarakis等［56，57］结合边界元法和遗传算法求三类经常遇到的地下水流和溶质运移问题的最优解，即确定导水系数、最小化抽水费用及污染羽的水动力控制；Morshed等［58］综述了遗传算法在地下水管理方面的应用，并提出了一些改进方法；Cai等［59］将遗传算法和线性规划相结合，求解大型非线性水资源管理模型，先用遗传算法识别出复杂的变量，这些变量不变时，问题趋于线性化，然后用线性规划分段求解水资源管理模型；Zheng等［60］采用遗传算法求解由响应矩阵法建立的地下水修复系统优化设计模型；Ines等［61］结合遥感和遗传算法对灌区的水管理进行优化。近年来，国内学者邵景力等［62］以山东省羊庄盆地地下水非线性管理模型为例，介绍了应用遗传算法求解这类问题的具体步骤；崔亚莉等［63］以山东省羊庄盆地3个水源地总抽水量最大为目标建立了地下水管理模型，采用遗传算法进行求解。
需要指出的是，遗传算法是一种近似算法和全局优化算法，其收敛速度和解的精度受控于该算法的某些参数选取；对于大规模、多变量的地下水管理问题，其收敛速度较慢，计算时间长，这是遗传算法在求解复杂地下水管理模型的不足之处。
1.2.3.2 模拟退火算法（Simulated Annealing Algorithm，SAA）
模拟退火算法是局部搜索算法的扩展，它不同于局部搜索算法之处是以一定的概率选择邻域中目标函数值好的状态。理论上来说，它是一个全局优化算法，它通过模拟金属物质退火过程与优化问题求解过程的相似性，另辟了求解优化问题新途径［64］。模拟退火算法已被应用到地下水管理领域。
Wang等［65］分别用遗传算法和模拟退火算法求解了地下水管理模型，并通过与线性规划、非线性规划和微分动态规划方法的计算结果相对比，评价了两种算法的优缺点。Dougherty等［66］介绍了模拟退火算法在地下水管理中的应用。Rizzo等［67］用模拟退火算法求解了多时段地下水修复的管理问题，并应用了一个价值函数以加速算法搜索速度。Cunha［68］用模拟退火算法求解了地下水管理问题，使在满足需求的条件下选择供水设备，使总安装费用和经营费用最低。Kuo等［69］提出了基于田间灌水制度和模拟退火算法的模型进行农业水资源管理。Rao等［70，71］运用SEAWAT建立了地下水流和溶质运移模型，并采用模拟退火算法求解地下水管理问题。
模拟退火算法的实验性能具有质量高、初值鲁棒性强、通用易实现的优点，但为寻到最优解，模拟退火算法往往优化时间比较长，这也是此算法最大的缺点［72］。
1.2.3.3 人工神经网络算法（Artificial Neural Network，ANN）
人工神经网络算法是一门新兴的学科，从20世纪40年代提出基本概念以来得到了迅速的发展。人工神经网络法属于集中参数模型，是模拟人脑工作模式的一种智能仿生模型，可以对信息进行大规模并行处理；具有自组织、自适应和自学习能力，以及具有非线性、非局域性等特点；而且善于联想、概括、类比和推理，能够从大量的统计资料中分析提炼实用的统计规律［73］。
在地下水管理中，由于含水层性质的空间变异性所导致的数据多变性和参数的不确定性以及水文地质数据的不完备性，使得一些精确分析方法在表达地下水资源系统各部分之间的非线性关系上具有很大的局限性。ANN技术的引入，对地下水管理模型的应用研究有着很大的促进作用。1992年，Rogers在博士论文中首先提出利用人工神经网络技术进行地下水优化管理，并在模型训练与识别中使用了遗传算法。此后，陆续有些学者在这一领域进行了大量研究。Ranjithan等［74］用人工神经网络模型对渗透系数不确定性条件下的地下水回灌方案进行优化研究；Coppola等［75］成功地把人工神经网络运用到3种地下水预测问题中，求解复杂地下水管理问题；Parida等［76］用人工神经网络预测水资源管理中的径流系数。
需要强调的是，ANN模型并不是对非线性过程的真实描述，不能反映系统的真实结构，因而不能最终完全替代系统的机理模型。ANN模型的这一本质是在建立各类地下水非线性系统管理模型时都必须首先考虑的。目前我国在地下水资源管理研究中对ANN技术的应用和研究还比较少，特别是在地下水资源管理中ANN技术的综合应用方面，与国外相比，还有一定的差距。
1.2.3.4 禁忌搜索算法（Tabu Search Algorithm，TSA）
禁忌搜索算法的逐步寻优思想最早由Glover［77］提出，它是对局部邻域搜索的一种扩展，是一种全局算法，是对人类智力过程的一种模拟。禁忌搜索算法通过引入一个灵活的存储结构和相应的禁忌准则来避免迂回搜索，并通过藐视准则来赦免一些被禁忌的优良状态，进而保证多样化的有效探索以最终实现全局优化。
Zheng等［78］联合禁忌搜索算法和线性规划方法求解了地下水污染的修复设计问题，主要应用了禁忌搜索的优点（在优化离散井位时更有效）和线性规划的优点（在优化连续抽水量时更有效）；Zheng等［79］分别用禁忌搜索算法和模拟退火算法进行最优参数结构识别，并评价和比较了两种方法的有效性和灵活性；Lee等［80］给出了八种求解非线性整数规划问题的启发式算法的经验比较，在监测网设计中的应用结果表明，模拟退火算法和禁忌搜索算法表现比较突出；杨蕴和吴剑锋等［81］将禁忌搜索算法和遗传算法分别应用于求解地下水管理模型，其结果表明禁忌搜索计算效率高于遗传算法。
禁忌搜索算法对初始解有较强的依赖性，好的初始解可使禁忌搜索在解空间搜索到好的解，而较差的初始解则会降低禁忌搜索的收敛速度。禁忌搜索能否在实际问题中应用好，要充分考虑初始解对优化结果的影响，这方面还有待于进一步的研究。此外，迭代搜索过程是串行的，仅是单一状态的移动，而非并行搜索，这就使得算法的优化时间往往较长，为了改善寻优效率，目前的趋势是把禁忌搜索与其他启发式方法结合起来，比如把禁忌搜索算法与遗传算法结合等［82，83］。
1.2.3.5 混合智能算法
模拟退火遗传算法（SAGA）是将遗传算法与模拟退火算法相融合而产生的一种优化算法。Sidiropoulos等［84］用模拟退火算法和遗传算法研究了以抽水费用最小为目标的地下水管理问题，最后提出了地下水管理模型更有效的解法——模拟退火遗传算法；Shieh等［85］应用模拟退火遗传算法进行了原位生物修复系统的最优化设计研究；韩万海等［86］用模拟退火遗传算法进行了石羊河流域的水资源优化配置研究；潘林［87］等应用模拟退火遗传算法对某灌区的灌溉水量进行了最优分配；吴剑锋等［88］运用遗传算法，同时用模拟退火罚函数方法处理约束条件，求解了地下水管理模型，并将该方法成功地应用于徐州市地下水资源评价与管理模型之中，取得了较为满意的结果。模拟退火遗传算法不但克服了基于梯度寻优算法的缺点，而且通过模拟退火过程，保证能够有效地求得问题在可行域上的最优解（或接近最优解）。然而在求解大型的多决策地下水优化管理问题时，如何减少群体规模，从而有效地提高遗传算法的寻优速度，还有待于进一步深入研究。
人工神经网络算法和遗传算法相结合来求解地下水管理模型的研究也很多。Rogers等［89］用人工神经网络算法和遗传算法进行最优地下水修复设计，用人工神经网络预测水流和溶质模拟结果；Aly等［90］提出了不确定条件下含水层净化系统最优设计的方法——人工神经网络算法和遗传算法；Brian［91］等将遗传算法与人工神经网络算法相结合求解了具有线性目标函数的含水层系统水质管理问题，并将该方法与基于梯度函数的传统算法进行了比较。
此外，其他一些混合算法也常应用于地下水管理问题中。Tung等［92］使用模式分类和禁忌搜索算法相结合的方法研究了地下水开采管理问题；Hsiao等［93］应用遗传算法与约束微分动态规划相结合的混合算法求解了非承压地下水含水层修复优化问题；Mantawy等［94］将遗传算法、禁忌搜索算法和模拟退火算法相结合求解单位运输问题，算法的核心是遗传算法，用禁忌搜索产生新种群，用模拟退火法加速收敛速度。
地下水管理模型求解的方法有很多，除文中提及的优化算法外，近年来快速发展的智能方法，如混沌优化算法、蚁群算法等都为解决这一问题提供了新的思路。地下水资源系统本身是一个高度复杂的非线性系统，其功能与作用是多方面、多层次的；模型的输入有确定的，也有随机的。因此，为实现地下水更科学有效的管理，地下水管理模型的求解方法也必须更具有准确性和实用性。
‘贰’ 禁忌搜索算法的简介
又名“tabu搜索算法”
为了找到“全局最优解”，就不应该执着于某一个特定的区域。局部搜索的缺点就是太贪婪地对某一个局部区域以及其邻域搜索，导致一叶障目，不见泰山。禁忌搜索就是对于找到的一部分局部最优解，有意识地避开它（但不是完全隔绝），从而获得更多的搜索区间。兔子们找到了泰山，它们之中的一只就会留守在这里，其他的再去别的地方寻找。就这样，一大圈后，把找到的几个山峰一比较，珠穆朗玛峰脱颖而出。
当兔子们再寻找的时候，一般地会有意识地避开泰山，因为他们知道，这里已经找过，并且有一只兔子在那里看着了。这就是禁忌搜索中“禁忌表（tabu list）”的含义。那只留在泰山的兔子一般不会就安家在那里了，它会在一定时间后重新回到找最高峰的大军，因为这个时候已经有了许多新的消息，泰山毕竟也有一个不错的高度，需要重新考虑，这个归队时间，在禁忌搜索里面叫做“禁忌长度（tabu length）”；如果在搜索的过程中，留守泰山的兔子还没有归队，但是找到的地方全是华北平原等比较低的地方，兔子们就不得不再次考虑选中泰山，也就是说，当一个有兔子留守的地方优越性太突出，超过了“best so far”的状态，就可以不顾及有没有兔子留守，都把这个地方考虑进来，这就叫“特赦准则（aspiration criterion）”。这三个概念是禁忌搜索和一般搜索准则最不同的地方，算法的优化也关键在这里。
‘叁’ 禁忌搜索算法与传统优化算法的区别
背景：禁忌搜索算法（Tabu Search）是由美国科罗拉多州大学的Fred Glover教授在1986年左右提出来的，是一个用来跳出局部最优的搜寻方法。在解决最优问题上，一般区分为两种方式：一种是传统的方法，另一种方法则是一些启发式搜索算法。
使用传统的方法，我们必须对每一个问题都去设计一套算法，相当不方便，缺乏广泛性，优点在于我们可以证明算法的正确性，我们可以保证找到的答案是最优的；而对于启发式算法，针对不同的问题，我们可以套用同一个架构来寻找答案，在这个过程中，我们只需要设计评价函数以及如何找到下一个可能解的函数等，所以启发式算法的广泛性比较高，但相对在准确度上就不一定能够达到最优，但是在实际问题中启发式算法那有着更广泛的应用
‘肆’ 禁忌搜索算法的其他算法
禁忌搜索是对人类思维过程本身的一种模拟，它通过对一些局部最优解的禁忌（也可以说是记忆）达到接纳一部分较差解，从而跳出局部搜索的目的.
遗传算法是基于生物进化的原理发展起来的一种广为应用的、高效的随机搜索与优化的方法。其主要特点是群体搜索策略和群体中个体之间的信息交换，搜索不依赖于梯度信息。
蚂蚁算法是群体智能可用于解决其他组合优化问题,比如有n个城市，需要对所有n个城市进行访问且只访问一次的最短距离。
‘伍’ 禁忌搜索算法的伪码表达
procere tabu search;
begin
initialize a string vc at random,clear up the tabu list;
cur:=vc;
repeat
select a new string vn in the neighborhood of vc;
if va>best_to_far then {va is a string in the tabu list}
begin
cur:=va;
let va take place of the oldest string in the tabu list;
best_to_far:=va;
end else
begin
cur:=vn;
let vn take place of the oldest string in the tabu list;
end;
until (termination-condition);
end;
以上程序中的关键在于： 禁忌对象：可以选取当前的值（cur）作为禁忌对象放进tabu list，也可以把和当前值在同一“等高线”上的都放进tabu list。 为了降低计算量，禁忌长度和禁忌表的集合不宜太大，但是禁忌长度太小容易循环搜索，禁忌表太大容易陷入“局部极优解”。 上述程序段中对best_so_far的操作是直接赋值为最优的“解禁候选解”，但是有时候会出现没有大于best_so_far的，候选解也全部被禁的“死锁”状态，这个时候，就应该对候选解中最佳的进行解禁，以能够继续下去。 终止准则：和模拟退火，遗传算法差不多，常用的有：给定一个迭代步数；设定与估计的最优解的距离小于某个范围时，就终止搜索；当与最优解的距离连续若干步保持不变时，终止搜索； 邻域：由伪码 select a new string vn in the neighborhood of vc,可以看出,系统总是在初始点的邻域搜索可能解的,因而必须定义适合的邻域空间,如果解空间存在一个最优解X*,初始搜索点为S0,那么如果S0不存在到达X*的通路,就会使搜索陷入S0的邻域的局部最优解。可以证明如果邻域满足对称性条件，则在假设禁忌表足够长的情况下必然可搜索到全局最优解。
‘陆’ 什么是禁忌搜索遗传算法
http://book.idoican.com.cn/detail/DefaultView.aspx?BookId=ISBN7-111-08090-4.1
‘柒’ 禁忌搜索解决任务分配问题（matlab)
function main()
clear
taskNum = 50;
machNum = 8;
densityV = [0.2]%,0.5,0.8];
ccrV = [0.5]%,1,2];
saSHH = [];
SAtimeHH = [];
for density = densityV
for ccr = ccrV
[ETC,adjMatrix,memReq,memCap] = instance(taskNum,machNum,ccr,density); %% taskH,machH,ccr,density,type
SAresultHH = [];
tSAHH = [];
for iter = 1:5
SAStart = cputime;
[SACost,IteratorSolution] = SA(ETC,adjMatrix,memReq,memCap);
SAresultHH = [SAresultHH,SACost];
SAtime = cputime - SAStart;
tSAHH = [tSAHH,SAtime];
end
saSHH = [saSHH;SAresultHH];
SAtimeHH = [SAtimeHH;tSAHH];
end
end
meanSAsHH = mean(saSHH')
stdSAsHH = std(saSHH')
meanSAtHH = mean(SAtimeHH')
col_sa = length(IteratorSolution);
plot(1:col_sa,IteratorSolution,'-x','linewidth',1.0);
xlabel('Evaluation number');
ylabel('Fitness value');
legend('SA');
function [bestCost,IteratorSolution] = SA(ETC,adjMatrix,memReq,memCap,speed,machRelia,linkRelia)
[taskNum,machNum] = size(ETC);
S = randint(1,taskNum,[1,machNum]); %initial the s randomly
T = IniTemp(S,ETC,adjMatrix,memReq,memCap); %initial the temprature
% Tlow = IniTemp(S,ETC,adjMatrix,memReq,memCap,0.50001);
[cost,memLoad] = calcCost(S,ETC,adjMatrix,memReq,memCap);
Alpha = 0.9; %the value of Alpha
Bita = 1.05; %the value of Bita
Nrep = taskNum * machNum; %the count of inner loop
IteratorSolution = []; %record the change among the loop
bestS = S;
bestCost = cost;
deadline1 = 0; %the count of the outer loop
while deadline1 <= 20
findBest = 0;
iter = 1;
deadline2 = 0;
while (iter <= Nrep)
triS = S;
triCost = cost;
t = fix(1 + rand * taskNum);
p = triS(t);
q = fix(1 + rand * machNum);
while p == q
q = fix(1 + rand * machNum);
end
triS(t) = q;
triCost = triCost - ETC(t,p) + ETC(t,q);
adjTask = find(adjMatrix(t,:));
for k = adjTask %alter communication cost
switch triS(k)
case q
triCost = triCost - adjMatrix(t,k);
case p
triCost = triCost + adjMatrix(t,k);
end
end
if (memLoad(p) > memCap(p)) %calculate violation
if (memLoad(p) - memReq(t)) <= memCap(p)
triCost = triCost - (memLoad(p) - memCap(p));
else
triCost = triCost - memReq(t);
end
end
% there exists no memory violation before migration
if (memLoad(q) + memReq(t)) > memCap(q)
if memLoad(q) <= memCap(q)
triCost = triCost + (memLoad(q) + memReq(t) - memCap(q));
else % there exists memory violation before migration
triCost = triCost + memReq(t);
end
end
Dita = triCost - cost;
if Dita < 0
S = triS;
cost = triCost;
memLoad(p) = memLoad(p) - memReq(t);
memLoad(q) = memLoad(q) + memReq(t);
if (triCost < bestCost)
bestS = triS;
bestCost = triCost;
deadline2 = 0;
findBest = 1;
end
else
if rand < exp(-Dita/T)
S = triS;
cost = triCost;
memLoad(p) = memLoad(p) - memReq(t);
memLoad(q) = memLoad(q) + memReq(t);
end
deadline2 = deadline2 + 1;
if deadline2 >= taskNum * machNum
break;
end
end
iter = iter + 1;
IteratorSolution = [IteratorSolution,cost];
end
T = Alpha * T;
Nrep = Bita * Nrep;
if findBest
deadline1 = 0;
else
deadline1 = deadline1 + 1;
end
end
function [totalCost,memLoad] = calcCost(S,ETC,adjMatrix,memReq,memCap)
[tN,mN] = size(ETC);
totalCost = 0;
memLoad = zeros(1,mN);
for t = 1:tN
totalCost = totalCost + ETC(t,S(t));
memLoad(S(t)) = memLoad(S(t)) + memReq(t);
for k = t+1:tN %t or t+1?
if (adjMatrix(t,k)>0) && (S(k) ~= S(t))
totalCost = totalCost + adjMatrix(t,k);
end
end
end
for m = 1:mN
if memLoad(m) > memCap(m)
totalCost = totalCost + (memLoad(m) - memCap(m));
end
end
function [ETC,adjMatrix,memReq,memCap] = instance(taskNum,machNum,ccr,density)
ETC = fix(1 + 200 * rand(taskNum,machNum));
for i = 1:taskNum-1
for j = i+1:taskNum
if (rand < density)
adjMatrix(i,j) = fix(2 * (1 + 200 * rand) * ccr / ((taskNum-1) * density));
else
adjMatrix(i,j) = 0;
end
adjMatrix(j,i) = adjMatrix(i,j);
end
end
% memory requirement of each task
memReq = fix(1 + 50 * rand(1,taskNum));
% memory capacity of each processor
memCap = fix((1 + rand(1,machNum)) * sum(memReq) / machNum);
function T = IniTemp(S,ETC,adjMatrix,memReq,memCap)
[taskNum,machNum] = size(ETC);
SumCi = 0;
AccValue = 0.9;
Ci = 0;
Cr = 0;
[cost,memLoad] = calcCost(S,ETC,adjMatrix,memReq,memCap); % calculate the total cost
for countNum = 1:200
triS = S;
triCost = cost;
t = fix(1 + taskNum * rand);
p = triS(t);
q = fix(1 + machNum * rand);
while p == q
q = fix(1 + machNum * rand);;
end
triS(t) = q;
triCost = triCost - ETC(t,p) + ETC(t,q);
adjTask = find(adjMatrix(t,:));
for k = adjTask %alter communication cost
switch triS(k)
case q
triCost = triCost - adjMatrix(t,k);
case p
triCost = triCost + adjMatrix(t,k);
end
end
if (memLoad(p) > memCap(p)) %calculate violation
if (memLoad(p) - memReq(t)) <= memCap(p)
triCost = triCost - (memLoad(p) - memCap(p));
else
triCost = triCost - memReq(t);
end
end
% there exists no memory violation before migration
if (memLoad(q) + memReq(t)) > memCap(q)
if memLoad(q) <= memCap(q)
triCost = triCost + (memLoad(q) + memReq(t) - memCap(q));
else % there exists memory violation before migration
triCost = triCost + memReq(t) ;
end
end
memLoad(p) = memLoad(p) - memReq(t);
memLoad(q) = memLoad(q) + memReq(t);
Dita = triCost - cost;
if Dita > 0
Ci = Ci + 1;
SumCi = SumCi + Dita;
else
Cr = Cr + 1;
end;
S = triS;
cost = triCost;
end;
Ca = SumCi / Ci;
T = -Ca / (log((AccValue - 1) * Cr / Ci + AccValue));
function T = calculateT(ETC,adjMatrix,tN,mN,solNum)
sol = fix(1+mN*rand(solNum,tN));
for i = 1:solNum
Fitness(i) = fitnessCal(ETC,adjMatrix,sol(i,:),tN);
end
T = max(Fitness) - min(Fitness);
% ***** the following function has no relation with the above ***** %
function machLoad = calcLoad(A,ETC,adjMatrix) % Objective 2
[tN,mN] = size(ETC);
machLoad = zeros(1,mN);
for k = 1:tN
machLoad(A(k)) = machLoad(A(k)) + ETC(k,A(k));
for h = k+1:tN
if (adjMatrix(k,h) > 0 && A(k) ~= A(h))
machLoad(A(k)) = machLoad(A(k)) + adjMatrix(k,h);
machLoad(A(h)) = machLoad(A(h)) + adjMatrix(k,h);
end
end
end
‘捌’ 禁忌搜索算法的主要思想和特征
禁忌算法是一种亚启发式随机搜索算法1，它从一个初始可行解出发，选择一系列的特定搜索方向(移动)作为试探，选择实现让特定的目标函数值变化最多的移动。为了避免陷入局部最优解，TS搜索中采用了一种灵活的“记忆”技术，对已经进行的优化过程进行记录和选择，指导下一步的搜索方向，这就是Tabu表的建立。 禁忌搜索是对人类思维过程本身的一种模拟，它通过对一些局部最优解的禁忌（也可以说是记忆）达到接纳一部分较差解，从而跳出局部搜索的目的.
‘玖’ 请问关于禁忌搜索算法
禁忌（TabuSearch）算法是一种亚启发式(meta-heuristic)随机搜索算法[1]，它从一个初始可行解出发，选择一系列的特定搜索方向(移动)作为试探，选择实现让特定的目标函数值变化最多的移动。为了避免陷入局部最优解，TS搜索中采用了一种灵活的“记忆”技术，对已经进行的优化过程进行记录和选择，指导下一步的搜索方向，这就是Tabu表的建立。Tabu表中保存了最近若干次迭代过程中所实现的移动的反方向移动，凡是处于Tabu表中的移动，在当前迭代过程中是不允许实现的，这样可以避免算法重新访问在最近若干次迭代过程中已经访问过的解群，从而防止了循环，帮助算法摆脱局部最优解。另外，为了尽可能不错过产生最优解的“移动”，TS搜索还采用“释放准则”的策略。
‘拾’ 有关禁忌搜索
禁忌搜索（Tabu Search或Taboo Search，简称TS）的思想最早由Glover(1986)提出，它是对局部领域搜索的一种扩展，是一种全局逐步寻优算法，是对人类智力过程的一种模拟。TS算法通过引入一个灵活的存储结构和相应的禁忌准则来避免迂回搜索，并通过藐视准则来赦免一些被禁忌的优良状态，进而保证多样化的有效探索以最终实现全局优化。相对于模拟退火和遗传算法，TS是又一种搜索特点不同的 meta-heuristic算法。迄今为止，TS算法在组合优化、生产调度、机器学习、电路设计和神经网络等领域取得了很大的成功，近年来又在函数全局优化方面得到较多的研究，并大有发展的趋势。本章将主要介绍禁忌搜索的优化流程、原理、算法收敛理论与实现技术等内容。
1. 引言
局部领域搜索是基于贪婪思想持续地在当前解的领域中进行搜索，虽然算法通用易实现，且容易理解，但其搜索性能完全依赖于领域结构和初解，尤其窥陷入局部极小而无法保证全局优化性。针对局部领域搜索，为了实现全局优化，可尝试的途径有：以可控性概率接受劣解来逃逸局部极小，如模拟退火算法；扩大领域搜索结构，如TSP的2opt扩展到k-opt；多点并行搜索，如进化计算；变结构领域搜索（ Mladenovic et al,1997）；另外，就是采用TS的禁忌策略尽量避免迂回搜索，它是一种确定性的局部极小突跳策略。
禁忌搜索是人工智能的一种体现，是局部领域搜索的一种扩展。禁忌搜索最重要的思想是标记对应已搜索的局部最优解的一些对象，并在进一步的迭代搜索中尽量避开这些对象（而不是绝对禁止循环），从而保证对不同的有效搜索途径的探索。禁忌搜索涉及到领域（neighborhood）、禁忌表（tabu list）、禁忌长度（tabu 1ength）、候选解（candidate）、藐视准则（candidate）等概念，我们首先用一个示例来理解禁忌搜索及其各重要概念，而后给出算法的一般流程。
2.禁忌搜索示例
组合优化是TS算法应用最多的领域。置换问题，如TSP、调度问题等，是一大批组合优化问题的典型代表，在此用它来解释简单的禁忌搜索算法的思想和操作。对于 n元素的置换问题，其所有排列状态数为n!，当n较大时搜索空间的大小将是天文数字，而禁忌搜索则希望仅通过探索少数解来得到满意的优化解。
首先，我们对置换问题定义一种邻域搜索结构，如互换操作（SWAP），即随机交换两个点的位置，则每个状态的邻域解有Cn2=n（n一1）/2个。称从一个状态转移到其邻域中的另一个状态为一次移动（move），显然每次移动将导致适配值（反比于目标函数值）的变化。其次，我们采用一个存储结构来区分移动的属性，即是否为禁忌“对象”在以下示例中：考虑7元素的置换问题，并用每一状态的相应21个邻域解中最优的5次移动（对应最佳的5个适配值）作为候选解；为一定程度上防止迂回搜索，每个被采纳的移动在禁忌表中将滞留3步（即禁忌长度），即将移动在以下连续3步搜索中将被视为禁忌对象；需要指出的是，由于当前的禁忌对象对应状态的适配值可能很好，因此在算法中设置判断，若禁忌对象对应的适配值优于“ best so far”状态，则无视其禁忌属性而仍采纳其为当前选择，也就是通常所说的藐视准则（或称特赦准则）。
可见，简单的禁忌搜索是在领域搜索的基础上，通过设置禁忌表来禁忌一些已经历的操作，并利用藐视准则来奖励一些优良状态，其中领域结构、候选解、禁忌长度、禁忌对象、藐视准则、终止准则等是影响禁忌搜索算法性能的关键。需要指出的是：
（1）首先，由于TS是局部领域搜索的一种扩充，因此领域结构的设计很关键，它决定了当前解的领域解的产生形式和数目，以及各个解之间的关系。
（2）其次，出于改善算法的优化时间性能的考虑，若领域结构决定了大量的领域解（尤其对大规模问题，如TSP的SWAP操作将产生Cn2个领域解），则可以仅尝试部分互换的结果，而候选解也仅取其中的少量最佳状态。
（3）禁忌长度是一个很重要的关键参数，它决定禁忌对象的任期，其大小直接进而影响整个算法的搜索进程和行为。同时，以上示例中，禁忌表中禁忌对象的替换是采用FIFO方式（不考虑藐视准则的作用），当然也可以采用其他方式，甚至是动态自适应的方式。
（4）藐视准则的设置是算法避免遗失优良状态，激励对优良状态的局部搜索，进而实现全局优化的关键步骤。
（5）对于非禁忌候选状态，算法无视它与当前状态的适配值的优劣关系，仅考虑它们中间的最佳状态为下一步决策，如此可实现对局部极小的突跳（是一种确定性策略）。
（6）为了使算法具有优良的优化性能或时间性能，必须设置一个合理的终止准则来结束整个搜索过程。
此外，在许多场合禁忌对象的被禁次数（frequency）也被用于指导搜索，以取得更大的搜索空间。禁忌次数越高，通常可认为出现循环搜索的概率越大。
3.禁忌搜索算法流程
通过上述示例的介绍，基本上了解了禁忌搜索的机制和步骤。简单TS算法的基本思想是：给定一个当前解（初始解）和一种邻域，然后在当前解的邻域中确定若干候选解；若最佳候选解对应的目标值优于“best so far”状态，则忽视其禁忌特性，用其替代当前解和“best so far”状态，并将相应的对象加入禁忌表，同时修改禁忌表中各对象的任期；若不存在上述候选解，则选择在候选解中选择非禁忌的最佳状态为新的当前解，而无视它与当前解的优劣，同时将相应的对象加入禁忌表，并修改禁忌表中各对象的任期；如此重复上述迭代搜索过程，直至满足停止准则。
条理化些，则简单禁忌搜索的算法步骤可描述如下：
（1）给定算法参数，随机产生初始解x，置禁忌表为空。
（2）判断算法终止条件是否满足？若是，则结束算法并输出优化结果；否则，继续以下步骤。
（3）利用当前解工的邻域函数产生其所有（或若干）邻域解，并从中确定若干候选解。
（4）对候选解判断藐视准则是否满足？若成立，则用满足藐视准则的最佳状态y替代x成为新的当前解，即x=y，并用与y对应的禁忌对象替换最早进入禁忌表的禁忌对象，同时用y替换“best so far”状态，然后转步骤6；否则，继续以下步骤。
（5）判断候选解对应的各对象的禁忌属性，选择候选解集中非禁忌对象对应的最佳状态为新的当前解，同时用与之对应的禁忌对象替换最早进入禁忌表的禁忌对象元素。
（6）转步骤（2）。
同时，上述算法可用如下流程框图更直观地描述，如图4．1．1。
我们可以明显地看到，邻域函数、禁忌对象、禁忌表和藐视准则，构成了禁忌搜索算法的关键。其中，邻域函数沿用局部邻域搜索的思想，用于实现邻域搜索；禁忌表和禁忌对象的设置，体现了算法避免迂回搜索的特点；藐视准则，则是对优良状态的奖励，它是对禁忌策略的一种放松。需要指出的是，上述算法仅是一种简单的禁忌搜索框架，对各关键环节复杂和多样化的设计则可构造出各种禁忌搜索算法。同时，算法流程中的禁忌对象，可以是搜索状态，也可以是特定搜索操作，甚至是搜索目标值等。
同时，与传统的优化算法相比，TS算法的主要特点是：
（1）在搜索过程中可以接受劣解，因此具有较强的“爬山”能力；
（2）新解不是在当前解的邻域中随机产生，而或是优于“best so far”的解，或是非禁忌的最佳解，因此选取优良解的概率远远大于其他解。由于TS算法具有灵活的记忆功能和藐视准则，并且在搜索过程中可以接受劣解，所以具有较强的“爬山”能力，搜索时能够跳出局部最优解，转向解空间的其他区域，从而增强获得更好的全局最优解的概率，所以TS算法是一种局部搜索能力很强的全局迭代寻优算法。