遗传算法和蚁群算法在求解TSP问题上的对比分析

原创比遗传算法性能更好：蚁群算法TSP(旅行商问题)通用matlab程序

声明：本程序为本人原创，在研学论坛首次发表，本人保留一切权利，仅供学习交流用，如转载请注明原作者！

function [R_best,L_best,L_ave,Shortest_Route,Shortest_Length]=ACATSP(C,NC_max,m,Alpha,Beta,Rho,Q)

%%=========================================================================

%% ACATSPm

%% Ant Colony Algorithm for Traveling Salesman Problem

%% ChengAihua,PLA Information Engineering University,ZhengZhou,China

%% Email:aihuacheng@gmailcom

%% All rights reserved

%%-------------------------------------------------------------------------

%% 主要符号说明

%% C n个城市的坐标，n×2的矩阵

%% NC_max 最大迭代次数

%% m 蚂蚁个数

%% Alpha 表征信息素重要程度的参数

%% Beta 表征启发式因子重要程度的参数

%% Rho 信息素蒸发系数

%% Q 信息素增加强度系数

%% R_best 各代最佳路线

%% L_best 各代最佳路线的长度

%%=========================================================================

%%第一步：变量初始化

n=size(C,1);%n表示问题的规模（城市个数）

D=zeros(n,n);%D表示完全图的赋权邻接矩阵

for i=1:n

for j=1:n

if i~=j

D(i,j)=((C(i,1)-C(j,1))^2+(C(i,2)-C(j,2))^2)^05;

else

D(i,j)=eps;

end

D(j,i)=D(i,j);

end

end

Eta=1/D;%Eta为启发因子，这里设为距离的倒数

Tau=ones(n,n);%Tau为信息素矩阵

Tabu=zeros(m,n);%存储并记录路径的生成

NC=1;%迭代计数器

R_best=zeros(NC_max,n);%各代最佳路线

L_best=infones(NC_max,1);%各代最佳路线的长度

L_ave=zeros(NC_max,1);%各代路线的平均长度

while NC<=NC_max%停止条件之一：达到最大迭代次数

%%第二步：将m只蚂蚁放到n个城市上

Randpos=[];

for i=1:(ceil(m/n))

Randpos=[Randpos,randperm(n)];

end

Tabu(:,1)=(Randpos(1,1:m))';

%%第三步：m只蚂蚁按概率函数选择下一座城市，完成各自的周游

for j=2:n

for i=1:m

visited=Tabu(i,1:(j-1));%已访问的城市

J=zeros(1,(n-j+1));%待访问的城市

P=J;%待访问城市的选择概率分布

Jc=1;

for k=1:n

if length(find(visited==k))==0

J(Jc)=k;

Jc=Jc+1;

end

end

%下面计算待选城市的概率分布

for k=1:length(J)

P(k)=(Tau(visited(end),J(k))^Alpha)(Eta(visited(end),J(k))^Beta);

end

P=P/(sum(P));

%按概率原则选取下一个城市

Pcum=cumsum(P);

Select=find(Pcum>=rand);

to_visit=J(Select(1));

Tabu(i,j)=to_visit;

end

end

if NC>=2

Tabu(1,:)=R_best(NC-1,:);

end

%%第四步：记录本次迭代最佳路线

L=zeros(m,1);

for i=1:m

R=Tabu(i,:);

for j=1:(n-1)

L(i)=L(i)+D(R(j),R(j+1));

end

L(i)=L(i)+D(R(1),R(n));

end

L_best(NC)=min(L);

pos=find(L==L_best(NC));

R_best(NC,:)=Tabu(pos(1),:);

L_ave(NC)=mean(L);

NC=NC+1

%%第五步：更新信息素

Delta_Tau=zeros(n,n);

for i=1:m

for j=1:(n-1)

Delta_Tau(Tabu(i,j),Tabu(i,j+1))=Delta_Tau(Tabu(i,j),Tabu(i,j+1))+Q/L(i);

end

Delta_Tau(Tabu(i,n),Tabu(i,1))=Delta_Tau(Tabu(i,n),Tabu(i,1))+Q/L(i);

end

Tau=(1-Rho)Tau+Delta_Tau;

%%第六步：禁忌表清零

Tabu=zeros(m,n);

end

%%第七步：输出结果

Pos=find(L_best==min(L_best));

Shortest_Route=R_best(Pos(1),:)

Shortest_Length=L_best(Pos(1))

subplot(1,2,1)

DrawRoute(C,Shortest_Route)

subplot(1,2,2)

plot(L_best)

hold on

plot(L_ave)

function DrawRoute(C,R)

%%=========================================================================

%% DrawRoutem

%% 画路线图的子函数

%%-------------------------------------------------------------------------

%% C Coordinate 节点坐标，由一个N×2的矩阵存储

%% R Route 路线

%%=========================================================================

N=length(R);

scatter(C(:,1),C(:,2));

