社会协作的多智能体进化

社会协作的多智能体进化

2009年4月第36卷　第2期

西安电子科技大学学报(自然科学版)

JOURNAL　OF　XIDIAN　UNIVERSITY

Apr.2009

Vol.36　No.2

社会协作的多智能体进化

潘晓英,焦李成

(西安电子科技大学智能感知与图像理解教育部重点实验室,陕西西安　710071)

摘要:提出了一种新的求解函数优化的算法.借鉴社会协作机制,定义可信任度表示智能体的历史活动信息,控制智能体间的相互作用;引入“熟人关系网”模型构建和更新智能体的局部环境,利用多智能体之间的协作特性来加快算法收敛速度;并构造了非一致变异算子保证智能体种群的多样性.仿真实验结果表明,与性能优越的多智能体遗传算法相比,该算法能以更少的函数评价次数找到精度更高的最优解.关键词:函数优化;多智能体进化;社会协作机制;熟人关系网;收敛

中图分类号:TP18　　文献标识码:A　　文章编号:100122400(2009)0220274207

Socialcooperationbasedmulti2agentevolutionaryalgorithm

PANXiao2ying,JIOLi2(MinistryofEducationKeyLab.of,

Univ.)

Abstract:AgentEvolutionaryAlgorithm(SCMAEA)whichmechanismandmulti2agentevolutionfornumericaloptimizationisproposed.thesocialcooperationmechanism,trustdegree,whichdenotesthehistoricalinformationforagents,isdefinedtocontroltheinteractionbetweenagents.Atthesametime,the

‘acquaintancenetmodel’isimportedtoconstructandupdatethelocalenvironmentoftheagent.It

improvestheconvergenceratebythecooperationcharacteristicofagents.Furthermore,adoptingthenon2uniformmutationoperationimprovesthesearchingforoptimalsolutionsinthelocalregionandassuresthediversityofthesolution.Simulationresultsshowthatcomparedwiththemulti2agentgeneticalgorithm,thesocialcooperationbasedmulti2agentevolutionaryalgorithmcanfindtheoptimabyasmallernumberoffunctionevaluations.

KeyWords:　functionoptimization;multi2agentevolution;socialcooperationmechanism;acquaintance

net;convergence

遗传算法是通过模拟生物在自然界中的进化过程而形成的一种全局优化方法,目前已得到了广泛的应用[1].凭借其对函数的类型,搜索空间的形状等都没有任何限制的优势,遗传算法已经成为求解函数优化问题的最有潜力的方法之一.但当函数的维数增加时,搜索空间增大,变量间耦合度增强,则会导致遗传算法陷入局部极值的概率增大.为了提高算法的性能,提出了各种各样的新策略和方法,如概率遗传算法[2],量子遗传算法[3],正交遗传算法[4],宏进化算法[5],多智能体遗传算法[6]等,都取得了良好的效果.

基于智能体的计算已广泛应用于计算机科学的各个分支,Liu[7]将分布式技术用于求解约束满足问题,设计了一种基于能量的多智能体模型,并求解了高达7000个皇后问题,显示出智能体的优越性能.钟等[6]针对函数优化问题,将智能体对环境的感知和反作用的能力与遗传算法的搜索方式相结合,提出了多智能体遗

传算法(MAGA),其收敛速度远远高于传统算法,证实了借助多智能体系统中的协作机制来实现进化算法中个体的竞争和协作可加快算法的收敛速度和增强算法的优化能力.但MAGA仅为每个智能体定义了位

收稿日期:2007212226

基金项目:国家“863”计划项目资助(2006AA01Z107);博士点基金资助(20060701007)

作者简介:潘晓英(19812),女,西安电子科技大学博士研究生,E2mail:xiaoying-pan@.

社会协作的多智能体进化

第2期　　　　　　　　　　　　　　　潘晓英等:社会协作的多智能体进化

275

