作者：包子阳,余继周
出版社：电子工业出版社
格式: AZW3, DOCX, EPUB, MOBI, PDF, TXT
基于MATLAB的遗传算法及其在稀布阵列天线中的应用试读：
前言
遗传算法由于其在解决大空间、非线性、组合优化和全局寻优等复杂问题方面所具有的独特优势，得到了国内外学者的广泛关注，并在电子、通信、计算机、自动化、信号处理和模式识别等众多领域得到了成功的应用。目前关于遗传算法的专著不多，大致可分为两类：一类是介绍遗传算法的理论知识和应用，没有实现程序；另一类是智能优化算法书籍中的某一章节，或是基于Sheffield、GAOT工具箱的实现。
在雷达和通信电子系统中，为了使天线具有高增益、窄波束、低旁瓣等特性，广泛采用阵列天线。为了保证天线波束在可视区内不出现栅瓣，均匀天线阵列相邻阵元间距不能大于半倍波长。因此，当要求天线阵列具有高增益、高分辨率时，阵列孔径长度必须很大，均匀间隔布阵就需要相当多的天线阵元，这会使得天馈系统的造价十分昂贵。采用非均匀间隔的稀布阵列天线能够大量节省成本，因而成为了一个研究热点。广义上的稀布阵（列）是指阵元不等间隔排列的天线阵列，又分为阵元间隔为某一数值整数倍的稀疏阵列和阵元间隔为任意数值的稀布阵列。目前介绍阵列天线稀疏、稀布方法的论文很多，但专业书籍还未曾出现。
本书首先介绍遗传算法的来源、原理、算法流程和关键参数说明，并给出具体的MATLAB仿真实例；然后介绍阵列天线综合方向图的理论知识，再通过根据具体问题适应性改进的遗传算法对它们进行稀疏布阵、稀布布阵，达到减少天线阵元，降低成本，同时防止出现栅瓣，得到低旁瓣方向图的目的。书中所有程序都是基于MATLAB基本语句实现的，便于读者的理解和针对具体问题的改进。本书具体内容如下：
第1章为概述，综合介绍了遗传算法的来源、原理和特点，阵列天线和稀布阵天线的基础理论知识；
第2、3章介绍遗传算法的概念、理论、主要应用方向、算法流程和关键参数说明，并给出MATLAB仿真实例；
第4～7章介绍直线阵列、平面阵列、圆形阵列、圆柱阵列综合方向图的理论知识，以及这些天线阵列的优化模型、稀布算法流程和MATLAB实例仿真。
本书由包子阳、余继周合著。在本书编写过程中得到了北京无线电测量研究所科技委、总体部、档信中心的支持和帮助，电子工业出版社相关编辑为本书的出版付出了辛勤劳动，特此表示感谢。
由于著者水平有限，书中难免有不足之处，诚挚希望各位专家和读者批评指正。著 者2017年5月第1章概 述1.1 遗传算法
自然界的生物体在遗传、选择和变异等一系列作用下，优胜劣汰，不断地由低级向高级进化和发展，人们将这种“适者生存”的进化规律的实质加以模式化而构成一种优化算法，即进化计算。进化计算是一系列的搜索技术，包括遗传算法、进化规划、进化策略等。它们在函数优化、信号处理、模式识别、机器学习、作业调度、智能控制等众多领域都有着广泛的应用。其中，遗传算法是进化计算中具有普遍影响的模拟进化优化算法。
遗传算法是模仿自然界生物进化机制而发展起来的随机全局搜索和优化方法。它最早由美国的J. H. Holland教授提出[1]，起源于20世纪60年代对自然和人工自适应系统的研究；70年代，K. A. De Jong基于遗传算法的思想在计算机上进行了大量的纯数值函数优化计算试验[2]；80年代，遗传算法由D. J. Goldberg在一系列研究工作的基础上归纳总结而成[3]。
20世纪90年代以后，遗传算法作为一种高效、实用、鲁棒性强的优化技术，发展极为迅速，在机器学习、模式识别、神经网络、控制系统优化及社会科学等不同领域得到广泛应用，引起了许多学者的关注。进入21世纪，以不确定性、非线性、时间不可逆为内涵的复杂性科学成为一个研究热点。遗传算法因能有效地求解NP（Non-deterministic Polynomial）问题以及非线性、多峰函数优化和多目标优化问题，得到了众多学科学者的高度重视，同时这也极大地推动了遗传算法理论研究和实际应用的不断深入与发展。目前，在世界范围内已掀起关于遗传算法的研究与应用热潮[4-6]。
遗传算法借鉴了达尔文的进化论和孟德尔的遗传学说，本质上是一种并行、高效、全局搜索的方法，它能在搜索过程中自动获取和积累有关搜索空间的知识，并自适应地控制搜索过程以求得最优解。遗传算法操作：使用“适者生存”的原则，在潜在的解决方案种群中逐次产生一个近似最优的方案。在每一代中，根据个体在问题域中的适应度值和从自然遗传学中借鉴来的再造方法进行个体选择，产生一个新的近似解。这个过程导致种群中个体的进化，得到的新个体比原个体更能适应环境。
同传统的优化算法相比，遗传算法具有对参数的编码进行操作、不需要推导和附加信息、寻优规则非确定性、自组织、自适应和自学习性等特点。当染色体结合时，双亲的遗传基因的结合使得子女保持父母的特征；当染色体结合后，随机的变异会造成子代同父代的不同。1.2 阵列天线1.2.1 阵列天线
天线的基本功能是能量转换和完成电磁波的定向辐射或接收；任何无线电设备都需要用到天线，天线的性能直接影响到无线电设备的使用。理论上，由单个天线阵元构成的天线就可以完成发射和接收电磁波的任务。但在实际应用中，往往要求天线具有较强的方向性和很高的增益，有时还要求天线波束可以扫描，并具有一定的形状等，这时就需要利用多个天线阵元按一定方式排列成阵列天线。
阵列天线是根据电磁波在空间相互干涉的原理，把具有相同结构、相同尺寸的某种基本天线按一定规律排列在一起组成的[7]。如果按直线排列，就构成直线阵列（简称线阵）；如果排列在一个平面内，就构成平面阵列（简称平面阵）。若天线阵元排列与载体表面形状一致，称为共形阵，共形阵中的所有天线阵元往往不在一个平面上，所以也可以称为非平面阵。如果各个天线阵元排列成一个圆环，就称之为圆形阵列（简称圆阵）；多个圆环平行布置在一个圆柱体上，便可构成圆柱阵列（简称圆柱阵）。圆阵和圆柱阵是最简单的两种共形阵。1.2.2 稀布阵天线
在雷达和通信电子系统中，广泛应用阵列天线，以使天线波束具有高增益、窄波束、低旁瓣、易电扫等特性。因此，阵列天线的优化设计成为现代电子系统设计中的一个非常重要的环节。天线阵列的优化布阵是在研究天线阵列性能与阵列几何结构关系的基础上，对阵列结构进行优化设计，以获得优良的性能指标。
均匀间隔的阵列由于数学处理方便和阵列结构装配简便而得到了广泛的研究和应用。但为了保证在可视区内不出现栅瓣，均匀天线阵列的相邻阵元间距不能大于半倍波长。当要求天线阵列具有高增益、高分辨率时，阵列孔径长度必须很大，均匀间隔布阵就需要相当多的天线阵元，这会使得天馈系统的造价十分昂贵。
非均匀间隔的稀布天线阵列能够大量节省成本。采用天线阵元在一定孔径上稀布的方法来实现阵列设计，可以通过较少的天线阵元数得到较高的增益，达到较高的分辨率，从而简化结构，降低造价，因此成为了一个研究热点[8]。广义上的稀布阵是指阵元不等间隔排列的天线阵列，又分为稀疏阵列和稀布阵列。稀疏阵列是从均匀间隔满阵中稀疏掉部分阵元，这样就形成了阵元间距约束为某个基本量（通常为半倍波长）的整数倍的非均匀阵列；而稀布阵列的阵元间隔是任意的，但由于阵元物理尺寸及互耦效应等的影响，一般要求阵元间隔不小于半倍波长。1.3 主要内容安排
本书主要包括两部分内容：（1）介绍遗传算法的基础理论、原理和实现，包括遗传算法的生物学基础、理论基础、基本算子、实现流程和关键参数说明等，并给出具体的MATLAB数值仿真实例和旅行商（TSP）仿真实例，以便于读者对遗传算法有初步的理解。（2）介绍阵列天线综合方向图的理论知识和优化模型，包括直线阵列、平面阵列、圆形阵列和圆柱阵列，并通过根据具体问题适应性改进的遗传算法对它们进行稀疏布阵、稀布布阵，达到减少天线阵元，降低成本，同时防止出现栅瓣，得到低旁瓣方向图的目的。参考文献
[1] Holland J H. Adaptation in natural and artificial systems[M]. Ann Arbor:University of Michigan press, 1975.
[2] De jong K A. An Analysis of the Behavior of a Class of Genetic Adaptive System[D]. Ph.D Dissertation, University of Miehigan, 1975.
[3] Goldberg D E. Genetic Algorithms in search, optimization, and machine learning[M], Addsin-Wesley Publishing Company, INC, 1989.
[4] Nicol N, Schraudolph, Richard K, Belew. Dynamic Parameter Encoding for Genetic Algorithms[J], Machine Learning, 1992, 9(1): 9-21.
[5] Davis L D. Handbook of Genetic Algorithm[M]. Van Nostrand Reinhold, 1991.
[6] Holland J H. Building Blocks, Cohort Genetic Algorithms, and Hyperplane-Defined Functions, Evolutionary Computation[J], Massachusetts Institute of Technology, 2000:373-391.
[7] 黄飞. 阵列天线快速自适应波束形成技术研究[D]. 南京: 南京理工大学博士学位论文, 2010: 1-15.
[8] 陈客松. 稀布天线阵列的优化布阵技术研究[D]. 成都：电子科技大学博士学位论文, 2006:1-10.第2章遗传算法基础理论2.1 遗传算法简介
遗传算法是模拟生物在自然环境中的遗传和进化的过程而形成的自适应全局优化搜索算法。它借用了生物遗传学的观点，通过自然选择、遗传和变异等作用机制，实现各个个体适应性的提高。
遗传算法本质是一种并行、高效、全局搜索的方法，它能在搜索过程中自动获取和积累有关搜索空间的知识，并自适应地控制搜索过程以求得最优解。遗传算法操作使用“适者生存”的原则，在潜在的解决方案种群中逐次产生一个近似最优的方案。在遗传算法的每一代中，根据个体在问题域中的适应度值和从自然遗传学中借鉴来的再造方法进行个体选择，产生一个新的近似解。这个过程导致种群中个体的进化，得到的新个体比原个体更能适应环境，就像自然界中的改造一样。
如前所述，遗传算法具有对参数的编码进行操作、不需要推导和附加信息、寻优规则非确定性、自组织、自适应和自学习性等特点。当染色体结合时，双亲的遗传基因的结合使得子女保持父母的特征；当染色体结合后，随机的变异会造成子代同父代的不同。2.2 遗传算法的生物学基础
自然选择学说认为适者生存，生物要存活下去，就必须进行生存斗争。生存斗争包括种内斗争、种间斗争以及生物跟环境之间的斗争三个方面。在生存斗争中，具有有利变异的个体容易存活下来，并且有更多的机会将有利变异传给后代；具有不利变异的个体就容易被淘汰，产生后代的机会也将少得多。因此，凡是在生存斗争中获胜的个体都是对环境适应性比较强的个体。达尔文把这种在生存斗争中适者生存、不适者淘汰的过程叫作自然选择。
达尔文的自然选择学说表明，遗传和变异是决定生物进化的内在因素。遗传是指父代与子代之间，在性状上存在的相似现象；变异是指父代与子代之间以及子代的个体之间，在性状上存在的差异现象。在生物体内，遗传和变异的关系十分密切。一个生物体的遗传性状往往会发生变异，而变异的性状有的可以遗传。遗传能使生物的性状不断地传送给后代，因此保持了物种的特性；变异能够使生物的性状发生改变，从而适应新的环境而不断地向前发展。
生物的各项生命活动都有它的物质基础，生物的遗传与变异也是这样。根据现代细胞学和遗传学的研究得知：遗传物质的主要载体是染色体；基因是有遗传效应的片段，它储存着遗传信息，可以准确地复制，也能够发生突变。生物体自身通过对基因的复制和交叉，使其性状的遗传得到选择和控制。同时，通过基因重组、基因变异和染色体在结构和数目上的变异产生丰富多彩的变异现象。生物的遗传特性，使生物界的物种能够保持相对的稳定；生物的变异特性，使生物个体产生新的性状，以至形成了新的物种，推动了生物的进化和发展。
由于生物在繁殖中可能发生基因交叉和变异，引起了生物性状的连续微弱改变，为外界环境的定向选择提供了物质条件和基础，使生物的进化成为可能。人们正是通过对环境的选择、基因的交叉和变异这一生物演化的迭代过程的模仿，才提出了能够用于求解最优化问题的强鲁棒性和自适应性的遗传算法[1]。生物遗传和进化的规律有：（1）生物的所有遗传信息都包含在其染色体中，染色体决定了生物的性状。染色体是由基因及其有规律的排列所构成的。（2）生物的繁殖过程是由其基因的复制过程来完成的。同源染色体的交叉或变异会产生新的物种，使生物呈现新的性状。（3）对环境适应能力强的基因或染色体，比适应能力差的基因或染色体有更多的机会遗传到下一代。2.3 遗传算法理论基础2.3.1 模式定理
模式定义：模式是描述种群中在位串的某些确定位置上具有相似性的位串子集的相似性模板。
不失一般性，考虑二值字符集{0，1}，由此可以产生通常的0、1字符串。增加一个符号“*”，称作“通配符”，即“*”既可以被当作“0”，也可以被当作“1”。这样，二值字符集{0，1}就扩展为三值字符集{0，1，*}，由此可以产生诸如0110、0 * 1 1 * *、* * 0 1 * 0等字符串。
基于三值字符集{0，1，*}所产生的能描述具有某些结构相似性的0，1字符串集的字符串称作模式。这里需要强调的是，“*”只是一个描述符，而并非遗传算法中实际的运算符号，它仅仅是为了描述上的方便引入的符号而已。
模式的概念可以简明地描述具有相似结构特点的个体编码字符串。在引入了模式概念之后，遗传算法的本质是对模式所进行的一系列运算，即通过选择操作数将当前群体中的优良模式遗传到下一代群体中，通过交叉操作数进行模式的重组，通过变异操作数进行模式的突变。通过这些遗传运算，一些较差的模式逐步被淘汰，而一些较好的模式逐步被遗传和进化，最终就可以得到问题的最优解。
多个串中隐含着多个不同的模式。确切地说，长度为L的串，隐含着2L个不同的模式，而不同的模式所匹配的串的个数是不同的。为了反映这种确定性的差异，引入模式阶概念。
模式阶定义：模式H中确定位置的个数称作该模式的模式阶，记作O(H)。
比如模式011*1*的阶数为4，而模式0*****的阶数为1。显然，一个模式的阶数越高，其样本数就越少，因而确定性就越高。但是，模式阶并不能反映模式的所有性质。即使具有同阶的模式，在遗传操作下，也会有不同的性质。为此，再引入定义距概念。
定义距定义：在模式H中第一个确定位置和最后一个确定位置之间的距离称作该模式的定义距，记作D(H)。
模式定理：在遗传算法选择、交叉和变异算子的作用下，具有低阶、短定义距，并且其平均适应度高于群体平均适应度的模式，在子代中将按指数级数增长[2]。
模式定理又称为遗传算法的基本定理。模式定理阐述了遗传算法的理论基础，说明了模式的增加规律，同时也给遗传算法的应用提供了指导。根据模式定理，随着遗传算法一代一代地进行，那些定义距短、位数少、适应度高的模式将越来越多，因而可期望最后得到的位串的性能越来越得到改善，并最终趋向全局的最优点。
模式的思路提供了一种简单而有效的方法，使能够在有限字母表的基础上讨论有限长位串的严谨定义的相似性；而模式定理从理论上保证了遗传算法是一个可以用来寻求最优可行解的优化过程。2.3.2 积木块假设
模式定理说明：具有某种结构特征的模式在遗传进化过程中的样本数目，将按照指数级增长。这种模式在遗传算法中非常重要，定义为积木块。
积木块定义：具有低阶、短定义距以及高平均适应度的模式，称作积木块。
之所以称之为积木块，是由于遗传算法的求解过程并不是在搜索空间中逐一地测试各个基因的枚举组合，而是通过一些较好的模式，像搭积木一样，将它们拼接在一起，从而逐渐构造出适应度越来越高的个体编码串。
模式定理说明了积木块的样本数呈指数级增长，也就说明了用遗传算法寻求最优样本的可能性，但它并未指明遗传算法一定能够寻求到最优样本。而积木块假设却说明了遗传算法的这种能力。
积木块假设：个体的积木块通过选择、交叉、变异等遗传算子的作用，能够相互结合在一起，形成高阶、长距、高平均适应度的个体编码串[3-4]。
积木块假设说明了用遗传算法求解各类问题的基本思想，即通过基因块之间的相互拼接能够产生出问题的更好的解，最终生成全局最优解。
从遗传算法的模式定理得到，具有高适应度、低阶、短定义矩的模式的数量会在种群的进化中呈指数形式增长，从而保证了该算法获得最优解的一个必要条件；而另一方面，积木块假设则指出，遗传算法有能力使优秀的模式向着更优的方向进化，即遗传算法有能力搜索到全局最优解。2.4 遗传算法的特点
遗传算法是模拟生物在自然环境中的遗传和进化的过程而形成的一种并行、高效、全局搜索的方法，它主要有以下特点：（1）遗传算法以决策变量的编码作为运算对象。这种对决策变量的编码处理方式，使得在优化计算过程中可以借鉴生物学中染色体和基因等概念，模仿自然界中生物的遗传和进化等机理，方便地应用遗传操作算子。特别是对一些只有代码概念而无数值概念或很难有数值概念的优化问题，编码处理方式更显示出了其独特的优越性。（2）遗传算法直接以目标函数值作为搜索信息。它仅使用由目标函数值变换来的适应度函数值，就可确定进一步的搜索方向和搜索范围，而不需要目标函数的导数值等其他一些辅助信息。实际应用中很多函数无法或很难求导，甚至根本不存在导数，对于这类目标函数的优化和组合优化问题，遗传算法就显示了其高度的优越性，因为它避开了函数求导这个障碍。（3）遗传算法同时使用多个搜索点的搜索信息。遗传算法对最优解的搜索过程，是从一个由很多个体所组成的初始群体开始的，而不是从单一的个体开始的。对这个群体所进行的选择、交叉、变异等运算，产生出新一代的群体，其中包括了很多群体信息。这些信息可以避免搜索一些不必搜索的点，相当于搜索了更多的点，这是遗传算法所特有的一种隐含并行性。（4）遗传算法是一种基于概率的搜索技术。遗传算法属于自适应概率搜索技术，其选择、交叉、变异等运算都是以一种概率的方式来进行的，从而增加了其搜索过程的灵活性。虽然这种概率特性也会使群体中产生一些适应度不高的个体，但随着进化过程的进行，新的群体中总会更多地产生出许多优良的个体。与其他一些算法相比，遗传算法的鲁棒性使得参数对其搜索效果的影响尽可能小。（5）遗传算法具有自组织、自适应和自学习等特性。当遗传算法利用进化过程获得信息自行组织搜索时，适应度大的个体具有较高的生存概率，并获得更适应环境的基因结构。同时，遗传算法具有可扩展性，易于同别的算法相结合，生成综合双方优势的混合算法。2.5 主要应用领域
遗传算法自提出之后，由于其独特的特性，得到了广泛的应用，主要应用领域有[5-7]：函数优化、组合优化、作业调度、智能控制、机器人学、图像处理、人工生命、机器学习等。
函数优化
函数优化是遗传算法的经典应用领域，也是对遗传算法进行性能评价的常用算例。很多人构造出了各种各样的复杂形式的测试函数，其中有连续函数也有离散函数，有凸函数也有凹函数，有低维函数也有高维函数，有确定函数也有随机函数，有单峰值函数也有多峰值函数等；用这些几何特性各具特色的函数来评价遗传算法的性能，更能反映算法的本质效果。而对于一些非线性、多模型、多目标的函数优化问题，用其他优化方法较难求解，而遗传算法却可以方便地得到较好的结果。
组合优化
随着问题规模的增大，组合优化问题的搜索空间也急剧扩大，有时在目前的计算机上用枚举法很难甚至不可能求出其精确最优解。对这类复杂问题，人们已意识到应把主要精力放在寻求其满意解上，而遗传算法正是寻求这种满意解的最佳工具之一。实践证明，遗传算法已经在求解旅行商问题、背包问题、装箱问题、布局优化、图形划分问题等各种具有NP难度的问题中得到了成功的应用。
作业调度
作业调度问题是一种资源分配问题。这里的资源主要是指设备资源，问题的求解目标是要找到一个将一组工件安排到设备上去，以使作业可为“最优”完成的方案。每个作业由一些任务组成，而每个任务必须由特定的设备处理。一个调度是按先后顺序条件将所有任务安排到设备上的一种方案。通常，约束的数目很大，使作业调度问题成为一个非常难解的组合问题。现在，遗传算法已成为解决复杂调度问题的有效工具，在单件生产车间调度、流水线生产间调度、生产规划、任务分配等方面都得到了有效的应用。
智能控制
许多控制领域问题，当考虑到系统优化、自适应、自组织和自学习等方面要求时，一般存在着许多常规方法难以奏效的困难。在智能控制领域中有很多与优化相关的问题需要求解，遗传算法已在其中得到了初步的应用，并显示出良好的效果。例如，用遗传算法进行航空控制系统的优化、使用遗传算法设计空间交会控制器、基于遗传算法的模糊控制器的优化设计、基于遗传算法的参数辨识、基于遗传算法的模糊控制规则的学习、利用遗传算法进行人工神经网络的结构优化设计和权值学习等，都显示出了遗传算法在这些领域中应用的可能性。
机器人学
机器人是一类复杂的难以精确建模的人工系统，而遗传算法的起源就来自于人工自适应系统的研究。所以机器人学理所当然地成为遗传算法的一个重要应用领域。例如，遗传算法已经在移动机器人路径规划、关节机器人运动轨迹规划、机器人逆运动学求解、细胞机器人的结构优化和行为协调等方面得到了研究和应用。
图像处理
图像处理是计算机视觉中的一个重要研究领域。在图像处理过程中，扫描、特征提取、图像分割等不可避免地会存在一些误差，从而影响图像的效果。如何使这些误差最小，是使计算机视觉达到实用化的重要要求。遗传算法在这些图像处理中的优化计算方面找到了用武之地，目前已在模式识别（包括汉字识别）、图像恢复、图像边缘特征提取等方面得到了应用。
人工生命
人工生命是用计算机、机械等人工媒体模拟或构造出的具有自然生物系统特有行为的人造系统。自组织能力和自学习能力是人工生命的两大主要特征。人工生命与遗传算法有着密切的关系。基于遗传算法的进化模型是研究人工生命现象的重要基础理论，虽然人工生命的研究尚处于启蒙阶段，但遗传算法已在其进化模型、学习模型、行为模型、自组织模型等方面显示出了初步的应用能力，并且必将得到更为深入的应用和发展。人工生命与遗传算法相辅相成，遗传算法为人工生命的研究提供一个有效的工具，人工生命的研究也必将促进遗传算法的进一步发展。
机器学习
迄今，自然界只有人类才真正具有完善的学习能力，机器学习实际上是对人的学习机制的一种抽象和模拟，是一种理想的学习模型。基于符号学习的机器学习系统、条件反射型学习系统、类比式学习系统、推理学习系统等，只具备一些较初级的学习能力。近年来，由于遗传算法的发展，基于进化机制的遗传学习成为了一种新的机器学习方法，它将知识表达为另一种符号形式——遗传基因型，通过模拟生物的进化过程，实现专门领域知识的合理增长型学习，所以有的学者称之为次符号学习方法。参考文献
[1] 杨淑莹, 张桦. 群体智能与仿生计算——Matlab技术实现[M]. 北京: 电子工业出版社, 2012: 13-30.
[2] Holland J H. Adaptation in natural and artificial systems[M]. Cambridge，Massachusetts: MITPress, 1992.
[3] Bagley J D. The Behavior of Adaptive Systems Which Employ Genetic and Correlation Algoritllms[D]. University of Michigan, 1967.
[4] Rosenberg R S. Simulation of Genetic populations with Biochemical Properties[D].University of Michigan, 1967.
[5] G1odberg D E，Riehardson J. Genetic Algorithms with Sharing for Multimodal Function Otimization[C]. conf. on GenetiCe Algorithms, Lawrence Erlbaum Assoeiates, 1987: 41-49.
[6] 雷英杰, 张善文, 李续武，等. 遗传算法工具箱及应用（第二版）[M]. 西安：西安电子科技大学出版社，2014: 1-8.
[7] 温政. 精通MATLAB智能算法[M]. 北京：清华大学出版社, 2015: 165-192.第3章遗传算法原理与实现
遗传算法是模拟生物在自然环境中的遗传和进化的过程而形成的自适应全局优化搜索算法。它借用了生物遗传学的观点，通过自然选择、遗传和变异等作用机制，实现各个个体适应性的提高。3.1 遗传算法的基本概念
简单而言，遗传算法使用群体搜索技术，将种群代表一组问题解，通过对当前种群施加选择、交叉和变异等一系列遗传操作来产生新一代的种群，并逐步使种群进化到包含近似最优解的状态。由于遗传算法是自然遗传学与计算机科学相互渗透而形成的计算方法，所以遗传算法中经常会使用遗传学中一些有关自然进化的基础术语[1]，其对应关系如表3.1所示。表3.1 遗传学与遗传算法术语对应关系
群体和个体
群体是生物进化过程中的一个集团，表示可行解集。
个体是组成群体的单个生物体，表示可行解。
染色体和基因
染色体是包含生物体所有遗传信息的化合物，表示可行解的编码。
基因是控制生物体某种性状（即遗传信息）的基本单位，表示可行解编码的分量。
遗传编码
遗传编码将优化变量转化为基因的组合表示形式，优化变量的编码机制有二进制编码、十进制编码（实数编码）等。
二进制编码
这里举例说明二进制编码的原理和实现。例如求实数区间[0，4]上函数f(x)的最大值，传统的方法是不断调整自变量x本身的值，直到获得函数最大值。遗传算法则不对参数本身进行调整，而是首先将参数进行编码，形成位串，再对位串进行进化操作。在这里，假设使用二进制编码形式，可以由长度为6 的位串表示变量x，即从“000000”到“111111”。并将中间的取值映射到实数区间[0，4]内。由于从整数上来看，6 位长度的二进制编码位串可以表示0～63，所以对应[0，4]的区间，每个相邻值之间的阶跃值为4/63≈0.0635，这个就是编码精度。一般来说，编码精度越高，所得到的解的质量也越高，意味着解更为优良；但同时，由于遗传操作所需的计算量也更大，算法的耗时将更长。因而在解决实际问题时，编码位数需要适当选择。
实数编码
基于二进制编码的个体尽管操作方便，计算简单，但也存在着一些难以克服的困难而无法满足所有问题的要求。例如，对于高维、连续优化问题，由于从一个连续量离散化为一个二进制量本身就存在误差，使得算法很难求得精确解。而要提高解的精度又必须加长编码串的长度，造成解空间扩大，算法效率下降。同时，二进制编码也不利于反映所求问题的特定知识，对问题信息和知识利用得不充分也会阻碍算法效率的进一步提高。为了解决二进制编码产生的问题，人们在解决一些数值优化问题（尤其是高维、连续优化问题）时， 经常采用实数编码方式。实数编码的优点是计算精确度高，便于和经典连续优化算法结合，适用于数值优化问题；但其缺点是适用范围有限，只能用于连续变量问题。
适应度
适应度即生物群体中个体适应生存环境的能力。在遗传算法中用来评价个体优劣的数学函数，称为个体的适应度函数。
遗传算法在进化搜索中基本上不用外部信息，仅以适应度函数为依据。它的目标函数不受连续可微的约束，且定义域可以为任意集合。对适应度函数的唯一要求是，针对输入可计算出能进行比较的结果。这一特点使得遗传算法应用范围很广。在具体应用中，适应度函数的设计要结合求解问题本身的要求而定。适应度函数评估是选择操作的依据，适应度函数设计直接影响到遗传算法的性能。常见的适应度函数构造方法主要有：目标函数映射成适应度函数、基于序的适应度函数等。
遗传操作
遗传操作是优选强势个体的“选择”、个体间交换基因产生新个体的“交叉”、个体基因信息突变而产生新个体的“变异”这三种变换的统称。在生物进化过程中，一个群体中生物特性的保持是通过遗传来继承的。生物的遗传主要是通过选择、交叉、变异三个过程把当前父代群体的遗传信息遗传给下一代（子代）成员。与此对应，遗传算法中最优解的搜索过程也模仿生物的这个进化过程，使用所谓的遗传算子来实现，即选择算子、交叉算子、变异算子。3.2 遗传算法的基本算子
选择算子
选择算子是根据个体的适应度，按照一定的规则或方法，从第t代群体P(t)中选择出一些优良的个体遗传到下一代群体P(t + 1)中。
其中，“轮盘赌”选择法是遗传算法中最早提出的一种选择方法，由Holland提出，因为它简单实用，所以被广泛采用。它是一种基于比例的选择，利用各个个体适应度所占比例的大小来决定其子孙保留的可能性。若某个个体i的适应度为fi，种群大小为NP，则它被选取的概率表示为：
个体适应度越大，则其被选择的机会也越大；反之亦然。为了选择交叉个体，需要进行多轮选择。每一轮产生一个[0，1]内的均匀随机数，将该随机数作为选择指针来确定被选个体。
交叉算子
交叉是指将群体P(t)中选中的各个个体随机搭配，对每一对个体，以某一概率（交叉概率Pc）交换它们之间的部分染色体。通过交叉，遗传算法的搜索能力得以飞跃提高。交叉操作一般分为以下几个步骤：
首先，从交配池中随机取出要交配的一对个体；
然后，根据位串长度L，对要交配的一对个体，随机选取[1，L-1]中的一个或多个整数k作为交叉位置；
最后，根据交叉概率Pc实施交叉操作，配对个体在交叉位置处，相互交换各自的部分基因，从而形成新的一对个体。
变异算子
变异是指对群体中的每个个体，以某一概率（变异概率Pm）将某一个或某一些基因座上的基因值改变为其他的等位基因值。根据个体编码方式的不同，变异方式有：二进制变异、实值变异。对于二进制变异，对相应的基因值取反；对于实值变异，对相应的基因值用取值范围内的其他随机值替代。
变异操作的一般步骤为：首先，对种群中所有个体按事先设定的变异概率判断是否进行变异；然后，对进行变异的个体随机选择变异位进行变异。3.3 标准遗传算法
标准遗传算法是指由美国J. H. Holland教授与他的同事和学生于1975年研究出的遗传算法理论和方法[2]。20世纪60年代中期，Holland提出了位串编码技术。这种编码既适用于变异操作，又适用于交叉操作，并强调将交叉作为主要的遗传操作。随后，他将该算法应用到自然和人工系统的自适应行为的研究中。Holland早期有关遗传算法的许多概念一直沿用至今，遗传算法通用的编码技术和简单有效的遗传操作为其后来的成功应用和广泛应用奠定了基础。
标准遗传算法又称为经典遗传算法，它的优化变量由二进制编码来描述，多个优化变量的二进制编码串接在一起组成染色体，这种编码既适用于变异操作，又适用于交叉操作。在创建初始群体时，代表个体的二进制串是在一定字长的限制下随机产生的。交叉算子作用在按交叉概率选中的两个染色体上，随机选中交叉位置，将两个染色体上对应于这些位置上的二进制数值交换，生成两个新的个体；而变异算子作用在按变异概率随机选中的个体上，一般是随机选定变异位，将该位的二进制值取反，生成一个新的个体。3.4 遗传算法的改进方向
标准遗传算法的主要本质特征，在于群体搜索策略和简单的遗传算子，这使得遗传算法获得了强大的全局最优解搜索能力、问题域的独立性、信息处理的并行性、应用的鲁棒性和操作的简明性，从而成为一种具有良好适应性和可规模化的求解方法。但大量的实践和研究表明，标准遗传算法存在局部搜索能力差和“早熟”等缺陷，不能保证算法的收敛。
在现有的许多文献中出现了针对标准遗传算法的各种改进算法，并取得了一定的成效[3-6]。它们主要集中在对遗传算法的性能有重大影响的6个方面：编码机制、选择策略、交叉算子、变异算子、特殊算子和参数设计（包括群体规模、交叉概率、变异概率）等。
此外，遗传算法与差分进化算法、免疫算法、蚁群算法、粒子群算法、模拟退火算法、禁忌搜索算法和量子计算等结合起来所构成的各种混合遗传算法，可以综合遗传算法和其他算法的优点，提高运行效率和求解质量。3.5 遗传算法流程
遗传算法使用群体搜索技术，通过对当前群体施加选择、交叉、变异等一系列遗传操作，从而产生出新一代的群体，并逐步使群体进化到包含或接近最优解的状态。
在遗传算法中，将n维决策向量X = [x1x2 … xn]T用n个记号Xi（i = 1，2, …, n）所组成的符号串X来表示：
把每一个Xi看作一个遗传基因，它的所有可能取值称为等位基因，这样，X就可看作由n个遗传基因所组成的一个染色体。一般情况下，染色体的长度是固定的，但对一些问题来说它也可以是变化的。根据不同的情况，这里的等位基因可以是一组整数，也可以是某一范围内的实数，或者是一个纯粹的记号。最简单的等位基因是由0或1的符号串组成的，相应的染色体就可以表示为一个二进制符号串。这种编码所形成的排列形式是个体的基因型，与它对应的X值是个体的表现型。染色体X也称为个体X，对于每一个个体X，要按照一定的规则确定其适应度。个体的适应度与其对应的个体表现型X的目标函数值相关联，X越接近于目标函数的最优点，其适应度越大；反之，适应度越小。
在遗传算法中，决策变量X组成了问题的解空间。对问题最优解的搜索是通过对染色体X的搜索过程来完成的，因而所有的染色体X就组成了问题的搜索空间。
生物的进化过程主要是通过染色体之间的交叉和染色体基因的变异来完成的。与此相对应，遗传算法中最优解的搜索过程正是模仿生物的这个进化过程，进行反复迭代，从第t代群体P(t)，经过一代遗传和进化后，得到第t + 1代群体P(t + 1)。这个群体不断地经过遗传和进化操作，并且每次都按照优胜劣汰的规则将适应度较高的个体更多地遗传到下一代，这样最终在群体中将会得到一个优良的个体X，将达到或接近于问题的最优解。
遗传算法的运算流程如图3.1所示。具体步骤如下：（1）初始化。设置进化代数计数器g=0，设置最大进化代数G，随机生成NP个个体作为初始群体P(0)。图3.1 遗传算法的运算流程（2）个体评价。计算群体P(t)中各个个体的适应度。（3）选择运算。将选择算子作用于群体，根据个体的适应度，按照一定的规则或方法，选择一些优良个体遗传到下一代群体。（4）交叉运算。将交叉算子作用于群体，对选中的成对个体，以某一概率交换它们之间的部分染色体，产生新的个体。（5）变异运算。将变异算子作用于群体，对选中的个体，以某一概率改变某一个或某一些基因值为其他的等位基因。群体P(t)经过选择、交叉和变异运算之后得到下一代群体P(t + 1)。计算其适应度值，并根据适应度值进行排序，准备进行下一次遗传操作。（6）终止条件判断：若g≤G，则g = g + 1，转到步骤（2）；若g > G，则此进化过程中所得到的具有最大适应度的个体作为最优解输出，终止计算。3.6 关键参数说明
下面介绍一下遗传算法的主要参数，它在程序设计与调试中起着至关重要的作用。
群体规模NP
群体规模将影响遗传优化的最终结果以及遗传算法的执行效率。当群体规模NP太小时，遗传优化性能一般不会太好。采用较大的群体规模可以减小遗传算法陷入局部最优解的机会，但较大的群体规模意味着计算复杂度高。一般NP取10～200。
交叉概率Pc
交叉概率Pc控制着交叉操作被使用的频度。较大的交叉概率可以增强遗传算法开辟新的搜索区域的能力，但高性能的模式遭到破坏的可能性增大；若交叉概率太低，遗传算法搜索可能陷入迟钝状态。一般Pc取0.25～1.00。
变异概率Pm
变异在遗传算法中属于辅助性的搜索操作，它的主要目的是保持群体的多样性。一般低频度的变异可防止群体中重要基因的可能丢失，高频度变异将使遗传算法趋于纯粹的随机搜索。通常Pm取为0.001～0.1。
遗传运算的终止进化代数G
终止进化代数G是表示遗传算法运行结束条件的一个参数，它表示遗传算法运行到指定的进化代数之后就停止运行，并将当前群体中的最佳个体作为所求问题的最优解输出。一般视具体问题而定，G取值可在100～1000之间。3.7 MATLAB实例仿真
例3.1 用标准遗传算法求函数 f(x) = x + 10cos(5x) + 7sin(4x) 的最小值，其中x的取值范围为[0，10]。这是一个有多个局部极值的函数，其函数值图形如图3.2所示。图3.2 例3.1函数值图形
其MATLAB实现程序如下：
解：仿真过程如下：（1）初始化种群数目为NP = 50，染色体二进制编码长度为L = 20，最大进化代数为G = 100，交叉概率Pc = 0.8，变异概率Pm = 0.05。（2）产生初始种群，将二进制编码转换成十进制，计算个体适应度值，并进行归一化；采用基于轮盘赌的选择操作、基于概率的交叉和变异操作，产生新的种群，并把历代的最优个体保留在新种群中，进行下一步遗传操作。（3）判断是否满足终止条件：若满足，则结束搜索过程，输出优化值；若不满足，则继续进行迭代优化。
优化结束后，其适应度进化曲线如图3.3所示，优化结果为x = 4.3715，函数f(x)的最小值为-12.39。图3.3 例3.1适应度进化曲线
MATLAB源程序如下：
例3.2 计算函数的最小值，其中个体x的维数n = 10。这是一个简单的平方和函数，只有一个最小点x = (0，0，…，0)，理论最小值f(0，0，…，0) = 0。当x的维数n = 2时，其函数值图形如图3.4所示。其MATLAB实现程序如下：图3.4 例3.2函数值图形
解：仿真过程如下：（1）初始化种群数目为NP = 100，染色体基因维数为D = 10，最大进化代数为G = 1000，交叉概率Pc = 0.8，变异概率Pm = 0.05。（2）产生实值初始种群，计算个体适应度值，并进行归一化；采用基于轮盘赌的选择操作、基于概率的交叉和变异操作，产生新的种群，并把历代的最优个体保留在新种群中，进行下一步遗传操作。（3）判断是否满足终止条件：若满足，则结束搜索过程，输出优化值；若不满足，则继续进行迭代优化。
优化结束后，其适应度进化曲线如图3.5所示，优化后的结果为x = [0.0035-0.0353 0.1694 -0.0767 -0.0341 -0.0650 -0.0004 0.0219 0.0608 0.0058 -0.0454]，函数f(x) 的最小值为-0.04544。图3.5 例3.2适应度进化曲线
MATLAB源程序如下：
例3.3 旅行商问题（TSP问题）。假设有一个旅行商人要拜访20个城市，城市坐标随机生成。他需要选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择要求是：所选路径的路程为所有路径之中的最小值。
解：仿真过程如下：（1）初始化种群数目为NP = 200，染色体基因维数为N = 20，最大进化代数为G = 1000，随机生成N个城市的坐标。（2）产生初始种群，计算个体适应度值，即路径长度；采用基于概率的方式选择进行操作的个体；对选中的成对个体，随机交叉其选中的成对城市坐标，以确保交叉后路径每个城市只到访一次；对选中的单个个体，随机交换其一对城市坐标作为变异操作，产生新的种群，进行下一次遗传操作。（3）判断是否满足终止条件：若满足，则结束搜索过程，输出优化值；若不满足，则继续进行迭代优化。
优化后的路径如图3.6所示，适应度进化曲线如图3.7所示。图3.6 例3.3优化后的路径图3.7 例3.3适应度进化曲线
MATLAB源程序如下：参考文献
[1] 包子阳，余继周. 智能优化算法及其MATLAB实例[M]. 北京: 电子工业出版社, 2016: 9-18.
[2] Holland J H. Adaptation in natural and artificial systems[M]. Ann Arbor:University of Michigan press, 1975.
[3] Yuan Xiaoyan, Cao Ling, Xia Liangzheng. Adaptive genetic algorithm with the criterion of premature convergence[J]. Journal of Southeast University(English Edition), 2003, 19(1): 40-43.
[4] Rudolph G. Convergence analysis of canonical genetic algorithms[J]. IEEE Transactions on Neural Networks, 1994, 5(l): 96-101.
[5] Mahofud S W, Glodberg D E. A Genetic Algorithm for Parallel Simulated Annealing[C]. Parallel Problem Solving from Nature 2, North Holland, 1992:301-310.
[6] 梁旭, 黄明, 宁涛, 等. 现代智能优化混合算法及其应用(第二版)[M]. 北京:电子工业出版社, 2014: 51-88.第4章遗传算法在稀布线阵中的应用4.1 引言
理论上，由单个天线阵元构成的天线就可以完成发射和接收电磁波的任务。但在实际应用中，往往要求天线具有较强的方向性和很高的增益，有时还要求天线波束可以扫描，并具有一定的形状等，这时就需要利用多个天线阵元按一定方式排列成阵列天线。
阵列天线是根据电磁波在空间相互干涉的原理，把具有相同结构、相同尺寸的某种基本天线按一定规律排列在一起组成的。如果按直线排列，就构成直线阵；如果排列在一个平面内，就为平面阵。若天线阵元排列与载体表面形状一致，称为共形阵，共形阵中的所有天线阵元往往不在一个平面上，因此也可以称为非平面阵。
直线阵列天线是最基本的阵列天线，广泛应用于一维电扫描的相控阵雷达中。由多个直线阵列按行或按列排列，可组成平面阵列。遗传算法由于在解决大空间、非线性等复杂问题的优势，在直线阵列优化中得到了成功应用[1-2]。本章采用遗传算法进行直线阵列天线的稀疏优化排列、带约束条件的稀疏优化排列、稀布优化排列，达到减少天线阵元、降低成本，同时防止出现栅瓣，得到低旁瓣方向图的目的。4.1.1 方向图乘积原理
阵列天线的阵元数目、阵元间距、分布形式、激励相位和幅度五个因素决定了阵列天线波束方向图的形成，控制这五个因素的变化就可以改变天线的辐射特征。描绘天线辐射特性随着空间方向坐标变化关系的图形叫作辐射方向图。阵列天线理论的出发点是叠加原理，此原理应用于阵列天线的远区辐射场就是方向图乘积原理[3]。
假设一个阵列天线，由M个阵元组成，第m个阵元在阵中的方向图为，则由阵列天线的知识，整个阵列的方向图为函数形式可以表示为
若每个阵元的相同，则式（4.1）可以改写为
式中，f(ϕ,)θ表示为阵元方向图，也可以称为阵元因子，S表示为阵列因子，它和天线阵元在阵列中所处的位置有关。式（4.2）就是方向图乘积原理的形式，即阵列方向图等于阵元因子与阵列因子的乘积。4.1.2 任意阵列的方向图函数
设阵列天线的各个阵元安装在一个曲面上，只要知道各个天线阵元在曲面上的坐标位置及其在阵列中的阵元方向图函数，就可以按要求的共形阵列天线方向图的指向，计算出各个天线阵元通道上应实现的幅度和相位补偿，以及计算出该共形阵列天线的方向图函数。
共形阵列天线的性能与平面阵列天线一样，可用其天线方向图函数来表示，由天线方向图可计算出其天线波束的指向，改变影响天线波束指向的参数即可实现天线的波束扫描。
设共有M个阵列天线阵元安装在图4.1上，并取坐标原点O为参考点，第m个阵元在阵列中的位置为，它的场强辐射方向图为，每个天线阵元的相位与幅度加权系数分别为mα和，也就是说，第m个天线阵元的复加权系数可以表示为
则整个阵列所有天线阵元在(ϕ,)θ方向上的方向图可以表示为图4.1 任意阵列天线阵元位置矢量示意图
上式中，，ΔRm是第m个天线阵元到目标的距离与参考点O到目标距离之间的差值，R是阵列相位参考点O到远区目标的距离，λ是接收信号电磁波的波长。由于阵列相位参考点到O目标距离
试读结束[说明：试读内容隐藏了图片]