实验六 遗传算法与优化设计一、实验目的1. 了解遗传算法的基本原理和基本操作（选择、交叉、变异）；2. 学习使用Matlab 中的遗传算法工具箱(gatool)来解决优化设计问题；二、实验原理及遗传算法工具箱介绍1. 一个优化设计例子图1所示是用于传输微波信号的微带线(电极)的横截面结构示意图，上下两根黑条分别代表上电极和下电极，一般下电极接地，上电极接输入信号，电极之间是介质(如空气，陶瓷等)。

微带电极的结构参数如图所示，W 、t 分别是上电极的宽度和厚度，D 是上下电极间距。

当微波信号在微带线中传输时，由于趋肤效应，微带线中的电流集中在电极的表面，会产生较大的欧姆损耗。

根据微带传输线理论，高频工作状态下（假定信号频率1GHz ），电极的欧姆损耗可以写成（简单起见，不考虑电极厚度造成电极宽度的增加）：图1 微带线横截面结构以及场分布示意图 {}28.6821ln 5020.942ln 20.942S W R W D D D t D W D D W W t D W W D e D D παπππ=+++-+++⎛⎫⎡⎤⎛⎫ ⎪ ⎪⎢⎥ ⎪⎝⎭⎣⎦⎡⎤⎛⎫⎝⎭ ⎪⎢⎥⎝⎭⎣⎦ (1) 其中πρμ0=S R 为金属的表面电阻率，为电阻率。

可见电极的结构参数影响着电极损耗，通过合理设计这些参数可以使电极的欧姆损耗做到最小，这就是所谓的最优化问题或者称为规划设计问题。

此处设计变量有3个：W 、D 、t ，它们组成决策向量[W, D ,t ] T ，待优化函数(,,)W D t α称为目标函数。

上述优化设计问题可以抽象为数学描述：()()min ..0,1,2,...,jf X s tg X j p ⎧⎪⎨⎪≤=⎩ (2) 其中()Tn x x x X ,...,,21=是决策向量，x 1，…，x n 为n 个设计变量。

这是一个单目标的数学规划问题：在一组针对决策变量的约束条件()0,1,...,j g X j p ≤=下，使目标函数最小化（有时也可能是最大化，此时在目标函数()X f 前添个负号即可）。

满足约束条件的解X 称为可行解，所有满足条件的X 组成问题的可行解空间。

2. 遗传算法基本原理和基本操作遗传算法(Genetic Algorithm, GA)是一种非常实用、高效、鲁棒性强的优化技术，广泛应用于工程技术的各个领域(如函数优化、机器学习、图像处理、生产调度等)。

遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化算法。

按照达尔文的进化论，生物在进化过程中“物竞天择”，对自然环境适应度高的物种被保留下来，适应度差的物种而被淘汰。

物种通过遗传将这些好的性状复制给下一代，同时也通过种间的交配(交叉)和变异不断产生新的物种以适应环境的变化。

从总体水平上看，生物在进化过程中子代总要比其父代优良，因此生物的进化过程其实就是一个不断产生优良物种的过程，这和优化设计问题具有惊人的相似性，从而使得生物的遗传和进化能够被用于实际的优化设计问题。

按照生物学知识，遗传信息基因(Gene)的载体是染色体(Chromosome)，染色体中一定数量的基因按照一定的规律排列（即编码），遗传基因在染色体中的排列位置称为基因座（Locus ），在同一个基因座上所有可能的基因就称为等位基因（Allele ），生物所持有的基因以及基因的构成形式称为生物的基因型（Genotype ），而该生物在环境中所呈现的相应性状称为该生物的表现型（Phenotype ）。

在遗传过程中，染色体上的基因能够直接复制给子代从而使得子代具有亲代的特征，此外，两条染色体之间也通过交叉(Crossover)而重组，即两个染色体在某个相同的位置处被截断，其前后两串基因交叉组合而形成两个新的染色体。