置相邻的感知邻域,这一点与实际的多智能体协作相差甚远,在一定的程度上影响了算法的性能.为克服该缺陷,笔者从研究多智能体系统中的协作机制出发,提出了一种社会协作的多智能体进化算法(SCMAEA).该算法定义可信任度表示智能体之间的历史活动信息,在多智能体和进化算法结合的基础上引入社会协作机制来建立和更新局部环境,加快算法的收敛速度;同时构造一个非一致变异算子来提高算法的局部搜索能力,在收敛的前提下保持多智能体种群的多样性.

1　问题描述

不失一般性,函数优化问题可描述为下述的数学模型

min　f(x)　,　x=(x1,x2,…,xn)∈S　,

其中f(x)为目标函数,SΑRnx≤xi≤xi,i=1,2,…,n的n维搜索空间.

定义1　智能体a表示待优化函数的一个候选解,其能量值等于目标函数的相反数,即

a∈Sandenergy(a)=-f(a)　,

(2)

(1)

其目标为最大化智能体的能量.

2　智能体社会协作机制———关系网模型

陈等[8]对agent社会组织方法和,agent之间联系的“熟人关系网模型”,同时对a的属性包括:name,address,capability以及(;address(a)表示联系地址;capability(a)用于描述a对问题的求解能力;a)所有熟人通信信息的列表,表示为contact(a)=<l1,l2,…,lm>,列表中的每一个元素li称为熟人i的联系信息,有li=<name,address,trust2degree>,其中name(i),address(i)和trust2degree(a,i)分别表示熟人i的名称,联系地址以及智能体a对i的可信任度.其中trust2degree(a,i)的取值范围为[-1,+1],与可信任度值大的熟人合作,成功的可能性也就越大.

定义2　智能体a认为b在时间t的可信任度为T(a,b,t),规定:T(a,b,t)∈[-1,+1];并将初始时间t=0时对b的可信任度置为0,即T(a,b,0)=0.

Agent为了确定熟人的可信任度,需从与熟人合作的成功与否来考虑,如果合作成功则给该熟人的可信任度增加一个数量值,如果合作失败,则减少一个数量值.为了鼓励agent积极合作,假设在agent社会中,agent遵循“知己难寻,冤家易结”的基本原则确定可信任度.设一次失败的合作对agent可信任度造成的损

γ>δ失为γ,一次成功的合作对agent可信任度带来的收益为δ,则.一种简单的可信任度确定方法为可信任

δ;当a与b合作失败时:T(a,b,t+度积累策略,当a与b合作成功时:T(a,b,t+1)=T(a,b,t)+

1)=T(a,b,t)-γ.

3　社会协作的多智能体进化

该算法采用多智能体进化的思想,将智能体作为传统进化算法中的个体并采用进化机制,每个智能体能够同时与环境和其他智能体交换信息,互相影响彼此的进化过程,通过其相互作用达到全局优化的目的,以下对此进行详细说明.311　智能体定义

根据函数优化问题的具体要求,定义agenta=(location,body,energy,neighbor),其中location表示智能体的位置;body(a)=(a1,a2,…,an)为智能体的内容;energy为智能体的能量;neighbor为智能体的局部环境,表示为neighbor(a)=(l1,l2,…,lm),其中每个元素为一智能体记录,有li=(location,trust2degree),location(i)和trust2degree(a,i)分别表示agenta局部环境中agenti所处的位置以及可信任度.所有的智能体均生存在规模为lat×lat的网格上,每个智能体占据网格上一个节点,且不能移动,如图1所示.

社会协作的多智能体进化

　　　　　　　　　　　　　　　　西安电子科技大学学报(自然科学版)　　　　　　　　　　　　　　第36卷276

312　局部环境定义

多智能体协作进化算法中,生存在网格上的智能体通过与其局部环境内的智能体相互作用来达到整体进化的目的,图2为智能体局部环境变化的示意图.31211　初始局部环境

