首页 / 算法 / 求解旅行商问题的离散人工萤火虫算法-matlab代码

求解旅行商问题的离散人工萤火虫算法-matlab代码

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了求解旅行商问题的离散人工萤火虫算法-matlab代码，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含8402字，纯文字阅读大概需要13分钟。

内容图文

求解旅行商问题的离散人工萤火虫算法-matlab代码

一、萤火虫算法

旅行商问题（TSP）是运筹学以及最优化理论等领域中的一个经典问题，它广泛应用于各行各业，如电路板钻孔、货物配送路线和车间调度安排等问题均可转化为 TSP，因此 TSP 的求解成为国内外学者研究的点.对于规模比较小的 TSP，可以应用分支定界法、贪婪法和割平面法等精确算法求解，但对于规模较大的 TSP，应用以上精确算法求解时计算量太大，在目前的条件下很难实现，而智能优化算法的出现为其求解开辟了新的途径.

萤火虫算法（Firefly Algorithm）是一种启发式算法，灵感来自于萤火虫闪烁的行为。萤火虫的闪光，其主要目的是作为一个信号系统，以吸引其他的萤火虫。剑桥大学的Xin-She Yang教授提出了萤火虫算法，其假设为：萤火虫不分性别，这样一个萤火虫将会吸引到所有其他的萤火虫;吸引力与它们的亮度成正比，对于任何两个萤火虫，不那么明亮的萤火虫被吸引，因此移动到更亮的一个，然而，亮度又随着其距离的增加而减少;如果没有比一个给定的萤火虫更亮的萤火虫，它会随机移动。亮度应与目标函数联系起来。萤火虫算法是以自然为灵感的启发式优化算法。

自然界中的萤火虫会发出荧光信号，从生物学角度，其作用有时是为了吸引异性关注，求得交配机会，繁衍后代；有时是为了捕食；有时是因处于危险境地而将其作为警戒信号.人工萤火虫算法中仅考虑萤火虫利用发出荧光信号在一定范围内吸引同伴，最终使大多数萤火虫聚集在一个或者多个位置上，即实现位置优化.萤火虫吸引同伴主要取决于荧光亮度和吸引度.其中，荧光亮度取决于自身所在位置的目标值，目标值越佳，亮度越高；吸引度和亮度紧密相关，越亮的萤火虫也拥有越高的吸引度，可以在一定范围内吸引亮度比其弱的萤火虫向自己移动 . 另外，在人工萤火虫算法中，考虑到萤火中发光的物理特性，亮度和吸引度都与萤火虫之间的距离成反比，即随着距离的增大，荧光亮度和吸引度逐渐减小.萤火虫在移动过程中主要遵循如下原则：

①萤火虫移动方向由荧光亮度决定，总是向比自身荧光亮度高的萤火虫移动；

②萤火虫移动距离由吸引度决定 . 文中对萤火虫荧光亮度和吸引度进行如下定义。

求解旅行商问题的离散人工萤火虫算法-matlab代码 - 文章图片

求解旅行商问题的离散人工萤火虫算法-matlab代码 - 文章图片

求解旅行商问题的离散人工萤火虫算法-matlab代码 - 文章图片

二、TSP离散问题的求解

求解连续变量的优化问题时，萤火虫间的空间距离可采用欧式距离进行计算；当求解 TSP 时，解向量为离散变量，其空间距离不能按欧式距离公式进行计算。定义萤火虫间的空间距离为

求解旅行商问题的离散人工萤火虫算法-matlab代码 - 文章图片

其中基本交换序的定义为

求解旅行商问题的离散人工萤火虫算法-matlab代码 - 文章图片

在求解连续变量的优化问题时，萤火虫移动距离可根据吸引度进行计算，但当求解 TSP 时，萤火虫的移动距离不应是连续变量，位置更新为

求解旅行商问题的离散人工萤火虫算法-matlab代码 - 文章图片

基于变邻域搜索（VNS）算法的思想，定义了离散变量的扰动机制.在搜索过程中采用多种邻域结构形式进行搜索，系统地改变其邻域，从而拓展搜索范围，增强算法跳出局部最优的能力.

求解旅行商问题的离散人工萤火虫算法-matlab代码 - 文章图片

三、应用离散萤火虫算法求解 TSP 的步骤

求解旅行商问题的离散人工萤火虫算法-matlab代码 - 文章图片

四、代码

