首页 > 编程语言 >禁忌搜索(Tabu Search or Taboo Search,TS)算法解决3DTSP问题

禁忌搜索(Tabu Search or Taboo Search,TS)算法解决3DTSP问题

时间:2024-07-26 15:00:05浏览次数:17  
标签:候选 Search S0 禁忌 Tabu TS zeros Location 当前

 禁忌搜索算法的基本思想:给定一个当前解(初始解)和一种邻域,然后在当前解的邻域中确定若干候选解;若最佳候选解对应的目标值优于“best so far”状态,则忽视其禁忌特性,用它替代当前解和“best so far”状态,并将相应的对象加入禁忌表,同时修改禁忌表中各对象的任期;若不存在上述候选解,则在候选解中选择非禁忌的最佳状态为新的当前解,而无视它与当前解的对比关系,同时将相应的对象加入禁忌表,并修改禁忌表中各对象的任期。如此重复上述迭代搜索过程,直至满足停止准则。

clc;
clear all;
file_path = '..\chapter2\data.csv'; %读取文件
Location = csvread(file_path, 1, 1);
N=size(Location,1);                    %TSP问题的规模
D=zeros(N);                     %任意两个加工区域的距离间隔矩阵
%%%%%%%%%%%%%%%%%%%%%求任意两个城市距离间隔矩阵%%%%%%%%%%%%%%%%%%%%%
for i=1:N
    for j=1:N
        D(i,j)=((Location(i,1)-Location(j,1))^2+(Location(i,2)-Location(j,2))^2+(Location(i,3)-Location(j,3)))^0.5;
    end
