一群算法

❶ 蚁群算法的基本原理

基本原理：

某一条路径越短，路径上经过的蚂蚁越多，其信息素遗留的也就越多，信息素的浓度也就越高，蚂蚁选择这条路径的概率也就越大，由此构成了正反馈过程，从而逼近了最优路径，找到最优路径。当蚂蚁从食物源走到蚁穴，或者从蚁穴走到食物的地方，都会在经过的路上释放信息素，蚂蚁可以感觉出路径上信息素浓度的大小，并且以较高的概率选择信息素浓度较高的路径。

❷ 蚁群算法是什么

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

原理
设想，如果我们要为蚂蚁设计一个人工智能的程序，那么这个程序要多么复杂呢？首先，你要让蚂蚁能够避开障碍物，就必须根据适当的地形给它编进指令让他们能够巧妙的避开障碍物，其次，要让蚂蚁找到食物，就需要让他们遍历空间上的所有点；再次，如果要让蚂蚁找到最短的路径，那么需要计算所有可能的路径并且比较它们的大小，而且更重要的是，你要小心翼翼地编程，因为程序的错误也许会让你前功尽弃。这是多么不可思议的程序！太复杂了，恐怕没人能够完成这样繁琐冗余的程序。

然而，事实并没有你想得那么复杂，上面这个程序每个蚂蚁的核心程序编码不过100多行！为什么这么简单的程序会让蚂蚁干这样复杂的事情？答案是：简单规则的涌现。事实上，每只蚂蚁并不是像我们想象的需要知道整个世界的信息，他们其实只关心很小范围内的眼前信息，而且根据这些局部信息利用几条简单的规则进行决策，这样，在蚁群这个集体里，复杂性的行为就会凸现出来。这就是人工生命、复杂性科学解释的规律！那么，这些简单规则是什么呢？

❸ 蚁群算法及其应用实例

       蚁群算法(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模型蚁群算法的性能没有明显影响，不必特别考虑，可任意选取。

❹ TSP解决之道——蚁群算法

蚁群算法java实现以及TSP问题蚁群算法求解

蚁群算法原理与应用讲解

蚁群算法原理与应用1 -自然计算与群体智能

1、蚁群算法(Ant Clony Optimization,ACO)是一种群智能算法，它是由一群无智能或有轻微智能的个体（Agent）通过相互协作而表现出智能行为，从而为求解复杂问题提供了一个新的可能性。

2、是一种仿生学的算法，是由自然界中蚂蚁觅食的行为而启发。（artificial ants；双桥实验）

3、运作机理：当一定路径上通过的蚂蚁越来越多时，其留下的信息素轨迹也越来越多，后来蚂蚁选择该路径的概率也越高，从而更增加了该路径的信息素强度，而强度大的信息素会吸引更多的蚂蚁，从而形成一种正反馈机制。

4、蚁群算法欧化过程中的两个重要原则：

     a、蚂蚁在众多路径中转移路线的选择规则。

     b、全局化信息素更新规则。信息素更新的实质就是人工蚂蚁根据真实蚂蚁在访问过的边上留下的信息素和蒸发的信息素来模拟真实信息素数量的变化，从而使得越好的解得到越多的增强。这就形成了一种自催化强化学习(Autocatalytic Reinforcement Learning)的正反馈机制。

1、描述：蚂蚁数量m；城市之间的信息素矩阵pheromone；每次迭代的m个蚂蚁的最短路径    BestLength；最佳路径BestTour。                                                                                                                                     每只蚂蚁都有 ：禁忌表(Tabu)存储已访问过的城市，允许访问的城市表(Allowed)存储还可以访问的城市，矩阵（ Delta ）来存储它在一个循环（或者迭代）中给所经过的路径释放的信息素。

2、 状态转移概率 ：在搜索过程中，蚂蚁根据各条路径上的信息量及路径的启发信息来计算状态转移概率。在t时刻蚂蚁k由元素（城市）i转移到元素（城市）j的状态转移概率：

τij (t) ：时刻路径(i, j)上的信息量。ηij=1/dij ：启发函数。

α为信息启发式因子 ，表示轨迹的相对重要性，反映了蚂蚁在运动过程中积累的信息在蚂蚁运动时所起的作用，其值越大，则该蚂蚁越倾向于选择其它蚂蚁经过的路径，蚂蚁之间的协作性越强；

β为期望启发式因子 ，表示能见度的相对重要性，反映蚂蚁在运动过程中启发信息在蚂蚁选择路径中的受重视程度，其值越大，则该状态状态转移概率越接近于贪心规则；

3、 息素更新规则 ：

ρ表示信息素挥发系数；Δτij(t)表示本次循环中路径(i, j)上的信息素增量，初始时刻Δτij(t) =0。

4、三种信息增量计算方法：

区别：第一种利用了全局信息，在走一圈后更新。二、三中都利用的是局部信息。通常使用第一种。

5、TSP中流程图

❺ 铓佺兢绠楁硶镄勪紭缂虹偣

浼樼偣锛氩叿链夊叏灞浼桦寲鑳藉姏锛岃兘澶熷勭悊澶嶆潅镄勯潪绾挎ч梾棰桡纴鍏锋湁杈冨ソ镄勯瞾妫掓у拰阃傚簲镐с
1銆佺己镣癸细绠楁硶镄勬敹鏁涢熷害杈冩参锛岄渶瑕佸ぇ閲忕殑璁＄畻璧勬簮鍜岄暱镞堕棿镓嶈兘鍙戞尌姝ｅ弽棣堢殑浣灭敤銆