定义3　对生存在网格位置(i,j)上的每个智能体agenta,其初始局部环境包括位置上与其相邻的4个智能

),(i″)),

体,表示为neighbor(a)=((i′,j),(i,j′,j),(i,j″

且初始可信任度均为0.

i-1　,i≠1j-1　,j≠1

其中i′=,　j′=,

lat　,i=1lat　,j=1i″=

i+1　,

i≠lati=lat

图1　智能体网格结构图

1　,

,　j″=

j+1　,j≠latj=lat

1　,

.

图2　智能体局部环境变化示意图

31212　局部环境更新

随着智能体与智能体之间以及智能体与环境之间不断的相互作

用,其局部感知环境也在不断地发生变化.文献[8]中指出,agent象,可通过构造agent社会关系网模型来表示协作agent.,模型中熟人圈子的扩充方式,Strategy1:令a=(,neighbor(a)=(l1,l2,…,lm),在网格中随机选取位于(i,j),即neighbor(a)=(l1,l2,…,lm,b),其中trust2degree(a,i)=0.

Strategy2:假设b∈neighbor(a),c∈neighbor(b),有trust2degree(a,b)=1和trust2degree(b,c)=1,则

c∈neighbor(a),且trust2degree(a,c)=0.

类似地,其局部环境缩减方式为:假设neighbor(a)=(l1,l2,…,lm,b),若trust2degree(a,b)=-1,则neighbor(a)=(l1,l2,…,lm).

智能体局部环境的扩充和缩减中涉及到可信任度trust2degree,该值记录了协作agent之间的历史活动信息,同时随着智能体的活动不断改变,具体改变方式在31312中进行说明.313　智能体行为

智能体的行为包括4种:竞争算子、协作算子、变异算子和自学习算子.其中竞争算子和协作算子作用在agent与其局部环境中的agent之间,实现agent的竞争和协作行为,变异算子和自学习算子是作用在单个agent之上,实现agent利用自身知识的学习.31311　竞争算子

竞争算子的作用是剔除网格上能量较低的智能体,提高整体的能量水平.假设执行竞争操作的智能体为agenta,其局部环境中能量最高的智能体为agentm,若energy(a)<energy(m),则执行竞争操作.借鉴协调勘探和开采的占据策略[9],定义占据概率Po,分别选择不同的策略产生新的智能体来替代agenta.假设body(a)=(a1,a2,…,an),body(m)=(m1,m2,…,mn),新产生的记为agentc,则body(c)=(c1,c2,…,cn),

两种占据策略描述如下:

Strategy1:启发式交叉,该方式有利于保留agenta的某些信息;

　,

ck=

xk　,

mk+U(-1,1)×(mk-ak)　,

(mk+U(-1,1)×(mk-ak))<　,

(mk+U(-1,1)×(mk-ak))>xk　,　k=1,2,…,n　,

其他.

(3)

Strategy2:逆转算子,该方法可以有效地将某一维的最优值很快扩散到整个空间当中.

社会协作的多智能体进化

第2期　　　　　　　　　　　　　　　潘晓英等:社会协作的多智能体进化

277

m′k=(mk-)(xk-)　,k=1,…,n　,

′′′′′′

new′=(c′1,c2,…,cn)=(m1,…,mi1-1,mi2,mi2-1,…,

′′′

m′i1+1,mi1,mi2+1,…,mn)　,

1<i1<n,1<i2<n,i1<i2　,

k=1,…,n　.

(4)

ck=+c′k(xk-)　,

31312　协作算子

除竞争操作外,智能体还将与其局部环境中的智能体发生协作关系,以提高自身能量,这里采用了Leung[4]的正交交叉算子来实现.设定交叉概率为Pc,则智能体将以概率Pc+trust2degree3011与其局部环

境当中的智能体进行协作操作.

假设执行协作操作的智能体为agenta,agentb为neighbor(a)中的一员,两者间的协作操作表示为

)>energy(a),则合作成功,以a′a′=cooperate(a,b),若energy(a′替代原有的a,同时令agenta对agentb

δ;若energy(a′)<energy(a),则合作失的可信任度增加,trust2degree(a,b,t+1)=trust2degree(a,b,t)+

败,保持原有agenta不变,并降低其对agentb的可信任度,令trust2degree(a,b,t+1)=trust2degree(a,b,

)=energy(a),则保持原有的agenta以及可信任度不变.t)-γ;若energy(a′

313.3　非一致变异算子

网格上的智能体以概率Pm发生变异,.假设发生变异操作的智能体为agenta,body(a)=(a1,a2,…,an),:

当迭代次数为奇数()时,,agentg和

′′)=(g′agentg′,且有),n,(g′1,g2,…,gn),则可按式(5)产生一个新智能体

agente,body(e)1,en).

n

xk　,

ek=

　,

n

ak+(gk-gk)

′

i=1n

∑(∑(

g′i-gi)>xk　,

g′k=1,2,…,n　.i-gi)<　,　

ak+(gk-gk)

′

′

i=1

ak+(gk-gk)

i=1

∑(

g′i-gi)　,其他,

(5)

当迭代次数为偶数或为第一次迭代时,采用类高斯的变异方式.

ak　,U(0,1)<1/n　,

ek=

ak+G(0,1/t)　,

其他,

　k=1,2,…,n　.(6)

然后以agente代替原有的agenta.按方向变异能够快速得到一个可能更优的解,而穿插类高斯变异方

式可以保证算法具备跳出局部最优的能力.因此,这种非一致变异算子可以在加快搜索速度的同时有效地保持整个智能体种群的多样性.31314　自学习算子

自学习算子仅对每一代中的最优个体进行操作.对于函数优化问题,将局部搜索和遗传算法相结合能够更好的求解问题.因此,对智能体进行自学习可以通过对智能体进行局部搜索来完成,这里采用一个小规模的多智能体遗传算法[6]来完成.314　社会协作的多智能体进化算法

设Latt为第t代的智能体网格,Latt+1/3和Latt+2/3是Latt和Latt+1间的中间代智能体网格,Bestt是前t代所有网格中最优的智能体,CBestt是Latt中最优的智能体;

Step1　初始化Lat0,更新Best0,并令t←0;

Step2　对Latt中的每个智能体执行竞争算子,得到Latt+1/3;

社会协作的多智能体进化

　　　　　　　　　　　　　　　　西安电子科技大学学报(自然科学版)　　　　　　　　　　　　　　第36卷278

Step3　对Latt+1/3中的每个智能体,以概率Pc+trust2degree3011与其邻域内的智能体发生协作,执

行合作算子,并更新局部环境,得到Latt+2/3;

Step4　对Latt+2/3中的每个智能体,若U(0,1)<Pm,则执行非一致变异算子,得到Latt+1;Step5　从Latt+1中找出CBestt+1,并执行自学习操作;Step6　若energy(CBestt+1)>energy(Bestt),则令Bestt+1←CBestt+1,否则令Bestt+1←Bestt,CBestt+1←Bestt;

Step7　若终止条件满足,输出Bestt并停止,否则令t←t+1并转Step2.

4　仿真实验

采用以下6个无约束标准多峰函数来测试基于社会协作机制的多智能体进化算法的性能.

n

f1(x)=f2(x)=

i=1n

∑(-∑

2

1/2n

xisin(xi)),　S=[-500,500]　,

(7)

n

πxi)+10],　S=[-5112,5112]　,[xi-10cos(2

n

n

(8)(9)

n

i=1

f3(x)=

4000

i=1

∑

xi-

2

i=1

∏

cos

n

i

1/2

+1,　S=[-600600],

1/2

n

f4(x)=-20exp-012f5(x)=

i=1

x

2i

2

n

n

i=i

+e,　S=[-32,32]　,

n

(10)

n

y1)i=1

(y

i

πyi+1)]+(yn-1)-1)[1+10sin(

xi>a　,

22

+

i=1

∑u(x

i

,10,100,4)　,

m

k(xi-a)　,

u(xi,a,k,m)=0　,

k(-xi-a)

m

-a≤xi≤a　,　　yi=1+(xi+1),　S=[-50,50]n　,

　,

xi<-a　,

4

(11)

f6(x)=

10

n

n-1

πx1)+sin(3

2

i=1

∑(x

i

22

πxi+1)]+(xn-1)2[1+sin2(2πxn)]+-1)[1+sin(3

(12)

n

i=1

∑u(x

i

,5,100,4),　S=[-50,50]　.

首先对这些函数包含30维时的情况进行测试,同时与多智能体遗传算法[6]进行比较.设定两个算法中

的参数保持一致,分别为Lat为5,Po=012,Pc=011,Pm=011,自学习算子中网格规模为3,半径为012,概率为0105,迭代次数为10,SCMAEA中的γ=012,δ=011,终止条件为150代.另外,由于算法具有随机性,对每个函数均独立运行50次并取平均结果.

表1　30维函数的优化实验结果

测试函数

MAGA

f1f2f3f4f5f6

平均最优解

SCMAEA-1256914926

00000

MAGA

均方差

SCMAEA412580×10-14

00000

-1256914866

00

414400×10-16111420×10-20110390×10-17

711210×10-12

00

118450×10-18413900×10-20411960×10-17

在迭代150次之后,除f1之外,SCMAEA对其余的5个函数均可求得最优解,且其均方差为0,即50次

独立实验中均能找到函数最优解.对于全局最优解为-1256915000的f1,SCMAEA在50次实验中所求解

社会协作的多智能体进化

第2期　　　　　　　　　　　　　　　潘晓英等:社会协作的多智能体进化

279

的平均值为-1256914926,与全局最优解已相当接近,且其50次运行结果的均方差仅为412580×10-14,这说明SCMAEA在函数优化问题上不但具有良好的性能,而且还具备了较强的稳定性.而在相同的参数设置条件下,MAGA仅对其中的f2和f3求得了最优解,对于其他4个函数,尽管其求解精度非常高,但还存在着一定的误差.因此相比于MAGA,SCMAEA具有更强的优化能力

.

图3　两种算法的求解结果比较

为了更直观地给出两种算法MAGA与SCMAEA性能的比较结果,图3为以上6个函数的平均最优解随迭代次数增加的求解结果.对于函数f1,两者的性能比较接近;对于两种算法都能找到最优解的f2和f3,SCMAEA花费了更少的迭代次数即达到最优解;对剩下的3个函数,MAGA无法收敛到最优解,而SCMAEA可以,且花费的计算代价相对较低.在绝大多数测试函数上,SCMAEA的收敛速度要快于MAGA,这一点得益于SCMAEA中引入的局部环境更新方式,借助多智能体系统中的协作机制来实现进化

算法中个体的竞争与协作,加快了算法的收敛速度.

函数优化问题中搜索空间的大小和局部极值的个数都会随着问题维数的增高而增长,维数越高,问题的求解难度相对越大.因此为进一步研究该算法的扩展性,也就是对更高维函数的优化能力,对f1～f6这6个函数维数达到1000维时进行了实验,其终止条件为fbest<ε,其中fbest为算法所求得的解,ε=10-4.由于函数f1的最优解为非零,因此对于f1的终止条件设为fbest-fmin<ε3

表2　1000维的函数优化实验结果

测试函数

MAGA

f1f2f3f4f5f6

fmin,ε=10.取随机50次实验

-2

所用的平均函数评价次数以及所求解的均方差作为比较指标,表2为1000维函数优化的结果.

平均函数评价次数

SCMAEA171561665254255318903213727

平均最优解

MAGA-41898218184113260×10

-5

均方差

MAGA14.0317×10

-5

-5

SCMAEA-41898313148312150×10113840×10-5614850×10-5114150×10-5110940×10-5

SCMAEA1013315×10-5116×10-5813×10-6312×10-5311×10-5

2282720083735872881121417829

213520×10-5813270×10-5316580×10-5411260×10-5

816×10-6118×10-5316×10-5315×10-5

当终止条件设为求解精度时,两种算法所得的平均最优解的质量均在同一水平上,此时SCMAEA所需的平均函数评价次数大大少于MAGA所需的评价次数.其原因是SCMAEA利用了智能体间的协作机制,

社会协作的多智能体进化

　　　　　　　　　　　　　　　　西安电子科技大学学报(自然科学版)　　　　　　　　　　　　　　第36卷280

采用可信任度来度量智能体之间的历史合作关系,并不断对局部环境进行更新,加速了智能体的进化速度.

5　结束语

在多智能体系统与进化算法相结合的基础上,引入了一个表示智能体之间联系的熟人关系网模型,用以构建和更新智能体的局部环境,同时以可信任度来表示智能体间的历史活动信息,控制智能体之间的相互作用,加快了算法的收敛速度.除此之外,构造了一个非一致变异算子,加强其局部搜索能力,保证整个智能体种群的多样性.通过几个典型的标准测试函数证明了算法的有效性,与多智能体遗传算法MAGA的比较表明:该算法可以很好地克服陷入局部最优的情况,具有较强的局部搜索能力和较快的收敛速度.参考文献:

[1]VaddeKK,SyrotiukVR,MontgomeryDC.OptimizingProtocolInteractionUsingResponseSurfaceMethodology[J].

IEEETransonMobileComputing,2006,5(6):6272639.

[2]汪西莉,刘芳,焦李成.基于概率模型的遗传算法[J].西安电子科技大学学报,2002,29(3):3472350.

WangXili,LiuFang,JiaoLicheng.AGeneticAlgorithmBasedontheProbabilityModel[J].JournalofXidianUniversity,2002,29(3):3472350.

[3]杨淑媛,刘芳,焦李成.一种基于量子染色体的遗传算法[J].,(1):76281.

YangShuyuan,LiuFang,JiaoLicheng.ANovelGeneticon[J].JournalofXidianUniversity,2004,31(1):76281.

[4]LeungYiuwing,WangGwithQuantizationforGlobalNumericalOptimization

[J].IEEE,,5(1):41253.

[5]KazarlisSA,SEJB,etal.MicroGeneticAlgorithmsasGeneralizedHill2climbingOperatorsfor

GAOptimization].IEEETransonEvolutionaryComputation,2001,5(3):2042217.

[6]ZhongWeicai,LiuJing,XueMingzhi,etal.AMultiagentGeneticAlgorithmforGlobalNumericalOptimization[J].

IEEETransonSystems,ManandCybernetics,2004,34(2):112821141.

[7]LiuJiming,HanJing,TangYY.Multi2agentOrientedConstraintSatisfaction[J].ArtificialIntelligence,2002,136(1):

1012144.

[8]陈刚,陆汝钤.关系网模型———基于社会合作机制的多Agent协作组织方法[J].计算机研究与发展,2003,40(1):1072

114.

ChengGang,LuRuqian.TheRelationWebModel—aOrganizationalApproachtoAgentCooperationBasedonSocialMechanism[J].JournalofComputerResearchandDevelopment,2003,40(1):1072114.

[9]江瑞,罗予频,胡东成,等.一种协调勘探和开采的遗传算法:收敛性及性能分析[J].计算机学报,2001,24(12):12332

1241.

JiangRui,LuoYupin,HuDongcheng.AGeneticAlgorithmbyCoordinatingExplorationandExploitation:ConvergencePropertiesandPerformanceAnalyses[J].ChineseJournalofComputers,2001,24(12):123321241.

(编辑:齐淑娟)　　

本文来源：https://www.bwwdw.com/article/yf21.html