（信号与信息处理专业论文）分布式自治智能体优化算法研究.pdf

摘要 本文结合人工生命和多智能体技术，对基于分布式自治智能体的优化算法及其应用 进行了深入研究，取得了如下成果： 1 分布式自治智能体系统建模 对人工生命、进化算法、多智能体理论和自治计算做了深入的研究，通过模拟人类 社会的组织方式，以及人的繁殖、迁移、死亡等行为，构建了一个分布式自治智能体 ( d a a ) 系统框架。在这个框架中对于自治智能体的状态、行为、组织方式、通信等做 了定义，并且给出了此系统的实现步骤。 2 基于分布式自治智能体的函数优化 将建立起来的d a a 系统框架用于连续空间的全局优化问题，提出了一种能够进行复 杂函数优化的分布式自治智能体函数优化算法( d a 0 ) 。通过标准函数的测试结果表明， 此算法能够快速、稳定的找到复杂函数的全局最优点。 3 基于分布式自治智能体的人脸区域检测和分割 将d a a 系统框架用于基于肤色的人脸检测问题，提出了一种基于分布式自治智能体 的彩色图像中人脸区域的检测和分割方法，实验结果表明，该方法突破了传统的逐点搜 索机制，大大提高了人脸候选肤色区域搜索标记的鲁棒性和效率，减少了后续处理工作。 关键词：优化算法，自治计算，分布式自治智能体，函数优化，人脸检测 s t u d yo nt h ed i s t r i b u t e da u t o n o m o u sa g e n t o p t i m i z a t i o n d uj u a n j u a n ( s i g n a la n di n f o r m a t i o np r o c e s s i n g ) d i r e c t e db yp r o f e s s o rw a n g y a n - j i a n g a b s t r a c t i nt h i st h e s i s ，t h ed i s t r i b u t e da u t o n o m o u s a g e n to p t i m i z a t i o na l g o r i t h ma n di t s a p p l i c a t i o na r es t u d i e dd e e p l yb a s e do na r t i f i c i a ll i f ea n dm u l t i a g e n tt h e o r y t h em a i nw o r k s a l ea sf o l l o w s ： 1 m o d e l i n go fd i s t r i b u t e da u t o n o m o u sa g e n ts y s t e m b a s e do nt h es t u d yo fa r t i f i c i a ll i f e ，e v o l u t i o n a r ya l g o r i t h m ，m u l t i a g e n tt h e o r ya n d a u t o n o m yo r i e n t e dc o m p u t i n g ，i nt h i st h e s i s ，w eb u i l dad i s t r i b u t e da u t o n o m o u sa g e n t ( d a a ) s y s t e mf r a m e w o r kb ys i m u l a t i n gt h eo r g a n i z a t i o no fh u m a ns o c i e t ya n dt h er e p r o d u c i n g ， m o v i n ga n dd y i n gb e h a v i o r so fm a n k i n d i nt h ed a af r a m e w o r k ，t h ea t t r i b u t e sa n db e h a v i o r s o ft h ea u t o n o m o u sa g e n t ，a n dt h eo r g a n i z a t i o ns t r u c t u r ea n dc o m m u n i c a t i o nm e c h a n i s m a m o n gt h ea u t o n o m o u sa g e n t sh a v eb e e nd e f i n e d ，a n dt h ei m p l e m e n t a t i o ns t e p so ft h e p r o p o s e dd a a sa r ea l s og i v e n 2 f u n c t i o no p t i m i z a t i o nb a s e do nd a a b a s e do nt h ep r o p o s e dd a af r a m e w o r k , w ep r o p o s ean e wd i s t r i b u t e da u t o n o m o u s m u l t i a g e n to p t i m i z a t i o na l g o r i t h m ( d a o ) a n da p p l yi tt os o l v et h eo p t i m i z a t i o np r o b l e mo f c o m p l e xf u n c t i o ni nt h ec o n t i n u o u ss p a c e t e s t i n gr e s u l t sb ys t a n d a r df u n c t i o ns h o wt h a tt h e p r o p o s e dd a oa l g o r i t h mc a nf i n dt h eo p t i m a ls o l u t i o nq m c m ya n ds t e a d i l y 3 f a c ed e t e c t i o na n ds e g m e n t a t i o nb a s e do nd a a i nt h i st h e s i s ，w ea l s os t u d yt h es k i n - b a s e df a c ed e t e c t i o nb yt h e p r o p o s e dd a a f r a m e w o r k ，a n dp r o p o s ean e wm e t h o dt od e t e c ta n ds e g m e mh u m a nf a c ei nc o l o ri m a g e e x p e r i m e n t a lr e s u l t s s h o wt h a tt h e p r o p o s e dd a a b a s e dm e t h o di ss u p e r i o rt ot h e c o n v e n t i o n a lm e t h o dw h i c hs c a n st h ew h o l ei m a g ep i x e lb yp i x e li nt h ea s p e c t so fr o b u s t n e s s a n de f f i c i e n c y k e yw o r d s ：o p t i m i z a t i o na l g o r i t h m ，a u t o n o m yo r i e n t e dc o m p u t i n g ，d i s t r i b u t e d a u t o n o m o u sm u l t i a g e n t ，f u n c t i o no p t i m i z a t i o n ，f a c ed e t e c t i o n 1 1 关于学位论文的独创性声明 本人郑重声明：所呈交的论文是本人在指导教师指导下独立进行研究工作所取得的 成果，论文中有关资料和数据是实事求是的。尽我所知，除文中已经加以标注和致谢外， 本论文不包含其他人已经发表或撰写的研究成果，也不包含本人或他人为获得中国石油 大学( 华东) 或其它教育机构的学位或学历证书而使用过的材料。与我一同工作的同志 对研究所做的任何贡献均己在论文中作出了明确的说明。 若有不实之处，本人愿意承担相关法律责任。 学位论文作者签名：扭一生鱼竭一 日期：_ 年岁月彩日 学位论文使用授权书 本人完全同意中国石油大学( 华东) 有权使用本学位论文( 包括但不限于其印 刷版和电子版) ，使用方式包括但不限于：保留学位论文，按规定向国家有关部门( 机 构) 送交学位论文，以学术交流为目的赠送和交换学位论文，允许学位论文被查阅、 借阅和复印，将学位论文的全部或部分内容编入有关数据库进行检索，采用影印、 缩印或其他复制手段保存学位论文。 保密学位论文在解密后的使用授权同上。 日期：砷年3 - 月e 1 日期：砷年岁月形日 中国石油大学( 华东) 硕士学位论文 第1 章前言 优化是一种以数学为基础，用于求解各种工程问题优化解的应用技术。作为一个重 要的科学分支，最优化一直受到人们的广泛重视，它对多个学科产生了重大影响，并在 诸多工程领域得到迅速推广和应用，己成为不同领域中很多工作都不可或缺的工具【1 1 。 优化算法是一种搜索过程或规则，它基于某种思想和机制，通过一定的途径或规则来得 到满足用户问题要求的解。 随着现代科技和生产的发展，生产形式己从大批量转向中小批量、多品种生产，相 应的各类先进生产系统均具有变量多、约束多、目标多的特点，这类复杂工程系统的规 划是一个多目标、多层次，多约束的复杂全局优化问题，传统的优化算法对此无能为力， 有效地求解全局最优至今仍是一个难题 2 1 。 尽管遗传算法以及最近发展起来的的仿生优化算法较传统的方法有巨大的优越性， 但是这些算法模型只是生物进化的一些简单模型，在优化任务中都存在这样那样的问 题，迫切需要建立更加逼近真实生物进化的模型，本文将从多智能体系统和进化计算相 结合的角度出发，来研究这一问题。 1 1 论文研究背景及意义 最优化技术在工程应用、航空、航天等众多领域都有重要的应用价值。基于优化问 题的普遍存在性及重要性，优化算法的发展几乎是和数学的发展同步进行的，国内外数 学家们一直在探索解决优化问题的数学方法。目前，已有许多基于迭代原理的数值算法 来求解函数优化问题，如拟牛顿法【3 1 、单纯形澍4 1 、共轭梯度法等【5 1 6 1 ，但这些方法一般 对目标函数约束比较强，如连续、可微、单峰等，方法对问题的依赖性较强，算法结果 与初始值的选择有关，而且容易陷入局部极小值，这些缺点使它们很难得到广泛的使用。 自从2 0 世纪4 0 年代以来，人们一直在利用来自于生物系统的灵感来解决许多实际 问题，并构造和设计出许多仿生优化算法o 】，人工神经网络【1 1 1 和遗传算法【1 卅应运而生。 1 9 8 7 年9 月2 1 日，美国罗莎拉莫斯( l o s a l a m o s ) 的人工生命研讨会中人工生命作为 - 1 7 新的研究科学诞生了，g c l a n g t o n 是人工生命这一概念的创始人。十多年来人工 生命引起了人们越来越多的关注，进行了大量的相关研究，涌现出许多新的仿生优化算 法，如人工免疫算法【2 9 1 、蚁群算法【3 1 1 、人工鱼群算法【3 2 】、微粒群算法【3 3 1 等，它们都是 模拟自然界生物系统，完全依赖生物体自身的本能，通过无意识的寻优行为来优化其生 存状态以适应环境的一类新型的最优化方法。 第1 章前言 进化算法属于一种随机搜索算法，它在初始解生成以及选择、交叉与变异等遗传操 作过程中，均采用了随机处理方法。其全局最优性、可并行性、高效性在函数优化中得 到了广泛的应用。 尽管进化算法较传统的方法有巨大的优越性，但是现有的进化算法仍然存在着一些 共同的不足【3 4 】： ( 1 ) 适应度函数是预先定义好的，而真正的适应性应该是局部的，是个体与环境 做生存斗争自然形成的。现有的进化算法的选择机制，从适应环境的局部化角度而言， 充其量来说，只是一个人工选择，而非自然选择。 ( 2 ) 遗传算法等进化算法只考虑到生物之间的竞争，而没有考虑到生物之间协作 的可能性。真实情况是竞争与协作并存，这就是所谓的协同进化。生物学证据表明协同 进化能大大加快生物进化的历程，这一点在现有的进化算法中很少得到体现。 ( 3 ) 生物进化过程是一个在环境生态系统中“学习 法则的过程，其中不仅包括 先天的遗传学习或遗传复制，而且还包括后天的个体学习。但是以“生成+ 检测”的进 化算法显然没有利用父代的进化经验，而且忽视了个体的学习能力。研究结果表明，利 用l a m a r k 遗传和b a l d w i n 效应能够提高进化算法的搜索效率。 随着科技的发展和工程问题的拓宽，问题的规模和复杂度越来越大，传统算法的优 化结果不够理想和单一算法性能改进的局限，以及新的优化算法的提出的困难，结合指 导性搜索算法和启发式算法的各自优点来构造新算法应运而生。其出发点就是使各种单 一算法相互取长补短，提高优化性能和效率。近年来，混合优化策略得到了较广泛的应 用，并取得了理想的效果，其设计与分析己成为算法研究的一个热点。 另外，分布式人工智能领域发展起来的多智能体理论也被用于解决优化问题。从智 能体系统的角度出发，把进化计算中的个体作为一个具有局部感知、竞争协作和自学习 能力的智能体，通过智能体与环境以及智能体间的相互作用达到全局优化的目的。这就 是多智能体进化的思想，这类引入了智能体特性的进化算法称为多智能体进化算法 ( m u l t i a g e n te v o l u t i o n a r ya l g o r i t h m ) 。目前很多学者致力于将智能体引入到进化算法中， 建立起更加真实可行的模型，用来解决优化及其他问题，取得了不少成果。 应实际要求，近年来在遗传算法、人工智能、进化计算的发展下，涌现出了一大批 用于解决优化问题的智能算法。虽然取得了丰硕的成果，但是仍有很多问题需要解决， 很多算法需要改进： 1 、加强现有智能算法的基础理论研究，进一步发展新的数学分析和建模工具。对 2 中国石油大学( 华东) 硕士学位论文 智能算法，特别是仿生优化算法的基础理论研究非常重要，包括对解决不同优化问题时 收敛性、收敛速度的估计、避免陷入局部最优值以及鲁棒性分析理论等。 2 、针对各种智能算法的不足之处进行改进，使得算法更加完善，解决现有的早熟 收敛、陷入局部最优、收敛速度慢等等问题。 3 、充分利用数学方法，将其与智能算法相结合，取长补短，更好的解决最优化问 题。 4 、将智能算法中的两种或者数种综合使用来开发混合优化方法，进而发展思想更 先进、功能更强大、解决更复杂系统的智能行为。目前国内外众多学者已经在这方面做 了很多尝试。 5 、从现实生活中提取灵感，建立新的模型，提出全新的、更加符合自然规律、更 加有效的优化算法。这一点比较难，但是也有很多学者在探索。 总之，在上述要求的推动下，如何建立起一个更加贴近现实的模型，用于解决复杂 计算和大规模系统建模问题已经成为近年来研究热点，由此便引出了本论文的研究核心 分布式自治智能体优化技术。 1 2 优化算法发展与研究现状 在工程应用上，连续空间上的全局优化问题是普遍存在的。一般而言解决这类问 题的标准途径是建立一个数学模型，使该模型的目标函数能反映应用问题的需求。从而 把连续空间上的全局优化问题转化成连续空间上的函数优化问题。 函数优化问题可以描述为：m i n f ( x ) ，x 亍( 而，屯，矗) r ” ( 1 - 1 ) 式中x s 。s r 称为搜索空间，f ( x ) 称为目标函数，通常每个自变量t 满足一 定的约束条件：l i x f “，i = 1 , 2 ，r l 用于解决这类优化问题的方法主要有两类：数值方法和智能进化算法。 1 2 1 数值方法 目前，已有许多基于迭代原理的数值算法来求解函数优化问题，如拟牛顿法、单纯 形法、共轭梯度法等，但这些方法一般对目标函数约束比较强，如连续、可微、单峰等， 方法对问题得依赖性较强，算法结果与初始值得选择有关，而且容易陷入局部极小值的 缺点，使它们很难得到广泛的使用。 一、拟牛顿法【3 】【4 】 拟牛顿法是求解无约束最优化问题的一类实用性很好的算法。求解最优值的算法采 3 第l 章前言 用如下迭代格式：坼+ l = + 五d k ，k = 1 , 2 ， 其中一是初始点，搜索方向d k = 一何1 9 。，这里g t = v f ( x 七) ，最由下列迭代产生： 瓦，斗鬻t 甓吲占：b 4 s 4 ) v 4 v ； 缈 0 ，1 ) ，s t = x 女+ l x i ，y i = g 女+ l g i ， 7 七= 3 9 4 r + l s + 3 9 ：s t + 6 ( 以+ 以+ 1 ) ，( 1 2 ) 辨儿+ 7 4 t 杀一磊b k s 4 ， 歹七= y k y 7 。4 0 ) 。 九、混合优化算法 随着科技的发展和工程问题的拓宽，问题的规模和复杂度越来越大，传统算法的优 化结果不够理想和单一算法性能改进的局限，以及新的优化算法的提出的困难，结合指 1 0 中国石油大学( 华东) 硕士学位论文 导性搜索算法和启发式算法的各自优点来构造新算法应运而生。其出发点就是使各种单 一算法相互取长补短，提高优化性能和效率。近年来，混合优化策略得到了较广泛的应 用，并取得了理想的效果，其设计与分析己成为算法研究的一个热点。 另外，分布式人工智能领域发展起来的多智能体理论也被用于解决优化问题。从智 能体系统的角度出发，把进化计算中的个体作为一个具有局部感知、竞争协作和自学习 能力的智能体，通过智能体与环境以及智能体间的相互作用达到全局优化的目的。这就 是多智能体进化的思想，这类引入了智能体特性的进化算法称为多智能体进化算法 ( m u l t i a g e n te v o l u t i o n a r ya l g o r i t h m ) 。本文后面章节将着重介绍一下多智能体理论，以 及近年来应用于优化领域的主要技术。 1 。3 本文主要研究内容及结构安排 作为一个重要的科学分支，最优化一直受到人们的广泛重视，它对多个学科产生了 重大影响，并在诸多工程领域得到迅速推广和应用，己成为不同领域中很多工作都不可 或缺的工具。随着现代科技和生产的发展，工程系统日益复杂，对于优化算法的要求也 越来越高，如何更好的解决多目标、多层次、多约束的复杂系统优化问题一直是最优化 技术面临的挑战。 本文研究的主要目标是分析研究多智能体理论，把多智能体系统和进化计算相结 合，用于解决复杂优化问题。具体地，本文的研究主要体现在以下几个方面： 1 多智能体理论技术概述 多智能体技术是人工智能技术的一次质的飞跃，多智能体系统( m a s ) 是由多个单 智能体组成的集合，该系统可以协调一组智能体的行为( 知识、目标、方法和规划) ， 以协同地完成一个任务或求解问题。本文总结了近年来多智能体理论技术的研究情况， 包括智能体概念的产生和定义，多智能体系统的体系结构、通信、协调与协作、学习及 冲突消解等问题，并对多智能体研究方向做了讨论。 2 分布式自治智能体系统( d a a ) 建模 人在社会中以家庭、民族和国家的形式存在，每个人都会受到家规和国法的限制和 指引，而生活状况的好坏，如工作待遇、居住环境、社会保障等则驱使人们从一个地方 移民至另一个地方。根据人类社会的这种特点，本文在分析研究面向自治的计算( a o c ) 系统的基础上，构建了一个分布式自治智能体( d a a ) 系统框架，这个框架是简单人类 社会的重现，框架中以智能体家庭模拟人类家庭，并引入一系列智能体行为来模拟社会 人的行为，以扩散来模拟人类社会的移民，并且其中引入了自适应步长等参数的自适应 11 第1 章前言 调整，目的是构建更加逼真的智能体模型，用于解决复杂问题。 3 基于分布式自治智能体的函数优化 在工程应用上，连续空间上的全局优化问题是普遍存在的。一般而言，解决这类问 题的标准途径是建立一个数学模型，使该模型的目标函数能反映应用问题的需求。从而 把连续空间上的全局优化问题转化成连续空间上的函数优化问题。本文将已经建立起来 的d a a 系统框架用于函数优化问题，建立起分布式自治智能体优化算法( d a o ) ，并 用标准函数进行检测，实验结果证明此算法的有效性。 4 基于分布式自治智能体的人脸分割 传统的区域分割方法是从图像的左上角开始，对图像中的每一点进行分类，然后对 满足分类特征的点利用区域增长的方法进行区域分割和区域标记。由于图像中往往会存 在许多噪声区域，因此这种方法无法迅速地确定出感兴趣的区域。对于人脸检测，这种 方法不仅耗时而且会增加误检率。本文将d a a 系统框架用于彩色图像中人脸区域的检 测和分割，研究结果表明这种方法较传统的图像分割方法无论在速度还是鲁棒性方面都 有很大提高。 本文的内容是这样安排的： 第1 章主要介绍了本文的研究背景、目的、意义、国内外研究现状以及本文要研 究的主要内容； 第2 章总结了近年来多智能体理论技术的研究情况，并对多智能体研究方向做了 讨论； 第3 章对面向自治的计算进行了学习和研究，在此基础上，提出了分布式自治智 能体( d a a ) 系统框架，并对d a a s 的应用前景做了展望； 第4 章将以建立起来的分布式自治智能体系统框架用于函数优化，实验结果证明 其有效性； 第5 章将已建立起来的分布式自治智能体框架用于彩色图像的人脸区域分割，研 究结果表明这种方法较传统的图像分割方法无论在速度还是鲁棒性方面都有很大提高； 第6 章对全文工作进行了总结，并提出存在的问题及进一步的研究计划。 1 2 中国石油大学( 华东) 硕士学位论文 第2 章多智能体理论技术概述 2 1 引言 迄今为止计算的发展历史中有五个重要的、相联系的发展趋势【3 4 1 。即：普适、互联、 智能、代理、人性化。这些趋势是对软件开发者的重要挑战。对于普适和互联的问题， 尚不清楚什么样的技术可以用来建立具有普适的处理能力的系统。现在的软件开发模型 已经令人失望地证明不适合设计多台处理器的问题，即使台数不多。但涉及到1 0 1 0 台处 理器系统的时候，需要什么样的技术? 代理和智能增加的趋势意味着可以建造更有效地 为人类工作的计算机系统。这隐含着两种能力：一是系统的独立操作能力，不需要人的 干预；二是当要计算机系统与人和其它系统交互时，它能按照代表用户最大利益的方式 工作。所有这些发展趋势导致了一个新的领域的出现，这就是多智能体系统。 2 2 智能体 2 2 1 智能体的概念 智能体( a g e n t ) 概念最早由美 i 约m i n s k y 教授在智力社会( ( - - j r 5 0 】 2 2 中国石油大学( 华东) 硕士学位论文 s u t t o n 定义强化学习为，在没有知道正确方案的外部指导存在的情况下基于尝试 出错循环的学习行为。作为一种常用的计算机技术，强化学习已经应用于涉及智能体反 应行为学的问题中。它在处理有限搜索空间( 比如，自治智能体要学习和执行的有限个 可能的动作) 的问题中很有用。 从强化学习的角度来看，一个智能体通过传感器来感知环境并选择一个执行动作， 同时从环境中得到一个反馈( 回报) ，其目的是通过选择合理的从环境状态到动作策略 的映射而使得未来的折扣回报最大。强化学习可以以不同的计算方式实现，这决定于： ( 1 ) 是否使用一些启发式规则；( 2 ) 是否有问题领域的模型或者动作选择的效用方程； ( 3 ) 学习过程是否总是收敛。例如，q 学习不使用任何领域模型，对某个状态下的每 个动作，q 一学习都试图迭代地推导出一个动作权重函数，即q 函数。目前，研究人员 已经提出许多不同的q 学习算法【5 1 5 2 1 。 现有的智能学习方法，如监督学习、无监督学习和分层学习等机器学习方法在多智 能体系统中都有应用。强化学习结合了监督学习和动态规划两种技术，具有较强的机器 学习能力，对于解决大规模复杂问题具有较大潜力，目前应用较多。 但是应用强化学习有一定的局限性。例如，智能体可能很难识别其所处的状态。即 使智能体知道其当前状态，有时仍难于经历所有的可能状态并在正确的时间得到正确的 奖励信号。此外，在一些任务中，智能体的目标是动态变化的，因而智能体就必须重复 的学习1 3 2 j 。 2 3 5 多智能体冲突消解 多智能体系统中每个智能体具有自治性，在问题求解过程中会按照自身的知识、能 力和目标进行活动。对于一些共享资源常会发生共享冲突和死锁，而智能体之间的目标 有时候也不一致。特别对于多智能体系统来说，我们不可能在设计或实现一个智能体时 就把它构建成与其他潜在的智能体的目标相一致。由于智能体高度的自主性和灵活性， 导致他们对于环境的理解不同，对于全局知识的获取往往不全面。所以对于多智能体系 统而言，动态的冲突管理是必然的要求。 目前，多智能体系统中解决冲突的主要方法是协商【3 4 1 。协商技术包括重构、限制、 调节和仲裁等。协商技术通常基于对策论，假定智能体具有完备的全局知识，根据最大 化效用的原则选择自己应采取的行为，且智能体的效用矩阵是共享的知识。但是智能体 的知识往往是不完备的，其效用不是共享的而是私有的，为了模拟现实世界中的问题， 通常通过建立社会规则来避免冲突的设想。但是社会规则和标准会妨碍多智能体系统的 2 3 第2 章多智能体理论技术概述 灵活性和适应性。如果说智能体个体模拟的是人类智能，那么多智能体系统则是对人类 社会的模拟。人类社会的冲突通过群体共同遵守的社会规则来解决，相应的多智能体系 统的设计中也要包含社会规则的内容。某一时期制订的规则也许会因为系统的动态变化 而失去适应性，同时规则的完善也是个不断发展的过程。 2 4 多智能体系统研究方向 2 4 1 人工智能和人工生命 从目前的研究趋势来看，关于智能体的理论和模型大约有两个大的发展方向：其一 是围绕分布式人工智能展开的各种理论和技术，其二是以人工生命等为理论基础的建模 和模拟【3 4 1 。 分布式人工智能( d i s t r i b u t e da r t i f i c i a li n t e l l i g e n c e ，d a i ) 的研究目标是建立一个由 多个子系统构成的协作系统，各个子系统间协作工作，对特定的问题进行求解，一般分 为分布式问题求解和多智能体系统。分布式问题求解考虑怎样将一个特殊的问题求解工 作在多个合作的、知识共享的模块或节点间划分。多智能体系统主要研究一组自治的智 能体间智能行为的协调。这两个方面都要研究如何对知识、资源、控制等进行划分，不 同之处在于，在分布式问题求解中，常常有一个全局的概念模型、全局的问题和全局成 功的标准，而在多智能体系统中，有多个局部的概念模型、问题和成功标准。分布式问 题求解是一种白顶向下的系统，因为处理系统是为满足在顶部所给定的需求而设计的； 而多智能体系统可以看作是采用由底向上的设计方法设计的系统，因为在原理上，分散 自主的智能体首先被定义，然后研究怎样完成一个或几个实体的任务求解，主体之间可 能是协作关系，也可能存在着竞争甚至是敌对的关系。 人工生命( a r t i f i c i a ll i f e ) 的概念是1 9 8 7 年由美国s r i 的l a n g t o n 教授首先提出来的， 他认为人工生命是具有自然界中生命系统的行为特征的人造系统。这里的行为特征主要 指自组织行为：不是通过全局的整体控制，而是通过大量的非生命分子的相互作用而 形成某种有序的行为；学习行为：指的是从生物进化过程的自适应现象中发现的自学 习及其传播行为。 人工生命基于自然生命，具有以下显著特征： ( 1 ) 人工生命是由单个个体的集团构成，集团中每个个体都只具有简单过程的行 为； ( 2 ) 人工生命系统既不存在全局控制过程；也不存在决定整体行为的规则； ( 3 ) 个体的每个过程都包含与其他个体的交叉，反映了它对局部状态的影响； 9 4 中国石油大学( 华东) 硕士学位论文 ( 4 ) 系统能超越各过程范围产生比较高级的行为，并且有“突现”结构和性质。 人工生命的研究内容很广泛，主要有：生命自组织和自复制发育和变异系统 复杂性进化和适应动力学自治智能体自治系统机器人和人脑。 2 4 2 多智能体系统与进化计算1 5 钙9 i 进化计算【3 4 1 ( e v o l u t i o n a r yc o m p u t a t i o n ，e c ) 是一类模拟生物进化过程与机制来求 解问题的自适应人工智能技术。这类基于进化计算的算法就称为进化算法( e v o l u t i o n a r y a l g o r i t h m ，e a ) ，目前研究的进化算法主要有四种：遗传算法( g a ) 、进化规划( e p ) 、 进化策略( e s ) 和遗传编程( g p ) 。近年来蓬勃发展起来的进化算法已被广泛应用于 优化领域，其全局最优性、可并行性、高效性在函数优化中得到了广泛的应用。进化算 法是一种群体搜索算法，利用群体中的个体在解空问中进行随机搜索。在进化过程中， 群体中的个体通过遗传算子产生新个体，保持群体的多样性，对新的空间进行搜索，以 得到问题的最优解。它克服了传统数值方法的缺点，借助了大自然的进化过程，是多线 索而非单线索的全局优化方法。 目前的搜索方法可以分成三类枚举法、解析法和随机法。枚举法是指枚举出可 行解集合内的所有可行解，以求精确最优解。对于连续函数，需对其进行离散化处理。 但许多实际问题所对应的搜索空间很大，因此该方法的求解非常低。解析法是在求解过 程中主要使用目标函数的性质，如一阶导数、二阶导数等。这一方法又可分为直接法与 间接法。直接法根据目标函数的梯度来确定下一步搜索的方向，从而难于找到整体最优 解，而间接法则从极值的必要条件出发导出一组方程，然后求解方程组。但是导出的方 程组一般是非线性的，它的求解是非常困难的。随机法在搜索过程总对搜索方向引入随 机的变化，使得算法在搜索过程中以较大的概率跳出局部极值点。随机法又可分为盲目 随机法和导向随机法。前者可以在可行解空间中随机地选择不同的点进行检测；后者以 一定的概率改变当前的搜索方向，在其他得方向上进行搜索。 进化算法属于一种随机搜索算法，它在初始解生成以及选择、交叉与变异等遗传操 作过程中，均采用了随机处理方法。与传统的搜索算法相比具有以下的不同点： ( 1 ) 进化算法不直接作用在解空间上，而是利用解空间的某种编码表示； ( 2 ) 进化算法从一个群体即多个点而不是一个点开始搜索，这是它能以较大概率 找到整体最优解的主要原因之一； ( 3 ) 进化算法只使用解得适应性信息( 即目标函数值) ，并在增加收益和减少开 销之间进行权衡，而传统搜索算法一般要使用导数等其他辅助信息； 2 5 第2 章多智能体理论技术概述 ( 4 ) 进化算法使用随机处理方法而不是确定性的转移规则。 应用进化算法求解优化问题的一般步骤为： ( 1 ) 随机给定一组初始解； ( 2 ) 评价当前这组解的性能； ( 3 ) 若当前解满足要求或进化过程达到一定代数，计算结束； ( 4 ) 根据( 2 ) 的评价结果，从当前解中选择一定数量的解作为基因操作对象； ( 5 ) 对所选的解进行基因操作( 如交叉、变异等) 得到一组新解，转到( 2 ) 。 进化算法包含的范围比较广，很多仿生优化算法都可以称为进化算法，只是由于所 模拟的模型不同，算法也有所不同，近几年来，很多学者从进化算法的一般步骤出发， 通过引入不同的策略对进化算法做了很多改进。 尽管进化算法较传统的方法有巨大的优越性，很多学者也在改进进化算法上做了很 大努力，但是现有的进化算法仍然存在着一些共同的不足： ( 1 ) 适应度函数是预先定义好的，而真正的适应性应该是局部的，是个体与环境 做生存斗争自然形成的。现有的进化算法的选择机制，从适应环境的局部化角度而言， 充其量来说，只是一个人工选择，而非自然选择。 ( 2 ) 遗传算法等进化算法只考虑到生物之间的竞争，而没有考虑到生物之间协作 的可能性。真实情况是竞争与协作并存，这就是所谓的协同进化。生物学证据表明协同 进化能大大加快生物进化的历程，这一点在现有的进化算法中很少得到体现。 ( 3 ) 生物进化过程是一个在环境生态系统中“学习”法则的过程，其中不仅包括 先天的遗传学习或遗传复制，而且还包括后天的个体学习。但是以“生成+ 检测 的进 化算法显然没有利用父代的进化经验，而且忽视了个体的学习能力。研究结果表明，利 用l a m a r k 遗传和b a l d w i n 效应能够提高进化算法的搜索效率。 显然已有的进化算法模型只是生物进化的一个简单模型，迫切需要建立更逼近真实 生物进化的模型，多智能体系统的产生和发展便适应了这一要求。 对于现实中的复杂的、大规模的问题，只靠单个智能体往往无法实现描述和解决。 多智能体系统通过多个具备自身的问题求解能力和行为目标的智能体的相互协作来达 到求解复杂的、大规模问题的目的。由于资源有限，构成多智能体系统的智能体的结构 和功能都比较简单，同时其行为也比较简单。当然，智能体只能感知有限的环境，称之 为邻域，但它可以通过扩散过程实现对全局环境的感知。借助多智能体系统中的协调协 作机制以实现进化算法中个体的竞争和协作无疑将加快算法的收敛和增强算法的优化 2 6 中国石油大学( 华东) 硕士学位论文 能力。由于开放分布式多智能体系统的结构和功能都十分复杂，要达到多智能体系统的 适应性，智能体的自学习能力又是不可缺少的。 多智能体系统是分布式人工智能研究的一个重要分支，由于其在解决实际问题中具 有很强的健壮性、可靠性和高效率等特点，已在许多领域得到了成功的应用，多智能体 系统和进化计算都是多学科相融合、具有很高实用价值的研究领域，它们也已在多个领 域得到了广泛的应用，但其结合是一个具有挑战性的研究课题。 从智能体系统的角度出发，把进化计算中的个体作为一个具有局部感知、竞争协作 和自学习能力的智能体，通过智能体与环境以及智能体间的相互作用达到全局优化的目 的。这就是多智能体进化的思想，这类引入了智能体特性的进化算法称为多智能体进化 算法( m u l t i a g e n te v o l u t i o n a r ya l g o r i t h m ) 。 目前很多学者致力于将智能体引入到进化算法中，建立起更加真实可行的模型，用 来解决优化及其他问题，取得了不少成果。 韩靖，蔡庆生【删在文章a e r 模型中的智能涌现中创建的多智能体模型以人工生命 理论为指导，吸取了元胞自动机，s w a r m 的基本思想，如图2 6 ，a e r 模型系统中包含 “智能体( a g e n t ) 、环境( e n v i r o n m e n t ) 、交互规则( i n t e r a c t i v er u l e ) 三个主要概 念，引入了“适者生存”的淘汰机制，建立了一个具有“简单性、局部性、全局性、内 聚力、动态性 的复杂自适应系统：a e r 多自主体模型，利用“突现 的智能求解问题。 a e r 系统是一个自组织的离散系统，a g e n t 可以感知局部环境，不断演化到解状态。文 章用智能体解决了高达7 0 0 0 个皇后的问题，充分显示出智能体的优越性。 图2 - 6a e r 模型 f i 9 2 - 6 a e rm o d e l 钟伟才【6 1 击3 】等基于智能体的感知与反作用能力提出了一种新的函数优化方法 多智能体遗传算法。该方法将智能体固定在网格上，而每个智能体为了增加自身的能量 2 7 第2 章多智能体理论技术概述 将与其邻域展开竞争或合作，同样智能体也可以利用自身的知识进行自学习来增加能 量，理论分析证明该算法具有全局收敛性。在后来的文章中，又将其成功应用于组合优 化问题。 黄永青晔】等将多智能体技术应用于交互式进化计算领域，提出一种新的交互式多智 能体进化算法。该方法让固定在网格上的相邻智能体之间展开竞争和最优智能体本身的 自学习，来提高智能体的能量，从而使得算法获得较强的全局收敛能力和局部搜索能力。 蔡自兴【6 5 】分析了在遗传算法的并行实现问题的研究现状：m a n d e r i c k 、m u h l e n b e i n 等人研究了一种称为细粒度的并行模型，该模型将群体中的个体分布到不同的处理机上 进行并行遗传操作，可能获得最大的并行性。p e t t e y 、c o h o o n 等人研究了粗粒度的孤岛 模型，把一个大群体分割成若干子群体，对每个子群体进行并行遗传操作。在粗粒度的 并行模型中，每一代都需要邻近子群体之间的个体迁移，从而形成新一代子群体，通讯 代价较大在细粒度并行模型中，群体中个体分布在不同的处理机上，交叉操作在邻域上 进行，需要更大的通讯代价现有的遗传算法并行模型均存在通讯代价大、系统效率低以 及硬件环境要求高等不足。这就是遗传算法发展至今，并行化实现研究进展甚微的主要 原因。作者把采用基于a g e n t 的并行遗传算法，把每个个体视作一个a g e n t ，每个子群 体中的优秀a g e n t 可以与其它子群体交互，从而实现通讯代价小而又能确保最终求取最 优解之目标。子群体之间的通讯采用黑板模型。 金福江【删等将多智能体优化算法应用到多目标函数优化上，提出了分布式多目标算 法，首先建立每个目标函数智能体，它在完成各个子目标函数优化的同时，将自己的优 化结果发送给其他智能体。同时，接收其他智能体的优化结果，通过协调算法完成对整 个多目标问题的整体优化。分布式智能多目标算法具有多目标遗传算法的隐含并行和全 局搜索的特性，且具有多目标优化数值算法的高精度、速度快等优点。 2 5 本章小结 本章总结了近年来多智能体理论技术的研究情况，包括智能体概念的产生和定义， 多智能体系统的体系结构、通信、协调与协作、学习及冲突消解等问题，并对多智能体 研究方向做了讨论，为本文后续工作的展开打下基础。 2 8 中国石油大学( 华东) 硕士学位论文 第3 章分布式自治智能体系统建模 3 1 引言 人在社会中以家庭、民族和国家的形式存在，每个人都会受到家规和国法的限制和 指引，而生活状况的好坏，如工作待遇、居住环境、社会保障等则驱使人们从一个地方 移民至另一个地方。在移民过程中，人会收集来自各个方面的信息，近邻、远亲以及媒 体提供的信息。根据消息来源不同，移民大致有两种方式：自发的移民，即没有亲人朋 友的指引，自己根据媒体收集到的信息而进行迁徙；有引导的移民，这种行为一般都是 在那些已经移入的居民帮助下完成。而根据移民激烈程度不同，移民也可以分为局部移 民和远距离移民。社会总在进步，人们的生活状况也总是在变好，如果设定一个生活目 标，那么最终肯定会有人能够到达这个生活水平。 根据人类社会的这种特点，本章在分析研究面向自治的计算( a o c 系统) 的基础 上，构建了一个分布式自治智能体( d a a ) 系统框架，这个框架是简单人类社会的重现， 框架中以智能体家庭模拟人类家庭，并引入一系列智能体行为来模拟社会人的行为，以 扩散来模拟人类社会的移民，并且其中引入了自适应步长等参数的自适应调整，目的是 构建更加逼真的智能体模型，用于解决复杂问题。 3 2 面向自治的计算( a o c ) 多智能体技术是人工智能技术的一次质的飞跃，正如人类群体协作的能力要远远大 于个体能力一样，多智能体系统具有比单个智能体更高的智能性和更强的问题求解能 力。当前智能体领域的研究也大都集中在多智能体系统上，国际上关于多智能体系统的 研究虽然时间很短，但发展相当迅速，国内外很多学者都致力于构造更加真实可靠的智 能体模型，并将分布式技术应用到多智能体系统中，以解决现实复杂问题。 虽然目前存在的基于多智能体的建模方法在一定程度上成功的解决了一些问题，但 是对于生物、社会、经济、数学、物理和自然系统等复杂系统问题，目前尚没有一个系 统的建模方法。 基于以上考虑，香港浸会大学的刘际明博士提出了面向自治的计算( a u t o n o m y o r i e n t e dc o m p u t i n g ，a o c ) 6 7 】【6 8 】来概括对复杂系统的研究，并用之解决复杂的计算问 题和刻画复杂系统行为特征。面向自治的计算是指一切以自治( a u t o n o m y ) 为核心模型 的算法，它是多个个体构成的自下而上的计算算法，其中个体最重要的特征就是自治， 系统中没有中央控制单元，个体仅仅处理局部信息，个体之间以及个体与环境之间的相 笙! 兰坌塑塞鱼塑塑丝堡墨笙垄堡 互作用是系统的推动力。 根据研究目的的不同，面向自治的计算可以分为三个方面【6 8 】： 1 基于构造的面向自治的计算。其目的是在计算中重现类似生命的行为。在这类计 算中，类似生命的行为建立在对系统的机制的充分理解上，其可以用来解决实际工程中 的有目的的问题。因此在这些算法中，系统行为的重现不是目的而是手段。在以往的研 究中，人工生命是基于构造的面向自治的计算的行为复制重现阶段，而由自然启发的算 法进化算法等是建立在对自然界优胜劣汰的进化机制充分理解，并提取其中最重要 的部分来解决问题的典型代表。 2 基于原型的面向自治的计算。其目标是通过假定和重复实验来理解真实世界中的 复杂系统的内在机制。在基于原型的面向自治的计算中，研究者对于系统的运行机制了 解很少，因此智能从观察到的系统基本单位行为出发，通过假设个体行为以及其相互作 用的机制来观察系统的宏观效果，并且进行重复试验来更好的理解和解释所建模系统的 实际工作机制。 3 基于自我发现的面向自治的计算。其目标是在不干涉的情况下的实现问题解决的 创现，即自适应算法。在该算法中，假定和重复实验被自治实现替换，问题和目标之间 差别是计算系统的机制进化的原动力。许多具有自适应的进化算法就属于这个范畴，其 可以根据进化结果和目标的进化算法的不同参数，如变异概率，交叉概率，群体大小甚 至遗传操作等。 3 2 1 概念和定义 定义3 1 (