多维搜索算法程序

拟牛顿算法

一、算法流程图/算法步骤

1、DFP算法：

（1）算法步骤：

2、BFGS算法

（1）算法步骤：

3、模式搜索算法

（1）算法步骤：

二、程序代码

1、DFP算法

%拟牛顿法中DFP算法求解f=x1*x1+2*x2*x2-2*x1*x2-4*x1的最小值tic

format long

syms x1 x2 r;

f= x1*x1+2*x2*x2-2*x1*x2-4*x1; %要最小化的函数

x=[x1,x2]; df=jacobian(f,x); %函数f的偏导

df=df.';

x0=[0,0]'; g1=subs(df,x,x0); %起始点的梯度

epsilon=1e-6; %0.000001为搜索精度

k=0;

H0=[1 0;0 1]; %初始矩阵为二阶单位阵

while(norm(g1)>epsilon) %迭代终止条件||g1||<=epsilon

if k==0

d=-H0*g1; %负梯度方向

else

H1=H0+pk*pk'/(qk'*pk)-H0*qk*qk'*H0/(qk'*H0*qk);

d=-H1*g1;H0=H1;

end

z=subs(f,x,x0+r*d); %关于r的函数

result1=jintuifa(z,r); %进退法求下单峰区间

result2= gold(z,r,result1); %黄金分割法求最优步长

step=result2;

x0=x0+step*d;

g0=g1;

g1=subs(df,x,x0);

%gk=double(gk);

qk=g1-g0;

pk=step*d;

k=k+1;

end

k%最优点

x0

min=subs(f,[x1 x2],x0)%最优值

toc

%进退法求下单峰区间

function result= jintuifa(y,r)

t0=0;step=0.0125;

t1=t0+step;

ft0=subs(y,{r},{t0}); %step1 求f(t0) 将函数y中变量x替换为t0 ft1=subs(y,{r},{t1});

if (ft1<=ft0) %step3 step4

step=2*step;

t2=t1+step;

ft2=subs(y,{r},{t2});

while(ft1>ft2)

t1=t2; step=2*step;

t2=t1+step;

ft1=subs(y,{r},{t1});

ft2=subs(y,{r},{t2});

end

else %step5 step6

step=step/2;

t2=t1;

t1=t2-step;

ft1=subs(y,{r},{t1});

while(ft1>ft0)

step=step/2;

t2=t1;

t1=t2-step;

ft1=subs(y,{r},{t1});

end

end

result=[t2]；

%黄金分割法求最优步长

function result=gold(y,r,m)

a=0;b=m;e=1e-5;

a1=a+0.382*(b-a); %step1

f1=subs(y,{r},{a1});

a2=a+0.618*(b-a); %step2

f2=subs(y,{r},{a2});

while(abs(b-a)>e)

if f1

b=a2;a2=a1;f2=f1;

a1=a+0.382*(b-a); %转step2

f1=subs(y,{r},{a1});

else

a=a1;a1=a2;f1=f2;

a2=a+0.618*(b-a); %step5

f2=subs(y,{r},{a2});

end

end

answer=(a+b)/2; %最优的x值

result=[answer]; %最优的函数值

2、BFGS算法

%拟牛顿法中BFGS算法求解f=x1*x1+2*x2*x2-2*x1*x2-4*x1的最小值

tic

format long

syms x1 x2 r;

f= x1*x1+2*x2*x2-2*x1*x2-4*x1; %要最小化的函数

x=[x1,x2]; df=jacobian(f,x); %函数f的偏导

df=df.'; x0=[0,0]'; g1=subs(df,x,x0); %起始点的梯度

epsilon=1e-6; %0.000001为搜索精度

k=0; %搜索次数用k来计数

H0=[1 0;0 1]; %初始矩阵为二阶单位阵

while(norm(g1)>epsilon) %迭代终止条件||g1||<=epsilon

if k==0

d=-H0*g1; %负梯度方向

else