end
Tabu=zeros(N);                      %禁忌表
TabuL=round((N*(N-1)/2)^0.5);       %禁忌长度
Ca=400;                             %候选集的个数(全部邻域解个数)
CaNum=zeros(Ca,N);                  %候选解集合
%S0=[22	78	122	101	49	131	80	21	100	97	103	99	96	37	12	93	31	102	98	115	41	44	19	20	109	107	111	112	64	35	46	42	75	113	16	71	74	72	69	70	73	68	67	63	29	76	120	50	9	105	62	130	126	124	128	129	125	127	123	84	34	33	66	60	116	59	57	53	54	58	56	52	13	94	25	121	117	26	11	132	85	87	91	88	89	92	86	90	28	15	36	38	17	48	134	39	2	114	61	135	82	95	10	65	77	1	5	3	8	7	4	6	55	79	24	51	104	133	14	23	18	27	106	81	110	108	30	118	45	47	40	136	83	32	119	43];  %ACO算法的结果设置为初始解
S0=randperm(N);               %随机产生初始解
bestsofar=S0;                       %当前最佳解
BestL=Inf;                          %当前最佳解距离
figure(1);
p=1;
Gmax=2000;                          %最大迭代次数   
%%%%%%%%%%%%%%%%%%%%%%%%%%%禁忌搜索循环%%%%%%%%%%%%%%%%%%%%%%%%%%
while p<Gmax
    ALong(p)=func1(D,S0);            %当前解适配值
    %%%%%%%%%%%%%%%%%%%%%%%%%%%交换城市%%%%%%%%%%%%%%%%%%%%%%%%%%
    i=1;
    A=zeros(Ca,2);                   %解中交换的城市矩阵
    %%%%%%%%%%%%%%%%%求邻域解中交换的城市矩阵%%%%%%%%%%%%%%%%%%%%%
    while i<=Ca
        M=N*rand(1,2);
        M=ceil(M);         
        if M(1)~=M(2)
            A(i,1)=max(M(1),M(2));
            A(i,2)=min(M(1),M(2));
            if i==1
                isa=0;
            else
                for j=1:i-1
                    if A(i,1)==A(j,1) && A(i,2)==A(j,2)
                        isa=1;
                        break;
                    else
                        isa=0;
                    end
                end
            end
            if ~isa
                i=i+1;
            else
            end
        else
        end
    end
    %%%%%%%%%%%%%%%%%%%%%%%%%产生邻域解%%%%%%%%%%%%%%%%%%%%%%%%%%
    %%%%%%%%%%%%%%%%保留前BestCaNum个最好候选解%%%%%%%%%%%%%%%%%%%
    BestCaNum=Ca/2;
    BestCa=Inf*ones(BestCaNum,4);
    F=zeros(1,Ca);
    for i=1:Ca
        CaNum(i,:)=S0;
        CaNum(i,[A(i,2),A(i,1)])=S0([A(i,1),A(i,2)]);
        F(i)=func1(D,CaNum(i,:));
        if i<=BestCaNum
            BestCa(i,2)=F(i);
            BestCa(i,1)=i;
            BestCa(i,3)=S0(A(i,1));
            BestCa(i,4)=S0(A(i,2));
        else
            for j=1:BestCaNum
                if F(i)<BestCa(j,2)
                    BestCa(j,2)=F(i);
                    BestCa(j,1)=i;
                    BestCa(j,3)=S0(A(i,1));
                    BestCa(j,4)=S0(A(i,2));
                    break;
                end
            end
        end
    end
    [JL,Index]=sort(BestCa(:,2));
    SBest=BestCa(Index,:);
    BestCa=SBest;
    %%%%%%%%%%%%%%%%%%%%%%%%藐视准则%%%%%%%%%%%%%%%%%%%%%%%%%%%
    if BestCa(1,2)<BestL
        BestL=BestCa(1,2);
        S0=CaNum(BestCa(1,1),:);
        bestsofar=S0;
        for m=1:N
            for n=1:N
                if Tabu(m,n)~=0
                    Tabu(m,n)=Tabu(m,n)-1;    
                    %更新禁忌表
                end
            end
        end
        Tabu(BestCa(1,3),BestCa(1,4))=TabuL;
        %更新禁忌表
    else
        for  i=1:BestCaNum
            if  Tabu(BestCa(i,3),BestCa(i,4))==0
                S0=CaNum(BestCa(i,1),:);
                for m=1:N
                    for n=1:N
                        if Tabu(m,n)~=0
                            Tabu(m,n)=Tabu(m,n)-1;
                            %更新禁忌表
                        end
                    end
                end
                Tabu(BestCa(i,3),BestCa(i,4))=TabuL;
                %更新禁忌表
                break;
            end
        end
    end
    ArrBestL(p)=BestL;
    p=p+1;   
    for i=1:N-1
        plot3([Location(bestsofar(i),1),Location(bestsofar(i+1),1)],...
            [Location(bestsofar(i),2),Location(bestsofar(i+1),2)], ...
            [Location(bestsofar(i),3),Location(bestsofar(i+1),3)],'bo-');
        hold on;
    end
    plot3([Location(bestsofar(N),1),Location(bestsofar(1),1)],...
        [Location(bestsofar(N),2),Location(bestsofar(1),2)], ...
        [Location(bestsofar(N),3),Location(bestsofar(1),3)],'ro-');
    title(['优化最短距离:',num2str(BestL)]);
    hold off;
    pause(0.005);
end
BestShortcut=bestsofar;            %最佳路线
theMinDistance=BestL;              %最佳路线长度
figure(2);
plot(ArrBestL); 
xlabel('迭代次数')
ylabel('目标函数值')
title('适应度进化曲线')

%%%%%%%%%%%%%%%%%%%%%%%%%适配值函数%%%%%%%%%%%%%%%%%%%%%%%%%%
function F=func1(D,s)
DistanV=0;
n=size(s,2);
for i=1:(n-1)
    DistanV=DistanV+D(s(i),s(i+1));
end
DistanV=DistanV+D(s(n),s(1));
F=DistanV;

标签:候选,Search,S0,禁忌,Tabu,TS,zeros,Location,当前
From: https://blog.csdn.net/weixin_47616070/article/details/140636956

