(转载)基于混合粒子群算法的TSP问题求解(matlab实现)

1 理论基础

        标准粒子群算法通过追随个体极值和群体极值完成极值寻优，虽然操作简单，且能够快速收敛，但是随着迭代次数的不断增加，在种群收敛集中的同时，各粒子也越来越相似，可能在局部最优解周边无法跳出。混合粒子群算法摒弃了传统粒子群算法中的通过跟踪极值来更新粒子位置的方法，而是引入了遗传算法中的交叉和变异操作，通过粒子同个体极值和群体极值的交叉以及粒子自身变异的方式来搜索最优解。

2 案例背景

2.1 问题描述

        旅行商问题(traveling saleman problem,TSP)又译为旅行推销员问题、货郎担问题，简称为TSP,是最基本的路线问题，该问题寻求单一旅行者由起点出发，通过所有给定的需求点之后，最后再回到起点的最小路径成本，最早的旅行商问题的数学模型是由Dantzig(1959)等人提出。旅行商问题是车辆路线问题(VRP)的特例，已证明旅行商问题是NP难题。

2.2 算法流程

        基于混合粒子群算法的TSP算法流程如图15-1所示。
        其中，种群初始化模块初始化粒子群种群；适应度值计算模块计算粒子群个体的适应度值；更新粒子模块根据粒子适应度值更新个体最优粒子和群体最优粒子；个体最优交叉把个体和个体最优粒子进行交叉得到新粒子；群体最优交叉把个体和群体最优粒子进行交叉得到新粒子；粒子变异是指粒子自身变异得到新粒子。

2.3 算法实现

        1.个体编码
        粒子个体编码采用整数编码的方式，每个粒子表示历经的所有城市，比如当历经的城市数为10,个体编码为[9 4 2 1 3 7 6 10 8 5],表示城市遍历从9开始，经过4,2,1,3,…最终返回城市9,从而完成TSP遍历。
        2.适应度值
        粒子适应度值表示为遍历路径的长度，计算公式为
        3.交叉操作
        个体通过和个体极值和群体极值交叉来更新，交叉方法采用整数交叉法。首先选择两个交叉位置，然后把个体和个体极值或个体与群体极值进行交叉，假定随机选取的交叉位置为3和5,操作方法如下：
        对得到的新个体采用了保留优秀个体策略，只有当新粒子适应度值好于旧粒子时才更新粒子。
        4.变异操作
        变异方法采用个体内部两位互换方法，首先随机选择变异位置pos1和pos2,然后把两个变异位置互换，假设选择的变异位置为2和4,变异操作如下所示：
        对得到的新个体采用了保留优秀个体策略，只有当新粒子适应度值好于旧粒子时才更新粒子。

3 MATLAB程序实现

        根据混合粒子群算法原理，在MATLAB中编程实现基于混合粒子群的TSP搜索算法。  

3.1 适应度函数

        适应度函数计算个体适应度值，个体适应度值为路径总长度，代码如下： 
function indiFit=fitness(x,cityCoor,cityDist)
%% 该函数用于计算个体适应度值
%x           input     个体
%cityCoor    input     城市坐标
%cityDist    input     城市距离
%indiFit     output    个体适应度值 

m=size(x,1);
n=size(cityCoor,1);
indiFit=zeros(m,1);
for i=1:m
    for j=1:n-1
        indiFit(i)=indiFit(i)+cityDist(x(i,j),x(i,j+1));
    end
    indiFit(i)=indiFit(i)+cityDist(x(i,1),x(i,n));
end

3.2主函数

%% 该文件演示基于TSP-PSO算法
clc;clear

%% 下载数据
data=load('eil51.txt');
cityCoor=[data(:,2) data(:,3)];%城市坐标矩阵

figure
plot(cityCoor(:,1),cityCoor(:,2),'ms','LineWidth',2,'MarkerEdgeColor','k','MarkerFaceColor','g')
legend('城市位置')
ylim([4 78])
title('城市分布图','fontsize',12)
xlabel('km','fontsize',12)
ylabel('km','fontsize',12)
%ylim([min(cityCoor(:,2))-1 max(cityCoor(:,2))+1])