H1=H0+(1+qk'*H0*qk/(pk'*qk))*(pk*pk')/(pk'*qk)-(pk*qk'*H0+H0*qk*pk')/(pk'*qk);

d=-H1*g1;H0=H1;

end

z=subs(f,x,x0+r*d); %关于r的函数

result1=jintuifa(z,r); %进退法求下单峰区间

result2= gold(z,r,result1); %黄金分割法求最优步长

step=result2;

x0=x0+step*d;

g0=g1; g1=subs(df,x,x0);

qk=g1-g0;

pk=step*d;

k=k+1;

end

k

x0

min=subs(f,[x1 x2],x0) %最优值

toc

%进退法求下单峰区间

function result= jintuifa(y,r)

t0=0;step=0.0125;

t1=t0+step;

ft0=subs(y,{r},{t0}); %step1 求f(t0) 将函数y中变量x替换为t0 ft1=subs(y,{r},{t1});

if (ft1<=ft0) %step3 step4

step=2*step;

t2=t1+step;

ft2=subs(y,{r},{t2});

while(ft1>ft2)

t1=t2; step=2*step;

t2=t1+step;

ft1=subs(y,{r},{t1});

ft2=subs(y,{r},{t2});

end

else %step5 step6

step=step/2;

t2=t1;

t1=t2-step;

ft1=subs(y,{r},{t1});

while(ft1>ft0)

step=step/2;

t2=t1;

t1=t2-step;

ft1=subs(y,{r},{t1});

end

end

result=[t2]；

%黄金分割法求最优步长

function result=gold(y,r,m)

a=0;b=m;e=1e-5;

a1=a+0.382*(b-a); %step1

f1=subs(y,{r},{a1});

a2=a+0.618*(b-a); %step2

f2=subs(y,{r},{a2});

while(abs(b-a)>e)

if f1

b=a2;a2=a1;f2=f1;

a1=a+0.382*(b-a); %转step2

f1=subs(y,{r},{a1});

else

a=a1;a1=a2;f1=f2;

a2=a+0.618*(b-a); %step5

f2=subs(y,{r},{a2});

end

end

answer=(a+b)/2; %最优的x值

result=[answer];%最优的函数值

3、模式搜索算法

function [u,I]=touzi(m,n,L)

for i=1:m+1

v(i,n)=L(i,n);

w(i,n)=i-1;

end

for k=n-1:-1:2

for i=1:m+1

v(i,k)=0;

w(i,k)=i-1;

for j=1:i

if v(i,k)

v(i,k)=L(j,k)+v(i+1-j,k+1);

w(i,k)=j-1;

end

end

end

end

v(m+1,1)=0;

w(m+1,1)=m;

for j=1:m+1

if v(m+1,1)

v(m+1,1)=L(j,1)+v(m+2-j,2);

w(m+1,1)=j-1;

end

end

I=v(m+1,1);

u(1)=w(m+1,1);

s=m-u(1);

for i=2:n

u(i)=w(s+1,i);

s=s-u(i);

end

三、具体算例

1、求解f=x1*x1+2*x2*x2-2*x1*x2-4*x1的最小值，精度为10^-6

2、3x1-cos(x2*x3)-1/2=0

求解方程组f= x1^2-81(x2+0.1)+sinx3+1.06=0, 精度为10^-6

e^-x1x2+20x3+1/3(10pi-3)=0

四、结果与分析

1、不同算例算法实现结果：

（1）对于函数f=x1*x1+2*x2*x2-2*x1*x2-4*x1的最小值，要求精度为10^（-6），有下表：

DFP算法BFGS算法模式搜索算法

最优解-8 -8.000000000000002 -8

X1 3.999999973127794 4.000000038039509 3.999999968943251

X2 1.999999973127734 2.000000025359692 1.999999975234561

分割次数 3 3 3

运算速度0.641077 0.587759 0.476789

（2）对于求解方程组的函数，要求精度为10^（-6），有下表：

DFP算法BFGS算法模式搜索算法

最优解 4.231952397804293e-19 9.504444513998618e-20 7.504444513998618e-19 X10.499626458237735 0.499626458171345 0.499626458171345

X2-0.090029188650297 -0.090029188647958 -0.090029188631349

X3-0.525899173018169 -0.525899173032793 -0.525899172667583

次数7 7 7

速度 1.289414 1.323472 1.597269

2、三种算法的基本比较：

（1）DFP算法采用近似的矩阵来代替HESSE阵，克服了在HESSE阵不可逆的情况下求解的问题，通过实验来看，该方法的计算速度还是很快的，而且在求解函数较为复杂的情况下较BFGS 效率更高；此外，在精度要求足够高的情况下，计算结果比较理想。

但是，在计算过程中由于舍入误差的影响，会导致校正矩阵的计算过程中出现除数为0的情况，这个问题需要进一步研究。

（2）BFGS算法不仅具有二次收敛性，而且只有初始矩阵对称正定，则BFGS修正公式所产生的矩阵Hk也是对称正定的，且Hk不易变为奇异，因此BFGS比DFP具有更好的数值稳

定性。从实验数据中也可以看到，该方法的计算结果较DFP更加精确，在优化函数相对简单的情况下具有更快的运算速度。

（3）模式搜索法较DFP、BFGS算法，是一种更为直接的搜索方法，在计算时不需要目标函数的导数，所以在解决不可导的函数或者求导异常麻烦的函数的优化问题时非常有效。从实验结果来看，在函数相对简单的情况下，模式搜索法计算效率较高，计算结果较为精确；但是在函数较为复杂的情况下，该方法的效率就容易受具体函数和终止条件的影响，比如说将误差因子设置的小一些，由10^(-6)变得更精确一些，那么计算速度将增加很多。

（4）总的来说：

a、当初始值接近真实的极值点时，收敛快慢依次为：模式搜索法>DFP方法>BFGS方法。且收敛的值相对于真实值的精度也是：模式搜索法>DFP方法>BFGS方法。所以，当在真实极值点附近，最好使用模式搜索法，收敛速度快而精确。

b、DFP方法的收敛速度和收敛精度要高于BFGS方法。BFGS方法要比DFP方法偏向于真实值。说明当初值点偏离真实点较远时，BFGS方法有更强的稳定性。

五、体会

1、通过与牛顿法的比较，以及对DFP和BPGS算法的编程实现与分析，我发现Hesse矩阵在拟牛顿法中是不计算的，拟牛顿法是构造与Hesse矩阵相似的正定矩阵，这个构造方法，使用了目标函数的梯度（一阶导数）信息和两个点的“位移”（Xk-Xk-1）来实现。使用Hesse矩阵的近似矩阵来代替Hesse矩阵，不仅不会导致求解效果变差，效果反而会变好。

具体来说，拟牛顿法与牛顿法的迭代过程一样，仅仅是各个Hesse矩阵的求解方法不一样。在远离极小值点处，Hesse矩阵一般不能保证正定，使得目标函数值不降反升。而拟牛顿法可以使目标函数值沿下降方向走下去，并且到了最后，在极小值点附近，可使构造出来的矩阵与Hesse 矩阵“很像”，这样，拟牛顿法也会具有牛顿法的二阶收敛性。

2、模式搜索是一种很直接的搜索方法，就是设置一定的终止条件，寻找一系列的X0，X1，X2，…，这些点都越来越靠近最优值点，当搜索进行到终止条件时则将最后一个点作为本次搜索的解。这样的算法也许会因为终止条件的不同，计算的结果和效率有所差异，但是它省去了更为繁琐的求导过程，应该说是一种很不错的优化方法。

3、通过这三个算法的学习，我进一步懂得了两个道理:

（1）在学习一个算法的时候，应该在充分理解的基础上加以分析，发现它的优缺点，以期作进一步的改进和优化，比如说拟牛顿法就是牛顿法的一个很好的改进；

（2）没有绝对最优的算法，但是要懂得扬长避短，懂得在合理的范围内加以转化，比如本例中利用模式搜索方法避免求导的方法。

六．改进

1.

禁忌搜索算法浅析

禁忌搜索算法浅析 摘要:本文介绍了禁忌搜索算法的基本思想、算法流程及其实现的伪代码。禁忌搜索算法（Tabu Search或Taboo Search，简称TS算法）是一种全局性邻域搜索算法，可以有效地解决组合优化问题，引导算法跳出局部最优解，转向全局最优解的功能。 关键词:禁忌搜索算法；组合优化；近似算法；邻域搜索 1禁忌搜索算法概述 禁忌搜索算法（Tabu Search）是由美国科罗拉多州大学的Fred Glover教授在1986年左右提出来的，是一个用来跳出局部最优的搜寻方法。在解决最优问题上，一般区分为两种方式：一种是传统的方法，另一种方法则是一些启发式搜索算法。使用传统的方法，我们必须对每一个问题都去设计一套算法，相当不方便，缺乏广泛性，优点在于我们可以证明算法的正确性，我们可以保证找到的答案是最优的；而对于启发式算法，针对不同的问题，我们可以套用同一个架构来寻找答案，在这个过程中，我们只需要设计评价函数以及如何找到下一个可能解的函数等，所以启发式算法的广泛性比较高，但相对在准确度上就不一定能够达到最优，但是在实际问题中启发式算法那有着更广泛的应用。 禁忌搜索是一种亚启发式随机搜索算法，它从一个初始可行解出发，选择一系列的特定搜索方向(移动)作为试探，选择实现让特定的目标函数值变化最多的移动。为了避免陷入局部最优解，TS搜索中采用了一种灵活的“记忆”技术，对已经进行的优化过程进行记录和选择，指导下一步的搜索方向。 TS是人工智能的一种体现，是局部领域搜索的一种扩展。禁忌搜索是在领域搜索的基础上，通过设置禁忌表来禁忌一些已经历的操作，并利用藐视准则来奖励一些优良状态，其中涉及邻域（neighborhood）、禁忌表（tabu list）、禁忌长度（tabu 1ength）、候选解（candidate）、藐视准则（candidate）等影响禁忌搜索算法性能的关键因素。迄今为止，TS算法在组合优化、生产调度、机器学习、电路设计和神经网络等领域取得了很大的成功，近年来又在函数全局优化方面得到较多的研究，并大有发展的趋势。 2禁忌搜索算法的基本思想 禁忌搜索最重要的思想是标记对应已搜索的局部最优解的一些对象，并在进一步的迭代搜索中尽量避开这些对象（而不是绝对禁止循环），从而保证对不同的有效搜索途径的探索，TS的禁忌策略尽量避免迂回搜索，它是一种确定性的局部极小突跳策略。 禁忌搜索是对局部邻域搜索的一种扩展，是一种全局逐步寻求最优算法。局部邻域搜索是基于贪婪思想持续地在当前解的邻域中进行搜索，虽然算法通用易实现，且容易理解，但搜索性能完全依赖于邻域结构和初解，尤其会陷入局部极小而无法保证全局优化型。 禁忌搜索算法中充分体现了集中和扩散两个策略，它的集中策略体现在局部搜索，即从一点出发，在这点的邻域内寻求更好的解，以达到局部最优解而结束，为了跳出局部最优解，扩散策略通过禁忌表的功能来实现。禁忌表中记下已经到达的某些信息，算法通过对禁

约束满足与邻域搜索结合的混合算法及应用

约束满足与邻域搜索结合的混合算法及应用[摘要] 总结约束满足求解技术和邻域搜索算法,分析约束满足与邻域搜索 单一算法的优劣,以及两者结合的优势,提出约束满足与邻域搜索相结合的混合算法的一般框架,并以Job Shop 调度优化问题为例对该算法框架进行实例说明。 [关键词] 约束满足;邻域搜索;混合算法 ddoi : 10 . 3969 / j . issn . 1673 - 0194 . 2009 . 21 . 017 1引言 约束满足技术集成了运筹学、人工智能、逻辑编程和图论中的方法和思想,是解决组合优化问题的一门新兴技术。约束满足建模能力较强,在约束求解中,能够充分利用问题的结构信息和约束关系,采用约束传播、回溯等技术对求解空间快速缩减,提高问题的求解效率。邻域搜索算法是一种非常有效的解决组合优化问题的方法,在搜索空间内利用局部指导规则探索优良解,搜索效率高,具有可衡量性。约束满足与邻域搜索法均存在自身的优势和局限性,相互结合可以有效利用算法的互补性。 目前对约束满足与邻域搜索相结合的混合算法的研究成果比较少。文献[1]将邻域搜索和向前看(Look Ahead)技术结合,在搜索过程中遇到死点时要么回溯,要么应用邻域搜索继续新的空间搜索。文献[2]中提出的“Decision-Repair”方法集成了禁忌搜索、一致性技术和基于冲突的启发式方法来引导搜索过程。文献[3]在系统搜索过程中,使用变量排序和值排序法,进行不完全搜索,用N皇后问题进行算法测试。文献[4]用约束规划算法产生一个可行解,作为禁忌搜索算法的初始解。文献[5]对NEH算法加以扩展,得到高质量的初始解,提出跳出局部极值方法,改进约束满足修复算法。 本文首先介绍约束满足技术和邻域搜索技术,然后总结两者相结合的混合算法的框架,最后以Job Shop 调度为例,给出混合算法实现步骤。 2约束满足技术和邻域搜索技术 2.1 约束满足技术

论文-禁忌搜索算法

基于禁忌搜索算法的车辆路径选择 摘要：本文从VRP的提出背景与求解方法出发，阐释了禁忌搜索算法的原理与影响算法性能的关键因素，进而将禁忌搜索算法的思想运用于解决车辆路径问题，在VRP问题初始解的基础上，用禁忌搜索算法优化车辆配送路线，设计出直观且策略易于理解的客户直接排列的解的表示方法，最后将该算法用C语言实现并用于求解VRP问题，测试结果表明该算法可行且解的质量较高。 关键词：车辆路径问题；禁忌搜索；邻域；禁忌表 1.引言 物流配送过程的成本构成中，运输成本占到52%之多，如何安排运输车辆的行驶路径，使得配送车辆依照最短行驶路径或最短时间费用，在满足服务时间限制、车辆容量限制、行驶里程限制等约束条件下，依次服务于每个客户后返回起点，实现总运输成本的最小化，车辆路径问题正是基于这一需求而产生的。求解车辆路径问题（Vehicle Routing Problem简记VRP）的方法分为精确算法与启发式算法，精确算法随问题规模的增大，时间复杂度与空间复杂度呈指数增长，且VRP问题属于NP-hard问题，求解比较困难，因此启发式算法成为求解VRP问题的主要方法。禁忌搜索算法是启发式算法的一种，为求解VRP提供了新的工具。本文通过一种客户直接排列的解的表示方法，设计了一种求解车辆路径问题的新的禁忌搜索算法。 因此研究车辆路径问题，就是要研究如何安排运输车辆的行驶路线，使运输车辆依照最短的行驶路径或最短的时间费用，依次服务于每个客户后返回起点，总的运输成本实现最小。 2.车辆路径问题的禁忌搜索算法 2.1 车辆路径问题的描述 车辆路径问题的研究目标是对一系列送货点或取货点，确定适当的配送车辆行驶路线，使车辆有序地通过它们，在满足一定的约束条件（如货物需求量、发送量交发货时间、车辆容量限制、行驶里程限制、时间限制等）下，达到一定的目标（如路程最短、费用最小、时间尽量少、使用车辆尽量少等)。参见下图2.1所示：其中0表示配送中心，1～８表示客户编号。 图2.1 车辆路径问题 在本文中为使得问题易于理解，将该问题描述为：有一定数量的客户，各自有不同数量的货物需求，且每个客户的位置和需求量一定，一个物流中心提供这些货物，并有一个车队负责分送货物，每台配送车辆的载重量一定，这里假设车辆的型号一致，即最大载重量和最

