2 karl wuzheng karl_wuzheng 于 2016.04.23 20:18 提问

基于C语言,用蚁群算法求最优路径。百度复制粘贴的别来了。。。要求可以直接运行的代码哈 30C

一个人从上海大学出发,经过若干个地点,路线不重复走,最后回到上海大学,找三条优化路线。
上海大学:北纬N31°19′5.86″ 东经E121°23′21.52″

星雨城:北纬N31°19′46.58″ 东经E121°24′9.29″

大康公寓:北纬N31°19′18.88″ 东经E121°25′3.98″

文景楼:北纬N22°35′23.78″ 东经E113°52′50.67″

大场中学:北纬N31°18′31.33″ 东经E121°23′37.45″

大场镇小学:北纬N31°18′27.11″ 东经E121°24′23.52″

津臣公寓:北纬N31°18′28.06″ 东经E121°25′38.71″

临汾小区:北纬N31°18′45.46″ 东经E121°27′14.83″

共和国际商务广场:北纬N31°18′24.34″ 东经E121°26′41.96″

海虹欣苑:北纬N31°17′55.72″ 东经E121°27′29.90″

上海马戏城:北纬N31°16′47.00″ 东经E121°26′48.44″

上海大学延长小区南门:北纬N31°16′30.15″ 东经E121°27′17.77″

宝山万达广场四号写字楼:北纬N46°31′17.14″ 东经E131°33′1.98″

锦阳小区:北纬N31°27′58.10″ 东经E104°44′13.29″

仁德坊:北纬N31°18′19.50″ 东经E121°28′45.91″

海尚逸苑:北纬N31°18′50.78″ 东经E121°28′33.11″

3个回答

devmiao
devmiao   Ds   Rxr 2016.04.23 23:45

一个用蚁群算法求最短路径的例子(matlab) (2013-10-14 03:59:46)转载▼
标签: matlab 蚁群算法 分类: matlab
这个例子其实是当初数模比赛时用来完成碎片拼接的,但其所用到原理还是求解最短路径的原理。但这里的最短路径和数据结构中最短路径有一定的区别。在数据结构中,对于最短路径的求解常用的一般有Dijkstra算法与Floyd算法,但对于要求出一条经过所有的点的并且要求路径最短,这些算法还是有一定的局限性的。而蚁群算法则很好地满足了这些条件。
话说回来,很想吐槽一下网络流传的一些蚁群算法的例子,当初学习这个时候,身边也没有相关的书籍,只好到网上找例子。网上关于这个算法源代码的常见的有2个版本,都是出自博客,但是在例子都代码是不完整的,缺失了一部分,但就是这样的例子,居然流传甚广,我很好奇那些转载这些源码的人是否真的有去学习过这些,去调试过。
当然,我下面的例子也是无法直接编译通过的,因为涉及到图像读取处理等方面的东西,所以就只贴算法代码部分。但是对于这个问题蚁群算法有一个比较大的缺点,就是收敛很慢,不过对于数量小的路径,效果还是很好的。
function bestqueue =aco1(nt,nc_max,m ,st, sd ,Alpha ,Beta ,Rho ,Q,gethead,getend)
%参数解释:
%nt 路径所经过的点的个数;
%nc_max 迭代的次数;
%m 蚂蚁的个数;
%st 起点序号;
%sd 终点序号;
%Alpha 信息素系数;
�ta 启发因子系数;
%Rho 蒸发系数;
% Q 信息量;
%gethead getend 是用来求距离矩阵的,可根据实际情况修改

% nt = 209;%碎片个数
full = zeros(nt,nt);
tic;
%初始化距离矩阵
for i =1:nt
for t = 1:nt
if i ~= t
full(i,t) = sum(abs(getend(:,i) - gethead(:,t)));
else
full(i,t) = inf;
end
end
end
% a =full(156,187)
eta = 1./full;%启发因子,取距离的倒数
% eta
% e = eta(4,2)
tau = ones(nt,nt);%信息素矩阵
% tabu = zeros(nt,nt);%禁忌矩阵,取蚂蚁数量和碎片数量一致,以减少迭代次数
nc =1;%初始化迭代次数;
rbest=zeros(nc_max,nt);%各代最佳路线
rbest(:,1) = (linspace(st,st,nc_max))';
rbest(:,nt) =(linspace(sd,sd,nc_max))';
lbest=zeros(nc_max,1);%各代最佳路线的长度
pathlen = 0;%临时记录每代最佳路线长度
stime = 1;%记录代数进度
for i = 1:nc_max % 代数循环
delta_tau=zeros(nt,nt);%初始化改变量
stime
for t = 1:m % 对蚂蚁群体的循环,

    tabu=zeros(1,nt);%禁忌向量,标记已访问的碎片,初试值设为0,访问之后则变为1;
    viseted = zeros(1,nt);%记录已访问的元素的位置
    tabu(st) = 1;%st为起点,在此表示为碎片矩阵的编号,因为已经将蚁群放在起点,故也应将禁忌向量和位置向量的状态进行修改
    tabu(sd) =1;%同上
    visited(nt) = sd ;%同上;
    visited(1) = st;%同上;

    ht  = 0;
    for r  = 2:nt-1  %记录了还没访问的图片编号
          vp = 1;%visited指示量
          pp  = [];%置空的概率向量
          jc = 0;
          %获取尚未访问的位置的向量。
          wv = zeros( nt -2 - ht );
          for  k  =1 : nt
              if tabu(k) ==  0
                  jc = jc +1;
                  wv(jc)  = k;

              end
          end