hold on

plot([C(R(1),1),C(R(N),1)],[C(R(1),2),C(R(N),2)])

hold on

for ii=2:N

plot([C(R(ii-1),1),C(R(ii),1)],[C(R(ii-1),2),C(R(ii),2)])

hold on

end

设置初始参数如下：

m=31;Alpha=1;Beta=5;Rho=01;NC_max=200;Q=100;

31城市坐标为：

1304 2312

3639 1315

4177 2244

3712 1399

3488 1535

3326 1556

3238 1229

4196 1004

4312 790

4386 570

3007 1970

2562 1756

2788 1491

2381 1676

1332 695

3715 1678

3918 2179

4061 2370

3780 2212

3676 2578

4029 2838

4263 2931

3429 1908

3507 2367

3394 2643

3439 3201

2935 3240

3140 3550

2545 2357

2778 2826

2370 2975

运行后得到15602的巡游路径，

首先确定xyz的范围，比如说xyz都是从1到10，那么

[x,y,z]=meshgrid(1:10);

这时x，y，z都是3维矩阵，因此后面无法进行乘法运算是吧。因此函数没法写。你是这个地方卡住了是吧？？？

可以这样解决：

x=x(:);y=y(:);z=z(:);这样将xyz变成向量。就可以像平时一样定义函数了。

“蚁群算法”学习包下载

下载地址： http://boardverycdcom/t196436html (请使用 eMule 下载)

近一百多篇文章，打包压缩后有 2499MB ，基本上是从维普数据库中下载来的，仅供学习和研究之用，请务用于商业活动或其他非法活动中，各文章版权归原作者所有。

如果您觉得本人这样做侵犯了您的版权，请在本帖后回复，本人会马上删除相应的文章。

以下是文件列表，全是 PDF 格式的：

基于蚁群优化算法递归神经网络的短期负荷预测

蚁群算法的小改进

基于蚁群算法的无人机任务规划

多态蚁群算法

MCM基板互连测试的单探针路径优化研究

改进的增强型蚁群算法

基于云模型理论的蚁群算法改进研究

基于禁忌搜索与蚁群最优结合算法的配电网规划

自适应蚁群算法在序列比对中的应用

基于蚁群算法的QoS多播路由优化算法

多目标优化问题的蚁群算法研究

多线程蚁群算法及其在最短路问题上的应用研究

改进的蚁群算法在2D HP模型中的应用

制造系统通用作业计划与蚁群算法优化

基于混合行为蚁群算法的研究

火力优化分配问题的小生境遗传蚂蚁算法

基于蚁群算法的对等网模拟器的设计与实现

基于粗粒度模型的蚁群优化并行算法

动态跃迁转移蚁群算法

基于人工免疫算法和蚁群算法求解旅行商问题

基于信息素异步更新的蚁群算法

用于连续函数优化的蚁群算法

求解复杂多阶段决策问题的动态窗口蚁群优化算法

蚁群算法在铸造生产配料优化中的应用

多阶段输电网络最优规划的并行蚁群算法

求解旅行商问题的混合粒子群优化算法

微粒群优化算法研究现状及其进展

随机摄动蚁群算法的收敛性及其数值特性分析

广义蚁群与粒子群结合算法在电力系统经济负荷分配中的应用

改进的蚁群算法及其在TSP中的应用研究

蚁群算法的全局收敛性研究及改进

房地产开发项目投资组合优化的改进蚁群算法

一种改进的蚁群算法用于灰色约束非线性规划问题求解

一种自适应蚁群算法及其仿真研究

一种动态自适应蚁群算法

蚂蚁群落优化算法在蛋白质折叠二维亲-疏水格点模型中的应用

用改进蚁群算法求解函数优化问题

连续优化问题的蚁群算法研究进展

蚁群算法概述

Ant colony system algorithm for the optimization of beer fermentation control

蚁群算法在K—TSP问题中的应用

Parallel ant colony algorithm and its application in the capacitated lot sizing problem for an agile supply chain

基于遗传蚁群算法的机器人全局路径规划研究

改进的蚁群算法在矿山物流配送路径优化中的研究

基于蚁群算法的配电网络综合优化方法

基于蚁群算法的分类规则挖掘算法

蚁群算法在连续性空间优化问题中的应用

蚁群算法在矿井通风系统优化设计中的应用

基于蚁群算法的液压土锚钻机动力头优化设计

改进蚁群算法设计拉式膜片d簧

计算机科学技术

基本蚁群算法及其改进

TSP改进算法及在PCB数控加工刀具轨迹中的应用

可靠性优化的蚁群算法

对一类带聚类特征TSP问题的蚁群算法求解

蚁群算法理论及应用研究的进展

基于二进制编码的蚁群优化算法及其收敛性分析

蚁群算法的理论及其应用

基于蚁群行为仿真的影像纹理分类