在基因复制时也会产生微小的变异（Mutation ），从而也产生了新的染色体。

因此交叉和变异是产生新物种的主要途径。

由于自然选择，在子代群体新产生的物种（或染色体）当中，只有那些对环境适应度高的才能生存下来，即适应度越高的被选择的概率也越大，然后又是通过遗传和变异再自然选择，一代一代不断进化。

因此生物遗传和进化的基本过程就是：选择(即复制)、交叉和变异。

遗传算法就是通过模拟生物进化的这几个基本过程而实现的。

① 编码编码是设计遗传算法首要解决的问题。

在生物进化中，选择、交叉、变异这些基本过程都是基于遗传信息的编码方式进行的，即基于染色体的基因型而非表现型，因此要模拟生物进化过程，遗传算法必须首先对问题的可行解X （决策向量）进行某种编码，以便借鉴生物学中染色体和基因等概念。

在遗传算法中，将每一个决策向量X 用一个染色体V 来表示：()[]112()(),...,,,...,T Tn m X x x V v v v =⇒= 表现型 基因型 (3)其中每一个v i 代表一个基因，染色体的长度m 不一定等于设计变量的数目n ，取决于染色体上基因的编码方式。

一般有两种编码方式：二进制编码和浮点数编码。

如果是二进制编码，每一个设计变量x i 的真实值用一串二进制符号0和1按照一定的编码规则来表示，每个二进制符号就代表一个基因，因此染色体长度要远大于设计变量的数目。

这种由二进制编码构成的排列形式V 就是染色体（也称个体）的基因型，而基因型经过解码后所对应的决策向量X （即可行解）就是个体的表现型。

如果是浮点数编码，每个设计变量i x 用其取值范围[]i iU U max min ,内的一个浮点数表示，构成染色体的一个基因v i ，因此个体的编码长度m 也就等于决策变量的个数n ，由于这种编码方式使用的是决策变量的真实值，所以也称真值编码方法。

无论哪种编码方式，所有可能的染色体（个体）V 构成问题的搜索空间（种群），遗传算法对最优解的搜索就是在搜索空间中搜索适应度最高的染色体(后面叙述适应度的计算)，因此通过编码将一个问题的可行解从其解空间转换到了遗传算法能够处理的搜索空间。

经过个体的编码后，就可以进行遗传算法的基本操作：选择、交叉和变异。

② 选择(复制)操作选择也就是复制，是在群体中选择适应度高的个体产生新群体的过程。

生物的进化是以集团为主体的，与此相应，遗传算法的运算对象是有M 个个体或染色体组成的集合，称为种群，M 也称为种群规模。

遗传算法在模拟自然选择时，以个体的适应度（Fitness ）高低为选择依据，即适应度高的个体被遗传到下一代种群的概率较高，而适应度低的个体遗传到下一代的概率则相对较低。

个体适应度由适应度函数()()X f Fit 计算，适应度函数总是和个体表现型(i.e. X )的目标函数值f(X)关联，一般是由目标函数经过一定的变换得到。

一种最简单的方法就是直接使用目标函数f(X)作为适应度函数：()()()()f X Fit f X f X =-⎧⎨⎩目标函数最小化问题目标函数最大化问题(4) 选定了适应度函数之后，个体适应度也随之确定，则在选择操作时，个体被选中的概率()M i FF p M i iii ,...,2,1 1==∑= (5) 其中F i 为个体的适应度。

这种选择方式称为比例选择，也称轮盘赌选择。

除此之外还有多种选择方法，如随机竞争选择、均匀选择、无回放随机选择等，不一一介绍。

③ 交叉操作所谓交叉就是以一定的概率(交叉概率)从群体中选择两个个体(染色体)按照某种方式交换其部分基因，从而形成两个新的个体。

在遗传算法中它是产生新个体同时也是获得新的优良个体的主要方法，它决定了遗传算法的全局搜索能力。

