硕士论文-遗传算法及其在通信中的应用.pdf

《硕士论文-遗传算法及其在通信中的应用.pdf》由会员分享，可在线阅读，更多相关《硕士论文-遗传算法及其在通信中的应用.pdf（75页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、山东大学硕士学位论文遗传算法及其在通信中的应用姓名：刘波申请学位级别：硕士专业：通信与信息系统指导教师：江铭炎20090420山东大学硕士学位论文中文摘要遗传算法(G A，G e n e t i cA l g o r i t h m)是一种基于生物界演化的随机搜索技术。近年来，遗传算法广泛而深入地应用于通信中的各种联合优化问题并已经有了很多成功的实例。盲均衡技术能够仅利用接收信号的统计特性对信道特性进行均衡，克服了传统自适应均衡技术需要训练序列、降低系统有效信息传输率的缺陷，成为目前的研究热点。本文简单介绍了通信中的盲均衡技术，并针对一个简单的信道模型给出了基于遗传算法的盲均衡算法。仿真结果表

2、明，多次迭代的盲均衡的均值能够很好地代表未知信道的性能。为了更好地利用O F D M 系统的性能，需要对资源分配进行设计。通过对功率、带宽、调制方式等的资源控制可以得到比较好的性能。O F D M 系统中存在着两种资源分配方案：动态和静态。本文采用遗传算法对一种动态资源分配方案进行了优化，采用自适应的功率分配的方法，在功率约束的条件下最大化系统容量，并保证了用户之间的公平性。随着无线应用的发展，传统的O S l 分层结构无法适应无线网络环境，人们提出了跨层设计，其主要内容就是通过在协议的各层之间传递特定的信息，使协议栈能够根据无线环境的变化来实现对资源的自适应优化配置，从而有效利用无线网络资源

3、，提高系统性能。本文提出了针对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 TG 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

4、 ep r i n c i p l e so fb 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 nc 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

5、n dB 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 ep 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 do v e r c o m et h ed i s a d v a

6、 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 hr 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 nr a t ei ns y s t e mt r a n s m i s s i o n T h i sp a p e rg i v e sar e v i e wo fb l i n de q

7、u a l i z a t i o n，a n db u i l d sas i m p l es 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 do 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

8、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 ea 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 sb a n d w i d t h，p o w e r,a n dm o d u l a

9、 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

10、 p e rf o r m u l a t e sa l lo p t i m i z a t i o np 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 lp 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

11、i t ht h ed 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 ti 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 ot h ec h a

12、 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 nt 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 ya n di m p r o v et h ep e r f

13、 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 ga 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 so 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 e

14、u s eg e n e t i ca l g o r i t h m st oo 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 rI 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

15、h o d K e yw o r d s：G e n e t i ca l g o r i t h m；R e s o u r c ea l l o c a t i o n；C r o s s l a y e rd e s i g n；O F D M A M I S Os y s t e mI I I山东大学硕士学位论文G AH G AA G AP G AI S IO F D MI C IC PS l N RQ o SM P FA W G NO S IA R QA M CC S IB E RA P AO F D M AM I S O符号说明G e n e t i ca l g o r i t

16、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

17、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

18、 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 y

19、D i v i s i o nM u l t i p l e x i n g 正交频分多址接入A c c e s sM u l t i p l eI n p u tS i n g l eO u t p u t多入单出原创性声明本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研究作出重要贡献的个人和集体，均已在文中以明确方式标明。本声明的法律责任由本人承担。论文作者签名：庭j 丛日期：2 型：!：们关于学位论文使用授权的声明本人完全了解山东大学有关保留、使用学位论文的规定

20、，同意学校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段保存论文和汇编本学位论文。(保密论文在解密后应遵守此规定)论文作者签名：丛导师签名：舶期：业山东大学硕士学位论文第一章遗传算法1 1 标准遗传算法1 1 1 生物进化理论和遗传基本知识介绍遗传算法 I 训，要首先了解有关的生物进化理论和遗传学的基本知识。我们知道，生物的基本特征包括生长、繁殖、新陈代谢和遗传与变异。生命是进化的产物，现代的生物是在长期进化过程中发展起来的。达尔文用自然选择(n a t u r

21、a ls 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)生存斗争和适者生存自然选择来自繁殖过剩和生存斗争。由于弱肉强食的生存斗争不断进行，其结果是适者生存、具有适应性变