% a =(tau(visited(end),ju(3))^Alpha)*(eta(visited(end),ju(3))^Beta)
% visited(end)
%计算选择的概率
for k=1:length(wv)
pp(k)=(tau(visited(vp),wv(k))^Alpha)*(eta(visited(vp),wv(k))^Beta);%下一张碎片的选择概率计算,p =(信息素^信息素系数)*(启发因子^启发因子系数)
end
pp=pp./(sum(pp));%归一化
pcum =cumsum(pp);
psl = find(pcum >= rand);%轮盘赌法
to_visit= wv(psl(1)) ;%完成选点
tabu(to_visit) =1;
visited(r) = to_visit;
ht =ht +1;%已访问碎片个数变化
vp =vp+1;
end
%路径变化信息
%对单个蚂蚁的路径进行统计
sum1 =0;
for pr = 1:nt -1
x = visited(pr);
y = visited(pr+1) ;
sum1 =sum1 + full(x,y);
end
% vcell{t} =visited;%元胞记录每个蚂蚁的路径,即碎片顺序;
% msum(t) = sum1;
%信息素变化;

      for ww=1:(nt-1)
        delta_tau(visited(ww),visited(ww+1))=delta_tau(visited(ww),visited(ww+1)) + Q/sum1;
      end

% delta_tau(visited(end),visited(1))=delta_tau(visited(end),visited(1))+Q/(sum1/100);
% if t == m & i == nc_max
% bestqueue = visited
% end
if t == m
bestqueue = visited
end
end
tau=(1-Rho).*tau+delta_tau;
%完成信息素的更新,找出现有的最新的最佳路径,即信息素最多的路径;
stime =stime +1;
end
toc;

devmiao
devmiao   Ds   Rxr 2016.04.23 23:44

一个用蚁群算法求最短路径的例子(matlab) (2013-10-14 03:59:46)转载▼
标签: matlab 蚁群算法 分类: matlab
这个例子其实是当初数模比赛时用来完成碎片拼接的,但其所用到原理还是求解最短路径的原理。但这里的最短路径和数据结构中最短路径有一定的区别。在数据结构中,对于最短路径的求解常用的一般有Dijkstra算法与Floyd算法,但对于要求出一条经过所有的点的并且要求路径最短,这些算法还是有一定的局限性的。而蚁群算法则很好地满足了这些条件。
话说回来,很想吐槽一下网络流传的一些蚁群算法的例子,当初学习这个时候,身边也没有相关的书籍,只好到网上找例子。网上关于这个算法源代码的常见的有2个版本,都是出自博客,但是在例子都代码是不完整的,缺失了一部分,但就是这样的例子,居然流传甚广,我很好奇那些转载这些源码的人是否真的有去学习过这些,去调试过。
当然,我下面的例子也是无法直接编译通过的,因为涉及到图像读取处理等方面的东西,所以就只贴算法代码部分。但是对于这个问题蚁群算法有一个比较大的缺点,就是收敛很慢,不过对于数量小的路径,效果还是很好的。
function bestqueue =aco1(nt,nc_max,m ,st, sd ,Alpha ,Beta ,Rho ,Q,gethead,getend)
%参数解释:
%nt 路径所经过的点的个数;
%nc_max 迭代的次数;
%m 蚂蚁的个数;
%st 起点序号;
%sd 终点序号;
%Alpha 信息素系数;
�ta 启发因子系数;
%Rho 蒸发系数;
% Q 信息量;
%gethead getend 是用来求距离矩阵的,可根据实际情况修改

