蚁群算法的研究现状

admin管理员组

文章数量:1531755

2024年5月11日发(作者：)

蚁群算法的研究现状　吴　斌

,

等

蚁群算法的研究现状

CurrentStatusofResearchonAntColonyAlgorithm

吴　斌　赵燕伟

(

浙江工业大学机电学院

,

杭州　

310032

)

摘　要　蚁群算法是一种新型的模拟进化算法

,

研究表明该算法具有很好的通用性和鲁棒性

,

在离散的组合优化问题中实验

,

取得了

良好的效果。介绍了蚁群算法的原理

,

对目前蚁群算法的研究进展情况进行了分析

,

同时对比国内外的研究状况提出了自己的观点

,

以推动该算法在更广阔的领域内得到应用。

关键词　蚁群算法　研究　现状　蚁群系统　组合优化　

TSP

Abstract

earchshowsthatthisalgorithmcanbecommonlyusedandoffers

verygoodrobustness,excellencipleofantcolonyalgorithmisintroduced

uationoftheresearchathomeandabroadarecomparedandtheviewpointofauthor

licationofthisalgorithminwiderareaispromoted.

Key

words

Antcolonyalgorithm

Research

Currentstatus

Antcolonysystem

Combinedoptimization

TSP

0

　引言

很早人们就知道模仿生物的一些特性

,

来更好地

为人类服务。近几年

,

在优化算法领域

,

一种新的仿生

优化算法进入了人们的视野———蚁群算法

(

antcolony

algorithm

)

。首先

,

由意大利科学家

等人提

子来说明蚂蚁的搜索机制。

出

,

称为蚁群系统

(

antsystem,AS

)

,

并成功地用于求解

TSP

问题

,

引起了人们关注。在求解二次分配

[1]

、

Job

2

Shop

问题

[3]

、图着色问题

[4]

、车辆调度

[14]

、集成电路设

图

1

　蚂蚁的搜索机制

如图

1

所示

,

假设在

t

=0

时刻有

16

只蚂蚁从巢

穴出发外出寻食

(

设蚂蚁在单位时间走过单位长度

)

。

在

t

=1

时到达

A

点

,

因为此时

AB

和

AC

都没有信息

激素

,

所以蚂蚁按等概率选择

,

8

只选择

AB,

8

只选择

AC

。在

t

=4

时

,

从

AB

走的

8

只到达食物处

,

并开始

计以及通信网络负载问题的处理中

作。

[5][13]

都取得了较

好的结果。越来越多的研究人员正在从事这方面的工

1

　算法的原理

根据昆虫学家的观察

,

发现自然界的蚂蚁虽然视

觉不发达

,

但它可以在没有任何提示的情况下找到从

食物源到巢穴的最短路径

,

并且能在环境发生变化

(

如

原有路径上有了障碍物

)

后

,

自适应地搜索新的最佳路

径。为什么呢

?

原来蚂蚁在走过的路上会释放一种特

殊的分泌物———信息激素

(

pheromone

)

,

使得一定范围

内其它的蚂蚁能够觉察到并由此影响他们的行为

,

当

一条路上的信息激素越来越多

(

当然

,

随时间的推移会

逐渐减弱

)

,

后来的蚂蚁选择这条路径的概率也越来越

大

,

从而增加该路径的信息激素强度

,

这种选择过程称

为蚂蚁的自催化过程

,

其原理是一种正反馈机制

,

所以

蚂蚁系统也称为增强型学习系统。这里我们举一个例

返回。在

t

=5

时

,

返回的蚂蚁到达

D,

这时

BD

和

CD

上的信息素浓度还相等

,

都为

8

,

所以蚂蚁还按等概率

选择

,

4

只从

BD,

4

只从

CD

。在

t

=8

时

,

从

BD

返回

的

4

只蚂蚁返回巢穴

,

并重新外出。当

t

=9

时

,

又来

到

A,

此时

AB

的信息激素的浓度是

16

,

而

CA

的是

12

,

所以将有较多的蚂蚁选择从

AB

走。以后

,

如此循环

,

最后所有的蚂蚁都会选择

ABD

路线。

由此可以看出

,

蚁群算法的基本思想是模仿蚂蚁

依赖信息素

(

pheromone

)

进行通信而显示出的社会性行

为

,

在智能体

(

agent

)

定义的基础上

,

由一个贪心法指导

下的自催化

(

autocatalytic

)

过程引导每个智能体

(

agent

)

的行动

,

它是一种随机的通用试探法

,

可用来解各种不

同的组合优化问题。下面简单介绍一下

