蚁群算法讲课

蚁群算法

主讲人：郝 娟

指导老师：张著洪

目录

1蚁群算法概述..............................................................................21

1.1蚁群算法的提出与发展.............................................................. 21

1.2蚁群算法原理.............................................................................. 22

1.3数学模型的建立.......................................................................... 25

2蚁群算法的仿真分析....................................................................... 29

2.1蚁群算法流程.......................................................................30

2.2蚁群算法的计算机仿真............................................................. 30

2.3分析与总结................................................................................. 34

3蚁群算法的优化............................................................................... 38

3.1基本蚁群算法的缺点................................................................. 38

3.2改进与优化方法......................................................................... 40

3.3优化蚁群算法方案的仿真分析................................................. 43

4小结................................................................................................... 44

第一章 蚁群算法概述

生物学家通过对蚂蚁的长期研究发现，虽然每只蚂蚁智能不高，也没有集中的指挥，但它们却可以协同工作，依靠群体能力发挥出超出个体的智能。蚁群算法(ant colony algorithm, ACA)是最新发展的一种模拟蚂蚁群体智能行为的仿生优化算法，具有较强的鲁棒性、分布式计算机制、易于与其它算法结合等优点。尽管目前蚁群算法的严格理论基础尚未奠定，国内外的相关研究还处在实验探索和初步应用阶段，但蚁群算法己经由当初的单一TSP旅行商问题领域渗透到多个应用领域，有着广泛的应用前景。

1蚁群算法的提出与发展

根据蚂蚁“寻找食物”的群体智能行为，意大利学者M.Dorigo于1991年在法国召开的第一届欧}}l}l人工生命会议(European Conference on Artificial Life, ECAL中第一次提出了蚁群算法的基本模型。到1992年，M.Dorigo又在其博士学位论文中进一步阐述了蚁群算法的核心思想。由于在模拟仿真中使用了人工蚂蚁的概念，因此也称蚂蚁系统(ant system, AS )。 近年来，蚁群算法逐渐被国内学者了解和研究，相继出现了一些介绍性的文献，其后在蚁群算法的应用研究方面(如组合优化问题、网络路由调度问题等)开展了许多研究工作。 2蚁群算法原理

2.1生物学原型

蚂蚁系统是最早建立的蚁群算法模型，其模型的建立来源于对蚂蚁寻找食物行为的研究。蚂蚁视力很有限，但是蚂蚁寻找食物的过程中却有能力在没有任何可见提示下找出从蚁穴到食物源的最短路径，并且能随环境的变化而变化，适应性地搜索新的路径，产生新的选择。

经过研究发现，在从食物源到蚁穴并返回的过程中，蚂蚁能在其走过的路径上分泌一种化学物质一信息素，通过这种方式形成信息素轨迹。信息素轨迹可以使蚂蚁找到其返回食物源(或蚁穴)的路径，其他蚂蚁也可以利用该轨迹找到由同伴发现的食物源的位置。由蚂蚁个体的特征可以看出，蚂蚁除了对信息素有感知外几乎无法获知环境的信息，因而当环境中不存在信息素时，蚂蚁的行为是完全随机的。也就是说，蚂蚁在一个新的环境中的初始行走是完全随机的。另外，蚂蚁的搜索不是孤立的。事实上，假如只有一只蚂蚁进行搜索，由于蚂蚁的短视，很难找到最佳路径。当蚂蚁走过一条路径时，在上面留下的信息素会吸引更多的 蚂蚁走这条路。当这条路径上通过的蚂蚁越来越多，以至信息素强度增大，后来蚂蚁选择该路径的概率也越高，从而更增加了该路径的信息素强度。

图2.1 蚁群的初始路径

图2.2 原来的路径上出现以障碍物

图2.3蚂蚁以同样的概率决定行进方向

图2.4蚁群最终选择较短的路径

2.2数学模型的建立

假定从A到E(或者从E到A)有两条路径(ABCDE和ABHDE)，其中B到H、D到H的距离为1, B到C和D到C的距离为0. 5(如图2. 5所示)。设每个单元时间有30个蚂蚁分别从A到B，同时有30个蚂蚁从E到D，每个蚂蚁以每单元时间1的速度行走，行走时在时刻t留下浓度为1的信息激素，为了简化模型便于说明，假定在每个连续时间段(t+1, t+2)的中间时间点，信息素瞬时完全挥发。下面分别考虑在时刻t =0，1 ,2„时蚁群的运动情况。

图2.5 初始图

在t=o时刻，图上没有“轨迹”，仅在B, D点各有30个蚂蚁，它们选择走哪一条道路完全是随机的，因此平均有15只蚂蚁走向H点，15只蚂蚁走向C点，如图2. 6所示。

图2.6蚂蚁以相同的概率选择路径

在t=1时刻，30个从A到B的“新”蚂蚁到通向H的路径上发现了浓度为15的轨迹(由上一时刻从B到H的15只蚂蚁留下)，同时发现了通向C的路径上有浓度为30的轨迹(由从B到C出发的15只蚂蚁加上从D到C到达B的15个蚂蚁留下的轨迹之和，如图2. 7所示。 因此，现在选择路径的概率就有了不同，在理想情况下走向C的蚂蚁数量应该是走向H的蚂蚁的数量的2倍，分别是20个和10个。从E到D的30个蚂蚁和以上情况相同。

图2.7 较短的边上有更多的信息素，更多的蚂蚁选择较短的边

这个过程持续下去的结果就是所有的蚂蚁都选择了较短的路径。

下面将以TSP问题为例，介绍蚁群算法数学模型的建立。TSP问题就是指给定n座城市和两两城市之间的距离，要求确定一条经过各城市当且仅当一次的最短路线。根据蚁群算法的思想和TSP问题的具体特征，求解TSP问题的人工蚁都是具有如下特征的简单主体:

1)在从城市i到城市J的运动过程中或是在完成一次循环后，蚂蚁在边(I,j)上产生信息素轨迹，该轨迹可以影响后来的蚂蚁，使得蚂蚁群体走向最优解。

2)蚂蚁概率地选择下一个将要访问的城市，这个概率由图中边上的轨迹浓度和问题空间的自启发因子共同决定;

