摘要多主体系统是目前人工智能研究的热点之一,多个主体通过协调和通讯这些自组织过程完成单一主体很难完成的功能。但是,如何定量分析主体在自组织过程中的行为和它们的相互作用是一个比较困难的问题。我们提出了一种基于信息论的定量分析多主体系统群体行为的方法,通过多主体系统中所有主体信息熵的均值分析多主体系统的整体行为,并通过主体对之间的互信息分析多主体系统中主体间的相互作用。通过粘液菌模型进行的验证实验表明所提出的方法可以定量分析主体的行为模式。
关键词群体行为 多主体系统 信息理论
中图分类号:TP3文献标识码:A
0 引言
自上世纪九十年代以来,随着计算机网络技术的发展,智能主体和多主体成为人工智能研究的一个热点,它可望将人类从浩瀚无边的信息海洋中解放出来,使用户只关注自己感兴趣的信息。目前,智能主体技术已在决策支持、①故障诊断、②商业市场建模③等很多领域得到成功应用。在很多情况下,我们所使用的主体都不只一个,多主体系统研究一组自治主体之间智能行为的协调,让很多智能主体协同在一起为完成一个共同的目标服务,这些自主主体通过主体间以及主体与环境间的相互作用进行合作。④
每个智能主体都有自己的独立目标,但从整体上看,多主体系统表现为一个整体。因此,研究单独主体的局部行为与多主体系统总体行为的一致性对设计多主体系统是非常重要的。在衡量一个多主体系统时,人们常使用目标完成比例和目标完成代价作为衡量系统整体行为的测量指标。这些测量指标从主体们需要完成其任务的角度来看是非常重要的。但是,这些测量标准对弄清楚多主体系统中各个主体的行为是不够的,因为很难说清楚一个主体为什么会得到高分以及它是如何得到高分的。而且这两个测量指标对不同的系统其标度也不相同,不利于不同系统间进行比较。
热力学第二定律指出如没有外部能量的作用系统总是趋向于无序,而多主体系统局部行为与总体行为的一致性表明系统在自组织状态下是趋于有序的。使多主体系统有序化的原因是因为信息的加入,而信息熵是一种广泛使用的量度信息的方法,因此有研究者提出可使用信息熵来分析多主体系统的动态自组织行为。⑤⑥⑦我们在本文中提出了一种新的基于信息论的定量分析多主体系统的方法,其在于分析系统的自组织行为及主体间的相互作用。我们所提出方法与其他方法的不同之处在于该方法不仅可定量分析系统的整体行为而且可以定量分析主体间相互作用的强度。
1 主体间相互作用
一般认为主体间的相互作用等同于交换主体状态的信息。由信息理论我们可以知道多主体系统中信息和熵之间的关系,信息增加将引起熵的减少,而信息减少将引起熵的增加。因此,可通过熵来度量主体的相互作用和自组织行为。
考虑一个多主体系统S,它具有N个主体s1,…sn,…sN,这些主体之间按概率规则互相联系、互相制约。各个主体的出现概率分别是p1,…pn,…pN。可通过这些主体的概率函数――熵来描述S的不确定性:
H(S) = -pnlogpn
当满足条件pn = ,n=1,…,N时,H(S)取最大值,记为H0,即H0 = [H(S)]max = logN。它表示系统具有最大的不确定性,各个元素完全以随机的方式,互相无关的实现。
因为主体出现的概率我们很难得到,以上的计算公式虽容易理解但不方便计算。我们使用各个主体熵的平均值来分析多主体系统的整体行为,例如:稳定性、约束或复杂性;由信息论我们知道,互信息意味着两个随机变量间信息交流的强度,如果两个随机变量是完全独立的,那么他们之间的互信息为零。因此,我们使用每个主体对的互信息来分析两个主体相互作用的强度。
当计算这两个指标时,需要知道主体的状态。一个主体是一个独立的自治体,它通过传感器从环境中得到输入并通过一个决策过程输出结果,但主体的决策过程依赖于它的内部行为模式,不同的系统其内部行为模式可完全不同。为了在分析主体的行为时不局限于特定的系统,使用主体的内部行为模式参数是不合适的,为此我们使用主体的输入和输出作为主体的状态。
为计算熵和互信息我们需要:
(1)主体X的状态集x∈{x1,…,xn}(也就是输入和输出);
(2)主体X处于某一个状态的概率p(x)。
一个主体X的熵以及X主体Y和间的互信息可定义如下:
H(X) = -p(x)logp(x)
I(X:Y) = p(x,y)log
2 信息学测量指标
为校验以上方法的可行性,我们通过一个简单的自组织模型―粘液菌模型(Slime Mold Model)对以上概念进行实验。
2.1 粘液菌模型
粘液菌细胞的群体行为在自组织系统中研究很多。⑧通常,它们作为独立的变形虫利用它们的伪足四处移动,其行动符合随机规律。但当环境条件恶化时,这些变形虫突然改变了它们的行为并聚合为一个单一的多细胞体。在这个聚合过程中,它们发出一种称为cAMP的化学信号来引导群体运动。当它们移动时,它们随着环境中cAMP的变化而移动。整个聚合过程是一个自组织过程,尽管所有的变形虫根据其自身的局部信息行动,但它们最终会自动聚合到一起。
在粘液菌模型中,变形虫主体被置于图1所示的网格中。主体及其环境模型描述如下:
图1粘液菌模型环境
2.1.1 主体模型
每个主体按照以下的步骤工作:(1)cAMP放在当前格中;(2)在8个邻域中嗅探前向三个网格的cAMP浓度;(3)动到具有最强cAMP浓度的网格。
2.1.2 环境模型
在周围环境中,cAMP被表示为T(x,y)和P(x,y),其中T(x,y)表示网格(x,y)上cAMP的数量,而P(x,y)表示网格(x,y)上cAMP的浓度。主体可以在网格上嗅探cAMP的浓度。
随着时间的推移,cAMP会挥发和扩散,每一步完成后,T(x,y)和P(x,y)变成T*(x,y)和P*(x,y)
T*(x,y) = (1-γeva)T(x,y)+△T
如果有一个代理在网格(x,y)上,其他情况
P*(x,y) = P(x,y) + γdif{P(x-1,y)+P(x+1,y)
+P(x,y-1)+P(x,y+1)-5P(x,y)}+γevaT(x,y)
其中Q表示主体在第一步释放的cAMP数量,而γeva和γdif表示cAMP的挥发率和扩散率。
2.2 粘液菌模型参数
在粘液菌模型中,由挥发率和扩散率定义的cAMP属性会影响主体的自组织过程模式。在我们的实验中,我们比较了不同的模式以及熵和互信息分布的关系。
实验环境是一个50×50的网格世界,共包含了50个主体。我们根据时间长度和精度改变cAMP的属性。挥发和扩散率的值被设为以下四个不同的值:
a. γeva = 0.1,γdif = 0.1
b. γeva = 0.1,γdif = 0.3
c. γeva = 0.5,γdif = 0.1
d. γeva = 0.5,γdif = 0.3
我们使用这些参数进行了1000步实验。
2.3 熵和互信息的计算
主体的输入是主体前向方向上三个网格的cAMP的浓度,而输出是主体的移动方向,测量这些状态需要观察主体的每一步行动。为了观测这些概率,我们使用了蒙特卡洛方法,通过统计这些状态在一个实验中各个步骤上的值来估计这些概率。
3 实验结果
实验结果如表1所示:
表1粘液菌模型中主体的熵和互信息的分布情况
表1显示了每一种参数(a~d)所对应的熵和互信息。和V(I)表示随机选择的10对主体间互信息的均值和偏差,和V(H)表示所有主体的熵的均值和偏差。rId表示主体间欧式距离与互信息的相关系数。实验结果表明,当选择参数a和c时,互信息的均值要大于选择参数b和d时。因此,选择参数a和c时,主体之间的相互作用要强于选择参数b和d时。当选择b和d时,熵的均值较小,表示主体的状态是稳定的。
通过运行startLogo仿真程序,⑨我们可以观察到:当选择参数a和c时,很多主体自组织为群体;而当选择参数b和d时,很多主体是独立行动的。这些主体的行为模式可以通过熵和互信息反映出来。同时,rId的值显示当两个主体越近时,它们间的相互作用越强烈。
我们在实验过程中同时可以观察到:当选择参数a和c时,因为相互作用的强度,主体再构成一个群体后随即解体,构成一个新的群体。而在选择参数b和d时,当主体构成一个群体后,该群体很少被重构。该行为模式与熵的分析结果一致,即主体的状态在选择参数b和d时比选择a和c时稳定。
4 结束语
研究主体的自组织行及主体间的相互作用对理解群体智能的作用机理具有重要作用。我们从信息论入手,提出了一种使用熵和互信息来定量分析主体间相互作用的方法。在粘液菌模型上进行的实验结果验证了我们所提出的方法能够定量表示主体的群体行为及它们之间的关系,表明我们所提出的方法是可行的。
★基金项目: 国家863计划项目(2005AA12150)
注释
①陈宏伟,袁国斌.基于多智能代理的分布式决策系统实现[J].计算机应用研究,2002.18(8):46-50.
②李卫宁.基于MAS的智能诊断技术集成方法研究[J].运筹与管理,2005.14(5):13-17.
③周晓俊,张申生,周根春.基于约束的智能主体及其在自动协商中的应用[J].上海交通大学学报,2005.39(4):574-577.
④Wooldridge M,Introduction to MultiAgent Systems[M], Chichester, UK, John Wiley & Sons, 2002:46-58.
⑤Guerin S, Kunkle D, Emergence of Constraint in Self-Organizing Systems[J]. J. of Nonlinear Dynamics, Psychology, & Life Sciences,2004.8(2):131-146.
⑥Parunak H V D, Brueckner S, Entropy and Self-organization in Multi-Agent Systems [C].Proceedings of the International Conference on Autonomous Agents. 2001:124-130.
⑦⑨Balch T, Hierarchic Social Entropy: An Information Theoretic Measure of Robot Team Diversity [J],J. Autonomous Robots. 2000.8(3):209-237.
⑧Resnick M , Turtles, Termits, and Traffic James: Explorations in Massively Parallel Microworlds [M], Cambridge, US, MIT Press,1997:59-68.