求网友解释下蚁群算法原理并举几个通俗易懂的例子，谢谢

来源：蜘蛛抓取(WebSpider) 时间：2018-10-08 08:20 标签： 蚁群算法

　　若干年前读研的时候，学院有一个教授，专门做群蚁算法的，很厉害，偶尔了解了一点点。感觉也是生物智能的一个体现，和遗传算法、神经网络有异曲同工之妙。只不过当时没有实际需求学习，所以没去研究。最近有一个这样的任务，所以就好好把基础研究了一下，驱动式学习，目标明确，所以还是比较快去接受和理解，然后写代码实现就好了。今天就带领大家走近TSP问题以及群蚁算法。 

本文原文地址： 

　　旅行商问题(Traveling Saleman Problem，TSP)是车辆路径调度问题(VRP)的特例，由于数学家已证明TSP问题是NP难题，因此，VRP也属于NP难题。旅行商问题（TSP）又译为旅行推销员问题、货郎担问题，简称为TSP问题，是最基本的路线问题，该问题是在寻求单一旅行者由起点出发，通过所有给定的需求点之后，最后再回到原点的最小路径成本。——

　　很明显，当节点数很少时，大多数人都会想到，问题很简单，直接穷举就OK了，但实际问题中，节点数往往很大，变得不可能。例如：对于一个仅有16个城市的旅行商问题，如果用穷举法来求问题的最优解，需比较的可行解有：15!/2=653，837，184，000个。在1993年，使用当时的工作站用穷举法求解此问题需时92小时。即使现在计算机速度快，但是面对复杂的问题，仍然不够。这就是所谓的“组合爆炸”，指数级的增长，所以科学家逐步寻找近似算法或者启发式算法，目的是在合理的时间范围内找到可接受的最优解。

　　TSP问题解决算法的发展可以分为3个部分：

1).经典精确算法:穷举法、线性规划算法、动态规划算法、分支定界算法等运筹学中的传统算法，这些算法复杂度一般都很大，只适用于求解小规模问题。

2).近似算法：当问题规模较大时，其所需的时间成级数增长，这是我们无法接受的，算法求解问题的规模受到了很大的限制，一个很自然的想法就是牺牲精确解法中的最优性，去寻找一个好的时间复杂度我们可以容忍的，同时解的质量我们可以接受的算法．基于这一思想所设计出的算法统称为近似算法。如插入算法，最邻近算法等。

3).智能算法：随着科学技术和生产的不断发展，许多实际问题不可能在合理的时间范围内找到全局最优解，这就促使了近代最优化问题求解方法的产生。随着各种不同搜索机制的启发式算法相继出现，如禁忌搜索、遗传算法、模拟退火算法、人工神经网络、进化策略、进化编程、粒子群优化算法、蚁群优化算法和免疫计算等，掀起了研究启发式算法的高潮。

　　具体每一种算法不再详细描述，大家可以针对性的寻找相应资料进行了解。

　　TSP问题在实际的生产生活中，更加实际环境不同，有很多衍生的经典问题。车辆路径调度(VRP)扩展问题是经典VRP加入各种约束条件后而形成的。例如需求约束形成的需求随机的车辆路径问题(SVRP);加入时间约束得到的带时间窗的车辆路径题(VRPTW);加入距离约束的距离约束车辆路径问题(DVRP);根据其它条件的不同,还有多配送中心车辆路径问题(MDVRP)、可切分的车辆路径问题(SDVRP);先配送再收集车辆路径问题(VRPB)、配送收集车辆路径问题(VRPPD);信息不完全的模糊车辆路径问题(FVRP)[3]。

+ C#版本的实现，不过我看了之后果断决定重写，封装不够完善，同时思路也不清楚。所以自己写的过程，理解也更清楚了。经过我的简单更改，目前还说得过去吧，当然后续我还打算继续进行研究，所以先把基本程序的过程写下来，当然是利用了C# 的面向对象特性，看了别人写的 完全面向过程，理解真的很费劲。简单说说实现过程和代码吧。

5.1 群蚁算法系统基类

　　我们封装了一个基础的BaseTspAntSystem类，包括了一些基本属性和计算过程，后续相关改进版本可以进行直接继承。当然设计可能有缺陷，先这样进行，碰到需求再改吧。 BaseTspAntSystem类的主要属性如下：

　　基类有一个构造函数，对系统的初始化就是传入基本的参数，并对相关列表进行初始化，代码如下：

 　　核心的是求解过程，完全按照迭代次数要求进行迭代进行，过程就是概率选择和信息素更新，我们辅助的用到了Ant蚂蚁类，目的就是让程序更加独立和容易理解。Ant类里面有蚂蚁路径寻找过程的所有信息。下一节将进行介绍。求解过程代码如下面，看看注释和对比算法进行：

4 //计算初始信息素的值，可直接指定，或者贪婪算法计算 11 //每条可行的路径的信息素初始值 15 //为每个蚂蚁随机选择出发城市,List的长度为蚂蚁个数，内部List长度为路径 24 //生成蚂蚁及初始访问城市，并设置对应禁忌表和路径列表 28 //所有蚂蚁依次寻找下一个节点，直到本轮完成 33 //取出前面指定的几条最短路径 37 //更新信息素的值：循环所有路径，依次进行添加 43 //再增强,循环所有蚂蚁

 　　根据算法的描述，m只蚂蚁同时进行自己的工作和寻找路程，是一个并行的过程，因此也在单次过程中，蚂蚁都是独立的。蚂蚁的每一次迭代，过程都比较清楚，寻找路径过程，注意维护一些可用的节点列表，以及最后一条路径的处理。看看蚂蚁类的主要属性和构造函数：

6 /// <summary>当前蚂蚁已经走过的路径节点列表，也就是禁忌表 7 /// 最后1个就是当前所处的位置

　　Ant类的核心是寻找下一个城市节点的过程，以及循环直到所有路径都完成。如下面代码，是一个循环过程： 

 1 #region 蚂蚁行为-依次按概率选择下一个城市，直到走完
 6 //为空，就不需要计算了
11 //依次计算当前点到其他点可选择点的 值
19 //计算各个点的概率
21 //产生1个随机数，并按概率确定下一个城市
29 //最后1条路径的问题，额外增加，直接 回原点

　　后面的GetNextCityByRandValue是一个辅助函数，进行随机概率值的选择，确定是否选择哪一个节点。

　　基本TSP问题的C#代码下载：

　　如果下载有问题，请到本文原文下载： 

[2].文永军.旅行商问题的两种智能算法[M].西安电子科技大学,2010年

[3].杨瑞臣.有时间窗和在前约束车辆路径问题的蚁群优化[M].西安建筑科技大学,2005.

[4].谷俊峰.智能算法-第七章：蚁群算法 PPT，大连理工大学，下载：

可选中1个或多个下面的关键词，搜索相关资料。也可直接点“搜索资料”搜索整个问题。

亲，程序搞到了吗？能传一个吗？万分感谢哈

采纳数：0 获赞数：0 LV1

有么，借阅一下，万分感谢！！

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

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

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

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

%%第一步：变量初始化

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

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

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

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

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

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

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

%%第五步：更新信息素

%%第六步：禁忌表清零

%% 画路线图的子函数

我要回帖

更多关于 蚁群算法 的文章

 

随机推荐