禁忌搜索算法评述(一)

禁忌搜索算法评述(一) 摘要:工程应用中存在大量的优化问题,对优化算法的研究是目前研究的热点之一。禁忌搜索算法作为一种新兴的智能搜索算法具有模拟人类智能的记忆机制,已被广泛应用于各类优化领域并取得了理想的效果。本文介绍了禁忌搜索算法的特点、应用领域、研究进展,概述了它的算法基本流程,评述了算法设计过程中的关键要点,最后探讨了禁忌搜索算法的研究方向和发展趋势。 关键词:禁忌搜索算法;优化;禁忌表;启发式;智能算法 1引言 工程领域内存在大量的优化问题,对于优化算法的研究一直是计算机领域内的一个热点问题。优化算法主要分为启发式算法和智能随机算法。启发式算法依赖对问题性质的认识,属于局部优化算法。智能随机算法不依赖问题的性质,按一定规则搜索解空间,直到搜索到近似优解或最优解,属于全局优化算法,其代表有遗传算法、模拟退火算法、粒子群算法、禁忌搜索算法等。禁忌搜索算法(TabuSearch,TS)最早是由Glover在1986年提出,它的实质是对局部邻域搜索的一种拓展。TS算法通过模拟人类智能的记忆机制,采用禁忌策略限制搜索过程陷入局部最优来避免迂回搜索。同时引入特赦(破禁)准则来释放一些被禁忌的优良状态,以保证搜索过程的有效性和多样性。TS算法是一种具有不同于遗传和模拟退火等算法特点的智能随机算法,可以克服搜索过程易于早熟收敛的缺陷而达到全局优化1]。 迄今为止,TS算法已经广泛应用于组合优化、机器学习、生产调度、函数优化、电路设计、路由优化、投资分析和神经网络等领域,并显示出极好的研究前景2~9,11~15]。目前关于TS 的研究主要分为对TS算法过程和关键步骤的改进,用TS改进已有优化算法和应用TS相关算法求解工程优化问题三个方面。 禁忌搜索提出了一种基于智能记忆的框架,在实际实现过程中可以根据问题的性质做有针对性的设计,本文在给出禁忌搜索基本流程的基础上,对如何设计算法中的关键步骤进行了有益的总结和分析。 2禁忌搜索算法的基本流程 TS算法一般流程描述1]: (1)设定算法参数,产生初始解x,置空禁忌表。 (2)判断是否满足终止条件?若是,则结束,并输出结果;否则,继续以下步骤。 (3)利用当前解x的邻域结构产生邻域解,并从中确定若干候选解。 (4)对候选解判断是否满足藐视准则?若成立,则用满足藐视准则的最佳状态y替代x成为新的当前解,并用y对应的禁忌对象替换最早进入禁忌表的禁忌对象,同时用y替换“bestsofar”状态,然后转步骤(6);否则,继续以下步骤。 (5)判断候选解对应的各对象的禁忌情况,选择候选解集中非禁忌对象对应的最佳状态为新的当前解,同时用与之对应的禁忌对象替换最早进入禁忌表的禁忌对象。 (6)转步骤(2)。 算法可用图1所示的流程图更为直观的描述。 3禁忌搜索算法中的关键设计 3.1编码及初始解的构造 禁忌搜索算法首先要对待求解的问题进行抽象,分析问题解的形式以形成编码。禁忌搜索的过程就是在解的编码空间里找出代表最优解或近似优解的编码串。编码串的设计方式有多种策略,主要根据待解问题的特征而定。二进制编码将问题的解用一个二进制串来表示2],十进制编码将问题的解用一个十进制串来表示3],实数编码将问题的解用一个实数来表示4],在某些组合优化问题中,还经常使用混合编码5]、0-1矩阵编码等。 禁忌搜索对初始解的依赖较大,好的初始解往往会提高最终的优化效果。初始解的构造可以

