（通信与信息系统专业论文）遗传算法及其在通信中的应用.pdf

山东大学硕士学位论文 中文摘要 遗传算法( g a ，g e n e t i ca l g o r i t h m ) 是一种基于生物界演化的随机搜索技术。近 年来，遗传算法广泛而深入地应用于通信中的各种联合优化问题并已经有了很多 成功的实例。 盲均衡技术能够仅利用接收信号的统计特性对信道特性进行均衡，克服了传 统自适应均衡技术需要训练序列、降低系统有效信息传输率的缺陷，成为目前的 研究热点。本文简单介绍了通信中的盲均衡技术，并针对一个简单的信道模型给 出了基于遗传算法的盲均衡算法。仿真结果表明，多次迭代的盲均衡的均值能够 很好地代表未知信道的性能。 为了更好地利用o f d m 系统的性能，需要对资源分配进行设计。通过对功率、 带宽、调制方式等的资源控制可以得到比较好的性能。o f d m 系统中存在着两种 资源分配方案：动态和静态。本文采用遗传算法对一种动态资源分配方案进行了 优化，采用自适应的功率分配的方法，在功率约束的条件下最大化系统容量，并 保证了用户之间的公平性。 随着无线应用的发展，传统的o s l 分层结构无法适应无线网络环境，人们提出 了跨层设计，其主要内容就是通过在协议的各层之间传递特定的信息，使协议栈 能够根据无线环境的变化来实现对资源的自适应优化配置，从而有效利用无线网 络资源，提高系统性能。本文提出了针对o f d m a ，m i s o 系统的跨层设计结构并得 到了最优解。因为问题的计算复杂度很高，我们采用遗传算法来进行求解，进而 获得这种跨层设计较好的性能。实验结果表明，采用遗传算法进行用户的选择可 以比传统的方法得到更好的性能。 关键词：遗传算法，资源分配，跨层设计，o f d m a m i s o 系统 山东大学硕士学位论文 a b s t r a c t g e n e t i ca l g o r i t h m sa r ep r o b a b i l i s t i cs e a r c ht e c h n i q u e sb a s e do nt h ep r i n c i p l e so f b i o l o g i c a le v o l u t i o n r e c e n t l y , g e n e t i ca l g o r i t h m sa r ed e e p l ys t u d i e da n dw i d e l yu s e di n c o m b i n a t o r i a lo p t i m i z a t i o np r o b l e m sa n dal o to fs u c c e s s f u la p p l i c a t i o ni n s t a n c e sa n d b l i n de q u a l i z a t i o ni sa na d a p t i v ee q u a l i z a t i o nt e c h n i q u e ，w h i c hc a ne q u a l i z et h e p r o p e r t i e so ft h ec h a n n e lj u s tu s i n gt h es t a t i s t i cp r o p e r t i e so ft h er e c e i v e ds i g n a la n d o v e r c o m et h ed i s a d v a n t a g e so fc o n v e n t i o n a la d a p t i v ee q u a l i z a t i o nt e c h n i q u e sw h i c h r e q u i r eat r a i n i n gs e q u e n c ea n dr e d u c ee f f e c t i v ei n f o r m a t i o n r a t ei ns y s t e mt r a n s m i s s i o n t h i s p a p e rg i v e s ar e v i e wo fb l i n de q u a l i z a t i o n ，a n db u i l d s a s i m p l e s i n g l e i n p u t - m u l t i p l e - o u t p u tm o d e l w ep r o p o s eab l i n de q u a l i z a t i o na l g o r i t h mb a s e d o ng e n e t i ca l g o r i t h m t h es i m u l a t i o n ss h o wt h a tw ec a nh a v eb e t t e rp e r f o r m a n c e s i no r d e rt of u l l ye x p l o i tt h ea d v a n t a g e so fo f d mi nc e l l u l a rs y s t e m s ，r e s o u r c e a l l o c a t i o nt e c h n i q u e sn e e dt ob ed e v i s e d ，w h i c he f f i c i e n t l yu s et h er e s o u r c e ss u c ha s b a n d w i d t h ，p o w e r , a n dm o d u l a t i o nt oi n c r e a s et h es p e c t r a le f f i c i e n c yo ft h es y s t e m t h e r ea r et w ok i n d so fr e s o u r c ea l l o c a t i o ns c h e m e se x i s t i n gi nc u r r e n to f d ms y s t e m ： s t a t i ca n dd y n a m i cr e s o u r c ea l l o c a t i o ns c h e m e s t h i sp a p e rf o r m u l a t e sa l lo p t i m i z a t i o n p r o b l e ma n du s eg at om a x i m i z et h es u mc a p a c i t yo fo f d ms y s t e mw i t ht h et o t a l p o w e rc o n s t r a i n t s t r a d i t i o n a lo s ia r c h i t e c t u r ei sn o ts u i t a b l et ow i r e l e s sn e t w o r kw i t h t h e d e v e l o p m e n to fw i r e l e s sa p p l i c a t i o n s c r o s s - l a y e rd e s i g ni sp r o p o s e d ，i t sm a i nc o n t e n t i st h a tt h ep r o t o c o ls t a c kc a nr e a l i z es e l f - a d a p t i v eo p t i m i z a t i o no fr e s o u r c e sa c c o r d i n gt o t h ec h a n g e so fw i r e l e s se n v i r o n m e n tt h r o u g ht r a n s m i t t i n gs p e c i f i ci n f o r m a t i o nb e t w e e n t h el a y e r so fp r o t o c o ls t a c k ，i no r d e rt ou t i l i z ew i r e l e s sn e t w o r kr e s o u r c e se f f e c t i v e l y a n di m p r o v et h ep e r f o r m a n c eo ft h es y s t e m t h eo p t i m a lc r o s s l a y e rs c h e d u l i n g a l g o r i t h mf o ro f d m a m i s oi sf o r m u l a t e d ，a n dt h eo p t i m a ls o l u t i o ni s o b t a i n e d b e c a u s eo ft h eh i g hc o m p u t a t i o n a lc o m p l e x i t yi n v o l v e d ，w eu s eg e n e t i ca l g o r i t h m st o o b t a i nt h em u l t i u s e rp e r f o r m a n c e t h er e s u l t ss h o wt h a tw ec a nh a v eb e t t e r i l 山东大学硕士学位论文 p e r f o r m a n c eb ym u l t i u s e rs e l e c t i o nb a s e do ng e n e t i ca l g o r i t h mt h a nt r a d i t i o n a lm e t h o d k e y w o r d s ：g e n e t i c a l g o r i t h m ； r e s o u r c e a l l o c a t i o n ； c r o s s l a y e r d e s i g n ； o f d m a m i s os y s t e m i i i 山东大学硕士学位论文 g a h g a a g a p g a i s i o f d m i c i c p s l n r q o s m p f a w g n o s i a r q a m c c s i b e r a p a o f d m a m i s o 符号说明 g e n e t i ca l g o r i t h m 遗传算法 h y b r i dg e n e t i ca l g o r i t h m 混合遗传算法 a d a p t i v eg e n e t i ca l g o r i t h m自适应遗传算法 p a r a l l e lg e n e t i ca l g o r i t h m并行遗传算法 in t e r - s y m b o lin t e r f e r e n c e 符号间干扰 o r t h o g o n a lf r e q u e n c yd i v i s i o nm u l t i p l e x i n g正交频分复用 i n t e r - c h a n n e li n t e r f e r e n c e信道间干扰 c y c l i cp r e f i x循环前缀 s i g n a lt oi n t e r f e r e n c ep l u sn o i s er a t i o 信号干扰噪声比 q u a l i t yo fs e r v i c e服务质量 m o d i f i e dp r o p o r t i o n a lf a i rs c h e d u l i n g 比例公平调度 a d d i t i v ew h i t eg a u s s i a nn o i s e 加性高斯白噪声 o p e ns y s t e mi n t e r c o n n e c t i o n 开放系统互连 a u t or e p e a tr e q u e s t 自动重发请求 a d a p t i v em o d u l a t i o na n dc o d i n g自适应调制和编码 c h a n n e ls t a t u si n f o r m a t i o n 信道状态信息 b i te r r o rr a t i o 误比特率 a d a 【p t i v ep o w e ra l l o c a t i o n 自适应功率分配 o r t h o g o n a lf r e q u e n c yd i v i s i o nm u l t i p l e x i n g 正交频分多址接入 a c c e s s m u l t i p l ei n p u ts i n g l eo u t p u t 多入单出 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究所取得的成果。除文中已经注明引用的内容外，本 论文不包含任何其他个人或集体已经发表或撰写过的科研成果。 对本文的研究作出重要贡献的个人和集体，均已在文中以明确方 式标明。本声明的法律责任由本人承担。 论文作者签名：庭j 丛日期：2 型：! ：们 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同 意学校保留或向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅和借阅；本人授权山东大学可以将本学位论 文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印或其他复制手段保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：丛导师签名：舶期：业 山东大学硕士学位论文 第一章遗传算法 1 1 标准遗传算法 1 1 1 生物进化理论和遗传基本知识 介绍遗传算法 i 训，要首先了解有关的生物进化理论和遗传学的基本知识。我 们知道，生物的基本特征包括生长、繁殖、新陈代谢和遗传与变异。生命是进化 的产物，现代的生物是在长期进化过程中发展起来的。达尔文用自然选择( n a t u r a l s e l e c t i o n ) 来解释物种的起源和生物的进化，其自然选择学说包括以下三个方面： ( 1 ) 遗传( g e n e t i c ) 。这是生物的普遍特征， “种瓜得瓜，种豆得豆亲代把生 物信息交给子代，子代按照所得信息而发育、分化，因而子代总是与亲代具有相 同或相似的性状。生物有了这个特征，物种才能稳定存在。 ( 2 ) 变异( m u t a t i o n ) 。亲代和子代之间以及子代的不同个体之间总有些差异，这 种现象称为变异。变异是随机发生的，变异的选择和积累是生命多样性的基础。 ( 3 ) 生存斗争和适者生存自然选择来自繁殖过剩和生存斗争。由于弱肉强食的 生存斗争不断进行，其结果是适者生存、具有适应性变异的个体被保留下来，不 具有适应性变异的个体被淘汰。通过一代代的生存环境的选择作用，物种变异被 定向向一个方向积累，于是性状逐渐和原先的祖先不同，进而演变为新的物种。 这种自然选择过程是一个长期的、缓慢的、连续的过程。 达尔文的进化理论是生物学史上的一个重要里程碑，它解释了自然选择作用 下生物的渐进式变化。遗传算法效法于自然选择的生物进化，是一种模拟生物进 化过程的随机方法。下面给出了几个生物学的基本概念和术副2 1 ，这对于理解遗传 算法是非常重要的。 1 染色体( c h r o m o s o m e ) ：生物细胞中含有的一种微小的丝状化合物。它是 遗传物质的主要载体，由多个遗传因子一基因组成。 2 遗传因子( g e n e ) ：d n a 长链结构中占有一定位置的基本遗传单位，也称为 基因。 3 基因型( g e n o t y p e ) ：遗传因子组合的模型，它是染色体性状的内部表现， 山东大学硕士学位论文 叫做基因型。 4 基因座( 1 0 c u s ) ：遗传基因在染色体中所占据的位置。同一基因座可能有的 全部基因称为等位基因( a l l e l e ) 。 5 个体( i n d i v i d u a l ) ：指染色体带有特征的实体。 6 种群( p o p u l a t i o n ) ：染色体带有特征的个体的集合称为种群。该集合内个 体数称为群体的大小。有时个体的集合也称为个体群。 7 进化( e v o l u t i o n ) ：生物在其延续生存的过程中，逐渐适应其生存环境，使 得其品质不断得到改良，这种生命现象称为进化。生物的进化是以种群的形式进 行的。 8 适应度( f i t n e s s ) ：在研究自然界中生物的遗传和进化现象时，生物学家使 用适应度这个术语来度量某个物种对于生存环境的适应程度。对生存环境适应程 度较高的物种将获得更多的繁殖机会，而对于生存环境适应程度较低物种，其繁 殖机会就会相对较少，甚至逐渐灭绝。 9 选择( s e l e c t i o n ) ：根据各个个体的适应度，按照一定的规则或方法，从第 t 代群体p ( t ) 中选择一些优良的个体遗传到下一代群体p ( t + 1 ) 中。 1 0 交叉( c r o s s o v e r ) ：将群体内的各个个体随机搭配成对，对每一对个体， 以某一概率( 称为交叉概率，c r o s s o v e rr a t e ) 交换它们之间的部分染色体。 11 变异( m u t a t i o n ) ：对群体中的每一个个体，以某一概率( 称为变异概率， m u t a t i o nr a t e ) 改变某一个或某些基因座上的基因值 1 2 编码( c o d i n g ) ：在细胞进行复制的时候可能以很小的概率产生某些复制 差错，从而使d n a 发生某种变异，产生出新的染色体，这些新的染色体表现出新 的性状。 13 解码( d e c o d i n g ) ：从基因型到表现型的映射。 1 1 2 遗传算法基本思想 遗传算法实质上是一种繁衍、监测和评价的迭代算法。它一般要包含以下几 个处理步骤【3 l ：首先对问题的解进行编码，p , p m 染色体表示问题的潜在解，生成经 过编码的初始种群；适应度函数因优化问题的目标函数而定，然后根据适应度大 小挑选个体进行遗传操作；最后按照适者生存和优胜劣汰的原理逐代演化，得到 问题的最优解或近似最优解。每个个体在种群演化过程中都被评价优劣并得到其 2 山东大学硕士学位论文 适应度值，个体在选择、交叉以及变异算子的作用下向更高的适应度进化以达到 寻求问题最优解的目标。在准备应用遗传算法求解问题时，要完成以下四个主要 步骤： ( 1 ) 确定表示方案； ( 2 ) 确定适应值度量； ( 3 ) 确定控制算法的参数和变量； ( 4 ) 确定指定结果的方法和停止运行的准则。 1 1 3 标准遗传算法的流程 遗传算法以自然选择和遗传理论为基础，将生物进化过程中适者生存规则与 群体内部染色体的随机信息交换机制相结合的搜索算法。遗传算法模拟了自然选 择和遗传中发生的复制、交叉和变异等现象，从任意初始种群出发，通过随机选 择、交叉、变异等操作，产生一群更适应环境的个体，使群体进化到搜索空间越 来越好的区域，这样一代一代的不断繁衍进化，最后收敛到一群最适应环境的个 体，求得问题最优解。在搜索之前，先将变量进行编码( 编码后个体称为染色体) ， 不同的染色体构成一个群体。对群体中的染色体，按一定的方法求出适应度值。 新的下一代群体的产生由以下两个步骤完成：首先，根据染色体适应度值选择被 保留的染色体及相应的复制次数；其次，对被选择的染色体进行交叉、变异，产 生新的个体。其流程如下： ( 1 ) 根据问题编码方法随机产生一组初始个体构成初始种群； ( 2 ) 评价每一个个体的适应度值； ( 3 ) 判断算法是否满足收敛准则，若收敛则输出否则进行以下步骤； ( 4 ) 根据适应度值大小进行复制操作； ( 5 ) 按交叉概率进行交叉操作； ( 6 ) 按变异概率执行变异操作； ( 7 ) 返回( 2 ) 。 流程图描述，如图1 1 1 所示。 山东大学硕士学位论文 图1 1 1 遗传算法流程图 1 2 遗传算法的基本要素 从基本遗传算法的介绍我们可以看出，遗传算法主要包含编码方法、个体适 应度评价，遗传算子和运行参剡4 1 等几个方面。 1 2 1 编码 在遗传算法运行过程中，它不对所求解问题的实际变量进行操作，而是对表 示可行解的个体编码施加选择、交叉、变异等遗传运算，通过这种遗传操作来达 到优化目的，这是遗传算法的特点之一。 4 山东大学硕士学位论文 编码是应用遗传算法首先要解决的问题，也是设计遗传算法时的一个关键步 骤。编码方法除了决定了个体的染色体排列形式外，它还决定了个体从搜索空间 的基因型变换到解空间的表现型时的解码方法，编码方法也影响到交叉算子、变 异因子等遗传算子的运算方法。由此可见，编码方法很大程度上决定了如何进行 群体的遗传进化运算以及遗传进化运算的效率。 一般来讲，编码方式有很多种，诸如二进制编码、大字符集编码、序列编码、 实数编码等。常用的编码方式有二进制编码和浮点数编码。 1 二进制编码二进制编码的编码符号集由0 和1 组成，因此染色体是一个二 进制符号串，其优点在于编码、解码操作简单，交叉、变异等遗传操作便于实现， 对于全局搜索能力有一定的优势；其缺点在于，不便于反映所求问题的特定知识， 如对于一些连续函数的优化问题等；也由于遗传算法的随机特性而使得其局部搜 索能力较差，对于一些多维、高精度要求的连续函数优化，二进制编码存在着连 续函数离散化时的映射误差，个体编码串较短时，可能达不到精度要求；而个体 编码串的长度较长时，虽然能提高精度，但却会使算法的搜索空间急剧扩大。如 果个体编码串特别长时，会造成遗传算法的性能降低。 2 浮点数编码浮点数编码方法是指个体的基因值用某一范围内的一个浮点 数来表示，个体的编码长度等于其决策变量的个数的编码方法。就二进制编码和 浮点数编码比较而言，浮点数编码在一些情况下比较能反映所求问题的特定知识， 编码结构一般比二进制来得简单些。一般二进制编码比浮点数编码搜索能力强， 但浮点数编码比二进制编码在变异操作上能够保持更好的种群多样性。 编码应适合要解决的问题，而不是简单的描述问题。b a l a k a r i s h m a n 等较全面 地讨论了不同编码方法的一组特性，针对一类特别的应用，为设计和选择编码方 法提供了指南，主要有以下九个特性【5 】： ( 1 ) 完全性( c o m p l e t e n e s s ) ：原则上，分布在所有问题域的解都可能被构造出来。 ( 2 ) 封闭性( c l o s u r e ) ：每个基因编码对应一个可接受的个体，封闭性保证系统 不会产生无效个体。 ( 3 ) 可扩展性( s c a l a b i l i t y ) ：对于具体问题，编码的大小确定了解码的时间。两者 存在一定的函数关系，若增加一种表现型，作为基因型的编码大小也作相应的增加。 ( 4 ) 多重性( m u l t i p l i c i t y ) ：多个基因型解码成一个表现型，即从基因型到相应的 表现型空间是多对一的关系，这是基因的多重性。若相同的基因型被解码成不同 5 山东大学硕士学位论文 的表现型，这是表现型的多重性。 ( 5 ) 紧致性( c o m p a c t n e s s ) ：若两种基因编码能解码成相同的个体，那么占用 空间越小的编码方式就越紧致。 ( 6 ) 个体可塑性( f l e x i b i l i t y ) ：决定表现型与相应给定基因型是受环境影响的。 ( 7 ) 模块性( m o d u l a r i t y ) ：若表现型的构成中有多个重复的结构，在基因编码中 这种重复是应当避免的。 ( 8 ) 冗余性( r e d u n d a n c y ) ：冗余性能提高可靠性和鲁棒性。 ( 9 ) 复杂性( c o m p l e x i t y ) ：指基因型结构的复杂性，解码的复杂性，计算时空 的复杂性。 1 2 2 初始种群 初始种群的好坏对于遗传算法的计算结果的优劣和算法的效率有着重要影 响。简单遗传算法通过随机的方法产生一定数目的初始种群，它覆盖的参数空间 具有很大的不确定性，如果初始种群中不包含全局最优解的基因，而经过有限次 进化后，算法又没有得到全局最优解，那么就一定会产生早熟收敛。另外，对于 约束优化问题，初始种群能否分布在可行域范围之内或接近于可行域范围，是影 响遗传算法能否得到全局最优解的主要因素之一。而在简单遗传算法中，随机产 生初始种群的方法根本无法避免非可行解在种群中的存在，往往由于大量非可行 解的存在导致遗传算法在运行过程中无法接近可行域，最终导致得到非法解。 对于求解多峰的复杂问题，算法能否收敛到全局最优解，就取决于遗传算法 的初始种群。一般来说，初始种群的范围越大，越有利于遗传算法得到较为理想 的计算结果。 产生初始种群通常有两种方法。一种是完全随机的产生方法，它适用于对待 求解问题的解无任何先验知识的情况：另一种是把某些先验知识转化为必须满足 的一组要求，然后在满足这些要求的解中随机地选取。这种选择初始种群的方法 可以使遗传算法最快地达到最优解。 1 2 3 适应度函数 对于自然界中生物的遗传进化，我们一般使用适应度这个术语来衡量某个物 种对于其生存环境的适应程度。对生存环境适应程度较高的物种将有更多的繁殖 6 山东大学硕士学位论文 机会；而对生存环境适应度较低的物种，其繁殖机会就相对较少，甚至会逐渐灭 绝。与此相类似，遗传算法中也使用适应度这个概念来度量群体中各个个体在优 化计算中有可能达到或接近于最优解的优良程度。适应度较高的个体以较高的概 率遗传到下代；而适应度较低的个体遗传到下一代的概率就相对小一些。度量 个体适应度的函数称为适应度函数( f i t n e s sf u n c t i o n ) 。 遗传算法的一个特点是它仅使用所求问题的目标函数值就可以得到下一步的 有关搜索信息。而对目标函数值的使用是通过评价个体的适应度来体现的。评价 个体适应度的一般过程是： ( 1 ) 对个体编码串进行解码处理后，可得到个体的表现型。 ( 2 ) 由个体的表现型可计算出对应个体的目标函数值。 ( 3 ) 根据最优化问题的类型，由目标函数值按一定的转换规则求出个体的适应度。 最优化问题一般可以分为两大类，一类为求目标函数的最大值，另一类为求 目标函数的最小值。而将目标函数转换成适应度函数一般遵循两个基本原则【6 】： ( 1 ) 适应度值必须大于等于零； ( 2 ) 优化过程中目标函数变化方向应与群体进化过程中适应度函数变化方向一致。 因此，可由解空间中某一点的目标函数值厂( x ) 到搜索空间对应个体的适应度 函数值，( x 1 的转化方法： 对于最小值优化问题，可通过式( 1 2 1 ) 建立与目标函数存在映射关系的适应度 函数。 僻f 八刁蒜乏 2 m 式中是一个可调参数，可取目标函数厂( j ) 理论上可能的最大值。 对于最大值优化问题，可通过式( 1 2 2 ) 建立与目标函数存在映射关系的适应度 函数。 ，( x ，= 完二；厂x ；：二；三三 ( 1 2 2 ) 7 山东大学硕士学位论文 式中c m h 是一个可调参数，其取值使f ( 石) 恒大于o 。 1 2 4 选择算子 在生物的遗传和进化过程中，对生存环境适应度较高的物种将有更多的机会 遗传到下一代，而对生存环境适应程度较低的物种遗传到下一代的机会较少。模 拟这个过程，遗传算法使用选择算子来对群体中的个体进行优胜劣汰操作：适应 度较高的个体被遗传到下一代群体中的概率较大；适应度较低的个体被遗传到下 一代群体中的概率较小。遗传算法中的选择操作就是用来确定如何从父代群体中 按某种方法选取哪些个体遗传到下一代群体中的一种遗传运算。 选择运算使用的算子主要有：比例选择、最优保存策略、确定式采样选择、 排序选择等。经常使用的是比例选择算子，其思想是各个个体被选中的概率与其 适应度大小成正比；最优保存策略则是考虑到由于选择、交叉、变异操作的随机 性，可能破坏当前群体中适应度最好的个体，为了避免这种情况发生，我们保留 适应度最好的个体不参与交叉和变异。 以比例算子为例，其过程为： ( 1 ) 先计算出群体中所有个体的适应度的总和； ( 2 ) 其次计算出每个个体的相对适应度的大小，它即为各个个体被遗传到下一 代群体中的概率； ( 3 ) 最后再使用模拟赌盘操作( 即0 到1 之间的随机数) 来确定各个个体被选中的 次数。 1 2 5 交叉算子 交叉( c r o s s o v e r ) 是模拟自然界中生物繁殖的机制而设计的遗传操作，通过交 叉，实现了基因重组( r e c o m b i n a t i o n ) ，从而将父代基因的信息有选择的遗传到其 下一代基因中间去。 传统的单点交叉操作是随机产生一个交叉点，然后将两个父个体在交叉点右 侧的部分相互交换。另外可以根据实际情况的不同，使用双点交叉、多点交叉和 算术交叉等交叉算子。 山东大学硕士学位论文 1 2 6 变异算子 变异( m u t a t i o n ) 是模拟自然界中生物基因突变的机制而设置的遗传操作。在从 少数几个原始的单细胞生物发展到如今种类繁多，形态各异的生物种群的历史长 河中，变异发挥了极其重要的作用。 变异运算使用基本位变异算子或均匀变异算子。基本位变异是指对个体编码 串以变异概率随机指定某一位或几位基因座上的基因做运算。均匀变异是指用某 一范围的随机数，以较小的概率来替换个体编码串中基因座上的基因值。 1 2 7 参数选择 遗传算法中的参数选择非常关键【7 1 ，参数的不同选取会对遗传算法的性能产生 较大影响，会影响到整个算法的收敛性。遗传算法中需要的参数主要包括种群规 模m 、编码长度，、交叉概率见、变异概率等。 ( 1 ) 群体规模。群体规模的大小直接影响到遗传算法的收敛性或计算效率。规 模过小，容易收敛到局部最优解；规模过大，会造成计算速度降低。群体规模可 以根据实际情况在10 - 2 0 0 之间选定。 ( 2 ) 编码串长度。使用二进制编码来表示个体时，长度的选取一般与求解问题 的精度有关；使用浮点数编码时，编码长度于决策变量的个数相等；而使用符号 编码来表示个体时，长度由问题的编码方式确定；此外，也可使用变长度编码来 表示个体。 ( 3 ) 交叉概率。交叉操作是遗传算法中产生新个体的主要方法，所以一般取较 大值。交叉概率控制着交叉操作被使用的频度，较大的交叉概率可增强遗传算法 开辟新的搜索区域的能力，但高性能的模式遭破坏的可能性较大。 ( 4 ) 变异概率。变异在遗传算法中属于辅助性搜索操作，主要目的是增强算法 的局部搜索能力，低频度的变异可防止群体中重要单一基因的丢失，高频度变异 将使算法趋于纯粹的随机搜索。通常取值0 0 0 1 - 0 1 。 1 3 遗传算法的特点 运用独到的工作原理和机制，遗传算法能够在复杂空间中进行全局优化搜索， 9 山东大学硕士学位论文 并且具有较强的鲁棒性。遗传算法是一种更为宏观意义下的仿生算法，它模仿的 机制是一切生命与智能的产生与进化过程。它模拟达尔文的自然进化论和孟代尔 的遗传变异理论，具有坚实的生物学基础：它提供从智能生成过程观点对生物智 能的模拟，具有鲜明的认知学意义；它适合与无表达或有表达的任何函数，具有 可实现的并行计算行为；它能解决任一类实际问题，具有广泛的应用价值。作为 一种随机的优化与搜索方法，遗传算法有着其鲜明的特点【8 9 】： ( 1 ) 它对进化过程中的适应值函数没有限制性的要求或假设，即不要求适应值 函数连续或者可微等，甚至不需要有显式的函数形式，因此目标函数也可以是映 射矩阵或者神经网络等隐函数。 ( 2 ) 遗传算法的优化对象是参数的编码而非参数本身。遗传算法对一些个体进 行进化操作，这些个体是基于某种编码方式而获得的位串，因此遗传算法首先有一 个有限的字母表。而对应于实际问题解方案的个体则是这个字母表的闭包子集。应 当注意的是，一般遗传算法中的个体编码串的长度都是统一的，所有这些组合方式 构成了字母表闭包的一个子集。通常遗传算法的编码方式是基于二进制的编码。 ( 3 ) 遗传算法具有很强的并行性，这种并行性主要表现在两个方面。其一是内 含并行性( i m p l i c i tp a r a l l e l i s m ) ，即遗传算法的遗传操作是从许多个体开始的，一 个种群中的多个个体同时进行进化，这使得算法具有并行特征。理论研究证明， 遗传算法每处理数量为n 的个体计算，实际处理的模式数量却为n 的三次方。其二 是内在并行性( i n h e r e n tp a r a l l e l i s m ) ，即遗传算法本身能够实现并行计算。最简单 的并行方式是让许多台计算机各自进行独立种群的进化计算，计算的过程中甚至 可以不进行任何形式的通信，直到每个种群进化收敛得到结果后再通信比较，选 出最终最优个体。多种群并行进化和岛模型的提出都为遗传算法实现宏观并行提 供了条件。 ( 4 ) 遗传算法通过适应值函数即目标函数来计算每个个体的适应值大小，而 不需要其它有关问题的信息和推导，算法的独立性强，使得遗传算法能够形成一 种通用算法框架，在处理完全不同的问题时，仅需要稍加修改就可以移植使用， 降低了推广的成本。这点使遗传算法被迅速推广应用，也是各个领域的学者对它 普通感兴趣的原因之一。 ( 5 ) 遗传算法的寻优规则是由概率确定的，而非确定性的。算法的目标函数 给出一个进化的方向和目标，但算法以何种路径进行搜索则是概率确定的。因此 l o 山东大学硕士学位论文 遗传算法被称为是一种随机优化算法。但这点并不意味着遗传算法是完全地进行 随机搜索。遗传算法在解空间中进行高效的启发式搜索，而不是盲目地穷举或者 完全随机的搜索。 此外，遗传算法还具有计算简单，编程实现难度低，功能强的优点，因此更 适用于大规模复杂问题的优化求解。 1 4 遗传算法的改进 尽管遗传算法有着许多优点。但许多专家学者研究表明，遗传算法存在的问 题还有很多，比如说：适应值标定方式多种多样、遗传算法的早熟现象，在最优 解附近的摆动等问题。 遗传算法通常需要解决以下问题，如确定编码方案，适应度函数标定，选择 遗传方式及相关控制参数，停止准则确定等。相应的，为了改进遗传算法的性能， 改进工作也是分别从参数编码、初始群体设定、适应度函数标定、遗传操作算子、 控制参数的选择以及遗传算法的结构等方面提出。改进遗传算法的基本途径主要 有下面几个方面： ( 1 ) 改进遗传算法的组成成分或使用技术。如选用优化控制参数、适合问题特 性的编码技术等； ( 2 ) 采用混合遗传算法( h y b n dg e n e t i ca l g o r i t h m ) ； ( 3 ) 采用动态自适应技术，在算法过程中调节相应的参数； ( 4 ) 采用非标准的遗传操作算子； ( 5 ) 采用并行算法。 一般来说存在着以下七种常见的改进遗传算法： ( 1 ) 分层遗传算法( h i e r a r c h i cg e n e t i ca l g o r i t h m ) ； ( 2 ) c h c 算法； ( 3 ) m e s s y 遗传算法； ( 4 ) 自适应遗传算法( a d a p t i v eg e n e t i ca l g o r i t h m ) ； ( 5 ) 基于小生境技术的遗传算法( n i c h e dg e n e t i ca l g o r i t h m ，n g a ) ： ( 6 ) 并行遗传算法( p a r a l l e lg e n e t i ca l g o r i t h m ) ； ( 7 ) 混合遗传算法。 山东大学硕士学位论文 第二章基于遗传算法的盲信道均衡 2 1 引言 信道的失真和畸变所引起的码问干扰( i s l ，i n t e r - s y m b o li n t e r f e r e n c e ) 是影响 现代通信质量的一个主要因素，需要有效的信道均衡技术来消除。传统的做法是 通过发送训练序列或根据信道的先验知识实现信道的辨识与均衡，而这种方法并 不适用于无线信道，因为我们一般无法得到信道的先验知识。这种信道均衡技术 是自适应的，但是会由于需要发送训练序列而浪费一部分资源。 盲均衡( b l i n de q u a l i z a t i o n ) 1 0 】技术能够不借助于训练序列，仅利用接收序列 本身的先验信息，便可以均衡信道特性，使均衡器的输出序列尽量接近发送序列 的一种自适应均衡技术，能很好地运用于多点通信系统和被动接收系统中的均衡 问题，在没有训练序列时，仅利用接收序列本身的先验信息也能正确地恢复发送 序列。此项技术的实际应用，对于提高接收信号的质量、保证信息的准确可靠， 具有十分重要的意义。 2 2 通信中的盲均衡理论 盲均衡与传统的均衡器不同的特点是在通信建立阶段或通信中断时不需要训练 序列，仅根据接收序列进行均甜1 1 】。由于它有许多优点成为通信研究中的热点问题。 因为在信息传输过程中插入训练序列会引起传输时延，并且在有些情况下发 送训练序列并非可能，盲均衡技术有效地克服了使用训练序列的均衡技术的缺陷。 盲均衡的原理如图2 2 1 所示。 噪声 1 2 y ( k ) 图2 2 1 盲均衡原理图 山东大学硕士学位论文 图2 2 1 中h ( k ) 为离散时间传输信道( 包括发射滤波器、传输媒介和接收滤波 器的综合作用) 的冲激响应，w ( 尼) 为均衡器的冲激响应，x ( k ) 为系统发送序列， y ( k ) 为经过信道传输后的接收序列，同时也是盲均衡器的输入序列，l ( 尼) 为信道 迭加噪声，x ( k ) 为经过均衡后的恢复序列。根据信号传输理论有下式： y ( 七) = j i l ( 后) 幸石( 后) + 刀( 尼) = h ( i ) x ( k - i ) + n ( k ) ( 2 2 1 ) ， 由此可知j ，( 后) 是由x ( 尼) 和j l ( 后) 卷积而成，要想从y ( 七) 中获得z ( 后) ，就需要 对y ( 尼) 进行反卷积或解卷积运算，或等价辨识传输信道 ( 尼) 的逆信道。当y ( 后) 和 x ( k ) 已知时，h ( k ) 可以获得，均衡器的训练就属于此种情况【1 2 l 。但当x ( k ) 未知时， 即3 个参数中只有一个是已知，求解就相当困难，这就是盲均衡。 盲均衡作为一种算法考察其是否具有实用价值，主要取决于其性能。评价标 准一般有三条：一是收敛速度的快慢，这决定该算法能否用于实时系统；二是算法 能否获得最优解，也就是代价函数有无凸性；三是算法收敛后稳态剩余误差的大 小。一般情况下，表征盲均衡器性能的有关参数与自适应均衡器基本一样，包括 收敛速度，运算复杂度，误码特性，稳态剩余误差，跟踪时变信道能力和抗干扰 能力等。 2 3 系统模型和目标函数 2 3 1 离散通信系统模型 考虑一个离散的通信系统模型： x ( 聍) = & h ( 疗一地) + v ( ) k = - - ( 2 3 1 ) 其中墨表示第k 个源信号，刀表示符号间隔，l 是一个整数，表示过采样的数 目，h ( 刀) 表示离散信道的冲激响应，假设它是一个有限的冲激响应。v ( 刀) 是加 性噪声，假设其与源信号不相关。 1 3 山东大学硕士学位论文 过采样的单输入单输出模型可以等价于一个单输入多输出模型，因此得到： 玉( 以) = & 呜( 刀一尼) + m ( 刀) i = o , 1 ，三一1 k = - - c o 其中玉= x ( 比+ f ) ，红= h ( n l + i ) ，m ( 刀) = v ( 比+ f ) 。 2 3 2 目标函数的建立 根据上一节所提到的通信系统模型，考虑在没有噪声的情况下，对于任一组 ( ，利1 3 1 毛盼( 2 ( 2 3 3 ) ( k ) = 勺幸j ( 后) 、 嘭( 足) 謇五( 尼) = 勺( 尼) 木 ( 后) 幸j ( 七) = 鸟( 后) 吐哆( 尼) 囊s ( 七) = 鸭( j | ) + _ ( k ) 对于后= l ，n ，其中n 表示观测到的信号五( 七) 的个数，由上式z 。，1 0 ： x x ，- 倒, f h , = 。 其中h 。= k ( 三) ，以( o ) 7 。 | ( 1 )靠( 2 )( + 1 ) 耻惮矗 3 卜一“叫 【( n 一己) ( 一l + i ) ( ) j 山东大学硕士学位论文 为了遍历所有的( f ，) ，令 其中所有矩阵大小为( n - l ) x ( l + i ) ，定义 由此得： h = m ，h ： r x | h = 0 把所有的现行等式用矩阵形式表示， 叫斟 = 0 由以上分析，为了确定系统冲激响应给出以下目标函数： 2 4 1 算法描述 m 。j n j = i i 1 1 2 2 4 基于遗传算法的盲信道均衡 ( 2 3 6 ) ( 2 3 7 ) 将信道冲激响应抽像为行矢量) ；，应用( 2 3 6 ) 式的目标函数，给出交叉和 变异算子【1 4 1 ： 1 5 o x x o o 一 一：k o 0o ；o l =x 山东大学硕士学位论文 交叉：采用算术交叉算子，即产生一个随机数口 o ，1 】对于两个交叉个体，其 交叉子代为 = 爿1 1 一曲矛，俨= 彳+ ( 1 一司i l ( 2 4 1 ) 变异：采用高斯变异算子，即对要进行变异的个体j ；，产生刀个均值为0 ，方 差为q 的正态分布随机变量( o ，q ) ，则变异后的子代分量为 矿= h i + ( o