蚁群算法c

❶ Ubuntu系统下由gcc编译的C语言利用蚁群算法计算tsp（旅行商问题）的详解和注释

买本书看看去。

你这个只是所有代码里的一个开头，我只能解释这两句话，解释了你又不满意。
我只能叫你去买本书看。

❷ 蚁群算法

在蚂蚁种群中，蚂蚁间相互交流的方式是通过一种名为信息素的物质，它可以是蚂蚁行动时留下的物质，可以被其他蚂蚁所感知。

在寻找食物的过程中，如左图所示，三角形ABC是等边三角形，蚂蚁窝在A点，C点有食物，A点的两只蚂蚁选择了两条路线前往C点，一条为AB->BC，另一条A->C，当走远路的蚂蚁，到达C点时，延AC边上的蚂蚁已经走了一个来回，路径上信息素如右图所示。后到会感知到边AC上的信息素浓度更高一些，于是他也会选择AC来行走，因为相同时间内，信息素浓度更高的说明，路程更短。

蚁群算法便是基于这样的一个思想来解决如TSP等优化问题，一下介绍便是拿TSP问题来介绍蚁群算法

信息素用符号τ来表示，如下式，下标i，j表示从城市i到城市j这条道路上的信息素，上标0表示这是初次计算，也就是初始信息素，初始信息素都设置为1，或者一个较小的常数，表示每条道路上的信息素都相等，这样通过运算蚂蚁爬向各个城市的概率都相等

基于信息素，每只蚂蚁都有一个选择道路的公式，如下式

其中

当所有蚂蚁完成一次周游后，各个路径上的信息素进行一次更新

❸ 蚁群算法的相关研究

