基于蚁群算法的路径最优相关研究 毕业答辩

导

师:

王康平答辩人:

刘媛媛专

业:

计算机科学与技术基于蚁群算法的路径最优问题研究论文的结构和主要内容P

a

g

e2

第一部分选题的背景与意义

第二部分国内外研究现状

第三部分研究内容与方法

第四部分研究中可能存在的问题

第五部分预期结果一选题背景与意义2

0

0

1年至今1

9

9

6年-2

0

0

1年意大利学者

Dorig

o1991年启发P

a

g

e3

一选题背景与意义

蚁群算法的由来：蚂蚁是地球上最常见、数量最多的昆虫种类之一，常常成群结队地出现在人类的日常生活环境中。这些昆虫的群体生物智能特征，引起了一些学者的注意。意大利学者M.Dor

i

go，V.Ma

niezzo等人在观察蚂蚁的觅食习性时发现，蚂蚁总能找到巢穴与食物源之间的最短路径。

经研究发现，蚂蚁的这种群体协作功能是通过一种遗留在其来往路径上的叫做信息素(Pher

omone)的挥发性化学物质来进行通信和协调的。化学通信是蚂蚁采取的基本信息交流方式之一，在蚂蚁的生活习性中起着重要的作用。通过对蚂蚁觅食行为的研究，他们发现，整个蚁群就是通过这种信息素进行相互协作，形成正反馈，从而使多个路径上的蚂蚁都逐渐聚集到最短的那条路径上。P

a

g

e4

二国内外研究现状P

a

g

e5

目前，蚁群算法己经成为一个备受关注的研究热点和前沿性课题。人们对蚁群算法的研究已经由当初的TSP领域渗透到多个应用领域，由解决一维静态优化问题发展到解决多维动态组合优化问题，由离散域范围内研究逐渐拓展到了连续域范围内研究。同时在蚁群算法的模型改进以及其他仿生优化算法的融合方面也取得了相当丰富的研究成果，从而使这种新兴的仿生优化算法展现出前所未有的生机。三研究内容与方法1.基本蚁群算法及其改进算法基本蚁群算法蚁群系统最大-最小蚂蚁系统2.蚁群算法与TSP应用蚁群算法的思想、原理蚁群算法的实现方式TSP应用举例P

a

g

e6

3.1.1蚁群算法的基本思想在自然界中，蚂蚁的食物源往往随机散布于蚁巢周围，通过观察可以发现，经过一段时间后，蚂蚁总能找到一条从蚁巢到食物源的最短路径。自然界中的蚂蚁虽然视觉能力十分有限，但它们在觅食过程中，却能够通过播撒、感知信息素与其它同伴建立起通讯关系，并以此相互协调、分工、合作来找到食物源和巢穴之间的最短路径。并且在相同的时间内，路径越短则遗留的信息素浓度就越大，而蚂蚁在选择路径时，倾向于那些信息素浓度较高的路径，这样选择较短路径的蚂蚁也随之增多。因此，由大量蚂蚁组成的蚁群集体觅食行为表现出了一种正反馈现象：一条路径上走过的蚂蚁越多，则后来者选择这条路径的概率就越高。蚂蚁个体之间就是通过这种信息素的交流机制，来搜索食物，并最终找到最短路径。P

a

g

e7

3.1.2蚂蚁觅食原理：

自然界中，蚂蚁这种视盲生物，在没有任何先知经验的情况下总能找到从其巢穴到食物源的最佳路径，甚至在该路径上放置障碍物之后，它们仍然能很快重新找到新的最佳路线。P

a

g

e8

P

a

g

e9

3.1.3蚁群算法的优缺点P

a

g

e10

蚁群算法的优点

不依赖于所求问题的具体数学表达式描述，具有很强的找到全局最优解的优化能力。

该算法具有正反馈、较强的鲁棒性、全局性、普遍性、优良的分布式并行计算机制、易于与其他方法相结合等诸多优点。蚁群算法的缺点：P

a

g

e11

蚁群算法的成功主要在实验层次上，很少有理论来解释利用蚁群算法为什么能够成功地解决这些问题，它没有坚实的数学基础；

蚁群算法的模型普适性不强，其模型不能直接应用于实际优化问题；

蚁群算法的局部搜索能力较弱，易于出现停滞和局部收敛、收敛速度慢等问题，因而往往需要嵌入一些专门的辅助技巧；

长时间花费在解的构造上，从而导致搜索时间过长，

算法最先基于离散问题，不能直接解决连续优化问题。3.2自然蚁群与人工蚁群P

a

g

e12

蚁群算法都是从自然界中真实蚂蚁寻找食物行为得到启发提出来的。人们只有通过对蚁群行为的一种模拟来满足实际问题的求解需要。所以人工蚁群与真实蚁群之间存在一定的异同。相似之处在于：都是优先选择信息素浓度大的路径。两者的区别：（1

）在于人工蚁群有一定的记忆能力，能够记忆已经访问过的节点。（2

）人工蚁群选择路径时不是盲目的。而是按一定规律有意识地寻找最短路径。例如，在TSP问题中，可以预先知道当前城市到下一个目的地的距离。3.3.1基本蚁群算法P

(

t

)i

jis

isP

a

g

e13

kisisij

(t)(t)

(t)

(t),sallowk

P

(t)

xallowk

蚂蚁k(

k=1,

2，⋯,

m)

根据各个城市间k

连接路径上的信息素浓度决定其下一个访问城市，设

表示t

时刻蚂蚁k从城市i转移到城市j的概率，其计算公式为：

0,sallowk

信息更新公式为：nk

ij

(t1)(1)ij(t)ij,01

