（通信与信息系统专业论文）智能算法及其在网络优化中的应用研究.pdf

南京邮电大学博士研究生学位论文 摘要 工程领域中常见的多目标、多约束、非线性优化问题一般属于n p 完全问题，难以用 传统的最优化技术求解。例如：基于q o s 约束的组播路由问题，a dh o c 网络中基于拓扑 结构的功率控制问题等。近年来，一些模拟或揭示某些自然现象或过程的智能算法相继出 现( 如遗传算法、蚁群算法等) ，这些方法已在n p 完全问题的求解和实际工程应用中显 示出强大的生命力，吸引了众多研究者的目光，并取得了令人注目的研究成果。本论文从 算法的理论分析、并行实现、智能融合等方面进行了探讨，并将研究成果应用于网络优化 的实际问题中，解决基于多个不相关可加性度量的q o s 组播路由问题以及a dh o e 网络中 的功率控制问题。 本文对蚁群算法的参数设定进行了实验分析，指出在蚁群算法的求解过程中，参数 是影响算法求解性能和效率的关键因素，而且蚁群算法中各参数的作用是紧密耦合的，研 究其参数的最佳组合配置有着很重要的意义。基于此，本文提出将蚁群算法和遗传算法相 融合的改进策略，应用遗传算法对蚁群算法的四个控制参数( 口、夕、p 、q 0 ) 进行优化，为参 数的选择提供依据。然后将遗传蚁群算法用于求解包含延迟、延迟抖动、带宽、丢包率和 代价等约束条件在内的q o s 组播路由问题，取得了较好的应用效果。 随着计算机技术的发展，遗传算法越来越得到人们的重视，但遗传算法在实际应用中， 往往出现早熟收敛和收敛性能差等缺点。本文从算法的理论分析、并行实现、智能融合、 应用领域等方面对遗传算法提出改进策略。 在智能融合方面，本文将量子计算和遗传算法进行融合。将量子的态矢量引入遗传编 码，使融合算法比常规遗传算法拥有更好的多样性特征；自适应地进行量子旋转门的调整， 以加快收敛速度，避免早熟收敛，仿真实验验证了算法的有效性。在理论分析方面，本文 证明了量子遗传算法的收敛性。在应用领域方面，本文提出了一种基于多宇宙量子遗传算 法的q o s 组播路由算法，并且采用动态旋转角调整策略以提高算法的性能。仿真实验结果 v i 摘要 表明：采用动态旋转角调整策略的多宇宙量子遗传算法可以获得比采用遗传算法和采用静 态旋转角的量子遗传算法更好的效果，算法效率更高。在并行实现方面，通过对遗传算法 的四种并行模型进行深入研究，本文基于粗粒度模型提出了分布式并行量子遗传算法，并 将其应用于求解q o s 组播优化问题，取得了令人满意的优化效果。 a dh o e 网络中基于拓扑结构的功率控制是在考虑多个约束的条件下，保证全网连通并 且尽量降低节点的发射功率。本文设计了一个功率控制模型，该模型采用基于拓扑结构的 功率控制机制，跨越m a c 层、网络层和应用层。在应用层利用遗传算法来进行功率控制的 计算，求解多约束条件下的n p 完全问题，并通过网络层和m a c 层的接口对功率进行调节。 仿真实验结果表明基于遗传算法的a dh o e 功率控制可以节省节点的能量，提高网络的吞吐 量，延长网络的生存寿命。 关键词：智能算法，遗传算法，蚁群算法，量子计算，多宇宙量子遗传算法，并行量子遗 传算法，q o s 组播路由，a dh o e 网络，功率控制 a b s t r a c t t h ec o m m o ni s s u e sa b o u tm u l t i o b j e c t ，m u l t i c o n s t r a i n ta n dn o n l i n e a ro p t i m i z a t i o na r ea l l n pc o m p l e t ep r o b l e m ，t h e r e f o r e ，i ti s v e r yh a r dt or e s o l v et h e mb ym e a n so ft r a d i t i o n a l o p t i m i z a t i o n ，e g q o sm u l t i c a s tm u t i n ga n dp o w e rc o n t r o lo fa d h o cn e t w o r k ( b a s e do n t o p o l o g y ) p r o b l e m s r e c e n t l y , m a n yi n t e l l i g e n c ea l g o r i t h m s ，w h i c hs i m u l a t i n go rr e v e a l i n gs o m e n a t u r e - p h e n o m e n a , a r ep r e s e n t e do n eb yo n e t h e s ea l g o r i t h m sh a v es h o w nt h eg r e a tp o w e ro n s o l v i n gn pc o m p l e t ep r o b l e m sa n da c t u a le n g i n e e rp r o b l e m s t h i st h e s i sd i s c u s s e st h ep r o b l e m i i lt h ef i e l d so ft h e o r e t i c a l a n a l y s i s ，p a r a l l e li m p l e m e n t a t i o na n di n t e l l i g e n c e i n t e g r a t i o n m o r e o v e r , i ta p p l i e st h er e s e a r c hr e s u l ti n t ot h ep r o b l e mo fn e t w o r k o p t i m i z a t i o n ，r e s o l v i n gq o s m u l t i c a s tr o u t i n gp r o b l e m ，w h i c hb a s e do nm u l t i p l eu n c o r r e l a t e da d d i t i v i t y m e t r i c ，a n dp o w e r c o n t r o lp r o b l e mo f a d h o cn e t w o r k t h i st h e s i sm a k e sp r a c t i c a la n a l y s i s0 1 1t h ep a r a m e t e r s c o n f i g u r a t i o no fa c a a n dr e v e a l s t h a tt h e s ep a r a m e t e r sp l a yk e yr o l e so nt h ea l g o r i t h mp e r f o r m a n c ea n de f f i c i e n c y m o r e o v e r , t h e r ea r ec l o s ec o u p l i n gb e t w e e np a r a m e t e r so fa c a ，s os t u d y i n gt h eo p t i m u m g r o u po f p a r a m e t e r si sv e r yi m p o r t a n t t h e r e f o r e ，t h et h e s i sg i v e so n ei m p r o v e dp o l i c yw h i c hc o m b i n e s t h ea c aa n dg a ；a p p l i e sg at oo p t i m i z et h ef o u rp a r a m e t e r s 、p 、p 、q 0 ) o fa c a i ta l s o p r o v i d e st h eb a s eo fs e l e c t i o no fp a r a m e t e r s t h et h e s i sa p p l i e sg e n e t i ca n tc o l o n ya l g o r i t h mi n r e s o l v i n gp r o b l e mo fq o sm u l t i c a s tr o u t i n gw h i c ha r ec o n s t r a i n e db yd e l a y , j i t t e r , b a n d w i d t h ， p a c k e tl o s tr a t i oa n dc o s t s a t i s f i e dp e r f o r m a n c ei sa t t a i n e da st h er e s u l t w i t ht h ed e v e l o p m e n to fc o m p u t e rs c i e n c e ，g ab e c o m e sm o r ea n dm o r e i m p o r t a n t h o w e v e r , i nt h er e a lc i r c u m s t a n c e ，t h ep r e m a t u r ea n dl o wp e r f o r m a n c eo fc o n v e r g e n c ew i l l a l w a y se x i s t t h et h e s i sg i v e st h ei m p r o v e dp o l i c i e sf r o mt h o s ea s p e c t so ft h e o r e t i c a la n a l y s i s ， p a r a l l e li m p l e m e n t a t i o n ，i n t e l l i g e n c ei n t e g r a t i o na n dr e g i o n so fa p p l i c a t i o n ，e t c f o rt h ei n t e l l i g e n c ei n t e g r a t i o n ，t h et h e s i si n t e g r a t e st h eq u a n t u mc o m p u t a t i o na n dg a w h i l ei n t r o d u c i n gt h es t a t e v e c t o ro fq u a n t u mi n t ot h eg e n e t i cc o d i n g ，m a k i n gt h e i n t e g r a t i n g a l g o r i t h mo b t a i nb e t t e rc h a r a c t e r i s t i c so fv a r i e t y , a d j u s t i n gq u a n t u mr o t a t eg a t ea d a p t i v e l y , t h e - v i l l a b s t r a c t a l g o r i t h mp o s s e s s e sf a s t e rc o n v e r g e n c ea n da v o i d a n c eo fp r e m a t u r e t h r o u g ht h es i m u l a t i o n , a v a i l a b i l i t yo fi m p r o v e m e n ti sp r o v e d f o rt h e o r e t i ca n a l y s i s ，t h et h e s i sp r o v e st h ec o n v e r g e n c e o fq g a f o rr e g i o n so fa p p l i c a t i o n , t h et h e s i sr a i s e saq o sm u l t i e a s tr o u t i n ga l g o r i t h mb a s e do n t h em u l t i - u n i v e r s eq u a n t u mg e n e t i ca l g o r i t h m ，a n da d o p t st h ed y n a m i cr o t a t i o n a n g l e - a d j u s t m e n t p o l i c yt oi m p r o v et h ep e r f o r m a n c eo fa l g o r i t h m t h es i m u l a t i o nr e s u l ts h o w st h a tm q g a w h i c h a d o p t i n gd y n a m i cr o t a t i o n - a n g l e a d j u s t m e n tp o l i c yg e t sb e t t e rp e r f o r m a n c et h a ng a a n dq g a w h i c ha d o p t i n gs t a t i cr o t a t i o n a n g l e a d j u s t m e n tp o l i c y f o rt h ec a s eo fp a r a l l e li m p l e m e n t a t i o n ， t h r o u g hs t u d y i n gt h ef o u rk i n d so fp a r a l l e lm o d e l si n - d e p t h ，t h et h e s i sp u t sf o r w a r dd i s t r i b u t e d p a r a l l e lq g a a n da p p l i e si ti ns o l v i n gt h ep r o b l e mo fq o sm u l t i c a s to p t i m u m ，a n ds a t i s f i e d o p t i m u mr e s u l ti so b t a i n e d t h ep o w e rc o n t r o l ，b a s e do nt h et o p o l o g y , o ft h ea dh o cn e t w o r ka s s u r e sa l ln o t e s c o n n e c t e da n dr e d u c e st r a n s m i s s i o np o w e ra tb e s ti nt h ec i r c u m s t a n c eo fm u l t i - c o n s t r a i n t t h e t h e s i sd e s i g n sap o w e rc o n t r o lm o d e lw h i c ha d o p t i n gp o w e rc o n t r o lm e c h a n i s mb a s e do n t o p o l o g ys t r u c t u r e ，s p a n n i n ga c r o s sm a cl a y e r , n e t w o r kl a y e ra n da p p l i c a t i o nl a y e r i nt h e a p p l i c a t i o nl a y e r , i ta p p l i e sg a t om a k et h ec o m p u t a t i o no fp o w e r - c o n t r o l ，s o l v e sn p c o m p l e t e p r o b l e mi nt h ec a s eo fm u l t i c o n s t r a i n t ，a n da d j u s t st h ep o w e rt h r o u g ht h ei n t e r f a c e so fn e t w o r k a n dm a cl a y e r t h es i m u l a t i n gr e s u l ti n d i c a t e st h a tt h ea dh o c sp o w e r - c o n t r o l ，b a s e do ng a ， n o to n l ys a v e st h ep o w e ro fn o d e s ，i n c r e a s e st h r o u g h p u to ft h en e t w o r k ，b u ta l s om a k e st h e t i m et ol i v eo ft h en e t w o r kl o n g e r k e yw o r d s ：i n t e l l i g e n ta l g o r i t h m s ，g e n e t i ca l g o r i t h m s ( g a ) ，a n tc o l o n ya l g o r i t h m s ( a c a ) ， q u a n t u mc o m p u t a t i o n ，m u l t i u n i v e r s eq u a n t u mg e n e t i ca l g o r i t h m ( m q g a ) ，p a r a l l e lq u a n t u m g e n e t i ca l g o r i t h m ( p q g a ) ，q o sm u l t i e a s tr o u t i n g ，a dh o cn e t w o r k s ，p o w e rc o n t r 0 1 i x 南京邮电大学博士研究生学位论文 缩略词 缩略词英文全称译文 a c aa n tc o l o n ya l g o r i t h m s蚁群算法 a t m a s y n c h r o n o u st r a n s f e rm o d e异步传输模式 c b rc o n s t a n tb i tr a t e恒定比特率 c b tc o r eb a s e dt r e e有核树 c o m p l e m e n t a r ym e t a l - o x i d e c m o s互补金属氧化物半导体 s e m i c o n d u c t o r c t sc l e a rt os e n d确认发送 g ag e n e t i ca l g o r i t h m s遗传算法 g a c ag e n e t i ca n tc o l o n ya l g o r i t h m遗传蚁群算法 g b a s g r a p h b a s e da n ts y s t e m基于图的蚂蚁系统 g p sg l o b a lp o s i t i o ns y s t e m ，全球定位系统 g q a g e n e t i cq u a n t u ma l g o r i t h m遗传量子算法 h g a h y b r i dg e n e t i ca l g o r i t h m混合遗传算法 i c a i n d e p e n d e n tc o m p o n e n ta n a l y s i s独立构成分析 i p i n t e r n e tp r o t o c o l网际协议或互联网协议 l e a rl o c a le n e r g y a w a r er o u t i n g本地能量感知路由 m a cm e d i u ma c c e s sc o n t r o l媒体访问控制 m m a sm a x m i na n ts y s t e m最大最小蚂蚁系统 n pn o n d e t e r m i n i s t i cp o l y n o m i a lt i m e 非确定性的多项式时间 n sn e t w o r ks i m u l a t i o n 网络仿真 p a np e r s o n a la r e an e t w o r k 个人局域网 p a r op o w e r - a w a r er o u t i n go p t i m i z a t i o n能量感知路由优化 p c d cp o w e rc o n t r o l l e dd h a lc h a n n e l功率控制双通道 p c mp u l s ec o d em o d u l e 脉码调制 1 0 8 缩略词 q u a n t u mc o m p u t a t i o na n dg e n e t i c量子计算和遗传算法的 q c o a a l g o r i t h m融合 q g aq u a n t u mg e n e t i ca l g o r i t h m量子遗传算法 q o sq u a l i t yo fs e r v i c e服务质量 i 心tr e n d e z v o u sp o i n tt r e e 共享树 i 汀s r e q u e s tt os e n d请求发送 s p ts h o r t e s tp a t ht r e e最短路径树 t d dt i m ed u p l e x i n g时分双工 t it a c t i c a li n t e m e t战术互联网 t s p t r a v e l i n gs a l e s m a np r o b l e m旅行商问题 w l a nw i r e l e s sl o c a la r e an e t w o r k无线局域网 w n i c w i r e l e s sn e t w o r ki n t e r f a c ec a r d 无线网络接口卡 ：“ 1 0 9 南京邮电大学博士研究生学位论文 图表清单 表1 1a dh o e 网络中节能问题的研究2 l 图2 1 实验网络3l 图2 - 2 实验最优路由3 2 表2 1( 1 ，3 ) 最佳路由结果3 2 表2 - 2 不同参数取值情况下的实验结果3 2 表3 15 个t s p 问题求解结果的比较3 8 图3 1g a c a 找到的最优路径3 9 图3 2q 蛇a 一次随机迭代求得的最好结果3 9 图3 3g a c a 一次随机迭代求得的最好结果3 9 图4 18 节点网络拓扑图4 5 图4 2 最佳组播树结果一4 5 图4 - 3 遗传算法在搜索中组播树的延迟、延迟抖动、代价随代数变化曲线4 6 图4 4 遗传蚁群算法在搜索中组播树的延迟、延迟抖动、代价随代数变化曲线一4 6 图4 5 由最优参数组合指导下的蚁群算法在搜索中组播树的延迟、延迟抖动、代价随代数 变化曲线4 7 表5 1 旋转门调整策略5 0 图5 1v e l n s 的网络结构5 1 表5 - 2 网络节点间的通信量和候选路由矩阵5 2 表5 3 不同方法实验结果比较5 3 图5 2 不同算法成功率比较5 4 图5 3 第一次找到最优解代数的比较5 4 图7 15 0 节点的随机生成网络拓扑图6 6 图7 2 动态旋转角m q g a 和静态旋转角q g a 结果比较6 6 图7 3 动态旋转角m q g a 和g a 结果比较6 7 图表清单 图8 1 圆锥形连接拓扑6 9 图8 2 粗粒度主从式模型7 l 图8 3 分布式并行量子遗传算法结构图7 4 图8 - 42 0 节点实验网络7 6 图8 5 最优组播树结果7 7 图8 - 62 0 点网络q g a 和p q g a 代价随代数变化曲线7 7 表8 1q g a 和p q g a 的运行结果比较7 7 表9 1 最优解的性能参数8 4 图9 1 最优解所对应的拓扑结构8 5 表9 2 算法运行结果的统计8 5 图9 2 传统的分层模型8 6 图9 3 自适应跨层模型8 6 ，j 图9 4 功率控制模型8 7 图9 5 全连通网络8 9 图9 - 6 网络中出现了孤立节点：8 9 图9 7 网络中出现了单向链路8 9 套 图9 8 应用层的相关模块9 3 图9 - 9 能量消耗的比较。9 5 图9 1 0 吞吐量的比较9 5 图9 1 1 丢包率的比较：9 6 图9 1 2 生存时间9 7 表9 3 统计结果比较9 7 表9 - 4 遗传算法运行结果9 7 图9 1 32 0 节点2 m s 时吞吐量9 8 图9 1 42 0 节点2 m s 时能耗均衡性。9 8 图9 1 53 0 节点2 m s 时吞吐量一9 9 图9 1 63 0 节点2 m s 时能耗均衡性9 9 图9 1 74 0 节点2 m s 时吞吐量1 0 0 图9 1 84 0 节点2 m s 时能耗均衡性1 0 0 1 1 1 南京邮电大学博士研究生学位论文 表9 5 吞吐量比较10 1 表9 - 6 有效能耗利用率比较10 1 1 1 2 南京邮电大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不 包含为获得南京邮电大学或其它教育机构的学位或证书而使用过的 材料。与我一同工作的同志对本研究所做的任何贡献均己在论文中 作了明确的说明并表示了谢意。 研究生签名：盘查壑舀日期争型 南京邮电大学学位论文使用授权声明 南京邮电大学、中国科学技术信息研究所、国家图书馆有权保 留本人所送交学位论文的复印件和电子文档，可以采用影印、缩印或 其他复制手段保存论文。本人电子文档的内容和纸质论文的内容相 一致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布 ( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权南 京邮电大学研究生部办理。 研究生签名：巡导师签名恤日期：之山f 第一章绪论 1 1 课题来源和意义 第一章绪论 优化技术是一种以数学为基础，求解各种工程问题优化解的应用技术。它是从6 0 年 代初期开始发展起来的- - i 丁新的学科，是最优化方法和计算机技术在工程领域应用的结 果。工程应用中常见的多目标、多约束、非线性优化问题一般属于n p 完全问题，即算法 的计算时间是呈指数增长的，这一论断确立了此类问题的理论深度。对于n p 完全问题目 前在数学上还没有一个通用的算法能够很好地解决。鉴于实际工程问题的复杂性、约束性、 非线性等特点，寻求一种具有智能特征的求解算法是研究的目标和方向。 2 0 世纪8 0 年代以来，通过模拟或揭示某些自然现象或过程，提出了一类解决复杂优 化问题的新算法，如遗传算法、模拟退火算法、人工神经网络，禁忌搜索等，特别近年来 蚁群算法、量子计算等相继出现，这些方法为解决复杂问题提供了新的思路和手段。由于 这些算法的独特机制，伴随着计算机技术的发展，在一些工程领域当中得到了成功应用， 成为求解n p 完全问题的主要方法，引起了国内外学者的广泛重视，并成为目前的研究热 点。通常将此类算法称为智能算法，或称为启发式算法。由于这些算法简单和有效，而且 具有某种智能，因而成为科学计算和人类之间的桥梁。 典型的几种智能算法介绍如下： ( 1 ) 遗传算法：是根据生物演化，模拟演化过程中基因染色体的选择、交叉和变异 得到的算法。在进化过程中，较好的个体有较大的生存概率。 ( 2 ) 模拟退火：是模拟统计物理中固体物质的结晶过程。在退火的过程中，如果搜 索到好的解接受；否则，以一定的概率接受不好的解( 即实现多样化或变异的思想) ，达 到跳出局部最优解的目的。 ( 3 ) 神经网络：模拟大脑神经处理的过程，通过各个神经元的竞争和协作，实现选 择和变异的过程。 ( 4 ) 禁忌搜索：模拟人的经验，通过禁忌表记忆最近搜索过程中的历史信息，禁忌 某些解，以避免走回头路，达到跳出局部最优解的目的。 南京邮电大学博士研究生学位论文 ( 5 ) 蚂蚁算法：模拟蚂蚁的行为，学习蚂蚁的协作方式。 以上算法有一个共同的特点：从随机的可行初始解出发，采用迭代改进的策略，去逼 近问题的最优解。 目前智能算法存在的问题： ( 1 ) 智能算法缺乏统一、完整的理论体系。 ( 2 ) 智能算法都不可避免的遇到局部最优的问题。 ( 3 ) 智能算法都有各自的特点，如何来进行融合。 ( 4 ) 智能算法中的参数对算法的效果起着很重要的作用，如何有效地设置参数。 ( 5 ) 智能算法缺乏有效的迭代终止条件。 q o s 组播路由技术是网络多媒体信息传输的关键技术之一，其目的是在网络中寻找一 条组播路由，满足用户对线路带宽、延迟、代价等要求，即向用户提供端到端的服务质量 保证。基于多个不相关可加性度量的q o s 组播路由问题已证明是n p 完全问题l ij ，目前一 般采用智能算法进行求解。 a dh o c 网络是一种特殊的无线通信网络，在很多a dh o c 网络的应用场合，由于重量和 体积的限制，网络节点采用可充电或不可充电电池进行供电，容量受限且充电不易。在当 前电池技术发展缺乏重大突破的情况下，节省能量开销对推广a dh o e 网络的应用具有重要 意义。早期业界研究的重点在终端硬件方面，已经取得了很多成果并应用到终端节点的生 产制造中。在软件方面的研究，近年来集中于如何在协议栈各层设计专门的节能协议来降 低节点的能耗，主要包括两类：一类是无线网卡动态关闭机制，另一类是功率控制机制m j 。 a dh o c 网络中的功率控制是指在不牺牲系统性能的前提下，尽可能地降低节点的发射 功率，从而降低节点的能耗，提高网络的生存时间和系统的能量效率。有效的功率控制策 略可以减少网络中节点不必要的能量消耗，延长网络的生存周期。例如：基于拓扑结构的 功率控制是在考虑多个目标的条件下，保证全网连通并尽量降低节点的发射功率，已被证 明属于典型的n p 完全问题【3 1 。 本课题“智能算法在网络优化中若干问题的研究”主要来源于以下项目： ( 1 ) 国家高技术研究发展计划( 8 6 3 计划) 专题课题项目“基于a g e n t 的面向应用的无 线传感器网络中间件技术 ( 2 0 0 6 a a o l z 2 1 9 ) ( 2 ) 江苏省高技术计划项目“无线传感器网络中间件与平台技术研究”( b g 2 0 0 5 0 3 8 ) 第一章绪论 ( 3 ) 江苏省高校自然科学研究计划项目“基于智能技术的分布式实时入侵检测关键技术 研究 ( 0 4 k j b 5 2 0 0 9 5 ) 1 2 遗传算法 遗传算法1 4 ( g e n e t i c a l g o r i t h m s ，g a ) 由美国m i c h i g a n 大学j h o l l a n d 教授于1 9 7 5 年 首次提出，它是借鉴生物进化规律( 适者生存、优胜劣汰) 而产生的一种高度并行、随机 和自适应的优化算法。其主要特点是直接对结构对象进行操作，不存在求导和函数连续性 的限定；具有内在的隐并行性和全局解空间搜索能力：采用概率化的寻优方法，能自动获 取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。目前，g a 在机 器学习、模式识别、图像处理、神经网络、优化控制、组合优化、v l s i 设计等领域得到了 成功地应用。 遗传算法将问题的求解，表示成“染色体”的进化过程，通过“染色体 选择、交叉、 变异等遗传操作不断进化，直到满足一定性能指标和收敛条件终止，从而求得问题的解。 1 2 1 遗传算法的基本流程 遗传算法不是简单的随机比较搜索，是具有“生成+ 检测的迭代过程的搜索算法。 遗传算法的工作步骤是： ( 1 ) 随机产生一组初始个体构成初始群体，并计算个体的适应度。 ( 2 ) 根据适应度值大小以一定方式执行选择操作。 ( 3 ) 按交叉概率p c 执行交叉操作。 ( 4 ) 按变异概率p m 执行变异操作。 ( 5 ) 判断算法收敛准则是否满足。若满足则终止；否则返回( 2 ) 。 适应度值是对染色体( 个体) 进行评价的指标，它与个体的目标值存在某种对应关系： 选择操作是将已有的优良个体复制后加入新群体中，删除劣质个体，提高了种群的平均适 应度值：交叉操作通过交换两父代个体的部分信息构成子代个体，有助于产生优良个体； 变异操作通过随机改变个体中某些基因而产生新个体，有助于增加种群的多样性，避免未 成熟收敛。 遗传算法的流程图描述，如图1 1 所示。 南京邮电大学博士研究生学位论文 图l lg a 沉程图 由图1 1 可知，遗传算法是一种以群体中的所有个体为对象的群体型操作，选择、交叉、 变异是遗传算法的3 个主要操作算子。在应用遗传算法时，需要确定以下要素：1 ) 染色体 的编码，如何由染色体的编码体现问题的解；2 ) 初始群体的设定：3 ) 适应度函数的设计； 4 ) 确定遗传算子，即如何进行选择、交叉、变异等遗传操作；5 ) 控制参数设定，包括： 群体规模、终止进化代数、交叉概率和变异概率。 1 2 2 遗传算法的运行机理 关于遗传算法运行机理的解释有两类：一是由j h o l l a n d 教授创立的传统的模式理论； 二是1 9 9 0 年以后发展起来的有限状态马尔可夫链模型。 ( 1 ) 模式理论【4 卅 1 9 7 5 年，j h o l l a n d 提出了模式定理和隐并行性定理。1 9 8 9 年，又提出了积木块假说。 模式定理( s c h e m at h e o r e m ) 遗传算法在进化过程中，个体的适应度越高，其生存的机会越多，而通过遗传算法的 第一苹绪论 主要操作一交叉操作，在子代中将产生适应度更高的个体。可以发现，由父个体通过交 叉操作产生的子个体，在结构上其染色体与父个体之间存在一定的相似性，而适应度高的 父子个体之间相似的结构，也对应高的适应度值。这些相似的字符串模板，称为模式 ( s c h e m a ) 。 定义1 1 基于三值字符集 o ，1 ， 所产生的能描述具有某些结构相似性的0 ，1 字符串集 的字符串称为模式。 例如对长度为5 的字符串，模式0 1 1 表示字符串集 0 1 0 0 1 ，0 1 0 11 ，0 11 0 1 ，0 111l 。 一个长为z 的串中隐含的模式个数为2 。，而长度相同的不同模式所匹配的串( 称为模式 的样本) 个数不一定相同。例如模式o l l 毒l 的样本个数为2 个，而o + 幸 l 的样本个数为2 7 = 8 。 为反映这种确定性的差异，引入模式阶的概念。 定义1 2 出现在模式中取确定值的位置的数目称为该模式的模式阶，记作o ( h ) ，如 o ( 0 1 1 ) = 3 。 但是模式阶并不能反映模式的所有性质，在交叉操作中，模式被破坏的概率与模式的 确定位置之间的距离有关。 定义1 3 模式中第一个取确定值的位置与最后一个取确定值位置之间的距离称为该 模式的对应长度，记作万( 日) ，如8 ( o l 幸1 ) = 4 。 下面讨论遗传过程中的模式数目。 考虑选择过程。假设在第t 代，群体p ( t ) 中模式h 所能匹配的样本数为m ( h ，) 。选择操 作时以适应度比例的方法进行，即一个串的选择概率为： 只= z z ， 其喊是个体f 的适应度a 则模式日在第t + l 代中的样本数m ( h ，r + 1 ) 为： m ( h ，r + 1 ) = m ( h ，) 以f ( h ) z = m ( h ，t ) f ( h ) f ( 1 - 1 ) 式中，f ( h ) 是模式日中所有样本的平均适应度，群体平均适应度记为f 。由式( 1 一1 ) 可见，模式样本数的增加或减少依赖于模式的平均适应度与群体平均适应度之比，平均适 应度高于群体平均适应度的模式将在子代得以增长，而平均适应度低于群体平均适应度的 模式在子代将减少，符合“优胜劣汰”原则。 考虑单点交叉操作对于模式生存的影响。假设染色体串长为，模式日的对应长度为 5 南京邮电大学博士研究生学位论文 8 ( h ) ，只有交叉点落在定义长度之外的模式才能生存，日的生存概率为 只- 1 - 8 ( h ) ( 1 - 1 ) ，若交叉概率为只，模式h 的生存概率为： 只= l 一只8 ( n ) ( t 一1 )( 1 - 2 ) 如果发生交叉的两个个体都与模式匹配，那么模式并没有被破坏。从而式( 1 2 ) 给出的 是一个下界，即： 只l 一只3 ( h ) ( 1 一1 ) ( 1 3 ) 由式( 1 3 ) 可见，模式的定义长度对模式的存亡有很大影响。6 ( h ) 越大，模式存活的可 能性越小。 考虑变异操作。模式h 在变异算子作用下，若要不受破坏，其中的所有确定的位置都 必须保持不变。因此，模式日保持不变的概率为： ( 1 一己) d l d ( 日) 已 ( 1 4 ) 结合式( 1 1 ) 、式( 1 - 3 ) 和式( 1 4 ) ，在遗传操作下，模式日在子代中的样本数为： m ( n ，f d r l ) m ( n ，r ) f ( h ) 九1 一e 6 ( h ) ( 1 一1 ) 一o ( h ) 己】( 1 - 5 ) 由式( 1 5 ) 可以给出以下的模式定理。 定理1 1 ( 模式定理) 在遗传算子选择、交叉和变异的作用下，阶次低、定义长度短 且平均适应度高于群体平均适应度的模式在子代中将以指数级递增。 积木块假说 定义1 4 具有低阶、短定义长度且高适应度的模式称作积木块。 假说1 1 ( 积木块假说) 低阶、短定义长度、高平均适应度的模式( 积木块) 在遗传 算子的作用下，相互结合，能生成高阶、长定义长度、平均适应度高的模式。 模式定理保证了较优的模式样本数呈指数级增长，说明遗传算法存在着寻找到全局最 优解的可能性。而积木块假说指出遗传算法具备寻找到全局最优解的能力。 隐并行性定理( i m p l i c i tp a r a l l e l i s m ) 遗传算法实质是模式的运算。隐并行性定理讨论的是遗传算法中能以指数级增长的模 式个数的下界。 定理1 2 ( 隐并行性定理) 设g 是一小正数，l c ( t 1 ) + l ，群体规模疗= 2 ，j 2 ，则 第一章绪论 遗传算法一次处理的存活概率不小于l s 且定义