TSP

问题的基

本蚁群算法求解

:

1

《自动化仪表》第

25

卷第

1

期　

2004

年

1

月

假设

n

个城市

,m

个蚂蚁

,

任意两城市

r,s

之间

的距离为

d

(

r,s

)

,

τ

(

r,s

)

表示两个城市间信息素的

τ

(

r,s

)

k

表示第

K

个蚂蚁访问过支路

(

r,s

)

浓度

,

Δ

后释放的信息浓度。

P

k

(

r,s

)

表示第

K

个蚂蚁的转

移概率

:

P

k

(

r,s

)

=

蚁密算法

(

ant

2

density

)

和蚁量算法

(

ant

2

quantity

)

。它们

的区别主要在于更新信息素的方式。对于这两种模

型

,

每个蚂蚁不是在整个路径结束后释放信息素

,

而是

在每一步的过程中释放。对于

ant

2

density

算法

,

每当蚂

蚁经过边

(

r,s

)

时

,

浓度为常量

Q

的信息素被释放在

这条边上。对于

ant

2

quantity

算法

,

每当蚂蚁经过边

τ

s

|

=z

τ

(

r,s

)

α

η

(

r,s

)

β

αβ

;s

|

z

6

τ

(

r,s

)

η

(

r,s

)

;s

∈

z

(

1

)

(

r,s

)

时

,

浓度为

Q/d

ij

的信息素被释放在这条边上。

0

很明显

,

在

ant

2

density

算法中

,

蚂蚁释放的信息素浓度

与边长度

d

ij

无关

;

在

ant

2

quantity

算法中

,

这两者就建

立了相关性。也就是说

,

蚂蚁倾向于选择下一步较短

的路径。

前面介绍的蚁群算法

,

又称为蚁周算法

(

ant

2

cy

2

clealgorithm

)

。由于蚁周算法在搜索过程中使用的反馈

式中

:s

表示未访问过的城市

;z

表示已经访问过城市

的集合

;

η

(

r,s

)

=1

/d

(

r,s

)

,

称为边弧的能见度

;

α

为

信息素浓度的重要程度

;

β

为可见度的相对重要程度。

信息素浓度更新公式为

τ

(

r,s

)

new

=

ρ

・

τ

(

r,s

)

old

+

k

∈

z

τ

(

r,s

)

6

Δ

k

(

2

)

式中

:

ρ

表示信息浓度挥发后的剩余浓度

;

Δτ

(

r,s

)

k

信息是全局的

,

而蚁量和蚁密算法使用的反馈信息都

是局部的

,

故蚁周算法要优于另两种算法

,

仿真的结果

也证明了这个推断。

此外

,

在

Dorigo

等人的论文中还对蚁群算法提出

了一些讨论

,

其中包括不同的蚁群初始分布对求解的

影响等

,

还提出了所谓的精英策略

(

elitistrategy

)

,

以强

化精英蚂蚁

(

发现迄今最好路径的蚂蚁

)

的影响。结果

发现

,

对精英蚂蚁数而言有一个最优的范围

,

低于此范

围

,

增加精英蚂蚁数可较早地发现更好的路径

,

高于此

范围

,

精英蚂蚁会在搜索早期迫使寻优过程始终在次

优解附近

,

导致性能变差。

1996

年

,Gambardella

和

Dorigo

又提出一种修正的

=

Q/L

k

;

若蚂蚁

k

访问过

(

r,s

)

0

;

若蚂蚁

k

没有访问过

(

3

)

Q

为一个常数

,

表示蚂蚁完成一次完整的路径搜索后

释放的信息素的总量

;L

k

表示路径总长度。整个算法

的过程

,

简单描述如下

:

①首先初始化

,

设迭代次数为

NC

。初始化

NC=

τ

(

r,s

)

初始化

;

将

m

个蚂蚁置于

n

个

0,

各

τ

(

r,s

)

,

Δ

顶点上

;

②将各个蚂蚁初始位置至于当前的解集

z

中。

然后对每个蚂蚁

k

(

k

=1

,

2

,

…

,m

)

,

按照概率

P

k

转移

到下一个城市

S,

将

S

置于当前解集中

,

如此循环

,

直

到所有的蚂蚁访问完所有的城市

;

③计算每个蚂蚁行走的总路径

L

k

,

并将最优解

保存

;

④按信息浓度更新公式

,

更新各边的信息浓度

;

τ

(

r,s

)

初始化

,NC=NC+1;

⑤各边的

Δ

⑥如果

NC

小于预定值并且没有稳定解

,

则转第

