请选择 进入手机版 | 继续访问电脑版

Hello Mat

 找回密码
 立即注册
查看: 5898|回复: 2

禁忌搜索算法的TSP问题求解

[复制链接]

1278

主题

1504

帖子

90

金钱

管理员

Rank: 9Rank: 9Rank: 9

积分
22549
发表于 2018-5-12 10:03:05 | 显示全部楼层 |阅读模式

禁忌搜索算法的TSP问题求解:
  1. clc,clear,close all
  2. warning off
  3. x=[82 91 12 92 63 9 28 55 96 97 15 98 96 49 80 12 80 55];
  4. y=[14 42 92 80 96 66 3 85 94 68 76 75 39 66 17 78 80 45];
  5. [Position, BestCost]= Tabu_Search_TSP(x,y,50);

  6. figure(1);
  7. hold on
  8. plot(x,y,'o')
  9. for i=1:length(x)
  10.     if i<length(x)
  11.         plot( [x(Position(i)),x(Position(i+1))], [y(Position(i)),y(Position(i+1))],'-','linewidth',2 )
  12.     else
  13.         plot( [x(Position(i)),x(Position(1))], [y(Position(i)),y(Position(1))],'-','linewidth',2 )
  14.     end
  15. end
  16. hold off
复制代码
函数如下:
  1. function [Position, BestCost]= Tabu_Search_TSP(x,y,MaxIt)
  2. % x=[82 91 12 92 63 9 28 55 96 97 15 98 96 49 80 12 80 55];
  3. % y=[14 42 92 80 96 66 3 85 94 68 76 75 39 66 17 78 80 45];

  4. model = CreateModel_ysw(x, y);                  % Create TSP Model
  5. CostFunction=@(tour) TourLength(tour, model);   % Cost Function
  6. ActionList=CreatePermActionList(model.n);       % Action List
  7. nAction=numel(ActionList);                      % Number of Actions
  8. %% Tabu Search Parameters
  9. % MaxIt=50;                   % Maximum Number of Iterations
  10. TL=round(0.5*nAction);      % Tabu Length
  11. %% Initialization
  12. % Create Empty Individual Structure
  13. empty_individual.Position=[];
  14. empty_individual.Cost=[];
  15. % Create Initial Solution
  16. sol=empty_individual;
  17. sol.Position=randperm(model.n);
  18. sol.Cost=CostFunction(sol.Position);
  19. % Initialize Best Solution Ever Found
  20. BestSol=sol;
  21. % Array to Hold Best Costs
  22. BestCost=zeros(MaxIt,1);
  23. % Initialize Action Tabu Counters
  24. TC=zeros(nAction,1);
  25. %% Tabu Search Main Loop
  26. for it=1:MaxIt
  27.     bestnewsol.Cost=inf;
  28.     % Apply Actions
  29.     for i=1:nAction
  30.         if TC(i)==0
  31.             newsol.Position=DoAction(sol.Position,ActionList{i});
  32.             newsol.Cost=CostFunction(newsol.Position);
  33.             newsol.ActionIndex=i;

  34.             if newsol.Cost<=bestnewsol.Cost
  35.                 bestnewsol=newsol;
  36.             end
  37.         end
  38.     end
  39.     % Update Current Solution
  40.     sol=bestnewsol;
  41.     % Update Tabu List
  42.     for i=1:nAction
  43.         if i==bestnewsol.ActionIndex
  44.             TC(i)=TL;               % Add To Tabu List
  45.         else
  46.             TC(i)=max(TC(i)-1,0);   % Reduce Tabu Counter
  47.         end
  48.     end
  49.     % Update Best Solution Ever Found
  50.     if sol.Cost<=BestSol.Cost
  51.         BestSol=sol;
  52.     end
  53.     % Save Best Cost Ever Found
  54.     BestCost(it)=BestSol.Cost;
  55.     % Show Iteration Information
  56. %     disp(['Iteration ' num2str(it) ': Best Cost = ' num2str(BestCost(it))]);
  57.    
  58. %     % Plot Best Solution
  59. %     figure(1);
  60. %     PlotSolution(BestSol, model);
  61. %     pause(0.01);
  62.     % If Global Minimum is Reached
  63.     if BestCost(it)==0
  64.         break;
  65.     end
  66. end
  67. % BestCost=BestCost(1:it);
  68. Position = BestSol.Position;
  69. BestCost = BestSol.Cost;

  70. end

  71. function model=CreateModel_ysw(x,y)
  72. %     x=[82 91 12 92 63 9 28 55 96 97 15 98 96 49 80 12 80 55];
  73. %     y=[14 42 92 80 96 66 3 85 94 68 76 75 39 66 17 78 80 45];
  74.     n=numel(x);
  75.     d=zeros(n,n);
  76.     for i=1:n-1
  77.         for j=i+1:n
  78.             d(i,j)=sqrt((x(i)-x(j))^2+(y(i)-y(j))^2);
  79.             d(j,i)=d(i,j);
  80.         end
  81.     end
  82.     xmin=0;
  83.     xmax=100;
  84.     ymin=0;
  85.     ymax=100;
  86.     model.n=n;
  87.     model.x=x;
  88.     model.y=y;
  89.     model.d=d;
  90.     model.xmin=xmin;
  91.     model.xmax=xmax;
  92.     model.ymin=ymin;
  93.     model.ymax=ymax;
  94. end

  95. function L=TourLength(tour,model)
  96.     n=numel(tour);
  97.     tour=[tour tour(1)];
  98.     L=0;
  99.     for k=1:n
  100.         i=tour(k);
  101.         j=tour(k+1);
  102.         L=L+model.d(i,j);
  103.     end
  104. end

  105. function ActionList=CreatePermActionList(n)
  106.     nSwap=n*(n-1)/2;
  107.     nReversion=n*(n-1)/2;
  108.     nInsertion=n^2;
  109.     nAction=nSwap+nReversion+nInsertion;
  110.     ActionList=cell(nAction,1);
  111.     c=0;
  112.     % Add SWAP
  113.     for i=1:n-1
  114.         for j=i+1:n
  115.             c=c+1;
  116.             ActionList{c}=[1 i j];
  117.         end
  118.     end
  119.     % Add REVERSION
  120.     for i=1:n-1
  121.         for j=i+1:n
  122.             if abs(i-j)>2
  123.                 c=c+1;
  124.                 ActionList{c}=[2 i j];
  125.             end
  126.         end
  127.     end
  128.     % Add Insertion
  129.     for i=1:n
  130.         for j=1:n
  131.             if abs(i-j)>1
  132.                 c=c+1;
  133.                 ActionList{c}=[3 i j];
  134.             end
  135.         end
  136.     end
  137.     ActionList=ActionList(1:c);
  138. end

  139. function q=DoAction(p,a)
  140.     switch a(1)
  141.         case 1
  142.             % Swap
  143.             q=DoSwap(p,a(2),a(3));
  144.         case 2
  145.             % Reversion
  146.             q=DoReversion(p,a(2),a(3));
  147.         case 3
  148.             % Insertion
  149.             q=DoInsertion(p,a(2),a(3));     
  150.     end
  151. end

  152. function q=DoSwap(p,i1,i2)
  153.     q=p;
  154.     q([i1 i2])=p([i2 i1]);
  155. end

  156. function q=DoReversion(p,i1,i2)
  157.     q=p;
  158.     if i1<i2
  159.         q(i1:i2)=p(i2:-1:i1);
  160.     else
  161.         q(i1:-1:i2)=p(i2:i1);
  162.     end
  163. end

  164. function q=DoInsertion(p,i1,i2)
  165.     if i1<i2
  166.         q=p([1:i1-1 i1+1:i2 i1 i2+1:end]);
  167.     else
  168.         q=p([1:i2 i1 i2+1:i1-1 i1+1:end]);
  169.     end
  170. end
复制代码








算法QQ  3283892722
群智能算法链接http://halcom.cn/forum.php?mod=forumdisplay&fid=73
回复

使用道具 举报

0

主题

23

帖子

0

金钱

注册会员

Rank: 2

积分
92
发表于 2023-8-16 09:49:17 | 显示全部楼层
谢谢楼主分享
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

Python|Opencv|MATLAB|Halcom.cn ( 蜀ICP备16027072号 )

GMT+8, 2024-3-29 00:16 , Processed in 0.220203 second(s), 24 queries .

Powered by Discuz! X3.4

Copyright © 2001-2021, Tencent Cloud.

快速回复 返回顶部 返回列表