（电磁场与微波技术专业论文）基于遗传算法的阵列天线综合.pdf

哈尔滨工程大学硕士学位论文 摘要 随着无线通信技术的飞速发展，有限的频谱资源嚣临着枯竭的危险，如 何优化通信系统资源配置和提高资源利用效率，直是通信领域科学家和工 程师追求的目标之一。智能天线就是在这一背景下应运而生的。而阵列天线 方向图的综合正是智能天线的核心技术，它是指通过改变天线阵的阵元数、 阵元位置、阵元馈电幅值、相位，针对不砑的信号环境实现系统参数选择的 最优化，从嚣提高了频谱资源的利用率，遗传算法由于其强大的全局寻优能 力，解决此类问题时有其特有的优点。 遗传算法是一种模拟生物在自然环境中遗传和进化过程宏观仿生方法， 根据“生存竞争 和“优胜劣汰 原则通过选择、交叉、变异程序，而组成 的畲适应全局优化概率搜索算法。由予它在解决大空阆、多参数、非线性等 复杂问题时所具有的独特优越性，所以在很多领域 | 导到广泛地应用。近年来， 遗传算法开始逐渐应用到天线优化设计领域。 本文对遗传算法在阵列天线方向图综合中的应用方面进行了研究。对旁 瓣摔制和零点生成进行了讨论，并对其中的超低副瓣天线阵和稀疏阵列的低 副瓣控制作了详缨的研究。 本文在理想条件下，运用遗传算法对直线阵和矩形阵进行了方向图综合 的仿真，得到如下结论： 1 遗传算法是阵列天线方向图综合的有效方法。 遗传算法是一种高效的智能仿生搜索算法，它采用全局与局部相结合的 搜索方式保证了群体的多样性，从恧避免了早熟现象。文孛采用遗传算法分 别对直线阵和矩形阵的阵元间距、激励幅度和相位进行了优化，并根据指标 要求实现了对副瓣电平的有效控制、超低副瓣的生成及在指定角度生成指定 零深的零陷。 2 遗传算法对方向图综合效果优于传统方法，并且处理昀优化问题越复 杂，效果越明显。 靖尔滨工程大学硕士学位论文 采用遗传算法综合后的方向图明显优予采用传统方法的，并且当阵元的 数嚣越多或方向图函数的形式越复杂，遗传算法的优越程度表现豹就越甓显； 3 采用了离散化阵列天线方向图函数。 对阵剜天线方扁图函数避幸亍采样，采耀适合计算祝和遗传算法运算的离 散讫函数，用矩阵运算替代了循环迭代，提高了计算的效率，并在仿真中得 到验证。 关键词：遗传算法；阵列天线；方怠鎏综合 哈尔滨工程大学硕士学位论文 a b s t r a c t w i t ht h ed e v e l o p m e n to fw i r e l e s sc o m m u n i c a t i o n , t h el i m i t e df r e q u e n c y r e s o u r c ed e c l i n e dr a p i d l y t oo p t i m i z et h er e s o u r c ea l l o c a t i o na n di m p r o v et h e u t i l i z a t i o nr a t i oo fr e s o u r c ei sb e c o m i n gap u r s u i n gg o a lf o rs c i e n t i s t sa n d e n g i n e e r s s m a r ta n t e n n at e c h n o l o g yo c c u r r e di ns u c hb a c k g r o u n d ，a n dp a t t e r n s y n t h e s i so fa n t e n n aa r r a yi st h ec o l et e c h n o l o g yo f s m a r ta n t e n n a i tc a l lu t i l i z e t h er e s o u r c ee & c f i v e l y 姆a d j u s t i n gt h ep a r a m e t e r so ft h ea n t e n n au n i t ss u c ha s t h en u m b e r s ，p o s i t i o n s ，f e e d i n g b a c ka m p l i t u d e sa n dp h a s e si nd i f f e r e n t 丘e q u e n c y c i r c u m s t a n c e t h ec o m p a r a t i v ea d v a n t a g eo fg e n e f i ca l g o r i t h mi so b v i o u s b e c a u s e o fi t s a b i l i t yo fg l o b a lr a p i do p t i m u m g e n e t i ca l g o r i t h mi sab i o n i ca l g o r i t h mw h i c hs i m u l a t e st h eh e r e d i t ya n d v a r i a t i o no fc r e a t u r e b a s e do nt h ep r i n c i p l eo f 啦玲s u r v i v a lo ft h ef i t t e s t ，i tc a n f i n dt h eo p t i m a ls o l u t i o nt h r o u g ht h ep r o c e s so fs e l e c t i n g ，c r o s s i n ga n dv a r i a t i o n g e n e t i ca l g o r i t h mh a st h ea d v a n t a g e st os e t t l el a r g es p a c e ，m u l t i p a r a m e t e ra n d n o - l i n e a rp r o b l e m s ，s oi ti sa p p l i e di ne x t e n s i v ef i e l d i nr e c e n ty e a r sg e n e t i c a l g o r i t h mh a sa p p l i c a t i o nt oa n a l y z ea n dd e s i g na n t e n n a 1 f 1 ：l i st h e s i sc a r r i e do i lar e s e a r c hi na p p l y i n gg e n e t i ca l g o r i t h mt op a 髓e m s y n t h e s i so fa n t e n n aa r r a y s i d e l o b es u p p r e s s i o na n dn u l ls t e e r i n ga r er e s e a r c h e d n ec o n t r o lo fl o ws i d e l o bi nu l t r a - l o ws i d e l o b ea n t e n n aa r r a ya n dt h i n n e da r r a y a l ed i s c u s s e dd e t a i l e d l y p a t t e ms y n t h e s i so fl i n e a r a r r a y a n dr e c t a n g u l a r a r r a yu s i n g g e n e t i c a l g o r i t h mi su n d e rt h ei d e a lc o n d i t i o ni nt h et h e s i s 。c o n c l u s i o n sg a i n e da r e 勰 f o l l o w s ： f i r s t l y , g e n e t i ca l g o r i t h mi st h ee f f i c i e mm e t h o do fp a t t e r ns y n t h e s i so f a n t e n n aa r r a y g e n e t i ca l g o r i t h mi sa l le f f i c i e n ti n t e l l i g e n tb i o n i ca l g o r i t h m 。i tu s e so v e r a l l 晗尔滨工程大学硕士学位论文 a n dl o c a ls e a r c h i n gm e t h o dt oe n s u r et h ed i v e r s i t yo ft h ec o l o n y , i no r d e rt oa v o i d t h ee a r l i n e s s 。i nt h et h e s i s ，a r r a ys p a c i n g 、a m p l i t u d ea n dp h a s eo f e x c i t e m e n ti n l i n e a ra r r a ya n dr e c t a n g u l a ra r r a ya r eo p t i m i z e du s i n gg e n e t i ca l g o r i t h m t h e r e s u l tc o n f i r mw i t ht h ed e s i g nb e a c o nw h i c hi st h ee f f i c i e n tc o n t r o lo fs i d e l o b e ， u l t r a - l o ws i d e l o b ea n dd e p t ho ft h en u l ls t e e r i n gi ns p e c i f i e da n g l e s e c o n d l y , t h ep e r f o r m a n c eo fp a t t e r ns y n t h e s i su s i n gg e n e t i ca l g o r i t h mi s b e t t e rt h a nw h i c hu s i n gt r a d i t i o n a lm e t h o d ，a n dw h i c hi sm o r ee v i d e n c ew h e n p r o b l e mr e q u i r e do p t i m i z a t i o ni sm o r ec o m p l e x i t y r e s u l t ss h o wt h a tp a t t e r ns y n t h e s i z e du s i n gg e n e t i ca l g o r i t h mi sm o r e e x c e l l e n tt h a nw h i c ho ft r a d i t i o n a lm e t h o d ，a n dw h e nt h ea r r a ya m o u n ti sl a r g e ro r t h ep a t t e r nf u n c t i o ni sm o r ec o m p l i c a t e d , t h es u p e r i o r i t yi sm o r eo b v i o u s 。 a l a i r d l y ，t h ep a t t e mf u n c t i o no fa n t e n n aa r r a yi st r a n s f o r m e dt od i s c r e t ef o r m t h r o u g hs a m p l i n gt op a t t e mf u n c t i o no fa n t e n n aa r r a y , ad i s c r e t ef u n c t i o ni s g a i nw h i c hi sa d a p t e dt oc o m p u t e ro p e r a t i n ga n dg e n e t i ca l g o r i t h m c i r c u l a t o r y o p e r a t i o n i s r e p l a c e db ym a t r i x e s p r o d u c t , w h i c ha d v a n c e se f f i c i e n c yo f c o m p u t i n g k e yw o r d s ：g e n e t i ca l g o r i t h m ( g a ) ；p a t t e r ns y n t h e s i s ；a r r a ya n t e n n a 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导 下，由作者本人独立完成的。有关观点、方法、数据和文 献等的引用已在文中指出，并与参考文献相对应。除文中 己经注明引用的内容外，本论文不包含任何其他个人或集 体已经公开发表的作品成果。对本文的研究做出重要贡献 的个人和集体，均已在文中以明确方式标明。本人完全意 识到本声明的法律结果由本人承担。 作者( 签字) ： 楹邀 日期：溯年7 月3 矽e t 哈尔滨工程大学硕士学位论文 第1 章绪论 1 1 课题研究背景及目的 随着无线通信技术的飞速发展，可用频谱资源越来越有限，如何优化通 信系统资源配置和提高资源利用率成为无线通信进一步发展的关键问题。智 麓天线技术就是在这一背景下应运面生的遥信领域关键技术之一。智能天线 利用多个天线阵元组合进行自动调整发射和接收方向图，针对不同的信号环 境实现系统参数选择的最优化。在移动通信等现代通信系统中，智能天线发 挥着越来越重要的作用，而方向图综合技术正是智能天线的一项核心技术。 阵列天线方向图综合是指按规定的方向图要求，用一种或多种优化方 法进行天线系统的设计，使该系统产生的方离匿与所要求的方向罄良好逼近。 它实际上是天线分析的反设计，即给定期望方向图，设计阵列天线相关参数。 阵列天线方向图综合设计参数包括：阵列单元数目、阵元分布形式、阵元间 距、各阵元激励幅度和相位。在阵元的分布形式和阵元数目都给定的情况下， 控制阵元闻距以及激励的幅度和相位分布就可以改变辐射特性，例如，主瓣 形状、副瓣电平、零陷生成等p 1 。 隧着通信技术的迅猛发展，对阵列天线方向图的要求也越来越高，越来 越多的优化技术被应用到方向图综合中，并在一定程度上取得了诸如获得窄 的扫描波束、抑制旁瓣电平到一个较低值、较好的控制了零点生成等可观的 优化效果，但寻找能取得更优方向图的优化技术仍然是阵列天线方向圈综合 的一个重点。 在一些实际应用中，例如，雷达天线及卫星天线，动辄需要上千、上万 个单元，而且为改善天线阵方向性还须采用幅度相位加权，将导致阵列的馈 电网络非常复杂，甚至难以实现州。此时改变其布阵方式的就是一个很好的 选择，即采用稀疏阵列来解决这一问题，实现用较少的阵元数量达到技术指 标，并且大大降低了生产成本。但阵列的周期性交稀会使方向图出现j # 常 哈尔滨工程大学硕士学位论文 誓islsli i i i h 一 i i i i i i 黼葺暑葺宣蛊 高的副瓣，如何抑制稀疏阵列的副瓣电平到设计允许范围内成为了一项关键 技术。 1 2 国内外研究现状 1 2 1 传统方向图综合方法 阵列天线方向图综合润题是阵列天线设计的核心闻题，综会方法很多并 且发展迅速。现在被公认且较有用的天线综合方法可分为以下四类： 第一类综合问题，是根据已给出的对主瓣宽度和旁瓣电平的要求，或指 定方向图的零点位置，来确定阵因子中四个变量中的某几个( 例如，辐射元 的数日、辐射元上的激励幅度) ，面其余的参量俸为菲变量，对方向图的其它 细节和方向性系数没有具体规定。常见的方法有d i o l p 辩c h e b y 虫e v 网综合法和 t a y l o r t 明综合法。d o l p h - c h e b y s h e v 综合法是利用c h e b y s h e v 多项式的性质， 在给定的副瓣相对电平条件下能够得到最窄的主瓣宽度，或者在给定第一零 点主瓣宽度条件下，获得最低副瓣相对电平，且是等副瓣的。t a y l o r 综合法 是对c h e b y s h e v 多项式进行适当靛修正，使其两大振幅区域合并为方向圈主 瓣，丽副瓣则在由c h e b y s h e v 多项式控制的基础上再加一衰减爱数形成。 d o l p h - c h e b y s h e v 综合法多用于离散阵的综合，t a y l o 综合法则即可用于离散 线阵，也可用于连续阵的综合问题，但当阵列天线规模很大或者形状很复杂 时，以c h e b y s h e v 和t a y l o r 法为代表的经典解析优化方法难以计算h 锄。 第二类综合闻题是要求达到预先指定的方向图形状。综合过程主要是确 定必要的单元数旦、闻距分布和激励i 以便获得最好的可实现的阵因子。用 综合的阵因子代替预期的方向图时带来的均方差或最大误差应当是最小的。 传统的波束赋形方法有傅立叶变换法、w o o d w a r d l a w s o n 法等。傅立叶变换 法的原理是阵列单元的激励幅度与其产生的阵列函数构成一对傅立叶变换， 对裳望的方向图进行反傅立叶变换就可得到各单元的激励系数，该方法要求 阵列函数( 阵因子) 满足周期性条彳孛。因为理想的傅立叶变换需无限线源， 2 哈尔滨工程大学硕士学位论文 而实际中不可能实现，文献 1 1 1 提出了用窗函数进行改进的方法，加窗后的 傅立时交换性能有缀大改善。w o o d w a r d l a w s o n 法是1 9 4 8 年由w o o d w a r d 和l a w s o n 提出的，他们弓l 入了一系列正交波束，每个波束的加权值等于所 要求的方向图在对应采样点处的幅度。利用此方法可以对连续线源和离散线 阵进行综含。文献【1 2 】利用样本函数的性质对w o o d w a r d l a w s o n 法进行了改 进，提出的w - s 法用较少的单元就可以综合相同效果的方向图，或者在单元 数星掏同时，w - s 法综合的方向图更接近样本蘧数，且天线的波瓣交窄，增 益较高。傅立叶变换法综合的方向图与所要求的方向图之间的均方误差最小， w o o d w a r d l a w s o n 法综合出的方向图在抽样点上的值与所要求的方向图完全 一致，而在抽样点之间对方向图没有任何控制，因而不会具有最小均方的方 向图，得粥的结果一般在主瓣区波纹系数较大，副瓣的高度也不能得到很好 的控制。但是w o o d w a r d - l a w s o n 法更加灵活，理论上可以综合任意所需要的 方向图，包括实测结果，不论是模拟形式或数字形式的都可以。 第三类综合问题是从已知的方向图出发，通过微变遥近指定的方向图指 标，通常称为徽扰法。文献 1 3 1 介绍的微扰法是从己知的方向图出发，逐步 地改变辐射单元闻距和激励幅度，达到所需要韵方淘鹰指标。 第四类综合闽题是阵列天线参数的最优化设计。天线参数的最优化设计 经常采用数值分析法。 在天线方向图综合中，传统解析的方法虽然计算简单，但适用范围窄， 在实际工程中，由于天线阵分布的随意性以及各阵列单元方向图的任意性， 很难翻用上述解析的方法进行计算，因而通常采用数值计算方法。数值方法 可以综合出很多解折方法蹶不能综合的复杂方自图，丽且在改善波束性能上 也有很大的优势。用数值优化的方法进行方向图综合的主要任务是建立数学 模型，构造合适的目标函数。由于方向图综合问题中的目标函数或约束条件 大部分呈多参数、非线性、不可微甚至不连续，基于梯度寻优技术的传统数 值优化方法无法有效地求得工程满意解，因此逶常选择壹接优亿方法对天线 方向图进行设计。经典的壹接优化方法的效率对初始蠖的依赖性很强，使用 3 哈尔滨工程大学硕士学位论文 不同的初始值，运用不同的方法构造新的搜索方向，最终计算的效率会有很 大的差别。 1 2 2 智能优化方法 近年来，随着高速计算机技术的发展，智能优化算法显示出其独有的优 势。其中遗传算法( g e n e t i ca l g o r i t h m ，简称g a ) 是研究最为广泛深入的一 种智慧优化算法，其固有的鲁棒性强、适应范围广和具有势行计算能力等特 点，可以在复杂多模空间搜索寻优，成为电磁计算领域问题求解的有效工具， 在电磁学和天线领域得到了广泛的应用 遗传算法最早由美国m i c h i g a n 大学的h o l l a n d 教授于二十世纪七十年代 初提出的，随后隗如鸳将其扩展到了最优化数值函数计算的应用中。遗传 算法利用物竟天择，优胜劣汰，适者生存的自然选择，交叉、变异的遗传机 理形成一种求解多变量复杂问题的高效并行全局搜索方法，在搜索过程中， 自动获得和积累有关搜索空间的知识，自适应的控制搜索过程以求得最优解。 遗传算法作为一种模拟生物体迸化的随机搜索算法，遥几年来在闯题求 解，优化和搜索，机器学习，系统控制和模式识剐等领域得到广泛的应用， 并且取得了很大的成榭悱啪。a l d e n w r i g h t 二十世纪九十年代初对十进制遗传 算法进行了有益的研究。在遗传算法的并行处理，适应各种问题的编码方案 的设计等方面都有了深入而有益的研究和应用。 1 9 9 4 年，j m i c h a e lj o h n s o n 和y a h y ar a h m a t - s a m i i 首次将基本遗传算法 应用到天线综合中刚，并说明了用基本遗传算法进行阵列综合的基本方法， 阐明了用遗传算法综合一维和二维均匀及j 均匀阵列的可行性。同年，r a n d y l h a u p t t 2 u 用遗传算法以获取最低旁瓣电平为目标对阵元数为2 0 0 的线形阵 和平面阵分别进行了优化，得到了低于- - 2 0 d b 的旁瓣电平，提供了用遗传算 法进行阵列综合的一般方法。此后遗传算法被不断地应用到天线阵综合闽题 中，如y a n 瞄1 等采用遗传算法来抑制最大旁瓣电平，t e n n a n t 等人利用遗传算 法控制阵元位置、激励相位进行方向图零点生成伽。 4 哈尔滨工程大学硕士学位论文 1 3 本文的主要工作 本文将遗传算法应用到阵列天线方向圈综合中，主要就以下几个方面的 内容进行了研究： l 。详细研究了一个基于遗传算法的阵列天线综合阀题中通用的嗣标函 数，该通用目标函数： ( 1 ) 包括了主瓣位置控制、最高旁瓣抑制和零点生成： g ) 具有可扩展性，如果需要增加新的指标，只需要在目标函数的表达 式后添加即可。 2 采用遗传算法优化阵元间距、激励的幅度和相位这三个参量，使 | 导优 化后的方向图满足： ( 1 ) 抑制最大相对旁瓣至指定值内和超低副瓣； ( 2 ) 在指定角度生成指定零深的零陷； 0 ) 同时包含主瓣宽度抑制、旁瓣抻制和零深抑制指标。1 3 对阵列天线方向图函数进行进一步的推导，得到了离教化的阵列天线 方向图函数，使之适合计算机及遗传算法的运行，提高了计算和算法的搜索 效率。 4 采用遗传算法综合稀疏阵列方向图，采用了一种基于标志位的规茭| j 槠 格稀疏阵列模型，并在其基础上对不同布满率的稀蔬直线阵进行了综合，降 低最大相对旁瓣。 5 提出了一种基于遗传算法的唯幅控制阵列天线方向图零点生成的方 法，通过仿真，与唯相控制阵列天线方向圈零点生成做了比较。 本文共分4 章，各章主要内容安排如下： 第l 章，绪论部分分缨了天线阵方向圈综合的研究背景秘意义，简单介 绍了天线阵综合的经典综合方法和以及新算法的应用，重点介绍了遗传算法 的应用发展状况，最后介绍了本文的主要工作及章节安排。 第2 章，介绍了遗传算法的生物学基础，对遗传算法的特点进行了简介； 5 哈尔滨工程大学硕士学位论文 重点介绍了遗传算法的基本实现技术，并给出了其实现流程。 第3 章，会绍了基于遗传算法的阵列天线综合。酋先给出了线阵和矩形 蘑阵及其方向图函数公式，并且在此基础上结合遗传算法，给出了阵列天线 综合的遗传算法模型。详细介绍了一个基于遗传算法的阵列天线方向图综合 问题中通用的目标函数，该通用目标函数中包括了主瓣位置控制、最高旁瓣 抑制和零点生成。另外该通用目标函数还其有可扩展性，如果需要增加新的 指标，只需要在霉标函数的表达式后添加馨可。 第4 章，首先采用遗传算法对阵列天线进行综合，针对直线阵和矩形面 阵，讨论了超低副瓣天线阵的综合，取得了很好的优化效果；在对阵列天线 方向图函数进行分析的基础上，充分考虑到在计算机仿真过程中，连续的方 向图需要离散化后再参加运算，因此对阵列天线方向圈函数进行进一步的推 导，使之适合计算机及遗传算法的运行，并且在离散化方向蓥的基础上，讨 论了对阵列天线的零点生成，并分别采用对激励的幅度控制和相位控制，在 方向图的指定位置生成了到达指定零深的零点；最后对稀疏直线阵进行了综 合，分别对阵布满率7 1 和7 7 的稀疏直线阵进行遗传优化，均有效的抑制 了其最大副瓣。 6 嗡尔滨工程大学硕士学盘论文 第2 章遗传算法 2 1 遗传算法的生物学基础 生物在自然界中的生存繁衍，显示出了其对自然环境的优异自适应能力。 受其启发，人们致力于对生物各种生存特性的机理研究和行为模仿，为入工 自适应系统的设计和开发提供了广阔的前景。遗传算法( g e n e t i ca l g o r i t h m s 简称g a s ) 就是这种生物行为的计算机模拟中另人瞩目的重要成果。基于对 生物遗传和进化过程的计算机模拟，遗传算法使得各种人工系统具有优良的 自适应能力和优化能力。遗传算法所借鉴的生物学基础就是生物的遗传和进 化。 2 1 1 遗传与变异 世间的生物从亲代继承特性或性状，这种生命现象称为遗传( h e r e d i t y ) ， 研究这种生命现象的科学嚣鹰做遗传学( g e n e t i c s ) 。由于遗传的作用，使得人 们可以神瓜褥瓜、种豆褥豆、也使得鸟仍然是在天空中飞翔，鱼仍然是在水 中邀游。 构成生物的基本结构和功能单位是细胞( c e l l ) 。细胞中含有的一种微小 的丝状化合物称为染色体( c h r o m o s o m e ) ，生物的所有遗传信息都包含在这 个复杂焉又微小的染色俸中。遗传信息是由基嚣( g e n e ) 组成的，生物的各 种性状壹其相应的基因所控制，基因是遗传的基本单位。细胞通过分裂具有 自我复制的能力，在细胞分裂的过程中，其遗传基因也同时被复制到下一代， 从而其性状也被其下一代所继承。经过生物学家的研究，现在人们已经明白 控制并决定生物遗传性状的染色体主要是e l j 一种叫做脱氧核糖核酸 ( d e o x y r i b o n u c l e i ca c i d ，简称d n a ) 的物质骈构成，除此之外，染色体中 还含有很多蛋白质。d n a 在染色体中有规则地排列着，它是个大分子的有机 聚合物，其基本构成单位是核苷酸。每个核苷酸由四种称为碱基的环状有机 7 喻尔滨工程大学硕士学位论文 化合物中静一种、一分子戊糖和磷酸分子所组成。许多核蓄酸通过磷酸二酯 键相结合形成个长长的链状结构，两个链状结构再通过碱基间的氢键有规 律的扭合在一起，相互卷曲起来形成一种双螺旋结构。另外，低等生物中还 含有一种叫做核糖核酸( r i b o n u c l e i ca c i d ，简称r n a ) 的物质，它的作用和 结构与d n a 相似。基因就是d n a 和r n a 长链结构中占有一定位置的基本 遗传单位。生物的基因数量根据物种的不阉也多少不，小的瘸毒只含有几 个基因，而高等动植物的基因却以数万计。在d n a 中，遗传信息在条长 链上按一定的模式排列，亦即进行了遗传编码。一个基因或多个基因决定了 组成蛋白质的2 0 组氨基酸的组成比例及其排列顺序。遗传基因在染色体中所 占据的位置称为基因座( l o c u s ) ，同一基因座可能有的全部基因称为等位基 因( a l l e l e ) 。某种生物所特有的基因及其构成形式称为基医型( g e n o t y p e ) ， 而该生物在环境中呈现出的相应的性状称为该生物的表现型( p h e n o t y p e ) 。 一个细胞核中所有染色体携带的遗传信息的全体称为一个基因组( g e n o m e ) 。 细胞在分裂时，遗传物质d n a 通过复制( r e p r o d u c t i o n ) 而转移到新产 生的缨胞中，新细胞就继承了；霹细胞的基因。有幢生殖生物在繁殖下一代时， 两个同源染色体之间通过交叉( c r o s s o v e r ) 两重缰，亦即在两个染色体的某 一相同位置处d n a 被切断，其前后两串分别交叉组合而形成两个毅的染色 体。另外，在迸行细胞复制时，虽然概率很小，但也有可能产生某些复制差 错，从而使d n a 发生某种异变( m u t a t i o n ) ，产生出新的染色体。这些新的 染色体表现盘新豹性状。如此这般，遗传基因或染色体在遗传的过程中由于 各种各样的原因丽发生变化。 2 。王2 进化 生物在其延续生存的过程中，逐渐适应于其生存环境，使得其品质不断 得到改良，这种生命现象称为进化( e v o l u t i o n ) 。生物的进化是以集藿的形式 共同进化的，这样的一个团体称为群体( p o p u l a t i o n ) ，组成群体的单个生物 称为个体( i n d i v i d u a l ) ，每一个个体对其生存环境都有不同的适应能力，这 哈尔滨工程大学硕士学位论文 种适应能力称戈个体的适庞度( f i t n e s s ) 。达尔文( d a r w i n ) 的自然选择学说 ( n a t u r a ls e l e c t i o n ) 构成了现代进化论的主体。自然选择学说认为，通过不 同生物间的交配以及其他一些原因，生物的基因有可能发生变异而形成一种 新的生物挂凶，这部分变异了的基因也将遗传剑f 一代。虽然这种变化的概 率是可以预测的，但具体哪一个个体发生变化却是偶然的。这种新的基因依 据其与环境的适应程度决定其增殖能力，有利于生存环境的基嚣逐渐增多， 而不利于生存环境的基因逐渐减少。通过这种自然的选择，物种将逐渐的向 适应于生存环境的方向进化，从而产生出优良的物种。 2 1 3 遗传与进化的系统观 虽然人们还未完全揭开遗传与进化的奥秘，既没有完全掌握其机制，也 不完全清楚染色体编码和译码过程的细节，更不完全了解其控制方式，但遗 传与进化的以下几个特点却为人们所共识： 1 生物的所有遗传信息都包含在其染色体上，染色体决定了生物的性状。 2 染色体是壶基因及英有规律的排列所构成的，遗传和进化过程发生在 染色体上。 3 生物的繁殖过程是由其基因的复制过程来完成的。 4 通过同源染色体之间的交叉或染色体的变异会产生新的物种，使生物 产生新的性状。 5 对环境适应性好的基因或染色体经常比适应性差的基嚣或染色体有更 多的机会遗传到下一代。 2 2 遗传算法概述 模拟生物界中自然选择和群体遗传机制的遗传算法，采用麓单的编码技 术来表示各种复杂的结构，：并通过对一组编码表示进行简单的遗传操作和优 胜劣汰的自然选择来指导学习和确定搜索的方向。由于它采用种群的方式组 织搜索，这使得它可以同时搜索解空间内的多个域，而且用种群组织搜索的 9 哈零滨工程大学硕士学位论文 i mi l l li i l l l 警；宣i i ；眷薯葺宣昌宣高黧葺暑；警赫i ；盏眷嗣置宣昌宣薯 方式使撂它特别适合大规模并纾。医此它能够解决许多常规方法尚无法处理 的复杂优化问题。 2 。2 。l 遗传算法的运算流程 遗传算法模拟了自然选择和遗传中发生的复制、交叉和变异等现象，从 任一初始种群( p o p u l a l i o n ) 出发，透过随机选择、交叉和变异操作，产生一 群更适应环境的个体，使群体进化到搜索空间中越来越好的区域，这样一代 一代地不断繁衍进化，最后收敛到一群最适应环境的个体( i n d i v i d u a l ) ，求 得问题的最优解。 遗传算法的运算流程包括编码、初始群体生成、适应度值评价检测、选 择、交叉、变异六部分，下面分别做篱要的介绍。 1 编码：解空间的解数据x ，作为遗传算法的表现型形式。从表现型到 基因型的映射称为编码。遗传算法在进行搜索之前先将解空间的解数据表示 成遗传空间的基因型串结构数据，这些串结构数据的不同组合就构成了不同 的点。 2 。初始群体的生成：随机生成个串结构数据，每个串结构数据称为 一个个体，个个体构成一个群体。遗传算法以这个串结构作为初始点开 始迭代。设置进化代数计数器，= 0 ；设置最大进化代数丁；随机生成个个 体作为初始群体p ( o ) 。 3 。适应度僮评价检测；适应度番数表明个体或解的优劣性。对于不同的 问题，适应度函数定义的方式不同。根据具体的问题，计算群体尹( f ) 中各个 个体的适应度。 4 选择：将选择算子作用于群体，根据适应度函数值的大小，选取适应 度嵩的个体进行下一步的搡作。 5 。交叉：将交叉算子作用于群体，交叉操作以交叉概率随机选取群 体中的个体在随机生成的位置进行交叉。 6 变异：将变异算子作用于群体，变异操作以变异概率己，随机选取 l o 噙尔滨工程大学硕士学位论文 个体中的基于霞进行变异，得到薪的个体。 根据上述的流程，可以观察得出遗传算法存在初始种群个数，交叉概 率只和变异概率乞这三个关键参数，这三个关键参数有如下的确定规则口q ： 1 初始群体规模 一 群体规模影响遗传优化的最终结果以及遗传算法的执行效率。当群体规 模太小时，遗传算法韵优化魏能一般不会太好，丽采用较大的群体觏模则 可减少遗传算法陷入局部最优解的机会，但较大的群体规模意味着计算复杂 度高。一般取从1 0 到1 6 0 之间。 2 交叉概率只 交叉概率e 控制着交叉操作被使用的频度。较大的交叉概率可增强遗传 算法开辟新的搜索送域的能力，僵高性能的模式遭到破坏的可毙性增大；若 交叉概率太低，遗传算法搜索可能陷入迟钝状态。一般取值从0 。2 5 到1 o o 之间。 3 变异概率己 变异在遗传算法中属予辅助性的搜索操作，它的主要目的是维持解群体 的多样性。一般，低频度的变异可防止群体中重要的、单一基因的可能丢失， 高频度的变异将使遗传算法趋于纯粹的随机搜索。通常取变异概率为0 。0 0 1 左右。 2 。2 2 遗传算法的特点 遗传算法具有如下优点： 1 对可行解表示的广泛性。遗传算法处理的对象不是参数本身，而是针 对那些通过参数集进行编码得到的基因个体。此编码操作使得遗传算法可以 直接对结构对象进行搡作。 2 。群体搜索特性。许多传统的搜索方法都是单点搜索，这种点对点的搜 索方法，对于多峰分布的搜索空间常常会陷于局部的某个单峰的极值点。相 反，遗传算法采用的是同时处理群体中多个个体的方法，即同时对搜索空间 哈尔滨互程大学硕学位论文 孛的多个解进行评信。这一特点使遗传算法具有较好麓全局搜索性能，也使 得遗传算法本身易于并行化。 3 不需要辅助信息。遗传算法仅用适应度函数的数值来评估基因个体， 并在此基础上进行遗传操作。更重要的是，遗传算法的适应度函数不仅不受 连续可微的约束，而且其定义域可以往意设定。对适应度函数的唯一要求是， 编码必须与可行解空间对应，不能育死码。由于限制条件鲶缩小，使得遗传 算法的应用范围大大扩展。 4 内在的启发式随机搜索特征。遗传算法不是采用确定性规则，而是采 用概率的变迁规则来指导它的搜索方向。 5 遗传算法在搜索过程中不容易陷入局部最优，即使在所定义的适应度 丞数是不连续的、非规则的或有噪声的情况下，也能以很大的概搴找到全局 最优解。 6 遗传算法采用自然进化机制来表现复杂的现象，能够快速可靠的解决 求解非常困难的问题。 7 遗传算法具有固有的并行性和并行计算的能力。 8 遗传算法具有可扩展的熊力，易于同别的技术结合起来使用。 同时遗传算法也具有如下不足之处： 1 编码不规范及编码存在表示的不准确性。 2 单一的遗传算法编码不能全面的将优化问题的约束表示出来。考虑约 束的一个方法就是对不可行解采用阂值，这样，计算的时闻必然增加。 3 遗传算法通常的效率比其他传统的优化方法低。 4 遗传算法容易出现过早收敛。 5 遗传算法对算法的精度、可信度、计算复杂性等方面还没有有效的定 量分析方法。 2 2 3 遗传算法的基本操作 遗传算法具有三个基本操作：选择( s e l e c t i o n ) ，交叉( c r o s s o v e r ) 和变 1 2 晗尔滨工程大学硕士学盈论文 异( m u t a t i o n ) l 。选择。选择的圈的是为了从当前的群体中选出优良的个体，使它们有 机会作为父代为下一代繁衍子孙。根据个体的适应度傻，按照一定的规则或 方法从上一代群体中选择出一些优良的个体遗传到下一代群体中。遗传算法 通过选择运算体现这一思怒，进行选择的原则是适应往强的个体为下一代贡 献一个和多个震代的概率大。这样就体现了达尔文的适者生存原英| l 。 2 交叉。交叉操作是遗传算法中最主要的操作。通过交叉操作可以 | 导到 新一代个体，新个体组合了父辈个体的特征。将群体内的各个个体随机搭配 成对，对每一个个体，以交叉概率( c r o s s o v e rr a t e ) 只交换它们之间的部分 染色体。交叉体现了信息交换的思想。 3 变异。变异操作首先在群体中选择一个个体，对于选中的个体以变异 概率圪随机改变串结构数据中某个串的值，即对群体中的每一个个体以变异 概率( m u t a t i o nr a t e ) 改变某一个或某一些基因座上的基因值为其他的等 位基因。同生物界一样，遗传算法中变异发生的概率很低。变异为新个体的 产生提供了机会。 2 2 4 标准遗传算法 标准遗传算法( 也称为基本遗传算法或简单遗传算法，s i m p l eg e n e t i c a l g o r i t h m ，简称s g a ) 是一种群体型操作，该操作以群体中的所有个体为对 象，只使鬻基本的遗传算子( g e n e t i co p e r a t o r ) - 选择算子( s e l e c t i o no p e r a t o r ) ， 交叉算子( c r o s s o v e ro p e r a t o r ) 秘变异算子( m u t a t i o no p e r a t o r ) 。其遗传进 化操作过程简单，容易理解，是其他遗传算法的基础，它不仅给其他遗传算 法提供了一个基本框架，同时也具有一定的应用价值。选择、交叉和变异是 遗传算法的3 个主要操作算子，他们构成了遗传操作，使遗传算法具有了其 他算法没裔的特点。 下面描述s g a 的数学模型。 s g a 可表示为： 晗尔滨工程大学硬士学位论文 s g a = ( c ，e e o ，l 髫，f )( 2 1 ) 其中：c 个体的编码方法； e 个体适应度评价函数； 异初始种群； 种群大小； 选择算子； i 交叉算子； 甲褒异算子； 丁遗传算法叠代终止条件。 下图为s g a 的流程图： 图2 1s g a 流程图 2 3 遗传算法的基本实现技术 遗传算法的每一步都与所求解的闻题紧密相关，对于具体的阕题，采用 合适的方法，有利于简化遗传算法，加速遗传算法收敛的功能。下面对遗传 算法根据具体问题的实现技术作简单的介绍。 1 4 晗尔滨工程大学硕士学位论文 2 3 1 编码 编码是遗传算法首先要解决的问题，也是设计遗传算法的一个关键步骤。 在遗传算法执行过程中，对不同的具体问题进行编码，编码的好坏直接影响 选择、交叉、变异等遗传运算。下面介绍a 种常用的编码方法。 l 。二进制编码 二进制编码方法是遗传算法中最主要的一种编码方法，它使用的编码符 号集是由二进制符号。和1 组成的二值符号集 o ，l ，它所构成的个体基因型 是一个二进制编码符号串。二迸制编码符号串的长度与问题所要求的求解精 度有关。 2 。格雷玛编码 使用格雷码编码方法对整数进行编码，连续的两个整数对应的编码之间 仅有一个码位是不同的，其余码位都相同。格雷码编码方法是二进制编码方 法的一种变形。 3 浮点数编码 对于一些多维、高精度要求的连续函数优化问题，使用浮点数编码。所 谓浮点数编码，是指个体的每个基因值使用某一范围内的浮点数来表示，个 体的编码长度等于其决策变量的个数。浮点数编码方法也叫实数编码方法。 4 多参数级联编码 对含有多个变量的个体进行编码的方法就称为多参数级联编码方法。多 参数级联编码最常用也是最基本的一种方法是：将各个参数分别以某种方法 进行编码，然后再将它们的编码按照一定的顺序连接在一起就组成了表示全 部参数的个体编码。 2 3 2 适应度函数及其尺度变换 遗传算法在进化搜索中基本不利用外部信息，仅以适应度函数作为区分 种群个体好坏的标准。一般而言，适应度函数是由目标函数变换而来的。因 哈尔滨工程大学硬士学位论文 就，适应度函数选择的好坏壹接影响葬法的优劣，季| 入适应僮调节和资源共 享策略可以加快收敛速度和跳出局部最优点。对适应傻进行调节就是通过变 换来改变原适应值的比例关系，常用的比例关系有线性变换，幂函数变换和 指数变换等姗。 个体适应度函数( f i t n e s sf u n c t i o n ) 通常是目标函数的一个变换。若目标 丞数为最小化闷题，则 f i t ( f ( x ) ) = 篡八曲 卜( 2 - 2 ) 其中，f ( x ) 为目标函数，为舀标舔数的最大值估计，f i t ( f ( x ) ) 为适应值。 若譬标函数为最大化阀题，则 f i t ( f ( x 峨f ，( p x 娩) - l 侧 。( 2 - 3