clc
clear
close all
%% 输入城市坐标初始化参数
X=[114 50 99 30 60 26 29 7 53 40 102 3 32 12 100];
Y=[228 70 146 171 150 262 220 29 246 275 175 48 52 227 99];
city=[X',Y'];
N=size(X,2);
n=50;%萤火虫数目
gamma=0.1;%光强吸收系数
T_max=100;%最大迭代次数
K=50;%混沌迭代次数
ew=0.2;%选取精英比例
%% 初始化种群
for i=1:n
popus.order(i,:)=randperm(N);%初始每只
POP=[popus.order(i,:),popus.order(i,1)];%每只萤火虫数值
dis=0;
for j=1:N%距离求和的倒数（距离越短越好）
dis=dis+sqrt((X(POP(j+1))-X(POP(j)))^2+(Y(POP(j+1))-Y(POP(j)))^2);
end
popus.P(i)=1/dis; %计算目标函数
end
Mp=mean(popus.P(:));%平均种群距离和的倒数
L(1)=max(popus.P);%记录函数最优值
popus.max_Y=max(popus.P)./popus.P;%荧光强度j=2 k=2
popus.pg=max(popus.P);%最优目标值，作为比较标准，更新迭代
PO=find(popus.P==max(popus.P));%最优种群位置
popus.Popus=popus.order(PO,:);%取出最优种群
%% 算法迭代过程
for im=1:T_max
sprintf('迭代次数%d',im)
popus.YY=popus.max_Y;
r=ones(n,n)*0;
AA=ones(n,n)*0;
beta=ones(n,n)*0;
fd=0;
oe=(1:N);%初始预存矩阵
for i=1:n%不同种群
for j=1:n%种群中的数值
if i~=j%判断每个种群与另一个种群之间的空间距离（A 为两只萤火虫解向量基本交换序中的交换子个数）
S=[];
x=popus.order(i,:);
y=popus.order(j,:);
LL=nchoosek(oe,2);
A=0;
for k=1:size(LL,1)
ec=LL(k,:);
if sum(abs(x(LL(k,:))==y([ec(2),ec(1)])))==2%先判断两个位置是否相等，相等就直接交换
x(LL(k,:))=y(LL(k,:));
A=A+1;
S=[S;LL(k,:)];
end
end
for k=1:N
if x(k)~=y(k)%不相等的话就将x中对应y位置的城市移过来，然后将原位置处城市移过去
xt=find(x==y(k));
x(x==y(k))=x(k);
x(k)=y(k);
A=A+1;
S=[S;[k,xt]];
for kk=1:size(LL,1)
ec=LL(k,:);
if sum(abs(x(LL(kk,:))==y([ec(2),ec(1)])))==2%判断两个位置是否相等，相等就直接交换
x(LL(kk,:))=y(LL(kk,:));
A=A+1;
S=[S;LL(kk,:)];
end
end
end
end
SS{i,j}=S;%种群的基本交换序
AA(i,j)=A;%A 为两只萤火虫解向量基本交换序中的交换子个数
r(i,j)=A/N;
end
end
end
choose=ones(1,n);
for i=1:n
x=popus.order(i,:);
for j=1:n
popus.YY(j)=popus.max_Y(i)*exp(-gamma*r(i,j));%萤火虫荧光强度
end
p=popus.YY/sum(popus.YY);%最大荧光强度
P=p;
for m=1:size(p,2)%基于轮盘赌选择移向荧光亮度更高的其他个体，确定移动方向
P(m)=sum(p(1:m));
end
num=rand(1);
for m=1:size(P,2)
if num<P(m)
choose(i)=m;
break
end
end
end
for i=1:n
for j=1:n
if i~=j
beta(i,j)=randi([0,AA(i,j)]);%确定移动距离
end
end
end
for i=1:n%根据移动距离和移动方向，对各个萤火虫进行更新
x=popus.order(i,:);
Choose=choose(i);
Sx=SS{i,Choose};
Num1=beta(i,Choose);
OD=zeros(1,size(Sx,1));
OD(randperm(size(Sx,1),Num1))=1;
Sx(OD==0,:)=[];
for j=1:size(Sx,1)
aa=Sx(j,:);
x([aa(1),aa(2)])=x([aa(2),aa(1)]);
end
popus.order(i,:)=x;
end
for i=1:n
POP=[popus.order(i,:),popus.order(i,1)];
dis=0;
for j=1:N
dis=dis+sqrt((X(POP(j+1))-X(POP(j)))^2+(Y(POP(j+1))-Y(POP(j)))^2);
end
popus.P(i)=1/dis; %计算目标函数
end

