智能算法—蚁群算法浅析作者：赵磊学校：西安建筑科技大学院系：应用数学年级：09级学号：00000摘要:智能算法在在现代生活、工程实践中应用比较广泛,主要是用来解决优化问题.本文主要研究智能算法在优化问题中的应用，智能算法包含种类较多，如遗传算法、蚁群算法、模拟退火法等,这些算法在解决优化问题时，都有其独特之处.本文主要对蚁群算法的起源、算法原理、特点和应用进行简单介绍。

关键词：智能算法、蚁群算法、算法概述、算法原理随着信息技术的发展，许多新方法和技术进入工程化、产品化阶段，这对自动控制技术提出新的挑战，促进了智能理论在控制技术中的应用，以解决用传统的方法难以解决的复杂系统的控制问题。

随着计算机技术的飞速发展，智能计算方法的应用领域也越来越广泛。

以及常用智能算法有:遗传算法、蚁群算法、免疫算法等。

蚁群算法是近些年来迅速发展起来的，并得到广泛应用的一种新型模拟进化优化算法。

研究表明该算法具有并行性，鲁棒性等优良性质。

它广泛应用于求解组合优化问题，所以本文着重介绍了这种智能计算方法，即蚁群算法，阐述了其工作原理和特点，同时对蚁群算法的前景进行了展望。

一、蚁群算法概述1、起源蚁群算法(ant colony optimization, ACO)，又称蚂蚁算法，是一种用来在图中寻找优化路径的机率型技术。

它由Marco Dorigo于1992年在他的博士论文中引入，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。

Deneubourg及其同事(Deneubourg et al.,1990; Goss et al.,1989)在可监控实验条件下研究了蚂蚁的觅食行为，实验结果显示这些蚂蚁可以通过使用一种称为信息素的化学物质来标记走过的路径，从而找出从蚁穴到食物源之间的最短路径。

在蚂蚁寻找食物的实验中发现，信息素的蒸发速度相对于蚁群收敛到最短路径所需的时间来说过于缓慢，因此在模型构建时，可以忽略信息素的蒸发。

然而当考虑的对象是人工蚂蚁时，情况就不同了。

实验结果显示，对于双桥模型和扩展双桥模型这些简单的连接图来说，同样不需要考虑信息素的蒸发。

相反，在更复杂的连接图上，对于最小成本路径问题来说，信息素的蒸发可以提高算法找到好解的性能。

2、基于蚁群算法的机制原理模拟蚂蚁群体觅食行为的蚁群算法是作为一种新的计算智能模式引入的，该算法基于如下假设：（1）蚂蚁之间通过信息素和环境进行通信。

每只蚂蚁仅根据其周围的环境作出反应，也只对其周围的局部环境产生影响。

（2）蚂蚁对环境的反应由其内部模式决定。

因为蚂蚁是基因生物，蚂蚁的行为实际上是其基因的自适应表现，即蚂蚁是反应型适应性主体。

（3）在个体水平上，每只蚂蚁仅根据环境作出独立选择；在群体水平上，单只蚂蚁的行为是随机的，但蚁群可通过自组织过程形成高度有序的群体行为。

由上述假设和分析可见，基本蚁群算法的寻优机制包括两个基本阶段：适应阶段和协作阶段。

在适应阶段，各侯选解根据积累的信息不断调整自身结构，路径上经过的蚂蚁越多，信息量越大，则该路径越容易被选择；时间越长，信息量会越小，在协作阶段，侯选解之间通过信息交流，以期望产生性能更好的解，类似于学习自动机的学习机制。

蚁群算法实际上是一类智能多主体系统，其自组织机制使得蚁群算法需要对所求问题的每一个方面都有详尽的认识。

自组织本质上是蚁群算法机制在没有外界作用下使系统熵增加的动态过程，体现了无序到有序的动态变化。

先将具体的组合优化问题表述成规范的格式，然后利用蚁群算法在“探索（exploration）”和“利用(exploitation)”之间根据信息素这一反馈载体确定决策点，同时按照相应的信息素更新规则对每只蚂蚁个体的信息素进行增量构建，随后从整体角度规划出蚁群活动的行为方向，周而复始，即可求出组合优化问题的最优解。

