（无线电物理专业论文）遗传算法研究、程序实现及其在天线研究中的应用.pdf

电子科技大学硕士学位论文 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名： 三土：列逐 日期：可_ 年s - b ，日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：蝉导师签名 - 日期：沙巧年歹月日 电子科技大学硕士学位论文 摘要 本文首先研究了遗传算法的基本概念、特点和发展进展，介绍了本人编成的 遗传算法程序，并应用一些在评估遗传算法性能时经常用到的测试函数对该遗传 算法程序进行了性能评估。 还详细介绍了本人对新的遗传操作算子( 跳变基因算子- j u m p i n gg e n e s ) 所进行的理论分析：用模式定理讨论了模式在跳变基因算子作用下的生存概率问 题，为跳变基因算子在遗传算法程序中的合理应用提供指导；对杂交算子、变异 算子和跳变基因算子进行了比较，简单说明了引进跳变基因算子的好处。 在遗传算法的工作基础上，结合遗传算法和高频仿真软件( h f s s ) 的各自 特点，本文提出了一种适用于对微波无源结构进行仿真优化的方案，并将其编成 一个优化程序。应用该优化程序，对几个实际例子进行仿真优化，证明了本文所 提出的优化方案是可行和有效的。 最后，还介绍了本人所设计的两种微带天线：一种是可实现半空间四个波瓣 扫描的x 形方向图可重构微带天线，通过改变其四个微机电开关的不同工作状 态，使天线辐射场的主瓣方向发生改变；另一种是具有大于8 0 的阻抗带宽的 宽带微带天线，其应用双谐振和其他有利于提高阻抗带宽的办法，使天线的阻抗 带宽得到提高。 关键词：遗传算法：跳变基因；高频仿真软件；宏命令；可重构天线 宽带天线 电子科技大学硕士学位论文 a b s t r a c t f i r s t ，t h ep a p e ri n t r o d u c e st h eb a s i cc o n c e p t s ，t r a i t sa n dr e c e n td e v e l o p m e n to f g e n e t i ca l g o r i t h m ag e n e t i cp r o g r a mi sd e v e l o p e d ，a n di t se v a l u a t i o nr e s u l t sa l ea l s o g i v e n a tt h es a r n et i m e ，r e s e a r c ho nj u m p i n gg e n e s ，an e wg e n e t i co p e r a t o r , i sp r e s e n t e d i ti su s e f u lf o rt h er e a s o n a b l ea p p l i c a t i o no f j u m p i n gg e n e si ng e n e t i cp r o g r a m s t h e c o m p a r i s o na m o n gc r o s s o v e r , m u t a t i o na n dj u m p i n gg e n e si s d o n ea n de x p l a i n s s i m p l yw h y t oi n t r o d u c ej u m p i n gg e n e si ng e n e t i ca l g o r i t h m b a s e do nt h ew o r ka b o u tg e n e t i ca l g o r i t h m ，a no p t i m i z a t i o ns c h e m e ，t h a ti ss u i t e d f o rt h e s i m u l a t i o no p t i m i z a t i o no fp a s s i v em i c r o w a v es t r u c t u r e ，i sp r o p o s e da c c o r d i n g t ot h et r a i t so fg e n e t i ca l g o r i t h ma n dh i g hf r e q u e n c ys i m u l a t i o ns o f t w a r e ac o d e b a s e do nt h i so p t i m i z a t i o ns c h e m eh a sb e e nd e v e l o p e d s e v e r a lp r a c t i c a le x a m p l e sa r e o p t i m i z e db yt h eo p t i m i z a t i o nc o d e ，a n dt h eo p t i m i z a t i o nr e s u l t s s h o wt h a tt h e o p t i m i z a t i o ns c h e m ei sf e a s i b l ea n d e f f e c t i v e a tl a s t ，t w ok i n d so fa n t e n n a sd e s i g n e db ym y s e l fa r ei n t r o d u c e d o n ei sn a m e da s p a t t e r nr e c o n f i g u r a b l em i c r o s t i r pa n t e n n aw i t hxc o n t o u r f o u rs w i t c h a b l ed i r e c t i o n a l p a t t e r n sa r ea c h i e v e db yc h a n g i n gt h ec o n n e c t i o ns t a t e so f t h ef o u rm e m ss w i t c h e s t h eo t h e ri sn a m e da sw i d e b a n dm i c r o s t f i pa n t e n n a i t si m p e d a n c eb a n d w i d t hi s b e y o n d8 0 k e yw o r k s ：g e n e t i ca l g o r i t h m ；j u m p i n gg e n e s ；h i g hf r e q u e n c ys i m u l a t i o n s o f t w a r e ；m a c r ol a n g u a g e ；r e e o n f i g u r a b l ea n t e n n a ；w i d e b a n da n t e n n a 4 电子科技大学硕士学位论文 1 1 工作背景 第一章引言 现代科学理论研究与实践中存在着大量与优化、自适应相关的问题，除了一 些简单的情况，人们对于大型复杂系统的优化和自适应问题仍然无能为力【l 】。本 课题组在仿真设计中，也碰到了许多需要优化的实际问题，而应用一般的软件却 很难得到一个令人满意的结果，所以急需开发具有强优化能力的优化软件。 自然界中的生物在复杂环境的生存问题上表现出了优异的能力，它们能够以 优胜劣汰、适者生存的自然进化规则生存和繁殖，并逐步产生出对其生存环境适 应性很高的优良物种。遗传算法正是借鉴生物的自然选择和遗传进化机制而开发 的一种全局优化自适应概率搜索算法。隐含并行性和对全局信息的有效利用能力 是遗传算法的两大显著特点，前者使遗传算法只需检测少量的结构就能反映搜索 空间的大量区域，后者使遗传算法具有稳健性【1 ，2 】。遗传算法己被众多领域的学 者应用到实际问题的优化中 3 - s ) ，比如天线结构、能量流动问题、最佳路径、布 局方式等优化问题，说明遗传算法具有很强的实用性。 遗传算法是新发展起来的- - 1 7 学科，各种理论 9 , 1 0 川、方法尚未成熟，有待 于进一步的发展和完善，但它却为我们解决许多复杂问题提供了希望。尽管在遗 传算法的研究和应用过程中会出现许多难题，同时也会产生许多不同的算法设计 观点 1 2 , 1 3 , 1 4 ，然而，目前遗传算法的各种应用实践已经展现出了其优异的性能和 巨大的发展潜力，它的发展前景激励着各类专业技术人员把遗传算法的理论和方 法应用到自己的工作实践中。随着研究工作的进一步深入和发展，遗传算法必将 在智能计算领域中起到关键作用。 高频仿真软件( h f s s ) 是适用于射频、无线通信、封装及光电子设计的任 意形状三维电磁场仿真软件，是业界公认的三维电磁场标准仿真软件包，为下一 代射频、无线通信、封装及光电子产品新功能的开发提供了崭新高效的研究手段。 h f s s 已被许多设计工程师广泛应用于天线、波导、谐振腔、滤波器等领域的仿 真设计，并得到了与实际产品性能较为符合的计算结果，从而证明了h f s s 的准 确性。 1 2 本工作的意义 本论文的研究工作主要包括：遗传算法、基于遗传算法和h f s s 的优化方 案及程序实现、以及微带天线设计。 电子科技大学硕士学位论文 本工作的意义在于以下几个方面： 1 对遗传算法进行了大量的调查和研究工作，并编写遗传算法程序，为以后 将遗传算法应用于实际的优化工作提供了有力的帮助，并为后续工作奠定 了基础。 2 对新的遗传操作算子( 跳变基因算子- j u m p i n gg e n e s ) 进行理论分析， 为其在遗传算法程序中的正确及合理应用提供了指导，有助于整个遗传算 法程序性能的提高。 3 基于遗传算法和h f s s 的各自优点所提出的优化方案及编写的优化程序， 对本人及课题组的优化设计工作提供了很大的帮助，提高了工作效率。 4 对天线所进行的研究工作，为课题组以后的天线设计研究提供了有力的帮 助。 1 3 本文内容结构安排 第一章，主要介绍本文研究工作的相关背景及意义。 第二章，对遗传算法原理和高频仿真软件( h f s s ) 进行简要介绍。 第三章，介绍本人在遗传算法上的主要工作，包括本人编写的遗传算法程序 及其性能评估、以及本人对新的遗传操作算子( 跳变基因算子- j u m p i n gg e n e s ) 所做的理论工作。 第四章，介绍了本文基于遗传算法和h f s s 各自特点所提出的优化方案，并 依据该优化方案编写了优化程序。 第五章，给出优化程序的几个应用实例，验证本优化方案的可行性和有效性。 第六章，介绍了本人所设计并优化的两种不同类型的微带天线：x 形方向图 可重构微带天线和宽带微带天线。 第七章，结论。 电子科技大学硕士学位论文 第二章遗传算法及高频仿真软件( h f s s ) 的介绍 2 1 遗传算法 2 1 1 遗传算法简介 遗传算法是一种宏观意义下的仿生算法，它模拟的机制是一切生命与智能的 产生与进化过程。它通过模拟达尔文“优胜劣汰、适者生存”的原理鼓励产生好 的结构，通过模仿盂德尔遗传变异理论在迭代过程中保持已有的结构，同时寻找 更好的结构。 由于遗传算法具有思想简单、易于实现、应用效果明显等优点而被众多应用 领域所接受，并在自适应控制、组合优化、模式识别、机器学习、人工生命、管 理决策等领域得到了广泛的应用。遗传算法是一种不依赖于问题类型的通用算法 框架。 遗传算法是一类具有较强鲁棒性的优化算法，特别是对于一些大型、复杂非 线性系统，它表现出比其他传统优化算法更加独特和优越的性能。隐含并行性和 对全局信息的有效利用能力是遗传算法的两大显著特点，前者使遗传算法只需检 测少量的结构就能反映搜索空间的大量区域，后者使遗传算法具有稳健性m ”。 遗传算法使用群体搜索技术，通过对当前群体施加选择、杂交、变异等一系 列遗传操作，从而产生出新一代的群体，并逐步使群体进化到包含或接近最优解 的状态，其基本的思路如图2 1 所示。 图2 - 1 遗传算法的基本思路 在遗传算法中，将n 维决策向量x = k ，k r 用n 个记号x ( f = 1 “2 一， ) 所组成的符号串x 来表示： 电子科技大学硕士学位论文 x = x 】x 2 x 。j x = x 1 ，x 2 ，t 一，石。 7 把每一个x 看作一个遗传基因，它的所有可能取值称为等位基因，这样，x 就 可看作是由r 1 个遗传基因所组成的一个染色体。般情况下，染色体的长度是固 定的，但对一些问题也可以是变化的。根据不同的情况，这里的等位基因可以是 一组整数，也可以是某一范围内的实数值，或者是一个纯粹的记号。最简单的等 位基因是由0 或l 的符号串组成的，相应的染色体就可以表示为一个二进制符号 串。这种编码所形成的排列形式x 是个体的基因型，与它对应的x 值是个体的 表现型。通常个体的表现型和其基因型是一一对应的，但有时也允许基因型和表 现型是多对一的关系。染色体x 也称为个体x ，对于每一个个体x ，要按照一 定的规则确定其适应度。个体的适应度与其对应的个体表现型x 的目标函数值相 关联，x 越接近于目标函数的最优点，其适应度越大：反之，适应度越小口l 。 在遗传算法中，决策变量x 组成了问题的解空间。对问题最优解的搜索是 通过对染色体x 的搜索过程来完成的，从而所有的染色体x 就组成了问题的搜 索空间。 生物的进化是以集团为主体的。与此相对应，遗传算法的运算对象是由m 个个体所组成的集合，称为群体。与生物一代一代的自然进化过程相类似，遗传 算法的运算过程也是一个反复迭代过程，第t 代群体记作p ( t ) ，经过一代遗传和 进化后，得到第什1 代群体，它们也是由多个个体组成的集合，记作p ( 什1 ) 。这 个群体不断地经过遗传和进化操作，并且每次都按照优胜劣汰的规则将适应度较 高的个体更多地遗传到下一代，这样最终在群体中将会得到一个优良的个体x ， 它所对应的表现型x 将达到或接近于问题的最优解。 生物的进化过程主要是通过染色体之间的杂交和染色体的变异来完成的。与 此相对应，遗传算法中最优解的搜索过程也模仿生物的这个进化过程，使用遗传 操作算子作用于群体p ( t ) 中，进行下述遗传操作，从而得到新一代群体p ( t + 1 ) 。 选择：根据各个个体的适应度，按照一定的规则或方法，从第t 代群体p ( t ) 中选择出一些优良的个体遗传到下一代群体p ”1 ) 中。 杂交：将群体p “) 内的各个个体随机搭配成对，对每一对个体，以某个概 率交换它们之间的部分染色体。 变异：对群体p ( t ) q b 的每一个个体，以某一概率改变某一或某一些基因座 上的基因值为其他的等位基因。 遗传算法的运算过程如图2 2 所示。 电子科技大学硕士学位论文 ：遗话圭商解空间 ，、 琏堡( ! y 1 选择运算 士 杂交运算 个体评估 t jl 变异运算 土 ，一、 一解码l寸“葡 、莲体p “+ 】) 厂 fj 、 图2 2 遗传算法的运算过程示意 2 1 2 遗传算法的特点 为解决各种优化计算问题，人们提出了各种各样的优化算法，如单纯形法、 梯度法、动态规划法、分枝定界法等【2 】。这些优化算法各有各的长处，各有各的 使用范围，也各有各的限制。遗传算法是一类可用于复杂系统优化计算的鲁棒搜 索算法，与其他一些优化算法相比，它主要有下述几个特点： ( 1 ) 遗传算法以决策变量的编码作为运算对象。传统的优化算法往往直接 利用决策变量的实际值本身来进行优化计算，但遗传算法不是直接以决策变量的 值，而是以决策变量的某种形式的编码为运算对象。这种对决策变量的编码处理 方式，使得我们在优化计算过程中可以借鉴生物学中染色体和基因等概念，可以 模仿自然界中生物的遗传和进化等机理，也使得我们可以方便地应用遗传操作算 子。特别是对一些只有代码概念而无数值概念或很难有数值概念的优化问题，编 码处理方式更显示出了其独特的优越性。 ( 2 ) 遗传算法直接以目标函数值作为搜索信息。传统的优化算法不仅需要 利用目标函数值，而且往往需要目标函数的导数值等其他一些辅助信息才能确定 搜索方向。而遗传算法仅使用由目标函数值变换来的适应度函数值，就可确定进 步的搜索方向和搜索范围，无需目标函数的导数值等其他一些辅助信息。实际 电子科技大学硕士学位论文 应用中很多函数无法或很难求导，甚至根本不存在导数，对于这类目标函数的优 化以及组合优化问题，遗传算法就显示了其高度的优越性，因为它避开了函数求 导这个障碍。再者，直接利用目标函数值或个体适应度，也可使得我们可以把搜 索范围集中到适应度较高的部分搜索空间中，从而提高了搜索效率。 ( 3 ) 遗传算法同时使用多个搜索点的搜索信息。传统的优化算法往往是从 解空间中的一个初始点开始最优解的迭代搜索过程。单个搜索点提供的搜索信息 毕竟不多，所以搜索效率不高，有时甚至使搜索过程陷于局部最优解而停滞不前。 遗传算法从由很多个体所组成的一个初始群体开始最优解的搜索过程，而不是从 一个单一的个体开始搜索。对这个群体所进行的选择、杂交、变异等运算，产生 出新一代的群体，在这之中包括了很多群体信息。这些信息可以避免搜索些不 必搜索的点，相当于搜索了更多的点，这是遗传算法所特有的一种隐含并行性。 ( 4 ) 遗传算法使用概率搜索技术。很多传统的优化算法往往使用的是确定 性的搜索方法，即一个搜索点到另一个搜索点的转移有确定的转移方向和转移关 系，这种确定性往往也有可能使得搜索永远达不到最优点，因而也限制了算法的 应用范围。而遗传算法属于自适应概率搜索技术，其选择、杂交、变异等运算都 是以一种概率的方式来进行的，从而增加了其搜索过程的灵活性。虽然这种概率 特性也会使群体中产生一些适应度不高的个体，但随着进化过程的进行，新的群 体中总会更多地产生出许多优良的个体，实践和理论都已证明了在一定条件下遗 传算法总是以概率l 收敛于问题的最优解。当然，杂交概率和变异概率等参数也 会影响算法的搜索效果和搜索效率，所以如何选择遗传算法的参数在其应用中是 一个比较重要的问题。而另一方面，与其他一些算法相比，遗传算法的鲁棒性也 使得参数对其搜索效果的影响尽可能的低。 2 1 3 遗传算法的发展 经过多年的研究发展，出现了许多带有各自特点的遗传算法，大致上可以分 为以下几种： 1 传统的遗传算法 这类遗传算法是按照最基本的遗传算法步骤编写而成，其改进的地方是针对 特定的单个或多个遗传操作( 例如配对方式、杂交或变异等) 所进行的。 如：编码方式已经提出了二进制编码、格雷码编码、浮点数编码、符号编码 电子科技大学硕士学位论文 等；而杂交方式也提出了单点杂交、多点杂交、均匀杂交等。 结合多个遗传操作也提出了一些改进的方案。比如，一种基于合作机制的改 进型遗传算法，其特点是在产生下一代群体的过程中，同时采用自我变异复制模 块( s e l f - r e p r o d u c t i o nw i t hm u t a t i o n ) 和杂交变异模块( c r o s s o v e ra n d m u t a t i o n ) d s i ，结合淘汰选择技术，保证了群体的多样性，一定程度上提高了算 法对最佳个体的搜索能力和算法的可靠性。 2 并行的遗传算法 并行遗传算法大致包括如下几种类型： 实现个体适应度并行计算的遗传算法。这种算法只包括一个群体，只 是在群体适应度评估过程中，将群体分配到几个处理器中并行计算各 个个体的适应度值。 分域遗传算法。其最突出的特点是：具有一个空间结构的群体，是在 受限制的区域内对个体进行选择和配对【1 “。 分布式遗传算法。这种算法将一个群体分成几个类群，通过某种拓扑 结构实现各类群之间的连接，采用选择机制和迁移技术实现各类群之 间的相互作用，最终提高算法的搜索能力和效率邮l 。 此外还有尝试性的并行遗传算法、混合遗传算法等。 总之，各种类型的遗传算法都具有各自的特点，但彼此之间并不是完全独立 的，可以结合各种类型的算法提出新的方案。此外，遗传算法是一门新学科，还 有其未被开发的潜能，算法稳定性、结果可靠性、计算效率等各方面都还可以得 到不断的改善和提高。 2 2 高频仿真软件( s s ) 2 2 1 高频仿真软件( s s ) 简介 高频仿真软件( h f s s ) 是适用于射频、无线通信、封装及光电子设计的任 意形状三维电磁场仿真软件，其核心是业已证明的真正可靠、精确、快速的第六 代f e m 解算器，工程师完全可以相信利用h f s s 设计的产品性能与仿真结果是 一致的。 h f s s 是业界公认的三维电磁场标准仿真软件包，为下一代射频、无线通信、 封装及光电子产品新功能的开发提供了崭新高效的研究手段。h f s s 提供了一简 电子科技大学硕士学位论文 沽直观的用户设计界面以及精确自适应的场求解器，其拥有空前电性能分析能力 的功能强大的后处理器，能计算任意形状三维无源结构的s 一参数和全波电磁场。 h f s s 充分利用各种先进技术，如自动匹配网格产生及加密、切线向矢量有 限元、a l p s ( a d a p t i v el a n c z o sp a d es w e e p ) 和模式一节点转换( m o d e n o d e ) 等， 使工程师们可以在自己的电脑上利用有限元法( f e m ) 对任意形状的三维无源结 构进行电磁场仿真。h f s s 自动计算多个自适应的解决方案，直到满足用户指定 的收敛要求值。其基于m a x w e l l 方程的场求解方案能精确预测所有高频性能， 如散射、模式转换、材料和辐射引起的损耗等。 用高效的计算机虚拟模型取代费时费力的“c u t a n d t r y ”试验方法，可大大 缩短设计周期。仿真分析诸如天线、微波转换器、发射设备、波导器件、射频滤 波器和任意三维非连续性等复杂闯题，已简单化成只需画结构图、定义材料性能、 设置端口和边界条件。h f s s 自动产生场求解方案、端口特性和s 一参数。其s 一 参数结果可输出到通用的线形和非线形电路仿真器中使用。 h f s s 的自适应网格加密技术使f e m 方法得以实用化。初始网格( 将几何 子分为四面体单元) 的产生是以几何结构形状为基础的，利用初始网格可以快速 解算并提供场解信息，以区分出高场强或大梯度的场分布区域。然后只在需要的 区域将网格加密细化，其迭代法求解技术节省计算资源并获得最大精确度。必要 时还可方便地使用人工网格化来引导优化加速网格细化匹配的解决方案。 h f s s 采用高阶基函数、对称性和周期边界等方法，从而节省计算时间和内 存，进一步加大求解问题的规模并加速求解的速度。 总之，h f s s 利用其独特先进的白适应网格剖分和算法技术，通过合理优化 减少网格总数、节省单位网格的计算资源，同时充分利用6 4 位机的超大的r a m 容量，最终完成大规模问题和高精确度的电磁场求解仿真。 2 2 2 高频仿真软件( e n f s s ) 的宏命令 高频仿真软件( h f s s ) 的宏命令是一种能够重复完成相同或相似工作的快 速、有效的方法。像c 语言、f o r t r a n 语言等都有自己的语法一样，h f s s 的 宏命令使用的是其自身的语法。通过使用宏命令，能够很快的完成重复性工作、 创建和求解那些带有可变参量的问题( 比如模型尺寸或边界条件等) 肿】。 在三维问题的求解过程中，建立模型往往是虽麻烦的事情。一旦模型建立完 成，指定材料、赋边界条件和设置解的条件等工作相对来说是比较容易的，而求 解过程也只是c p u 的时间问题而已。返回画图界面重新画图是一个又费时间又 单调乏昧的工作，并且无法对变结构问题进行反复计算或优化，而h f s s 的宏命 电子科技大学硕士学位论文 令则提供了一个有效的解决办法。 h f s s 的宏命令的好处是能够根据所给出的一系列参数去描叙结构，建立一 个新的模型只需重新调用宏命令便可以了。通过宏命令，完全能够控制h f s s 完成建模、赋材料、指定边界、设定解的条件、运行计算模块、输出计算结果等 工作，也就是说，所研究的问题的宏命令一旦建立起来，程序就能一遍又一遍的 自行求解问题，完成各种类型的优化【l ”。 电子科技大学硕士学位论文 3 1 遗传算法程序 第三章遗传算法研究 在前一章中我们介绍了遗传算法的基本原理，本节将介绍一个具有较强通用 性的遗传算法程序。该程序是通过课程学习以及阅读大量的参考文献和书籍，同 时进行了大量的编程实践后完成的。该遗传算法程序最终被应用到实现本文所提 出的优化方案的优化程序( 将在第四章中详细介绍) 中。 本遗传算法程序采用模块化的思想进行编写，如图3 1 所示。 图3 - 1 遗传算法程序 参数定义模块：通过参数定义模块，使用者可以设置相关的遗传参数，包 括群体规模、变量的二进制编码长度、二进制编码的编码方式、杂交方式、 杂交概率等。 参数与群体初始化模块：根据在参数定义模块中所设置的各种遗传参数， 电子科技大学硕士学位论文 程序通过这一模块初始化群体和设定遗传算法程序中各种遗传操作算子 的运行方式。 适应度评估函数模块：这一模块是遗传算法程序的外接出口，实现遗传算 法程序与各种不同的适应度评估函数之间的连接。因为对于不同的问题而 言，其适应度评估函数存在着很大的差异甚至是完全不同，因此，需要为 遗传优化提供个体参数及其个体适应度值的输出输入连接。 终止条件判断模块：每一次循环运算过后，根据达到终止条件与否，决定 是否继续优化运算。终止条件包括：是否达到最大的循环次数；群体是否 收敛。 优化结果输出模块：作用为以文件形式输出最终的优化结果，并在显示器 上显示。 选择算子模块：包含有不同的个体保留机制和各种配对方式。 杂交算子模块：包含有各种染色体杂交方式，如单点杂交、两点杂交和均 匀杂交。 变异算子模块：包含有等概率变异和非等概率变异。 程序采用模块化思想进行编写的优点是： ( 1 ) 每一个程序模块都是相对独立的，对某模块进行修改或者添加并不 会对别的模块产生太大影响。 ( 2 ) 有利于引入新的计算模块。比如在后续的工作中，在选择算子模块和 杂交算子模块之间插入了一个新的运算模块( 跳变基因算子模块) 。 为了提高遗传算法的性能( 比如多样性、收敛速度等) ，不断有新的遗传操 作技术和遗传操作算子被提出。程序采用模块化的思想进行编写有利于对程序进 行实时的修改或者添加，在不断扩大程序功能的同时，也提高了程序的优化性能。 3 2 遗传算法程序的性能评估 本遗传算法程序的性能应用以下一些在评估遗传算法性能时经常用到的测 试函数1 2 进行了评估。 这些测试函数包括有单峰值函数、多峰值函数咀及带有约束条件的函数等， 其测试结果表明本遗传算法程序具有良好的寻优能力。 l 。d ej o n g 函数1 电子科技大学硕士学位论文 f ( x ：，为) = x ? 一5 1 2 z ，s5 1 2( f = 1 , 2 ，3 ) 这是一个简单的平方和函数，只有一个极小点f ( o ，0 ，o ) = o 。优化结果和每一 代的最佳适应度值曲线( 如图3 2 所示) 为： 目标适应度值：0 最佳适应度值：一0 0 0 2 6 8 0 最佳个体：0 0 4 5 0 4 4 0 0 2 5 0 2 40 0 0 5 0 0 5 2 。d ej o n g 函数2 循环次数 图3 - 2 最佳适应度值曲线 i f ( x i , x 2 ) = a o o ( g x 2 ) 2 + ( 1 一_ ) 2 z 【一2 0 4 8 x ，2 0 4 8 ( i = 1 , 2 ) 这是一个二维函数，它具有一个全局最小点f ( 1 ，1 ) = o 。该函数虽然是单峰值 的函数，但它却是病态的，难以进行全局最小化。优化结果和每一代的最佳适应 度值曲线( 见图3 3 ) 为： 电子科技大学硕士学位论文 目标适应度值：0 最佳适应度值：一0 0 0 1 5 6 5 最佳个体：1 0 0 3 9 2 2 1 0 0 3 9 2 2 3 。d ej o n g 函数3 循环次数 图3 - 3 晶佳适应度值曲线 f ( x l ，z 2 ，a ，x 5 ) 5 1 2 x ，5 1 2( i = 1 , 2 ，a ，5 ) 这是一个不连续函数，对于x ， - 5 1 2 ，一5 0 区域内的每一个点，它都取全局 最小值f ( x 。，x ：，码，x 。，x ，) = 一2 5 。优化结果和每一代的最佳适应度值曲线( 见图 3 4 ) 为： 目标适应度值：2 5 最佳适应度值：2 5 0 0 0 0 0 0 最佳个体：一5 0 3 9 9 2 2 5 0 0 9 8 9 25 0 8 9 9 7 1 5 0 7 9 9 6 15 0 7 9 9 6 1 1 9 x 玎唧 - 旨 ，h ，。，、l 电子科技大学硕士学位论文 4 。s c h a f f e r 函数2 图3 4 最佳适应度值曲线 该函数在其定义域内只具有一个全局最小点f ( o ，0 ) = o 。优化结果和每一代 的最佳适应度值曲线( 见图3 5 ) 为： 目标适应度值：0 最佳适应度值：一0 5 9 9 5 0 8 最佳个体：一0 0 9 7 7 5 2 0 0 9 7 7 5 2 图3 - 5 最佳适应度值曲线 + ) o ) 2 2 x ) + 卫 砰 = 叫 o p nh o 1 m c ；， 一 + o x 0 ( 1 = 一 ) 岛 x ( ， 。，、l 电子科技大学硕士学位论文 5 。g o l d s t e i n p r i c e 函数 f ( x 】，x 2 ) = 1 + ( x 】+ x 2 + 1 ) 2 ( 1 9 1 4 x l + 3 x ? 一1 4 x 2 + 6 x l x 2 + 3 x ；) 3 0 + ( 2 x 】- 3 x 2 ) 2 0 8 3 2 x l + 1 2 x ? + 4 8 x 2 3 6 x 】x 2 + 2 7 x ；) 】 一2s x ，s2 ( f = 1 , 2 ) 该函数在其定义域内只具有一个全局最小点f ( o ，一1 ) = 3 。优化结果和每一代 的最佳适应度值曲线( 见图3 - 6 ) 为： 目标适应度值：一3 最佳适应度值：一3 0 2 8 3 9 5 最佳个体：一0 0 0 7 8 4 3 0 9 9 6 0 7 8 6 。s h u b e r t 函数 图3 - 6 最佳适应度值曲线 j f ( x l ，x 2 ) ：童托0 s ( 1 ) _ “ 善5 沁o s ( h 1 ) ”j 【一1 0 x 1 0( f = 1 , 2 ) 这是一个多峰值函数，在其定义域内总共有7 5 0 个局部最小点，其中的1 8 电子科技大学硕士学位论文 个点是全局最小点，全局最小值为，= 一1 8 6 7 3 l 。优化结果和每一代的最佳适应 度值曲线( 见图3 - 7 ) 为： 目标适应度值：1 8 6 7 3 1 最佳适应度值：18 6 5 6 4 4 4 0 最佳个体：- 1 4 1 7 4 0 0 7 0 8 6 9 9 9 7 。六峰值驼背函数 图3 7 最佳适应度值曲线 厂( 训) = ( 4 - 2 1 x 2 + 哟x 2 + x y + ( - 4 + 4 y 2 ) y 2 3 x 3 2 y 2 该函数共有六个局部极小点 厂( 一0 0 8 9 8 ，0 7 1 2 6 ) = f ( 0 0 8 9 8 ，- 0 7 1 2 6 ) 应度值曲线( 见图3 8 ) 为： ，其中有两个全局最小点，分别为 = 一1 0 31 6 2 8 。优化结果和每一代的最佳适 目标适应度值：1 0 3 1 6 2 8 最佳适应度值：1 0 3 1 3 9 2 最佳个体：0 0 8 2 3 5 3 0 7 1 3 7 2 5 电子科技大学硕士学位论文 图3 - 8 最佳适应度值曲线 8 。带有复杂约束条件的函数l m i n ，( y ) = 5 x l + 5 工2 + 5 x 3 + 5 工4 s 2 + 2 。2 + y 6 + y 7 兰1 02 x l + 2 x 3 + y 6 + 儿s 1 0 2 。2 + 2 2 3 + y 7 + y 8 1 0 8 x l + y 6 1 0 8 。2 + y 7 0 8 x 3 十y 8 蔓0 2 x 4 一m + y 6 0 2 y 2 一y 3 + y 7 0 2 y 4 一儿+ y 8 00 s s 1 ( i = 1 , 2 ，3 ，4 ) 0 蔓y ，l ( i = 1 , 2 ，3 ，4 ，5 ，9 ) 0 y ，( f = 5 , 7 ，8 ) 该函数的全局最小点为f o 111 ，1 ，1 ，1 ，1 ，1 333 ，1 ) = - 1 5 。优化结果( 满足所有约 束条件) 和每一代的最佳适应度值曲线( 见图3 9 ) 为： 目标适应度值：1 5 最佳适应度值：1 2 4 11 7 6 5 最佳个体：0 4 9 4 11 8 0 8 6 2 7 4 50 5 1 7 6 4 70 8 7 4 5 1 0 0 9 7 2 5 4 90 9 9 6 0 7 80 9 0 5 8 8 20 6 9 8 0 3 9 1 0 0 0 0 0 02 4 7 0 5 8 82 4 9 0 1 9 62 1 1 7 6 4 7 o 7 6 0 7 8 4 y ，m 一 圩 。m j一 电子科技大学硕士学位论文 1 。 痿m 值。 图3 - 9 最佳适应度值曲线 9 。带有复杂约束条件的函数2 m 刚x , x 2 , x 3 ，= 等专x 半+ 鬻 z x 一，+ x ，z 十j x ，一x ， s 1 x 1 + x 2 一x 3 1 一x 】+ x 2 一x 3 一1 1 2 x l + 5 x 2 + 1 2 x 3 e3 4 8 1 2 x 1 + 1 2 x 2 + 7 x 3 2 9 1 6 。1 + x 2 + x 3 一4 1 0 s x ，( f = 1 , 2 ，3 ) 该函数的全局最大点为f ( 1 ，0 ，o ) = 2 4 7 1 4 2 8 。优化结果( 满足所有约束条件) 和每一代的最佳适应度值曲线( 见图3 - 1 0 ) 为： 目标适应度值：2 4 7 1 4 2 8 最佳适应度值：2 2 8 5 1 3 0 最佳个体：0 9 0 1 9 6 1 0 0 5 8 8 2 40 1 5 6 8 6 3 2 4 电子科技大学硕士学位论文 图3 一l o 最佳适应度值曲线 注： 本遗传算法程序的优化目标是搜索最大值，所以在求解最小值的问题上，需 要将其转变为求解最大值。 上述遗传算法测试例子的最佳适应度值并不等于目标适应度值，其主要原因 在于采用二进制编码以及有限的群体规模和循环次数。二进制编码的长度与计算 精度成正比，但也与优化空间的大小成正比，所以二进制编码的长度一般不会取 太长；另外，在实际的优化过程中，群体规模和循环次数不可能取太大甚至无穷 大，所以，要根据优化问题的大小和时间上的限制适当的选取群体规模和循环次 数。 综上所述，本遗传算法程序的性能良好，特别是对单峰值函数或约束条件不 太高的多峰值函数具有较强的寻优能力。 3 3 新的遗传操作算子：跳变基因算子( j u m p i n gg e n e s ) 3 3 1跳变基因算子的简单介绍 3 3 1 1 跳变基因算子的生物背景 细胞质中能够自由移动并传播遗传信息的质粒，经研究，被命名为“转位子” 电子科技大学硕士学位论文 基因，即可以自由活动而插入到其他细胞基因序列中去的移动基因。转位子基因 的发现者是美国的麦克林托克。她于1 9 5 年就提出移动基因学说，直到4 0 年后， 才得到承认，并于1 9 8 3 年获诺贝尔奖。 早在2 0 世纪4 0 年代，美国女科学家麦克林托克在研究玉米的遗传规律时发 现，玉米的某些性状的改变是和一些基因在染色体上的位置变动有关的。进一步 的研究还发现，这些基因可以从染色体的一个位置“跳到”另一个位置，从一条 染色体“跳到”另一个染色体。于是她便提出了“可移动的遗传因子”的概念。 直到7 0 年代以后，随着分子遗传学的发展，科学家们证实了“可移动的遗传因 子”确是存在的，而且还发现这些因子并不罕见，它们还对有关的生物产生一定 的影响。于是，有人便给这些遗传因子起了一个正式的名字转位子，麦克林 托克也因为她在这方面的开创性工作而获得了1 9 8 3 年的诺贝尔奖。 转位子中包含一些基因，这些基因可以使转位子从原来的d n a 链位置上断裂 开来，然后再插入到另外的d n a 链位置上。当插入到一个新的位置后，转位子对 其附近基因的功能会造成一定的影响；在离开该位置时，它又有可能把一些附近 的基因也一起带走。转位子的这种行为有点“唯我独尊”，是基因的自私性的一 种表现。但无疑，转位子对基因组的进化是有很大作用的。还有一种转位子的自 私性则表现得更为严重。这种转位子本身并不离开原来的位置，而是先转录出 r n a ，再由r n a 反转录成d n a ，然后插入到基因组的其他位置上。反复进行这一 过程，就会使这种转位子在基因组中的拷贝数不断增加。由于这种转位子的特殊 性，因此又把它们称为逆转位子。 细菌细胞中的遗传物质，除了染色体d n a 以外，还有染色体外d n a 质粒。 质粒( p l a s m i d ) 原指一切染色体外的遗传因子，但现在习惯上专指存在于细菌 等微生物细胞中的染色体外遗传因子。质粒是能自主复制的染色体以外的双股环 状d n a ，携有遗传信息，控制非细菌存活所必须的某些特定性状。细菌的质粒具 有自我复制、传给子代、可几个质粒共存于一个菌体、可自然丢失以及可通过结 合或转化转移至受体菌等特性。质粒可分为转移型和非转移型两大类。转移型质 粒可以从一个细胞转移至另一个细胞。它们可以不依赖染色体独立地进行转移， 也可以携带染色体d n a 的片段一起转移，还可以带动自身不能转移的小质粒进行 转移。 3 3 1 2 逮传算法中的跳变基因算子 最近，一种新的遗传操作算子，跳变基因算子( j u m p i n gg e n e s ) ，被提了出 来【1 9 】，并且己被应用到实际的优化问题中，提出跳变基因算子的生物背景就是 电子科技大学硕士学位论文 在上- - ，j , 节中所提到的移动基因现象。在遗传算法中，跳变基因算子与杂交算子 和变异算子一样，直接对染色体进行操作，从而产生新的个体，推动算法的优化 进程。 模仿生物中的移动基因现象，跳变基因算子包含有两种类型的基因操作：复 制移动变换( c o p y a n d p a s t et r a n s p o s i t i o n ) 和剪切移动变换( c u t a n d p a s t e t r a n s p o s i t i o n ) 。 ( 1 ) 复制移动变换( c o p y a n d p a s t et r a n s p o s i t i o n ) 在这种基因变换中，转位子( t r a n s p o s o n ) 本身并不移动，但它的复制体却取 代了同一或另一条染色体上的某一段二进制编码串，如图3 - 1 1 所示。复制移动 变换在程序中的操作流程如图3 一1 2 所示。 在跳变基因算子中，转位子可以是一位或多位连续的二进制编码。以图3 - i 1 为例，转位子的长度为二位二进制编码。 电子科技大学硕士学位论文 在染色体i 上随机地选择个转位子 j 随机地选择一条染色俸k i 在染色体k 上随机地选择一个复制位 将染色俸i 上的转位子复制到染色体k 上的复制位 图3 1 2 复制移动变换的操作流程图 ( 2 ) 剪切移动变换( c u t a n d p a s t et r a n s p o s i t i o n ) 在这种基因变换中，转位子从原来的位置脱离出来并转移到同一或另一条染 色体的其他位置，如图3 1 3 所示。剪切移动变换在程序中的操作流程如图3 1 4 所示。 电子科技大学硕士学位论文 图3 1 4 剪切移动变换的操作流程图 在引入跳变基因算子后，遗传算法程序的基本流程如图3 1 5 所示，跳变基 因算子位于选择算子之后及杂交算子之前。而跳变基因算子本身的操作过程如图 3 1 6 所示。 图3 1 5 引入跳变基因算子后的遗传算法程序流程图 电子科技大学硕士学位论文 图3 1 6 跳变基因算子的程序流程图 3 3 2 基于二进制编码的理论分析 3 3 2 1 模式的生存概率 术语介绍 模式( s c h e m a ) ：表示一些相似的模块，它描述了在某些位置上具有相似结 构特征的个体编码串的一个子集。在二进制编码中，个体是由二值字符集 0 ，1 ) 中的元素所组成的一个编码串，而模式却是由三值字符集( 0 ，l ，$ ) 中的元素所组 成的一个编码串，其中“ ”表示通配符，它既可被当作“1 ”，也可