TSP问题有一个特点，在完成一次循环之前，不允许第二次访问同一个城市。为了满足蚂蚁必须经过所有n座不同的城市这个约束条件，为每只蚂蚁都设计了一个禁忌表(tabu lis0。禁忌表记录了在t时刻蚂蚁己经走过的城市，不允许该蚂蚁在本次循环中再经过这些城市。当本次循环结束后，禁忌表被用来计算该蚂蚁当前所建立的解决方案。

为模拟实际蚂蚁的行为，首先引入如下记号:

m一一蚁群中蚂蚁数量;

bi(t)一一t时刻位于城市i的蚂蚁的个数, m= bi(t).

i=1N

dij一一两城市i和j之间的距离;

nij一一边((i,j)的能见度，反映由城市i转移到城市j的启发程度，这个量在

蚂蚁系统的运行中不改变;

τij一一边((i,j)上的信息素轨迹强度;

△τij一一蚂蚁k在边(i,j)上留下的单位长度轨迹信息素量;

k一一蚂蚁k的转移概率，J是尚未访问的城市。 pij

初始时刻，各条路径上的信息素量相等，设τij(0) =C (C为常数)。蚂蚁k(k=1, 2,……, m)在运动过程中根据各条路径上的信息素量决定转移方向。蚂蚁系统所使用的状态转移规则被称为随机比例规则，式3. 1给出了位于城市i的蚂蚁k选择移动到城市j的概率。在t时刻，

k蚂蚁k在城市i选择城市j的转移概率可pij(t)为

其中，j∈allowedkk={0,1,……,n-1}表示蚂蚁k下一步允许选择的城市。由上式可知，转移概率pij(t)与τij.ηij成正比，nij为能见度因数，。α和β为两个参数，分别反映了蚂蚁在运动过程中所积累的信息和启发信息在蚂蚁选择路径中的相对重要性。蚂蚁按照上述状态转移规则选择城市并最终形成一条封闭路径，当所有的蚂蚁完成了它们的闭合路径后即一次迭代结束。利用全局信息更新规则来更新路径的信息量，再开始下一次迭代直到达到最大迭代次数或最大停滞次数。

蚁群算法的全局信息更新规则如式(3. 2)、式(3. 3)、式(3. 4)所示

: kαβ

在全局信息素更新公式中:

ρ一表示信息残留的程度即旧的信息素相对于新增加的信息所占的比重。

Q一取为常数，其值与y,(0)有关。

Lk一第k只蚂蚁在本次循环中所走过的路径的长度。

K—当前迭代次数

M一一最大迭代次数。

在每次迭代的初始时刻，设△τij=0

M. Dorigo曾给出三种不同模型，分别称为蚁周系统(ant-cycle system)、蚁量系统(ant-quantity system)、蚁密系统(ant-density system)。它们的差别在于全局信息更新规则的不同

:

从上面三个表达式中不难看出，蚁密系统和蚁量系统两种模型中利用的是局部信息而蚁周系统利用的是整体信息。蚁周系统在求解TSP时性能较好因此常作为基本模型，称之为基本蚁群优化算法。蚁群算法中α,β,Q等参数对算法性能也有很大的影响。α值的大小表明留在每个结点上的信息量受重视的程度，α值越大，蚂蚁选择以前选过的点的可能性越大，但过大会使搜索过早陷于局部最小点; β的大小表明启发式信息受重视的程度;Q值会影响算法的收敛速度，Q过大会使算法收敛于局部最小值，过小又会影响算法的收敛速度，随着问题规模的增大Q的值也需要随之变化。算法的全局搜索参数Q, α,β,ρ可以用实验方法综合分析确定其取值，以获得更优的求解效率和效果。

2蚁群算法的仿真分析

通过上一节对蚁群算法的介绍和数学模型的建立，可以确定蚁群算法可使用软件程序进行计算机仿真分析，并可以根据仿真的结果进行分析和讨论。根据蚁群算法的数学模型，针对基本的TSP问题建立仿真模型，实现蚁群算法在TSP问题模型中的仿真分析。在仿真的过程中通过调整各个参数的值和TSP问题的规模，可以检验和分析蚁群算法中的参数对算法性能的影响，进而可以分析蚁群算法的空间复杂度和时间复杂度。

2.1蚁群算法流程

根据数学模型，可以确定用蚁群算法求解TSP问题的流程为:首先初始化蚂蚁和信息素浓度等数值以及禁忌表，然后计算蚂蚁移动的概率，进行蚂蚁的移动，同时不断计算每个蚂蚁走过的路径总长度，计算信息素的变化，最终根据结束条件(如最大循环次数或不发展状

态)

TSP问题的流程图如图3. 8所示:

2.2程序

蚁群算法

主讲人：郝 娟

指导老师：张著洪

目录

1蚁群算法概述..............................................................................21

1.1蚁群算法的提出与发展.............................................................. 21

1.2蚁群算法原理.............................................................................. 22

1.3数学模型的建立.......................................................................... 25

2蚁群算法的仿真分析....................................................................... 29

2.1蚁群算法流程.......................................................................30

2.2蚁群算法的计算机仿真............................................................. 30

2.3分析与总结................................................................................. 34

3蚁群算法的优化............................................................................... 38

3.1基本蚁群算法的缺点................................................................. 38

3.2改进与优化方法......................................................................... 40

3.3优化蚁群算法方案的仿真分析................................................. 43

4小结................................................................................................... 44

第一章 蚁群算法概述

生物学家通过对蚂蚁的长期研究发现，虽然每只蚂蚁智能不高，也没有集中的指挥，但它们却可以协同工作，依靠群体能力发挥出超出个体的智能。蚁群算法(ant colony algorithm, ACA)是最新发展的一种模拟蚂蚁群体智能行为的仿生优化算法，具有较强的鲁棒性、分布式计算机制、易于与其它算法结合等优点。尽管目前蚁群算法的严格理论基础尚未奠定，国内外的相关研究还处在实验探索和初步应用阶段，但蚁群算法己经由当初的单一TSP旅行商问题领域渗透到多个应用领域，有着广泛的应用前景。

1蚁群算法的提出与发展

根据蚂蚁“寻找食物”的群体智能行为，意大利学者M.Dorigo于1991年在法国召开的第一届欧}}l}l人工生命会议(European Conference on Artificial Life, ECAL中第一次提出了蚁群算法的基本模型。到1992年，M.Dorigo又在其博士学位论文中进一步阐述了蚁群算法的核心思想。由于在模拟仿真中使用了人工蚂蚁的概念，因此也称蚂蚁系统(ant system, AS )。 近年来，蚁群算法逐渐被国内学者了解和研究，相继出现了一些介绍性的文献，其后在蚁群算法的应用研究方面(如组合优化问题、网络路由调度问题等)开展了许多研究工作。 2蚁群算法原理

2.1生物学原型

蚂蚁系统是最早建立的蚁群算法模型，其模型的建立来源于对蚂蚁寻找食物行为的研究。蚂蚁视力很有限，但是蚂蚁寻找食物的过程中却有能力在没有任何可见提示下找出从蚁穴到食物源的最短路径，并且能随环境的变化而变化，适应性地搜索新的路径，产生新的选择。

经过研究发现，在从食物源到蚁穴并返回的过程中，蚂蚁能在其走过的路径上分泌一种化学物质一信息素，通过这种方式形成信息素轨迹。信息素轨迹可以使蚂蚁找到其返回食物源(或蚁穴)的路径，其他蚂蚁也可以利用该轨迹找到由同伴发现的食物源的位置。由蚂蚁个体的特征可以看出，蚂蚁除了对信息素有感知外几乎无法获知环境的信息，因而当环境中不存在信息素时，蚂蚁的行为是完全随机的。也就是说，蚂蚁在一个新的环境中的初始行走是完全随机的。另外，蚂蚁的搜索不是孤立的。事实上，假如只有一只蚂蚁进行搜索，由于蚂蚁的短视，很难找到最佳路径。当蚂蚁走过一条路径时，在上面留下的信息素会吸引更多的 蚂蚁走这条路。当这条路径上通过的蚂蚁越来越多，以至信息素强度增大，后来蚂蚁选择该路径的概率也越高，从而更增加了该路径的信息素强度。

图2.1 蚁群的初始路径

图2.2 原来的路径上出现以障碍物

图2.3蚂蚁以同样的概率决定行进方向

图2.4蚁群最终选择较短的路径

2.2数学模型的建立

假定从A到E(或者从E到A)有两条路径(ABCDE和ABHDE)，其中B到H、D到H的距离为1, B到C和D到C的距离为0. 5(如图2. 5所示)。设每个单元时间有30个蚂蚁分别从A到B，同时有30个蚂蚁从E到D，每个蚂蚁以每单元时间1的速度行走，行走时在时刻t留下浓度为1的信息激素，为了简化模型便于说明，假定在每个连续时间段(t+1, t+2)的中间时间点，信息素瞬时完全挥发。下面分别考虑在时刻t =0，1 ,2„时蚁群的运动情况。

图2.5 初始图

在t=o时刻，图上没有“轨迹”，仅在B, D点各有30个蚂蚁，它们选择走哪一条道路完全是随机的，因此平均有15只蚂蚁走向H点，15只蚂蚁走向C点，如图2. 6所示。

图2.6蚂蚁以相同的概率选择路径

在t=1时刻，30个从A到B的“新”蚂蚁到通向H的路径上发现了浓度为15的轨迹(由上一时刻从B到H的15只蚂蚁留下)，同时发现了通向C的路径上有浓度为30的轨迹(由从B到C出发的15只蚂蚁加上从D到C到达B的15个蚂蚁留下的轨迹之和，如图2. 7所示。 因此，现在选择路径的概率就有了不同，在理想情况下走向C的蚂蚁数量应该是走向H的蚂蚁的数量的2倍，分别是20个和10个。从E到D的30个蚂蚁和以上情况相同。

图2.7 较短的边上有更多的信息素，更多的蚂蚁选择较短的边

这个过程持续下去的结果就是所有的蚂蚁都选择了较短的路径。

下面将以TSP问题为例，介绍蚁群算法数学模型的建立。TSP问题就是指给定n座城市和两两城市之间的距离，要求确定一条经过各城市当且仅当一次的最短路线。根据蚁群算法的思想和TSP问题的具体特征，求解TSP问题的人工蚁都是具有如下特征的简单主体:

1)在从城市i到城市J的运动过程中或是在完成一次循环后，蚂蚁在边(I,j)上产生信息素轨迹，该轨迹可以影响后来的蚂蚁，使得蚂蚁群体走向最优解。

2)蚂蚁概率地选择下一个将要访问的城市，这个概率由图中边上的轨迹浓度和问题空间的自启发因子共同决定;