算法设计与分析复习题目及答案 (3)

分治法 1、二分搜索算法是利用（分治策略）实现的算法。 9. 实现循环赛日程表利用的算法是（分治策略） 27、Strassen矩阵乘法是利用（分治策略）实现的算法。 34．实现合并排序利用的算法是（分治策略）。 实现大整数的乘法是利用的算法（分治策略）。 17．实现棋盘覆盖算法利用的算法是（分治法）。 29、使用分治法求解不需要满足的条件是（子问题必须是一样的）。 不可以使用分治法求解的是（0/1背包问题）。 动态规划 下列不是动态规划算法基本步骤的是（构造最优解） 下列是动态规划算法基本要素的是（子问题重叠性质）。 下列算法中通常以自底向上的方式求解最优解的是（动态规划法） 备忘录方法是那种算法的变形。（动态规划法） 最长公共子序列算法利用的算法是（动态规划法）。 矩阵连乘问题的算法可由（动态规划算法B）设计实现。 实现最大子段和利用的算法是（动态规划法）。 贪心算法 能解决的问题：单源最短路径问题，最小花费生成树问题，背包问题，活动安排问题， 不能解决的问题：N皇后问题，0/1背包问题 是贪心算法的基本要素的是（贪心选择性质和最优子结构性质）。 回溯法 回溯法解旅行售货员问题时的解空间树是（排列树）。 剪枝函数是回溯法中为避免无效搜索采取的策略 回溯法的效率不依赖于下列哪些因素（确定解空间的时间）

分支限界法 最大效益优先是（分支界限法）的一搜索方式。 分支限界法解最大团问题时，活结点表的组织形式是（最大堆）。 分支限界法解旅行售货员问题时，活结点表的组织形式是（最小堆） 优先队列式分支限界法选取扩展结点的原则是（结点的优先级） 在对问题的解空间树进行搜索的方法中,一个活结点最多有一次机会成为活结点的是( 分支限界法). 从活结点表中选择下一个扩展结点的不同方式将导致不同的分支限界法,以下除( 栈式分支限界法)之外都是最常见的方式. （1）队列式(FIFO)分支限界法：按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。 （2）优先队列式分支限界法：按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。 （最优子结构性质）是贪心算法与动态规划算法的共同点。 贪心算法与动态规划算法的主要区别是（贪心选择性质）。 回溯算法和分支限界法的问题的解空间树不会是( 无序树). 14．哈弗曼编码的贪心算法所需的计算时间为（ B ）。 A、O（n2n） B、O（nlogn） C、O（2n） D、O（n） 21、下面关于NP问题说法正确的是（B ） A NP问题都是不可能解决的问题 B P类问题包含在NP类问题中 C NP完全问题是P类问题的子集 D NP类问题包含在P类问题中 40、背包问题的贪心算法所需的计算时间为（ B ）

禁忌搜索算法

