蚁群算法及算例.pptx

1、蚁 群 优 化 算 法 （ACO算法）,一、概述 二、蚂蚁系统（AS） 三、算例 四、改进的ACO算法,一、概述,（一）算法背景蚁群的自组织行为特征,1、高度结构化的组织虽然蚂蚁的个体行为极其 简单，但由个体组成的蚁群却构成高度结构化的社会 组织，蚂蚁社会的成员有分工，有相互的通信和信息 传递。 2、自然优化蚁群在觅食过程中，在没有任何提示 下总能找到从蚁巢到食物源之间的最短路径；当经过的 路线上出现障碍物时，还能迅速找到新的最优路径。 3、信息正反馈蚂蚁在寻找食物时，在其经过的路 径上释放信息素（外激素）。蚂蚁基本没有视觉，但能 在小范围内察觉同类散发的信息素的轨迹，由此来决定 何去何从，并

2、倾向于朝着信息素强度高的方向移动。 4、自催化行为某条路径上走过的蚂蚁越多，留下 的信息素也越多（随时间蒸发一部分），后来蚂蚁选择 该路径的概率也越高。,（二）算法的产生与发展,1、产生受蚁群觅食行为启发，意大利学者M.Dorigo 于1991年在其博士论文中首次系统地提出一种基于蚂蚁种群 的新型智能优化算法“蚂蚁系统（Ant system,简称AS）”， 并用该法求解旅行商问题，获得了较好的效果。 2、发展后来，提出者及许多研究者对该算法作了各种 改进，将其应用于更为广泛的领域，如图着色问题、二次分 配问题、工件排序问题、车辆路径问题、车间作业调度问题、 网络路由问题、大规模集成电路设计等。

3、近些年来，M.Dorigo 等人把蚂蚁算法进一步发展成一种通用的优化技术“蚁群优化 （Ant Colony Optimization,简称ACO）”，并将所有符合ACO 框架的算法称为“蚁群优化算法（ACO algorithm）”。 3、展望初步的研究结果已显示出ACO算法在求解复杂 优化问题，特别是离散优化问题方面的优越性。虽然严格的 理论基础尚未奠定，但从当前的应用效果来看，此算法具有 光明的发展前景。,（三）特点,（四）优点,二、蚂蚁系统（AS算法）最早的ACO算法,（一）算法基本思想（以旅行商为例说明）,1、根据具体问题设置多只蚂蚁，分头并行搜索。 2、每只蚂蚁完成一次周游后，在行进的

4、路上释放信息素，信息素量与解的质量成正比。 3、蚂蚁路径的选择根据信息素强度大小（初始信息素量设为相等），同时考虑两点之间的距离，采用随机的局部搜索策略。这使得距离较短的边，其上的信息素量较大，后来的蚂蚁选择该边的概率也较大。,4、每只蚂蚁只能走合法路线（经过每个城市 1次且仅1次），为此设置禁忌表来控制。 5、所有蚂蚁都搜索完一次就是迭代一次，每 迭代一次就对所有的边做一次信息素更新，原 来的蚂蚁死掉，新的蚂蚁进行新一轮搜索。 6、更新信息素包括原有信息素的蒸发和经过 的路径上信息素的增加。 7、达到预定的迭代步数，或出现停滞现象（所有蚂蚁都选择同样的路径，解不再变化），则算法结束，以当前最

5、优解作为问题的最优解。,（二）参数含义及符号,（三）计算公式,1、转移概率 计算公式：,2、启发式因子计算公式：,3、信息素计算公式,（四）算法步骤,（六）AS算法的优点与不足,三、算例5个点的货郎担问题,参数设置：,四、改进的蚁群优化算法,（一）带精英策略的蚂蚁系统,特点在信息素更新时给予当前最优解以额外的信息素量，使最优解得到更好的利用。找到全局最优解的蚂蚁称为“精英蚂蚁”。,（二）蚁群系统,规则和都是为了使搜索过程更具有指导性，即使蚂蚁的搜索主要集中在当前找出的最好解邻域内。规则则是为了使已选的边对后来的蚂蚁具有较小的影响力，以避免蚂蚁收敛到同一路径。,（三）最大最小蚂蚁系统,关于 的取

6、值，没有确定的方法，有的 书例子中取为0.01，10；有的书提出一个在最大 值给定的情况下计算最小值的公式。,（四）基于优化排序的蚂蚁系统,特点：每次迭代完成后，蚂蚁所经路径由小到大排序， 并根据路径长度赋予不同的权重，路径越短权重越大。 信息素更新时对 考虑权重的影响。,（六）一种新的自适应蚁群算法,特点：将ACS中的状态转移规则改为自适应伪随机 比率规则，动态调整转移概率，以避免出现 停滞现象。,说明：在ACS的状态转移公式中， 是给定的常数；在AACA中， 是随平均节点分支数ANB而变 化的变量。ANB较大，意味着下一步可选的城市较多， 也变大，表示选择信息素和距离最好的边的可能性增大；

7、反之减小。,（七）基于混合行为的蚁群算法,特点：按蚂蚁的行为特征将蚂蚁分成4类，称为4个子蚁群，各子蚁群按各自的转移规则行动，搜索路径，每迭代一次，更新当前最优解，按最优路径长度更新各条边上的信息素，如此直至算法结束。,蚂蚁行为蚂蚁在前进过程中，用以决定其下一步移动到哪个状态的规则集合。,五、蚁群算法与遗传、模拟退火算法的比较,实验结果表明： 1、蚁群算法所找出的解的质量最高，遗传算法次之，模拟退火算法最低。 2、蚁群算法的收敛速度最快，遗传算法次之，模拟退火算法最慢。蚁群算法之所以能够快速收敛到全局最优解，是因为该算法的个体之间不断进行信息交流和传递。单个个体容易收敛于局部最优，多个个体通过

8、合作可以很快地收敛于解空间的最优解的附近。,讨 论,1、对已学过的算法作出某种改进。 2、介绍自学的一种新的算法。 3、查阅文献，介绍某算法在某领域的一个应用。 4、应用某算法解决一个实际问题。,已 知 资 料 表,E,参数设置：,算 例,正常数，,蚂蚁 在本次周游中所走路径的长度。,当所有蚂蚁完成1次周游后，各路径上的信息素为：,开始时，令,信息素矩阵,至此出现了停滞现象，算法结束。 已找到最优解：AEDCBA,目标函 数值为9。,试用蚁群算法求解6个点的对称TSP。已知资料如下。,练 习,参数设置：,令,开始时，令,已 知 资 料 表,E,参数设置：,算 例,正常数，,蚂蚁 在本次周游中所走路