d_order=zeros(n,1);
f_t=sort(popus.P,'ascend');%将适应度按升序排列
for k=1:n
x=find(popus.P==f_t(k));%升序排列的个体序号
d_order(k)=x(1);
end
NN=ew*n;%选取部分精英进行混沌优化迭代
N_order=d_order(n-NN+1:n);
for i=1:NN
x=popus.order(N_order(i),:);
xs=x;
xr=x;
xs=[xs,xs(1)];
dis=0;
for k=1:N
dis=dis+sqrt((X(xs(k+1))-X(xs(k)))^2+(Y(xs(k+1))-Y(xs(k)))^2);
end
Dis=1/dis;
for j=1:K
x=xr;
numm=randi([1,N],1,2);
x(numm)=x([numm(2),numm(1)]);
xe=x;
x=[x,x(1)];
dis=0;
for k=1:N
dis=dis+sqrt((X(x(k+1))-X(x(k)))^2+(Y(x(k+1))-Y(x(k)))^2);
end
Diss=1/dis;
if Diss>Dis
Dis=Diss;
xr=xe;
end
end
popus.order(N_order(i),:)=xr;
end

M_order=d_order(1:NN);%将目标值最差的部分种群重新随机赋值
for i=1:NN
popus.order(M_order(i),:)=randperm(N);
end

for i=1:n
POP=[popus.order(i,:),popus.order(i,1)];
dis=0;
for j=1:N
dis=dis+sqrt((X(POP(j+1))-X(POP(j)))^2+(Y(POP(j+1))-Y(POP(j)))^2);
end
popus.P(i)=1/dis; %计算目标函数
end
Mpe=mean(popus.P(:));

if max(popus.P)>popus.pg
popus.pg=max(popus.P);
popus.max_Y=max(popus.P)./popus.P;%荧光强度
PO=find(popus.P==max(popus.P));
popus.Popus=popus.order(PO(1),:);
L(im+1)=max(popus.P);
Mp(im+1)=Mpe;
else
L(im+1)=L(im);
Mp(im+1)=Mpe;
end
close all
plot(X,Y,'.k','LineWidth',5);%标明城市
hold on
ex=[popus.Popus,popus.Popus(1)];
plot(X(ex),Y(ex),'r');%标明城市
pause(0.1)
end
figure(2)
L2=L;Mp2=Mp;
plot((1:size(L2,2)),1./L2,'r',(1:size(L2,2)),1./Mp2,'g');%迭代过程
xlabel('迭代次数')
ylabel('路径长度')
legend('最优路径长度','种群平均路径长度')

五、运行结果

求解旅行商问题的离散人工萤火虫算法-matlab代码 - 文章图片

求解旅行商问题的离散人工萤火虫算法-matlab代码 - 文章图片

内容总结

以上是互联网集市为您收集整理的求解旅行商问题的离散人工萤火虫算法-matlab代码全部内容，希望文章能够帮你解决求解旅行商问题的离散人工萤火虫算法-matlab代码所遇到的程序开发问题。如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/605755.html

来源：【匿名】

【上一篇】【Python算法作业】解一元二次方程【下一篇】浅谈php实现映射的两种方法（链表和二叉树）

更多 ►

【求解旅行商问题的离散人工萤火虫算法-matlab代码】教程文章相关的互联网学习教程文章

各种排序算法整理（附带习题及代码）【代码】【图】

模板部分（想背的就背一下吧，但是不建议……毕竟排序用sort函数就行了，这些排序的算法只是为了锻炼你的思维逻辑能力罢了）：1.选择排序#include<cstdio>#define N 100000+100int a[N],n;int main(){scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&a[i]);for(int i=1;i<n;i++){int k=i;for(int j=i+1;j<=n;j++)if(a[j]<a[k]) k=j;if(k!=i){int p=a[k];a[k]=a[i];a[i]=p;}}for(int i=1;i<n;i++)printf("%d ",a[i]);printf("%d",...

编程算法 - 最长公共子序列(LCS) 代码(C)【图】

最长公共子序列(LCS) 代码(C)本文地址: http://blog.csdn.net/caroline_wendy题目: 给定两个字符串s,t, 求出这两个字符串最长的公共子序列的长度. 字符串的子序列并一定要连续, 能够包含间隔.即最长公共子序列问题(LCS, Longest Common Subsequence)使用动态规划, 假设字符相等, 两个字符串就依次递增一位, 一直到字符串的结尾.代码:/** main.cpp** Created on: 2014.7.17* Author: spike*//*eclipse cdt, gcc 4.8.1*/#inclu...