②步

,

否则输出最优解。

2

整个算法的复杂度为

O

(

NC

・

m

・

n

)

,

经实验

,

一般

蚁群算法

,

他们称之为蚁群系统

(

antcolonysystem,

ACS

)

。它与前面提到的蚁群算法有三点不同

:

①蚂蚁选择城市时遵循的规则不同

,

这里使用的

是所谓的状态转移规则

(

statetransitionrule

)

:

argMAX

[[

τ

(

r,s

)

]

・

[

η

(

r,s

)

]

];

S

k

=

αβ

s

|

z,Q

≤

Q

0

P

k

;s

|

z,

　　其他

(

4

)

式中

:

Q

是一个随机变量

;Q

0

是一个阀值。蚂蚁在选

择下一个城市之前先进行一次随机试验得

Q,

若

Q

≤

Q

0

,

则选择城市时按取最大值的情况转移

,

如果

Q

>

Q

0

,

则按式

(

1

)

的转移概率转移。

情况下

,m

取与

n

同一数量级

,

大致相等的情况下

,

效

3

果最好

,

所以最终复杂度是

O

(

NC

・

n

)

。算法中的参

数设置

,

现在尚无理论上的研究

,

已公布的实验结果都

是针对特定问题而言的

,

就

TSP

问题

,

从实验结果可

α

≤

β

≤

5

,

0

1

1

≤

ρ

≤

0

1

9

(

0

1

7

左右最佳

)

,

知

:0

≤

5

,

1

≤

10

≤

Q

≤

10000

,

各参数在以上区间内取值

,

能得到比较

②全局更新规则不同。全局更新不再是对所有

的蚂蚁

,

而是仅对一次循环中最优的蚂蚁使用。

③增加了局部更新规则。局部更新规则是在所

有蚂蚁完成一次转移后执行。

为了克服蚁群算法存在的收敛慢、容易出现停滞

现象、算法的运算时间长等缺点

,

人们提出了许多改进

算法。德国学者

Thomastuzle

和

Holerhoos

[8]

提出的一种

好的结果。

2

　算法研究

还设计了两种蚁群算法的变形

,

分别是

2

PROCESSAUTOMATIONINSTRUMENTATION,Vol.25,No.1,Jan.,2004

蚁群算法的研究现状　吴　斌

,

等

改进的算法

,

最大最小系统

(

max

2

minantsystem,

MMAS

)

是比较好的一个算法

,

在解决

TSP,QAP

等问题

鲁棒性。从提出到现在

,

仅短短十余年的时间

,

但其在

离散型组合优化问题中

,

表现得很突出

,

所以引起人们

的关注。目前蚁群算法的研究学者主要集中在比利

时、意大利、德国等国家

,

美国和日本在近几年也开始

了对蚁群算法的研究。国内的研究始于

1998

年末

,

主

要在上海、北京、东北少数几个学校和研究所开展了此

项工作

,

主要围绕

TSP

及相关问题的实验仿真

,

少数涉

及通信网络的路由选择

[29]

、负载平衡、电力系统的故

障检测

[10]

以及蚁群算法在连续系统应用

[19,23,26]

,

如函

数逼近

[19]

等方面应用的尝试。在国外

,

蚁群算法已经

在集成电路布线

[5]

、网络路由选择

[13]

、机器人线路规

划

[15]

等方面得到了应用。自

1998

年

,

第一届蚂蚁优化

国际研讨会召开以来

,

已经是第三届了

,

大大推动了蚁

群算法的发展。蚁群算法已经引起越来越多的关注

,

尽管还缺乏完善的理论分析

,

对它的有效性也没有给

出严格的数学解释

,

但回顾模糊控制的发展历史

,

理论

的不完善并不妨碍应用

,

有时应用是超前于理论的

,

并

推动理论的研究。我们相信蚂蚁算法必将得到广泛的

应用。

参考文献

1

ColormA,DorigoM,butedoptimizationbyant

colonies[C].ficialLife,

Paris,FranceElsevierPublishing,1991:134

～

142

2

DorigoM,onysystem:acooperativelearning

approachtothetravelingsalesmanproblem[J].IEEETransonEvolu

2

tionaryComputation,1997,1

(

1

)

:53

～

66

3

ColorniA,temforjob

2

shopscheduling[J].JORBEL,

1994,34

(

1

)

:39

～

53

4

CostaD,colorgraphs[J].oftheOpnlResSoc,

1997,48

(

3

)

:295

～

305

5

CoelloCAC,GutierrezRLZ,GarciaBM,tedde

2

ering

