（计算机应用技术专业论文）协作型协进化算法及其应用.pdf

中文摘要 协进化算法是近年来兴起的一种算法，它的发展时间虽然不长，但已经成功地 应用到一些优化问题中，包括许多n p 问题。它从传统的进化算法发展而来，而又 有自己的特点：在协进化算法中，不同种群间的个体间存在相互合作的关系，而不 是像传统进化算法那样个体间仅存在竞争关系。目前国内外许多的学者已经在协进 化算法方面作了许多的研究工作。 本文首先较全面系统地分析了目前国内外关于协进化算法的研究工作与所取 得的研究成果。其次介绍了协进化算法的核心思想、算法的基本流程；为了克服进 化过程中出现的早熟问题，提出了基于混沌的协作型协进化算法，它利用混沌原理 打破了局部优秀个体的垄断现象，并使进化种群中的个体分布广泛。最后还将协作 型协进化算法应用到实际的问题中，包括生产调度问题及数据聚类问题。在生产调 度的应用中，全面分析了车间调度问题，并提出了一种适合车间调度的协进化算法 编码方式。在数据聚类的应用中，将数据聚类与图形分割联系起来，使问题变得简 单容易解决。 关键词：协作型协进化算法；生产调度；数据聚类 a b s t r a c t c o e v o l u t i o n a r ya l g o r i t h m ( c a ) i so n ea l g o r i t h mw h i c hh a se m e r g e d d u r i n gr e c e n ty e a r s a l t h o u g hi t sd e v e l o p m e n tt i m ew a sn o tl o n g ，t h e a l g o r i t h mh a sb e e ns u c c e s s f u l l yu s e d i ns o m e o p t i m i z a t i o nq u e s t i o n ， i n c l u d i n gm a n yn pq u e s t i o n s i t c o m e sf r o mt h et r a d i t i o n a le v o l u t i o n a l g o r i t h m ，a l s os h o w si t s o w nc h a r a c t e r i s t i c s ：i nc a ，i n d i v i d u a l se x i s t i n g m u t u a l l yc o o p e r a t i o nr e l a t i o n sb e t w e e nd i f f e r e n ts p e c i e sg r o u p s ，i n s t e a do f t h eo n l yc o m p e t i t i o nr e l a t i o n si nt h et r a d i t i o n a le v o l u t i o na l g o r i t h m s a t p r e s e n t ，al o to fw o r ka b o u tc ah a sb e e nd o n eb yt h es c h o l a r sb o t ha b r o a d a n da th o m e i nt h i sp a p e r , f i s t l y , w ea n a l y z e dt h er e s e a r c hw o r k st h a ts c h o l a r sa r e g o i n ga l o n gw i t hi nt h ea s p e c to fc a s e c o n d l y , t h ec o r ea n db a s i cr o u t eo f t h i sa l g o r i t h mw e r ei n t r o d u c e d ；i no r d e rt oo v e r c o m et h ep r e m a t u r e c o n v e r g e n c ep r o b l e mw h i c ha p p e a r si nt h ee v o l u t i o np r o c e s s ，w ep r o p o s e da n e wa l g o r i t h mc a l l e dc o o p e r a t i v ec o e v o l u t i o n a r yg e n e t i ca l g o r i t h mb a s e d o nc h a o s ( c c g a g ) ；i tu s e dt h ec h a o sp r i n c i p l et ob r e a kt h em o n o p o l y p h e n o m e n o no fp a r t i a lo u t s t a n d i n gi n d i v i d u a l ，a n dc a u s e dt h ei n d i v i d u a li n t h ee v o l u t i o n p o p u l a t i o nw i d e l yd i s t r i b u t e d f i n a l l y , w ea p p l i e d t h e c o o p e r a t i v ec o e v o l u t i o n a r yg e n e t i ca l g o r i t h m t op r a c t i c a lp r o b l e m ，e g p r o d u c t i o n s c h e d u l i n gp r o b l e ma n dt h ep r o b l e mo fd a t ac l u s t e r i n g i n i i i p r o d u c t i o ns c h e d u l i n ga p p l i c a t i o n s ，t h ej o bs h o ps c h e d u l i n gp r o b l e mh a s b e e na n a l y z e di nd e t a i l ，a n da ne n c o d i n gm e t h o do fc o e v o l u t i o nt h a tf i t sjo b s h o ps c h e d u l i n gh a sb e e np r o p o s e d i nd a t ac l u s t e r i n ga p p l i c a t i o n s ，t h e p a p e rl i n k e du pd a t ac l u s t e r i n gw i t hg r a p hp a r t i t i o nt ok e e pt h eq u e s t i o na s b r i e fa sp o s s i b l ea n de a s yt os o l v e k e yw o r d s ：c o o p e r a t i v ec o e v o l u t i o n a r yg e n e t i ca l g o r i t h m ；p r o d u c t i o n s c h e d u l i n g ；d a t ac l u s t e r i n g i v 声明尸明 本人郑重声明：所呈交的学位论文，是本人在指导教师的指导下， 独立进行研究所取得的成果。除文中已经注明引用的内容外，本论文 不包含其他个人或集体已经发表或撰写过的科研成果。对本文的研究 做出重要贡献的个人和集体，均已在文中以明确方式标明。本声明的 法律责任由本人承担。 作者签名： 弦面日期：2 辞盘1 4 生鳕 关于学位论文使用权的说明 本人完全了解太原科技大学有关保管、使用学位论文的规定，其 中包括：学校有权保管、并向有关部门送交学位论文的原件、复印 件与电子版；学校可以采用影印、缩印或其它复制手段复制并保存 学位论文；学校可允许学位论文被查阅或借阅；学校可以学术交 流为目的，复制赠送和交换学位论文；学校可以公布学位论文的全 部或部分内容( 保密学位论文在解密后遵守此规定) 。 作者签名： 立函 日期： 21 幽生亟一 导师签名：妻鍪圣叁眺2 幽m 第一章绪论 第一章绪论 1 1 协进化算法的研究发展与现状 人们利用进化算法可以解决一些使用传统的搜索方法难以解决的复杂问题，但 是同时也发现，对于某些复杂问题进化算法并不能有效地解决，如难以编码的复杂 问题、大型复杂结构( 如神经网络) 的生成问题等。此外，进化算法还存在一些难 以解决的问题：传统进化算法中的物种群体具有很强的收敛性，使算法到最后只 保留了最“强壮的个体，并没有利用个体的多样性和个体之间的共生性，这样使 该算法对于那些需要给出除峰值以外更多信息的问题就无能为力了；传统进化算 法中的每个个体都代表了求解问题的完整解决方案，并且个体之间是彼此孤立的并 没有交互，这样十分不利于成员之间产生共同适应和协调行为。 协进化算法( c o e v o l u t i o n a r ya l g o r i t h m ) 的出现，向人们提供了一种解决问 题的新方法。生物学领域中的进一步研究表明，生物界中还存在多个个体或是多个 物种为了进化而彼此之间相互合作的规律( 如寄主与宿主之间的共生关系) 。协进化 算法正是源于这种思想。这种算法包含多个子群体，这些子群体之间相互合作、共 同进化。 早在1 9 7 8 年，h o l l a n d 在他的论文【l 】中就初步提出了子群体的概念。他在规则学 习的分类系统中使用了包含有子群体的进化算法，其中子群体中个体的适应度是由 与其相互作用的其他规则共同决定的，此处已经体现了协进化的思想。在9 0 年代初， h u s b a n d s 提出了子群体间的相互合作与竞争的概念【2 j 。同一时期，在h i l l i s 的论文 中，宿主与寄主协进化的计算模型被提出【3 】。以上仅仅是零散地体现了一些协进化的 思想。 9 0 年代，是协进化算法发展的兴盛时期。1 9 9 4 年，p o t t e r 和d ej o n g 提出了遗 传协进化算法( c c g a ：c o o p e r a t i v ec o e v o l u t i o n a r yg e n e t i ca l g o r i t h m s ) ，并将 该算法应用于函数优化问题中，通过实验对算法的性能加以检验，他们还指出其他 进化算法( 如进化规划、进化策略) 也同样适用于协进化思想。之后的一年里，p o t t e r 和d ej o n g 发表了不少关于协进化算法的论文【4 ，5 ，6 ，7 1 ，在这些论文中，他们用协进化 算法解决了不少复杂问题，如神经网络的生成问题等。1 9 9 7 年p o t t e r 在他的博士毕 业论文【8 】中对协进化算法模型加以详细描述，对算法的性能加以分析，特别从子群体 间的相互独立性、问题的维数、模型处理适应度评价函数的能力等方面进行了详细 分析；文中指出子群体具有适应动态环境的能力，它的功能可随环境的改变而变化； 1 协作型协进化算法及其应用 同时，p o t t e r 还针对神经网络的生成问题用协进化算法与非协进化算法进行了比较 实验，结果验证了协进化算法的优良性能。 q i a n g f uz h a o 等提出了一种协进化的社会模型【9 1 ，而该模型可以与大多数的协进 化算法相匹配；同时在解决模式识别的生成问题时使用了协进化算法，并着重讨论 了在该算法中如何评价子群体，通过实验对不同的评价方法加以分析和比较；另外 还将协进化算法应用到了神经网络的进化学习中。 其它一些相关的研究有：s e v a ng f i c i c i 提出了一种协进化的对策论方法【l o 】； r i c h a r da w a t s o n 在问题的分解、个体组合方法以及协进化的多种模型等多个方面 进行了研究与探讨f 1 1 j ；m a r i ag o r d i n 等人将协进化算法应用到多智能体系统中两个 智能体之间的合作问题中，并分析了在计算个体适应度值时，使用不同的组合机制 对算法性能的影响【1 2 】。 以上都是国外的研究情况，国内对协进化算法的研究起步较晚。1 9 9 8 年，周远 晖等在克服遗传算法的早熟收敛问题时，提出了多个群体并行进化与控制参数自适 应调整相结合的方法【1 3 】，体现了协进化的思想，但这种多群体进化方法中的子群体 之间的相互合作不显著。 1 9 9 9 年，曹先彬等提出了遗传强化学习的生态竞争模型【1 4 】，在该模型中竞争占 有十分重要的地位，子群体内的个体具有先天遗传进化和后天竞争学习的能力，同 时在子种群层次上实现了进一步的竞争强化学习，实验结果显示该模型在解决收敛 问题时具有很好的效果。 2 0 0 0 年，郑浩然等提出了基于共生策略的多模式进化算法 1 5 】，该算法主要应用 的思想是生物在面对生存压力时可采用不同策略协同进化，其反映了生物在生态环 境中进化的多样性，他还将该算法应用到系统跟踪问题中。 谢涛等通过理论分析证明，协进化遗传算法的求解效率比传统单种群遗传算法要 高，且协进化遗传算法中子种群数目越多，该算法的求解效率越高【1 7 】。 1 2 协进化算法的特点 虽然协进化算法被提出的时间并不长，但它的出现使进化算法的研究向前迈进 了一大步，与其相关的理论与应用研究非常之多。协进化算法除了具有简单、鲁棒 性强以及适合并行处理等这些一般进化算法所具有的特点外，还具有他自己的一些 特性。 适合于复杂问题的求解。协进化算法主要依据的是“分而治之”的思想：先 2 第一章绪论 将问题分为几个子问题，对几个子问题分别求解，再利用子问题的解计算出整个问 题的解。对绝大部分复杂问题来说，如果用传统的进化算法求解，需要对整个问题 进行编码、遗传操作、适应度函数等复杂的设计；而使用协进化算法可以将问题分 解，将一个高度复杂的问题转化几个复杂度较低的子问题，分解后只需要对复杂度 较低的子问题进行编码、遗传操作以及适用度函数等的设计，大大降低了问题的难 度。 可以用于不同的进化算法。传统进化算法( 包括遗传算法、遗传编码、进化 规划以及进化策略) 都有相应的协进化算法。并且还可以将两种或多种进化算法结 合起来应用到协进化算法中来解决问题。 有很广泛的应用范围。目前，在背包问题、神经网络的生成问题、分类系统、 字符串覆盖问题等领域都可使用协进化算法。在本文中，我们将介绍协进化算法在 生产调度与数据聚类中的应用。 1 3 生产调度的研究发展与现状 生产调度是制造系统的一个研究热点，也是理论研究中最为困难的问题之一。 调度的任务是根据生产目标和约束，为每个加工对象确定具体的加工路径、时间、 机器和操作等，其实调度就是对共同使用的资源进行时间上的分配从而达到某一目 的。优良的调度策略对于提高生产系统的最优性、提高经济效益，有着极大的作用。 调度问题的研究始于2 0 世纪5 0 年代。在1 9 5 4 年，j o h n s o n 针对两台机床的f l o w s h o p 型调度问题进行了研究，标志着调度问题广泛研究的开始。调度理论的主体在 6 0 7 0 年代建立，在这段时间内人们重视调度复杂性的研究。到7 0 年代后期，随着 调度理论的研究及发展，出现了许多新的调度理论与方法。 由于调度问题的复杂性，研究者从不同的角度进行研究，产生了许多解决调度 问题的类型和方法。最初使用整数规划、简单规则等方法解决生产调度问题，但这 些方法难以解决复杂问题或生成的调度结果不理想【1 8 】。后来，出现了许多新的方法， 如神经网络法、模拟退火法、遗传算法等，使得生产调度问题的研究方法走向了多 元化。 1 4 本文的主要工作 本文首先分析了协进化算法，并对它的一个重要分支协作型协进化算法进行 了改进；然后将协作型协进化算法应用到生产调度与数据聚类问题领域中。各章内 3 协作型协进化算法及其应用 容提要如下： 第二章对协进化算法进行了较为系统的论述，详细地介绍了协进化算的主要思 想、形式化描述以及流程，并介绍了多群体协进化的数学模型。 第三章为了克服协作型协进化算法中出现的早熟收敛问题，在协作型协进化算 法中引用混沌理论对其进行改进，通过仿真实验验证了改进算法的有效性。 第四章介绍了协进化算法在车间调度中的应用。详细分析了车间调度的流程、 研究方法与策略，并对协进化算法在车间调度中的应用进行了仿真实验。 第五章介绍了协进化算法在数据聚类中的应用。将数据聚类与图形分割联系起 来，并介绍了一种适合该问题的协进化算法编码方法。 第六章总结与展望。回顾了本文完成的主要工作，展望了协进化算法的发展前 景。 4 第二章协进化算法 第二章协进化算法 2 1 协进化算法的基本思想 1 8 9 5 年达尔文创立的进化论，曾经作为生物界以及人类文明史上的一个里程碑， 促进了科学技术的发展。2 0 世纪6 0 年代以来，进化论又被推广应用于工程技术，形 成一种新型的计算方法进化算法( e v o l u t i o n a r ya l g o r i t h m s ) ，又称为进化计算 ( e v o l m i o n a r yc o m p u t a t i o n ) 。 进化算法仿效生物学中进化和遗传的过程，遵从“优胜劣汰”的原则，从一组随 机生成的初始可行群体出发，借助选择( 复制) 、交叉( 重组) 、变异等遗传操作， 逐步逼近所研究问题的最优解。从实质而言，进化算法是一种具有自适应调节能力 的搜索寻优技术。 通常，进化算法包括遗传算法( g e n e t i ca l g o r i t h m s ) 、遗传规划( g e n e t i c p r o g r a m m i n g ) 、进化策略( e v o l u t i o ns t r a t e g i e s ) 、进化规划( e v o l u t i o n a r yp r o g r a m m i n g ) 4 种典型方法。它们在进化原则上是一致的，只是在实施进化的手段上却各有特点互 不相同。 目前，进化算法已经成为继人工智能专家系统、人工神经网络之后的又一个受人 青睐的新学科。在美国、德国、法国等发达国家，它已被成功地用于机械、化工、 建筑、计算机等领域，着重用于解决结构性优化、非线性优化、并行计算等复杂问 题。近年来，进化算法在我国也得到重视和推广，特别是遗传算法，已被成功地应 用于许多领域。 虽然在很多领域使用进化算法取得了很好的效果，但是对一些复杂度很高的问 题，进化算法的效果并不是很理想。 那么能不能对传统的进化算法进行改进呢? 回归到进化算法的起源：自然界， 在自然界中，多种物种共存于一个生态系统中，在这个生态环境中，每种生物在不 断地进化着，同时其自身的改变也影响其他生物的改变，他们之间相互影响，彼此 制约。物种们之间的这种自身在不断变化的同时又影响其他物种进化的现象被称为 协进化。将自然界中的这种协进化思想应用到进化算法中，人们提出了协进化算法， 该算法从传统的进化算法发展而来，是达尔文进化论思想在问题领域中的进一步映 射。在协进化算法中，存在多个物种群体( 被称为子种群) ，每个子种群在自己的进 化过程中都有自己的进化算法，只是每个子种群中的个体不是孤立的，必须通过种 群问的协调来评价自身的适应度。通过对个体适应度的评价，子种群之间产生协调 5 协作型协进化算法及其应嘎 行为，这是协进化算法的关键。 协作与竞争是自然界中物种间最基本的协作方式，据此，可以把协进化算法总 体上分为两类：协作型协进化( c o o p e r a t i v ec o - e v o l u t i o n ) 和竞争型协进化 ( c o m p e t i t i v ec o e v o l u t i o n ) 。但物种间的关系很复杂，两个物种间的关系并不是 单一的协作或竞争，我们可以对协进化进一步细化分类，如图2 1 所示。 图2 - i 根据物种之间的关系对协进化算法进一步分类 f i g u r e2 - 1t h ef u r t h e rc l a s s i f i c a t i o no fc o e v o l u t i o na l g o r i t h m ，a c c o r d i n gt ot h er e l a t i o n s h i pb e t w e e n s p e c i e s 虽然物种间的关系很复杂，但不论是协作型协进化还是竞争型协进化，在评价 物种群体中个体的适应度时，都要考虑其他物种群体的情况。其他种群对个体的影 响可以是正面的( 协作) ，也可以是负面的( 竞争) ，或是更为复杂的影响。事实上， 在整个协进化的过程中，物种间的关系并不是单一的竞争或合作，很有可能是多种 关系组合在一起。但不论协进化算法的类型是协作还是竞争，协进化算法都围绕着 一个核心思想：种群中的个体适应度都与其他种群有关，其他种群对该种群的影响 即可能是正面的也可能是负面的，还有可能是多中情况的结合。协进化算法就是通 过种群间的这种影响来相互协调的完成进化过程。当然，种群间的协调方式以及种 群自身的情况等这些因素都影响着协进化的最终结果，最后可能是多个物种彼此协 调发展，也可能因竞争过于激烈而出现物种灭绝的情况。 协作型协进化算法( c o o p e r a t i v ec o e v o l u t i o n a r yg e n e t i ca l g o r i t h m ，c c g a ) 是协进化算法的一个重要分支，也是近年来被研究的比较多的一种算法。协作型协 进化算法仿照生物种群间的合作特征：首先对目标问题进行划分，分成几个互相关 6 第二章协进化算法 联的子问题，每个子问题对应于生态系统中的一个物种；每个物种群体在进化过程 中与其他物种群体发生信息交互，使各个物种群体的进化达到互相指导的目的，从 而使整个生态系统即完整的目标问题得到求解。 2 2 协进化算法的形式化描述 协进化算法的主要因素包括：各个物种群体、每个物种的进化算法以及物种之 间的合作的方式等。协进化算法c a t 2 0 1 可以形式化描述如下( 每个物种群体都采用标 准遗传算法) ： c a = ( c o u n t ，c ，s g a ，s ( o ) ，s ( k ) ，t ) 其中： c o u n t ：表示协进化算法中物种的种群个数； c = c 。，c ：c c 0 肿) ，c ，表示第i ( i = 1 ，2 c o u n t ) 个种群的所包含的个体数 量。 s ( k ) = 鼻，彤磁。胛) 表示协进化算法的当前物种群体； 只2 = x f ：。，x ：，x i 。，) ，c ，f = 1 , 2 ，c ，只表示第i 个进化的物种 的当前群体； ic1=b l o = o ，1 ) i o 表示长度为i c ，的二进制位串的全体，称为位串 的空间，且象征性的记j c d 肿= i c l ，ic ，1 n c 。u r ) ； s ( o ) = 芹，口，圪m ) 表示协进化算法中每个物种群体的初始化情况； t 表示协进化算法的终止条件，可以是进化的代数也可以是变量或函数满足的 条件，还可以人为终止。 s g a = c a 。，g a ：g a c d 肿) 表示各种进化种群所采用的进化算法，每个物种 的进化算法可以相同也可以不同，在这里所有的物种都采用遗传算法； s g a ：s ( k - 1 ) - s ( k ) ，表示从k - 1 代进化到k 代的过程( k 的取值可以从1 到进化 过程结束所经历的代数值) ； s ( 0 ) - s ( 1 ) - s ( 2 ) 一 - s ( i ) 一 s ( k ) 表示物种进化过程； g a 为遗传算法，它规定了该物种的进化选择策略( 在其他种群中选择代表个体) 、 进化操作算子( 选择，交叉，变异) 、各个操作算子执行的概率以及该物种中个体适 应度的评价方式等。 7 协作型协进化算法及其应用 2 3 协作型协进化算法 2 3 1 协作协进化算法流程 为简单起见，本文只考虑协作型协进化算法，且不考虑种群的灭绝与新种群的 生成问题。 首先考虑传统遗传算法g a ，g a 只涉及一个物种的进化过程，它的流程图如图2 2 所示。 图2 - 2 遗传算法( g a ) 的流程图 f i g u r e2 - 2t h ef l o wo fg a 与遗传算法( g a ) 的处理方法类似，协作型协进化算法的流程如图2 3 所示。 首先，初始化一定数目的种群，每个种群代表所求问题的一部分；然后，每个种群 中个体通过与其他种群中个体的合作而得到适应度值的评估；如果没达到要求，那 么所有种群进一步进化。 8 第二章协进化算法 图2 - 3 协作型协进化算法( c c g a ) 的流程 f i g u r e2 - 3t h ef l o wo fc c g a 其中，核心问题是对物种群体中个体的适应度评价，不同的个体适应度评价方 法决定了不同的协进化算法。实际上，可以根据所要解决问题的不同，采取不同的 个体适应度评价策略。一个典型的适应度评价方法是先从其他种群中选择代表个体， 将选出的代表个体与待评价个体组成问题领域中的一个完整解，然后根据这个完整 解来评价该个体的适应度。 对每个种群而言，进化过程中的个体选择是建立在其适应度的基础上的，并运用 遗传操作如交叉和变异来产生后代、评估后代的适应度、用新的个体来取代旧的个 体。 2 3 2 协作型协进化算法中的要素 染色体编码。染色体是一组符号串，它应该能间接或直接表达问题的一个有效解。 在协进化算法中，每个染色体对应一个子问题的解。对染色体编码是建立算法的第 一步，可以用二进制、实数或字符组成染色体。 用到的遗传算子。包括选择、交叉和变异。选择的目的是为了从当前群体中选出 9 协作型协进化算法及其应用 优良的个体，使他们有机会作为父代为下一代繁殖子孙。根据各个个体的适应度值， 按照一定的规则或方法从上一代群体中选出一些优良的个体遗传到下一代群体中。 进行选择的原则是适应度强的个体为下一代贡献一个或多个后代的概率大。交叉操 作是将群体内的各个个体随机搭配成对，对每一对个体，以某个概率( 称为交叉概 率) 交换它们之间的部分染色体，通过交叉可以得到新一代个体，新个体结合了父 辈个体的特性。变异操作首先在群体中选择一个个体，对于选中的个体以一定的概 率随机改变串结构中某个串位的值，即对群体中的每一个个体，以某一概率( 称为 变异率) 改变某一个或某一些基因座上的基因值，变异为新个体的产生提供了机会。 个体适应度的评价。与传统的遗传算法评价适用度的方法不同，在协作型协进 化算法中，评价一个个体时需要从其他的每个群体中都选择一个个体( 我们称此为 代表个体) 与该个体组成一个完整的解，然后用这个完整的解在问题领域中的应用 作为依据来评价该个体的适用度。其中代表个体的选择是关键，根据贪心度的不同， 目前主要的代表个体选择方法可分为最优选择法和随机选择法两种【2 l 】。杨东勇等人 结合这两种方法提出了自适应代表个体选择方法【2 2 】。也可以在对个体进行适应度评 价时，分别进行最优和随机选择，然后选取较高的适应度做为该个体的评价方案。 2 4 多种群协进化的数学模型及分析 为了更进一步的了解协进化算法，我们对协进化算法进行数学模型分析。而要 研究多种群的进化数学模型，我们需要先研究进化算法的数学模型问题。目前关于 进化算法的数学模型还没有形成完整的体系，这是一个仍然需要深入研究的领域。 到现在为止主要有两种思路【2 3 1 ，模式分析法和随机分析法。传统的单个种群的模式 复制方程可以通过对这个种群的模式分析方法而得出，在这里，将这一思路应用到 多个种群的协进化模式分析中去，并将所得结果应用到协进化中代表个体的最优选 择法和随机选择法的分析中。 2 4 1 模式复制方程 如果用不同的信息模式表示种群中每种不同类型的个体，那么种群进化的规律就 能通过信息模式的变化体现出来。为简单期间，在研究模式的增长变化规律时，只 考虑选择遗传操作( 交叉、变异先不考虑) 对种群中各个信息模式变化的影响。该 过程可以用方程表示，我们命名为模式复制方程。并且，通过后面的推导，我们可 以看到模式复制方程在考虑了交叉和变异算子后就可以成为著名的模式复制定理。 首先考虑单个种群的情况。为了方便分析，对种群先假定如下： 1 0 第二章协进化算法 a ) 种群中的信息模式有r 1 种，信息模式表示为i i ，i 属于 1 ，n ； b ) 种群中每种信息模式i i 有x i 个个体，x ，0 ； c ) 信息模式i ：在种群中占的l l f 防j 为p i ，0 尸1 ，这里 p ，：ljx i ：p ，芝x ， x ， 户1 d ) 信息模式，有a ，的相对增长率，这里， 九，：业芸x i ( f + 1 ) ：, 无t x i x ，( ，) 、。 式( 2 2 ) 既为单种群执行遗传算法g a 时信息模式的模式复制方程。 将( 2 1 ) 代入式( 2 2 ) ，并累加整个种群的信息模式，可得： x i ( f + 1 ) = a ，x 心) = 允，p 心) x ，( f ) 结合式( 2 1 ) 、式( 2 3 ) ，可得： 因此， p ，( 川) ：坠生：下j 丛坚： x j ( f + 1 ) a ，p 心) x 。( f ) = l，= l t = 1 p 小+ 1 ) ：- 盟 a ，p ，( f ) j = i ( 2 1 ) ( 2 2 ) ( 2 3 ) 瘩兰! 盟 x 。( f ) k = l ( 2 4 ) 式( 2 4 ) 就是信息模式i ；在单个种群中所占的比例p ，的增长公式。在这里模 式的相对增长率a 实际上于该模式的适应度相对应。 加入交叉和变异因素的模式定理【2 4 2 6 1 如下示： 州m 一) 掣( 1 吨等_ o ( ( 2 5 ) 其中，表示模式串的长度， o ( i ，) 表示模式l i 中的固定位数目， 6 ( ，i ) 表示模式i i 的定义长度， p 。表示交叉概率， 一 o 驴 协作犁协进化算法及其应用 p 。表示变异概率， f ( i 。) 表示模式i i 的适应度， 表示整个种群的平均适应度， 并且： 一x ，f ( 1 ，) f = l ；一 x j 一 ， 与式( 2 2 ) 对比可见，模式定理可以视为模式复制方程的特殊形式，此时： ”a 等”p 。等- d ( ， 娩l o( 2 6 ) 2 4 2 多种群协进化方法的建模 依据多种群协进化的思想：先选择代表个体，再组成协作行为最后应用到目标领 域评估适应度。我们知道，在对个体进行适应度评估时，需要从其他种群中选出代 表个体，与待评估个体组成协作行为，该个体的适应度根据协作行为在目标领域的 表现情况来评估。这里必须重点考虑两个问题： 第一、对协作行为评估过程的建模。因为这里并不是考虑某一具体问题，而是对 一般的情况进行建模，所以不能给出明确的评估模型。为了建模的方便，可以用一 个给定的表现值来表示每种协作行为的评估情况。例如：在两个种群的协进化算法 中，可以用一个矩阵来表示所有个体相互协作的评估值，我们称这个矩阵为交互回 报矩阵，群体a 中的个体i i 与群体b 中的个体j i 的协作行为在目标领域中所得到的 回报用a 打表示，所有的这些元素组成了交互回报矩阵。 第二、代表个体的选择。有多种方法来选择代表个体，可以根据具体的问题采 用不同的选择方法。但在这些方法中，随机选择法和最优选择法是两种最常用的方 法。 下面我们以两个群体的协作型协进化方法为例进行分析，对于三个以上群体的情 况，可以类似分析。 假定a 、b 是两个要进行协进化的群体，群体a 中的参数为：信息模式有m 种， 用，。，i ：，i 。表示；每种模式的个体数目分别为x l ，x ：，x 。，所占比例为p 。， p ：，p 。，相对增长率为九，a ：，a 。群体b 中有n 种信息模式，分别 设为j 。，j 2 ，d 。，每种信息模式的个体数目为y i ，y 2 ，y 。，各自所占的 1 2 第二章协进化算法 比例为q 。，q 2 ，q 。，各自的相对增长率为。，p ：，。根据上述对协作 行为评估过程建模的分析，我们将群体a 与群体b 中个体组合配对的交互回报矩阵 定义为 a 盯) 矿胛，矩阵中的每个元素af ，即为群体a 中的信息模式i i 与群体b 中信息 模式j i 组合配对的适应度回报值。下面就具体化到随机选择和最优选择代表个体时 的情况。 随机选择法 按照此方法对种群a 中的信息模式i i 进行评估，需要随机的从种群b 中选一个 代表个体j j 与之配对。已知条件有：j j 在b 中占的比例吼( 于) ，i i 与j ：j 相配对的适应 度回报值为口打。因为是随机选择的，所以种群b 中的每种模式都可能被选到，可以 用公式表示i i 的适应度如下： 允，= 口 q ，( 于) ( 2 7 ) j = 1 将式( 2 7 ) 代入群体a 中信息模式i i 所占比例增长公式( 2 4 ) 中，即得： 0 p i ( f + 1 ) = p 心) 木i l 九p 七( f ) 其中，a = 口 q j ( f )厶一 。， ：p i ( f ) 木i _ 竽一 ( 口移q ) ) p 。( f ) k = lj = l 口l q )厶“l 7 邓如r 言象丽 k = 1 m ，= i ，h 口l ，qj ( f )厶“l ， ， 谓 广爷 口埘1 a 卅2 口埘 ( 2 8 ) ，p2 【p l ，p 2 ，p 。j ，g2 【g l ，g2 ，g 。j 。 r1r1 1 3 协作型协进化算法及其应用 这里，g7 = a 扩夕，( o q _ ，( f ) 是两个群体a 与b 的平均回报。 i = 1 m _ ，= l ，疗 由式( 2 8 ) 可见，配对回报a 。和相应的配对模式所占比例g ( r ) 在很大程度上 影响着信息模式的增长率，体现在公式中就为：配对回报越大，配对模式所占比例 越大，口。g ，( ，) 就越大，则该两种信息模式的配对就越有利于解决问题，那么，该 = l 信息模式的适应度就越大，在下一代中所占的比例就越大。 最优选择法 按照此方法应在其他种群中选取当前适应度最好的个体与待评估的个体组成完 整解。对应到信息模式中就是，在交互回报矩阵中应该找适应度最好的信息模式， 而适应度最好的信息模式在两个群体的交互回报矩阵中所对应的回报值就是与所要 评估模式i i 相配对信息模式之中的最优回报表现值。 即： a ，2 嚆x ，。) ( 2 9 ) 同上述随机选择的方法：把式( 2 9 ) 代入式( 2 4 ) 即得到信息模式i i 种群a 中 所占比例的增长公式： p ，( f + 1 ) ：0 盟 九。p 。( f ) m a x a ， = p l ( f ) 宰i 盟l 一 ( 2 1 0 ) 。：。m ，：a ，x 。 口茸) z ，t ( f ) 由此可见，模式i i 的增长只与最好的配对回报譬瓷 口f ，) 有关，与相配对的模式 所占的比例g ，( f ) 无关。因此，不管配对模式j j 所占的比例是否很小，只要能够与其 它群体中的个体进行配对并取得好的配对回报，就能促使群体a 中的相应模式快速 增长，这就更加有利于群体中少量存在的优秀信息模式来发挥它们的作用。 1 4 第二章基于混沌理论的协作型仂进化算法 第三章基于混沌理论的协作型协进化算法 与任何其他新生事物一样，协作型协进化算法也存在着一些缺点。核心问题是， 随机产生的有限的个体规模往往无法均匀地覆盖整个解空间，进化过程中的超级个 体会导致进化算法出现早熟收敛( p r e m a t u r ec o n v e r g e n c e ) 现象【2 7 】。 混沌是自然界中一种较为普遍的现象，它看似混乱，却有着精致的内在结构， 具有“随机性”、“遍历性 及“规律性 等特剧2 8 1 ，在一定范围内能按其自身的“规 律”不重复地遍历所有的状态。混沌运动的上述性质作为避免陷入局部极小的优化 搜索机制，恰好可以弥补协作型协进化算法算法易陷入局部最优、收敛速度慢的缺 陷。 本文将混沌映射和协作型协进化算法结合起来，通过在进化的不同阶段进行混沌 映射搜索，大大提升了协作型协进化算法的寻优能力。通过对函数优化问题的求解 实验表明，与标准协作型协进化算法相比，该算法能更有效地求得全局最优解，具 有更好的收敛效果。 3 1 混沌理论简介 一般的混沌是指由确定性方程得到的具有随机性的运动状态，呈现混沌状态的 变量称为混沌变量。常用的混沌模型是一维l o g i s t i c 映射，一维l o g i s t i c 映射从数 学形式上来看是一个非常简单的混沌映射，早在2 0 世纪5 0 年代，有好几位生态学家 就利用过这个简单的差分方程，来描述种群的变化。其数学模型如式3 1 。 x 。+ l = p 木x 。枣( 1 一x 。)肛【0 , 4 x 【0 ，l 】 ( 3 1 ) 式中“为控制参数，有限差分方程( 3 1 ) 可以看作是一个动力学系统。研究表明：当 p 值确定后，由任意初值 0 ，1 ，可以迭代出一个确定的时间序列x 。，x ：，磁。 x o 0 ，1 】时，l o g i s t i c 映射工作处于混沌状态，也就是说，由初始条件x o 在l o g i s t i c 映射作用下产生的序列是非周期的、不收敛的，而在此范围之外，生成的序列必将 收敛于某一个特定的值，而当= 4 时，该系统没有稳定解，是 0 ，1 区间的满映射， 呈现出完全的混沌状态。混沌映射的随机性、遍历性、对初始条件的极度敏感性等 特性，是混沌用于函数优化的根本出发点。 3 2 基于混沌的协作型协进化算法的原理 可以利用上述混沌理论的性质进行优化搜索，其基本思想是首先产生一组与优化 15 协作型协进化算法及其应用 变量相同数目的混沌变量，用类似载波的方法将混沌引入优化变量使其呈现混沌状 态，同时把混沌运动的遍历范围放大到优化变量的取值范围，然后直接利用混沌变 量搜索。由于混沌运动具有随机性、遍历性、对初始条件的敏感性等特点，基于混 沌的搜索技术无疑会比其他搜索更具有优越性。本文将混沌搜索应用到协作型协进 化算法中，提出了基于混沌的协作型协进化算法( c o o p e r a t i v ec o e v o l u t i o n a r y g e n e t i ca l g o r i t h mb a s e do nc h a o s ，c c g a c ) ，其基本思想是在协作型协进化算法 的基础上增加一个进化停滞判断函数，如果进化发生停滞，则对最优个体进行混沌 映射。 不失一般性，考虑如下的优化问题： m a x f ( x 1 ，x 2 ，x d )a ，x ，b ， ( 3 2 ) 日，b ，】为x ，的变化区间，d 为变量的个数，i = l ，2 ，d 。 3 2 1 进化停滞判断函数 在一定的进化代数内，如果最佳适应度值增长小于一个阈值，则判定进化出现 停滞。 一 进化停滞判定函数：f ( t ) 一f ( t 一，) f 。 ( f ) 表示第t 代时整个协进化群体中最高的适应度值。l 表示间隔代数，f 表示 判定停滞的阈值。 3 2 2 混沌映射 在进化过程发生停滞后，对最优个体x = i x 。，x ：，x d 】r 进行混沌映射操作。混 沌映射的具体步骤如下： s t e p l 令混沌映射次数k = o ，随机生成d 个不同的混沌变量，= 【0 ，t ，鬈】r ， 其中，? ( j = 1 ，2 d ) 的值不能取0 ，0 2 5 ，0 5 ，o 7 5 ，1 这5 个l o g i s t i c 映射的 不动点。 s t e p 2 用混沌映射迭代公式t + 1 = j l f 宰彤+ ( 1 一t ) 生成k + 1 代的混沌变量 ，“1 = 【1 k + lt 州，瑶“r s t e p 3 有下列式子计算 的新值： x j - - - a 奉x j + ( 1 一口) 宰彤+ 1 1 6 第三章基于混沌理论的协作雪! 协进化算法 a 的值按公式口：1 一( 兰兰) ”确定，其中m 为整数，依优化目标函数而定，k 为迭 庀 代次数； s t e p 4 计算x = x ，。，x ：，x d 】7 1 的适应度，如果大于x 鼬g 的适应度或混沌映射 迭代达到一定的代数，则停止混沌映射迭代；否则转s t e p 2 ； 3 3 基于混沌的协作型协进化算法的流程 基于混沌的协作型协进化算法的流程如下： s t e p l 对需要优化问题进行分解，生成多个物种群体； s t e p 2 初始化参数：每个种群的大小，变异算子，交叉率，最大进化代数； s t e p 3 对每个种群随机产生一组初始解，初始解的个数为该种群的种群规模， 这样就产生了第一代染色体； s t e p 4 将每个子种群中的每条染色体进行解码，通过种群间的合作转换为问题 的解，并通过此解计算出这条染色体的适应度，并找出种群的最优个体。其中其 他种群的代表个体采用最优选择法。 s t e p 5 用进化停滞判断函数判断进化过程是否发生停滞：若是，则对最优个体 进行一定代数的混沌映射操作；否，进入s t e p 6 。 s t e p 6 对每个种群中的所有个体进行选择、交叉、变异操作； s t e p