22、异的个体被保留下来，不具有适应性变异的个体被淘汰。通过一代代的生存环境的选择作用，物种变异被定向向一个方向积累，于是性状逐渐和原先的祖先不同，进而演变为新的物种。这种自然选择过程是一个长期的、缓慢的、连续的过程。达尔文的进化理论是生物学史上的一个重要里程碑，它解释了自然选择作用下生物的渐进式变化。遗传算法效法于自然选择的生物进化，是一种模拟生物进化过程的随机方法。下面给出了几个生物学的基本概念和术副2 1，这对于理解遗传算法是非常重要的。1 染色体(c h r o m o s o m e)：生物细胞中含有的一种微小的丝状化合物。它是遗传物质的主要载体，由多个遗传因子一基因组成。2 遗传因子(g

23、 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

24、)：生物在其延续生存的过程中，逐渐适应其生存环境，使得其品质不断得到改良，这种生命现象称为进化。生物的进化是以种群的形式进行的。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

25、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 遗传算法基本思

26、想遗传算法实质上是一种繁衍、监测和评价的迭代算法。它一般要包含以下几个处理步骤【3 l：首先对问题的解进行编码，P,P m 染色体表示问题的潜在解，生成经过编码的初始种群；适应度函数因优化问题的目标函数而定，然后根据适应度大小挑选个体进行遗传操作；最后按照适者生存和优胜劣汰的原理逐代演化，得到问题的最优解或近似最优解。每个个体在种群演化过程中都被评价优劣并得到其2山东大学硕士学位论文适应度值，个体在选择、交叉以及变异算子的作用下向更高的适应度进化以达到寻求问题最优解的目标。在准备应用遗传算法求解问题时，要完成以下四个主要步骤：(1)确定表示方案；(2)确定适应值度量；(3)确定控制算法的参数和

27、变量；(4)确定指定结果的方法和停止运行的准则。1 1 3 标准遗传算法的流程遗传算法以自然选择和遗传理论为基础，将生物进化过程中适者生存规则与群体内部染色体的随机信息交换机制相结合的搜索算法。遗传算法模拟了自然选择和遗传中发生的复制、交叉和变异等现象，从任意初始种群出发，通过随机选择、交叉、变异等操作，产生一群更适应环境的个体，使群体进化到搜索空间越来越好的区域，这样一代一代的不断繁衍进化，最后收敛到一群最适应环境的个体，求得问题最优解。在搜索之前，先将变量进行编码(编码后个体称为染色体)，不同的染色体构成一个群体。对群体中的染色体，按一定的方法求出适应度值。新的下一代群体的产生由以下两个步

28、骤完成：首先，根据染色体适应度值选择被保留的染色体及相应的复制次数；其次，对被选择的染色体进行交叉、变异，产生新的个体。其流程如下：(1)根据问题编码方法随机产生一组初始个体构成初始种群；(2)评价每一个个体的适应度值；(3)判断算法是否满足收敛准则，若收敛则输出否则进行以下步骤；(4)根据适应度值大小进行复制操作；(5)按交叉概率进行交叉操作；(6)按变异概率执行变异操作；(7)返回(2)。流程图描述，如图1 1 1 所示。山东大学硕士学位论文图1 1 1 遗传算法流程图1 2 遗传算法的基本要素从基本遗传算法的介绍我们可以看出，遗传算法主要包含编码方法、个体适应度评价，遗传算子和运行参剡4

29、 1 等几个方面。1 2 1 编码在遗传算法运行过程中，它不对所求解问题的实际变量进行操作，而是对表示可行解的个体编码施加选择、交叉、变异等遗传运算，通过这种遗传操作来达到优化目的，这是遗传算法的特点之一。4山东大学硕士学位论文编码是应用遗传算法首先要解决的问题，也是设计遗传算法时的一个关键步骤。编码方法除了决定了个体的染色体排列形式外，它还决定了个体从搜索空间的基因型变换到解空间的表现型时的解码方法，编码方法也影响到交叉算子、变异因子等遗传算子的运算方法。由此可见，编码方法很大程度上决定了如何进行群体的遗传进化运算以及遗传进化运算的效率。一般来讲，编码方式有很多种，诸如二进制编码、大字符集编