k1ij

ii

针对蚂蚁释放信息是问题，M.Dor

i

go等人曾给出3中不同的模型，分别为蚁周系统、蚁量系统和蚁密系统，其计算公式如下：P

a

g

e14

3.蚁密系统模型

k

Q/dij，第k只蚂蚁从城市i访问城市j2.蚁量系统模型i

0,其他

k

Q，第k只蚂蚁从城市i访问城市j1.蚁周系统模型

k

Q/Lk，第k只蚂蚁从城市i访问城市ji

0,其他i

0,其他其中，Q为常数，表示蚂蚁循环一次所释放的信息素总量；L为第k只蚂蚁经过路径的长度。d为城市间的距离。3.3.2蚁群系统

蚁群系统的状态转移规则一只位于节点r的蚂蚁通过应用下式给出的规则选择下一个将要移动到的城市s：q是在[0,1]区间均匀分布的随机数q0的大小决定了利用先验知识与探索新路径之间的相对重要性。0ua

llowedks

arg

max{[(r,u)]

[(r,u)]

},如果q

q按先验知识选择路径

S,否则其中，S根据下列公式得到ij

ijP

a

g

e15

kkis

isPij

(t

)

(t

),

j

a

l

lowed

(t

)

(t

)(t

)

sa

l

lowedk

0,

otherwise

gbP

a

g

e16

L

1

,

(r

,

s)

0,如果(r,s)

全局最优路径否则

蚂蚁系统全局更新原则只有全局最优的蚂蚁才被允许释放信息素。目的：使蚂蚁的搜索主要集中在当前循环为止所找出的最好路径领域内。全局更新在所有蚂蚁都完成它们的路径之后执行，试用下式对所建立的路径进行更新：为到目前为止找出的全局最优路径。

为信息素挥发因数，0<

g

b<1。L(r,s)(1)(r,s)(r,s)

蚁群系统局部更新原则蚂蚁应用下列局部更新原则对它们所经过的边进行激素更新：(r,s)

(1

)(r,s)(r,s)其中,

为一个参数,0

10P

a

g

e17

1最近的邻域启发n产n

生的一个路径长度。局部更新原则可以有效的避免收敛到同一路径。实验发现，

n

Lnn可以产生好的结果，其中n是城市的数量，L

是由3.3.3最大-最小蚂蚁系统ijijij(t

1)

(t)

bestijP

a

g

e18

1

f

(sbest

)

信息素轨迹更新在MMAS中，只有一只蚂蚁用于在每次循环后更新信息轨迹。经修改的轨迹更新原则如下：bestf(sbest

)表示迭代最优解或全局最优解的值。在蚁群算法中主要使用全局最优解，而在MMAS中则主要使用迭代最优解。

m

i

n

i

j

(

t

)

m

a

x1P

a

g

e19

tf

(

s

o

p

t

)t

ii

1(

t

)

信息素轨迹的限制MMAS对信息素轨迹的最小值和最大值分别施加了

min和

max的限制，从而使得对所有信息素

轨ij

(t迹)

，有

max

的选取：

m

a

xi

j其中,f(s

opt

)为对于一个具体问题的最优解

min

的选取要基于两点假设：

最优解在搜索停滞发生之前不久被找出。

对解构造的主要影响是由信息素轨迹的上限与下限之间的相对差异决定。3.4蚁群算法的实现(

1)

参数初始化。令时间t

=0和循环次数Nc

=0，设置最大循环次数Nc

ma

x,

将m个蚂蚁置于n个元素(

城市)

上，令有向图上每条边(

i

,

j

)

的初始化信息量τi

j

(

t

)

=c

ons

t

,

其中cons

t

表示常数，且初始时刻Δτi

j

(

0)

=0(2)循环次数Nc←Nc+1。(3)蚂蚁的禁忌表索引号k=1。(4)蚂蚁数目k←k+1。(

5)

蚂蚁个体根据状态转移概率公式(

1)

计算的概率选择元素(

城市)

j

并前进，j

∈{

C

-

t

abuk}

。(6)修改禁忌表指针，即选择好之后将蚂蚁移动到新的元素(城市)，并把该元素(城市)移动到该蚂蚁个体的禁忌表中。(7)若集合C中元素(城市)未遍历完，即k<m，则跳转到第(4)步，否则执行第(8)步。(8)根据公式(2)和式(3)更新每条路径上的信息量。(9)若满足结束条件，即如果循环次数Nc≥Nc

ma

x则循环结束并输出程序计算结果，否则清空禁忌表并跳转到第(2)步。P

a

g

e20

四预期结果

对于信息素挥发因子ρ、启发式因子α、自启发因子β、蚂蚁的数目m对于蚁群算法性能的影响进行了实验研究，发现蚁群算法中各个参数的取值对最后的求解性能有很大的影响，目前还是靠经验对各个参数取值。在分析各个参数的作用及对算法性能的影响的基础上，并通过大量实验验证，给出了蚁群算法中各参数的一个较理想取值范围。P

a

g

e21

五研究中可能遇到的问题P

a

g

e22

问题一蚁群算法参数选择很重要，选择不当的话会出现搜索的过早停滞现象或陷入局部最优问题。

问题二蚁群算法对非线性系统辨识中对输入信号的选择是一个难点。结论蚁群算法解决了TSP问题只是解决了众多组合优化问题的一种，但是围绕着TSP问题的解决才有了蚁群算法的发展和创新，它涉及了仿生学，程序设计学，计算机科学仿真技术多个学科，是信息处理领域中的一项前沿技术。本文的前期工作是介绍了基本蚁群算法的原理和蚁群算法的机制原则。在本文