Optimization,2002,34

(

2

)

:109

～

127

6

ticfromnatureforhardcombinationoptimizationprob

2

lems[J].InternationalTransactionoperationalresearch,1998,3

(

1

)

:

1

～

21

7

MerkleD,lgorithmwithanewpheromoneeval

2

uationrulefortotaltardinessproblems,Real

2

WorldApplicationsofEvo

2

lutionaryComputing,Proceeding2000,18

(

3

)

:287

～

296

8

StutzleT,

2

GenerationCom

2

puterSystems,2000,16

(

8

)

:889

～

914

9

GambardellaLM,TaillardED,oniesforthe

lofTheOperationalResearchSo

2

ciety,1999,50

(

2

)

:167

～

176

10

ChangCS,TianL,proachtofaultsectionestima

2

icPowerSystemsRe

2

search,1999,49

(

1

)

:63

～

70

11

KuntzP,LayzellP,yofantlikeagentsforpartition

2

时结果要优于一般的

ACO

类算法。

MMAS

与

ACS

两者

的共同点是在算法的每次迭代中只允许表现最好的蚂

蚁更新路径上的迹

;

其不同之处主要在于如何防止过

早的停滞现象

(

stagnation

)

。

MMAS

限定了痕迹浓度允

许值的上下限

,

并且采用了平滑机制

,MMAS

在算法启

动时将所有支路上的痕迹浓度初始化为最大值

τ

max

,

每次迭代后

,

按挥发系统

ρ

降低痕迹浓度

,

只有最佳

路径上的支路才允许增加其浓度

,

并保持在高水平上。

但是

,

光采用最大最小痕迹浓度的限制还不足以在较

长的运行时间里消除停滞现象

,

因此采用了平滑机制

;

(

r,s

)

之差。痕迹浓度的增加正比于

τ

max

和当前浓度

τ

对于

ACO

算法的收敛性问题

,2002

年

Gutjah

首先在他

的论文中证明了

ACO

类算法的收敛性

[18]

。

一些学者还把蚁群算法与其他的算法相结合。意

大利学者

Fabio,Abbattista

等人受遗传算法的启发提出

蚁群算法和遗传法相结合的思路。鉴于在蚁群算法中

参数

α

,

β

(

分别对应信息素和能见度对决策的权重

)

和

Q

(

对应蚂蚁在一个周期中留下的信息素量

)

的选择对

算法的性能有很大影响

,

可以将

α

,

β

和

Q

看成代表蚂

蚁典型特征的染色体

G

中的三段代码。在

G

中

,G

α

和

G

β

将

α

,

β

编码为实数

,G

Q

将

Q

编码为整数

,

然后将此

染色体通过遗传算子交由一个进化过程处理。这样就

把蚁群系统的协作效应与遗传算法的进化效应结合起

来。

1999

年

,

吴庆洪等

[

28

]

提出了具有变异特征的蚁群

算法。其核心思想是为了克服蚁群算法收敛较慢的问

题

,

采用逆转变异方式

,

随机地进行变异

,

以增大进化

时所需的信息量。这种变异机制充分利用了

2-

交换

法简洁高效的特点

,

因而具有较快的收敛速度。

还有一些学者提出了一些自适应算法

,

如把常数

Q

改为时间的函数

[

24

]

等。本文作者针对现有算法中

每只蚂蚁都要访问所有城市的问题

,

提出了一种信息

交换算法

,

即若干蚂蚁在某个城市相遇后

,

互相交换信

息

,

这样蚂蚁系统不止是在并行的寻找所有可能路径

,

而且在同一条路径上也在并行搜索。具体算法和实验

数据将另文发表。

蚁群算法在其他方面的应用

,

如

Job

2

shop

、二次分

配等

,

算法虽然不一样

,

但其原理是一样的

,

都可以归

结为图上寻优的过程。

3

　结束语

蚁群算法是一种新生算法

,

具有很强的通用性和

3

《自动化仪表》第

25

卷第

1

期　

2004

年

1

月

4

th

ficalLife.

BostonMITPress,1997:417

～

424

12

MiddendorfM,ReischleF,olonyantalgorithms.

JournalofHeuristics,2002,8

(

3

)

:305

～

320

13

CordoneR,edantsystemandlocalsearchtodesign

ationsofEvolutionaryComput

2

ing,Proceeding,2001,2037:60

～

69

14

BullnheimerB,HartlRF,ovedantsystemalgorithm

ofOperationsResearch,1999,

89:319

～

328

15

,RobertMatthews,k,SevenBrueck

2