跟着蚂蚁的踪迹，你找到了什么？通过上面的原理叙述和实际操作，我们不难发现蚂蚁之所以具有智能行为，完全归功于它的简单行为规则，而这些规则综合起来具有下面两个方面的特点：
1、多样性
2、正反馈
多样性保证了蚂蚁在觅食的时候不至走进死胡同而无限循环，正反馈机制则保证了相对优良的信息能够被保存下来。我们可以把多样性看成是一种创造能力，而正反馈是一种学习强化能力。正反馈的力量也可以比喻成权威的意见，而多样性是打破权威体现的创造性，正是这两点小心翼翼的巧妙结合才使得智能行为涌现出来了。
引申来讲，大自然的进化，社会的进步、人类的创新实际上都离不开这两样东西，多样性保证了系统的创新能力，正反馈保证了优良特性能够得到强化，两者要恰到好处的结合。如果多样性过剩，也就是系统过于活跃，这相当于蚂蚁会过多的随机运动，它就会陷入混沌状态；而相反，多样性不够，正反馈机制过强，那么系统就好比一潭死水。这在蚁群中来讲就表现为，蚂蚁的行为过于僵硬，当环境变化了，蚂蚁群仍然不能适当的调整。
既然复杂性、智能行为是根据底层规则涌现的，既然底层规则具有多样性和正反馈特点，那么也许你会问这些规则是哪里来的？多样性和正反馈又是哪里来的？我本人的意见：规则来源于大自然的进化。而大自然的进化根据刚才讲的也体现为多样性和正反馈的巧妙结合。而这样的巧妙结合又是为什么呢？为什么在你眼前呈现的世界是如此栩栩如生呢？答案在于环境造就了这一切，之所以你看到栩栩如生的世界，是因为那些不能够适应环境的多样性与正反馈的结合都已经死掉了，被环境淘汰了！ 蚁群算法的由来：蚂蚁是地球上最常见、数量最多的昆虫种类之一，常常成群结队地出现在人类的日常生活环境中。这些昆虫的群体生物智能特征，引起了一些学者的注意。意大利学者M.Dorigo，V.Maniezzo等人在观察蚂蚁的觅食习性时发现，蚂蚁总能找到巢穴与食物源之间的最短路径。经研究发现，蚂蚁的这种群体协作功能是通过一种遗留在其来往路径上的叫做信息素(Pheromone)的挥发性化学物质来进行通信和协调的。化学通信是蚂蚁采取的基本信息交流方式之一，在蚂蚁的生活习性中起着重要的作用。通过对蚂蚁觅食行为的研究，他们发现，整个蚁群就是通过这种信息素进行相互协作，形成正反馈，从而使多个路径上的蚂蚁都逐渐聚集到最短的那条路径上。
这样，M.Dorigo等人于1991年首先提出了蚁群算法。其主要特点就是：通过正反馈、分布式协作来寻找最优路径。这是一种基于种群寻优的启发式搜索算法。它充分利用了生物蚁群能通过个体间简单的信息传递，搜索从蚁巢至食物间最短路径的集体寻优特征，以及该过程与旅行商问题求解之间的相似性。得到了具有NP难度的旅行商问题的最优解答。同时，该算法还被用于求解Job-Shop调度问题、二次指派问题以及多维背包问题等，显示了其适用于组合优化类问题求解的优越特征。
多年来世界各地研究工作者对蚁群算法进行了精心研究和应用开发，该算法现已被大量应用于数据分析、机器人协作问题求解、电力、通信、水利、采矿、化工、建筑、交通等领域。
蚁群算法之所以能引起相关领域研究者的注意，是因为这种求解模式能将问题求解的快速性、全局优化特征以及有限时间内答案的合理性结合起来。其中，寻优的快速性是通过正反馈式的信息传递和积累来保证的。而算法的早熟性收敛又可以通过其分布式计算特征加以避免，同时，具有贪婪启发式搜索特征的蚁群系统又能在搜索过程的早期找到可以接受的问题解答。这种优越的问题分布式求解模式经过相关领域研究者的关注和努力，已经在最初的算法模型基础上得到了很大的改进和拓展。
经过一定时间，从食物源返回的蚂蚁到达D点同样也碰到障碍物，也需要进行选择。此时A, B两侧的信息素浓度相同，它们仍然一半向左，一半向右。但是当A侧的蚂蚁已经完全绕过障碍物到达C点时，B侧的蚂蚁由于需走的路径更长，还不能到达C点，图3表示蚁群在障碍物前经过一段时间后的情形。
此时对于从蚁巢出发来到C点的蚂蚁来说，由于A侧的信息素浓度高，B侧的信息素较低，就倾向于选择A侧的路径。这样的结果是A侧的蚂蚁越来越多，最终所有蚂蚁都选择这条较短的路径，图4 表示蚁群最终选择的路径
上述过程，很显然是由蚂蚁所留下的信息素的“正反馈”过程而导致的。蚂蚁个体就是通过这种信息的交流来达到搜索食物的目的。蚁群算法的基本思想也是从这个过程转化而来的。
蚁群算法的特点：
1)蚁群算法是一种自组织的算法。在系统论中，自组织和它组织是组织的两个基本分类，其区别在于组织力或组织指令是来自于系统的内部还是来自于系统的外部，来自于系统内部的是自组织，来自于系统外部的是他组织。如果系统在获得空间的、时间的或者功能结构的过程中，没有外界的特定干预，我们便说系统是自组织的。在抽象意义上讲，自组织就是在没有外界作用下使得系统熵减小的过程(即是系统从无序到有序的变化过程)。蚁群算法充分体现了这个过程，以蚂蚁群体优化为例子说明。当算法开始的初期，单个的人工蚂蚁无序的寻找解，算法经过一段时间的演化，人工蚂蚁间通过信息激素的作用，自发的越来越趋向于寻找到接近最优解的一些解，这就是一个无序到有序的过程。
2)蚁群算法是一种本质上并行的算法。每只蚂蚁搜索的过程彼此独立，仅通过信息激素进行通信。所以蚁群算法则可以看作是一个分布式的多agent系统，它在问题空间的多点同时开始进行独立的解搜索，不仅增加了算法的可靠性，也使得算法具有较强的全局搜索能力。
3)蚁群算法是一种正反馈的算法。从真实蚂蚁的觅食过程中我们不难看出，蚂蚁能够最终找到最短路径，直接依赖于最短路径上信息激素的堆积，而信息激素的堆积却是一个正反馈的过程。对蚁群算法来说，初始时刻在环境中存在完全相同的信息激素，给予系统一个微小扰动，使得各个边上的轨迹浓度不相同，蚂蚁构造的解就存在了优劣，算法采用的反馈方式是在较优的解经过的路径留下更多的信息激素，而更多的信息激素又吸引了更多的蚂蚁，这个正反馈的过程使得初始的不同得到不断的扩大，同时又引导整个系统向最优解的方向进化。因此，正反馈是蚂蚁算法的重要特征，它使得算法演化过程得以进行。
4)蚁群算法具有较强的鲁棒性。相对于其它算法，蚁群算法对初始路线要求不高，即蚁群算法的求解结果不依赖于初始路线的选择，而且在搜索过程中不需要进行人工的调整。其次，蚁群算法的参数数目少，设置简单，易于蚁群算法应用到其它组合优化问题的求解。
蚁群算法的应用进展以蚁群算法为代表的蚁群智能已成为当今分布式人工智能研究的一个热点，许多源于蜂群和蚁群模型设计的算法己越来越多地被应用于企业的运转模式的研究。美国五角大楼正在资助关于群智能系统的研究工作-群体战略(Swarm Strategy)，它的一个实战用途是通过运用成群的空中无人驾驶飞行器和地面车辆来转移敌人的注意力，让自己的军队在敌人后方不被察觉地安全进行。英国电信公司和美国世界通信公司以电子蚂蚁为基础，对新的电信网络管理方法进行了试验。群智能还被应用于工厂生产计划的制定和运输部门的后勤管理。美国太平洋西南航空公司采用了一种直接源于蚂蚁行为研究成果的运输管理软件，结果每年至少节约了1000万美元的费用开支。英国联合利华公司己率先利用群智能技术改善其一家牙膏厂的运转情况。美国通用汽车公司、法国液气公司、荷兰公路交通部和美国一些移民事务机构也都采用这种技术来改善其运转的机能。鉴于群智能广阔的应用前景，美国和欧盟均于近几年开始出资资助基于群智能模拟的相关研究项目，并在一些院校开设群体智能的相关课程。国内，国家自然科学基金”十五”期间学科交叉类优先资助领域中的认知科学及其信息处理的研究内容中也明确列出了群智能领域的进化、自适应与现场认知主题。
蚁群优化算法最初用于解决TSP问题，经过多年的发展，已经陆续渗透到其他领域中，比如图着色问题、大规模集成电路设计、通讯网络中的路由问题以及负载平衡问题、车辆调度问题等。蚁群算法在若干领域己获得成功的应用，其中最成功的是在组合优化问题中的应用。
在网络路由处理中，网络的流量分布不断变化，网络链路或结点也会随机地失效或重新加入。蚁群的自身催化与正向反馈机制正好符合了这类问题的求解特点，因而，蚁群算法在网络领域得到一定应用。蚁群觅食行为所呈现出的并行与分布特性使得算法特别适合于并行化处理。因而，实现算法的并行化执行对于大量复杂的实际应用问题的求解来说是极具潜力的。
在某群体中若存在众多无智能的个体，它们通过相互之间的简单合作所表现出来的智能行为即称为集群智能(Swarm Intelligence)。互联网上的交流，不过是更多的神经元连接(人脑)通过互联网相互作用的结果，光缆和路由器不过是轴突和突触的延伸。从自组织现象的角度上看，人脑的智能和蚁群也没有本质上的区别，单个神经元没有智能可言，单个蚂蚁也没有，但是通过连接形成的体系，是一个智能体。（作者： 李精灵 编选：中国电子商务研究中心）