grid on

%% 计算城市间距离
n=size(cityCoor,1);            %城市数目
cityDist=zeros(n,n);           %城市距离矩阵
for i=1:n
    for j=1:n
        if i~=j
            cityDist(i,j)=((cityCoor(i,1)-cityCoor(j,1))^2+...
                (cityCoor(i,2)-cityCoor(j,2))^2)^0.5;
        end
        cityDist(j,i)=cityDist(i,j);
    end
end
nMax=200;                      %进化次数
indiNumber=1000;               %个体数目
individual=zeros(indiNumber,n);
%^初始化粒子位置
for i=1:indiNumber
    individual(i,:)=randperm(n);    
end

%% 计算种群适应度
indiFit=fitness(individual,cityCoor,cityDist);
[value,index]=min(indiFit);
tourPbest=individual;                              %当前个体最优
tourGbest=individual(index,:) ;                    %当前全局最优
recordPbest=inf*ones(1,indiNumber);                %个体最优记录
recordGbest=indiFit(index);                        %群体最优记录
xnew1=individual;

%% 循环寻找最优路径
L_best=zeros(1,nMax);
for N=1:nMax
    N
    %计算适应度值
    indiFit=fitness(individual,cityCoor,cityDist);
    
    %更新当前最优和历史最优
    for i=1:indiNumber
        if indiFit(i)<recordPbest(i)
            recordPbest(i)=indiFit(i);
            tourPbest(i,:)=individual(i,:);
        end
        if indiFit(i)<recordGbest
            recordGbest=indiFit(i);
            tourGbest=individual(i,:);
        end
    end
    
    [value,index]=min(recordPbest);
    recordGbest(N)=recordPbest(index);
    
    %% 交叉操作
    for i=1:indiNumber
       % 与个体最优进行交叉
        c1=unidrnd(n-1); %产生交叉位
        c2=unidrnd(n-1); %产生交叉位
        while c1==c2
            c1=round(rand*(n-2))+1;
            c2=round(rand*(n-2))+1;
        end
        chb1=min(c1,c2);
        chb2=max(c1,c2);
        cros=tourPbest(i,chb1:chb2);
        ncros=size(cros,2);      
        %删除与交叉区域相同元素
        for j=1:ncros
            for k=1:n
                if xnew1(i,k)==cros(j)
                    xnew1(i,k)=0;
                    for t=1:n-k
                        temp=xnew1(i,k+t-1);
                        xnew1(i,k+t-1)=xnew1(i,k+t);
                        xnew1(i,k+t)=temp;
                    end
                end
            end
        end
        %插入交叉区域
        xnew1(i,n-ncros+1:n)=cros;
        %新路径长度变短则接受
        dist=0;
        for j=1:n-1
            dist=dist+cityDist(xnew1(i,j),xnew1(i,j+1));
        end
        dist=dist+cityDist(xnew1(i,1),xnew1(i,n));
        if indiFit(i)>dist
            individual(i,:)=xnew1(i,:);
        end
        
        % 与全体最优进行交叉
        c1=round(rand*(n-2))+1;  %产生交叉位
        c2=round(rand*(n-2))+1;  %产生交叉位
        while c1==c2
            c1=round(rand*(n-2))+1;
            c2=round(rand*(n-2))+1;
        end
        chb1=min(c1,c2);
        chb2=max(c1,c2);
        cros=tourGbest(chb1:chb2); 
        ncros=size(cros,2);      
        %删除与交叉区域相同元素
        for j=1:ncros
            for k=1:n
                if xnew1(i,k)==cros(j)
                    xnew1(i,k)=0;
                    for t=1:n-k
                        temp=xnew1(i,k+t-1);
                        xnew1(i,k+t-1)=xnew1(i,k+t);
                        xnew1(i,k+t)=temp;
                    end
                end
            end
        end
        %插入交叉区域
        xnew1(i,n-ncros+1:n)=cros;
        %新路径长度变短则接受
        dist=0;
        for j=1:n-1
            dist=dist+cityDist(xnew1(i,j),xnew1(i,j+1));
        end
        dist=dist+cityDist(xnew1(i,1),xnew1(i,n));
        if indiFit(i)>dist
            individual(i,:)=xnew1(i,:);
        end
        
       %% 变异操作
        c1=round(rand*(n-1))+1;   %产生变异位
        c2=round(rand*(n-1))+1;   %产生变异位
        while c1==c2
            c1=round(rand*(n-2))+1;
            c2=round(rand*(n-2))+1;
        end
        temp=xnew1(i,c1);
        xnew1(i,c1)=xnew1(i,c2);
        xnew1(i,c2)=temp;
        
        %新路径长度变短则接受
        dist=0;
        for j=1:n-1
            dist=dist+cityDist(xnew1(i,j),xnew1(i,j+1));
        end
        dist=dist+cityDist(xnew1(i,1),xnew1(i,n));
        if indiFit(i)>dist
            individual(i,:)=xnew1(i,:);
        end
    end

    [value,index]=min(indiFit);
    L_best(N)=indiFit(index);
    tourGbest=individual(index,:); 
    