er,EvolvingAdaptivePheromonepathplanningmechanisms,Proceed

2

ingsofthefirstinternationaljointconferenceonAutonomousagentsand

multiagentsystems,ACMpress,2002:434

～

400

16

WangLei,manceevolutionofantsystemoptimization

.4

th

WCICA2002,IEEEpress:2546

～

2550

17

YangXinbin,SunJingao,usteringmethodbased

.4

th

WCICA2002,IEEEpress:2223

～

2226

18

GutjahACOalgorithmswithguaranteedconvergencetotheoptimalsolu

2

tion[J].InformationProcessingLetters,2002,82

(

3

)

:145

～

153

19

WangLei,examplestudyonantsystemalgorithm

.4

th

WCICA2002,IEEE

press:2541

～

2545

20

　庄昌文

,

范明钰

,

等

.

基于协同工作方式的一种蚁群布线系统

.

半

　　收稿日期

:2002-12-06

。

第一作者吴斌

,

男

,1979

年生

,

在读硕士研究生

;

研究兴趣为神经网

络、蚁群算法及其应用。

导体学报

,1999,20

(

5

)

:400

～

406

21

　覃刚力

,

杨家本

.

自适应调整信息素的蚁群算法

.

信息与控制

,

2003,31

(

3

)

:199

～

201

22

　马良

,

项培军

.

蚁群算法在组合优化中的应用

.

管理科学学报

,

2001,4

(

2

)

:32

～

37

23

　马良

.

一种全局优化的新方法

.

系统工程与电子技术

,2000,22

(

9

)

:61

～

63

24

　王颖

,

谢剑英

.

一种自适应蚁群算法及其仿真研究

.

系统仿真学

报

,2002,14

(

1

)

:30

～

33

25

　张纪会

,

高齐圣

,

徐心和

.

自适应蚁群算法

.

控制理论与应用

,

2000,17

(

1

)

:1

～

3

26

　林锦

,

朱文兴

.

凸整数规划问题的混合蚁群算法

.

福州大学学报

(

自然科学版

)

,1999,27

(

6

)

:5

～

9

27

　郑肇葆

.

协同模型与遗传算法的集成

.

武汉大学学报

(

信息科学

版

)

,2001,26

(

5

)

:381

～

385

28

　吴庆洪

,

张纪会

,

徐心和

.

具有变异特征的蚁群算法

.

计算机研究

与发展

,1999,36

(

10

)

:1240

～

1245

29

　王颖

,

谢剑英

.

一种基于蚁群系统的多点路由新算法

.

计算机工

程

,27

(

1

)

:55

～

56

30

　徐宁

,

朱小科

,

等

.

用于两端线网布线的蚁群系统方法

.

计算机辅

助设计与图形学学报

,2002,14

(

5

)

:410

～

412

基于

PSD

算法的单神经元

PID

控制器在汽温控制中的应用

TheApplicationofPSDAlgorithmBasedSingleNeuronPIDControllerinSteamTempera

2

tureControl

肖　军　任挺进　李东海　高琪瑞

(

清华大学热能工程系

,

北京　

100084

)

摘　要　介绍将自适应

PSD

控制算法中递推计算并修正增益的方法引入单神经元

PID

控制

,

形成了具有增益自适应能力的控制器

,

设

计了基于

PSD

算法的单神经元

PID

控制器

,

并应用于超临界机组过热汽温控制系统。仿真结果表明

,

基于

PSD

算法的单神经元

PID

控

制器具有较强的自适应能力和鲁棒性

,

其控制品质优于常规的

PID

控制器和一般单神经元控制器。

关键词　

PID

控制器　单神经元　

PSD

算法　过热汽温控制　超临界机组

Abstract

Byintroducingrecurrencecalculationandgaincorrectionofself

2

adaptivePSDcontrolalgorithmintosingleneuronPIDcontrol,thecontroller

withself

2

esingleneuronPIDcontrollerbasedonPSDalgorithmisdesignedandusedinsuperheatedsteam

ultofsimulationshowsthatthesingleneuronPIDcontrollerbasedonPSDalgorithmoffershigha

2

bilityofself

2

trolqualityofthiscontrollerisbetterthanofconventionalPIDcontrollerandcommonsingleneuroncon

2

troller.

Key

words

PIDcontroller

Singleneuron

PSDalgorithm

Superheatedsteamtemperaturecontrol

Supercriticalpowerunit

4

PROCESSAUTOMATIONINSTRUMENTATION,Vol.25,No.1,Jan.,2004

本文标签： 算法蚂蚁信息研究浓度