禁忌搜索算法 2009210042 李同玲运筹学与控制论 搜索是人工智能的一个基本问题，一个问题的求解过程就是搜索。人工智能在各应用领域中，被广泛的使用。现在，搜索技术渗透在各种人工智能系统中，可以说没有哪一种人工智能的应用不用搜索方法。 禁忌搜索算法(Tabu Search或Taboo Search,简称TS)的思想最早由Glover (美国工程院院士，科罗拉多大学教授)在1977年提出，它是对局部邻域搜索的一种扩展，是一种全局邻域搜索算法，是人工智能的一种体现，是一种全局逐步寻优算法，是对人类智力过程的一种模拟。TS算法通过引入一个灵活的存储结构和相应的禁忌准则来避免迂回搜索，并通过藐视准则来赦免一些被禁忌的优良状态，进而保证多样化的有效探索以最终实现全局优化。迄今为止，TS算法在组合优化、生产调度、机器学习、电路设计和神经网络等领域取得了很大的成功，近年来又在函数全局优化方面得到较多的研究，并大有发展的趋势。 1.1引言 1.1.1局部邻域搜索 局部邻域搜索是基于贪婪思想持续地在当前的邻域中进行搜索，虽然算法通用易实现，且容易理解，但其搜索性能完全依赖于邻域结构和初始解，尤其容易陷入局部极小而无法保证全局优化性。 局部搜索的算法可以描述为：

1、 选定一个初始可行解：0x ； 记录当前最优解0best x x =，()best T N x =； 2、 当\best T x =?时，或满足其他停止运算准则时，输出计算结果， 停止运算；否则，从T 中选一集合S ，得到S 中的最好解now x ；若()()now best f x f x <，则b e s t n o w x x =，()best T N x =；否则，\T T S =；重复2，继续搜索 这种邻域搜索方法容易实现理解，容易实现，而且具有很好的通用性，但是搜索结果完全依赖于初始解和邻域的结构，而且只能搜索到局部最优解。为了实现全局搜索，禁忌搜索采用允许接受劣解来逃离局部最优解。针对局部领域搜索，为了实现全局优化，可尝试的途径有：以可控性概率接受劣解来逃逸局部极小，如模拟退火算法；扩大领域搜索结构，如TSP 的2-opt 扩展到k-opt ；多点并行搜索，如进化计算；变结构领域搜索（ Mladenovic et al,1997）；另外，就是采用TS 的禁忌策略尽量避免迂回搜索，它是一种确定性的局部极小突跳策略。 1.1.2禁忌搜索算法的基本思想 禁忌搜索算法的基本思想就是在搜索过程中将近期的历史上的搜索过程存放在禁忌表（Tabu List ）中，阻止算法重复进入，这样就有效地防止了搜索过程的循环。禁忌表模仿了人类的记忆功能，禁忌搜索因此得名，所以称它是一种智能优化算法。 具体的思路如下：禁忌搜索算法采用了邻域选优的搜索方法，为了能逃离局部最优解，算法必须能够接受劣解，也就是每一次迭代得到的解不必一定优于原来的解。但是。一旦接受了劣解，迭代就可能

模拟退火算法和禁忌搜索算法的matlab源程序

%%% 模拟退火算法源程序 % 此题以中国31省会城市的最短旅行路径为例： % clear;clc; function [MinD,BestPath]=MainAneal(pn) % CityPosition存储的为每个城市的二维坐标x和y； CityPosition=[1304 2312;3639 1315;4177 2244;3712 1399;3488 1535;3326 1556;3238 1229;... 4196 1044;4312 790;4386 570;3007 1970;2562 1756;2788 1491;2381 1676;... 1332 695;3715 1678;3918 2179;4061 2370;3780 2212;3676 2578;4029 2838;... 4263 2931;3429 1908;3507 2376;3394 2643;3439 3201;2935 3240;3140 3550;... 2545 2357;2778 2826;2370 2975]; figure(1); plot(CityPosition(:,1),CityPosition(:,2),'o') m=size(CityPosition,1);%城市的数目 % D = sqrt((CityPosition(:,ones(1,m)) - CityPosition(:,ones(1,m))').^2 + ... (CityPosition(:,2*ones(1,m)) - CityPosition(:,2*ones(1,m))').^2); path=zeros(pn,m); for i=1:pn path(i,:)=randperm(m); end iter_max=100;%i m_max=5;% Len1=zeros(1,pn);Len2=zeros(1,pn);path2=zeros(pn,m); t=zeros(1,pn); T=1e5; tau=1e-5; N=1; while T>=tau iter_num=1; m_num=1; while m_num

禁忌搜索和应用

目录 一、摘要 (2) 二、禁忌搜索简介 (2) 三、禁忌搜索的应用 (2) 1、现实情况 (2) 2、车辆路径问题的描述 (3) 3、算法思路 (3) 4、具体步骤 (3) 5、程序设计简介 (3) 6、算例分析 (4) 四、禁忌搜索算法的评述和展望 (4) 五、参考文献 (5)

禁忌搜索及应用 一、摘要 工程应用中存在大量的优化问题,对优化算法的研究是目前研究的热点之一。禁忌搜索算法作为一种新兴的智能搜索算法具有模拟人类智能的记忆机制,已被广泛应用于各类优化领域并取得了理想的效果。本文介绍了禁忌搜索算法的特点、应用领域、研究进展,概述了它的算法基本流程,评述了算法设计过程中的关键要点,最后探讨了禁忌搜索算法的研究方向和发展趋势。 二、禁忌搜索简介 禁忌搜索（Tabu Search或Taboo Search，简称TS）的思想最早由Glover(1986)提出，它是对局部领域搜索的一种扩展，是一种全局逐步寻优算法，是对人类智力过程的一种模拟。TS算法通过引入一个灵活的存储结构和相应的禁忌准则来避免迂回搜索，并通过藐视准则来赦免一些被禁忌的优良状态，进而保证多样化的有效探索以最终实现全局优化。相对于模拟退火和遗传算法，TS是又一种搜索特点不同的meta-heuristic算法。 迄今为止，TS算法在组合优化、生产调度、机器学习、电路设计和神经网络等领域取得了很大的成功，近年来又在函数全局优化方面得到较多的研究，并大有发展的趋势。 禁忌搜索是人工智能的一种体现，是局部领域搜索的一种扩展。禁忌搜索最重要的思想是标记对应已搜索的局部最优解的一些对象，并在进一步的迭代搜索中尽量避开这些对象（而不是绝对禁止循环），从而保证对不同的有效搜索途径的探索。禁忌搜索涉及到邻域（neighborhood）、禁忌表（tabu list）、禁忌长度（tabu length）、候选解（candidate）、藐视准则（aspiration criterion）等概念。 三、禁忌搜索的应用 禁忌搜索应用的领域多种多样，下面我们简单的介绍下基于禁忌搜索算法的车辆路径选择。 1、现实情况 物流配送过程的成本构成中，运输成本占到52%之多，如何安排运输车辆的行驶路径，使得配送车辆依照最短行驶路径或最短时间费用，在满足服务时间限制、车辆容量限制、行驶里程限制等约束条件下，依次服务于每个客户后返回起点，实现总运输成本的最小化，车辆路径问题正是基于这一需求而产生的。求解车辆路径问题（vehicle routing problem简记vrp）的方法分为精确算法与启发式算法，精确算法随问题规模的增大，时间复杂度与空间复杂度呈指数增长，且vrp问题属于np-hard问题，求解比较困难，因此启发式算法成为求解vrp问题的主要方法。禁忌搜索算法是启发式算法的一种，为求解vrp提供了新的工具。本文通过一种客户直接排列的解的表示方法，设计了一种求解车辆路径问题的新的禁忌搜索算法。 因此研究车辆路径问题，就是要研究如何安排运输车辆的行驶路线，使运输车辆依照最