% nt = 209;%碎片个数
full = zeros(nt,nt);
tic;
%初始化距离矩阵
for i =1:nt
for t = 1:nt
if i ~= t
full(i,t) = sum(abs(getend(:,i) - gethead(:,t)));
else
full(i,t) = inf;
end
end
end
% a =full(156,187)
eta = 1./full;%启发因子,取距离的倒数
% eta
% e = eta(4,2)
tau = ones(nt,nt);%信息素矩阵
% tabu = zeros(nt,nt);%禁忌矩阵,取蚂蚁数量和碎片数量一致,以减少迭代次数
nc =1;%初始化迭代次数;
rbest=zeros(nc_max,nt);%各代最佳路线
rbest(:,1) = (linspace(st,st,nc_max))';
rbest(:,nt) =(linspace(sd,sd,nc_max))';
lbest=zeros(nc_max,1);%各代最佳路线的长度
pathlen = 0;%临时记录每代最佳路线长度
stime = 1;%记录代数进度
for i = 1:nc_max % 代数循环
delta_tau=zeros(nt,nt);%初始化改变量
stime
for t = 1:m % 对蚂蚁群体的循环,

    tabu=zeros(1,nt);%禁忌向量,标记已访问的碎片,初试值设为0,访问之后则变为1;
    viseted = zeros(1,nt);%记录已访问的元素的位置
    tabu(st) = 1;%st为起点,在此表示为碎片矩阵的编号,因为已经将蚁群放在起点,故也应将禁忌向量和位置向量的状态进行修改
    tabu(sd) =1;%同上
    visited(nt) = sd ;%同上;
    visited(1) = st;%同上;

    ht  = 0;
    for r  = 2:nt-1  %记录了还没访问的图片编号
          vp = 1;%visited指示量
          pp  = [];%置空的概率向量
          jc = 0;
          %获取尚未访问的位置的向量。
          wv = zeros( nt -2 - ht );
          for  k  =1 : nt
              if tabu(k) ==  0
                  jc = jc +1;
                  wv(jc)  = k;

              end
          end

% a =(tau(visited(end),ju(3))^Alpha)*(eta(visited(end),ju(3))^Beta)
% visited(end)
%计算选择的概率
for k=1:length(wv)
pp(k)=(tau(visited(vp),wv(k))^Alpha)*(eta(visited(vp),wv(k))^Beta);%下一张碎片的选择概率计算,p =(信息素^信息素系数)*(启发因子^启发因子系数)
end
pp=pp./(sum(pp));%归一化
pcum =cumsum(pp);
psl = find(pcum >= rand);%轮盘赌法
to_visit= wv(psl(1)) ;%完成选点
tabu(to_visit) =1;
visited(r) = to_visit;
ht =ht +1;%已访问碎片个数变化
vp =vp+1;
end
%路径变化信息
%对单个蚂蚁的路径进行统计
sum1 =0;
for pr = 1:nt -1
x = visited(pr);
y = visited(pr+1) ;
sum1 =sum1 + full(x,y);
end
% vcell{t} =visited;%元胞记录每个蚂蚁的路径,即碎片顺序;
% msum(t) = sum1;
%信息素变化;

      for ww=1:(nt-1)
        delta_tau(visited(ww),visited(ww+1))=delta_tau(visited(ww),visited(ww+1)) + Q/sum1;
      end

% delta_tau(visited(end),visited(1))=delta_tau(visited(end),visited(1))+Q/(sum1/100);
% if t == m & i == nc_max
% bestqueue = visited
% end
if t == m
bestqueue = visited
end
end
tau=(1-Rho).*tau+delta_tau;
%完成信息素的更新,找出现有的最新的最佳路径,即信息素最多的路径;
stime =stime +1;
end
toc;

devmiao
devmiao   Ds   Rxr 2016.04.26 05:35

【前言】
智能蚂蚁机器人的集群控制,很可能也采用到了蚁群算法这种人工智能理论与技术。
编程知识:蚁群算法在最优路径求解方案中的应用
【蚁群算法简介】
蚁群算法(antcolony optimization, ACO),又称蚂蚁算法,指的是一种源于自然现象的算法,也是一种 metaheuristic,即与具体问题关系不大的优化算法,也就是它是一种用来在图中寻找优化路径的机率型技术。它由MarcoDorigo于1992年在他的博士论文中提出,其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。蚁群算法是一种模拟进化算法,初步的研究表明该算法具有许多优良的性质。针对PID控制器参数优化设计问题,将蚁群算法设计的结果与遗传算法设计的结果进行了比较,数值仿真结果表明,蚁群算法具有一种新的模拟进化优化方法的有效性和应用价值。