❹ 蚁群算法及其应用实例

       蚁群算法(ant colony optimization, ACO)，又称蚂蚁算法，是一种对自然界蚂蚁的寻径方式进行模拟而得到的一种仿生算法，是一种用来在图中寻找优化路径的机率型算法。
       蚂蚁在运动过程中，可以在行走的路径上留下信息素，后来的蚂蚁可以感知到信息素的存在，信息素浓度越高的路径越容易被后来的蚂蚁选择，从而形成一种正反馈现象。
       它能够求出从原点出发，经过若干个给定的需求点，最终返回原点的最短路径。这也就是着名的旅行商问题(Traveling Saleman Problem，TSP)。

       若蚂蚁从A点出发到D点觅食，它可以随机从ABD或ACD中选择一条路。假设初始时为每条路分配一只蚂蚁，每个时间单位行走一步，则经过8个时间单位后，情形如下图所示：ABD路线的蚂蚁到达D点，ACD路线的蚂蚁到达C点。

       那么，再过8个时间单位，很容易可以得到下列情形：ABD路线的蚂蚁回到A点，ACD路线的蚂蚁到达D点。

α 代表信息素量对是否选择当前路径的影响程度，反映了蚁群在路径搜索中随机性因素作用的强度。
α 越大，蚂蚁选择以前走过的路径的可能性越大，搜索的随机性就会减弱。
α 过小，会导致蚁群搜索过早陷入局部最优，取值范围通常为[1,4]。

β 反映了启发式信息在指导蚁群搜索中的相对重要程度，蚁群寻优过程中先验性、确定性因素作用的强度。
β 过大，虽然收敛速度加快，但是易陷入局部最优。
β 过小，蚁群易陷入纯粹的随机搜索，很难找到最优解。通常取[0,5]。

ρ 反映了信息素的蒸发程度，相反，1-ρ 表示信息素的保留水平
ρ 过大，信息素会发过快，容易导致最优路径被排除。
ρ 过小，各路径上信息素含量差别过小，以前搜索过的路径被在此选择的可能性过大，会影响算法的随机性和全局搜索能力。通常取[0.2,0.5]。

m过大，每条路径上信息素趋于平均，正反馈作用减弱，从而导致收敛速度减慢。
m过小，可能导致一些从未搜索过的路径信息素浓度减小为0，导致过早收敛，解的全局最优性降低