算法之美_源代码发布（6）【图】

本文辑录了《算法之美——隐匿在数据结构背后的语言》（电子工业出版社2016年出版）一书第7章之代码（P184~P230）。全文目录、“45个算法”目录、“22个经典问题目录”，以及有奖捉虫活动详情请见如下链接：http://blog.csdn.net/baimafujinji/article/details/50484348附录中的经典笔试、面试问题参考答案请见：http://blog.csdn.net/baimafujinji/article/details/50484683In general，我不太喜欢翻开一本书（技术书），里面密密...

python-Kmeans\Kmeans++算法理解及代码实现【代码】【图】

一、环境：Python 3.7.4Pycharm Community 2019.3二、问题：对六个样本点[1, 5], [2, 4], [4, 1], [5, 0], [7, 6], [6, 7]进行K-means聚类。三、理论推导　此处依照我个人理解所写，错误之处欢迎指出 K-means核心操作为：聚类中心选取—分类—调整聚类中心—再次分类并调整聚类中心直到调整幅度小于阈值或程序运行轮数大于阈值选取聚类中心：　　聚类中心的选取可以选择随机选取、人工选取。K-means+...

星力九代命中算法源代码特殊用户处理点控调整【代码】【图】

难度命中算法制excel表格 package com.miracle9.game.algorithm; import com.miracle9.game.algorithm.FishServerSuanfa.FISH_TYPE;import java.util.Objects; import java.util.Random;import org.apache.log4j.Level; import org.apache.log4j.Logger; import org.apache.log4j.xml.DOMConfigurator;public class DieFishSuanfa {public Logger log = Logger.getLogger(DieFishSuanfa.class);private static float afloat14 =...

LeetCode算法题-C#代码实现-栈（一）【代码】

20. Valid Parentheses有效的括号解题思路将括号比较后者后，不同的入栈，相同的出栈，最后字符串遍历结束后栈为空则匹配成功。publicbool IsValid(string s) {//声明字典，括号匹配键值对Dictionary<char, char> dict = new Dictionary<char, char>();dict.Add(‘)‘, ‘(‘);dict.Add(‘]‘, ‘[‘);dict.Add(‘}‘, ‘{‘);Stack<char> stack = new Stack<char>();//遍历字符s，直到遍历s所有字符结束循环for (int i = 0; i < s...

模式匹配之sift--- sift图像特征提取与匹配算法代码

sift，The Scale Invariant Feature Transform ，尺度不变特征变换，是检测图像中具有唯一性、对图像平移、旋转、缩放、甚至仿射变换（如从不同角度拍摄图片）保持不变性的图像局部特征的一种有效方法。可以容易地应用到图像匹配的应用中，如目标检测与识别，或者计算图像间的几何变换。该算法由David. Lowe在2004年发表，并在好像是2007年申请了专利。网络已有几个版本的实现请大家查看sift创始人的代码：David Lowe‘s SIFT code...

编程算法 - 丑数代码(C)【图】

丑数代码(C)本文地址: http://blog.csdn.net/caroline_wendy题目: 我们把只包含因子2, 3 和 5的数称作丑数. 求按从小到大的顺序的第5个丑数.可以设置一个数组包含所需要的丑数, 依次比较乘以2, 乘以3, 乘以5的最小的数, 最后返回结果.如第5个丑数是5, 如1, 2, 3, 4(2*2), 5均是丑数.代码:/** main.cpp** Created on: 2014.6.12* Author: Spike*//*eclipse cdt, gcc 4.8.1*/#include <stdio.h> #include <stdlib.h> #include...

常见算法简介及python代码【代码】

1.冒泡排序def bubblesort(nums):for i in range(len(nums)-1):for j in range(len(nums)-i-1):if nums[j]>nums[j+1]:nums[j],nums[j+1] =nums[j+1],nums[j]return nums nums = [23,43,54,12,44,56,65] re = bubblesort(nums) print(re)简单解析：从list首端逐个对数据进行两两比较，大的往后放，外层循环一次，会在list尾端得到一个最大值，类似于冒泡行为，每次循环的最大值都固定不动，循环到最后就会出现一组从小到大的数据。...

deep learning 自编码算法详细理解与代码实现（超详细）【代码】【图】

在有监督学习中，训练样本是有类别标签的。现在假设我们只有一个没有带类别标签的训练样本集合，其中。自编码神经网络是一种无监督学习算法，它使用了反向传播算法，并让目标值等于输入值，比如。下图是一个自编码神经网络的示例。通过训练，我们使输出接近于输入。当我们为自编码神经网络加入某些限制，比如限定隐藏神经元的数量，我们就可以从输入数据中发现一些有趣的结构。举例来说，假设某个自编码神经网络的输入是...

C言语次序查找算法及代码【代码】

次序査找是一种复杂的査找算法，其完成办法是从序列的肇端元素开端，逐一将序列中的元素与所要查找的元素停止比拟，假如序列中有元素与所要查找的元素相等，那么査找胜利，假如査找到序列的最初一个元素都不存在一个元素与所要査找的元素值相等，那么标明査找掉败。接下来经过一段代码来理解次序査找的详细运用。 #include <stdio.h> #include <stdlib.h> #include <memory.h> int ordersearch(int a[], int n, int des){ int i;...

提升代码质量，从数据结构与算法说起【图】

数据结构与算法的应用在计算机编程领域非常广泛，甚至可以说无处不在，比如图像视频处理、数据压缩、数据库、游戏开发、操作系统、编译器、搜索引擎、AR、VR、人工智能、区块链等等领域，都是以数据结构与算法为基石。因为其知识点太多、难度略高，很多人学习到中途就放弃了，但是数据结构与算法对一个程序员来说真的是必不可少的内功，不管是面试还是提升自我，都跨不过数据结构与算法这道坎，数据结构与算法不仅可以帮助我们站在...

编程算法 - 篱笆修理(Fence Repair) 代码(C)【图】

篱笆修理(Fence Repair) 代码(C)本文地址: http://blog.csdn.net/caroline_wendy题目: 把一块木板切成N块, 每次切两块, 切割的开销是木板长度, 求将木板切割完的最小开销.即霍夫曼编码(Huffman).贪心算法, 类似二叉树型结构, 最短板和次短板是兄弟结点, 选取两个最小木板, 最后进行切割, 合并两个最小木板, 依次递推.代码:/** main.cpp** Created on: 2014.7.17* Author: spike*//*eclipse cdt, gcc 4.8.1*/#include <stdio....

编程算法 - 把字符串转换为整数代码(C)【图】

把字符串转换为整数代码(C)本文地址: http://blog.csdn.net/caroline_wendy题目: 写一个函数StrToInt, 模拟atoi的功能, 把字符串转换为整数.须要考虑异常处理, 正负数, 还有Int的最大值(0x7FFFFFFF)和最小值(0x80000000)等情况.代码:/** main.cpp** Created on: 2014.7.12* Author: spike*/#include <stdio.h> #include <stdlib.h> #include <string.h> #include <math.h>enum Status {kValid=0, kInvalid};int g_nStatus =...

算法基础课相关代码模板【代码】【图】

算法基础课相关代码模板活动链接 —— 算法基础课快速排序算法模板 —— 模板题 AcWing 785. 快速排序 void quick_sort(int q[], int l, int r) {if (l >= r) return;int i = l - 1, j = r + 1, x = q[l + r >> 1];while (i < j){do i ++ ; while (q[i] < x);do j -- ; while (q[j] > x);if (i < j) swap(q[i], q[j]);}quick_sort(q, l, j), quick_sort(q, j + 1, r);}归并排序算法模板 —— 模板题 AcWing 787. 归并排序void m...

MATLAB - 相关标签

matlab2018a MATLAB编程 matlab程序 matlab代码 matlab仿真 matlab函数 matlab图像处理

算法 - 相关标签

算法笔记算法导论算法的时间复杂度算法第四版算法分析算法分析与设计算法复杂度算法工程师算法竞赛入门经典算法面试

算法 - 最新教程

TCP慢启动算法 HashMap与HashTable的哈希算法——JDK1...C++ 算法 A*算法研究南邮算法分析与设计实验4 密码算法令牌桶限流算法和漏桶限流算法区别省选算法学习-矩阵与矩阵快速幂 DotNet常用排序算法总结机器学习---算法学习3 算法导论学习笔记(2)－归并排序

算法 - 最热教程

浅谈SQLServer查询优化器中的JOIN算法有没那种可逆算法是密文比明文短的呢？...javascript-类似Excel里面的NORMDIST函...C++中的分治算法及常见题目汇总压缩感知重构算法综述-学习笔记 c++中内置函数qsort（快速排序）和bsea...一、fpga图像处理算法整合基于遗传算法（deap）的非线性函数寻优...集成学习-Bagging集成学习算法随机森林...机器学习笔记（九）聚类算法及实践（K-...