（计算机软件与理论专业论文）蚂蚁劳动分工策略的计算场建模及其在资源调度中的应用.pdf

蚂蚁劳动分工策略的计算场建模及其在资源调度中的 应用 计算机软件与理论 硕士生：石现 指导老师：张治国副教授 摘要 并行分布计算是当前计算机科学的热点之一。资源调度又是影响分布计算的 关键因素，也是一个具有挑战性的课题。 本文基于蚂蚁劳动分工策略，将新型协调模型计算场的思想与之结合，建立 了一种直观、简便而且能降低通信成本和决策算法成本的新模型，并把它应用到 分布计算中去。 本文的研究目的并不在于论证该模型在资源调度算法中的重要地位雨在于 它将动物的群体智慧转化成资源调度算法，并且将新的协调模型计算场的直观性 和有效性展现给大家。这两个方面的思想对于计算机科学以后的发展道路都具有 非常积极的意义。 本文主要采用对比的论证方法。从虚拟空间的定义、场的定义、运动方程及 其系统行为方程的建立到实验、测试以说明模型的有效性，都与前人的成果进行 比较，突出新模型与原模型的差别，论证它的优点。由于计算场本身具有直观性， 所以本文还采用了图示法。因此，整个分工过程已经由图形呈现出来了。 本文所建模型与前人数量模型相比，专业化区别更加明显，解决了滞后性， 并且协调起来更加灵活，更重要的是能够节省通信及其决策算法的计算费用。 关键词：蚂蚁劳动分工，计算场，资源调度，任务刺激强度，反应极限 t h ec o f i e l d sm o d e lo fd i v i s i o no fl a b o ri na n t s s o c i e t ya n d i t sa p p l i c a t i o ni nr e s o u r c es c h e d u l i n g s o f t w a r ea n dt h e o r e t i cc o m p u t e rs c i e n c e n a m e ：s h ix i a n s u p e r v i s o r ：z h a n gz h i g u o a b s t r a e t t h ep a r a l l e la n dd i s t r i b u t e dc o m p u t i n gi sah o t s p o to fc o m p u t e rs c i e n c et o d a y t h er e s o u r c es c h e d u l i n g ，w h i c hi sap r o b l e mf u l lo fc h a l l e n g e s ，i sak e yf a c t o ro fi t t h i st h e s i sb a n d st h en e wc o o r d i n a t i n gm o d e l c o f i e l d s ”a n dt h es t r a t e g yo f d i v i s i o no fl a b o ri na n t ss o c i e c ym g e t h e r t h e ni tb u i l d sa ni n t u i t i o n i s t i cm o d e l w h i c hc a nr e d u c et h ec o s to nc o m m u n i c a t i o na n dd e c i s i o n m a k i n g f i n a l l yi ta p p l i e s t h em o d e lt ot h ed i s t r i b u t e dc o m p u t i n g t h ei n t e n t i o ni sn o tt oa r g u et h es t a t u so ft h en e wm o d e li nr e s o u r c es c h e d u l i n g i st ot r a n s f e rt h ea n i m a l s s w a m ii n t e l l i g e n c ei n t ot h es t r a t c ，g yo fr e s o u r c es c h e d u l i n g a n de x h i b i tt h es i m p e ra n di n t u i t i o no ft h ec o f i e l d st oy o u t h ei d e a so ft h e s et w o a s p e c t sh a v ev e r yi m p o r t a n tm e a n i n gf o rt h ec o m p u t e rs c i e n c ed e v e l o p m e n t t h i st h e s i sa d o p t sa na n t i t h e s i s f r o mt h ed e f i n i t i o no fv i r t u a ll o o m ，t h e d e f i n i t i o no ff i e l d s t h eb u i l d i n go fm o v e m e n te q u a t i o na n ds y s t e m - a c t i v i t i e se q u a t i o n ， t ot h ee x p e r i m e n t sa n dt e s t st or e a s o l af o rt h ev a l i d i t yo ft h en e wm o d e l 。i ti sf u l lo f c o m p a r i s o nt ot h eo l dm o d e l i te m p h a s i z e st h ed i f f e r e n c e sb e t w e e nt h et w o ，s u p p o r t s t h ee x c e l l e n c eo fn e wm o d e l b e c a u s eo ft h ei n t u i t i o no fc o - f i e l d s ，t h i st h e s i sa l s o a d o p t st h eg r a p h o l o g y s ow ec a ns a yt h a tt h ew h o l ed i v i s i o np r o c e s si se x h i b i t e dw i t h t h e s ec h a r t s c o m p a r i n gt ot h eo l dm o d e l 。t h en e wm o d e l i e t st h es p e c i a l i z a t i o nd i f f e r e n t i a t i o n b em o r eo b v i o u s ，t h eh y s t e r e s i sh ea b s e n t ，a n dc o o r d i n a t i o nb em o r ef l e x i b l e t h e m o r ei m p o r t a n ti sr e d u c i n gt h ec o m m u n i c a t i o nc o s ta n dd e c i s i o n m a k i n gc o s t k e yw o r d s ：d i v i s i o no f l a b o r i na n t ss o c i e t y 、c o - f i e l d s 、r e s o u r c es c h e d u l i n g 、 t h es t i m u l a t i n gi n t e n s i o no fd u t y 、t h er e s p o n s et h r e s h o l d 1 1 第1 章问题陈述 并行分布计算是当前计算机科学的热点之一。调度算法是影响分布计算的关 键因素，也是一个具有挑战性的课题。本文企图把蚂蚁劳动分工策略这个生物界 的成功范例，用计算场( c o - f i e l d s ) 这个新型的协调方法建模，并把它归位到分 布式计算的资源调度问题( 主要是任务分配问题) 。 1 1 基本概念 论文题目中的两个主要概念是：计算场和蚂蚁劳动分工策略。下面分别介绍： 1 l1 计算场( c o - f i e l d s ) 1 1 。l t l 由来 在分布式计算特别是无处不在的计算( p e r v a s i v ec o m p u t i n g ) 场景中，要使智 能体之间进行可适应的和有效的协调。既要使智能体在获得环境信息方面所花的 代价最小，也要使智能体在按照这些信息与其它智能体协调方面所花的代价最 小。计算场思想主要是基于这些考虑和目标：向智能体提供理想简单但是有 效的环境描述，使专门的协调动作能够由智能体花最小代价实现，也能够动 态地适应执行场景的灵活性。 它得益于物理学中的“力场”概念。科学家企图用这种连续的数据结构来对 分布式环境特别是多智能体系统进行描述。它的中心思想是把使智能体自动协调 起来的所有活动委托给基础结构。希望基础结构建立一个特别为智能体协调任务 设计的全局环境视野。智能体感知这个专门协调视野，能够轻松达到它们的目的， 因为视野确切地表征了智能体协调任务的环境。这样，当基础结构负责特制这种 人为的专门协调视野的同时，智能体只需决定它们是否要遵循这个预备的协调原 则，而不需要什么复杂的决策算法。这些特征也意味着智能体的活动是自动适应 动态环境的，即环境视野的改变不需要智能体改变自身。提出计算场的全部含义 都是基于整体设计远景，智能体不需要单独设计，只作为全局组织的一部分。利 用这种方法，智能体能够达到目标并不是因为作为独立个体的能力，而是因为它 们是自主组织系统的一部分，这个系统引导它们达到目标。也就是说。能够达到 目标不是单个智能体的功劳，而是整个系统协调作用的成果【l 】。 1 1 1 2 核心 2 1 ) 环境被表示和抽象为“场”，由智能体和环境本身传播。这些“场” 传播一些直接对智能体协调任务有用的信息，并且向智能体提供完 成协调任务所需要的环境感知能力。 2 ) 协调策略通过让智能体顺着“场”的坡度移动来实现。 3 ) 环境的动态变化和智能体的运动导致“场”表面的变化，这就形成了 一个反馈机制，以至影响智能体的迸一步运动。 4 ) 这个反馈机制使得系统( 智能体和环境) 自动组织起来，协调任务得 以完成。 1 1 1 3 特点 1 ) 基本构造：一个唯一标志、基于位置的数值( 场势) 、一个传播规则。 2 ) 物质要求：一个适当的基础结构或中间件。这个中间件可以基于某 个负责存储场量值的外部服务器，也可以嵌入智能体本身、采取智能体 之间特殊的交流方案。 3 ) 动态场和静态场：场值随时间变化而变化的场为动态场否则为静 态场。 4 ) 简单场和协调场：专门定义的场为简单场，简单场的线性组合为协 调场。 5 ) 运动方式：个体的运动方式，我们可以根据具体的协调任务来定义。 可以定义个体从低势走向高势( 上坡) ，也可以定义个体从高势走向低 势( 下坡) ，还可以定义沿等势线移动。 l _ 1 1 4 举例说明 如图卜1 所示，这是表示x 的个人存在场。它的意义在于：x 所在的位置 场值为1 ，其它位置随着离x 的距离增加，依次增l 。越是远离她，场值就越大。 因此，若是要找x ，只需找到x 的个人存在场的最小场值所在位置就行了。若 是要远离x ，只需朝场值增大的方向走就可。例如图中的 ，正朝着远离x 的方 向运动( 上坡) 。另外，如果x 移动位置，那么x 的存在场就会随之变化。如果 y 要和x 保持一定的距离，y 就得定时感应x 的个人存在场是否发生了变化， 从而来修正自己的位置。我们从此例可看出，计算场确实是人们为了某种协调目 的而虚构的场。它利用位置之间的势差来促使个体的运动。单位距离之间的势差 越大，则运动速度越大。 图卜1 个人存在场 1 i 1 5 发展现况 利用计算场为多智能体系统建立数量模型已经有多例：博物馆 1 、狼围捕鹿 3 、城市交通控制 4 等。不过到现在为止，计算场模型的实现只限于在多智能 体模拟环境中，模拟基于j a v a 和s w a r ms i m u l a t i o nt o o i k i t 。 i 1 2 基于反应极限机制的蚂蚁劳动分工策略 对于社会性昆虫来说，不同活动经常是由各专门个体分别同时进行的。这种 现象称为劳动分工。它的主要特点是可塑性：随着内部动荡或外部挑战，承担各 种任务的个体数量是变化的。一种基于反应极限的机制可解释蚂蚁是怎样达到劳 动分工的灵活性和专门性的【5 】。每个个体都有对每个任务的反应极限，也可以 说是个体对每个任务都有一个忍耐限度。当某个任务的刺激强度超过个体的该反 应极限值时，个体便参与执行这个任务。当任务刺激强度低于该反应极限值时， 个体就放弃该任务。这样，每个个体可根据群体需要来调整任务刺激强度。并且， 一旦执行某个任务，个体对该任务的反应极限值会逐渐减小。一段时问没有执行 给定任务，则会导致相关反应极限值的增大。这是专门化的主要策略：个体若在 过去执行某任务的次数越多，它在以后就越可能参与执行该任务。可塑性的表现 是：若本来执行某任务的个体被撤除后( 它们的反应极限低于该任务的刺激强 度) ，该任务相关要求将会增加，直到它达到其余那些本来拥有更高反应极限的 个体的极限值( 这些个体原本没有执行过该任务) 。刺激强度超过极限以外的部 分用来刺激这些个体参与到任务中去。 1 2 背景 1 2 1 协调模型 近年来，除了计算场以外，人们针对多智能体系统的协调问题，提出了一些 协调模型和中间件，可简单分为三类 6 ： 1 2 1 1 直接通信模型 该模型的组件之间以直接的方式通信。智能体被置于“无效”空间中：空间 不提供任何环境信息，只能让智能体主动感知其它组件并与它们交互。模型的中 间件大部分用来发现通信伙伴。每个智能体不得不通过发现环境中的其他实体来 “人为”地感知环境。这种方式不太适合多智能体系统场景的协调需要。它要求 智能体在计算和通信方面花很多代价，才能获得环境感知信息。系统如j i m 、 u p n p 、基于f i p a 智能体系统，还有p 2 p 系统如j x t a 都是基于这个模型的中间件 结构。 1 2 1 2 共享数据空间模型 该模型利用共享的位置数据结构，这些数据结构可以放于数据空间( n g l t 空 间) ，也可以由智能体携带。智能体在可模型化和可用数据空间信息描述的环境 中，数据空间可以从某位置获得，该位置向智能体提供环境信息，不强迫智能体 直接与其他智能体通信。但这种模型表达环境信息的是原始位置数据，不便于智 4 能体理解，以至于很难完成任务。协调决策由智能体在可获得数据基础上直接执 行( 要花费大量计算代价) 。t s p a c e s 、j a v a s p a c e s 、l i m e 和x m i d d l e 是这个模 型的代表。 1 2 1 3 基于事件公布订阅模型 该模型的组件利用产生事件以及对感兴趣的事件产生反应来互相作用。它能 够促进更强大的环境感知能力。组件可被认为是存在于能够通知它们所发生事件 的积极环境中。这使智能体从主动询问环境或其他智能体的要求中解放出来，促 进了软件系统在计算和通信方面的有效性。但它还是太复杂了，即使智能体被提 供所需的所有信息，还必须应用个复杂的决策算法才能通过内部信息做出要到 哪里去的决定。这个模型的典型结构有：j e d i 、j i n i 分布式事件和u p n p 一般事 件公告结构( g e n a ) 。 因此，以上3 类模型与计算场相比，不足之处主要是：通信费用很高或决策 算法复杂，这两方面中的任一方面都导致了它们不适合分布式环境。 1 2 2 资源调度问题的策略 1 2 2 1 调度策略现状 现有的许多调度技术一般以任务的执行时间为基础 7 ，把重点集中在负载平 衡上，忽略了任务与处理机之间的关系。因而会做出一些盲目的调度。造成这种 状况的一个很明显的原因是，同时考虑负载平衡和任务与处理机之间的关系会增 加调度的复杂性；另一个原因是分布调度对存取任务与处理机之间关系的能力有 限。 1 2 2 2 社会性昆虫给人们的提示 社会性昆虫为我们提供了开发分布式系统( 拥有简单交互的多智能体) 的生 动比喻a 它们自然而生的集体智慧群体智能仰仗的不是复杂的单个个体 能力，而是个体与个体之间、个体与环境之间的不断交互。关于社会性昆虫的生 态成功的证据比比皆是。其中，以反应极限机制为基础的蚂蚁劳动分工策略可以 转化为分布式的资源调度( 特别是任务分配) 策略 8 。人们欣喜地发现，这种 策略不仅巧妙地解决了任务与处理机之间的关系问题，还可以使能者多劳( 提高 效率) ，使物尽其用，人尽其能( 负载平衡) 。 因此本文有了利用计算场协调思想，将蚂蚁劳动分工策略应用到资源调度中 的想法。 1 3 论文内容 1 3 1 任务 本文要做的是把新型策略( 蚂蚁劳动分工策略) 运用新型协调方法( 计算场) 建成数量模型，证明其有效性，并把它应用到多智能体系统的资源调度中。 1 3 2 目标 用数学分析软件画出用计算场模型模拟的蚂蚁劳动分工策略的基本过程，证 明模型的有效性，并将其归位到多智能体系统的资源调度中。 1 3 3 方法、步骤 1 3 3 1 建立模型 1 ) 定义空间 蚂蚁劳动分工是对任务的分配，与物理位置无关，所以还必须建立一个虚 拟的空间。 2 ) 定义场 根据影响分工的主要因素及其数量关系，定义简单场，组成协调场。 3 ) 建立运动方程 根据定义的空间意义和场意义，各因素之间的关系，建立个体运动微分方 6 程。 4 ) 建立系统行为模型( 方程组) 综合个体运动微分方程、运动对场的反馈方程建立整个系统行为方程组。 1 3 3 2 模拟实验、分析结果 在数学分析软件m a t h e m a t i c a 上模拟场景、测试其有效性，并且与前入的数 量模型作比较。指出新模型的优点。 1 3 3 3 应用 根据新模型的特点、类别将其归位到多智能体系统的资源调度方法中，并举 例说明。 1 3 4 意义 本文对资源调度和计算场两方面都具有积极的意义： 1 ) 一旦能在数学分析软件中模拟出蚂蚁劳动分工过程，就证明了用计算场描述 该策略的有效性，为最后编程实现提供了可能。一旦实现，便可将这种策略应用 到分布式的资源调度问题中( 只需将协调场的某些参数改变或赋予不同的含义) 。 2 ) 一旦证明了用计算场描述该策略的有效性，便为计算场建模开辟了新路，扩 大了建模范围，也为计算场成为多智能体系统协调模型的标准提供了有力的证 据。 7 第2 章相关研究 2 1 两种概率控制模型 生物社会学家们通过各种实验，总结出蚂蚁劳动分工策略的两种基于反应极 限机制的概率型数量关系：固定反应极限模型和变化反应极限模型。 2 t 1 固定反应极限模型 为了解释w i l s o n 在蚁群中观察到的现象，b o n a b e a u 提出了一种基于反应极 限的简单模型 9 。他的观点是每个个体对于各种任务都有一个极限值。极限代 表了个体对某任务的专业化程度。一项任务引发一个刺激以吸引个体的注意。刺 激强度越高，个体就越注意这个任务，以致接受执行任务，反之亦然。该模型被 称为固定极限是因为极限不会随时间变化而改变。 设有1 个任务要执行，它有相关的刺激机制和要求。若要求没有得到满足， 刺激就会增大( 由于没有足够的个体参与或是效率不高) 。假设有个个体，分 别用j ；暴记，都有对于该任务相关刺激的反应极限毋( f = 1 ，n ) 。用s 表示 任务刺激强度。那么，个体f 参与任务的概率为： c 2 ( 5 ) 3 南f 治1 设n 个个体分为两种个体( 由于研不同) ，, 7 1 和n ：分别是两种个体的数量 ( 伪- i - n ：= n ) 。设f = ，l l n ，是第一种个体占整个个体数的百分比。设1 ，2 分 别是两种个体中，参与执行任务个体的数量。而玉；l ，玛，毛= n 21 n 21 ，分别是 参与任务个体占该种个体数的分数。五，t 的变化方程为： 1 ，屯也可定义为每个个体单位时间内执行该任务的时间百分数，变化反应极限模型中一般使用这个定 义。 a t 玉2 五( 5 ) ( 1 一葺) 一肼( 2 2 ) o , x 2 = ( j ) ( 1 一x 2 ) 一p x 2 假设一个原本活动的个体放弃任务、变成非活动状态的概率为p ( 每单位时间) ， ( 我们假设对于所有的个体和任务，p 是相同的) 。方程右边减式的第一部分表 示本来未参与执行任务的但在本单位时间内参与到任务中的个体数百分比。第二 部分表示本来执行任务的但在本单位时间内放弃任务的个体数百分比。刺激s 的 变化方程为： a ，s = 占一n i + 2 ) ( 2 3 ) a , s = - - o q c x l - a ( i - f ) x 2 ( 2 4 ) 其中，万是单位时间内刺激强度的固定增量，活动个体需要完成的任务量用个体 数 ，来衡量。口是衡量执行任务效率的等级因数。本文设j 、口这两个因数对所 有任务都是相同的。o r 不随时间变化，与个体无关。但在现实中。口可随专门化 的程度不同而不同。( 2 3 ) 式右边减式的第二个部分表示单位时间内参与个体完 成的任务分数( 完成任务速度) 。( 2 4 ) 式由( 2 - 3 ) 式转变而来，因为它表示的 s 与玉，屯的变化关系更为明显，我们一般使用( 2 4 ) 式。 该固定极限模型假设：个体对任务的反应极限是固定不变的，所以它们对于 某给定任务的专业程度也是不变的。然而，该模型不能解释蚁群的可塑性。它的 有效性仅限于很短的时间内。 2 1 2 变化反应极限模型 为了解释固定反应极限模型无法解释的现象，t h e r a u l a z 改良了该模型 8 。 它允许极限随着时间的变化而有规律的变化。 设有m 个任务要执行，分别用，表示。它们有相关的刺激机制和要求，用已表 示。若要求没有得到满足，刺激就会增大( 由于没有足够的个体参与或是效率不 高) 。假设有个个体，分别用沸i 记，都有对于每个任务相关刺激的反应极限岛 ( f = 1 ，n ：，= l ，m ) 。那么，个体f 参与任务的概率为： ( 2 1 ) 岛以一种自我修正的方式更新。个体f 越多地执行，任务，岛就越小，反之 成立。设善、妒分别为学习参数和遗忘参数。那么，在个体国行( 放弃) 任 务| 时间后，会对j 任务的刺激更加( 更少) 敏感： 当i 进行j 纽时间后，岛j 岛一缸 当f 放弃ja t 时间后，甘岛+ 舭f 设为单位时间内f 花在j 上的时间分数：在f 时间内，f 进行j 用掉时间r ， 进行其它任务用掉时间o - x o ) t a 。那么又有了以下的式子 岛- 岛一气缸+ ( 1 一) 础 给出连续方程： 鲁= ( 1 _ 勘炉嘞胡。( 岛一。( 一岛) ( 2 _ 5 ) 其中，o o 是个阶段函数( o ( ) ，) = o 当y - o ) ，o ( ) 用来保证岛 在界定范围之内的平均时间动力由以下方程给出： 誓吲嘣l 一砉驴毗 ) ( 2 - 6 ) 方程右边第一个乘积式描述把卜靠中的多少时间分数分配给j 任务。第二个 乘积式假设一个活动个体放弃任务、变成非活动状态的概率为p ( 每单位时间) 。 个体花在j 任务上的平均时间( 在放弃之前) 是l ，p 。这里假设p 是固定的，对 于所有任务和个体都相同，并且与刺激无关。个懈f _ l l p 时间后放弃任务，但若 刺激强度仍然很大，它可能马上又参加这个任务。( f ，f ) 是关于变量盯2 的高斯 1 0 寿 一一 )0 飞 随机过程，跟时间无关，也跟个体、任务无关： v f ，j ，t = 0 ( 2 - 6 1 ) v i ，j ，h ，k ，t ，t 妒( f ，j ，f ) 缈 = c r 2 8 0 ( i - h ) 点o ( j k ) 8 0 ( t t ) ( 2 6 2 ) 其中，皖是d i r a c 分布，w ( i ，j ，f ) 是用来模仿个体遇到不同情况的随机式。为了 简单起见，每个任务要求以固定的速率增加。s ，( j 任务的刺激强度) 的动态过 程可被描述为： 鲁小号c 缸吲 其中，占是单位时间内刺激强度的固定增量，口是衡量执行任务效率的等级因数。 设这两个因数对所有任务是相同的。口不随时间变化，与个体无关。但在现实中， 口可随专门化的程度不同而不同。活动个体执行的任务量用个体数n 来衡量。 2 2 前人所构想之计算场模型 计算机科学家们正积极地为把动物群体活动策略，应用到为多智能体系统建 立灵活、健壮的计算场模型而努力。已有人提出把基于反应极限机制的蚂蚁劳动 分工策略建成计算场模型，然后将其应用在我们生产、生活中的资源调度问题中。 由于蚂蚁劳动分工策略并不是在物理空间中进行的，因此首先应该建立起一 个虚拟空间 3 。这是一个多维空间。一维表示一个任务。如图2 - 1 ，一只蚂蚁 位于有三个任务的系统空间中。蚂蚁的具体位置决定于它正在执行什么任务。每 根数轴表示对执行各任务的时间百分比度量( 个体执行速度是一定的) 。图中， 这只蚂蚁花去3 3 的时间执行任务a ，3 3 的时间执行任务b 和3 3 的时间执 行任务c 。 一般情况下，一只蚂蚁必须存在于 。x ， 1 0 0 的子空间内。它在 这个空间内活动，只表示任务的执行和转换，并不代表它的物理活动。如图2 2 所示，一只蚂蚁正渐渐放弃任务c ，而开始执行任务b 。在此空间内，进一步定 义了某种场，此场由蚂蚁感知和传播。它代表某种刺激，促使蚂蚁执行某项任务。 场的形态基本上是一个有坡度的曲面，曲面朝着任务轴方向降低高度。任务越是 紧急，场曲面下降的坡度越陡。如图2 3 所示，三个不同的任务a 场，曲面越陡， 说明任务a 越紧急。 图2 一l 图2 2 图2 - 3 并且，关于这样定义的场，已有了算法：每只蚂蚁计算它们所感知的各场的 组合，仅仅考虑那些坡度大于一定极限的场。蚂蚁顺着场曲面下坡。随着它沿着 某任务轴走，该任务的曲面会逐渐平坦起来，这是因为该任务逐渐得到完成。蚂 蚁将处在稳定的任务格局中，直到新的刺激出现，继而场曲面发生新的变形。图 2 - 3 中，任务场表面并不是单纯的斜面，它的坡度在两个方向上有所增加：任务 轴方向及其向任务轴弯曲的方向。这种非线性的形状是为了强调专门化。一方面， 增加轴方向的坡度，使得蚂蚁越是朝着该方向( 越是执行该任务) ，将来它便越 容易再次执行该任务( 因为场的坡度很大) 。另一方面，对轴弯曲的方向上的坡 度的增加( 对零) ，使得本来不执行该任务的蚂蚁也加入到此任务执行当中。 这个模型是l e t i z i al e o n a r d i 、m a r c om a m e i 和f r a n c oz a m b o n e l i 建立的a 但因为它并没有根据反应极限机制的数量关系定义具体的场数量模型因此没有 测试其有效性。并且曲面变化的算法过于复杂，缺乏现实性。 2 3 建立计算场模型的一般方法 计算机学家已总结了用计算场建模的标准步骤： 1 ) 定义简单场，继而组合成协调场； 2 ) 建立运动微分方程 3 ： 我们考虑个体f ，若它在一个空间( 1 ( f ) ，t ( f ) ，z ( f ) ) 中活动，它所受的协调 场为c 0 0 以( x ，x ：，x 。，f ) ，那么f 个体的微分方程为： 堕：蜘塑堕嘎磐：型，：l 怎棚式( 2 8 ) d t 一獬 。” 方程左边是个体f 在_ 方向上的速度，右边的“v ”可控制协调场作用对个体f 在 _ 方向上的速度的影响大小，可由自己设置。“v ”后面部分是协调场在_ 方向 上的作用。“y ”煎的符号“”设置原则是：若顺着协调场的上升( 上坡) ，可 以完成协调任务，则设为“+ ”；若顺着协调场的下降( 下坡) ，可以完成协调任 务，则设为“一”。式( 2 8 ) 就是将计算场与个体运动联系起来的关键处，利 用这个方程，人们才能模拟出运动过程和轨迹。进而证明模型的有效性。 3 ) 建立整个系统行为方程： 4 ) 在数学分析软件中编写程序整理出系统变化过程测试空间、场定义的合理 性。 第3 章求解问题 3 1 研究基础及动机 3 1 1 基础 从第2 章我们可以看出，只要根据蚂蚁劳动分工策略中某种主导因素的变化 方程及其它们之间的数量关系，定义具体的协调场。并利用标准运动方程，在数 学分析软件中模拟出个体变化轨迹。一旦这种轨迹符合我们的设想，就证明我们 可以利用“场”来指导系统的资源调度。 3 1 2 动机 本文认为，应尽量简化空间定义和场定义，这样才利于算法的简便。前人所 构想的计算场模型虽然比较接近真实的蚂蚁劳动分工策略，但曲面过于复杂，反 而不利于控制算法的简化。因为一个方法是否有效并不是看它是否和某个事物多 么相似，而是要看它到底在我们的生产、生活中有多大用处。 3 1 3 本文所做工作 本文将根据计算场建模的标准步骤，建立新的虚拟空间，定义新的简单场、 协调场，并且进一步建立具体的场表达式、个体运动方程，继而建立整个系统变 化模型，最后在m a t h e m a t i c a 中对运动过程进行模拟和测试。 3 2 建模过程 3 2 1 建立虚拟空间 本文定义空间的名字为任务空间。空间的维数由任务数决定。每根数轴的正 方向代表一个任务的进度方向，因此口q 做任务轴。本文所定义的进度与前人构想 的计算场模型中的执行任务时间百分比不同。每个任务都有一定的任务完成 量，它是执行速度对总时间的积分。而某个时刻的任务进度则是执行速度对一段 时间的积分。不同的任务，可能具有不同的任务量。由于个体执行速度也可能不 同，所以任务进度也可能不同。此外，由于固定反应极限模型与变化反应极限模 型之间有一个变量而是有概念上的差别的，所以区别对待。由于固定反应极限 模型中的矗是表示个体种类i 中，执行任务j 的个体百分数，因此毛的变化，影 响的是个体种类i 执行任务，的总速度，因此任务轴代表的是个体种类f 执行任务 的总进度。而在变化反应极限模型中的置；是表示个体i 在单位时间内分配给任务 ，的时间百分比，因此它的变化，影响的是单个个体f 执行任务，的速度，从而 任务轴代表的是单个个体f 执行任务的进度。 在这样一个任务空间中，本文定义个体只作平行于各个任务轴的运动( 为了 简化场的定义，不计算任务之间的转换时间) ：平行于某轴方向的运动，表示执 行该任务。因此要进行任务转换时，个体直接从该点转向平行于另一任务方向运 动。 3 2 2 定义简单场、协调场 所谓场就是随着某任务的进度变化，而发生形态变化的曲面。这种形态变化 取决于斜率的变化。所谓斜率就是我们要用来引导系统运行的主导因素了。因为 计算场的思想实际上是要利用不同空间位置之间的场势差别，来对个体的运动进 行控制。相等距离之间的场势差别越大，运动速度会越大( 可参考物理学中的场 概念) 。从前人所总结的概率型数量关系模型，可以看出影响个体执行任务速度 的直接因素有两个：任务刺激强度和个体对该任务的反应极限。并且，任务肃j 激 越大，要求个体执行速度越大；而反应极限越大。个体执行速度越小。所以本文 定义两种简单场：任务场和反应极限场。两种场曲面的起始场值都为0 。任务场 的斜率为负，即随着该任务的完成，个体所在位置的任务场值( 小于等于o ) 越 来越小( 下坡) ；反应极限场的斜率为正，即随着该任务的完成，个体所在位置 的反应极限场值( 大于等于0 ) 越来越大( 上坡) 。这两场线性组合成协调场以 后，直接控制个体执行任务速度，这个直接控制通过计算场的般运动方程来实 现。 3 2 3 列出运动方程 在本文所定义的空间中，个体朝着各任务完成进度方向运动。根据定义的简单 场的曲面变化特点，随着任务的完成，个体所在位置的任务场值越来越小，反应 极限场值越来越大，但总的协调场值是越来越小的。因此可以确立运动方程右边 “y ”前的符号是“一”。我们考虑个体，在任务空间( ( f ) ，“( ，) ) 中活动( 双 任务) ，它所受的协调场作用为c d d 脚( ，咒，f ) ，那么个体女的运动微分方程为： 冬：下bcoord(x,yt,t) ( 3 出 积。 、。 d y 一，l ：一v b c o o r - = d ( x , , 一y 女, t ) ( 3 - 2 )出 a k 更具体化： ! 翌：一。+ 曼! 鱼! 塑! 蔓：墨：堕鱼竺堕! 互：兰：坐 出 a k ：一。i ! 鱼竺型兰! 生丝! 生( 圣：坐 a e 1 6 ：一v 3 c o o r d l ( y k , t ) a 匕 ：一。+ 型! ! 蔓：盟! 坐! ! 圣：盟 a 砭 ! 虹：一。+ i 垡望塑! 墨! 蔓：尘鱼翌堕! 茎：蔓! ! 1 2 m d x k ：一vc)(coordl(yk,t)+coord2(xk,t) a x 2 ：一v $ b c o o r d 2 ( x k , t ) a x ：一v十a(s2(xk,t)+oak2(xk,t)。 淑。 ( 3 - 3 ) ( 3 4 ) 从以上的方程可以看出，协调场的斜率直接控制任务的完成速度。其中，v 表 示协调场对完成任务速度的控制作用的大小。 3 2 4 建立系统行为模型 根据基于反应极限机制的蚂蚁劳动分工策略思想、前人所总结的概率型数量 模型和计算场思想，本文所建系统行为模型如下： 设系统有m 个任务，分别标识为j ( j = 1 ，2 ，m ) ，n 个个体，分别标识为k ( k = l ，2 ，h ) ，任务，的刺激强度标为s ，个体k 对任务j 的反应极限标为， 任务场，标为c o o r d s ，k 对任务，的反应极限场标为c o o r a e v ，为k 个体在 单位时间内分配给，任务的时间百分比，a ，y 目= 口t f * ，是七个体执行j 任务 的速度，则系统行为模型为： 1 ) 固定反应极限场模型： c o o r d s q = l s i 由日+ c q c o 。m = 1 8 q 由q + d q ( 3 5 ) ( 3 - 6 ) a ，。= 一v $ ! ! ! ! ! ：! ! 铲( 3 7 ) 即，一伊詈喜】 ( 3 - 8 ) 2 ) 变化反应极限场模型： c o d 吨= 卜，d y “+ ( 3 9 c o 。趔= j o 目a y , j + o , i ( 3 1 0 ) 矾y e = - v * 塑掣( 3 - 1 1 ) a t s j = 1 j 一詈喜】( 3 - 1 2 ) a ，毛= ( t 一) _ q , - x d ( 3 一1 3 ) 下面本文列出单任务和双任务的模型。列出本文所建计算场模型的同时，还 列出了前人所建的概率型数量模型。可以让大家更清楚它们之间的差别。其中， 原模型及其计算场模型的一些式子比前人模型稍有简化：岛的变化方程去掉了 控制范围的函数，本文在实验中注意了这个方面的控制；原模型中的嘞的变化 方程去掉了随机函数，为了大家能够对模型有本质性的认识，本文认为没有必要 增加模型复杂性。 3 2 4 1 固定反应极限模型 3 2 4 。1 1 单任务 1 ) 原模型： ( 加i 虿 2 ( 3 一1 4 ) 吃( 加孟虿 2 毛o ) ( 卜小肚( 3 - 1 5 ) a ，x 2 = ( j ) ( 1 一x o 一鹏 b , s = 万一a f x , 一a ( 1 一f ) x 2 ( 3 1 6 ) 2 ) 场模型： 胁t2 j 叻t + c l ( 3 1 7 ) c o o r d s 2 = j 曲2 + c 2 f c d 。剧q 。哆嘲+ d ( 3 1 8 ) c o o r d 0 22j 岛咄+ f a f m ：一v a ( c o o r d s t + c o o r d o t ) 毋1 ( 3 1 9 ) a ，y 2 ：一扩o ( c o o r d s 、2 + c o o r d 0 2 ) a ，s = - 万一口+ ，+ 五一口4 ( 1 一厂) 。而】 ( 3 - 2 0 ) 其中，a ，y l = 盯。f4 五，a ，2 = 口4 ( 1 一，) + 而。 3 2 4 1 2 双任务 1 ) 原模型： 毛- 。t 卜看弃 ”) = 纛 v 班君万 ：屯2 两s 2 - - ( 3 - 2 1 ) a ， - = ( 而) ( 1 一 。) 一p x t 2 登一( 1 1 i ) 一p x 2 ( 3 - 2 2 ) a ，x t 2 = 毛：( 毛) ( 1 一而2 ) 一p x t 2 a ，勘= ：( 岛) ( 1 一x 2 2 ) 一 ； , s , = 乖8 - o 鸭t f x t t ：- o r ( 1 - f ) x 2 , ：( 3 - 2 3 ) - i t ( 1 - f ) x 2a f s 2 = 占一鸭22 2 ) 场模型： 1 9 c o o r d s = 卜d y 。j i - c i ， c o 口r d s ：。= 卜a y ：十c 2 l c o 。r d s 。2 = 卜2 + e t 。 c o o r d s 。= l s 曩x ：+ e 。 c o 口耐q ，= j o d y + d t c o 口以氏= n 。d y ：+ e c o 。r d o , ：= 一2 d x , + d z c o d 耐岛：= 他2 d x 2 + f z a ，m i ：一v o ( c 。r d _ s t l - + c 。r d s t t ) a ，y 2 i ：一v o ( c o o r d s i 2 1 + c o o r d 0 2 1 ) a ，y 1 2 ：一v o ( c o o r d _ s , 2 - + c o o r d g t 2 ) a ，y 2 2 ：一v 3 ( c o o r d _ s 2 2 - + c o o r d 0 2 z ) r j y 2 2 3 t s l = 一【占一o f 8 f + 五l o f 4 ( 1 一，) 4 x 2 l 】 a ，岛= 一 艿一o f * ，+ 置，一o f * ( 1 一，) 4 而，】 ( 3 2 4 ) ( 3 2 5 ) ( 3 2 6 ) ( 3 2 7 ) 其中， a f m i = 口+ f + i ， a r y 2 l = 口+ ( 1 一，) + 屯i ， a t ) ，1 2 = o f * f * x 1 2 a f y 2 2 = 盯+ ( 1 - f ) + x 2 2 a 3 2 4 2 变化反应极限模型 3 2 4 2 1 单任务 1 ) 原模型： 弘，= 南 强( s 卜珂8 2 a ，= 毛( s ) ( 1 一五) 一p x i a ，而= ( j ) ( 1 一x 2 ) 一p x 2 a j = j a f x , 一o r ( 1 - f ) x 2 2 0 ( 3 - 2 8 ) ( 3 - 2 9 ) ( 3 - 3 0 ) a ，q = ( 1 一五) 妒一玉善】 a ，岛= ( 1 一x 2 ) 妒- x 2 善】 2 ) 场模型： c o o r d s l = i s a y t + c i i c o o r d s 2 = f s a y 2 + c 2 。 c o o r d o l = i 最嘲+ d f c o o r a e 2 = i 岛西l + e a ，y i ：一v o ( c o o r d 弋s , + c o o r d 8 i ) 、 a ，儿：一v + o ( c o o r d s _ 2 + c o o r d 0 2 ) ( 3 - 3 1 ) ( 3 - 3 2 ) ( 3 - 3 3 ) ( 3 - 3 4 ) a ，s = 一 8 - o r + f4 玉一甜+ ( 1 - f ) 4 x 2 ( 3 3 5 ) a ，研= 【( 1 一而) 矿一五掌】 a ，睦= f ( 1 一屯) 妒一恐毋 ( 3 - 3 6 ) 其中，a ，y i = 口4 f4 玉，a 。y 2 = 口+ ( 1 - ，) + x 2 ，分别是个体种类1 和2 完成任务 的速度。 3 2 4 2 2 双任务： 1 ) 原模型： 引2 嚣玎 卜再s i 可2 w 妒才玎 k 5 ：卜再s 2 砑 a ， t = 毛。( s 1 ) ( 1 一x 1 1 ) 一朋i a ，屯t = & ：( 最) ( 1 一屯。) 一p x 2 ， a ， 2 = ：( 屯) ( 1 一x 1 2 ) 一p x t 2 o , x 2 2 = 玩( j 2 ) ( 1 一吒2 ) 一肫2 2 1 ( 3 3 7 ) ( 3 - 3 8 ) a 。j i = 万一a f x , i a ( 1 一f ) x 2 i a ，j 2 = 万一a f x , 2 一a ( 1 一f ) x 2 2 9 , 0 , = 【( 1 - x 1 1 ) ( 尹- - x i i 刳 9 , a 2 l =