组合优化近似搜索算法中的超启发式发展趋势

文章编号:100622475(2004)0620007205 收稿日期:2003206230 作者简介:李菊芳(19782),女,河南林州人,国防科技大学人文与管理学院博士研究生,研究方向:系统管理与综合集成技术,智能优化算法;谭跃进(19582),男,湖南长沙人,教授,博士生导师,研究方向:系统管理与综合集成技术。 组合优化近似搜索算法中的超启发式发展趋势 李菊芳,谭跃进 (国防科技大学人文与管理学院系统工程研究所,湖南长沙　410073) 摘要:对组合优化中近似搜索算法采用的超启发式策略进行了总结和分类,并着重从强化和变化两个概念出发分析了不同超启发式的优缺点,探讨了其发展趋势,目的是为开发博采众长的混合近似搜索算法提供参考和指导。关键词:近似搜索算法;超启发式;强化;变化;混合算法中图分类号:TP301.6 文献标识码:A U ptrend on Metaheuristics in Approxim ate Search Algorithms for Combinatori al Optimization LI Ju 2fang ,T AN Y ue 2jin (Institute of Management Science ,National University of Defense T echnology ,Changsha 410073,China ) Abstract :This paper classifies and summarizes the metaheuristics in approximate search alg orithms for combinatorial optimization ,and em phasizes analyzing s ome strengths and weaknesses of different approaches from tw o concepts as intensification and diversification.The purpose is to find the uptrend and provide s ome references and guidance for developing hybrid alg orithms combining strengths of different mataheuristics. K ey w ords :approximate search alg orithm ;metaheuristic ;intensification ;diversification ;hybrid alg orithm 0　引　言 组合优化问题的求解算法可以分为两大类:一类 是精确算法,这类算法将对解空间进行完整搜索,可以保证找到小规模问题的最优解;另一类是近似算法,这类算法放弃了对解空间搜索的完整性,因此不能保证最终解的全局最优性。由于组合优化问题中大量存在着NP 2Hard 问题,因此精确搜索算法在问题规模较大时往往无法实现。而近似算法尽管不能证明解的最优性,但很多情况下却能够以合理的计算代价找出较好的近优解,因而逐渐被理论研究和实践应用所广泛关注。 组合优化问题的近似求解技术中,较常用、较有代表性的是邻域搜索(neighborhood search )算法,这类算法从某初始解出发,利用一些规则指导搜索过程反复对当前解的邻域进行搜索并替换当前解,最终逐步实现向最优解移动。基本局部搜索(basic local search )算法或称爬山法(hill climbing )可以看作是最简单的邻域搜索算法,它采用一种迭代式改进的简单 思想,以贪婪的方式在当前解的近邻中进行搜索,每步移动只接受比当前解更好的解。基本局部搜索的最大缺点在于其往往很快就会到达局部极值并终止整个搜索过程,从而放弃对解空间中其它区域的搜索,所找到的局部极值解则往往离全局最优解还有很大距离。针对这个缺点,许多改进的邻域搜索算法在基本局部搜索算法的基础上,采用了一些更好的规则和方法来指导搜索过程摆脱局部极值,实现在整个解空间中对优良解的探索,如模拟退火、禁忌搜索、遗传算法等等,它们所使用的用于指导搜索的规则和方法又被称为超启发式(metaheuristics )。目前对超启发式尚没有统一的标准定义,从字面理解,英文中heuristic (译为启发式)的意思是探索性过程或方法,而前缀meta 是超出、在一个更高层次的意思,算法中采用超启发式的目的是要在一个更高的层次对解空间进行探索。 总的说来,超启发式一般具有如下基本属性[2]:(1)它是一种指导搜索过程的策略;(2)其目标是高效地探索解空间来寻找最优(次优)解;(3)构造超启发 计算机与现代化 　2004年第6期 J IS UAN J I Y U XI ANDAIH UA 总第106期

一维数组的常用算法源代码

1.数组元素逆置 #include #include int main() { int a[10],t,i,j; //随机生成数组元素,并显示 printf("逆置前:"); for(i=0;i<10;i++) { a[i]= rand()%100; printf("%4d",a[i]); } printf("\n"); //数组元素逆置，即对称位置交换for(i=0,j=9;i

2.静态查找 #include #include int main() { int a[10],t,i,j; //随机生成数组元素,并显示 printf("数组元素:"); for(i=0;i<10;i++) { a[i]= rand()%100; printf("%4d",a[i]); } printf("\n"); //输入查找的数 printf("请输入要查找的数："); scanf("%d", &t); //静态查找:从前往后依次遍历 for(i=0;i<10;i++) if(a[i]==t) break;//找到并退出//输出查找结果 if(i<10)

printf("%d在数组a[%d]中。\n",t,i); else printf("%d不在a数组中。\n",t); } 3.二分查找：前提数组有序 #include #include void sort(int a[], int n) { int i,j, t; for(i=0;ia[j+1]) {t=a[j]; a[j]=a[j+1]; a[j+1]=t;} } int main() { int a[10],t,i,left,right,mid; //随机生成数组元素 printf("数组元素:"); for(i=0;i<10;i++)

常用一维搜索算法