相关文章

  • Python,运行Yolo项目,报错AttributeError: ‘ImageDraw‘ object has no attribute ‘te
    Python3.9问题描述:其他电脑已经运行成功的Python,YOLO代码到我电脑上运行报错Traceback(mostrecentcalllast): File"C:\Users\Administrator\Desktop\20240725\识别项目\predict.py",line122,in<module>  frame=np.array(yolo.detect_image(frame)) Fil......
  • ElasticSearch第1讲(4万字详解 Linux下安装、原生调用、API调用超全总结、Painless、IK
    ElasticSearch官方文档:https://www.elastic.co/guide/en/elasticsearch/reference/current/getting-started.html非官方中文文档:https://learnku.com/docs/elasticsearch73/7.3极简概括:基于ApacheLucene构建开源的分布式搜索引擎。解决问题:MySQLlike中文全文搜索不走索引......
  • “Elasticsearch精英进阶:从零到精通的安装,从Kibana到Java API,全面掌握CRUD与DSL查询及
    目录引言1.初识elasticsearch1.1.认识和安装 1.1.1.安装elasticsearch 1.1.2.安装Kibana 1.2.倒排索引1.2.1.正向索引1.2.2.倒排索引1.2.3.正向和倒排1.3.基础概念1.3.1.文档和字段1.3.2.索引和映射1.3.3.mysql与elasticsearch1.4.1.安装IK分词器1.4.2.使......
  • 【Python】成功解决:`FileExistsError: [Errno 17] File exists: ‘xxx’`
    【Python】成功解决:FileExistsError:[Errno17]Fileexists:‘xxx’在Python编程中,处理文件和目录是常见的任务之一。然而,当我们尝试执行某些文件操作,如创建新文件或目录时,如果目标文件或目录已经存在,就可能会遇到FileExistsError异常。这个错误通常伴随着消息[Errno1......
  • 详解视频中的I帧、P帧、B帧、GOP、IDR 和PTS, DTS
    一.视频传输原理视频是利用人眼视觉暂留的原理,通过播放一系列的图片,使人眼产生运动的感觉。单纯传输视频画面,视频量非常大,对现有的网络和存储来说是不可接受的。为了能够使视频便于传输和存储,人们发现视频有大量重复的信息,如果将重复信息在发送端去掉,在接收端恢复出来,这样就......
  • OpenAI SearchGPT:终于开始测试搜索能力
    OpenAI官推发文表示,SearchGPT 正在测试中,需要访问这里加入白名单,主要特点如下:快速响应:快速生成答案实时信息:从互联网获取最新信息,并提供来源链接。对话式搜索:以聊天的方式提出问题。可视化结果:以图表、视频、图像提供响应。网友 @kifleswing 指出,SearchGPT的......
  • [ABC363G] Dynamic Scheduling 与 P4511 [CTSC2015] 日程管理
    思路:对于插入操作,设插入\(\{t,p\}\):若当前\(1\simt\)有空位,那么就放进去。否则,\(1\simt\)是被塞满了的:首先容易想到的是找到\(1\simt\)中贡献最小的那个工作,若贡献比\(p\)还小,可以与之替换掉。但是假了,考虑这样一种情况:在\(1\simt\)外有一个更小的......
  • 单机模式下ElasticSearch8(ES8设置账号密码访问)
     重置密码报错:ERROR:Failedtoresetpasswordforthe[elastic]user 修改配置文件/config/elasticsearch.yml修改或添加discovery.type:single-nodexpack.security.enabled:truexpack.security.http.ssl.enabled:falsexpack.security.enrollment.enabled:......
  • 【摘译+整理】System.IO.Ports.SerialPort使用注意
    远古的一篇博客,内容散落于博文和评论https://sparxeng.com/blog/software/must-use-net-system-io-ports-serialportC#和.NETFramework提供了一种快速的应用程序开发,非常适合需要随着硬件设计的发展跟踪不断变化的需求的早期开发。在大多数方面都很理想。但.NET附带的Sy......
  • PYTHON 代码执行错误 - 冻结 importlib._bootstrap>(1165)_find_and_load()?
    在MACOS10.15(CATALINA)上执行此PYTHON代码时出现以下错误。我正在使用IDLEShell编写PYTHON3.11。Python3.11.4(v3.11.4:d2340ef257,Jun 62023,19:15:51)[Clang13.0.0(clang-1300.0.29.30)]ondarwinType"help","copyright","credits"o......