二、蚁群算法的原理蚁群算法是一种模拟进化算法，初步的研究表明该算法具有许多优良的性质。

针对PID控制器参数优化设计问题，将蚁群算法设计的结果与遗传算法设计的结果进行了比较，数值仿真结果表明，蚁群算法具有一种新的模拟进化优化方法的有效性和应用价值。

蚁群算法是一种求解组合最优化问题的新型通用启发式方法，该方法具有正反馈、分布式计算和富于建设性的贪婪启发式搜索的特点。

预期的结果：各个蚂蚁在没有事先告诉他们食物在什么地方的前提下开始寻找食物。

当一只找到食物以后，它会向环境释放一种信息素，吸引其他的蚂蚁过来，这样越来越多的蚂蚁会找到食物！有些蚂蚁并没有象其它蚂蚁一样总重复同样的路，他们会另辟蹊径，如果令开辟的道路比原来的其他道路更短，那么，渐渐，更多的蚂蚁被吸引到这条较短的路上来。

最后，经过一段时间运行，可能会出现一条最短的路径被大多数蚂蚁重复着。

事实上，每只蚂蚁并不是像我们想象的需要知道整个世界的信息，他们其实只关心很小范围内的眼前信息，而且根据这些局部信息利用几条简单的规则进行决策，这样，在蚁群这个集体里，复杂性的行为就会凸现出来。

这就是人工生命、复杂性科学解释的规律！那么，这些简单规则是什么呢？下面详细说明：1、范围：蚂蚁观察到的范围是一个方格世界，蚂蚁有一个参数为速度半径（一般是3），那么它能观察到的范围就是3*3个方格世界，并且能移动的距离也在这个范围之内。

2、环境：蚂蚁所在的环境是一个虚拟的世界，其中有障碍物，有别的蚂蚁，还有信息素，信息素有两种，一种是找到食物的蚂蚁洒下的食物信息素，一种是找到窝的蚂蚁洒下的窝的信息素。

每个蚂蚁都仅仅能感知它范围内的环境信息。

环境以一定的速率让信息素消失。

3、觅食规则：在每只蚂蚁能感知的范围内寻找是否有食物，如果有就直接过去。

否则看是否有信息素，并且比较在能感知的范围内哪一点的信息素最多，这样，它就朝信息素多的地方走，并且每只蚂蚁多会以小概率犯错误，从而并不是往信息素最多的点移动。

蚂蚁找窝的规则和上面一样，只不过它对窝的信息素做出反应，而对食物信息素没反应。

4、移动规则：每只蚂蚁都朝向信息素最多的方向移，并且，当周围没有信息素指引的时候，蚂蚁会按照自己原来运动的方向惯性的运动下去，并且，在运动的方向有一个随机的小的扰动。

为了防止蚂蚁原地转圈，它会记住最近刚走过了哪些点，如果发现要走的下一点已经在最近走过了，它就会尽量避开。

5、避障规则：如果蚂蚁要移动的方向有障碍物挡住，它会随机的选择另一个方向，并且有信息素指引的话，它会按照觅食的规则行为。

6、播撒信息素规则：每只蚂蚁在刚找到食物或者窝的时候撒发的信息素最多，并随着它走远距离，播撒的信息素越来越少。

根据这几条规则，蚂蚁之间并没有直接的关系，但是每只蚂蚁都和环境发生交互，而通过信息素这个纽带，实际上把各个蚂蚁之间关联起来了。

比如，当一只蚂蚁找到了食物，它并没有直接告诉其它蚂蚁这儿有食物，而是向环境播撒信息素，当其它的蚂蚁经过它附近的时候，就会感觉到信息素的存在，进而根据信息素的指引找到了食物。

通过上面的原理叙述和实际操作，我们不难发现蚂蚁之所以具有智能行为，完全归功于它的简单行为规则，而这些规则综合起来具有下面两个方面的特点：1、多样性2、正反馈多样性保证了蚂蚁在觅食的时候不置走进死胡同而无限循环，正反馈机制则保证了相对优良的信息能够被保存下来。

