Python&Matlab实现蚂蚁群算法求解最短路径问题的示例

目录
  • 1知识点
    • 1.1 蚁群算法步骤
    • 1.2 蚁群算法程序
  • 2蚂蚁算法求解最短路径问题——Python实现
    • 2.1源码实现
    • 2.2 ACA_TSP实现
  • 3 蚂蚁算法求解最短路径问题——Matlab实现
    • 3.1流程图
    • 3.2代码实现
    • 3.3结果

1 知识点

详细知识点见:智能优化算法—蚁群算法(Python实现)

我们这一节知识点只讲蚁群算法求解最短路径步骤及流程。

1.1 蚁群算法步骤

设蚂蚁的数量为m,地点的数量为n,地点i与地点j之间相距Dij,t时刻地点i与地点j连接的路径上的信息素浓度为Sij,初始时刻每个地点间路径上的信息素浓度相等。

蚂蚁k根据各个地点间连接路径上的信息素决定下一个目标地点,Pijk表示t时刻蚂蚁k从地点i转移的概率,概率计算公式如下:

上式中,为启发函数,,表示蚂蚁从地点i转移到地点j的期望程度;为蚂蚁k即将访问地点的集合,开始时中有n-1个元素(除出发地点),随时间的推移,蚂蚁每到达下一个地点,中的元素便减少一个,直至空集,即表示所有地点均访问完毕;a为信息素重要程度因子,值越大,表明信息素的浓度在转移中起到的作用越大,也就是说蚂蚁选择距离近的下一个地点的概率更大,β为启发函数重要程度因子。

蚂蚁在释放信息素的同时,每个地点间连接路径上的信息素逐渐消失,用参数

表示信息素的挥发程度。因此,当所有蚂蚁完成一次循环后,每个地点间连接路径上的信息素浓度需更新,也就是有蚂蚁路过并且留下信息素,有公式表示为:

其中,表示第k只蚂蚁在地点i与j连接路径上释放的信息素浓度;表示所有蚂蚁在地点i与j连接路径上释放的信息素浓度之和;Q为常数,表示蚂蚁循环一次所释放的信息素总量;Lk表示第k只蚂蚁经过路径的长度,总的来说,蚂蚁经过的路径越短,释放的信息素浓度越高,最终选出最短路径。

1.2 蚁群算法程序

(1)参数初始化

在寻最短路钱,需对程序各个参数进行初始化,蚁群规模m、信息素重要程度因子α、启发函数重要程度因子β、信息素会发因子、最大迭代次数ddcs_max,初始迭代值为ddcs=1。

(2)构建解空间

将每只蚂蚁随机放置在不同的出发地点,对蚂蚁访问行为按照公式计算下一个访问的地点,直到所有蚂蚁访问完所有地点。

(3)更新信息素

计算每只蚂蚁经过的路径总长Lk,记录当前循环中的最优路径,同时根据公式对各个地点间连接路径上的信息素浓度进行更新。

(4)判断终止

迭代次数达到最大值前,清空蚂蚁经过的记录,并返回步骤(2)。

2 蚂蚁算法求解最短路径问题——Python实现

2.1 源码实现

智能优化算法—蚁群算法(Python实现)

2.2  ACA_TSP实现

补充知识点:scipy.spatial.distance.cdist

#============导入相关库=================
import numpy as np
from scipy import spatial
import pandas as pd
import matplotlib.pyplot as plt
from sko.ACA import ACA_TSP

num_points = 25

points_coordinate = np.random.rand(num_points, 2)  # 生成点的坐标
distance_matrix = spatial.distance.cdist(points_coordinate, points_coordinate, metric='euclidean')#函数用于计算两个输入集合的距离

def cal_total_distance(routine):
    num_points, = routine.shape
    return sum([distance_matrix[routine[i % num_points], routine[(i + 1) % num_points]] for i in range(num_points)])

#=============ACA_TSP解决==================================

aca = ACA_TSP(func=cal_total_distance, n_dim=num_points,
              size_pop=50, max_iter=200,
              distance_matrix=distance_matrix)

best_x, best_y = aca.run()

#=============可视化=======================

fig, ax = plt.subplots(1, 2)
best_points_ = np.concatenate([best_x, [best_x[0]]])
best_points_coordinate = points_coordinate[best_points_, :]
ax[0].plot(best_points_coordinate[:, 0], best_points_coordinate[:, 1], 'o-r')
pd.DataFrame(aca.y_best_history).cummin().plot(ax=ax[1])
plt.show()

3 蚂蚁算法求解最短路径问题——Matlab实现

3.1 流程图

3.2 代码实现

下表为一些坐标点,找出最短路线:

%蚁群算法寻找最短路径程序
%% 清空环境变量
clear
clc
%% 导入数据,导入方式,看个人习惯
zuobiao=[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];
%% 计算城市间相互距离
n = size(zuobiao,1);%城市个数
jl = zeros(n,n);%首先求得各个坐标点的距离,这里是矩阵初始化
for i = 1:n
    for j = 1:n
        if i ~= j  %~=是不等于的意思,zuobiao矩阵中每行都有个坐标,坐标相减用i和j区分不同的坐标点,然后求两点距离
            jl(i,j) = sqrt(sum((zuobiao(i,:) - zuobiao(j,:)).^2));
%上式运算如a=[2,2;1,1]=>a(1,:)-a(2,:)=>ans =1 1,然后1?+1?=2,最后开根号
        else
            jl(i,j) = 1e-4;%相等的点相减准确说是等于0的,这里设置成了一个很小的数,是为了避免后面程序运算出错
        end
    end
end
%% 初始化参数
m = 50;         % 蚂蚁数量,视情况而定,坐标点多的话可以适当增加蚂蚁数量
a= 1;           % 信息素重要程度因子
b= 5;           % 启发函数重要程度因子
r = 0.1;        % 信息素挥发因子
Q = 1;          % 常数
qfhs = 1./jl;    % 启发函数,将jl矩阵中每个元素转化为倒数
xxsjz = ones(n,n);       % 信息素矩阵初始化
ljjl = zeros(m,n);       % 路径记录表矩阵初始化
ddcs = 1;                % 迭代次数初值
ddcs_max = 200;          % 最大迭代次数
Lujin_best = zeros(ddcs_max,n);      % 各代最佳路径
L_best = zeros(ddcs_max,1);     % 各代最佳路径的长度
L_ave = zeros(ddcs_max,1);      % 各代路径的平均长度
%% 迭代寻找最佳路径
while ddcs <= ddcs_max%在ddcs小于ddcs_max前,一直循环
%% 随机产生各个蚂蚁的起点
      start = zeros(m,1);
      for i = 1:m
          temp = randperm(n);%功能是随机打乱一个数字序列,也就是现将坐标点排号再打乱,相当于将蚂蚁随机分布在各个地点
          start(i) = temp(1);
      end
      ljjl(:,1) = start;
%% 构建解空间
      zuobiao_index = 1:n;
      % 逐个蚂蚁路径选择
      for i = 1:m
          % 逐个地点路径选择
         for j = 2:n
             yfw = ljjl(i,1:(j - 1));           % 已访问的地点集合(禁忌表)
             allow_index = ~ismember(zuobiao_index,yfw);%ismember用于判断矩阵某个元素是否存在,用法详见后文函数讲解
             allow = zuobiao_index(allow_index);  % 待访问的城市集合
             P = allow;
             % 计算城市间转移概率
             for k = 1:length(allow)
                 P(k) = xxsjz(yfw(end),allow(k))^a * qfhs(yfw(end),allow(k))^b;%见文中公式
             end
             P = P/sum(P);
             % 选择下一个访问城市
             Plj = cumsum(P);     %cumsum函数用于累加,具体用法详见后文函数讲解
             yidong_index = find(Plj >= rand);
             yidong = allow(yidong_index(1));
             ljjl(i,j) = yidong;
         end
      end
      % 计算各个蚂蚁的路径距离
      L = zeros(m,1);
      for i = 1:m
          Lujin = ljjl(i,:);
          for j = 1:(n - 1)
              L(i) = L(i) + jl(Lujin(j),Lujin(j + 1));
          end
          L(i) = L(i) + jl(Lujin(n),Lujin(1));
      end
      % 计算最短路径距离及平均距离
      if ddcs == 1
          [min_L,min_index] = min(L);
          L_best(ddcs) = min_L;
          L_ave(ddcs) = mean(L);
          Lujin_best(ddcs,:) = ljjl(min_index,:);
      else
          [min_L,min_index] = min(L);
          L_best(ddcs) = min(L_best(ddcs - 1),min_L);
          L_ave(ddcs) = mean(L);
          if L_best(ddcs) == min_L
              Lujin_best(ddcs,:) = ljjl(min_index,:);
          else
              Lujin_best(ddcs,:) = Lujin_best((ddcs-1),:);
          end
      end
%% 更新信息素
      S = zeros(n,n);
      % 逐个蚂蚁计算
      for i = 1:m
          % 逐个城市计算
          for j = 1:(n - 1)
              S(ljjl(i,j),ljjl(i,j+1)) = S(ljjl(i,j),ljjl(i,j+1)) + Q/L(i);
          end
          S(ljjl(i,n),ljjl(i,1)) = S(ljjl(i,n),ljjl(i,1)) + Q/L(i);
      end
      xxsjz = (1-r) * xxsjz + S;
    % 迭代次数加1,清空路径记录表
    ddcs = ddcs + 1;
    ljjl = zeros(m,n);
