浅析蚁群算法及其应用

打开文本图片集

摘要：蚁群算法是人工智能领域的一种模拟进化算法，在求解复杂优化问题方面具有一定的优势，是一种很有发展前景的计算智能方法。本文首先了解并分析了蚁群算法的基本原理，接着阐述了它的经典应用，最后总结了该算法的优点与不足。

Abstract： Ant colony algorithm is a simulated evolutionary algorithm in the field of artificial intelligence. It has certain advantages in solving complex optimization problems and is a promising computational intelligence method. This paper first analyzes the basic principle of ant colony algorithm， then expounds its classical application， and finally summarizes the advantages and disadvantages of the algorithm.

關键词：人工智能;蚁群算法;应用

Key words： artificial intelligence;ant colony algorithm;application

中图分类号：TP301.6                                    文献标识码：A                                  文章编号：1006-4311（2019）08-0156-04

0  引言

20世纪90年代中期，Italy科学家M.Dorigo根据动物的觅食过程，首先引出了蚁群算法（Ant Colony Optimization，ACO）。部分研究学者将蚁群算法引入到TSP（Traveling Saleman Problem）旅商问题、JSP（Job-shop Scheduling Problem）调度问题和QAP（Quadratic Assignment Problem）分配问题的研究之中，并取得了较好的研究成果。蚁群算法虽然提出的时间较短，但由于其分布运算和正反馈等特点，易于发现问题最优解，现已推广应用到多个研究领域。

1  蚁群算法的基本原理

ACO算法是模仿生态界中蚂蚁、昆虫的觅食行为提出的，为了详细了解该算法的基本原理，我们先对生态界中昆虫的觅食过程进行详细的了解。蚂蚁在寻找食物行为中，蚂蚁个体会散发出一种信息素（Pheromone）物质，多个个体之间可以通过该物质进行沟通，蚂蚁个体通过探知周围该物质的强度来指引觅食行为的行走路径。

如图1所示：为蚂蚁觅食路径的寻优过程，在图a中，当蚂蚁到达道路分岔口处时，无法确定往上最优还是向下最优？蚁群随机进入两个道路岔口，由统计学原理可知，蚂蚁向上或向下走的几率一样，均为二分之一。假设所有蚂蚁的行走速度一致，则b、c图为接下来发生的蚂蚁觅食行为路线。由于下方行走距离较少，则在相同的时间范围内有较多的觅食个体通过，进而散发出更多的Pheromone，如图所示：虚线为蚂蚁分泌信息素的强度，经过一段时间以后，下方行走路线上聚集的信息素越来越多形成d图，新出来觅食的蚂蚁则有更大的可能性选择下方行走路线，通过寻优路径的循环进行，造成局部行走路径该信息素物质累积。到最后，所有觅食昆虫个体均行进在下方距离较短的觅食路线。

M.Dorigo等专家学者在蚂蚁、蜜蜂等昆虫寻找食物过程研究的基础之上，提出了ACO算法。同时，将算法中的单个个体称为“人工蚂蚁”，如图2所示，我们通过具体的实例对蚁群算法进行具体的研究。假设A点为蚂蚁觅食出发点，E点为待寻觅食物目标地址，FC为蚁群觅食出发点A通往待寻觅食物目标点E道路上的路障，蚂蚁个体不能够翻越障碍FC到达食物源E处。设单个时间范围内总计有40只觅食昆虫个体分别从出发点A到节点B和从食物源E到路径节点D，设蚂蚁个体经过后留有蚁群信息素浓度为1，且经过单个时间信息素发挥结束。当T=0开始阶段，BC、CD、BF、FD蚂蚁觅食行径路径上均没有Pheromone物质存在;在接下来的过程中，B点的蚂蚁以相同的概率和速度分别往F、C出发，D点的蚂蚁分别以相同的概率和速度分别往F、C点出发，由此可得：

T=1时刻，分别有40只蚂蚁在B、D点;

T=2时刻，在B点和D点各有20只蚂蚁，且有40只觅食蚂蚁个体行进到了F点。

同时，各条线段上蚂蚁挥发出的信息素浓度分别为：AB=DE=BC=CD=40，BF=FD=20。由此可见：BCD行进道路上的不同个体之间交流物质浓度明显高于BFD行进道路之上，随着时间上的推移，有更多新出去觅食的昆虫个体选择觅食行进道路BCD，最后直至所有觅食的个体均通过BCD觅食道路外出觅食，由上可知，蚂蚁觅食道路寻优为一种通过不同个体之间信息交流沟通而得到了信息素正积累过程。