end

%% 结果作图
figure
plot(L_best)
title('算法训练过程')
xlabel('迭代次数')
ylabel('适应度值')
grid on


figure
hold on
plot([cityCoor(tourGbest(1),1),cityCoor(tourGbest(n),1)],[cityCoor(tourGbest(1),2),...
    cityCoor(tourGbest(n),2)],'ms-','LineWidth',2,'MarkerEdgeColor','k','MarkerFaceColor','g')
hold on
for i=2:n
    plot([cityCoor(tourGbest(i-1),1),cityCoor(tourGbest(i),1)],[cityCoor(tourGbest(i-1),2),...
        cityCoor(tourGbest(i),2)],'ms-','LineWidth',2,'MarkerEdgeColor','k','MarkerFaceColor','g')
    hold on
end
legend('规划路径')
scatter(cityCoor(:,1),cityCoor(:,2));
title('规划路径','fontsize',10)
xlabel('km','fontsize',10)
ylabel('km','fontsize',10)

grid on
ylim([4 80])

4仿真结果

        采用混合粒子群算法规划TSP路径，各城市的初始位置如图15-2所示。混合粒子群算法的进化次数为100,种群规模为100,算法进化过程中最优粒子适应度值变化和规划出的最优路径如图15-3和图15-4所示。 从图15-3与图15-4可以看到，混合粒子群算法能够较快找到连接各个城市的最优
路径。

         对于更大规模的TSP问题，同样可以采用粒子群算法进行求解，运行结果如下：

 

 

 

 

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.mfbz.cn/a/26303.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

2023/5/29总结

2023/5/29总结

abstract修饰符 抽象类就是当类和类之间有相同特征时&#xff0c;将这些共同的特征提取出来&#xff0c;形成的就是抽象类。 抽象类的特点&#xff1a; 抽象类和抽象方法必须使用abstract 关键字修饰&#xff1a;publicabstract class 类名 / public abstract void eat();抽象…
阅读更多...
测评补单操作在美客多店铺及产品优化中的决定性角色：深度解读

测评补单操作在美客多店铺及产品优化中的决定性角色：深度解读

许多经营美客多平台的商家有一种观念&#xff0c;他们认为美客多平台的规则与亚马逊有所区别。在美客多上&#xff0c;店铺比产品更重要&#xff0c;而且平台的竞争相对较小。因此&#xff0c;他们认为在美客多平台进行补单操作是不必要的。 然而&#xff0c;是否真的如此呢&a…
阅读更多...
FM实现F4帮助系列三：弹出框多筛选条件的搜索帮助（根据搜索帮助筛选字段）...

FM实现F4帮助系列三：弹出框多筛选条件的搜索帮助（根据搜索帮助筛选字段）...