对于不同的编码方式，交叉操作的具体方法也不相同，对于浮点数编码，一般使用算术交叉；对于二进制编码有单点交叉和多点交叉等方式。

不论何种方式，在交叉操作时首先应定义交叉概率P c ，这个概率表明种群中参与交叉的个体数目的期望值是M P C ，M 是种群规模。

通常交叉概率应取较大的值，以便产生较多的新个体，增加全局搜索力度。

但是P c 过大时优良个体被破坏的可能性也越大，如果P c 太小则搜索进程变慢，影响算法的运行效率。

一般建议的取值范围是0.4–0.99。

④ 变异操作遗传算法中的变异操作就是将染色体上某些基因座上的基因以一定的变异概率P m 用其他的等位基因替代，从而形成新的个体。

对于浮点数编码，变异操作就是将变异点处的基因用该基因取值范围内的一个随机数替换。

对于二进制编码则是将变异点处的基因由“1”变成“0”，“0”变成“1”。

变异操作也有多种方法，如均匀变异、非均匀变异、高斯变异等。

变异操作的概率P m 要比交叉操作的概率P c 小得多，变异只是产生新个体的辅助手段。

但它是遗传算法必不可少的一个环节，因为变异操作决定了算法的局部搜索能力，它弥补了交叉操作无法对搜索空间的细节进行局部搜索的不足，因此交叉和变异操作相互配合共同完成对搜索空间的全局和局部搜索。

以上简要介绍了遗传算法的基本原理和操作，归纳起来，基本遗传算法一般可以表示为一个8元组：()T ψΓΦ=,,,,,,,0M P E C SGA (6)式中，C 个体的编码方法；E 个体适应度评价函数；P 0 初始种群；M 种群规模； 选择操作； 交叉操作； 变异操作； 是进化终止代数(进化终止条件)。

其中有4个运行参数需要预先设定：M, T, Pc ，P m种群规模M 一般取为20~100； 终止代数T 一般取100~500；交叉概率P c 一般取0.4~0.99； 变异概率P m 一般取0.0001~0.1最后给出遗传算法的基本步骤：① 选择二进制编码或浮点数编码把问题的解表示成“染色体”。

② 随机产生一群“染色体”(个体)，也就是初始种群。

③ 计算每一个个体的适应度值，按适者生存的原则，从中选择出适应度较大的“染色体”进行复制，再通过交叉、变异过程产生更适应环境的新一代“染色体”群，即子代。

④ 重复第3步。

经过这样的一代一代地进化，最后就会收敛到最适应环境（适应度最大）的一个“染色体”(即个体)上，它就是问题的最优解。

图2给出了基本遗传算法设计流程图，其中t 代表当前代数，T 是进化终止代数。

图2 基本遗传算法设计流程图3. Matlab 遗传算法工具箱(gatool)Matlab 的遗传算法工具箱有一个精心设计的图形用户界面，可以帮助用户直观、方便、快速地利用遗传算法求解最优化问题。

在Matlab 命令窗口输入命令：gatool可以打开遗传算法工具箱的图形用户界面，如图3所示。

GA 工具箱的参数设置步骤如下：图3. 遗传算法工具(1) 首先，使用遗传算法工具箱必须输入下列信息：① Fitness function(适应度函数)这里指的是待优化的函数，也即目标函数。

该工具箱总是试图寻找目标函数的最小值。

输入适应度函数的格式为@fitnessfun ，其中符号@产生函数fitnessfun 的句柄，fitnessfun 代表用户编写的计算适应度函数(目标函数)的M 文件名，该M 文件的编写方法如下：假定我们要计算Rastrigin 函数的最小值22121212(,)2010(cos2cos2)f x x x x x x ππ=++-+ (7)M 函数文件确定这个函数必须接受一个长度为2的行向量X ，也即决策向量，向量的长度等于变量数目，行向量X 的每个元素分别和变量x 1和x 2对应。