禁忌搜索算法

<> <>算法思想

标记已经解得的局部最优解或求解过程,并在进一步的迭代中避开这些局部最优解或求解过程。局部搜索的缺点在于,太过于对某一局部区域以及其邻域的搜索,导致一叶障目。为了找到全局最优解,禁忌搜索就是对于找到的一部分局部最优解,有意识地避开它,从而或得更多的搜索区域

<> <>算法过程
 
*
(1)给定一个禁忌表(Tabu List)H=null,并选定一个初始解X_now.

*

(2)如果满足停止规则,则停止计算,输出结果;否则,在X_now的领域中选出满足不受禁忌的候选集N(X_now).在N(X_now)中选择一个评价值最贱的解X_next,X_next:=X_now;更新历史记录H,
重复步骤(2).

* 1
* 2
<> <>对搜索性能有影响的因素

禁忌长度

控制其他变量,单就禁忌长度的选择而言,禁忌长度越短,机器内存占用越少,解禁范围更大(搜索范围上限越大),但很容易造成搜索循环(实际去搜索的范围却很小),过早陷入局部最优。禁忌长度过长又会导致计算时间过长。

特赦规则

通俗定义:对于在禁忌的对象,如果出现以下情况,不论现在对象的禁忌长度如何,均设为0
(1)基于评价值的规则,若出现一个解的目标值好于前面任何一个最佳候选解,可特赦;
(2)基于最小错误的规则,若所有对象都被禁忌,特赦一个评价值最小的解;
(3)基于影响力的规则,可以特赦对目标值影响大的对象。

候选集

候选集的大小,过大增加计算内存和计算时间,过小过早陷入局部最优。候选集的选择一般由邻域中的邻居组成,可以选择所有邻居,也可以选择表现较好的邻居,还可以随机选择几个邻居。

评价函数

评价函数分为直接评价函数和间接评价函数。
直接评价函数:上述例子,均直接使用目标值作为评价函数。
间接评价函数:反映目标函数特性的函数(会比目标函数的计算更为简便,用以减少计算时间等)。

终止规则

禁忌算法是一个启发式算法,我们不可能让搜索过程无穷进行,所以一些直观的终止规则就出现了
(1)确定步数终止,无法保证解的效果,应记录当前最优解;
(2)频率控制原则,当某一个解、目标值或元素序列的频率超过一个给定值时,终止计算;
(3)目标控制原则,如果在一个给定步数内,当前最优值没有变化,可终止计算。
clear clc %% 用importdata这个函数来读取文件 c208=importdata('c208.txt'); cap=700; %车辆负荷
maxIter=300; %最大迭代次数 E=c208(1,5); %仓库时间窗开始时间 L=c208(1,6); %仓库时间窗结束时间
vertexs=c208(:,2:3); %所有点的坐标x和y customer=vertexs(2:end,:); %顾客坐标
cusnum=size(customer,1); %顾客数 vecnum=cusnum; %车辆数 demands=c208(2:end,4); %需求量
a=c208(2:end,5); %顾客时间窗开始时间[a[i],b[i]] b=c208(2:end,6); %顾客时间窗结束时间[a[i],b[i]]
s=c208(2:end,7); %客户点的服务时间 h=pdist(vertexs); dist=squareform(h);
%距离矩阵,满足三角关系,暂用距离表示花费c[i][j]=dist[i][j] vehicles_customer=cell(vecnum,1);
%每辆车所经过的顾客 %% CW法构造VRPTW初始解 %输出init_vc 每辆车所经过的顾客 %输出init_TD 所有车行驶的总距离
%输出init_vl 每辆车的装载量 %输出violate_INTW 判断是否违背时间窗约束,0代表不违背,1代表违背
[init_vc,init_TD,init_vl,violate_INTW] =
init_TW(c208,L,demands,a,b,s,dist,cap); %%
初始化各个车辆配送路线,每个安装场地由一辆车配送,有d2需求的安装场地在前面加上加工车间用0表示 % [ init_vc ] = init_route(
vehicles_customer ); % init_TD=travel_distance(init_vc,dist); S=init_vc; %当前解
eS=minLen(S); %当前解各路径中所经过的最少数目的顾客数 initNV=size(S,1); %所用车辆数目 Sbest=S; %全局最优解 %
f=initNV*cusnum+eS; % fBest=initNV*cusnum+eS; f=initNV*cusnum+init_TD;
fBest=initNV*cusnum+init_TD; TbList=zeros(cusnum,initNV); %禁忌表 TbLength=20;
%禁忌长度 NS=neighborhood(S,L,cusnum,demands,a,b,s,dist,cap); %S的邻域
[subNS]=subNeighbor(TbList,NS,fBest); % non-tabu or allowed by aspiration %%
Tabu Search iter=0; count=0; while iter<maxIter if ~isempty(subNS)
[minValue,minIndex]=min(subNS(:,5)); %从邻域中找出车辆总行驶距离最小的行序号
value=subNS(minIndex,:); %提取最小行序号的这一行数组 i=value(1); j=value(2); k=value(3);
p=value(4); fS=value(5); [S_copy]=insert(S,i,j,k,p); if fS<fBest fBest=fS;
Sbest=S_copy; S=S_copy;
NS=neighborhood(S_copy,L,cusnum,demands,a,b,s,dist,cap);
[subNS]=subNeighbor(TbList,NS,fBest); %更新禁忌表 for l=1:cusnum for h=1:initNV if
TbList(l,h)~=0 TbList(l,h)=TbList(l,h)-1; end end end if TbList(i,j)==0
TbList(i,j)=TbLength; else TbList(i,j)=0; end else if TbList(i,j)==0 S=S_copy;
NS=neighborhood(S,L,cusnum,demands,a,b,s,dist,cap);
[subNS]=subNeighbor(TbList,NS,fBest); % 更新禁忌表 for l=1:cusnum for h=1:initNV if
TbList(l,h)~=0 TbList(l,h)=TbList(l,h)-1; end end end TbList(i,j)=TbLength; end
end else break end iter=iter+1; end Sbest=deal_vehicles_customer(Sbest);
bestNV=size(Sbest,1); bestTD=travel_distance(Sbest,dist); DEL=Judge_Del(Sbest);
% 检查最优解中是否存在元素丢失的情况 % 计算每辆车配送路线上在各个点开始服务的时间,还计算返回仓库时间 bsv=
begin_s_v(Sbest,a,s,dist ); [ violate_TW ] = Judge_TW( Sbest,bsv,b,L ); %
判断是否违背时间窗约束,0代表不违背,1代表违背

完整代码添加QQ1575304183

技术
今日推荐
阅读数 20
阅读数 13
阅读数 10
阅读数 9
友情链接
码工具
Toolsou
API参考文档
云服务器优惠
阿里云优惠券
腾讯云优惠券
华为云优惠券
站点信息
问题反馈
邮箱:ixiaoyang8@qq.com
QQ群:766591547
关注微信