end
%% 结果显示
[Shortest_L,index] = min(L_best);
Shortest_Lujin = Lujin_best(index,:);
disp(['最短距离:' num2str(Shortest_L)]);
disp(['最短路径:' num2str([Shortest_Lujin Shortest_Lujin(1)])]);
%% 绘图
figure(1)
plot([zuobiao(Shortest_Lujin,1);zuobiao(Shortest_Lujin(1),1)],...
     [zuobiao(Shortest_Lujin,2);zuobiao(Shortest_Lujin(1),2)],'o-');
grid on
for i = 1:size(zuobiao,1)
    text(zuobiao(i,1),zuobiao(i,2),['   ' num2str(i)]);
end
text(zuobiao(Shortest_Lujin(1),1),zuobiao(Shortest_Lujin(1),2),'       起点');
text(zuobiao(Shortest_Lujin(end),1),zuobiao(Shortest_Lujin(end),2),'       终点');
xlabel('城市位置横坐标')
ylabel('城市位置纵坐标')
title(['蚁群算法优化路径(最短距离:' num2str(Shortest_L) ')'])
figure(2)
plot(1:ddcs_max,L_best,'b',1:ddcs_max,L_ave,'r')
legend('最短距离','平均距离')
xlabel('迭代次数')
ylabel('距离')
title('各代最短距离与平均距离对比')

3.3 结果