TSP问题有一个特点，在完成一次循环之前，不允许第二次访问同一个城市。为了满足蚂蚁必须经过所有n座不同的城市这个约束条件，为每只蚂蚁都设计了一个禁忌表(tabu lis0。禁忌表记录了在t时刻蚂蚁己经走过的城市，不允许该蚂蚁在本次循环中再经过这些城市。当本次循环结束后，禁忌表被用来计算该蚂蚁当前所建立的解决方案。

为模拟实际蚂蚁的行为，首先引入如下记号:

m一一蚁群中蚂蚁数量;

bi(t)一一t时刻位于城市i的蚂蚁的个数, m= bi(t).

i=1N

dij一一两城市i和j之间的距离;

nij一一边((i,j)的能见度，反映由城市i转移到城市j的启发程度，这个量在

蚂蚁系统的运行中不改变;

τij一一边((i,j)上的信息素轨迹强度;

△τij一一蚂蚁k在边(i,j)上留下的单位长度轨迹信息素量;

k一一蚂蚁k的转移概率，J是尚未访问的城市。 pij

初始时刻，各条路径上的信息素量相等，设τij(0) =C (C为常数)。蚂蚁k(k=1, 2,……, m)在运动过程中根据各条路径上的信息素量决定转移方向。蚂蚁系统所使用的状态转移规则被称为随机比例规则，式3. 1给出了位于城市i的蚂蚁k选择移动到城市j的概率。在t时刻，

k蚂蚁k在城市i选择城市j的转移概率可pij(t)为

其中，j∈allowedkk={0,1,……,n-1}表示蚂蚁k下一步允许选择的城市。由上式可知，转移概率pij(t)与τij.ηij成正比，nij为能见度因数，。α和β为两个参数，分别反映了蚂蚁在运动过程中所积累的信息和启发信息在蚂蚁选择路径中的相对重要性。蚂蚁按照上述状态转移规则选择城市并最终形成一条封闭路径，当所有的蚂蚁完成了它们的闭合路径后即一次迭代结束。利用全局信息更新规则来更新路径的信息量，再开始下一次迭代直到达到最大迭代次数或最大停滞次数。

蚁群算法的全局信息更新规则如式(3. 2)、式(3. 3)、式(3. 4)所示

: kαβ

在全局信息素更新公式中:

ρ一表示信息残留的程度即旧的信息素相对于新增加的信息所占的比重。

Q一取为常数，其值与y,(0)有关。

Lk一第k只蚂蚁在本次循环中所走过的路径的长度。

K—当前迭代次数

M一一最大迭代次数。

在每次迭代的初始时刻，设△τij=0

M. Dorigo曾给出三种不同模型，分别称为蚁周系统(ant-cycle system)、蚁量系统(ant-quantity system)、蚁密系统(ant-density system)。它们的差别在于全局信息更新规则的不同

:

从上面三个表达式中不难看出，蚁密系统和蚁量系统两种模型中利用的是局部信息而蚁周系统利用的是整体信息。蚁周系统在求解TSP时性能较好因此常作为基本模型，称之为基本蚁群优化算法。蚁群算法中α,β,Q等参数对算法性能也有很大的影响。α值的大小表明留在每个结点上的信息量受重视的程度，α值越大，蚂蚁选择以前选过的点的可能性越大，但过大会使搜索过早陷于局部最小点; β的大小表明启发式信息受重视的程度;Q值会影响算法的收敛速度，Q过大会使算法收敛于局部最小值，过小又会影响算法的收敛速度，随着问题规模的增大Q的值也需要随之变化。算法的全局搜索参数Q, α,β,ρ可以用实验方法综合分析确定其取值，以获得更优的求解效率和效果。

2蚁群算法的仿真分析

通过上一节对蚁群算法的介绍和数学模型的建立，可以确定蚁群算法可使用软件程序进行计算机仿真分析，并可以根据仿真的结果进行分析和讨论。根据蚁群算法的数学模型，针对基本的TSP问题建立仿真模型，实现蚁群算法在TSP问题模型中的仿真分析。在仿真的过程中通过调整各个参数的值和TSP问题的规模，可以检验和分析蚁群算法中的参数对算法性能的影响，进而可以分析蚁群算法的空间复杂度和时间复杂度。

2.1蚁群算法流程

根据数学模型，可以确定用蚁群算法求解TSP问题的流程为:首先初始化蚂蚁和信息素浓度等数值以及禁忌表，然后计算蚂蚁移动的概率，进行蚂蚁的移动，同时不断计算每个蚂蚁走过的路径总长度，计算信息素的变化，最终根据结束条件(如最大循环次数或不发展状

态)

TSP问题的流程图如图3. 8所示:

2.2程序