1 局部领域搜索
又称爬山启发式算法,从当前的节点开始,和周围的邻居节点的值进行比较。如果当前节点是最大的,那么返回当前节点,作为最大值(即山峰最高点);反之就用最高的邻居节点替换当前节点,从而实现向山峰的高处攀爬的目的。它是禁忌搜索的基础,TS算法是在其上改进而来。
1.1 优点:
容易理解,容易实现,具有较强的通用性;
局部开发能力强,收敛速度很快。
1.2 缺点:
全局开发能力弱,只能搜索到局部最优解;
搜索结果完全依赖于初始解和邻域的映射关系。
通过针对爬山法的分析,提出了TS搜索算法:
改进1:接受劣解。
改进2:引入禁忌表。
改进3:引入长期表和中期表。
2 TS算法的特点:
2.1 基本思想——避免在搜索过程中的循环
2.2 只进不退的原则,通过禁忌表实现
2.3 不以局部最优作为停止准则
2.4 邻域选优的规则模拟了人类的记忆功能
TS算法构成要素:
(1)编码方式
将不相同的n件物品分为m组,可以用的编码:
a、带分隔符的顺序编码
以自然数1~n分别代表n件物品,n个数加上 m-1个分割符号混编在一起,随机排列。 如:1-3-4-0-2-6-7-5-0-8-9
b、自然数编码
编码的每一位分别代表一件物品,而每一位的值代表该物品所在的分组。
如:1-2-1-1-2-2-2-3-3
(2)初始解的获取
可以随机给出初始解,也可以事先使用其他启发式等算法给出一个较好的初始解。
(3)移动邻域
移动是从当前解产生新解的途径,例如上述问题中用移动s产生新解s(x)。 从当前解可以进行的所有移动构成邻域,也可以理解为从当前解经过“一步”可以到达的区域。
(4)禁忌表
禁忌表的作用:防止搜索出现循环
(1)记录前若干步走过的点、方向或目标值,禁止返回
(2)表是动态更新的
(3)表的长度称为Tabu-Size
禁忌表的主要指标(两项指标)
禁忌对象:禁忌表中被禁的那些变化元素
禁忌长度:禁忌的步数
禁忌对象(三种变化)
以状态本身或者状态的变化作为禁忌对象
以状态分量以及分量的变化作为禁忌对象
采用类似的等高线做法,以目标值变化作为禁忌对象
禁忌长度:可以是一个固定的常数(T=c),也可以是动态变化的,可按照某种规则或公式在区间内变化。
禁忌长度过短,一旦陷入局部最优点,出现循环无法跳出;
禁忌长度过长,候选解全部被禁忌,造成计算时间较大,也可能造成计算无法继续下去。
(5)渴望水平函数
A(x,s)一般为历史上曾经达到的最好目标值,若有C(s(x))<A(x,s)则S(x)是不受T表限制。即使s(x)∈T,仍可取 x=s(x)。A(x,s)称为渴望水平函数。
(6)停止准则
(1)给定最大迭代步数(最常用 )
(2)设定某个对象的最大禁忌频率。
(3)设定适配值的偏离阈值。
clc; clear; close all; %% Problem Definition model = CreateModel(); % Create TSP Model CostFunction=@(tour) TourLength(tour, model); % Cost Function ActionList=CreatePermActionList(model.n); % Action List nAction=numel(ActionList); % Number of Actions %% Tabu Search Parameters MaxIt=50; % Maximum Number of Iterations TL=round(0.5*nAction); % Tabu Length %% Initialization % Create Empty Individual Structure empty_individual.Position=[]; empty_individual.Cost=[]; % Create Initial Solution sol=empty_individual; sol.Position=randperm(model.n); sol.Cost=CostFunction(sol.Position); % Initialize Best Solution Ever Found BestSol=sol; % Array to Hold Best Costs BestCost=zeros(MaxIt,1); % Initialize Action Tabu Counters TC=zeros(nAction,1); %% Tabu Search Main Loop for it=1:MaxIt bestnewsol.Cost=inf; % Apply Actions for i=1:nAction if TC(i)==0 newsol.Position=DoAction(sol.Position,ActionList{i}); newsol.Cost=CostFunction(newsol.Position); newsol.ActionIndex=i; if newsol.Cost<=bestnewsol.Cost bestnewsol=newsol; end end end % Update Current Solution sol=bestnewsol; % Update Tabu List for i=1:nAction if i==bestnewsol.ActionIndex TC(i)=TL; % Add To Tabu List else TC(i)=max(TC(i)-1,0); % Reduce Tabu Counter end end % Update Best Solution Ever Found if sol.Cost<=BestSol.Cost BestSol=sol; end function PlotSolution(sol,model) xmin=model.xmin; xmax=model.xmax; ymin=model.ymin; ymax=model.ymax; tour=sol.Position; tour=[tour tour(1)]; plot(model.x(tour),model.y(tour),'k-o',... 'MarkerSize',10,... 'MarkerFaceColor','y',... 'LineWidth',1.5); xlabel('x'); ylabel('y'); axis equal; grid on; alpha = 0.1; dx = xmax - xmin; xmin = floor((xmin - alpha*dx)/10)*10; xmax = ceil((xmax + alpha*dx)/10)*10; xlim([xmin xmax]); dy = ymax - ymin; ymin = floor((ymin - alpha*dy)/10)*10; ymax = ceil((ymax + alpha*dy)/10)*10; ylim([ymin ymax]); function model=CreateModel() x=[82 91 12 92 63 9 28 55 96 97 15 98 96 49 80 12 80 55]; y=[14 42 92 80 96 66 3 85 94 68 76 75 39 66 17 78 80 45]; n=numel(x); d=zeros(n,n); for i=1:n-1 for j=i+1:n d(i,j)=sqrt((x(i)-x(j))^2+(y(i)-y(j))^2); d(j,i)=d(i,j); end end xmin=0; xmax=100; ymin=0; ymax=100; model.n=n; model.x=x; model.y=y; model.d=d; model.xmin=xmin; model.xmax=xmax; model.ymin=ymin;
版本:2014a
完整代码或代写加QQ1564658423