1．基本蚁群算法的机制原理

模拟蚂蚁群体觅食行为的ACO是作为一种新的计算智能模式引入的，该算法基于如下基本假设：

（1）蚂蚁之间通过信息素和环境进行通信。每只蚂蚁仅根据其周围的局部环境做出反应，也只对其周围的局部环境产生影响。

（2）蚂蚁对环境的反应由其内部模式决定。因为蚂蚁是基因生物，蚂蚁的微型实际上是其基因的适应性表现，即蚂蚁是反应型适应性主体。

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

由上述假设和分析可见，基本蚁群算法的寻优机制包含两个基本阶段：适应阶段和写作阶段。在适应阶段，各候选解根据积累的信息不断调整自身结构，路径上经过的蚂蚁越多，信息量越大，则该路径越容易被选择；时间越长，信息量会越小；在写作阶段，候选解之间通过信息交流，以期望产生性能更好的解，类似于学习自动机的学习机制。

对于一个传统的算法而言，比如说一个求无约束值的解析方法—牛顿法，由于算法各个组成部分完成的功能之和就等于算法最后抓奶哥完成的功能（具有加和性），所以不能看作是一个系统。然而在基本蚁群算法中，采用多只蚂蚁的求解结果明显好于单只蚂蚁的求解结果，因此不具有加和性，整体大于部分之和，因此基本蚁群算法是一个系统。自然界中蚁群具备系统的三个基本特征，即多元性、相关性和整体性，从而构成了一个系统。在这个系统中，蚂蚁的个体行为是系统的元素，蚁群行为的相互影响体现了系统相关性，而蚁群可以完成个体完成不了的任务，则体现了系统的完整性，显示出系统整体大于部分之和的整体突现原理。

最为对蚁群觅食行为抽象的蚁群算法，如果把算法本身看作一个整体，就会发现它具备了系统的特征，这也是仿生优化算法的最重要的特征之一。自然界中的真实蚁群行为是一个分布式系统，当蚁群需要完成某项工作时，其中的许多蚂蚁都为共同目的进行着同样的工作，而最终任务的完成不会由于某些个体的缺陷儿收到影响。每只人工蚂蚁在问题空间的多个点同时开始相互独立地构造问题解，而整个问题的求解不会因为某只人工蚂蚁无法成功获得解而受到影响。

ACO的另一个重要特征是自组织。最典型的自组织就是生物体，在生物学上有一个观点，即类似ant、bee这样的昆虫，由于个体作用简单，而个体之间的协作作用特别明显，因而可把他们当做一个整体来研究，甚至把他们看作一个独立的生物体。在这样的群落中，生物个体相互作用，协同完成某项群体工作，自然体现出很强的自组织特性。从抽象意义上讲，自组织就是在没有外界作用下使得系统熵增加的过程（即系统从无序到有序的进化过程）。基本蚁群算法体现了这一过程，以蚁群优化为例，当算法开始的初期，单只人工蚂蚁无序地寻找解，经过一段时间的算法演化，人工蚂蚁越来越趋向于寻找到接近最优解的一些解，这恰恰体现了从无序到有序的自组织进化。自组织大大增强了算法的鲁棒性，传统的算法都是针对某一问题而设计的，这往往建立在对该问题有了全面清晰认识的基础上，通常很难适应其他问题。而自组织的蚁群算法不需要对待求解问题的所有方面都有所认识，因为家容易用用到一类问题中。

2.熵

科学家发明了测量无序的量，它称为熵，熵也是混沌度，是内部无序结构的总量。未知的信息越多，熵越大。基于上述熵与热力学几率之间的关系，可以得出结论：系统的熵值直接反映了它所处状态的均匀程度，系统的熵值越小，它所处的状态越是有序，越不均匀；系统的熵值越大，它所处的状态越是无序，越均匀。系统总是力图自发地从熵值较小的状态向熵值较大（即从有序走向无序）的状态转变，这就是隔离系统“熵值增大原理”的微观物理意义。　

3．TSP

TSP可分为对称TSP（symmetric traveling salesmanproblem）和非对称TSP（asymmetric traveling salesman problem）两大类，若两城市往返的距离相同，则为对称TSP，否则为非对称TSP。

对于个城市规模的TSP，则存在条不同的路径。（顺、逆时针）

转载本文请联系原作者获取授权，同时请注明本文来自丁力科学网博客。
链接地址：https://blog.sciencenet.cn/blog-1423136-800778.html

上一篇：航迹规划&ACO
下一篇：彷徨