《基于差分进化算法的阵列天线优化设计论文32238.doc》由会员分享，可在线阅读，更多相关《基于差分进化算法的阵列天线优化设计论文32238.doc（53页珍藏版）》请在三一文库上搜索。
1、本科毕业设计论文 题 目 基于差分进化算法的阵列天线优化设计 摘 要 i摘 要随着现代信息技术和计算机技术渗透到各个科学领域，人类正在步入一个科技迅速发展的新时期。一种新颖的演化算法即差分进化算法在各种演化算法中脱颖而出，差分进化是一种基于群体差异的启发式随机搜索算法，因原理简单、受控参数少、鲁棒性强等特点，在许多方面得到了广泛应用。为了达到给定阵列天线方向图的指标要求，本文将差分进化算法用于阵列天线方向图的综合之中。首先介绍了差分进化算法的基本原理及阵列天线的基本理论，然后采用差分进化算法分别实现了一维点源阵列和二维点源阵列的方向图综合。研究了低副瓣和在指定角度形成零点时的方向图综合情形，并
2、讨论了算法的收敛情况。结果表明，该算法能得到满足设计要求的方向图，且具有较快的收敛速度。关键词：方向图综合 差分进化 零点形成 差分策略 ABSTRACT iiABSTRACTWith the development of modern information technology and computer technology in every fields of science, humanity is moving into a new period when science and technology are quickly developed. A novel algorithm
3、called differential evolution algorithm is talent showing itself among various evolutionary algorithm. Differential evolution is a population-based heuristic random search algorithm differences, because simple in principle, less controlled parameters, and robustness features, has been widely used in
4、 many applications. Therefore, differential evolution algorithm for its excellent performance to global search and the objective function which does not require differentiability and continuity conditions, in recent years is widely used among the array antenna pattern synthesis.To meet the pattern r
5、equirements of a certain array antenna, the differential evolution algorithm was used to synthesis of array antenna pattern in this thesis. Firstly the relevant principle of the differential evolution algorithm and the basic theory of the array antenna are introduced., Then a one-dimensional and a t
6、wo-dimensional point source arrays are synthesized respectively by using the differential evolution algorithm. The requirements of lowest sidelobes and formation of the designated zero-point are considered in the pattern synthesis. The convergence of the algorithm is discussed. The results show that
7、 the algorithm can satisfy the design requirements of the direction pattern, and has a faster convergence speed.Key words: Pattern synthesis Differential evolution Zero-point formation Differential evolution strategy目 录目 录第一章 绪 论11.1 课题研究背景及目的11.2 国内外研究现状11.2.1 传统方向图综合方法11.2.2 智能优化方法31.3 关于差分进化算法41.
8、3.1 优化算法及其分类41.3.2 智能优化算法的特点51.3.3 智能优化算法的应用71.4 本论文的主要研究内容9第二章 差分进化算法的基本理论112.1 进化计算的产生背景及现状112.1.1 产生背景112.1.2 进化计算的发展过程112.2 进化算法的特征及其应用132.2.1 进化算法的特征132.2.2 进化算法的应用142.3 差分进化算法152.3.1 差分进化算法的概述与进展152.3.2 差分进化算法的基本原理162.3.3 差分进化算法的特征182.4 差分进化算法的改进192.4.1 引言192.4.2 变异算子的改进192.4.3 改进算法流程192.5 本章小
9、结20第三章 阵列天线基础213.1 阵列天线背景知识213.2 阵列天线结构213.3 阵列天线基本参数243.4 本章小结28第四章 基于差分进化算法的阵列天线优化294.1 DE算法的基本步骤及具体流程图294.2.1 算法基本步骤294.2.2 DE算法的基本流程图294.2 差分进化算法对应的程序流程图314.3 目标函数的确定324.4 基于差分进化算法优化阵列天线334.4.1 一维直线阵列旁瓣电平优化和零陷生成334.4.2 二维平面阵列旁瓣电平优化354.5 本章小结37第五章 总结与展望395.1 本文小结395.2 研究展望39致 谢41参考文献4345参考文献 第一章
10、绪 论1.1 课题研究背景及目的随着无线通信技术的飞速发展，可用频谱资源越来越有限，如何优化通信系统资源配置和提高资源利用率成为无线通信进一步发展的关键问题。阵列天线方向图综合是指按规定的方向图要求，用一种或多种优化方法进行天线系统的设计，使该系统产生的方向图与所要求的方向图良好逼近。它实际上是天线分析的反设计，即给定期望方向图，设计阵列天线相关参数。阵列天线方向图综合设计参数包括：阵列单元数目、阵元分布形式、阵元间距、各阵元激励幅度和相位。在阵元的分布形式和阵元数目都给定的情况下，控制阵元间距以及激励的幅度和相位分布就可以改变辐射特性，例如，主瓣形状、副瓣电平、零陷生成等。随着通信技术的迅猛
11、发展，对阵列天线方向图的要求也越来越高，越来越多的优化技术被应用到方向图综合中，并在一定程度上取得了诸如获得窄的扫描波束、抑制旁瓣电平到一个较低值、较好的控制了零点生成等可观的优化效果，但寻找能取得更优方向图的优化技术仍然是阵列天线方向图综合的一个重点。在一些实际应用中，例如，雷达天线及卫星天线，动辄需要上千、上万个单元，而且为改善天线阵方向性还须采用幅度相位加权，将导致阵列的馈电网络非常复杂，甚至难以实现。此时改变其布阵方式就是一个很好的选择，即采用稀疏阵列来解决这一问题，实现用较少的阵元数量达到技术指标，并且大大降低了生产成本。但阵列的周期性变稀会使方向图出现非常高的副瓣，如何抑制稀疏阵列
12、的副瓣电平到设计允许范围内成为了一项关键技术。1.2 国内外研究现状1.2.1 传统方向图综合方法天线综合问题就是确定天线的一些参数，使天线的某些辐射特性满足给定的要求，或者使阵列的辐射方向图尽可能地接近期望的方向图。阵列天线的性能取决于辐射元的形式、排列方式、位置以及辐射元上激励的幅度和相位。为了简化对阵列天线的讨论，设计中的所有辐射元都是全向性的点源。这样的阵列天线所产生的场强表达式称为阵因子。辐射元的数目、单元间距、激励幅度和相位是阵因子中的四个可变参量。所谓天线分析，就是指这四个参量在给定的情况下去确定天线的辐射特性，如波瓣图、方向性系数、增益和阻抗等。反之，若根据所需的波瓣图或给定的
13、性能指标，然后用某一种方法去确定这四个参量，再根据这些参量构成阵列天线， 看它们的性能指标是否符合或接近我们预先提出的性能指标，这种方法则称为天线综合1-4。第一类综合问题，是根据已给出的对主瓣宽度和旁瓣电平的要求，或指定方向图的零点位置，来确定阵因子中四个变量中的某几个(例如，辐射元的数目、辐射元上的激励幅度)，而其余的参量作为非变量，对方向图的其它细节和方向性系数没有具体规定。常见的方法有Dolph-Chebyshev综合法和Taylor综合法。DolphChebyshev综合法是利用Chebyshev多项式的性质，在给定的副瓣相对电平条件下能够得到最窄的主瓣宽度，或者在给定第一零点主瓣宽
14、度条件下，获得最低副瓣相对电平，且是等副瓣的。Taylor综合法是对Chebyshcv多项式进行适当的修正，使其两大振幅区域合并为方向图主瓣，而副瓣则在由Chebyshev多项式控制的基础上再加一衰减函数形成。Dolph-Chebyshev综合法多用于离散阵的综合，Taylor综合法则即可用于离散线阵，也可用于连续阵的综合问题。第二类综合问题是要求达到预先指定的方向图形状。综合过程主要是确定必要的单元数目、间距分布和激励，以便获得最好的可实现的阵因子。用综合的阵因子代替预期的方向图时带来的均方差或最大误差应当是最小的。传统的波束赋形方法有傅立叶变换法、WoodwardLawson法等。傅立叶变
15、换法的原理是阵列单元的激励幅度与其产生的阵列函数构成一对傅立叶变换，对期望的方向图进行反傅立叶变换就可得到各单元的激励系数，该方法要求阵列函数满足周期性条件。因为理想的傅立叶变换需无限线源，而实际中不可能实现。Woodward.Lawson法是1948年由Woodward和Lawson提出的，他们引入了一系列正交波束，每个波束的加权值等于所要求的方向图在对应采样点处的幅度。利用此方法可以对连续线源和离散线阵进行综合。利用样本函数的性质对Woodward.Lawson法进行了改进，提出的W-S 法用较少的单元就可以综合相同效果的方向图，或在单元数目相同时，w-s法综合的方向图更接近样本函数，且天
16、线的波瓣变窄，增益较高。 傅立叶变换法综合的方向图与所要求的方向图之间的均方误差最小， Woodward-Lawson法综合出的方向图在抽样点上的值与所要求的方向图完全一致，而在抽样点之间对方向图没有任何控制，因而不会具有最小均方的方向图，得出的结果一般在主瓣区波纹系数较大，副瓣的高度也不能得到很好的控制。但是Woodward-Lawson法更加灵活，理论上可以综合任意所需要的方向图，包括实测结果，不论是模拟形式或数字形式的都可以。第三类综合问题是从己知的方向图出发，通过微变遥近指定的方向图指标，通常称为微扰法。微扰法是从已知的方向图出发，逐步地改变辐射单元间距和激励幅度，达到所需要的方向图指
17、标。第四类综合问题是阵列天线参数的最优化设计。天线参数的最优化设计经常采用数值分析法。在天线方向图综合中，传统解析的方法虽然计算简单，但适用范围窄，在实际工程中，由于天线阵分布的随意性以及各阵列单元方向图的任意性，很难利用上述解析的方法进行计算，因而通常采用数值计算方法。数值方法可以综合出很多解析方法所不能综合的复杂方向图，而且在改善波束性能上也有很大的优势。用数值优化的方法进行方向图综合的主要任务是建立数学模型，构造合适的目标函数。由于方向图综合问题中的目标函数或约束条件大部分呈多参数、非线性、不可微甚至不连续，基于梯度寻优技术的传统数值优化方法无法有效地求得工程满意解，因此通常选择直接优化
18、方法对天线方向图进行设计。经典的直接优化方法的效率对初始值的依赖性很强，使用不同的初始值，运用不同的方法构造新的搜索方向，最终计算的效率会有很大的差别。1.2.2 智能优化方法差分进化算法(Differential Evolution ,DE)是一种新兴的进化计算技术。它是由Storn 等人于1995 年提出的，和其它演化算法一样，DE 是一种模拟生物进化的随机模型，通过反复迭代，使得那些适应环境的个体被保存了下来。但相比于进化算法，DE 保留了基于种群的全局搜索策略，采用实数编码、基于差分的简单变异操作和一对一的竞争生存策略，降低了遗传操作的复杂性。同时，DE 特有的记忆能力使其可以动态跟踪
19、当前的搜索情况，以调整其搜索策略，具有较强的全局收敛能力和鲁棒性，且不需要借助问题的特征信息，适于求解一些利用常规的数学规划方法所无法求解的复杂环境中的优化问题。目前，DE 已经在许多领域得到了应用，譬如人工神经元网络、化工、电力、机械设计、机器人、信号处理、生物信息、经济学、现代农业、食品安全、环境保护和运筹学等。1.3 关于差分进化算法1.3.1 优化算法及其分类如今，科学技术正处于多学科相互交叉和渗透的时代。特别是计算机科学与技术的迅速发展，从根本上改变了人类的生产与生活。同时，随着人类生存空间的扩大以及认识与改造世界范围的拓宽，人们对科学技术提出了新的和更高的要求，其中对高效的优化技术
20、和智能计算的要求日益迫切。优化技术是一种以数学为基础，用于求解各种工程问题优化解的应用技术。作为一个重要的科学分支，它一直受到人们的广泛重视，并在诸多工程领域得到迅速推广和应用，如系统控制、人工智能、模式识别、生产调度、VLSI 技术和计算机工程等。鉴于实际工程问题的复杂性、约束性、非线性、多极值、建模困难等特点，寻求一种适合于大规模并行且具有智能特征的算法已成为有关学科的一个重要研究目标和引人注目的研究方向。20 世纪80 年代以来，一些新颖的优化算法，如模拟退火算法、遗传算法、进化策略、进化规划、遗传程序设计、微粒群优化算法、蚁群算法、差分进化算法、人工免疫系统、DNA 计算等，通过模拟或
21、揭示某些自然现象或过程而得到发展，其思想和内容涉及数学、物理学、生物进化、人工智能、神经学科和统计力学等方面，为解决复杂问题提供了新的思路和手段。这些算法独特的优点和机制，引起了国内外学者的广泛重视掀起了该领域的研究热潮，且在诸多领域得到了成功应用。在优化领域，由于这些算法构造的直观性与自然机理，因而通常称作智能优化算法（Intelligent Optimization Algorithms），或称现代启发式算法（Meta-heuristic Algorithm）5。所谓优化算法，其实就是一种搜索过程或规则，它是基于某种思想和机制，通过一定的途径或规则来得到满足用户要求的问题的解。就优化机制与
22、行为而分，目前工程中常用的优化算法主要可分为：经典算法、构造型算法、改进型算法、基于系统动态演化的算法和混合型算法等。（1）经典算法。包括线性规划、动态规划、整数规划和分枝定界等经典最优化中的差分进化算法及应用研究传统算法，其算法计算复杂性一般很大，而且对函数要求连续、可导等，只适合求解小规模问题，在工程中往往不实用。（2）构造型算法。用构造的方法快速建立问题的解，通常算法的优化质量差、难以满足工程需要。譬如，调度问题中的典型构造型方法有：Johnson 法、Palmer 法、Gupta法、CDS 法、Daunenbring 的快速接近法等。（3）改进型算法，或称邻域搜索算法。从任一解出发，对
23、其领域的不断搜索和当前解的替换来实现优化。根据搜索行为，它又可分为局部搜索和指导性搜索法。 局部搜索法。以局部优化策略在当前解的邻域中贪婪搜索，如只接受优于当前解的状态作为下一当前解的爬山法；接受当前解邻域中的最好解作为下一当前解的最陡下降法等。 指导性搜索法。利用一些指导规则来指导整个解空间中优良解的探索，如遗传算法、进化策略、进化规划、微粒群优化算法、蚁群优化算法、差分进化算法等。（4）混合型算法。指上述各算法从结构或操作上相混合而产生的各类算法。优化算法当然还可以从别的角度进行分类，如确定性算法和不确定性算法，局部优化算法和全局优化算法等。1.3.2 智能优化算法的特点智能优化算法与传统
24、法相比，具有很多不同之处。（1）智能性智能优化算法的智能性包括自组织、自适应和自学习性等。应用智能优化算法求解问题时，在确定了编码方案、适应值函数及遗传算子之后，算法将利用进化过程中获得的信息自行组织搜索。由于基于自然的选择策略为适者生存、不适应者淘汰，适应值优的个体具有较高的生存概率。通常适应值优的个体具有与环境更适应的基因结构，再通过杂交和基因突变等遗传操作就可能产生与环境更适应的后代。智能优化算法的这种自组织、自适应特征同时也赋予了它具有能根据环境的变化自动发现环境的特性和规律的能力。（2）本质并行性进化算法的本质并行性表现在两个方面。一方面，进化算法是内在并行的，即进化算法本身非常适合
25、于大规模并行计算。最简单的并行方式是让几百甚至数千台计算机各自进行独立种群的进化计算，运行过程中甚至不进行任何通信（独立种群之间若有少量的通信一般会带来更好的结果），等到运算结束时才通信比较，选取最佳个体。这种并行处理方式对并行系统结构也没有什么限制和要求。另一方面，进化算法的内含并行性。进化算法采用种群的方式组织搜索，因而它可以同时搜索解空间的多个区域，并相互交流信息。这种搜索方式使得它虽然每次只执行与种群规模N 成比例的计算，而实质上已进行了大约次有效搜索，能以较少的计算获得较大的收益。（3）其他特征除了其自组织、自适应性和本质并行性以外，智能优化算法的基本特征还表现在以下几个方面。过程性
26、。智能优化算法通过自然选择和遗传操作等自组织行为来增强群体的适应性。算法模拟的是一个过程，算法的实施也是一个过程。在这个过程中，算法本身无法判定个体处在解空间的位置，因此需要人为干预（即事先确定终止准则）才能终止。 多解性。智能优化算法的另一基本特征是采用群体的方式组织搜索。它从多个点出发，通过这些点内部结构的调整和重组来形成新的点。因而，每次都将提供多个近似解，对多目标搜索或有需要多个近似解作为参照的情况下是非常有用的。不确定性。智能优化算法的不确定性是伴随其随机性而来的。一般而言，大多数智能优化算法的主要步骤都含有随机因素，从而在算法的进化过程中，事件发生与否带有很大的不确定性。内在学习性
27、。学习是进化过程自身所具有的不可与其分割的行为方式。与自然进化过程类似，它也有三种不同的学习方式，且这些学习方式又内在地体现在进化计算的整个过程中：宗亲学习（Phylogenetic-Learning），这种学习是发生在整个进化过程中，祖先的良好特征通过遗传传递给后代，后代通过家族成员“血缘”继承方式学习其先辈的自适应行为；社团学习（Sociogenetic Learning），这种学习是一些经验和知识在某个社团内的共享，体现在进化计算中即是独立群体内部知识或结构的共享；个体学习（Ontogenetic Learning），这种学习是自然界中发生的最为频繁的一种行为，生物体为了生存就必须进行学
28、习，通过不断实践来积累知识和经验，以增强自己的适应性，进化计算的个体学习方式是通过改变个体的基因结构来提高自己的适应度。统计性。智能优化算法的种群方式决定它是一个统计过程。在每一进化代，都要进行统计，以确定个体的优劣并推动进化的进行。稳健性。由于智能优化算法利用个体的适应值推动群体的进化，而不管求解问题本身的结构特征，因而用进化计算求解不同问题时，只需要设计相应的适应性评价函数，而无需修改算法的其他部分。同时，因为智能优化算法具有自然系统的自适应特性，算法在效率和效益之间的权衡使得它能适应于不同的环境并取得较好的效果。整体优化。传统的优化方法一般采用的是梯度下降的爬山策略，从而使得对多峰函数的
29、情形往往容易陷入局部最优。而智能优化算法能同时在解空间的多个区域内进行搜索，并且能以较大的概率跳出局部最优，以找到整体最优解。1.3.3 智能优化算法的应用智能优化算法不依赖于问题具体的领域，对问题的种类有很强的鲁棒性，是求解复杂系统优化问题的有效方法，所以广泛应用于许多学科。目前，智能优化算法在生物技术和生物学、化学和化学工程、计算机辅助设计，物理学和数据分析，动态处理、建模与模拟、医学与医学工程、微电子学、模式识别、人工智能、生产调度、机器学习、采矿工程、电信学、售货服务系统等领域都得到了应用，成为求解全局优化问题的有力工具之一6。(1) 函数优化函数优化（Function Optimiz
30、ation）是智能优化算法的经典应用领域，也是对智能优化算法性能评价的常用算例。可以用各种各样的函数来验证智能优化算法的性能。对一些非线性、多模型、多目标的函数优化问题，使用智能优化算法可得到较好的结果。(2) 组合优化随着问题规模的增大，组合优化问题的搜索空间也急剧扩大，有时在目前的计算机上用枚举法很难甚至不能求出问题的最优解，对这类问题，人们已意识到应把主要精力放在寻求其满意解上，而智能优化算法就是寻求这种满意解的最佳工具之一。实践证明，智能优化算法对于组合优化中的NP 完全问题非常有效。(3) 生产调度问题采用智能优化算法能够解决复杂的生产调度问题。在单件生产车间调度、流水线生产车间调度
31、、生产规划、任务分配等方面，智能优化算法都得到了有效的应用。(4) 自动控制在自动控制领域中有很多与优化相关的问题需要求解，智能优化算法已在其中得到了初步应用，并显示出了良好的效果。例如，基于智能优化算法的模糊控制器优化设计，用智能优化算法进行航空控制系统的优化，使用智能优化算法设计空间交会控制器等。(5) 机器人学机器人是一类复杂的难以精确建模的人工系统，而智能优化算法起源来自对于人工自适应系统的研究，所以机器人学理所当然地成为智能优化算法的一个重要领域。例如，智能优化算法已经在移动机器人路径规划、机器人逆运动学求解等方面得到了很好的应用。(6) 图像处理图像处理是计算机视觉中的一个重要领域
32、，在图像处理过程中，如扫描、特征提取、图像分割等不可避免地会存在一些误差，这些误差会影响图像处理的效果。如何使这些误差最小是使计算机视觉达到实用化的重要要求，智能优化算法在这些图像处理的优化计算方面找到了用武之地。(7) 机器学习基于智能优化算法的机器学习，特别是分类器系统，在很多领域中都得到了应用。例如，智能优化算法被用于模糊控制规则，利用智能优化算法来学习隶属函数等。基于智能优化算法的机器学习可用于调整人工神经网络的连接权，也可用于神经网络结构的优化设计。分类器系统在多机器人路径规划系统中得到了成功的应用。(8) 数据挖掘数据挖掘（Data Mining）是指从大型数据库或数据仓库中提取隐
33、含的、未知的、非平凡的及有潜在应用价值的信息或模式，它是数据库研究中的一个很有应用价值的新领域，由于智能优化算法的特点，智能优化算法可用于数据挖掘中的规则开采。(9) 信息战智能优化算法在信息战领域得到了初步应用。使用智能优化算法能够进行雷达目标识别、数据挖掘、作战仿真、雷达辐射源识别、雷达天线优化设计、雷达目标跟踪、盲信号处理、空间谱估计、天线设计、网络入侵检测、情报分析中的数据挖掘和数据融合、信息战系统仿真作战效能评估、作战辅助决策等。表 1.1 智能优化算法的主要应用领域应用领域 例 子自动控制瓦斯管道控制，防避导弹控制、机器人控制规 划生产规划，并行机任务分配设 计VLSI布局，通信网
34、络设计，喷气发动机设计组合优化TSP问题，背包问题，图划分问题信号处理滤波器设计，目标识别，运动目标分割图像处理模式识别，特征提取，图像恢复机 器 人路径规划人工生命生命的遗传进化1.4 本论文的主要研究内容本文将遗传算法应用到阵列天线方向图综合中，主要就以下几个方面的内容进行了研究：1.重点就差分进化算法的相关Fortran程序进行了研究，该程序包括一个主程序和调用的包含有具体算法的子程序，以及计算中要用到的几个子函数。2.通过程序详细研究了一个基于差分进化算法的阵列天线综合问题中通用的目标函数，该通用目标函数：（1）包括了主瓣位置控制、最高旁瓣抑制和零点生成：（2）具有可扩展性，如果需要增
35、加新的指标，只需要在目标函数的表达式后添加即可。3采用差分进化算法优化阵元间距、激励的幅度等参量，使得优化后的方向图满足：（1）抑制最大相对旁瓣至指定值内和超低副瓣；（2）在指定角度生成指定零深的零陷；（3）同时包含主瓣宽度抑制、旁瓣抑制和零深抑制指标。本文共分5章，各章主要内容安排如下：第l章，介绍了差分进化优化算法的产生对现代优化技术的重要影响，阐述了智能优化算法的研究和发展对现代优化技术和工程实践应用的必要性，归纳总结了智能优化算法的主要特点，简要介绍了智能优化算法的主要研究内容及应用领域，对差分进化算法进行了简要的概述。而后部分介绍了天线阵方向图综合的研究背景及意义，简单介绍了天线阵综
36、合的经典综合方法和以及新算法的应用，最后介绍了本文的主要工作及章节安排。第2章，主要介绍了差分进化计算的产生背景、发展、应用和特征等，详细阐述了标准差分进化算法的基本原理、进化过程、特征及其改进，并给出了其实现流程。第3章，介绍天线的主要参数和天线阵列的形式和原理。第4章，介绍了基于Fortran语言的优化过程的详细步骤，对程序相关的每一部分的功能及输入输出变量进行了分析，给出了流程图。对一维和二维的平面阵列天线进行优化后得出最终结果，并对得出的结论进行分析。第5章，给出本文的总结与展望，提出有待解决的问题和进一步研究的方向。第二章 差分进化算法的基本理论进化计算是模拟自然界生物进化过程与机制
37、求解优化与搜索问题的一类自组织、自适应人工智能技术。2.1 进化计算的产生背景及现状2.1.1 产生背景生物群体的生存过程普遍遵循达尔文的物竞天择、适者生存的进化准则；生物通过个体间的选择、交叉、变异来适应大自然环境，20世纪60年代以来，如何模仿生物来建立功能强大的算法，进而将它们运用于复杂的优化问题，越来越成为一个研究热点。进化计算(evolutionary computation) 正是在这一背景下孕育而生的。进化算法模仿的是一切生命与智能的生成与进化过程，他不仅模拟达尔文“优胜劣汰，适者生存”的进化原理激励好的结构，而且也通过模拟孟德尔等人的遗传变异理论在优化过程中保持已有的结构，同时
38、寻找更好的结构，这就是进化计算核心思想的起源。进化计算也就是借用生物进化的规律，通过繁殖，竞争，再繁殖，再竞争，实现优胜劣汰，一步一步地逼近问题的最优解。进化算法作为一种随机搜索技术，对优化问题的不连续性，不可微性，高度非线性性，没有要求，是一种具有通用，并行，稳健，简单与全局优化能力强的优化算法。2.1.2 进化计算的发展过程进化计算与其他科学技术一样，都经历了一段成长过程，逐渐发展壮大。此过程可大致分为三个时期：萌芽时期，成长时期和发展时期。第一时期：萌芽时期（50年代后期至70年代初期）早在50年代后期，一些生物学家就着手采用电子计算机模拟生物的遗传系统，尽管这些工作纯粹是研究生物现象，
39、但其中已使用现代遗传算法的一些标识方式。例如：美国A.S.Fraser于1960年为了建立生物的表现型方程，用3组5位（共15位）的0-1字符串表示方程的三个参数。1965年，德国的I.Rechenberg等人正式提出进化策略的方法，当时的进化策略只有一个个体，而且进化操作也只有突变一种。1965年，美国的L.J.Fogel正式提出进化规划，再计算中采用多个个体组成的群体，而且只运用突变操作。60年代期间，美国芝加哥大学教授J.H.Holland在研究自适应系统时，提出系统本身与环境相互协调的遗传算法。 1968年，J.H.Holland教授又提出模式理论，它成为遗传算法的主要理论基础。第二时
40、期：成长时期（70年代中期至80年代末期）1975 年，J.H.Holland 教授的专著自然界和人工系统的适应性(Adaptation in Natural and Artificial Systems)正式出版，全面地介绍了遗传算法，人们常常把这一事件视作遗传算法问世的标志，Holland 也被视作遗传算法的创始人。1975 年，德国H.P.Schwefel 在他的博士论文中发展了进化策略，采用多个个体组成的群体而不是单个个体参与进化，而且进化的手段包括突变及重组，使进化策略更加完美。80年代期间，许多研究工作者积极从事遗产算法的研究，使遗传算发成为美国人工智能领域的又一个研究热点。198
41、7 年，美国D.Lawrence 总结人们长期从事遗传算法的经验，公开出版遗传算法和模拟退火(Genetic Algorithm and Simulated Annealing)一书，以论文集形式用大量实例介绍遗传算法。1989 年，作为J.H.Holland 的学生，D.E.Goldberg 博士出版专著遗传算法搜索，优化及机器学习(Genetic Algorithms-in Search, Optimization and Machine Learning)，全面，系统地介绍遗传算法，使这一技术得到普及与推广。该书被人们视为遗传算法的教科书。第三时期：发展时期（90年代以后）这时期在进化算
42、法方面最突出的成就，是遗传规划的出现。早在 80 年代后期，人们已经开始努力改进遗传算法的表达形式，例如，有人采用字符串，也有人使用一系列If-then语句表达问题。美国斯坦福大学的J.R.Koza 于1989 年提出遗传规划新概念，用层次化的计算机程序代替字符串表达问题。1992年，他出版专著 遗传规划应用自然选择法则的计算机程序设计 (Genetic Programming: on the Programming of Computer by Means of Natural Selection)，该书全面介绍了遗传规划的原理及其应用实例，表明遗传规划已经成为进化算法的一个重要分支，Koz
43、a 本人也被视作遗传规划的奠基人。1994 年，J.R.Koza 又出版第二部专著遗传规划：可再用程序的自动发现(GeneticPragramming:Automatic Discovery of Reusable Programs)，提出自动定义函数的新概念，在遗传规划中引入子程序的新技术。 同年，K.E.Kinnear Jr 主编遗传规划进展(Advances inGenetic Programming)，汇编许多研究工作者有关应用遗传规划的经验和技术。1998年，W.Banzhaf 等人出版专著遗传规划：计算机程序的自动进化及其应用综(Genetic Programming: An In
44、troduction On the Automatic Evolution of Computer Programs and its Applications)，除了全面总结遗传规划的方法外，还对各种改进技术进行评述。与此同时，有关遗传规划的定期国际学术会议也多次召开，标志着遗传规划已经得到广泛应用。90 年代，遗传算法不断地向广度和深度发展。1991 年，D.Lawrence 出版遗传算法手册(Handbookof Genetic Algorithms)一书，详尽地介绍遗传算法的工作细节。1996 年，Z.Michalewicz的专著遗传算法+数据结构=进化程序(Genetic Algori
45、thms +Data Structure=Evolution Programs)深入讨论了遗传算法的各种专门问题。同年，T.Back 的专著进化算法的理论与实践：进化策略、进化规划、遗传算法(Evolutionary Strategies,Evolutionary Programming,Genetic Algorithms)深入阐述进化算法的许多理论问题。这一时期，国外有关进化算法的专著有十几本，说明进化算法已得到广泛的关注。我国开展进化算法研究，主要在 90 年代。目前，已经成为继专家系统、人工神经网络之后有关人工智能方面的第三个热点课题。2.2 进化算法的特征及其应用2.2.1 进化算法
46、的特征I 进化算法的实质进化算法中，无论是遗传算法、遗传规划、进化策略或进化规划，都是从一组随机生成的初始个体出发，经过复制（选择）、交换（重组）、突变等操作，并根据适应度大小进行个体的优胜劣汰，提高新一代群体的质量，再经过多次反复迭代，逐步逼近最优解。从数学角度讲，进化算法实质上是一种搜索寻优的方法7。II 进化算法的主要特征进化算法的搜索方式，具有如下特征：(1)有指导搜索。进化算法的搜索策略，既不是盲目式的乱搜索，也不是穷举式的全面搜索，它是有指导的搜索。指导进化算法执行搜索的依据是适应度，也就是它的目标函数。在适应度的驱动下，使进化算法逐步逼近目标值。(2)自适应搜索。进化算法在搜索过
47、程中，借助复制（选择）、交换（重组）、突变等操作，体现“适者生存，劣者消亡”的自然选择规律，无需添加任何额外的作用，就能使群体的品质不断得到改进，具有自动适应环境的能力。(3)渐进式寻优。进化算法从随机产生的初始可行解出发，一代一代地反复迭代，使新一代的结果优于下一代，逐渐得出最优结果，这是一个逐渐寻优的过程。(4)并行式搜索。进化算法每一代运算都是针对一组个体同时进行，而不是只对单个个体。因此，进化算法是一种多点齐头并进的并行算法，大大提高了进化算法的搜索速度。并行式计算是进化算法的一个重要特征。(5)全局最优解。进化算法由于采用多点并行搜索，而且每次迭代借助交换和突变产生新个体，不断扩大搜索范围，因此进化算法很容易搜索出全局最优解而不是局部最优解。(6)通用性强。传统的优化算法，需要将所解决的问题用数学式子表达，而且要求该数学函数的一阶导数或二阶导数存在，采