【蚁群算法原理】
自然界中的蚂蚁是没有视觉的,既不知道向何处寻找食物,也不知道发现食物后如何返回自己的巢穴,它仅仅依赖于同类散发在周围环境中的特殊物质—信息素的轨迹,来决定自己何去何从。但是尽管没有任何先验的知识,但蚂蚁们还是有能力找到从其巢穴到食物源的最佳路径。所以大量研究发现,同一蚁群中的蚂蚁能感知信息素及其强度,后来的蚂蚁会倾向于朝信息素浓度高的方向移动,而移动留下的信息素又会对原有信息素进行加强,后续的蚂蚁而后续的蚂蚁选择该路径的可能性也越大。由于在相同时间段内越短的路径会被越多的蚂蚁访问,所以后续的蚂蚁选择较短路径的可能性也越大,最后所有的蚂蚁都走最短的那条路径。 应该指出,以蚁群为基础的方法能够有效地寻找较短的路径,但不一定是最短的路径。不过,对于那些难于获得最优解的问题,如那些NP难题,这种近于最优的解法常常已经是绰绰有余了。事实上,随着城市数目的增多,寻找精确解很快就会变成一个无法对付的问题。

【蚁群算法求解步骤】
(1)本文要解决的问题(TSP问题)。TSP问题,又称为旅行商问题、货郎担问题、TSP问题,是一个多局部最优的最优化问题:有n个城市,一个推销员要从其中某一个城市出发,唯一走遍所有的城市,再回到他出发的城市,求最短的路线。也即求一个最短的哈密顿回路。TSP问题是一个组合优化问题。该问题可以被证明具有NP计算复杂性。因此,任何能使该问题的求解得以简化的方法,都将受到高度的评价和关注。旅行推销员问题是数图论中最著名的问题之一,即“已给一个n个点的完全图,每条边都有一个长度,求总长度最短的经过每个顶点正好一次的封闭回路”。Edmonds,Cook和Karp等人发现,这批难题有一个值得注意的性质,对其中一个问题存在有效算法时,每个问题都会有有效算法。迄今为止,这类问题中没有一个找到有效算法。倾向于接受NP完全问题(NP-Complet或NPC)和NP难题(NP-Hard或NPH)不存在有效算法这一猜想,认为这类问题的大型实例不能用精确算法求解,必须寻求这类问题的有效的近似算法。此类问题中,经典的还有子集和问题;Hamilton回路问题;最大团问题。本文提出的问题是:我国31个直辖市、省会和自治区首府的巡回路线应有很多种,试着寻找一条最短路径。(2)算法求解步骤
编程知识:蚁群算法在最优路径求解方案中的应用

【求解结果】
(1)TSP路线展示
编程知识:蚁群算法在最优路径求解方案中的应用
(2)适应度函数变化(目标值变化情况)

编程知识:蚁群算法在最优路径求解方案中的应用
【蚁群算法源代码】
function [R_best,L_best,L_ave,Shortest_Route,Shortest_Length]=ACATSP(C,NC_max,m,Alpha,Beta,Rho,Q)
%%=========================================================================
%% ACATSP.m
%% Ant Colony Algorithm for Traveling Salesman Problem
%% ChengAihua,PLA Information Engineering University,ZhengZhou,China
%% Email:aihuacheng@gmail.com
%% All rights reserved
%%-------------------------------------------------------------------------
%% 主要符号说明
%% C n个城市的坐标,n×2的矩阵
%% NC_max 最大迭代次数
%% m 蚂蚁个数
%% Alpha 表征信息素重要程度的参数
%% Beta 表征启发式因子重要程度的参数
%% Rho 信息素蒸发系数
%% Q 信息素增加强度系数
%% R_best 各代最佳路线
%% L_best 各代最佳路线的长度
%% 运行可能要很久,需要耐心等待
%%=========================================================================

n=length(C); %n 为市个数
for i=1:n %坐标矩阵转换为距离矩阵
for j=1:n
D(i,j)=sqrt((x(i,1)-x(j,1))^2+(x(i,2)-x(j,2))^2);
end
end
for i=1:n %Eta为启发因子,这里设为距离的倒数
for j=1:n %原文作者少考虑的当D=0是MATLAB提示出错
if i~=j
Eta(i,j)=1./D(i,j);
end
end
end
for i=1:n
Eta(i,i)=0;
end
Tau=ones(n,n); %Tau为信息素矩阵
Tabu=zeros(m,n); %存储并记录路径的生成
NC=1; %迭代计数器
R_best=zeros(NC_max,n); %各代最佳路线
L_best=inf.*ones(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));
DrawRoute(C,Shortest_Route) %调用函数绘图
【总结】
(1)蚁群算法具有很强的发现较好解的能力。由于算法本身采用正反馈原理,加快了进化过程,且不易陷入局部最优解; (2)蚁群算法具有很强的并行性,个体之间不断进行信息交流和传递,有利于发现较好解。单个个体容易收敛于局部最优,多个个体通过合作,可很快收敛于解空间的某一子集,有利于对解空间的进一步探索,从而发现较好解。 存在的问题是该算法本身很复杂,一般需要较长的搜索时间;容易出现停滞现象,即搜索进行到一定程度后,所有个体所发现的解完全一致,不能对解空间进一步进行搜索,不利于发现更好的解。

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!