函数&#xff1a;F4IF_GET_SHLP_DESCR F4IF_START_VALUE_REQUEST 效果图&#xff1a; 本例子代码&#xff1a; 找到需要的帮助: *& Report ZLM_TEST_045 REPORT zlm_test_045. TABLES makt. DATA: BEGIN OF str_f4, matnr TYPE matnr, maktx TYPE maktx, END OF str_f4.…
阅读更多...
react antd Modal里Form设置值不起作用

react antd Modal里Form设置值不起作用

问题描述&#xff1a; react antd Modal里Form设置值不起作用&#xff0c;即使用form的api。比如&#xff1a;编辑时带出原有的值。 造成的原因&#xff1a;一般设置值都是在声明周期里设置&#xff0c;比如&#xff1a;componentDidMounted里设置&#xff0c;hook则在useEff…
阅读更多...
国际植物命名数据库（International Plant Names Index）

国际植物命名数据库（International Plant Names Index）

功能介绍 https://www.ipni.org/ 是国际植物命名数据库&#xff08;International Plant Names Index&#xff09;的官方网站。国际植物命名数据库是一个全球性的植物命名和分类资源&#xff0c;旨在提供植物命名信息的权威来源。以下是该网站的一些特点和功能&#xff1a; 植…
阅读更多...
Web Scoket简述

Web Scoket简述

Web Socket 简介 初次接触 Web Socket 的人&#xff0c;我们已经有了 HTTP 协议&#xff0c;为什么还需要另一个协议&#xff1f;它能带来什么好处&#xff1f; 因为 HTTP 协议有一个缺陷&#xff1a;通信只能由客户端发起。http基于请求响应实现。 &#xff08;准确来说HTTP…
阅读更多...
使用Python进行接口性能测试：从入门到高级

使用Python进行接口性能测试：从入门到高级

前言&#xff1a; 在今天的网络世界中&#xff0c;接口性能测试越来越重要。良好的接口性能可以确保我们的应用程序可以在各种网络条件下&#xff0c;保持流畅、稳定和高效。Python&#xff0c;作为一种广泛使用的编程语言&#xff0c;为进行接口性能测试提供了强大而灵活的工…
阅读更多...
尚硅谷大数据hadoop教程_mapReduce

尚硅谷大数据hadoop教程_mapReduce

p67 课程介绍 p68概述 p69 mapreduce核心思想 p70 wordcount源码 序列化类型 mapReduce三类进程 p71 编程规范 用户编写的程序分成三个部分&#xff1a;Mapper、Reducer和Driver。 P72 wordcount需求案例分析 p 73 -78 案例环境准备 &#xff08;1&#xff09;创建maven…
阅读更多...
基于Html5的在线资料库的设计与实现(asp.NET,SQLServer)

基于Html5的在线资料库的设计与实现(asp.NET,SQLServer)

在线资料库系统采用.NET开发平台进行开发&#xff0c;开发工具采用Microsoft Visual Studio 2010集成开发环境&#xff0c;后台编程语言采用C#编程语言来进行编程开发&#xff0c;数据库我们采用当下流行的SQL Server 2008数据库管理系统来存放平台中的数据信息&#xff0c;整个…
阅读更多...
Nginx 之 Tomcat 负载均衡、动静分离

Nginx 之 Tomcat 负载均衡、动静分离

一.详细安装及操作实例&#xff08;Nginx 七层代理&#xff09; 首先至少准备三台服务器 Nginx 服务器&#xff1a;192.168.247.131:80 Tomcat服务器1&#xff1a;192.168.247.133:80 Tomcat服务器2&#xff1a;192.168.247.134:8080 192.168.247.134:80811.部署Nginx 负载均…
阅读更多...
windows下编译roadrunner和作为laravel服务器实践

windows下编译roadrunner和作为laravel服务器实践

roadrunner源码地址&#xff1a;https://gitee.com/mirrors/RoadRunner?_fromgitee_search windows下编译roadrunner源码获得rr.exe可执行文件 将rr.exe拷贝到laravel目录下 .rr.yaml配置文件内容&#xff1a; version: 3 server: command: "php vendor/spiral/road…
阅读更多...
【Jmeter】生成html格式接口自动化测试报告