30、码、序列编码、实数编码等。常用的编码方式有二进制编码和浮点数编码。1 二进制编码二进制编码的编码符号集由0 和1 组成，因此染色体是一个二进制符号串，其优点在于编码、解码操作简单，交叉、变异等遗传操作便于实现，对于全局搜索能力有一定的优势；其缺点在于，不便于反映所求问题的特定知识，如对于一些连续函数的优化问题等；也由于遗传算法的随机特性而使得其局部搜索能力较差，对于一些多维、高精度要求的连续函数优化，二进制编码存在着连续函数离散化时的映射误差，个体编码串较短时，可能达不到精度要求；而个体编码串的长度较长时，虽然能提高精度，但却会使算法的搜索空间急剧扩大。如果个体编码串特别长时，会造成遗传算法的

31、性能降低。2 浮点数编码浮点数编码方法是指个体的基因值用某一范围内的一个浮点数来表示，个体的编码长度等于其决策变量的个数的编码方法。就二进制编码和浮点数编码比较而言，浮点数编码在一些情况下比较能反映所求问题的特定知识，编码结构一般比二进制来得简单些。一般二进制编码比浮点数编码搜索能力强，但浮点数编码比二进制编码在变异操作上能够保持更好的种群多样性。编码应适合要解决的问题，而不是简单的描述问题。B a l a k a r i s h m a n 等较全面地讨论了不同编码方法的一组特性，针对一类特别的应用，为设计和选择编码方法提供了指南，主要有以下九个特性【5】：(1)完全性(c o m p l

32、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山东大学硕士学位论文的表现型，这是表现型的多重性。

33、(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 初始种群初始种群的好坏对于遗传算法

34、的计算结果的优劣和算法的效率有着重要影响。简单遗传算法通过随机的方法产生一定数目的初始种群，它覆盖的参数空间具有很大的不确定性，如果初始种群中不包含全局最优解的基因，而经过有限次进化后，算法又没有得到全局最优解，那么就一定会产生早熟收敛。另外，对于约束优化问题，初始种群能否分布在可行域范围之内或接近于可行域范围，是影响遗传算法能否得到全局最优解的主要因素之一。而在简单遗传算法中，随机产生初始种群的方法根本无法避免非可行解在种群中的存在，往往由于大量非可行解的存在导致遗传算法在运行过程中无法接近可行域，最终导致得到非法解。对于求解多峰的复杂问题，算法能否收敛到全局最优解，就取决于遗传算法的初始种

35、群。一般来说，初始种群的范围越大，越有利于遗传算法得到较为理想的计算结果。产生初始种群通常有两种方法。一种是完全随机的产生方法，它适用于对待求解问题的解无任何先验知识的情况：另一种是把某些先验知识转化为必须满足的一组要求，然后在满足这些要求的解中随机地选取。这种选择初始种群的方法可以使遗传算法最快地达到最优解。1 2 3 适应度函数对于自然界中生物的遗传进化，我们一般使用适应度这个术语来衡量某个物种对于其生存环境的适应程度。对生存环境适应程度较高的物种将有更多的繁殖6山东大学硕士学位论文机会；而对生存环境适应度较低的物种，其繁殖机会就相对较少，甚至会逐渐灭绝。与此相类似，遗传算法中也使用适应度

36、这个概念来度量群体中各个个体在优化计算中有可能达到或接近于最优解的优良程度。适应度较高的个体以较高的概率遗传到下代；而适应度较低的个体遗传到下一代的概率就相对小一些。度量个体适应度的函数称为适应度函数(f i t n e s sf u n c t i o n)。遗传算法的一个特点是它仅使用所求问题的目标函数值就可以得到下一步的有关搜索信息。而对目标函数值的使用是通过评价个体的适应度来体现的。评价个体适应度的一般过程是：(1)对个体编码串进行解码处理后，可得到个体的表现型。(2)由个体的表现型可计算出对应个体的目标函数值。(3)根据最优化问题的类型，由目标函数值按一定的转换规则求出个体的适应度。

37、最优化问题一般可以分为两大类，一类为求目标函数的最大值，另一类为求目标函数的最小值。而将目标函数转换成适应度函数一般遵循两个基本原则【6】：(1)适应度值必须大于等于零；(2)优化过程中目标函数变化方向应与群体进化过程中适应度函数变化方向一致。因此，可由解空间中某一点的目标函数值厂(x)到搜索空间对应个体的适应度函数值，(x 1 的转化方法：对于最小值优化问题，可通过式(1 2 1)建立与目标函数存在映射关系的适应度函数。僻F 八刁蒜乏2 m式中是一个可调参数，可取目标函数厂(J)理论上可能的最大值。对于最大值优化问题，可通过式(1 2 2)建立与目标函数存在映射关系的适应度函数。，(x，=完

38、二；厂x；：二；三三(1 2 2)7山东大学硕士学位论文式中C m h 是一个可调参数，其取值使F(石)恒大于o。1 2 4 选择算子在生物的遗传和进化过程中，对生存环境适应度较高的物种将有更多的机会遗传到下一代，而对生存环境适应程度较低的物种遗传到下一代的机会较少。模拟这个过程，遗传算法使用选择算子来对群体中的个体进行优胜劣汰操作：适应度较高的个体被遗传到下一代群体中的概率较大；适应度较低的个体被遗传到下一代群体中的概率较小。遗传算法中的选择操作就是用来确定如何从父代群体中按某种方法选取哪些个体遗传到下一代群体中的一种遗传运算。选择运算使用的算子主要有：比例选择、最优保存策略、确定式采样选择

39、、排序选择等。经常使用的是比例选择算子，其思想是各个个体被选中的概率与其适应度大小成正比；最优保存策略则是考虑到由于选择、交叉、变异操作的随机性，可能破坏当前群体中适应度最好的个体，为了避免这种情况发生，我们保留适应度最好的个体不参与交叉和变异。以比例算子为例，其过程为：(1)先计算出群体中所有个体的适应度的总和；(2)其次计算出每个个体的相对适应度的大小，它即为各个个体被遗传到下一代群体中的概率；(3)最后再使用模拟赌盘操作(即0 到1 之间的随机数)来确定各个个体被选中的次数。1 2 5 交叉算子交叉(C r o s s o v e r)是模拟自然界中生物繁殖的机制而设计的遗传操作，通过交

40、叉，实现了基因重组(R e c o m b i n a t i o n)，从而将父代基因的信息有选择的遗传到其下一代基因中间去。传统的单点交叉操作是随机产生一个交叉点，然后将两个父个体在交叉点右侧的部分相互交换。另外可以根据实际情况的不同，使用双点交叉、多点交叉和算术交叉等交叉算子。山东大学硕士学位论文1 2 6 变异算子变异(M u t a t i o n)是模拟自然界中生物基因突变的机制而设置的遗传操作。在从少数几个原始的单细胞生物发展到如今种类繁多，形态各异的生物种群的历史长河中，变异发挥了极其重要的作用。变异运算使用基本位变异算子或均匀变异算子。基本位变异是指对个体编码串以变异概率随机

41、指定某一位或几位基因座上的基因做运算。均匀变异是指用某一范围的随机数，以较小的概率来替换个体编码串中基因座上的基因值。1 2 7 参数选择遗传算法中的参数选择非常关键【7 1，参数的不同选取会对遗传算法的性能产生较大影响，会影响到整个算法的收敛性。遗传算法中需要的参数主要包括种群规模M、编码长度，、交叉概率见、变异概率等。(1)群体规模。群体规模的大小直接影响到遗传算法的收敛性或计算效率。规模过小，容易收敛到局部最优解；规模过大，会造成计算速度降低。群体规模可以根据实际情况在10 -2 0 0 之间选定。(2)编码串长度。使用二进制编码来表示个体时，长度的选取一般与求解问题的精度有关；使用浮点

42、数编码时，编码长度于决策变量的个数相等；而使用符号编码来表示个体时，长度由问题的编码方式确定；此外，也可使用变长度编码来表示个体。(3)交叉概率。交叉操作是遗传算法中产生新个体的主要方法，所以一般取较大值。交叉概率控制着交叉操作被使用的频度，较大的交叉概率可增强遗传算法开辟新的搜索区域的能力，但高性能的模式遭破坏的可能性较大。(4)变异概率。变异在遗传算法中属于辅助性搜索操作，主要目的是增强算法的局部搜索能力，低频度的变异可防止群体中重要单一基因的丢失，高频度变异将使算法趋于纯粹的随机搜索。通常取值0 0 0 1 -0 1。1 3 遗传算法的特点运用独到的工作原理和机制，遗传算法能够在复杂空间

43、中进行全局优化搜索，9山东大学硕士学位论文并且具有较强的鲁棒性。遗传算法是一种更为宏观意义下的仿生算法，它模仿的机制是一切生命与智能的产生与进化过程。它模拟达尔文的自然进化论和孟代尔的遗传变异理论，具有坚实的生物学基础：它提供从智能生成过程观点对生物智能的模拟，具有鲜明的认知学意义；它适合与无表达或有表达的任何函数，具有可实现的并行计算行为；它能解决任一类实际问题，具有广泛的应用价值。作为一种随机的优化与搜索方法，遗传算法有着其鲜明的特点【8 9】：(1)它对进化过程中的适应值函数没有限制性的要求或假设，即不要求适应值函数连续或者可微等，甚至不需要有显式的函数形式，因此目标函数也可以是映射矩阵

44、或者神经网络等隐函数。(2)遗传算法的优化对象是参数的编码而非参数本身。遗传算法对一些个体进行进化操作，这些个体是基于某种编码方式而获得的位串，因此遗传算法首先有一个有限的字母表。而对应于实际问题解方案的个体则是这个字母表的闭包子集。应当注意的是，一般遗传算法中的个体编码串的长度都是统一的，所有这些组合方式构成了字母表闭包的一个子集。通常遗传算法的编码方式是基于二进制的编码。(3)遗传算法具有很强的并行性，这种并行性主要表现在两个方面。其一是内含并行性(i m p l i c i tp a r a l l e l i s m)，即遗传算法的遗传操作是从许多个体开始的，一个种群中的多个个体同时进

45、行进化，这使得算法具有并行特征。理论研究证明，遗传算法每处理数量为n 的个体计算，实际处理的模式数量却为n 的三次方。其二是内在并行性(i n h e r e n tp a r a l l e l i s m)，即遗传算法本身能够实现并行计算。最简单的并行方式是让许多台计算机各自进行独立种群的进化计算，计算的过程中甚至可以不进行任何形式的通信，直到每个种群进化收敛得到结果后再通信比较，选出最终最优个体。多种群并行进化和岛模型的提出都为遗传算法实现宏观并行提供了条件。(4)遗传算法通过适应值函数即目标函数来计算每个个体的适应值大小，而不需要其它有关问题的信息和推导，算法的独立性强，使得遗传算法能

46、够形成一种通用算法框架，在处理完全不同的问题时，仅需要稍加修改就可以移植使用，降低了推广的成本。这点使遗传算法被迅速推广应用，也是各个领域的学者对它普通感兴趣的原因之一。(5)遗传算法的寻优规则是由概率确定的，而非确定性的。算法的目标函数给出一个进化的方向和目标，但算法以何种路径进行搜索则是概率确定的。因此l O山东大学硕士学位论文遗传算法被称为是一种随机优化算法。但这点并不意味着遗传算法是完全地进行随机搜索。遗传算法在解空间中进行高效的启发式搜索，而不是盲目地穷举或者完全随机的搜索。此外，遗传算法还具有计算简单，编程实现难度低，功能强的优点，因此更适用于大规模复杂问题的优化求解。1 4 遗传

47、算法的改进尽管遗传算法有着许多优点。但许多专家学者研究表明，遗传算法存在的问题还有很多，比如说：适应值标定方式多种多样、遗传算法的早熟现象，在最优解附近的摆动等问题。遗传算法通常需要解决以下问题，如确定编码方案，适应度函数标定，选择遗传方式及相关控制参数，停止准则确定等。相应的，为了改进遗传算法的性能，改进工作也是分别从参数编码、初始群体设定、适应度函数标定、遗传操作算子、控制参数的选择以及遗传算法的结构等方面提出。改进遗传算法的基本途径主要有下面几个方面：(1)改进遗传算法的组成成分或使用技术。如选用优化控制参数、适合问题特性的编码技术等；(2)采用混合遗传算法(H y b n dG e n

48、 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

49、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)是影响现代通信质量的一个主要因素，需要有效的信道均衡技术来消除。传统的做法是通过发送训练序列或根据信道的先验知识实现信道的辨识与均衡，而这种方法并不适用于无线信道，因为我们一般无法得到信道的先验知识。这种信道均衡技术是自适应的，但是会由于

50、需要发送训练序列而浪费一部分资源。盲均衡(B l i n dE q u a l i z a t i o n)1 0】技术能够不借助于训练序列，仅利用接收序列本身的先验信息，便可以均衡信道特性，使均衡器的输出序列尽量接近发送序列的一种自适应均衡技术，能很好地运用于多点通信系统和被动接收系统中的均衡问题，在没有训练序列时，仅利用接收序列本身的先验信息也能正确地恢复发送序列。此项技术的实际应用，对于提高接收信号的质量、保证信息的准确可靠，具有十分重要的意义。2 2 通信中的盲均衡理论盲均衡与传统的均衡器不同的特点是在通信建立阶段或通信中断时不需要训练序列，仅根据接收序列进行均甜1 1】。由于它有许多