我们可以把多样性看成是一种创造能力，而正反馈是一种学习强化能力。

正反馈的力量也可以比喻成权威的意见，而多样性是打破权威体现的创造性，正是这两点小心翼翼的巧妙结合才使得智能行为涌现出来了。

引申来讲，大自然的进化，社会的进步、人类的创新实际上都离不开这两样东西，多样性保证了系统的创新能力，正反馈保证了优良特性能够得到强化，两者要恰到好处的结合。

如果多样性过剩，也就是系统过于活跃，这相当于蚂蚁会过多的随机运动，它就会陷入混沌状态；而相反，多样性不够，正反馈机制过强，那么系统就好比一潭死水。

这在蚁群中来讲就表现为，蚂蚁的行为过于僵硬，当环境变化了，蚂蚁群仍然不能适当的调整。

三、蚁群算法的特点蚁群算法同目前流行的遗传算法、人工神经网络、微粒群算法、人工免疫算法、人工鱼群算法等都属于仿生优化算法，它们都属于一类模拟自然界生物系统、完全依赖于生物体本能、通过无意识寻优行为来优化其生存状态以适应环境需要的最优化智能算法。

因此，这些仿生优化算法有许多相同的特点。

是一种基于多个智能体的仿生优化算法仿生优化算法中的各个智能体之间通过相互协作来更好地适应环境，表现出与环境交互的能力具有本质并行性仿生优化算法的本质并行性表现在两个方面：一是仿生优化计算的内在并行性（inherent parallelism），即仿生优化算法本身非常适合大规模并行；二是仿生优化计算的内含并行性(implicit parallelism)，这使得仿生优化算法能以较少的计算获得较大的收益具有突现性仿生优化算法总目标的完成是在多个智能个体行为的运动过程中突现出来的都具有自组织性和进化性在不确定的复杂时变环境中，仿生优化算法可通过自学习不断提高算法中个体的适应性具有稳健性仿生优化算法的稳健性是指在不同条件和环境下算法的适用性和有效性。

由于仿生优化算法不依赖于优化问题本身的严格数学性质和所求解问题本身的结构特征，因此用仿生优化算法求解许多不同问题时，只需要设计相应的评价函数（代价函数），而基本上无需修改算法的其他部分6. 是一类不确定的算法不确定性体现了自然界生物的生理机制，并且在求解某些特定问题方面优于确定算法。

仿生优化算法的不确定性是伴随其随机性而来的，其主要步骤含有随机因素，从而在算法的迭代过程中，事件发生与否带有很大的不确定性。

7. 是一类概率型的全局优化算法非确定算法的优点在于算法能有更多的机会求得全局最优解8. 不依赖于优化问题本身的严格数学性质在优化过程中都不依赖于优化问题本身的严格数学性质（如连续性、可导性）以及目标函数和约束条件的精确数学描述四、蚁群算法的应用自从M Dorigo等人首先将蚁群算法应用于旅行商问题（TSP）并获得了较大的成功后，该算法吸引了许多学者对其进行研究，并取得了一系列的研究成果。

除了TSP，蚂蚁算法还用于求解二次分配问题（quadratic assignment problem,简称QAP）、车间作业调度问题(job-shop scheduling problem,简称JSP)、背包问题(knapsack problem,简称KP)、车辆路径问题(vehicle routing problem,简称VRP)、图着色(graph coloring,简称GC)问题、网络路由(network route,简称NR)问题和机器人路径规划问题[等.蚁群算法可应用于各种组合优化问题、函数优化问题、机器人路径规划等问题，其关键是：（1）将待解决的问题表示成相应的权值图；（2）能定义一种正反馈过程（如TSP中的残留信息素）；（3）问题结构本身能提供解题用的启发式信息（TSP中城市间的距离）；（4）建立约束机制（如TSP中已访问城市的列表），就可以应用蚁群算法来求解该问题。