【TSO】禁忌算法

Navigator

• Tabu Search
• • 算法流程
  • 算法终止准则
• Demo:求解以下函数的极小值
• • Code

Tabu Search

TS通过引入一个灵活的存储结构和禁忌准则避免迂回搜索，并通过藐视准则来赦免一些被禁忌的优良状态。简单的Tabu Search是在邻域搜索的基础上，通过设置禁忌表来禁忌一些已经历的操作，并利用藐视规则来奖励一些优良状态。

算法流程

1. 设置TS算法参数，随机产生初始解$x$，设置禁忌表为空。
2. 判断算法终止条件是否满足，如果满足则结束算法并给出最优结果，否则继续如下步骤
3. 利用当前解的$x$的邻域函数产生一些邻域解，并选出候选解
4. 判断候选解是否满足藐视规则，如果满足则进行最优状态替换，并设置禁忌对象
5. 判断候选解对应的各对象的禁忌属性，选择候选解集中非禁忌对象对应的最佳状态为新的当前解，同时用与之对应的禁忌对象替换最早进入禁忌对象元素
6. 转2

算法终止准则

常用终止准则如下：

1. 给定最大迭代步数
2. 设定某个对象的最大禁忌频率
3. 设定适配值的偏离幅度

Demo:求解以下函数的极小值

f ( x , y ) = sin ⁡ 2 ( x 2 + y 2 ) − 0.5 ( 1 + 0.001 ( x 2 + y 2 ) ) 2 − 0.5 , ∣ x i ∣ ≤ 10 f(x, y)=\frac{\sin^2(\sqrt{x^2+y^2})-0.5}{(1+0.001(x^2+y^2))^2}-0.5, |x_i|\leq 10 f(x,y)=(1+0.001(x2+y2))2sin2(x2+y2 ​)−0.5​−0.5,∣xi​∣≤10

Code

TS算法

function [cBest, iter]=TSOA(func, nvar, LB, UB, iter_max, Candidate_num, L, pm)% L is the length of Tabu table% nvar is the number of variables% LB, UB is the lower bound, upper bound, respectively% pm is probability of mutationif nargin==4StopL = 2000;Tabu_Length = 10;Candidate_num = 300;pm = 0.75;elseif nargin==5StopL = iter_max;Tabu_Length = 10;Candidate_num = 40;pm = 0.75;elseif nargin==6StopL = iter_max;Tabu_Length = 10;pm=0.75;elseif nargin==7StopL = iter_max;Tabu_Length=L;pm = 0.75;elseStopL = iter_max;Tabu_Length=L;endTabuList = zeros(Tabu_Length, 1+nvar);m_solution.idx = 1;m_solution.x = LB'+rand(1, nvar).*(UB-LB)';m_solution.fitness = func(m_solution.x);cBest = m_solution;for iter = 1:StopL% Setting of start pointif iter<0.95*StopLx0 = m_solution.x;elsex0 = cBest.x;endif iter<0.50*StopLCandidate = selectCandidate(x0, Candidate_num, nvar, iter, StopL, LB, UB, pm, 1);elseCandidate = selectCandidate(x0, Candidate_num, nvar, iter, StopL, LB, UB, pm, 2);endfor i=1:Candidate_numCandidate(i).fitness=func(Candidate(i).x);f(i)=Candidate(i).fitness;if iter == 1Candidate(i).bTabu=0;endend[a1, b1]=sort(f);for i=1:Candidate_numfor j=1:Tabu_Lengtha=norm(Candidate(i).x-TabuList(j, 1:end-1));b=abs(Candidate(i).fitness-TabuList(j, end));if a<=0.1 && b<=0.005Candidate(i).bTabu=1; % In Tabu Listbreak;elseCandidate(i).bTabu=0;endendendballtabu=1; % Judge if all of candidate solutions are in Tabu Listfor i=1:Candidate_numif Candidate(i).bTabu==0balltabu = 0;break;endendbestCandidate = Candidate(b1(1)); % the best candidate solutionif bestCandidate.fitness

function Candidate = selectCandidate(v, Candidate_num, nvar, iter, iter_max, LB, UB, pm, type)for i=1:Candidate_numCandidate(i).x=v;if type==1for j=1:nvarif rand>pmv1=v(j)-UB(j);v2=LB(j)-v(j);fg = rand*(1-iter/iter_max);if rand>0.5Candidate(i).x(j)=v(j)+v1*fg;elseCandidate(i).x(j)=v(j)+v2*fg;endelseCandidate(i).x(j)=v(j)+rand*(UB(j)-LB(j));end% Adjust valuesif Candidate(i).x(j)>=UB(j)Candidate(i).x(j)=LB(j)+(Candidate(i).x(j)-UB(j));elseif Candidate(i).x(j)<=LB(j)Candidate(i).x(j)=UB(j)-(LB(j)-Candidate(i).x(j));endendelseif type==2b = ceil(rand*nvar);Candidate(i).x(b)=LB(b)+rand*(UB(b)-LB(b));if Candidate(i).x(b)>=UB(b)Candidate(i).x(b)=LB(b)+(Candidate(i).x(b)-UB(b));elseif Candidate(i).x(b)<=LB(b)Candidate(i).x(b)=UB(b)-(LB(b)-Candidate(i).x(b));endendend
end

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！