2  蚁群算法的模型

在个体外出觅食道路寻优阶段中，假设于某一时刻t，用bi（t）来表示地点i处的觅食个体的多少，用τij（t）用来形容由i点出发到目标点j之间行进道路上的分泌用于不同个体之间交流的信息素物质浓度，假设总共存在m只蚂蚁于n个目标点寻觅食物，dij（i，j？哿n）为觅食点i到j之间的距离，则存在等式：

本文在研究蚁群算法基本模型的过程中，假设在n个觅食节点有m只蚂蚁觅食，且蚂蚁在觅食过程中根据一定的因素确定下一个未访问过的觅食节点。同时，当蚂蚁由出发点移动到目标点或遍寻完所有路径节点之后，及时将各个路径上的分泌获得的信息素浓度τij（t）从新更新。在觅食过程t时刻，觅食路径节点集合C中，不同觅食节点之间的信息素分泌残留浓度，如式（2）所示，在开始阶段，不同觅食道路上用于不同个体之间交流的初始信息物质量相同，即τij（0）=Const为常数，蚂蚁在觅食遍寻过程中，根据信息素残留浓度等一定规则确定蚁群未来的行进路线，研究学者将该算法模型規则称之为“随机比概率”规则，由此可得，外出觅食昆虫个体从觅食出发点i到觅食目标点j的随机行进概率可表述为：

式中：■表示觅食昆虫个体k当时间为t时由觅食出发位置i到觅食行径路径中点j的行走转移可行性;α表示为外出觅食昆虫个体在觅食行进道路上用于不同个体之间用于交流的信息物质的剩余量对蚁群转移路线作用的诱发因子;β为启发式信息对觅食昆虫个体行进方向作用的期望诱发因素;■表示为蚂蚁k在觅食过程中下一步可行进路径节点，tabk为tab表，意义为记录蚂蚁k行进路线过程的路径记录表。蚂蚁在接下的行进过程中，不能够再次去往tab表中已经存在记录的觅食节点。蚂蚁按照以上行进路线遍寻完所有节点，并最终形成一个闭合路径。待所有蚂蚁均完成所有地点的觅食遍寻过程，即本次觅食过程迭代完成。在下一时刻，从蚁穴新出去觅食蚂蚁根据更新后的信息素浓度，进行下一次路径迭代，并最终实现迭代路径最优过程。

同时，蚂蚁在行径过程中，移动行进规则遵循式：

式中，q表示为0到1区间范围内的一个随机变量，q0为事先确定在[0，1]范围内的一个常数，当q的取值大于q0时，J即为由蚁群算法转移概率■确定的下个觅食地点。在蚂蚁转移过程中，为了防止多余的信息分泌素过多引起启发信息淹没，因此当蚂蚁完成n个觅食地点的遍历以后，本文拟将所有的信息素物质进行整体更新，蚂蚁行走路径行为展示出了生物记忆特征，当有新的信息记忆碎片进入到大脑之后，大脑中原有记忆的信息将伴着时间的前进慢慢的消失。由此，当所有蚂蚁完成一次遍历循环以后，n个食物源节点之间所有路径中的信息素变化按如下方式更新：

根据以上研究成果，蚁群算法提出学者M.Dorigo结合蚁群行进过程中信息素浓度的变化规律，总结研究，分别获得了蚁群数量（Ant-Quantity）、蚁群周期（Ant-Cycle）和蚁群密度（Ant-Density）三种蚁群算法模型，其中，蚁群算法模型，从全局遍历出发，保证了信息素浓度随着蚂蚁行进时间的推移不断的累加更新，和其他两种模型相比正反馈效果明显较强，其具体求解过程如下所示：

3  蚁群算法的应用

3.1 蚁群算法求解VRP问题

本文以ACO算法在经典商旅问题求解的过程为例，详细阐述ACO问题求解过程的实现流程：

①定义系统在开始时刻t=0时，算法循环次数N=0，并规定最大循环次数Nmax，假设n个商旅待去城市中放置m个蚂蚁（代表商旅），赋予初始阶段节点i与节点j路径上蚁群信息素初始量τij（0）=Const，且Δτij（0）=0;②设置循环次数N=N+1;③假设蚂蚁路径记录表索引开始值1;④设置蚂蚁个数定义符合K=K+1;⑤蚂蚁行进过程中根据公式（2）选择下一个城市j的行进路线;⑥更新蚂蚁路径记录索引表tab，即把蚂蚁行径过的城市序号记录到索引表tab中;⑦若蚂蚁行经过所有城市则跳到步骤⑧，否则执行步骤④;⑧根据式（4）、（5）重设蚂蚁行经道路上的信息素情况;⑨若循环次数N？叟Nmax则循环过程截止，输出蚂蚁最短行走路径，否则清空tab表，重复步骤②。

