（计算机应用技术专业论文）计算智能及其在无线传感器网络优化中的应用.pdf

1iljjjllijljjilj j1-，lill一 i 授权说明 独立进行研究工作所取 得的成果。除文中已经注明引用的内容外，本论文不含任何其他个人或集体已经发表或撰写 过的作品或成果。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。 本声明的法律结果由本人承担。 论文作者签名： 也最 日期：少p 年3 - 月瑚e l 学位论文版权使用授权说明 本人完全了解海南大学关于收集、保存、使用学位论文的规定，即：学校有权保留并向 国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权海南大 学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存和汇编本学位论文。本人在导师指导下完成的论文成果，知识产权归属海 南大学。 保密论义在解密后遵守此规定。 ：j 9 讲最名：乞咿 日期：山如年 甫匀日日期：少口年f 月弼e 1 本人已经认真阅读“c a l l s 高校学位论文全文数据库发布章程”，同意将本人的学位论 文提交“c a l l s 高校学位论文全文数据库”中全文发布，并可按 权益。园童途塞握銮丘澄卮；遂匕生；旦= 生；旦三生蕉盔。 论文作者签名：一 j 痞乙 日期：如k 钳月船e l “章程”中规定享受相关 导师签名： 日期：泓舟r 月蟋日 海南大学硕士学位论文摘要 摘要 随着科学的发展和时代的进步，人们在工业生产和工程实践过程中遇到的问 题，越来越多地具有规模大、复杂性、约束性、非线性、不确定性等特点，在生 产实践和科学研究的诸多领域有大量的问题都急需人们在庞大和复杂空间寻找 最优解或近似最优解，常规的优化算法面对这样的大型问题已无能为力。计算智 能作为一种新兴的优化技术，很好地解决了常规优化算法遇到的难点，其算法相 对简单，易理解，易实现，更为重要的是，计算智能方法大都具有隐含并行性、 自组织、自适应等特点，有效地促进了其在生产各领域中的优化应用，对生产效 率的提高、能耗的降低、资源的合理利用等具有重要的作用。 本文从计算智能中的两种应用广泛的技术i 挂化计算和群体智能入手，以 进化计算中经典的遗传算法和群体智能中具有代表性的蚁群优化算法作为研究 基础，简单介绍了这两种算法的相关理论和特点，然后进行一些改进，并与其他 算法进行了融合，寻找适合于工程实践需求的智能优化应用。在具体的优化应用 中，本文针对无线传感器网络( w i r e l e s ss e n s o rn e t w o r k , w s n ) 必须有很强的自组 织性、自适应性和鲁棒性且传感器节点的能量资源都非常有限等不同于其他传统 网络的特点，充分利用计算智能特性，有机地将两个研究热点结合起来，为应用 计算智能方法解决w s n 优化问题，提供了方法与思路。 本文主要在三个方面做了一些工作：一，对w s n 分簇问题进行了描述和 研究，并将遗传算法应用于w s n 分簇过程，综合考虑簇内邻居节点的距离和能 量信息，优化簇头节点的选择，使得w s n 簇内节点的能量消耗得以均衡，避免 了节点因能量快速耗尽而过早死亡，能有效提高大规模无线传感器网络的生存周 期；二，对w s n 覆盖问题进行了描述，针对其具有多目标优化的特点，在基于 g a f 的拓扑控制下，应用基于p a r e t o 排序的遗传算法来求解此问题，并考虑群 体多样性和p a r e t o 最优解的性能，采取一些措施对算法进行改进，最终实现使用 尽可能少数目的传感器节点以达到尽可能大的覆盖度的目标，均衡了w s n 能量 消耗，减少了无线信道中潜在的访问冲突；三，针对w s n 路由问题，结合w s n 层次型路由算法特点，充分考虑传感器节点剩余能量和传输能耗，设计了一种基 于蚁群优化的分层路由算法，使得w s n 簇头多跳路由性能得以改善，网络节点 能量消耗得以均衡。 关键词g计算智能遗传算法蚁群优化算法无线传感器网络优化 r 。- 。1 。1 。 海南大学硕士学位论文 a b s 仃a c t f 。1 。- _ _ _ - _ - - - - - - - - _ - _ - _ _ - _ _ - - _ _ _ - 一 a b s t r a c t a ss c i e n c ed e v e l o p sa n dt e c h n o l o g yp r o g r e s s e s ，m o r ea n dm o r e p r o b l e m sh a v e t h ef e a t u r eo fl a r g e - s c a l e ，c o m p l e x i t y , c o n s t r a i n t ，n o n l i n e a r i t ya n dn o n d e t e r m i n a c y o p t i m i z i n go f a uk i n d so fp r o c e s si np r o d u c t i o na n ds c i e n c ei sa l lu r g e n tp r o b l e mt h a t n e e d st ob es o l v e d ，h o w e v e r , t r a d i t i o n a lo p t i m i z a t i o nm e t h o d sa r ed i f f i c u l tt os o l v e t h e s ec o m p l i c a t e d l a r g e s c a l ep r o b l e m s a sar i s i n gt e c h n o l o g yo fo p t i m i z a t i o n ， c o m p u t a t i o n a li n t e l l i g e n c ep r o v i d ei n n o v a t i v et h o u g h ta n dm e a n st os o l v e t h e s e c o m p l i c a t e dp r o b l e m s t h ea l g o r i t h m sb a s e do nc o m p u t a t i o n a li n t e l l i g e n c ea r ee a s y t ou n d e r s t a n da n dr e a l i z e ，e s p e c i a l l y , m o s to fc o m p u t a t i o n a li n t e l l i g e n c em e t h o d s p o s s e s si n n e rp a r a l l e la n dd i s t r i b u t i o n ，a u t o o r g a n i z a t i o n ，a u t o a d a p t a t i o n ，w h i c h e f f e c t i v e l yp r o m o t et h ea p p l i c a t i o no fc o m p u t a t i o n a li n t e l l i g e n c ei nt h ed o m a i no f o p t i m i z a t i o n c o m p u t a t i o n a li n t e l l i g e n c ep l a ym o r ea n dm o r ei m p o r t a n tr o l e si n i m p r o v i n gt h ep r o d u c t i o ne f f i c i e n c y , r e d u c i n gc o n s u m i n ge n e r g ya n ds a v i n gr e s o u r c e t h i s p a p e r s t a r t sw i t ht w om e t h o d s a p p l i e dw i d e l y o fc o m p u t a t i o n a l i n t e l l i g e n c e ：e v o l u t i o n a r yc o m p u t i n ga n ds w a r mi n t e l l i g e n c e i tm a k e st h eg e n e t i c a l g o r i t h m s ( g a ) t h a ti s c l a s s i ci n e v o l u t i o n a r yc o m p u t i n ga n da n tc o l o n y o p t i m i z a t i o n ( a c o ) a l g o r i t h m st h a ti sr e p r e s e n t a t i v ei ns w a r mi n t e l l i g e n c ea si t s s t u d yf o u n d a t i o n i tp r e s e n t st h e o r ya n dc h a r a c t e r i s t i co ft h et w om e t h o d ss i m p l y , t h e n g i v e ss o m ei m p r o v e m e n t sa n dm a k e ss o m ec o m b i n a t i o n sw i t ho t h e rm e t h o d st os e e k t h ea p p l i c a t i o no fi n t e l l i g e n to p t i m i z a t i o n v i e wo ft h ef e a t u r et h a tw i r e l e s s i ne n g i n e e r i n gp r a c t i c e i na p p l i c a t i o n ，i n s e n s o r n e t w o r k s ( w s n ) m u s tp o s s e s s a u t o - o r g a n i z a t i o n , a u t o 。a d a p t a t i o na n dr o b u s t n e s s ，e s p e c i a l l y , e n e r g yo fw s ni sv e r y l i m i t e d ，t h i sp a p e rf u l l yu t i l i z e st h ea d v a n t a g e so fc o m p u t a t i o n a li n t e l l i g e n c e ，m a r r i e s t o g e t h e rb o t ht h er e s e a r c hf o c u s e s i tp r o p o s e ss o m em e t h o d sa n di d e a sf o ra p p l y i n g c o m p u t a t i o n a li n t e l l i g e n c et os o l v eo p t i m i z a t i o np r o b l e m so fw s n t h em a j o r c o n t e n t so ft h i sp a p e rc o u l db es u m m a r i z e da sf o l l o w s ： 1 t h ep r o b l e mo fc l u s t e r i n gi nw s ni sd e s c r i b e da n ds t u d i e di nt h i sp a p e r s y n t h e t i c a l l yc o n s i d e r i n gi n f o r m a t i o no fp o s i t i o na n de n e r g yo fn e i g h b o rn o d e si n c l u s t e r , g ai sa p p l i e dt oo p t i m i z et h e s e l e c t i o no fc l u s t e rh e a dt ob a l a n c et h e c o n s u m i n ge n e r g yo fn o d e si nc l u s t e r , a v o i dn o d e sd y i n ge a r l y , a n dp r o l o n gt h e n e t w o r kl i 危- t i m e u - ah i e r a r c h i c a lr o u t i n ga l g o r i t h mb a s e do na c o f i n a l l y , t h ea l g o r i t h mi m p r o v e s p e r f o r m a n c eo fm u l t i h o pr o u t i n go f c l u s t e rh e a d ，a n db a l a n c e st h ec o n s u m i n ge n e r g y o f n o d e si nw s n k e yw o r d s ：c o m p u t a t i o n a li n t e l l i g e n c e g e n e t i ca l g o r i t h m sa n tc o l o n y o p t i m i z a t i o n w i r e l e s ss e n s o rn e t w o r k s i i i 一 目录 1 1 2 2 3 4 5 2 1 遗传算法5 2 1 1 遗传算法的基本原理一5 2 1 2 遗传算法的构成要素6 2 1 3 遗传算法的数学机理9 2 1 4 遗传算法的特点1 l 2 2 蚁群优化算法12 2 2 1 基本蚁群优化算法的原理12 2 2 2 蚁群系统1 4 2 2 3 蚁群优化算法的特点l5 2 3 本章小结1 5 3 无线传感器网络简介1 6 3 1 无线传感器网络系统结构1 6 3 2 无线传感器网络的特征1 7 3 3 无线传感器网络的一些关键技术1 8 3 4 本章小结2 0 4 基于遗传算法的无线传感器网络分簇优化2 1 4 1 无线传感器网络分簇问题描述2 l 4 2 遗传算法优化分簇设计2 2 4 2 1 适应度函数设计2 2 4 2 2 编码与算子设计。2 3 4 2 3 算法实现过程2 3 4 3 算法仿真与结果分析2 4 4 4 本章小结2 6 5 基于多目标遗传算法的无线传感器网络覆盖问题优化2 7 5 1 无线传感器网络覆盖问题描述2 7 5 2 多目标优化的基本概念2 9 5 3 多目标遗传算法设计2 9 5 3 1 适应度值分配机制3 0 海南人学硕士学位论文目录 5 3 2 编码与选择算子的改进3 0 5 3 3 最优保存策略31 5 3 4 群体多样性3l 5 3 5 算法实现过程3 2 5 4 算法仿真与结果分析3 3 5 5 本章小结3 4 6 蚁群优化算法在无线传感器网络路由中的应用3 5 6 1 无线传感器网络路由问题描述3 5 6 2 基于蚁群优化的路由算法设计。3 6 6 3 算法仿真与结果分析3 9 6 4 本章小结4 0 7 总结与展望4 1 参考文献4 3 硕士期间发表的论文4 6 后记4 7 1 随着科学的发展和时代的进步，人们在工业生产和工程实践过程中遇到的问 题，越来越多地具有规模大、复杂性、约束性、非线性、不确定性等特点，在生 产实践、经济管理和科学研究的诸多领域有大量的问题都急需人们在庞大和复杂 空间寻找最优解或近似最优解。然而，鉴于实际工程优化问题复杂程度和规模的 不断提高，常规的优化算法面对这样的大型问题已无能为力，寻找适合于工程实 践需求的各种新型优化方法，一直是人们研究的热点和重要方向。计算智能作为 一种新兴的优化技术，很好地解决了常规优化算法遇到的难点，其算法相对简单， 易理解，易实现，更为重要的是，计算智能方法大都具有隐含并行性、自组织、 自适应等特点，有效地促进了其在生产各领域中的优化应用，对系统效率的提高、 能耗的降低、资源的合理利用及经济效益的提高具有重要的作用和研究意义。 随着当今信息技术的飞速发展，无线传感器网络( w i r e l e s ss e n s o rn e t w o r k , w s n ) 以其高度的学科交叉性和广泛的应用前景而成为新兴前沿热点研究领域， w s n 是由众多具有通信和计算能力的传感器节点，以多跳通信、自组织方式形 成的网络，在军事和民用方面都有广阔的应用领域。现在，互联网为人们日常生 活提供了快捷的通信平台，极大地方便了人们的信息交流；而w s n 拓展了人们 的信息获取能力，将客观的物理世界同互联网虚拟的信息世界融合在一起，使人 们直接感知客观物理世界，极大地扩展现有网络功能和人类认识世界的能力。 遗传算法是进化计算方法的代表，蚁群优化算法是近几年来发展起来的群体 智能计算方法的代表，本文对这两种算法进行研究和一些改进，并与其他算法进 行融合，寻找适合于工程实践需求的智能优化应用。同时，针对w s n 不同于其 他传统网络的特点w s n 必须有很强的自组织性、自适应性和鲁棒性且传感 器节点的能量资源都非常有限，充分利用计算智能方法特性，对w s n 中分簇优 化、覆盖问题和路由选择进行研究与探索，为以较小代价实现w s n 分簇、覆盖 及路由功能，提高系统整体能量效率，提供了新的方法与思路。 海南大学硕士学位论文 1 序言 1 2 计算智能的发展和现状 1 2 1 计算智能发展及现状 传统的人工智能是基于符号处理的，通常也称为符号智能，它以知识为基础， 偏重于逻辑推理，以顺序离散符号推理为特征，强调知识表示和推理及规则的形 成和表示。而随着科学的发展和时代的进步，人们在工业生产和工程实践中遇到 的问题，越来越多地具有规模大、复杂性、约束性、非线性、不确定性等特点， 传统的人工智能在感知、理解、学习、联想及形象思维等方面遇到了严重的困难。 人们逐渐认识到探索新方法来解决更加灵活、鲁棒性较强问题的必要性，智能模 拟算法开始兴起，并越来越多地得到研究者的重视。随着计算机容量和计算速度 的不断提高、大规模并行处理技术的产生和逐步成熟，使得智能模拟方法进入了 一个全新的发展阶段。由智能模拟方法组成的计算智能技术，更是引起了诸多领 域专家学者的关注。计算智能的兴起与发展，摆脱了传统人工智能所面临的困境， 已成为该领域的一个新的发展方向。 计算智台g ( c o m p u t a t i o n a li n t e l l i g e n c e ) 是一种借鉴和利用自然界中自然现象或 生物体的各种原理和机理而开发的并具有自适应环境能力的计算方法。计算智能 的方法是人们从生物进化的机理和一些自然现象中受到启发，提出的许多用以解 决复杂优化问题的新方法，具有分布、并行、仿生、自学习、自组织、自适应等 特性【l 羽，因其高效的优化性能、无需问题特殊信息等优点，在诸多领域得到了 成功应用。研究较多的计算智能技术主要包括进化计算( e v o l u t i o n a r y c o m p u t i n d 、人工神经网络( a r t i f i c i a ln e u r a ln e t w o r k ) 、模糊计算( f u z z y c o m p u t i n g ) 、人工免疫系统( a r t i f i c i a li m m u n es y s t e m ) 和群体智能( s w a r m i n t e l l i g e n c e ) 等。 目前计算智能算法的研究呈现出三大趋势 4 1 ：一是对经典智能算法的改进和 广泛应用，以及对其理论的深入、广泛研究；二是现代智能算法的发展，即不断 从生物智能和自然界中得到启示，探索思想更先进、功能更强大的新型智能算法， 拓宽其应用领域，并对其寻求理论基础；三是各种智能算法的相互融合，相互补 充，增强彼此的能力，从而获得更有力的表示和解决实际问题的能力。至今新的 智能算法不断涌现，计算智能应用领域越来越广，从工程优化、模式识别、智能 控制、经济管理到网络智能自动化等领域都取得了显著的研究成果与应用。 本文主要就进化计算中的遗传算法和群体智能中的蚁群优化算法进行研究 与应用。 海南大学硕士学位论文1 序言 1 2 2 进化计算与群体智能 ( 1 ) 进化计算 进化计算( e v o l u t i o n a r yc o m p u t i n g ) 是基于自然选择和自然遗传等生物进化 机制的一种模拟生物进化过程的智能搜索算法。它以生物界的“优胜劣态、适者 生存 作为算法的进化规则，结合达尔文的自然选择与孟德尔的遗传变异理论， 将生物进化中的四个基本形式：繁殖、变异、竞争和选择引入到算法过程中。进 化计算采用简单的编码技术，并对一组编码进行遗传操作和优胜劣汰的自然选 择，从而达到指导学习和确定搜索方向的目的。由于它采用基于种群的方式组织 启发式搜索，从而具有自学习、自组织、自适应等智能特征。 2 0 世纪6 0 _ _ 7 0 年代，进化计算作为一个新兴的交叉学科并未受到普遍的重 视。自从8 0 年代以来，人们逐渐认识到传统优化方法的困境，并且随着计算机 处理速度的提高和并行技术的发展以及进化算法本身的不断发展和成功应用，进 化计算在理论和实践两个方面都取得了长足的发展，现在已经成为人工智能领域 中的一个重要分支，在工程技术、社会经济和科学计算等诸多领域表现出了良好 的应用前景。 目前研究的进化计算技术主要有四种算法：遗传算法( g e n e t i ca l g o r i t h m ) 、 进化规划( e v o l u t i o n a r yp r o g r a m m i n g ) 、进化策略( e v o l u t i o n a r ys t r a t e g y ) 和遗传规划 ( g e n e t i cp r o g r a m m i n g ) 。前三种算法是彼此独立发展起来的，最后一种是在遗传 算法的基础上发展起来的一个分支【5 1 。遗传算法及其在优化问题中的应用是本文 的研究重点之一。 ( 2 ) 群体智能 自然界存在着很多让人叹为观止的生物群体智能现象，如蚁群、鱼群和鸟群 等。这些群居生物所体现的社会性和分布式智能实现模式给了人类很大的启发。 群体智能( s w a r mi n t e l l i g e n c e ) 是受社会性昆虫的启发，通过对其行为的模拟 形成一系列用于解决复杂问题的新方法。由单个复杂个体完成的任务可由大量简 单的个体组成的群体合作完成，而后者往往更具有灵活性、鲁棒性和经济上的优 势。群体智能利用群体优势，在没有集中控制和全局模型的前提下，依靠群体中 众多智能个体相互之间的简单合作进行分布式的问题求解，为寻找复杂问题解决 方案提供了新的思路。群体智能是指群体中众多简单个体通过相互之间的简单合 作表现出来的智能行为，“简单个体”是只具有简单能力或智能的单个个体，而 “简单合作”是指个体与其邻近个体进行某种简单的直接通讯或通过改变环境因 素间接与其他个体通讯，从而实现相互影响和协同合作 6 1 。 群体智能方法作为一种新兴的具有并行性、分布式和自适应性的随机启发式 搜索算法，自从2 0 世纪8 0 年代出现以来，引起了多个学科领域研究人员的关注， 海南大学硕士学位论文1 序言 已经成为人工智能以及经济、社会、生物等交叉学科的热点和前沿领域。目前群 体智能主要有两种算法模式，分别是蚁群优化( a n tc o l o n yo p t i m i z a t i o n ) 和粒子群 优化( p a r t i c l es w a r mo p t i m i z a t i o n ) 。其中，蚁群优化算法及其在优化问题中的应 用是本文的研究重点之一。 1 3 论文主要研究内容和结构安排 本文主要内容是研究进化计算和群体智能中具有代表性的算法一遗传算法 和蚁群优化算法的原理、特点及其实现，对算法进行改进，并与其他算法进行融 合，然后应用于求解w s n 中一些优化问题，并通过算法仿真进行结果分析。本 文余下章节的内容和结构安排如下： 第2 章，简单介绍了两种在以后章节涉及到的计算智能方法：遗传算法和蚁 群优化算法。 第3 章，简单介绍了w s n 的结构、特征和一些关键技术，为后面章节应用 计算智能方法求解w s n 具体优化问题作基础。 第4 章，针对现有w s n 分簇算法存在的问题，充分考虑簇内邻居节点的能 量和距离分布信息，应用遗传算法优化分簇过程，从而改善分簇算法性能，以均 衡簇内能量消耗，提高系统能量效率，最后给出算法仿真，并分析结果。 第5 章，对w s n 节点覆盖问题进行了描述，针对其具有多目标优化的特点， 应用基于p a r e t o 排序的遗传算法来求解此问题，并考虑群体多样性和p a r e t o 最 优解的性能，采取一些措施对算法进行改进，最后给出算法仿真，并分析结果。 第6 章，针对w s n 路由问题，结合w s n 层次型路由算法特点，充分考虑 传感器节点剩余能量和传输能耗，设计了一种基于蚁群优化的分层路由算法，改 善w s n 簇头多跳路由性能，均衡网络节点能量消耗，最后给出算法仿真，并分 析结果。 总结与展望部分，对本文所做的工作进行了总结，并给出了还需进一步完善 的工作和设想。 4 海南大学硕士学位论文 2 计算智能方法概述 2 计算智能方法概述 计算智能作为新兴的智能处理技术，是一种借鉴、模拟自然现象或生物体各 种原理及机理而开发的并具有自适应环境能力的计算方法，具有分布、并行、仿 生、自学习、自组织、自适应等优点，其在诸多领域都受到越来越多的关注。下 面，本章将本文所要研究与应用的两种计算智能方法作为代表，对遗传算法和蚁 群优化算法的相关理论及特点进行简要概括。 2 1 遗传算法 遗传算法起源于2 0 世纪6 0 年代，密歇根大学教授h o l l a n d 在研究自然和人 工系统的自适应行为的过程中，意识到用群体方法搜索以及选择、交换等操作策 略的重要性，并开创了基因操作，提出了重要的模式理论和二进制编码。7 0 年 代d ej o n g 基于遗传算法的思想在计算机上进行了大量的纯数值函数优化的实 验。8 0 年代g o l d b e r g 在一系列研究工作基础上进行归纳总结，形成了遗传算法 的基本框架。遗传算法是模拟生物在自然环境中遗传和进化过程而形成的一种自 适应全局优化概率搜索算法，进入9 0 年以来，以不确定性、非线性、时间不可 逆为内涵，遗传算法在许多领域得到了广泛应用。 2 1 1 遗传算法的基本原理 遗传算法是以自然选择和遗传变异理论为基础，将生物进化过程中适者生存 规则与群体内部染色体的随机信息交换机制相结合的搜索算法。在利用遗传算法 求解问题时，问题的每个可能解都被编码成一个染色体，即个体，若干个个体构 成了群体。遗传算法总是从一组随机产生的初始解( 群体) 开始搜索过程，根据 预定的目标函数对每个个体进行评价，给出一个适应度值。根据每个个体适应度 值，选择个体用来复制下一代。选择操作体现了适者生存理论，适应度值高的个 体被选择用来复制，而适应度值低的个体则被淘汰。被选择出来的个体经过交叉 和变异操作重组为新的一代，这一新群体由于继承了上一代的一些优良性状，因 而在性能上优于上一代，这样逐步朝着更优解的方向进化。因此遗传算法可以看 作是一个由初始解组成的群体逐步向最优解或近似最优解群体搜索的迭代过程。 图2 1 描述了遗传算法的流程。 海南大学硕士学位论文2 计算智能方法概述 2 1 2 遗传算法的构成要素 图2 1 遗传算法流程图 1 染色体编码方法 遗传算法操作的对象是表示个体的染色体，因此编码是设计遗传算法的一 个关键步骤，它是把一个问题的可行解从其解空间转换到遗传算法所能处理的搜 索空间的转换方法，它不仅决定个体染色体的排列方式，还决定个体从搜索空间 的基因型变换到解空间的表现型时的解码方法。对于一个具体的应用问题，如何 设计一种好的编码方案，不仅影响到具体的遗传算子运算方法，而且在很大程度 上影响着遗传进化操作的效率。d ej o n g 曾提出了两条操作性较强的实用编码原 则川。 原则一：应使用能易于产生与所求问题相关的且具有低阶、短定义长度模 式的编码方式。 原n - ：应使用能使问题得到自然表示或描述的具有最小编码字符集的编 码方案。 海南大学硕士学位论文2 计算智能方法概述 这两条原则只是给出了设计编码方法时的指导性意见，而在实际应用中， 还须对编码方法、遗传操作和解码方法等统一考虑。目前人们已经提出的多种不 同的编码方法可以分为三大类：二进制编码方法、浮点数编码方法、符号编码方 法。 ( 1 ) 二进制编码 二进制编码是最常见的编码方式，它所使用的编码符号集是由二进制符号 0 和l 组成的二值符号集 o ，1 ) ，它所构成的个体基因型是一个二进制编码符号 串。一般来说，二进制编码、解码操作简单易行，符合最小字符集编码原则，也 使得交叉、变异等遗传操作便于实现。 ( 2 ) 浮点数编码 对于高维、高精度要求的连续优化问题，使用二进制编码常常是不方便的。 二进制编码存在着连续函数离散化的映射误差，个体编码串长度较短时，可能达 不到精度要求，而个体编码串的长度较长是，虽能提高编码精度，但会使遗传算 法的搜索空间急剧扩大。同时，二进制编码不便于反映所求问题的特定知识，这 样也就不便于开发针对专门问题的遗传算子。针对二进制编码的这些缺点，人们 提出了浮点数编码方法。采用浮点数编码时，个体的每个基因值用某一范围内的 一个浮点数来表示，个体的编码长度等于其决策变量的个数。 ( 3 ) 符号编码 符号编码是指个体染色体编码串中的基因值取自一个无数值含义、而只有 代码含义的符号集。这个符号集可以是一个字母表，也可以是一个数字符号表， 还可以是一个代码表。 2 个体适应度 遗传算法求解问题时，首先要确定问题的目标函数和决策变量，然后使用 所求问题的目标函数就可得到下一步的有关搜索信息。确定一个适应度函数，将 个体目标函数值转换为个体适应度值，就是使用目标函数值的体现。遗传算法采 用适应度来度量群体中各个个体在迭代过程中有可能达到或接近于找到最优解 的优良程度。适应度值高的个体以较高的概率遗传到下一代，而适应度值较低的 个体遗传到下一代的概率就相对小一些。 个体适应度的确定通常反映了应用者对个体的评价标准和搜索原则，在进 化的不同阶段可以根据实际情况作出一些调整。例如，在算法初期，由于个体差 异比较明显，某些优秀个体会迅速在后代中积累起来，导致群体多样性的丧失， 这时就应压缩优秀个体的适应度，缩小差异；相反，到了后期，由于群体中个体 适应度差异不大，就要扩大差异。 3 遗传操作 海南大学硕士学位论文 2 计算智能方法概述 遗传操作是模拟生物基因的操作，它根据个体的适应度对其施加一定的操 作，从而实现优胜劣汰的进化过程。遗传操作包括三个基本遗传算子：选择、交 海南大学硕士学位论文2 计算智能方法概述 因座的其他等位基因来替换，从而产生一个新个体。 变异算子本身是一种局部随机搜索，能够避免由于选择和交叉算子而引起 的某些信息的永久性丢失，保证了遗传算法的有效性，同时使得算法能保持群体 的多样性，防止出现早熟现象。交叉算子与变异算子互相配合、共同完成对搜索 空间的全局搜索和局部搜索，从而使得遗传算法能够以良好的搜索性能完成最优 化问题的寻优过程。 最简单的变异算子是基本位变异，是指对个体编码串中以变异概率p m 随机 指定的某一位或某几位基因座上的基因值作变异运算。此外，还有均匀变异、边 界变异、高斯变异等变异算子。在变异算子中，变异概率p m 通常较小，一般取 值为0 0 0 1 4 ) 0 1 。 4 遗传算法的运行参数 在遗传算法运行过程中，存在着对其性能产生重大影响的一些参数，这些 参数在初始阶段或群体进化过程中需要合理的选择和控制，以使遗传算法以最佳 的搜索性能达到最优解。运行参数主要有个体编码串长度l 、群体大小m 、交叉 概率p c 、变异概率p m 、终止代数t 等。这些参数的选择对算法运行性能影响较 大，需要认真衡量【9 】。 ( 1 ) 编码串长度l ：l 的选择取决于特定问题解的精度和决策变量的个数 等。编码串越长，算法计算时间就会越多，为了提高计算效率，也可以使用可变 长度的编码或在当前所达到的较小可行域内重新编码。 ( 2 ) 群体大小m ：即群体中所含个体的数量。当m 取值较小时，可提高 遗传算法的运算速度，但却降低了群体的多样性，可能会引起算法的早熟现象； 而当m 取值较大时，又会降低遗传算法的运行效率，一般取为2 0 1 0 0 。 ( 3 ) 交叉概率p 。：交叉概率越高，群体中新结构的引入越快，但已获得的 优良基因结构的丢失速度也相应升高；交叉概率太低又会使新个体的产生速度过 慢。一般p 。取值为0 鲫9 。 ( 4 ) 变异概率p m ：变异操作是保持群体多样性的有效手段，然而变异概 率不能过高，如果p m 0 5 ，遗传算法就退化为随机搜索了。p m 通常取值为 0 0 0 1 - - 4 ) o l 。 ( 5 ) 终止代数t ：终止代数表示遗传算法运行到指定的进化代数t 之后就 停止运行，并将当前群体中的最佳个体作为所求问题的最优解输出。t 通常取值 为1 0 0 - - - 5 0 0 。 2 1 3 遗传算法的数学机理 虽然遗传算法的计算过程和形式简单，但是其运行机理非常复杂。随着遗传 海南大学硕士学位论文 2 计算智能方法概述 算法在复杂优化问题和实际工程设计中的应用，人们为了更好地分析算法的性 质，对算法的工作机理、数学基础等进行了深入的研究和认识。 1 模式定理【1 0 l 模式是在某些确定位置上取相同字符的字符串集合。例如，在二进制编码串 中，模式是基于三个字符集( 0 ，1 ，) 的字符串，符号叶七表任意字符，可为0 ， 也可为l ，模式幸幸0 0 描述了一个后两个位置都为0 的子集 o o o o ，0 1 0 0 ，1 0 0 0 ，1 1 0 0 。 因此，可以把模板看成一个相似性模板，而遗传算法的搜素过程实际上就是对相 似模板的搜索过程。在某个模式中，确定字符的个数称为模式的阶，其最左端确 定字符到最右端确定字符间的距离称为模式的定义距。例如模式0 1 1 0 0 * 的阶 是5 ，定义距是5 。引入下列符号： 胁某个模式； z ：第价字符串( 解) 的适应度； ( f ) ：第f 代群体的平均适应度； f ( h ，f ) ：模式臃第玳群体的平均适应度； ( 日，+ 1 ) ：由第f 代模式硼勺某个解往第f + l 代生成的后代数的期望值； n ( h ，t ) - 第玳属于模式肭解的个数； 6 ( 日) ：脚勺定义距； d ( 日) ：肭阶。 首先考虑选择算子的作用。在基本遗传算法中，选择是采用按适应度值大小 比例的原则，第i 个个体经选择算子的作用在下一代继续存在的个数的期望值为 刀( z 艺力，因 f ( h , t ) 2 高n1 - 1t ，一 i 一。 贝i j n ( h ，+ 1 ) = 以( 日，r ) 厂( 日，) ( ，) ( 2 1 ) ( 2 2 ) 上述等式表明，选择算子的作用将使适应度高于( 低于) 平均水平的模式在 代代相传时增大( 减小) 其容量。 接着考虑交叉算子的作用。若不进行交叉或虽交叉但交叉点落在模式最左、 右两端确定字符所处位置之外，该模式在下一代显然能保存下来。因此，模式日 在下一代得以继续存在的概率应满足： 只l p c 8 ( h ) ( l 1 ) ( 2 3 ) 于是，综合考虑选择和交叉的作用，有 一|一 n ( h ，r + 1 ) n ( h ，f ) f ( h ，f ) 【1 一只8 ( h ) ( l - 1 ) 厂o ) ( 2 4 ) 最后，考虑变异算子。当模式日中0 ( 日) 个确定位都存活时，模式日被保存 海南大学硕士学位论文2 计算智能方法概述 下来，其存活概率为： ( 1 一己) 伙片1 - o ( h ) 巴( 己 ，( f ，j = 0 l ，2 ，一， 一1 ) 表示城市间的边，d = 4 ，) 表示两城市 f ，j 间的欧氏距离，构造解的过程即搜索权重最小的h a m i l t o n i a n 圈。匆( f ) 表示t 时刻位于城市f 的蚂蚁个数，m = 6 f ( f ) 为蚂蚁的总数。乃( f ) 表示f 时刻边f ，歹上 的信息素量，r u ( o ) = ( 为常数) 。随着时间的推移，新的信息素加进来，旧的 信息素要挥发，夕【0 , 1 】表示信息素挥发系数。当所有蚂蚁完成一次周游后，各 边上的信息素调整规则如下： r u ( t + 刀) = ( 1 一, o ) r o ( t ) + ( 2 9 ) 一 肼 一 乃= 勺七 k = l ( 2 1 0 ) 其中，乃( ，) 表示本次周游中路径f ，上的信息素增量，初始时刻，( f ) = 0 。 0 表示第k 只蚂蚁在周游过程中释放在边i