（计算机应用技术专业论文）一种基于种群簇的多种群遗传算法.pdf

大连理工大学硕士学位论文 摘要 遗传算法是一种有效的全局优化搜索算法，具有简单通用、鲁棒性强和可并行处理 以及应用范围广等显著特点，在诸多人工智能计算领域获得了广泛的应用，同时取得了 大量的研究成果。本文主要对遗传算法进行了学习与研究，在双种群遗传算法的基础上， 提出了双种群混沌遗传算法和一种基于种群簇的多种群遗传算法。 本文介绍了课题的研究背景以及遗传算法的搜索机制，并针对其早熟以及容易陷入 局部最优等缺点，融合混沌机制，首先提出了双种群混沌遗传算法。混沌是看似随机无 序，但却有着精致的内在结构，利用混沌随机性、遍历性和对初值敏感的特性初始化种 群，使初始种群个体能够均匀的分布在解空间中，避免了由于初始种群完全随机产生而 导致的搜索速度慢的弊端：利用混沌扰动变异的方法，使得算法更容易跳出局部最优解， 增强算法获得全局最优解的能力。通过经典测试算例的实验，结果表明此算法在平均截 止代数和在线性能两个评价指标方面都表现较优。 在双种群混沌遗传算法的基础上，本文进一步提出种群簇和簇首等概念，最终总结 提出一种基于种群簇的多种群遗传算法。每个种群簇由三个具有不同进化规律的种群构 成，第一个种群重视局部搜索，第二个种群重视全局搜索，第三个种群为此种群簇的簇 首，通过与前两个种群的移民机制来均衡算法的局部搜索和全局搜索能力，多个种群簇 之间通过簇首实现簇间信息的交互。通过对经典的测试函数算例的测试，利用平均截止 代数和在线性能这两个性能指标对此算法进行了评估，测试评估结果说明改进后的算法 在算法的稳定性及搜索的速度上均有了稳步的提高。最后将本文提出的算法应用到无线 电决策引擎的实际应用中，并取得了较好的应用效果。 关键词：多种群；种群簇；遗传算法；认知无线电 一种基于种群簇的多种群遗传算法 a m u l t i p l ep o p u l a t i o ng e n e t i ca l g o r i t h mb a s e d o np o p u l a t i o nc l u s t e r a b s t r a c t g e n e t i ca l g o r i t h mi sa l le f f e c t i v eg l o b a lo p t i m i z a t i o ns e a r c ha l g o r i t h m ，a n di ti sw i d e l y u s e di nm a n ya r t i f i c i a li n t e l l i g e n c ef i e l d s i th a st h ec h a r a c t e r i s t i c so fs i m p l e ，p a r a l l e l 谢t h s t r o n gr o b u s t n e s s t h i sp a p e rm a k e sas t u d ya b o u tt h eg e n e t i ca l g o r i t h m ，p r o p o s i n gd o u b l e p o p u l m i o nc h a o sg e n e t i ca l g o r i t h ma n dm u l t i p l ep o p u l a t i o ng e n e t i ca l g o r i t h mb a s e do n p o p u l a t i o nc l u s t e r ，b a s i n go nt h ed o u b l ep o p u l a t i o ng e n e t i ca l g o r i t h m t h er e s e a r c hb a c k g r o u n da n dt h es e a r c hm e c h a n i s ma r ei n t r o d u c e di np a p e r ，a n d c o n s i d e r i n ga b o u tt h ed i s a d v a n t a g eo fe a s i l ym a t u r i t y a n de a s i l yf a l l i n gi n t ol o c a l o p t i m i z a t i o n ，w ep r o p o s et h ed o u b l ep o p u l a t i o nc h a o sg e n e t i ca l g o r i t h m i ts e e m s t h a tt h e c h a o ss y s t e mi ss t o c h a s t i ca n do u to fo r d e r ，b u ti th a si t so w ne x q u i s i t es t r u c t u r e w ec a nu s e i t sc h a r a c t e r i s t i co fs t o c h a s t i c ，e r g o d i c i t ya n ds e n s i t i v i t yo fi n i t i a lv a l u et oi n i t i a l i z et h e p o p u l a t i o n ，m a k i n g t h ei n d i v i d u a l s e v e n l yd i s t r i b u t e d ，a v o i d i n gt h e d e f e c t so fs l o w c o n v e r g e n c ec a u s e db yt h et o t a l l ys t o c h a s t i c w i t ht h ec h a o sd i s t u r b a n c e ，t h ea l g o r i t h mc a n j u m po u to ft h el o c a lo p t i m i z a t i o n , i n c r e a s i n gt h ea b i l i t yo fg e r i n gt h eo p t i m a ls o l u t i o n t h r o u g ht h et e s t sb yc l a s s i c a le x a m p l e s ，t h er e s u l t ss h o wt h a tt h i sa l g o r i t h m i se x c e l l e n ta tt h e a s p e c t so fa v e r a g et r u n c a t e dg e n e r a t i o na n do nl i n ep e r f o r m a n c e b a s e do nt h ed o u b l ep o p u l a t i o nc h a o sg e n e t i ca l g o r i t h m ，t h i sp a p e rp r o p o s e st h e c o n c e p to fp o p u l a t i o nc l u s t e ra n d c l u s t e rh e a d ，s u m m a r i z i n gt h eg e n e t i ca l g o r i t h mb a s e do n t h ep o p u l a t i o nc l u s t e r e a c hp o p u l a t i o nc l u s t e rh a st h r e ep o p u l a t i o n sw i t hd i f f e r e n te v o l u t i o n p a r e m ，a n dt h ef i r s tf o c u so nt h el o c a ls e a r c h ，t h es e c o n df o c u so nt h eo v e r a l ls e a r c h ，w h i l e t h et h i r dt h a ti st h ec l u s t e rh e a dc a nb a l a n c et h es e a r c ha b i l i t ya tb c t ht h el o c a ls e a r c ha n d o v e r a l ls e a r c ht h r o u g ht h em i g r a t i o np a t t e m t h r o u g ht h et e s t sb yc l a s s i c a le x a m p l e s ，t h e r e s u l t ss h o wt h a tt h i sa l g o r i t h mm a k e sp r o g r e s sa tt h ea s p e c t so fa v e r a g et r u n c a t e dg e n e r a t i o n a n do nl i n ep e r f o r m a n c e a tl a s t ，w eu s et h i sa l g o r i t h mi nt h ea p p l i c a t i o no fc o g n i t i v er a d i o ， a n dr e c e i v eg o o da f f e c t k e yw o r d s ：m u l t i p l ep o p u l a t i o n ；p o p u l a t i o nc l u s t e r ；g e n e t i ca l g o r i t h m ；c o g n i t i v e r a d i o i i 大连理工大学学位论文独创性声明 作者郑重声明：所呈交的学位论文，是本人在导师的指导下进行研究 工作所取得的成果。尽我所知，除文中已经注明引用内容和致谢的地方外， 本论文不包含其他个人或集体已经发表的研究成果，也不包含其他已申请 学位或其他用途使用过的成果。与我一同工作的同志对本研究所做的贡献 均已在论文中做了明确的说明并表示了谢意。 若有不实之处，本人愿意承担相关法律责任。 学位论文题目：二盘基王盘羞筮鲍垒盘登遗笾篡洼 作者签名： 銎本纫釜一日期：翌年丝月二日 大连理工大学硕士学位论文 大连理工大学学位论文版权使用授权书 本人完全了解学校有关学位论文知识产权的规定，在校攻读学位期间 论文工作的知识产权属于大连理工大学，允许论文被查阅和借阅。学校有 权保留论文并向国家有关部门或机构送交论文的复印件和电子版：可以将 本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印、或扫描等复制手段保存和汇编本学位论文。 学位论文题目：二盘基王独登筮鲍垒盘登董笾簋洼 一 作者签名： 圣拉圣日期：3 翌2 年坠月- 二竺日 导师签名：差金生日期：j 咀年卫月生日 大连理工大学硕士学位论文 1 绪论 1 1 遗传算法的研究意义 遗传算法( g e n e t i ca l g o r i t h m s ，简称g a ) 是当今世界影响最广泛的进化计算方法 之一，是一种应用非常广泛的随机搜索和优化技术。遗传算法基于达尔文自然进化论和 孟德尔遗传变异理论为基础的随机搜索方法，是由美国m i c h i g a n 大学的h o l l a n d 教授首 先提出来【l 】。d a v i de g o l d b e r g 教授1 0 8 9 年出版的( ( g e n e t i ca l g o r i t h m s ) ) 一书通常认为 是对遗传算法的方法、理论及应用的全面系统的总结，它的出版标志着遗传算法的诞生 1 2 1 。达尔文的生物进化论说明，生物进化经历了自然选择、遗传算法的内涵哲理乃是启 迪于自然界生物从低级、简单，到高级、复杂，乃至人类这样一个漫长而绝妙的进化过 程。借鉴于达尔文的物竞天演、优胜劣汰、适者生存的自然选择和自然遗传的进化理论， 地球上的每一物种从诞生开始就进入了漫长的进化历程，而这一过程本质上就是一种优 化过程【3 】。遗传算法的演变过程正是基于对此过程的模拟，它是生命科学与工程科学互 相交叉、互相渗透的产物，是一种基于自然选择和遗传变异等生物进化机制的全局性概 率搜索算法，是一种可以有效解决最优化问题的方法。 遗传算法是模拟生物进化过程的计算模型，其引入繁殖、杂交、变异、竞争和选择 等概念，具有较强适应能力的个体会在进化中被保留下来并有较多的机会产生后代，而 适应能力弱的个体则会有较少的机会产生后代并且被淘汰。遗传算法在进化的过程中通 过维持一组或多组可行解，并且改进可行解在多维空间内的移动轨迹或趋势，通过不断 的迭代最终进行得到最优解或较优解。遗传算法做为一种全新的优化搜索算法，以其简 单通用、鲁棒性强、适用于并行处理等显著特点，被研究工作者广泛采用1 4 】。 遗传算法是- f - j 新兴学科，从上世纪六、七十年代形成相对规范的一套理论体系到 目前多种多样的改进方法，只有几十年的发展时间。由于其优良的特性和较强的实用性， 国内外学者都投入了大量的人力物力进行深入研究，极大的促进了遗传算法的长足发 展。目前，遗传算法在理论设计和领域应用等方面都取得了长足的发展，并且取得了丰 硕的研究成果。遗传算法已成功地应用于许多不同的实际问题，如：机器学习、人工神 经网络、自适应控制、t s p 问题、背包问题、作业调度问题( j s p ) 、资源分配问题、 网络计划问题、车辆调度问题以及人工智能问题等。 随着i n t e r n e t 技术的发展和对遗传算法研究工作的不断深入，遗传算法的有关研究 单位建立了大量的专题g a 网站，包括了世界范围内的开展遗传算法和进化计算研究的 大学和机构，历年来的可公开发表的论文和报告等等。美国和欧洲众多国家也相继开展 一种基于种群簇的多种群遗传算法 研讨会议，探讨遗传算法的改进以及应用。众多的研究单位和频繁的国际学术活动集中 反应了遗传算法的学术意义和应用价值。目前，遗传算法己成为一个多学科、多领域的 重要研究方向。 1 2 遗传算法的发展及现状 遗传算法起源于2 0 世纪6 0 年代对自然和人工自适应系统的研究，最早由美国密执 安大学的h o l l a n d 教授提出。h o l l a n d 的早期工作主要集中在生物学、社会学、控制工程 和人工智能领域的动态系统的适应性问题，他不仅设计了遗传算法的模拟与操作原理， 还运用统计决策理论对遗传算法的搜索机理进行了理论分析，建立了著名的模式定理和 隐含并行性原理，为遗传算法的发展奠定了基础【5 】。 2 0 世纪7 0 年代d ej o n g 基于遗传算法的思想在计算机上进行了大量的纯数值函数 优化计算实验，并在其博士论文中设计了一系列遗传算法的执行策略和性能评价指标， 对遗传算法性能作了大量的分析。2 0 世纪8 0 年代由g o l d b e r g 进行归纳总结，出版了专 著搜索、优化和机器学习中的遗传算法，形成了遗传算法的基本框架。2 0 世纪9 0 年代，遗传算法开始进入了高速发展期。我国关于遗传算法的研究始于2 0 世纪9 0 年代， 出现了不少研究遗传算法的专家，提出了许多遗传算法的改进。 目前关于遗传算法的改进工作大部分是结合其它优化理论而形成的混合遗传算法， 即是将遗传算法和一种或多种其它的优化算法结合到一起，对问题进行求解。例如文献 【6 利用遗传算法的全局搜索能力和模拟退火操作的局部寻优能力进行了改进，文献 7 】 混合了最优保存、最速下降法和自适应的理论，都对遗传算法的性能做出了改进。遗传 算法全局搜索能力强、局部搜索能力差，通过在遗传算法中引入局部搜索能力强的算法， 既可以发挥遗传算法自身的优势，又可以利用其它优化算法的长处来弥补其不足，扬长 避短，可以起到很好的效果。因为其优化效率较高，此种改进方式已渐渐成为近年来最 为活跃的一个研究方向，混合的方式大致可分为以下三类： ( 1 ) 两种算法各自独立求解，其中一方利用另一方计算结果，但并不直接进入对 方的搜索过程。常见的是，一旦遗传算法搜到优异的可行解，马上换用其它算法求解。 ( 2 ) 一方作为附加成分加入到另一方的搜索中。例如，在遗传算法中引入其它算 法，该算法在遗传算法的计算基础上，通过搜索产生更优的最优个体，引导种群新一轮 的进化。 大连理工大学硕士学位论文 ( 3 ) 两种算法融合在一起共同求解，一方作为另一方的必要组成部分，直接参与 对方的搜索。例如，遗传算法可以作为禁忌搜索的变异算子，融合到禁忌搜索的过程中； 模拟退火算法与遗传算法也属于这种方式的混合。 目前研究得较为成熟的主要有以下六种混合算法： ( 1 ) 启发式遗传算法：将启发式算法跟遗传算法的混合，贪心法、单纯型算法、 爬山法、梯度法、最速下降法、禁忌法等都属于启发式算法。 ( 2 ) 模拟退火遗传算法：模拟退火算法与遗传算法的混合，其一直是研究学者提 高遗传算法性能的重要途径之一。 ( 3 ) 免疫遗传算法：免疫算法是一种基于自然界生物体免疫系统的优化算法，是 目前机械多目标优化设计中的一个新的研究方向。混合方法主要有两种，一种是基于疫 苗机制的免疫遗传算法，提取问题基本的特征信息作为疫苗，对新生个体的基因进行修 正；另一种是在遗传算法中引入免疫算法的抗体多样性维持机制，使其性能比标准免疫 算法和标准遗传算法都更进了一步。 ( 4 ) 蚁群遗传算法：蚁群算法同遗传算法的混合，利用信息素浓度控制遗传算法 的搜索方向，适合求解旅行商( t s p ) 问题瞪j 。 ( 5 ) 混沌遗传算法：利用混沌系统随机性、遍历性和对初值敏感的特性，生成遗 传算法的初始进化种群；同时可利用混沌系统进行混沌扰动，增加遗传算法的全局搜索 能力1 0 1 。 ( 6 ) 量子遗传算法：用量子态来表示遗传信息，实现信息的量子化，是量子计算 和遗传计算的结合产物【1 1 1 。量子遗传算法建立在量子的态矢量表述基础上，将量子比特 的几率幅表示应用于染色体的编码，使得一条染色体可以表达多个态的叠加，并利用量 子旋转门和量子非门实现染色体的更新操作，从而实现了目标的优化求解。 1 3 遗传算法的特点及应用 遗传算法与传统的优化算法相比，主要有以下四个特点： ( 1 ) 运算对象是决策变量的编码。我们通过模拟借鉴生物进化学中的染色体以及 基因位等概念，结合研究者所提出的遗传操作算子等概念，将一些负责的数学问题转化 为计算机可执行的运算。这种发放将对特定复杂问题本身的优化转化为对染色体的优化 问题。 ( 2 ) 遗传算法只需处理染色体各基因位的变化，处理简单适应。而不需要对待求 解问题进行复杂的求导等数学运算，大大减少了工作量。 一种基于种群簇的多种群遗传算法 ( 3 ) 遗传算法是一种对概率灵活运用的一种数学方法。方法中的选择、交叉和变 异都是以一定的概率来进行遗传的，这样有利于算法在解空间内进行大范围的、不定性 的搜索。有的时候这种概率特性也会让种群中产生出适应度值比较低的个体，但是这完 全可以通过适当的替代策略来避免或提出适应度值低的个体的存在。实践和理论都己证 明了在一定条件下遗传算法总是以概率1 收敛到问题的最优解。 ( 4 ) 遗传算法是一种可并行处理的搜索算法，大大提高算法本身的搜索性能，适 用于规模并行计算机。传统的优化算法往往是从单个初始点开始搜索过程，所提供的搜 索信息毕竟不多，导致搜索效率往往不高，有时甚至使搜索过程陷于局部最优解而停滞 不前。遗传算法可从解空间的多个点同时进行搜索，并通过一系列的遗传操作产生出新 一代的群体，在这之中包括了很多群体信息，所以实际上相当于搜索了更多的点，覆盖 面大，利于全局择优。 现在遗传算法作为具有系统优化、适应和学习的高性能计算和建模方法的研究渐趋 成熟。其主要应用领域包括函数优化、优化组合、生产调度问题、自动控制、机器人学、 图像处理、人工生命、遗传编程和机器学习等方面。近些年来改进的遗传算法，已在各 个领域得到了广泛的应用，能够求解大规模问题和复杂问题。如用并行遗传算法优化无 线通讯网的选址问题、原子核反应堆的核设计优化和航天工程领域等，显示了遗传算法 巨大的潜力和诱人的前景，使越来越多的人和团体投入到这个领域，遗传算法的研究已 经出现热潮。 1 4 双种群遗传算法 作为一种搜索算法，遗传算法的基本框架已经形成，在各种问题的求解和应用中展 现了它的特点和魅力，同时也暴露了在理论和应用技术的不足和缺陷【l2 1 。遗传算法往往 出现早熟收敛或收敛缓慢等缺点，在进化计算过程中，个体的多样性下降过快，严重影 响遗传算法通过交叉和变异跳出局部最优的能力，也就降低了遗传算法进化到全局最优 的速度。为提高遗传算法全局收敛率，提出了一种改进的双群体遗传算法 ( d u a l p o p u l a t i o ng e n e t i ca l g o r i t h m ，简称d p g a ) ，多个子种群各自独立进化，并在 合适的时机以一定的规则进行相互交流。通过对不同的子种群采用不同的交叉、变异和 复制方法，使得遗传算法具有较强的局部搜索能力和全局探索能力。 1 4 1 双种群遗传算法的研究背景 目前遗传算法的应用已经越来越广泛，且在众多领域中都效果显著，但是此算法本 身仍存在有以下三个方面的问题： 大连理工大学硕士学位论文 ( 1 )目前研究者有很多通过融合各种优化算法到遗传算法中，进行算法结构以及 遗传算子的改进。但是混合的算法变多的同时也会增加算法的空间复杂度和时间复杂 度，并且过于复杂的结构会耗费大量的时间和资源。所以在进行遗传算法改进的过程中， 一定要注意算法本身的复杂程度。 ( 2 ) 遗传算法在遗传进化的后期，非常容易早熟或者陷入局部最优解。主要是因 为在进化算法中，各种替代策略都会在某种程度上降低种群的多样性，让有效基因位或 者染色个体消失。 。 ( 3 ) 对遗传操作过程中淘汰的劣解重视不足。模式定理中，将具有低阶、短定义 距及高适应度的模式称为积木块。低阶、短定义距及高于平均适应度的模式在遗传算子 的作用下，相互结合，能生成高阶、长定义距、更高平均适应度的模式，并可最终生成 全局最优解，这就是重要积木块假设。被淘汰的劣解整体实力并不是很强，但是其中却 可能存在着非常好的模式。这些好的模式的丧失会在一定程度上影响最终解的生成。 单种群算法简单易行，搜索速度快，但是其搜索空间有限，而且极易陷入局部最优 的困境。并行遗传算法可以比较好地解决这个问题。但是子种群多则意味着耗费的时间 增多，因为子种群的分配和信息的交换都需要耗费一定的时间。然而在某些问题上，人 们对解的精度要求不是特别高，对时间的要求确是特别苛刻，怎样在比较短的时间内得 到比较理想的目标解，针对这个问题，科研者提出了双种群遗传算法。m a r t i k a n i e n 等提 出了分层次的双种群遗传算法；杨小芹等提出基于熵的双群体遗传算法1 1 3 j ；卢雪燕等提 出了蜜蜂双种群遗传算法1 1 4 】；李军华等提出了一种改进的双种群遗传算法【l 5 1 。 1 4 2 双种群遗传算法的特点 在双种群遗传算法中同时进化两个群体，并且两个子种群的交叉、变异以及复制操 作互不相同。在一个子种群中，注重提高其局部搜索的能力，使高相似个体之间具有相 对高的交叉率，遗传操作得到的新个体替代上代种群的最劣的个体；在另二个子种群中， 注重提高其全局搜索的能力，使低相似个体之间具有相对高的交叉率，并且变异操作采 用大变异算子，遗传操作得到的新个体替代上代种群的与其最相似个体。两个子种群之 间的移民操作可以使新的算法获得良好的局部搜索能力和全局探索能力。双种群遗传算 法的主要优点在于：独立进化保证了种群的多样性，而子种群间优秀个体的交换保证了 可行解收敛的速度。 但是对于双种群的这个“双 的概念，并不是完全统一的，文献 1 6 1 归纳出以下 三种不同的“双 种群的结构形式： 种基于种群簇的多种群遗传算法 ( 1 ) 用两个子种群代替原来的单一种群 基本思想是：用两个种群代替传统遗传算法中的一个独立的种群，并且这两个种群 的遗传操作也都相互独立，选用不同的交叉和变异策略。通常将交叉和变异概率大的种 群叫做探测子种群，用于在全局解空间内搜索，可以为进化历程提供新的超平面，可以 很好的克服早熟和陷入局部最优的缺点。将交叉和变异概率小的种群叫做开发子种群， 用于在当前较优解的周围搜索更优个体，并将其保存到进化历程中。两个子种群各自独 立进化，每进化一代( 子种群独立进化次数) 就把当前总最优个体分散到所有子种群中 去，以促进各个子种群的进化，加快进化速度。 ( 2 ) 在大范围全局搜索之后引进小种群搜索 基本思想是：当全局搜索达到一定条件时，从中选取最好的个体集x ( x 1 ，x 2 x i x m ) ，m 小于种群的规模。而后，以x i 为中心，在一定范围内随机生成i 个小种 群，小种群各自独立进行局部搜索得到较好解y l ，y 2 y i y m ，组成局部较好解集 y ，并替换x t l 6 j 。 ( 3 ) 受蜜蜂和蜂群特殊繁殖方式的启发而提出的一种结构 基本思想是：模拟蜜蜂这种生物的群体生活方式，算法中由蜂王、工蜂和雄蜂组成， 它们在群体中各尽其责。一个群体中的蜂王只有一个，雄蜂会有1 0 0 0 多只，工蜂有成 千上万只。蜂王唯一的职能是产卵繁殖后代；雄蜂除了在繁殖季节与蜂王交尾外不承担 任何其他工作，其品种和体质的好坏对新蜂群后代的品质有直接影响；工蜂无生殖能力， 是蜂巢内外一切繁重劳动的承担者。这里的蜂王在此群体的进化过程中发挥着主导性的 作用，并且它可以与雄蜂交配进化出种群的下一代，工蜂通常对种群进化的基因变化不 产生影响，因此在进化计算的时候可以将工蜂忽略，只考虑群体中存在蜂王和雄蜂的情 况。另外，蜜蜂有中进化现象叫做婚飞，即一个群体中的蜂王也有可能与另一个群体中 的工蜂进行交尾产生下一代，由于蜜蜂交尾是在野外进行，因此婚飞的概率也很大。 通过上述三种双种群的结构，我们可以把它视为三种不同的信息交互的方式。第二 种结构通过局部更优解代替局部较优解实现交换；第三种结构通过将两个种群融合成一 个新种群来进行交流。这两种结构较少被使用，最常用的是第一种结构。在这种结构中， 信息的交换是靠交换优秀染色体实现的，也即是“迁移”这一策略。但是种群和种群之 间的关系除了信息交换外，也存在着“竞争”，能不能用竞争的方式来引导两个种群的 协同进化。 大连理工大学硕士学位论文 1 5 本论文的主要内容 随着遗传算法的广泛应用以及研究的深入，其诸多缺陷被暴露出来，例如早熟收敛 或收敛缓慢等。遗传算法在进化计算过程中，个体的多样性下降过快，严重影响遗传算 法通过交叉和变异跳出局部最优的能力，也降低了遗传算法进化到全局最优的速度。 本文在详细分析遗传算法机制的基础上，进一步思考遗传算法的理论根源，它是对 现实世界进化理论的一种模拟机制。一个现实生活中的国家是由不同地区组成，而整个 现实世界又是由很多国家构成。因此本文提出种群簇的概念，并提出一种基于种群簇的 多种群遗传算法( b a s e do nc l u s t e rm u l t i p l ep o p u l a t i o ng e n e t i ca l g o r i t h m ，b c m p g a ) ， 每个种群簇对应现实中的一个国家，每个种群簇中的不同种群对应现实一个国家的不同 地区，每个种群簇中的簇首是代表种群簇中优秀基因的群体。各种群簇之间的信息交互 通过各簇首的交互来实现，及实现现实世界中国家的信息传递。整体算法在扩大搜索群 体的同时，运用不用的遗传策略可保证算法的局部搜索特性和全局搜索特性。 最后结合本文所提出的基于种群簇的多种群遗传算法，文章中运用几个经典算例来 验证此算法的正确性，并将其应用到实际无线电决策系统中，取得了较好的应用效果。 1 6 本学位论文的组织 第一章：绪论，介绍传统遗传算法以及双种群遗传算法的发展。 第二章：基本遗传算法，详细分析研究基本遗传算法的理论背景。 第三章：详细研究双种群遗传算法，并引入混沌机制，提出基于混沌的双种群遗传 算法，并通过算例验证此算法的有效性。 第四章：结合本文提出的种群簇的概念以及混沌双种群的思想，提出一种基于种群 簇的多种群遗传算法。并通过诸多经典算例从平均截止代数和在线性能等方面验证此算 法的有效性。 第五章：把本文提出的算法应用到无线电认知决策系统中，进行大范围的决策优化 搜索，实验结果标明本算法可以很好的解决多目标优化问题。 一种基于种群簇的多种群遗传算法 2 基本遗传算法 2 1 生物进化 达尔文的自然选择学说是1 9 世纪世界四大学说之一，其主要内容是过度繁殖，生 存斗争( 也叫生存竞争) ，遗传和变异，适者生存。在这个世界上，一切的生物都有生 长、繁殖与变异等基本生物进化机制。在漫长的自然选择进化的历程中，各种物种都以 一定得进化规则朝着固定的方向发展，可以用相应的自然选择学说来解释生物的这种进 化，达尔文将这种生物规律进行总结归纳，主要包括以下三个方面： ( 1 ) 遗传：亲代把生物信息交给子代，子代按照信息发育分化产生与亲代相同或 相似的性状。遗传是生物进化最普遍的进化规律，是一切生物进化必须经历的发展历程。 它的主要表现形式是通过父代个体染色体的基因位进行遗传的，遗传算法主要是在等位 基因上进行交叉或者变异，大部分的遗传操作都是基于等位基因来进行的，有利于算法 的实现和管理。 ( 2 ) 变异：变异的主要载体是染色体，其中脱脂核糖核酸( d n a ) 是最主要的遗 传物质，而控制生物开关的基因是遗传物质的结构单位和功能单位。现代遗传学证明， 基因是有遗传效应的片段，它储存着遗传信息，可以准确地复制，也能够发生突变。生 物体自身通过对基因的复制和杂交选择和控制遗传性状，通过基因变异和重组使性状发 生突变。 ( 3 ) 适者生存：在生存斗争中，具有有利变异的个体由于对环境的适应性比较强 容易存活下来，从而在生存斗争中获胜，并且有更多的机会将有利变异传给后代。具有 不利变异的个体由于对环境的适应性比较差就容易被淘汰，成为生存斗争中的失败者， 产生后代的机会也就少得多。这就是达尔文进化论中“适者生存，不适者淘汰”的自然 选择学说。 这种进化过程从本质上来说算是一种复杂优化问题，会在各种外界因素的影响下向 最优的结果进化。这种生物进化的过程跟很多现实中的问题可以相对应，研究者通过利 用进化计算，在计算机大规模计算的帮助下，创立全新的优化算法，可以达到在可行的 时间范围内得到有效解。 2 2 遗传算法概况 遗传算法( g e n e t i ca l g o r i t h m ，简称g a ) 是最近几十年新兴的一种仿生全局优化算 法，它采用生物遗传学的观点，通过遗传机制自然选择、遗传和变异等操作，实现 大连理工大学硕士学位论文 种群进化、个体性能改善。遗传算法的运算跟传统的优化算法不同，不是从一个点开始 计算的，而是从多个空间点组成的种群开始的，初始的搜索是在问题可行域内的一组空 间点。 将生物世界中的每一个个体都对应到遗传算法中的每一染色体，具有n 位染色体基 因位的个体为一个独立的生物个体，可以在此基础上进行遗传操作，同时该个体在种群 中的生存适应度的大小也是由其染色体上各个基因位的编码来共同决定的。通常这些个 体的染色体是由计算机编码来随机生成的，但是在某些算法中，也可以通过适当的算法 来调整生成的初始种群的性能，有利于缩短群体进化的历程。根据“优胜劣汰、适者生 存的 生存规则，遗传算法定义相应的个体适应度评价方法，并根据此方法的评价结果 进行种群个体的选择、交叉以及淘汰。下一代的个体都是由父代个体经历选择、基因重 组和基因突变等遗传操作得到的，它们会更适应当前的生存环境。此种进化历程不断重 复，并通过适当方法保留历代种群中的最优解，直至进化到种群的最大进化代数或者满 足算法的终止条件，将最优个体进行解码，就得到了我们所求问题的最优解。 2 3基础术语 遗传算法是基于自然选择和生物进化的一种模仿生物进化的随机方法。因此遗传算 法经常会使用到一些关于自然进化的基本概念与术语【5 】。 种群( p o p u l a t i o n ) ：染色体带有特征的个体的集合。 个体( i n d i v i d u a l ) ：染色体带有特征的实体。 基因( g e n e ) ：控制生物性状的遗传物质的功能单位和结构单位。 染色体( c h r o m o s o m e ) ：遗传物质的主要载体，由多个遗传因子基因组成。 基因座( l o c u s ) ：染色体中基因的位置，同一基因座可能有的全部基因称为等位 基因。 表现型( p h e n o t y p e ) ：染色体表示模式，是指生物个体所表现出来的性状。 基因型( g e n e t y p e ) ：染色体表示模式，是指与表现型密切相关的基因组成。 同一种基因型的生物个体在不同的环境条件下可以有不同的表现型，因此表现型是 基因型与环境条件相互作用的结果。 适应度( f i t n e s s ) ：衡量某个物种对于生存环境的适应程度，对生存环境适应程度 较高的物种获得更多的繁殖机会。 选择( s e l e c t i o n ) ：指决定以一定的概率从种群中选择若干个体的操作。是一种基 于适应度的优胜劣汰的过程。 一9 一 一种基于种群簇的多种群遗传算法 交叉( c r o s s o v e r ) ：有性生殖生物在繁殖下一代时两个同源染色体之间通过交叉而 重组，亦即在两个染色体的某一相同位置处d n a 被切断，其前后两串分别交叉组合形 成两个新的染色体，俗称“杂交”。 变异( m u t a t i o n ) ：在细胞进行复制时可能以很小的概率产生某些复制差错，从而 使d n a 发生某种变异，产生出新的染色体，这些新的染色体表现出新的性状。 编码( c o d i n g ) ：遗传编码可以看作从表现型到基因型的映射。 解码( d e c o d i n g ) ：从基因型到表现型的映射。 2 4 基本原理 2 4 1 编码 编码工作是遗传算法的基础，合理选用不同的编码方式，可以大大降低算法的搜索 时间以及搜索范围，进而提高遗传算法搜索全局最优解的性能。编码同时也是遗传算法 的一大特点，算法不是对复杂问题本身进行处理，而是把在数学分析和处理中难以实现 得问题转化到在计算机这样易于大规模计算的领域。从而将待解决的问题从一个状态空 间转换到更易于实现得另一个码空间，这在很大程度上依赖于问题的性质，并将影响遗 传操作的设计【1 7 】。 通常使用的遗传算法的编码方式有以下三种，需要使用者根据具体实际问题选用能 提高算法性能的编码方式。 ( 1 ) 二进制编码 h o l l a n d 提出的遗传算法是采用二进制编码来表现个体的遗传基因型的，它使用的 编码符号集由二进制符号0 和1 组成的，因此实际的遗传基因型是二进制符号串，其优 点在于编码、解码操作简单，交叉与变异等遗传操作便于实现等。 设一维连续实数f ( x ) ，x 【1 1 , b 采用长度为的二进制字符串进行定长编码，建立 个体位串空间： 其中， s 工= q ，口2 a k 鲰) ，吼= ( a k l ，q 2 a r l ) 0 ，1 ) ，k = 1 ，2 k ，z = 1 ，2 上 大连理工大学硕士学位论文 其中，个体向量表示为a k = ( a k l ，吼2 ，) ，其字符串形式为s k = a k l a k 2 ，s k 称 为个体吼对应的位串，精度表示为：缸= ( b a ) ( 2 工1 ) 。采用二进制编码的遗传算法进 行数值优化时，可以通过改变编码长度，调节搜索精度和效率之间的关系。 ( 2 ) 序列编码 采用g a 求解类似t s p 问题时，用排列法进行编码，比如有1 0 个城市的t s p 问题， 城市序号为 0 ，1 ，2 ，3 ，4 ，5 ，6 ，7 ，8 ，9 ，若编码为1 3 5 7 9 2 4 6 8 0 表示按特定顺序 1 3 5 792 468 0 依次访问各个城市。 ( 3 ) 实数编码 实际应用中可根据需要选择实数位串形式。实数编码具有精度高，便于大空间搜索 的优点。由于二进制编码的进化层次是基因，实数编码的进化层次是个体，所以二进制 编码的一些理论并不适合于实数编码。但是试验结果表明，对于统一优化问题二进制编 码和实数编码g a 不存在显著的性能差异。 2 4 2 种群初始化 遗传算法与传统随机类搜索算法的最大区别之一，在于它的整个算法是在解的群体 上进行的。正是这一特点是g a 具有了搜索过程的并行性，全局性和鲁棒性，可见群体 的设定对整个g a 的运行性能具有决定作用。 根据模式定理，群体规模对遗传算法的性能影响很大。若群体规模为n ，则遗传算 子可以从这n 个个体中生成和检测o ( n 3 ) 个模式，并在此基础上不断形成和优化建筑模 块，直到找到问题的最优解。群体规模越大，群体中个体的多样性越高，个体陷入局部 解的危险就越小。但是随着群体规模增大，计算量也显著增加。若群体规模太小，使遗 传算法的搜索空间受到限制，则可能产生未成熟收敛的现象。 2 4 3 适应度函数的设计 遗传算法在进化搜索中基本不利用外部信息，仅以适应度函数( f i t n e s sf u n c t i o n ) 为依据，利用种群中每个个体的适应度值来进行搜索。遗传算法的目标函数不受连续可 微的约束且定义域可以为任何集合。由于适应度函数个体生存机会选择的唯一确定性指 标，所以适应度函数的形式直接决定着群体的进化行为。在具体应用中，适应度函数的 设计也要结合问题本身的要求而定。因此适应度函数的选取至关重要。几种常见的适应 度函数有以下二种： ( 1 ) 若目标函数为最小问题，则目标函数f ( x ) 与适应度函数f i t ( f ( x ) ) 的映射关 系： 一种基于种群簇的多种群遗传算法 f i t ( f ) - c 懈o x 巍q ( 2 1 ) 其中，c m 。可以是输入值或理论上的最大值，或者是当前代中f ( x ) 的最大值的最大 估计值，c m 。最好与种群无关。 ( 2 ) 若目标函数为最大问题，则目标函数f ( x ) 与适应度函数f i t ( f ( x ) ) 的映射关 系： 础砌= 舻嚣 ( 2 2 ) 其中，q 。可以是输入值或理论上的最小值，或者是当前代中f ( x ) 的最小值。 2 4 4 遗传因子的设计 遗传算法利用遗传算子产生新一代种群来实现种群进化，进行优胜劣汰时涉及算法 基本思路，并在选择、交叉、变异等遗传算子中得以体现，并考虑到对算法效率与性能 的影响【1 8 】。遗传算法的遗传算子，主要包括繁殖、杂交、变异以及其它高级操作。遗传 算法包括三种运算：遗传、杂交和变异【1 9 1 。 ( 1 ) 选择( s e l e c t i o n ) 算子 选择的目的是为了从当前的群体中选出优良的个体，使它们有机会作为父代繁殖子 孙。而判断群体中个体的优良依据各自的适应度值。算法借用了适者生存的进化原则， 适应度高的个体被选择的几率大。目前，主要的选择方式有按比例的适应度分配，基于 排序的适应度分配等。 适应度比例方法( f i t n e s sp r o p o r t i o n a lm o d e l ) 该方法是目前遗传算法中最基本也是最常用的选择方法，也称轮盘赌选择。在该方 法中，各个个体的选择概率和其适应度值成比例。 设群体大小为，z ，个体f 的适应度值为彳，则个体i 被选择的概率只为： 只= ，z ( 2 3 ) 从上式看到，适应度越大，其被选择的概率就越高。但是，当群体中个体适应度值 的差异较大时，最佳个体和最差个体被选择的概率之比也按指数增长，因此，最佳个体 的生存机会显著增加，而最差个体的生存机会被剥夺，最终导致当前群体的最佳个体快 速充满整个种群，群体的多样性迅速降低，g a 也就过早的失去了进化能力，导致早熟， 收敛到局部解，这是适应度比例选择容易出现的问题。 大连理工大学硕士学位论文 排序选择 排序选择方法是指将群体中个体按其适应度值由大到小的顺序排成一个序列，然后 将事先设计好的概率表按序分配给每个个体作为各自的选择概率。这种方法不利用个体 适应度值绝对值的信息，可以避免群体进化的适应度值标度变换，特别适用于动态调整 选择概率，根据进化效果适时改变群体选择压力。不足之处在于选择概率和序号的关系 需要事先确定。 b o l t z m a n 选择 在群体进化过程中，不同阶段需要不同的选择压力。早期阶段选择压力较小，希望 较差个体也有一定的生存机会，使得群体保持较高的多样性；后期阶段选择压力较大， 希望g a 缩小搜索邻域，加快当前最优解改善的速度。为了动态调整选择压力，可以使 用式( 2 4 ) 作为选择概率。其中，r 是退火温度，且t 0 。t 随迭代次数的增加而逐 渐减小。丁是控制群体进化过程中选择压力的关键，一般丁选择要考虑预计最大进化代 数。 ，” b = 7 7 ( 2 4 ) i - 一1 ， ( 2 ) 交叉( c r o s s o v e r ) 算子 生物进化的核心是基因重组加上变异，同样遗传算法中起核心作用的是遗传操作的 交叉算子。所谓交叉是指把两个父代个体的部分结构加以替换重组而生成新个体的操 作，通过交叉，使搜索能力得到飞跃提高。以字符串编码为前提介绍几种基本的交叉方 法。 一点交叉( o n e p o i n tc r o s s o v e r ) 一点交叉又称为简单交叉，在个体串中随机设定一个交叉点，实行交叉时，该点前 或后的两个个体的部分进行互换，并生成两个新的个体。交叉位置的偏差可能带来较大 的不同。 二点交叉( t w o p o i n tc r o s s o v e r ) 随机设置两个交叉点，两个个体将两个交叉点之间的位串互相交换。多点交叉则是 两点交叉的推广。然而多点交叉很少使用，因为此交叉方式进行太多次的交叉互换，因 而不能够保存重要的优的模式。 一致交叉( u n i f o r mc r o s s o