启发式蚁群算法及其在高填石路堤稳定性分析中的应用

蚁群算法的研究现状

一种快速全局优化的改进蚁群算法及仿真

聚类问题的蚁群算法

蚁群最优化——模型、算法及应用综述

基于信息熵的改进蚁群算法及其应用

机载公共设备综合管理系统任务分配算法研究

基于改进蚁群算法的飞机低空突防航路规划

利用信息量留存的蚁群遗传算法

An Improved Heuristic Ant-Clustering Algorithm

改进型蚁群算法在内燃机径向滑动轴承优化设计中的应用

基于蚁群算法的PID参数优化

基于蚁群算法的复杂系统多故障状态的决策

蚁群算法在数据挖掘中的应用研究

基于蚁群算法的基因联接学习遗传算法

基于细粒度模型的并行蚁群优化算法

Binary-Coding-Based Ant Colony Optimization and Its Convergence

运载火箭控制系统漏电故障诊断研究

混沌扰动启发式蚁群算法及其在边坡非圆弧临界滑动面搜索中的应用

蚁群算法原理的仿真研究

Hopfield neural network based on ant system

蚁群算法及其实现方法研究

分层实体制造激光头切割路径的建模与优化

配送网络规划蚁群算法

基于蚁群算法的城域交通控制实时滚动优化

基于蚁群算法的复合形法及其在边坡稳定分析中的应用

Ant Colony Algorithm for Solving QoS Routing Problem

多产品间歇过程调度问题的建模与优化

基于蚁群算法的两地之间的最佳路径选择

蚁群算法求解问题时易产生的误区及对策

用双向收敛蚁群算法解作业车间调度问题

物流配送路径安排问题的混合蚁群算法

求解TSP问题的模式学习并行蚁群算法

基于蚁群算法的三维空间机器人路径规划

蚁群优化算法及其应用

蚁群算法不确定性分析

一种求解TSP问题的相遇蚁群算法

基于蚁群优化算法的彩色图像颜色聚类的研究

钣金件数控激光切割割嘴路径的优化

基于蚁群算法的图像分割方法

一种基于蚁群算法的聚类组合方法

圆排列问题的蚁群模拟退火算法

智能混合优化策略及其在流水作业调度中的应用

蚁群算法在QoS网络路由中的应用

一种改进的自适应路由算法

基于蚁群算法的煤炭运输优化方法

基于蚁群智能和支持向量机的人脸性别分类方法

蚁群算法在啤酒发酵控制优化中的应用

一种基于时延信息的多QoS快速自适应路由算法

蚁群算法中参数α、β、ρ设置的研究——以TSP问题为例

基于人工蚁群优化的矢量量化码书设计算法

具有自适应杂交特征的蚁群算法

蚁群算法在原料矿粉混匀优化中的应用

基于多Agent的蚁群算法在车间动态调度中的应用研究

用蚁群优化算法求解中国旅行商问题

蚁群算法在婴儿营养米粉配方中的应用

蚁群算法在机械优化设计中的应用

蚁群优化算法的研究现状及研究展望

蚁群优化算法及其应用研究进展

蚁群算法的理论与应用

简单蚁群算法的仿真分析

一种改进的蚁群算法求解最短路径问题

基于模式求解旅行商问题的蚁群算法

一种求解TSP的混合型蚁群算法

基于MATLAB的改进型基本蚁群算法

动态蚁群算法求解TSP问题

用蚁群算法求解类TSP问题的研究

蚁群算法求解连续空间优化问题的一种方法

用混合型蚂蚁群算法求解TSP问题

求解复杂TSP问题的随机扰动蚁群算法

基于蚁群算法的中国旅行商问题满意解

蚁群算法的研究现状和应用及蚂蚁智能体的硬件实现

蚁群算法概述

蚁群算法的研究现状及其展望

基于蚁群算法的配电网网架优化规划方法

用于一般函数优化的蚁群算法

协同模型与遗传算法的集成

基于蚁群最优的输电网络扩展规划

自适应蚁群算法

凸整数规划问题的混合蚁群算法

一种新的进化算法—蛟群算法

基于协同工作方式的一种蚁群布线系统

n个城市，编号为1---n

for循环的次数是蚂蚁重复城市的次数，比如5个蚂蚁放到4个城市，需要重复两遍才能放完蚂蚁，每次循环产生n个1---n的随机数,相当于随机n个城市，产生城市序列

循环结束

Tabu一句表示将m个蚂蚁随机，每个蚂蚁放到前面产生的城市序列中，每个蚂蚁一个城市，需要m个，所以提取前面1：m个序列

'表示转置，没有多大用处，可能参与后面的计算方便。

我感觉如果m,n很大的话，你这样做会产生很大的浪费，计算很多的随机数，这样的话更好，一句就得：(如果变量Randpos后面没有用到的话，如果用到了，还要用你的程序)

Tabu=ceil(nrand(1,m))'