无约束优化：不对定义域或值域做任何限制的情况下，求解目标函数的最小值。 这是因为实际应用中，许多情形被抽象为函数形式后均为凸函数，对于凸函数来说局部最小值点即为全局最小值点，因此只要能求得这类函数的一个最小值点，该点一定为全局最小值。 （直接法：又称数值方法，它只需计算目标函数驻点的函数数值，而不是求其倒数，如坐标轮换法，单纯型法等。 间接法：又称解析法，是应用数学极值理论的解析方法。首先计算出目标函数的一阶或一阶、二阶导数，然后根据梯度及海赛矩阵提供的信息，构造何种算法，从而间接地求出目标函数的最优解，如牛顿法、最速下降法共轭梯度法及变尺度法。） 在优化算法中保证整体收敛的重要方法就是线搜索法与信赖域法,这两种算法既相似又有所不同。根据不同的线搜索准则就延伸出不同的线搜索算法,譬如比较常见和经典的最速下降法,牛顿法,拟牛顿法以及共辄梯度法等。 一维搜索又称线性搜索(Line Search),就是指单变量函数的最优化,它是多变量函数最优化的基础,是求解无约束非线性规划问题的基本方法之一。 一维搜索技术既可独立的用于求解单变量最优化问题,同时又是求解多变量最优化问题常用的手段,虽然求解单变量最优化问题相对比较简单,但其中也贯穿了求解最优化问题的基本思想。由于一维搜索的使用频率较高,因此努力提高求解单变量问题算法的计算效率具有重要的实际意义。 在多变量函数的最优化中,迭代格式X k+1=X k+a k d k其关键就是构造搜索方向d k和步长因子a k 设Φ(a)=f(x k+ad k) 这样从凡出发,沿搜索方向d k,确定步长因子a k,使Φ(a)<Φ(0)的问题就是关于步长因子a的一维搜索问题。其主要结构可作如下概括:首先确定包含问题最优解的搜索区间，然后采用某种分割技术或插值方法缩小这个区间，进行搜索求解。 一维搜索通常分为精确的和不精确的两类。如果求得a k使目标函数沿方向d k达到 极小,即使得f (x k+a k d k)=min f (x k+ ad k) ( a>0) 则称这样的一维搜索为最优一维搜索,或精确一维搜索,a k叫最优步长因子; 如果选取a k使目标函数f得到可接受的下降量,即使得下降量f (x k)一f (x k+a k d k)>0是用 户可接受的,则称这样的一维搜索为近似一维搜索,或不精确一维搜索,或可接受一维 搜索。 由于在实际计算中,一般做不到精确的一维搜索,实际上也没有必要做到这一点,因为精确的

基于matlab的一维搜索

最优化理论与算法 基于matlab 的一维搜索——0.618试探法 2 m in ()21def f x x x =-- ， 初始区间11[,][1,1]a b =-,精度0.16L ≤ clc clear %设定初始值 L=0.16; k=1; b=1; a=-1; r=a+0.382*(b-a); u=a+0.618*(b-a); fr=fun(r); fu=fun(u); c=[]; while b-a>L if fr>fu a=r; b=b; r=u; u=a+0.618*(b-a); fr=fun(r); fu=fun(u); else a=a; b=u; u=r; r=a+0.382*(b-a); fr=fun(r); fu=fun(u); end k=k+1; c=[c,[a,b,r,u,fr,fu]]; end k jieguo=reshape(c,6,k)’ s=[a,b] l=b-a jieguo = -1.0000 1.0000 -0.2360 0.2360 -0.6526 -1.1246 -0.2360 1.0000 0.2360 0.5278 -1.1246 -0.9706 -0.2360 0.5278 0.0558 0.2360 -1.0496 -1.1246 0.0558 0.5278 0.2360 0.3475 -1.1246 -1.1060 0.0558 0.3475 0.1672 0.2360 -1.1113 -1.1246 0.1672 0.3475 0.2360 0.2787 -1.1246 -1.1234 0.1672 0.2787 0.2098 0.2360 -1.1218 -1.1246

第5章 一维搜索