算法在TSP经典商旅问题中的计算求解流程如图3。

3.2 蚁群算法在配送车辆优化过程中的应用

3.2.1 扫描算法原理

扫描（Sweep）算法定义为：在车辆调度过程中即以指定的待配送目标位置为原点，进行顺或逆时针方向扫描。在扫描进行过程中，每扫描到一个目标客户，就根据配送车辆最大容量确定该客户快件是否分配给该配送车辆;倘若超过该配送车辆容量限制，则换下一辆配送车辆服务该目标客户，如此依次反复扫描，直至所有客户待配送快件，均安排到配送车辆之上。

3.2.2 求解一般车辆调度模型

当采用ACO算法求解调度车辆（VRP）配送的过程中，本文首先采用Sweep扫描算法对所有目标点的快件逐一扫描并分配车辆。紧接着，利用ACO算法中的Ant-Cycle求解算法对目标客户地点的服务顺序智能排序。

在利用Sweep扫描算法对所有快件进行扫描并分配配送车辆的过程中，可能会获取多种快件车辆分组情况，为了获取最优车辆配送调度方案，本文依据所有目标客户点在极坐标中的角度位置分别和货物配送中心进行Sweep扫描分析，近而获取n（n为目标客户数量）个相异的扫描分组情况，并可根据扫描结果获得n种车辆配送方案，结合Ant-Cycle蚁群算法模型在以上获得的结果中确定得出最优的调度配送方案。具体求解过程如下：

Step1：将待配送快件分派到车辆上具体实施方法为：首先选用未使用的车辆k，在未分配的待派送快件中依据目标点位置，从角度最小开始为车辆k指定目标派送点，直到达到汽车容量上限为止，如果有剩余未分配快件，则重复上面快件配送车辆分配方法;

Step2：对已经分配好任务的车进行如下操作确定配送地点访问顺序，设配送车辆k分配的目标集合为Vk，且"Vk|=n，设定有m只蚂蚁，按照Ant-Cycle确定最优配送路径;

Step3：按照各配送目标点极坐标中角度的大小和车场位置，利用Sweep扫描确地定n条初始扫描线，重复n次Step1和Step2得到n种调度方案，比较得到最优配送路径解。

4  蚁群算法的优点与不足

蚁群算法作为模仿蚂蚁觅食行为的一种仿生学路径寻优计算方法，为研究VRP、TSP等复杂的路径寻优问题提供了一种新的解决思路，具有一定的先进性和智能性。但该算法起步于上世纪90年代，发展历史不长，在具体应用过程中仍存在有部分缺陷，下面对蚁群算法的优缺点依次进行阐述：

优点：作为仿生物觅食演化而来的蚁群算法，利用蚂蚁觅食过程中信息素浓度变化的原理，拥有较强的最短路径计算求解能力。同时蚁群算法中的分布计算特点避免了问题求解过程中过早收敛、利用贪婪式搜索能力在开始运算的早期即尽可能提供最短路径，节省了寻优路径求解时间。同时，蚁群算法具有较强的鲁棒性和并行计算能力，即仅通过蚂蚁之间分泌的信息素浓度变化即可实现不同个体之间的交流与信息沟通，适用范围较广。

缺点：在利用蚁群算法求解具体问题过程中，虽然不同蚂蚁之间可以通过信息素沟通，但是在种群过大的情况下，因为单个蚂蚁的不确定性特点，该算法难以在小段时间范围中求解出最优的行走路径，造成搜索时间过长;同时，在具体应用求解中容易陷入部分区域搜索停滞情况，即在运算过程中，当达到相应规模以后，存在部分个体发现求解结果一样的情况，进而造成搜索停滞，不利于求出行进最短的路径。

参考文献：

[1]李宁馨.采用不同算法求解车辆路径问题的对比分析[J].重庆工商大学学报（自然科学版），2014，31（5）：70-76.

[2]梁承姬，崔佳诚，丁一.基于混合蚁群算法的车辆路径问题研究[J].重庆交通大学学报（自然科学版），2016（3）.

[3]朱喜基.基于蚁群算法的旅行商问题的研究[J].无线互联科技，2012（11）：120-121.

[4]赵吉东.蚁群算法的改进策略研究[J].中国科技信息，2012（12）：149-150.