算法 计算机 超级计算 高性能 科学探索

1. 算法背景——蚁群的自组织行为特征

高度结构化的组织——虽然蚂蚁的个体行为极其简单，但由个体组成的蚁群却构成高度结构化的社会组织，蚂蚁社会的成员有分工，有相互的通信和信息传递。

自然优化——蚁群在觅食过程中，在没有任何提示下总能找到从蚁巢到食物源之间的最短路径；当经过的路线上出现障碍物时，还能迅速找到新的最优路径。

信息正反馈——蚂蚁在寻找食物时，在其经过的路径上释放信息素（外激素）。蚂蚁基本没有视觉，但能在小范围内察觉同类散发的信息素的轨迹，由此来决定何去何从，并倾向于朝着信息素强度高的方向移动。

自催化行为——某条路径上走过的蚂蚁越多，留下的信息素也越多（随时间蒸发一部分），后来蚂蚁选择该路径的概率也越高。

2. 算法基本思想：

（1）根据具体问题设置多只蚂蚁，分头并行搜索。

（2）每只蚂蚁完成一次周游后，在行进的路上释放信息素，信息素量与解的质量成正比。

（3）蚂蚁路径的选择根据信息素强度大小（初始信息素量设为相等），同时考虑两点之间的距离，采用随机的局部搜索策略。这使得距离较短的边，其上的信息素量较大，后来的蚂蚁选择该边的概率也较大。

（4）每只蚂蚁只能走合法路线（经过每个城市1次且仅1次），为此设置禁忌表来控制。

（5）所有蚂蚁都搜索完一次就是迭代一次，每迭代一次就对所有的边做一次信息素更新，原来的蚂蚁死掉，新的蚂蚁进行新一轮搜索。

（6）更新信息素包括原有信息素的蒸发和经过的路径上信息素的增加。

（7）达到预定的迭代步数，或出现停滞现象（所有蚂蚁都选择同样的路径，解不再变化），则算法结束，以当前最优解作为问题的最优解。

3. 信息素及转移概率的计算：

4. 算法步骤

算法流程图如下：

5. 举例分析

我们假设5个城市的TSP问题，然由于某种原因，城市道路均是单行道，即A->B和B->A的距离不相同，也就是说这是一个不对称的TSP问题。现在城市距离信息如下表：

设置参数：

m=5,α=1,β=1,ρ=0.5,τ_ij(0)=2。

第一次迭代第一只蚂蚁：

第一次迭代第二只蚂蚁

第一次迭代第三只蚂蚁：

第一次迭代第四只蚂蚁：

第一次迭代第五只蚂蚁：

第一次迭代完成，更新信息素矩阵，信息素挥发系数为0.5。

第一代蚂蚁全部累死，重新随机生成第二代蚂蚁进行迭代。

第二次迭代第一只蚂蚁：

第二次迭代第二只蚂蚁：

第二次迭代第三只蚂蚁：

第二次迭代第四只蚂蚁：

第二次迭代第五只蚂蚁：

至此，我们已经发现在第二次迭代的时候，五只蚂蚁走的是同一条路，所以算法收敛结束。    最优路径A->E->D->C->B->A, 最有路径的距离为9.

6. 算法特点：

是一种基于多主体的智能算法，不是单个蚂蚁行动，而是多个蚂蚁同时搜索，具有分布式的协同优化机制。

本质上属于随机搜索算法（概率算法），具有概率搜索的特征。

是一种全局搜索算法，能够有效地避免局部最优。