第5章 一维搜索 §5.1 最优化算法的简单介绍 1．算法概念 在解非线性规划时，所用的计算方法，最常见的是迭代下降算法． 迭代：从一点) (k x 出发，按照某种规则A 求出后继点) 1(+k x ．用1+k 代替k ，重复以上 过程，产生点列}{) (k x 。 规则A 是在某个空间X 中点到点的映射，即对每一个X x k ∈) (，有点 X x A x k k ∈=+)() () 1(． 更一般地，把A 定义为点到集的映射，即对每个点X x k ∈) (，经A 作用，产生一个点 集X x A k ?)() (.任意选取一个点)() () 1(k k x A x ∈+，作为) (k x 的后继点． 定义1: 算法A 是定义在空间X 上的点到集映射，即对每一个点X x ∈，给定－个子集 X x A ?)(. 例1 考虑线性规划： 1 s.t. min 2 ≥x x 最优解1=x ．设计一个算法A 求出这个最优解． ???????

无约束最优化问题可以定义解集合为 }0)(|{=?=Ωx f x 约束最优化问题可以定义解集合为 }T -K 为|{点x x =Ω 2. 算法收敛问题 设Ω为解集合，X X A →:是一个算法，集合X Y ?.若以任一初点Y x ∈) 1(开始， 算法产生的序列其任一收敛子序列的极限属于Ω，则称算法映射A 在Y 上收敛． 收敛速率: 定义2: 设序列}{) (k γ 收敛于* γ，定义满足 ∞<=--≤+∞ →βγ γ γ γp k k k * ) (*) 1(lim 的非负数p 的上确界为序列}{) (k γ 的收敛级． 若序列的收敛级为p ，就称序列是p 级收敛的． 若1=p 且1<β，则称序列是以收敛比β 线性收敛的． 若1>p 或者1=p 且0=β，则称序列是超线性收敛的． 例2 序列{}10 ,<

禁忌搜索算法摘录

禁忌（Tabu Search）算法是一种亚启发式(meta-heuristic)随机搜索算法1，它从一个初始可行解出发，选择一系列的特定搜索方向（移动）作为试探，选择实现让特定的目标函数值变化最多的移动。为了避免陷入局部最优解，TS搜索中采用了一种灵活的“记忆”技术，对已经进行的优化过程进行记录和选择，指导下一步的搜索方向，这就是Tabu表的建立。 为了找到“全局最优解”，就不应该执着于某一个特定的区域。局部搜索的缺点就是太贪婪地对某一个局部区域以及其邻域搜索，导致一叶障目，不见泰山。禁忌搜索就是对于找到的一部分局部最优解，有意识地避开它（但不是完全隔绝），从而获得更多的搜索区间。兔子们找到了泰山，它们之中的一只就会留守在这里，其他的再去别的地方寻找。就这样，一大圈后，把找到的几个山峰一比较，珠穆朗玛峰脱颖而出。 当兔子们再寻找的时候，一般地会有意识地避开泰山，因为他们知道，这里已经找过，并且有一只兔子在那里看着了。这就是禁忌搜索 中“禁忌表（tabu list）”的含义。那只留在泰山的兔子一般不会就安家在那里了，它会在一定时间后重新回到找最高峰的大军，因为这个时候已经有了许多新的消息，泰山毕竟也有一个不错的高度，需要重新考虑，这个归队时间，在禁忌搜索里面叫做“禁忌长度（tabu length）”；如果在搜索的过程中，留守泰山的兔子还没有归队，但是找到的地方全是华北平原等比较低的地方，兔子们就不得不再次考虑选中泰山，也就是说，当一个没有兔子留守的地方优越性太突出，超过 了“best so far”的状态，就可以不顾及有没有兔子留守，都把这个地方考虑进来，这就叫“特赦准则（aspiration criterion）”。这三个概念是禁忌搜索和一般搜索准则最不同的地方，算法的优化也关键在这里。 伪码表达 procedure 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

黄金分割法 二次插值 牛顿 matlab 程序一维搜索方法比较

一维搜索方法应用比较 一、黄金分割法 （1）黄金分割法的起源 黄金分割在文艺复兴前后，经过阿拉伯人传入欧洲，受到了欧洲人的欢迎，他们称之为"金法"，17世纪欧洲的一位数学家，甚至称它为"各种算法中最可宝贵的算法"。这种算法在印度称之为"三率法"或"三数法则"，也就是我们现在常说的比例方法。 其实有关"黄金分割"，我国也有记载。虽然没有古希腊的早，但它是我国古代数学家独立创造的，后来传入了印度。经考证。欧洲的比例算法是源于我国而经过印度由阿拉伯传入欧洲的，而不是直接从古希腊传入的。 因为它在造型艺术中具有美学价值，在工艺美术和日用品的长宽设计中，采用这一比值能够引起人们的美感，在实际生活中的应用也非常广泛，建筑物中某些线段的比就科学采用了黄金分割，舞台上的报幕员并不是站在舞台的正中央，而是偏在台上一侧，以站在舞台长度的黄金分割点的位置最美观，声音传播的最好。就连植物界也有采用黄金分割的地方，如果从一棵嫩枝的顶端向下看，就会看到叶子是按照黄金分割的规律排列着的。在很多科学实验中，选取方案常用一种0.618法，即优选法，它可以使我们合理地安排较少的试验次数找到合理的西方和合适的工艺条件。正因为它在建筑、文艺、工农业生产和科学实验中有着广泛而重要的应用，所以人们才珍贵地称它为"黄金分割"。我国数学家华罗庚曾致力于推广优选法中的"0.618法"，把黄金分割应用于生活实际及科学应用中。 黄金分割〔Golden Section〕是一种数学上的比例关系。黄金分割具有严格的比例性、艺术性、和谐性，蕴藏着丰富的美学价值。应用时一般取0.618 ，就像圆周率在应用时取3.14一样。 由于公元前6世纪古希腊的毕达哥拉斯学派研究过正五边形和正十边形的作图，因此现代数学家们推断当时毕达哥拉斯学派已经触及甚至掌握了黄金分割。 公元前4世纪，古希腊数学家欧多克索斯第一个系统研究了这一问题，并建立起比例理论。 公元前300年前后欧几里得撰写《几何原本》时吸收了欧多克索斯的研究成果，进一步系统论述了黄金分割，成为最早的有关黄金分割的论著。 中世纪后，黄金分割被披上神秘的外衣，意大利数家帕乔利称中末比为神圣比例，并专门为此著书立说。德国天文学家开普勒称黄金分割为神圣分割。 到19世纪黄金分割这一名称才逐渐通行。黄金分割数有许多有趣的性质，人类对它的实际应用也很广泛。最著名的例子是优选学中的黄金分割法或0.618法，是由美国数学家基弗于1953年首先提出的，70年代在中国推广。

禁忌搜索算法

无时限单向配送车辆优化调度问题的禁忌搜索算法无时限单向配送车辆优化调度问题，是指在制定配送路线时不考虑客户对货物送到（或取走）时间要求的纯送货（或纯取货）车辆调度问题。 无时限单向配送车辆优化调度问题可以描述为：从某配送中心用多台配送车辆向多个客户送货，每个客户的位置和需求量一定，每台配送车辆的载重量一定，其一次配送的最大行驶距离一定，要求合理安排车辆配送路线，使目标函数得到优化，并满足一下条件：（1）每条配送路径上各客户的需求量之和不超过配送车辆的载重量； （2）每条配送路径的长度不超过配送车辆一次配送的最大行驶距离； （3）每个客户的需求必须满足，且只能由一台配送车辆送货。 一、禁忌搜索算法的原理 禁忌搜索算法是解决组合优化问题的一种优化方法。该算法是局部搜索算法的推广，其特点是采用禁忌技术，即用一个禁忌表记录下已经到达过的局部最优点，在下一次搜索中，利用禁忌表中的信息不再或有选择地搜索这些点，以此来挑出局部最优点。 在禁忌搜索算法中，首先按照随机方法产生一个初始解作为当前解，然后在当前解的领域中搜索若干个解，取其中的最优解作为新的当前解。为了避免陷入局部最优解，这种优化方法允许一定的下山操作（使解的质量变差）。另外，为了避免对已搜索过的局部最优解的重复，禁忌搜索算法使用禁忌表记录已搜索的局部最优解的历史信息，这可在一定程度上使搜索过程避开局部极值点，从而开辟新的搜索区域。 二、算法要素的设计 1.禁忌对象的确定 禁忌对象是指禁忌表中被禁的那些变化元素。由于解状态的变化可以分为解的简单变化、解向量分量的变化和目标值变化三种情况，则在确定禁忌对象时也有相对应的三种禁忌情况。 一般来说，对解的简单变化进行禁忌比另两种的受禁范围要小，因此可能早能造成计算时间的增加，但其优点是提供了较大的搜索范围。 根据配送车辆优化调度问题的特点，可采用对解的简单变化进行禁忌的方法。举例进行说明：当解从x变化到y时，y可能是局部最优解，为了避开局部最优解，禁忌y这一解再度出现，可采用如下禁忌规则：当y的领域中有比它更优的解时，选择更优的解；当y为其领域的局部最优解时，不再选y，而选比y稍差的解。 2.禁忌长度的确定 禁忌长度是指被禁对象不允许被选取的迭代步数，一般是给被禁忌对象x一个数l（称为禁忌长度），要求x在l步迭代内被禁，在禁忌表中采用Tabu(x)=l记忆，每迭代一步，该指标做运算Tabu(x)=l-1，直到Tabu(x)=0时解禁。关于禁忌长度l的选取，可归纳为以下几种情况。 （1）l为常数，可取l=10、（n为领域中邻居的总个数）。这种规则容易在算法中实现。 （2）。此时，l是可以变化的数，其变化的依据是被禁对象的目标函数值和领域的结构。、是确定的数，确定的常用方法是根据问题的规模N，限定变化区间；也可以用领域中邻居的个数n确定变化区间。 禁忌长度的选取同实际问题和算法设计者的经验有紧密联系，同时它也会影响计算的复杂性，过短会造成循环的出现，过长又会造成计算时间的增加。 3.候选集合的确定 候选集合由领域中的邻居组成，常规的方法是从领域中选择若干个目标函数值或评价值最佳的邻居。