总信息量Q对算法性能的影响有赖于αβρ的选取，以及算法模型的选择。
Q对ant-cycle模型蚁群算法的性能没有明显影响，不必特别考虑，可任意选取。

❺ 蚁群算法的执行结果一定收敛与全局最优解吗

什么是启发式算法转自：p://blog.csdn.net/aris_zzy/archive/2006/05/27/757156.aspx引言：解决实际的问题，要建模型，在求解。求解要选择算法，只有我们对各种算法的优缺点都很熟悉后才能根据实际问题选出有效的算法。但是对各种算法都了如指掌是不现实的，但多知道一些，会使你的选择集更大，找出最好算法的概率越大。现在研一，要开题了些点文献综述，愿与大家分享。大自然是神奇的，它造就了很多巧妙的手段和运行机制。受大自然的启发，人们从大自然的运行规律中找到了许多解决实际问题的方法。对于那些受大自然的运行规律或者面向具体问题的经验、规则启发出来的方法，人们常常称之为启发式算法（Heuristic Algorithm）。现在的启发式算法也不是全部来自然的规律，也有来自人类积累的工作经验。启发式算法的发展：启发式算法的计算量都比较大，所以启发式算法伴随着计算机技术的发展，取得了巨大的成就。40年代：由于实际需要，提出了启发式算法（快速有效）。50年代：逐步繁荣，其中 贪婪算法和局部搜索 等到人们的关注。60年代: 反思，发现以前提出的启发式算法速度很快，但是解得质量不能保证，而且对大规 模的问题仍然无能为力（收敛速度慢）。启发式算法的不足和如何解决方法：（水平有限 仅仅提出6点）启发式算法目前缺乏统一、完整的理论体系。很难解决！ 启发式算法的提出就是根据经验提出，没有什么坚实的理论基础。由于NP理论，启发式算法就解得全局最优性无法保证。等NP？=P有结果了再说吧，不知道这个世纪能不能行。各种启发式算法都有个自优点如何，完美结合。如果你没有实际经验，你就别去干这个，相结合就要做大量尝试，或许会有意外的收获。启发式算法中的参数对算法的效果起着至关重要的作用，如何有效设置参数。还是那句话，这是经验活但还要悟性，只有try again………..启发算法缺乏有效的迭代停止条件。还是经验，迭代次数100不行，就200，还不行就1000…………还不行估计就是算法有问题，或者你把它用错地方了………..启发式算法收敛速度的研究等。你会发现，没有完美的东西，要快你就要付出代价，就是越快你得到的解也就远差。其中（４）集中反映了超启发式算法的克服局部最优的能力。虽然人们研究对启发式算法的研究将近５０年，但它还有很多不足：1.启发式算法目前缺乏统一、完整的理论体系。2.由于NP理论，各种启发式算法都不可避免的遭遇到局部最优的问题，如何判断3.各种启发式算法都有个自优点如何，完美结合。4.启发式算法中的参数对算法的效果起着至关重要的作用，如何有效设置参数。5.启发算法缺乏有效的迭代停止条件。6.启发式算法收敛速度的研究等。70年代：计算复杂性理论的提出，NP问题。许多实际问题不可能在合理的时间范围内找到全局最优解。发现贪婪算法和局部搜索算法速度快，但解不好的原因主要是他们只是在局部的区域内找解，等到的解没有全局最优性。 由此必须引入新的搜索机制和策略……….. Holland的遗传算法出现了（Genetic Algorithm）再次引发了人们研究启发式算法的 兴趣。80年代以后： 模拟退火算法（Simulated Annealing Algorithm），人工神经网络（Artificial Neural Network），禁忌搜索（Tabu Search）相继出现。 最近比较热或刚热过去的：演化算法（Evolutionary Algorithm）, 蚁群算法（Ant Algorithms）， 拟人拟物算法，量子算法等。各个算法的思想这就不再详细给出（以后会给出一些，关注我的blog） ，为什么要引出启发式算法，因为NP问题，一般的经典算法是无法求解，或求解时间过长，我们无法接受。这里要说明的是：启发式算法得到的解只是近似最优解（近似到什么程度，只有根据具体问题才能给出）. 二十一世纪的最大的数学难题NP？=P，如果NP=P启发式算法就不在有存在的意义。 优胜劣汰是大自然的普遍规律，它主要通过选择和变异来实现。选择是优化的基本思想，变异（多样化）是随机搜索或非确定搜索的基本思想。“优胜劣汰”是算法搜索的核心，根据“优胜劣汰”策略的不同，可以获得不

❻ 蚁群算法求函数的最小值

未定义函数或变量 'max_global'。
出错 ant_main_program (line 107)
if max_local(i_ger) > max_global(i_ger-1)
怎么解决