到此这篇关于Python&Matlab实现蚂蚁群算法求解最短路径问题的示例的文章就介绍到这了,更多相关Python&Matlab蚂蚁群最短路径内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • Python实现蚁群算法

    目录 1.引言 2蚁群算法理论 3算法理论图解 4人工蚁群优化过程 5 基本蚁群算法及其流程 5.1  蚁群算法公式 5.2蚁群算法程序概括 5.3流程图 6案例实现 6.1案例1 6.2Python实现 6.3结果 6.4案例2 6.5Python实现 6.6结果 1.引言 在自然界中各种生物群体显现出来的智能近几十年来得到了学者们的广泛关注,学者们通过对简单生物体的群体行为进行模拟,进而提出了群智能算法.其中,模拟蚁群觅食过程的蚁群优化算法(Ant Colony Optimization,

  • Python 蚁群算法详解

    目录 蚁群算法简介 TSP问题描述 蚁群算法原理 代码实现 总结 蚁群算法简介 蚁群算法(Ant Clony Optimization, ACO)是一种群智能算法,它是由一群无智能或有轻微智能的个体(Agent)通过相互协作而表现出智能行为,从而为求解复杂问题提供了一个新的可能性.蚁群算法最早是由意大利学者Colorni A., Dorigo M. 等于1991年提出.经过20多年的发展,蚁群算法在理论以及应用研究上已经得到巨大的进步. 蚁群算法是一种仿生学算法,是由自然界中蚂蚁觅食的行为而启发

  • Python编程实现蚁群算法详解

    简介 蚁群算法(ant colony optimization, ACO),又称蚂蚁算法,是一种用来在图中寻找优化路径的机率型算法.它由Marco Dorigo于1992年在他的博士论文中提出,其灵感来源于蚂蚁在寻找食物过程中发现路径的行为.蚁群算法是一种模拟进化算法,初步的研究表明该算法具有许多优良的性质.针对PID控制器参数优化设计问题,将蚁群算法设计的结果与遗传算法设计的结果进行了比较,数值仿真结果表明,蚁群算法具有一种新的模拟进化优化方法的有效性和应用价值. 定义 各个蚂蚁在没有事先告诉

  • Python&Matlab实现蚂蚁群算法求解最短路径问题的示例

    目录 1知识点 1.1 蚁群算法步骤 1.2 蚁群算法程序 2蚂蚁算法求解最短路径问题——Python实现 2.1源码实现 2.2 ACA_TSP实现 3 蚂蚁算法求解最短路径问题——Matlab实现 3.1流程图 3.2代码实现 3.3结果 1 知识点 详细知识点见:智能优化算法—蚁群算法(Python实现) 我们这一节知识点只讲蚁群算法求解最短路径步骤及流程. 1.1 蚁群算法步骤 设蚂蚁的数量为m,地点的数量为n,地点i与地点j之间相距Dij,t时刻地点i与地点j连接的路径上的信息素浓度为

  • Python基于Floyd算法求解最短路径距离问题实例详解

    本文实例讲述了Python基于Floyd算法求解最短路径距离问题.分享给大家供大家参考,具体如下: Floyd算法和Dijkstra算法,相信大家都不陌生,在最短路径距离的求解中应该算得上是最为基础和经典的两个算法了,今天就用一点时间来重新实现一下,因为本科的时候学习数据结构才开始接触的这个算法,当时唯一会用的就是C语言了,现在的话,C语言几乎已经离我远去了,个人感觉入手机器学习以来python更得我心,因为太通俗易懂了,带给你的体验自然也是非常不错的. 当然网上 有很多的算法讲解教程,我不会在

  • Python编程实现粒子群算法(PSO)详解

    1 原理 粒子群算法是群智能一种,是基于对鸟群觅食行为的研究和模拟而来的.假设在鸟群觅食范围,只在一个地方有食物,所有鸟儿看不到食物(不知道食物的具体位置),但是能闻到食物的味道(能知道食物距离自己位置).最好的策略就是结合自己的经验在距离鸟群中距离食物最近的区域搜索. 利用粒子群算法解决实际问题本质上就是利用粒子群算法求解函数的最值.因此需要事先把实际问题抽象为一个数学函数,称之为适应度函数.在粒子群算法中,每只鸟都可以看成是问题的一个解,这里我们通常把鸟称之为粒子,每个粒子都拥有: 位置,可

  • Python&Matlab实现灰狼优化算法的示例代码

    目录 1 灰狼优化算法基本思想 2 灰狼捕食猎物过程 2.1 社会等级分层 2.2 包围猎物 2.3 狩猎 2.4 攻击猎物 2.5 寻找猎物 3 实现步骤及程序框图 3.1 步骤 3.2 程序框图 4 Python代码实现 5 Matlab实现 1 灰狼优化算法基本思想 灰狼优化算法是一种群智能优化算法,它的独特之处在于一小部分拥有绝对话语权的灰狼带领一群灰狼向猎物前进.在了解灰狼优化算法的特点之前,我们有必要了解灰狼群中的等级制度. 灰狼群一般分为4个等级:处于第一等级的灰狼用α表示,处于第

  • Python代码实现粒子群算法图文详解

    目录 1.引言 2.算法的具体描述: 2.1原理 2.2标准粒子群算法流程 3.代码案例 3.1问题 3.2绘图 3.3计算适应度 3.4更新速度 3.5更新粒子位置 3.6主要算法过程 结果 总结 1.引言 粒子群优化算法起源于对鸟群觅食活动的分析.鸟群在觅食的时候通常会毫无征兆的聚拢,分散,以及改变飞行的轨迹,但是在不同个体之间会十分默契的保持距离.所以粒子群优化算法模拟鸟类觅食的过程,将待求解问题的搜索空间看作是鸟类飞行的空间,将每只鸟抽象成一个没有质量和大小的粒子,用这个粒子来表示待求解

  • JS使用Dijkstra算法求解最短路径

    一.Dijkstra算法的思路 Dijkstra算法是针对单源点求最短路径的算法. 其主要思路如下: 1. 将顶点分为两部分:已经知道当前最短路径的顶点集合Q和无法到达顶点集合R. 2. 定义一个距离数组(distance)记录源点到各顶点的距离,下标表示顶点,元素值为距离.源点(start)到自身的距离为0,源点无法到达的顶点的距离就是一个大数(比如Infinity). 3. 以距离数组中值为非Infinity的顶点V为中转跳点,假设V跳转至顶点W的距离加上顶点V至源点的距离还小于顶点W至源点

  • Python实现快速排序和插入排序算法及自定义排序的示例

    一.快速排序 快速排序(Quicksort)是对冒泡排序的一种改进.由C. A. R. Hoare在1962年提出.它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列. 快速排序,递归实现 def quick_sort(num_list): """ 快速排序 """ if num_li

  • Java利用Dijkstra算法求解拓扑关系最短路径

    目录 算法简介 代码实现思路 算法思想 代码示例 算法简介 迪杰斯特拉算法(Dijkstra)是由荷兰计算机科学迪家迪杰斯特拉于1959年提出的,因此又叫狄克斯特拉算法.是从一个顶点到其余各顶点最短路劲算法,解决的是有权图中最短路径问题.迪杰斯特拉算法主要特点是从起始点开始,采用贪心算法的策略,每次遍历到始点距离最近且未访问过的顶点的邻接节点,直到扩展到终点为止. 代码实现思路 1.先初始化源节点(起始点)到其他各个拓扑节点的最短距离,可以用map存放,key为节点,value为节点到源节点的距

  • Python实现的直接插入排序算法示例

    本文实例讲述了Python实现的直接插入排序算法.分享给大家供大家参考,具体如下: # -*- coding:utf-8 -*- '''直接插入的python实现 时间复杂度O(n**2) 空间复杂度O(1) 稳定 思想:先将前两个元素排序,第三个元素插入前面已排好序列, 后面的元素依次插入之前已经排好序的序列 ''' author = 'Leo Howell' L = [89,67,56,45,34,23,1] def direct_insert_sort(numbers): for i in

随机推荐