【Jmeter】生成html格式接口自动化测试报告

jmeter自带执行结果查看的插件&#xff0c;但是需要在jmeter工具中才能查看&#xff0c;如果要向领导提交测试结果&#xff0c;不够方便直观。 笔者刚做了这方面的尝试&#xff0c;总结出来分享给大家。 这里需要用到ant来执行测试用例并生成HTML格式测试报告。 一、ant下载安…
阅读更多...
vue methods 互相调用的方法

vue methods 互相调用的方法

methods是一个内置的函数&#xff0c;主要用于两个组件之间的数据传递&#xff0c;也就是调用方法。下面给大家介绍一个在 vue中互相调用的方法&#xff0c;在使用过程中可以参考一下。 methods实现了两个组件之间数据的传递&#xff0c;我们先来看一下 Methods是如何实现数据传…
阅读更多...
Kafka

Kafka

Kafka 概述 基于Scala语言&#xff0c;是一个分布式&#xff0c;分区的&#xff0c;多副本的&#xff0c;多订阅者的消息队列系统。 优势 可靠性&#xff1a;分布式的&#xff0c;分区&#xff0c;复制和容错的。可扩展性&#xff1a;kafka消息传递系统轻松缩放&#xff0c…
阅读更多...
ROS：订阅者Subscriber的编程实现（C++）

ROS：订阅者Subscriber的编程实现（C++）

目录 一、话题模型二、创建功能包三、创建Subscriber代码四、编译代码五、运行 一、话题模型 图中&#xff0c;我们使用ROS Master管理节点。 有两个主要节点&#xff1a; Publisher&#xff0c;名为Turtle Velocity&#xff08;即海龟的速度&#xff09; Subscriber&#xff0…
阅读更多...
Docker安装kafka可视化管理工具 - Kafka Manager

Docker安装kafka可视化管理工具 - Kafka Manager

说明&#xff1a;此处是在前面使用Docker安装kafka的基础之上&#xff0c;再来使用Docker安装kafka-manager 第一步&#xff1a;使用下述命令从Docker Hub查找镜像&#xff0c;此处我们要选择的是sheepkiller所构建的kafka-manager镜像 docker search kafka-manager 第二步&a…
阅读更多...
aigc分享

aigc分享

AIGC技术分享 AIGC概述 AIGC的概念、应用场景和发展历程https://36kr.com/p/2135547607286144 ppt https://36kr.com/p/2243237713604482 机器学习基础 机器学习的基本概念、分类和常用算法&#xff0c;如线性回归、决策树、支持向量机、神经网络等。 深度学习基础 深度学…
阅读更多...
设计模式之~组合模式

设计模式之~组合模式

组合模式&#xff1a; 将对象组合成树形结构以表示‘部分-整体’的层次结构。组合模式使得用户对单个对象和组合对象的使用具有一致性。 结构图&#xff1a; 实例&#xff1a; 透明方式&#xff1a; leaf中也有add和remove叫做透明方式&#xff0c;在component中声明所有用来管…
阅读更多...
煤矿井下定位设备，实现特殊环境下人员安全管理

煤矿井下定位设备，实现特殊环境下人员安全管理

煤矿、金属矿山等地下作业场所的安全管理工作要求高、难度大&#xff0c;矿用人员定位系统通过实时定位等功能&#xff0c;可以帮助企业随时掌握作业人员的位置安全&#xff0c;提高生产和安全管理效率&#xff0c;并可在紧急情况时迅速采取措施&#xff0c;减少事故损失&#…
阅读更多...
基于OA的采购系统和专业的招标采购管理系统区别

基于OA的采购系统和专业的招标采购管理系统区别

当前采购信息化百家争鸣&#xff0c;既有初级版的审批和记录电子化&#xff0c;也有中级版的业务全流程电子化&#xff0c;还有升级版的数智化创新形式&#xff08;如电商平台、智能评标、供应商风险评估、专家行为画像、大数据统计分析等&#xff09;。 近年来&#xff0c;招标…
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站