遗传算法实验设计与仿真

硕士生考查课程考试试卷考试科目：考生姓名：考生学号：学院：专业：考生成绩：任课老师(签名)考试日期：年月日午时至时《MATLAB 教程》试题：A 、利用MATLAB 设计遗传算法程序，寻找下图11个端点最短路径，其中没有连接端点表示没有路径。

要求设计遗传算法对该问题求解。

ae h kB 、设计遗传算法求解f (x)极小值，具体表达式如下：321231(,,)5.12 5.12,1,2,3i i i f x x x x x i =⎧=⎪⎨⎪-≤≤=⎩∑ 要求必须使用m 函数方式设计程序。

C 、利用MATLAB 编程实现：三名商人各带一个随从乘船渡河，一只小船只能容纳二人，由他们自己划行，随从们密约，在河的任一岸，一旦随从的人数比商人多，就杀人越货，但是如何乘船渡河的大权掌握在商人手中，商人们怎样才能安全渡河？D 、结合自己的研究方向选择合适的问题，利用MATLAB 进行实验。

以上四题任选一题进行实验，并写出实验报告。

选择题目：B 、设计遗传算法求解f (x)极小值，具体表达式如下：321231(,,)5.12 5.12,1,2,3i i i f x x x x x i =⎧=⎪⎨⎪-≤≤=⎩∑ 要求必须使用m 函数方式设计程序。

一、问题分析（10分）这是一个简单的三元函数求最小值的函数优化问题，可以利用遗传算法来指导性搜索最小值。

实验要求必须以matlab 为工具，利用遗传算法对问题进行求解。

在本实验中，要求我们用M 函数自行设计遗传算法，通过遗传算法基本原理，选择、交叉、变异等操作进行指导性邻域搜索，得到最优解。

二、实验原理与数学模型（20分）（1）试验原理：用遗传算法求解函数优化问题，遗传算法是模拟生物在自然环境下的遗传和进化过程而形成的一种自适应全局优化概率搜索方法。

其采纳了自然进化模型，从代表问题可能潜在解集的一个种群开始，种群由经过基因编码的一定数目的个体组成。

每个个体实际上是染色体带有特征的实体；初始种群产生后，按照适者生存和优胜劣汰的原理，逐代演化产生出越来越好的解：在每一代，概据问题域中个体的适应度大小挑选个体；并借助遗传算子进行组合交叉和主客观变异，产生出代表新的解集的种群。

MATLAB实验遗传算法与优化设计遗传算法与优化设计一实验目的1 了解遗传算法的基本原理和基本操作选择交叉变异2 学习使用Matlab中的遗传算法工具箱 gatool 来解决优化设计问题二实验原理及遗传算法工具箱介绍1 一个优化设计例子图1所示是用于传输微波信号的微带线电极的横截面结构示意图上下两根黑条分别代表上电极和下电极一般下电极接地上电极接输入信号电极之间是介质如空气陶瓷等微带电极的结构参数如图所示Wt分别是上电极的宽度和厚度D是上下电极间距当微波信号在微带线中传输时由于趋肤效应微带线中的电流集中在电极的表面会产生较大的欧姆损耗根据微带传输线理论高频工作状态下假定信号频率1GHz电极的欧姆损耗可以写成简单起见不考虑电极厚度造成电极宽度的增加图1 微带线横截面结构以及场分布示意图1其中为金属的表面电阻率为电阻率可见电极的结构参数影响着电极损耗通过合理设计这些参数可以使电极的欧姆损耗做到最小这就是所谓的最优化问题或者称为规划设计问题此处设计变量有3个WDt它们组成决策向量[W D t] T待优化函数称为目标函数上述优化设计问题可以抽象为数学描述2其中是决策向量x1xn为n个设计变量这是一个单目标的数学规划问题在一组针对决策变量的约束条件下使目标函数最小化有时也可能是最大化此时在目标函数前添个负号即可满足约束条件的解X 称为可行解所有满足条件的X组成问题的可行解空间2 遗传算法基本原理和基本操作遗传算法 Genetic Algorithm GA 是一种非常实用高效鲁棒性强的优化技术广泛应用于工程技术的各个领域如函数优化机器学习图像处理生产调度等遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化算法按照达尔文的进化论生物在进化过程中物竞天择对自然环境适应度高的物种被保留下来适应度差的物种而被淘汰物种通过遗传将这些好的性状复制给下一代同时也通过种间的交配交叉和变异不断产生新的物种以适应环境的变化从总体水平上看生物在进化过程中子代总要比其父代优良因此生物的进化过程其实就是一个不断产生优良物种的过程这和优化设计问题具有惊人的相似性从而使得生物的遗传和进化能够被用于实际的优化设计问题按照生物学知识遗传信息基因Gene 的载体是染色体Chromosome 染色体中一定数量的基因按照一定的规律排列即编码遗传基因在染色体中的排列位置称为基因座Locus在同一个基因座上所有可能的基因就称为等位基因Allele生物所持有的基因以及基因的构成形式称为生物的基因型Genotype而该生物在环境中所呈现的相应性状称为该生物的表现型Phenotype在遗传过程中染色体上的基因能够直接复制给子代从而使得子代具有亲代的特征此外两条染色体之间也通过交叉 Crossover 而重组即两个染色体在某个相同的位置处被截断其前后两串基因交叉组合而形成两个新的染色体在基因复制时也会产生微小的变异Mutation从而也产生了新的染色体因此交叉和变异是产生新物种的主要途径由于自然选择在子代群体新产生的物种或染色体当中只有那些对环境适应度高的才能生存下来即适应度越高的被选择的概率也越大然后又是通过遗传和变异再自然选择一代一代不断进化因此生物遗传和进化的基本过程就是选择即复制交叉和变异遗传算法就是通过模拟生物进化的这几个基本过程而实现的①编码编码是设计遗传算法首要解决的问题在生物进化中选择交叉变异这些基本过程都是基于遗传信息的编码方式进行的即基于染色体的基因型而非表现型因此要模拟生物进化过程遗传算法必须首先对问题的可行解X决策向量进行某种编码以便借鉴生物学中染色体和基因等概念在遗传算法中将每一个决策向量X用一个染色体V来表示3其中每一个vi代表一个基因染色体的长度m不一定等于设计变量的数目n取决于染色体上基因的编码方式一般有两种编码方式二进制编码和浮点数编码如果是二进制编码每一个设计变量xi的真实值用一串二进制符号0和1按照一定的编码规则来表示每个二进制符号就代表一个基因因此染色体长度要远大于设计变量的数目这种由二进制编码构成的排列形式V就是染色体也称个体的基因型而基因型经过解码后所对应的决策向量X即可行解就是个体的表现型如果是浮点数编码每个设计变量用其取值范围内的一个浮点数表示构成染色体的一个基因vi因此个体的编码长度m也就等于决策变量的个数n由于这种编码方式使用的是决策变量的真实值所以也称真值编码方法无论哪种编码方式所有可能的染色体个体V构成问题的搜索空间种群遗传算法对最优解的搜索就是在搜索空间中搜索适应度最高的染色体后面叙述适应度的计算因此通过编码将一个问题的可行解从其解空间转换到了遗传算法能够处理的搜索空间经过个体的编码后就可以进行遗传算法的基本操作选择交叉和变异②选择复制操作选择也就是复制是在群体中选择适应度高的个体产生新群体的过程生物的进化是以集团为主体的与此相应遗传算法的运算对象是有M个个体或染色体组成的集合称为种群M也称为种群规模遗传算法在模拟自然选择时以个体的适应度Fitness高低为选择依据即适应度高的个体被遗传到下一代种群的概率较高而适应度低的个体遗传到下一代的概率则相对较低个体适应度由适应度函数计算适应度函数总是和个体表现型 ie X 的目标函数值f X 关联一般是由目标函数经过一定的变换得到一种最简单的方法就是直接使用目标函数f X 作为适应度函数4选定了适应度函数之后个体适应度也随之确定则在选择操作时个体被选中的概率5其中Fi为个体的适应度这种选择方式称为比例选择也称轮盘赌选择除此之外还有多种选择方法如随机竞争选择均匀选择无回放随机选择等不一一介绍③交叉操作所谓交叉就是以一定的概率交叉概率从群体中选择两个个体染色体按照某种方式交换其部分基因从而形成两个新的个体在遗传算法中它是产生新个体同时也是获得新的优良个体的主要方法它决定了遗传算法的全局搜索能力对于不同的编码方式交叉操作的具体方法也不相同对于浮点数编码一般使用算术交叉对于二进制编码有单点交叉和多点交叉等方式不论何种方式在交叉操作时首先应定义交叉概率Pc这个概率表明种群中参与交叉的个体数目的期望值是M 是种群规模通常交叉概率应取较大的值以便产生较多的新个体增加全局搜索力度但是Pc过大时优良个体被破坏的可能性也越大如果Pc 太小则搜索进程变慢影响算法的运行效率一般建议的取值范围是04–099④变异操作遗传算法中的变异操作就是将染色体上某些基因座上的基因以一定的变异概率Pm用其他的等位基因替代从而形成新的个体对于浮点数编码变异操作就是将变异点处的基因用该基因取值范围内的一个随机数替换对于二进制编码则是将变异点处的基因由1变成00变成1变异操作也有多种方法如均匀变异非均匀变异高斯变异等变异操作的概率Pm要比交叉操作的概率Pc小得多变异只是产生新个体的辅助手段但它是遗传算法必不可少的一个环节因为变异操作决定了算法的局部搜索能力它弥补了交叉操作无法对搜索空间的细节进行局部搜索的不足因此交叉和变异操作相互配合共同完成对搜索空间的全局和局部搜索以上简要介绍了遗传算法的基本原理和操作归纳起来基本遗传算法一般可以表示为一个8元组6式中C 个体的编码方法E 个体适应度评价函数P0 初始种群M 种群规模选择操作交叉操作变异操作是进化终止代数进化终止条件其中有4个运行参数需要预先设定M T PcPm 种群规模M一般取为20100 终止代数T一般取100500交叉概率Pc一般取04099 变异概率Pm一般取0000101最后给出遗传算法的基本步骤①选择二进制编码或浮点数编码把问题的解表示成染色体②随机产生一群染色体个体也就是初始种群③计算每一个个体的适应度值按适者生存的原则从中选择出适应度较大的染色体进行复制再通过交叉变异过程产生更适应环境的新一代染色体群即子代④重复第3步经过这样的一代一代地进化最后就会收敛到最适应环境适应度最大的一个染色体即个体上它就是问题的最优解图2给出了基本遗传算法设计流程图其中t代表当前代数T是进化终止代数图2 基本遗传算法设计流程图3 Matlab遗传算法工具箱 gatoolMatlab的遗传算法工具箱有一个精心设计的图形用户界面可以帮助用户直观方便快速地利用遗传算法求解最优化问题在Matlab命令窗口输入命令gatool可以打开遗传算法工具箱的图形用户界面如图3所示GA工具箱的参数设置步骤如下图3 遗传算法工具1 首先使用遗传算法工具箱必须输入下列信息Fitness function 适应度函数这里指的是待优化的函数也即目标函数该工具箱总是试图寻找目标函数的最小值输入适应度函数的格式为fitnessfun其中符号产生函数fitnessfun的句柄fitnessfun代表用户编写的计算适应度函数目标函数的M文件名该M文件的编写方法如下假定我们要计算Rastrigin函数的最小值7M函数文件确定这个函数必须接受一个长度为2的行向量X也即决策向量向量的长度等于变量数目行向量X的每个元素分别和变量x1和x2对应另外M文件要返回一个标量Z其值等于该函数的值下面是计算Rastrigin函数的M文件代码function Z Ras_fun XZ 20X 1 2X 2 2-10 cos 2piX 1 cos 2piX 2M文件编写保存后再在gatool工具箱界面Fitness function栏输入 Ras_funNumber of variable 变量个数目标函数中的变量数目也即适应度函数输入向量的长度在上例中它的值是22 其次设置遗传算法参数即Options设置以下只介绍部分运行参数的设置其他未提及的参数采用默认设置即可①种群参数 PopulationPopulation size 种群规模每一代中的个体数目一般是20-100之间种群规模大算法搜索更彻底可以增加算法搜索全局最优而非局部最优的概率但是耗时也更长Initial range 初始范围其值是两行的矩阵代表初始种群中个体的搜索范围实际上是决策向量X中每个变量xi的初始搜索范围矩阵的列数等于变量个数Number of variable第一行是每个变量的下限第二行是每个变量的上限如果只输入2 1的矩阵则每个变量的初始搜索范围都一样注意初始范围仅限定初始种群中个体或决策向量的范围后续各代中的个体可以不在初始范围之内初始范围不能设置太小否则造成个体之间的差异过小即种群的多样性降低不利于算法搜索到最优解②复制参数 ReproductionCrossover fraction 交叉概率一般取04099默认08③算法终止准则 Stopping Criteria提供了5种算法终止条件Generations最大的进化代数一般取100500默认是100当遗传算法运行到该参数指定的世代计算终止Time limit指明算法终止执行前的最大时间单位是秒缺省是Inf 无穷大Fitness limit 适应度限当最优适应度值小于或等于此参数值时计算终止缺省是-InfStall generation 停滞代数如果每一代的最佳适应度值在该参数指定的代数没有改善则终止计算缺省是50代Stall time 停滞时间如果每一代的最佳适应度值在该参数指定的时间间隔内没有改善则终止计算缺省是20秒3 设置绘图参数即Plots设置绘图参数Plots工作时可以从遗传算法得到图形数据当选择各种绘图参数并执行遗传算法时一个图形窗口在分离轴上显示这些图形下面介绍其中2个参数Best fitness 选择该绘图参数时将绘制每一代的最佳适应度值和进化世代数之间的关系图如图4的上图所示图中蓝色点代表每一代适应度函数的平均值黑色点代表每一代的最佳值Distance 选择此参数时绘制每一代中个体间的平均距离它反映个体之间的差异程度所以可用来衡量种群的多样性图4的下图显示的即是每一代个体间的平均距离图44 执行算法参数设置好了之后点击工具箱界面上的按钮Star 执行求解器在算法运行的同时Current generation当前代数文本框中显示当前的进化代数通过单击Pause按钮可以使计算暂停之后再点击Resume可以恢复计算当计算完成时Status and results窗格中出现如图5所示的情形图5其中包含下列信息算法终止时适应度函数的最终值即目标函数的最优值Fitness function value 0003909079476983379算法终止原因Optimization terminated imum number of generations exceeded 超出最大进化世代数最终点即目标函数的最优解[x1 x2] [-0004 -000193]两个变量的例子三实验内容1 Rastrigin函数的最小值问题函数表达式如 7 式函数图像如下图6所示它有多个局部极小值但是只有一个全局最小值Rastrigin函数的全局最小值的精确解是0出现在[x1 x2] [0 0]处图6 Rastrigin函数图像使用遗传算法工具箱近似求解Rastrigin函数的最小值首先编写计算适应度函数的M文件然后设置运行参数绘图参数Plots勾选Best fitness和Distance两项其它参数可以使用默认值执行求解器Run solver计算Rastrigin函数的最优值观察种群多样性对优化结果的影响决定遗传算法的一个重要性能是种群的多样性个体之间的距离越大则多样性越高反之则多样性越低多样性过高或过低遗传算法都可能运行不好通过实验调整Population 种群的Initial range 初始范围参数可得到种群适当的多样性取Initial range参数值[1 11]观察Rastrigin函数最小值的计算结果取Initial range参数值[1 100]观察Rastrigin函数最小值的计算结果取Initial range参数值[1 2]观察Rastrigin函数最小值的计算结果2 微带电极欧姆损耗的优化微带电极的欧姆损耗公式可由 1 式表示令设计变量[WDt] [x1 x2 x3] X变量的约束条件如下8根据 1 式和 8 式使用遗产算法工具箱优化设计电极的结构参数W 宽度 D 间距 t 厚度使得电极的欧姆损耗最小 1 式中用到的常数提示对约束条件 8 式的处理可以在编写计算适应度函数的M文件中实现方法是在M文件中引入对每个输入变量值范围的判断语句如果任一变量范围超出 8 式的限制则给该个体的适应度施加一个惩罚使得该个体被遗传到下一代的概率减小甚至为0一般可用下式对个体适应度进行调整9其中F x 是原适应度F x 是调整后的适应度P x 是罚函数为简单计本问题中我们可以给个体的适应度 com件的返回值Z 加上一个很大的数即可如正无穷Inf四思考题1 在遗传算法当中个体的变异对结果有何影响如果没有变异结果又将如何试以Rastrigin函数最小值的计算为例说明取变异概率为0即交叉概率Crossover fraction 102 遗传算法工具箱针对的是最小化函数值问题如果要利用该工具箱计算函数的最大值该如何实现。

实验六：遗传算法求解TSP问题实验2篇第一篇：遗传算法的原理与实现1. 引言旅行商问题（TSP问题）是一个典型的组合优化问题，它要求在给定一组城市和每对城市之间的距离后，找到一条路径，使得旅行商能够在所有城市中恰好访问一次并回到起点，并且总旅行距离最短。

遗传算法作为一种生物启发式算法，在解决TSP问题中具有一定的优势。

本实验将运用遗传算法求解TSP问题，以此来探讨和研究遗传算法在优化问题上的应用。

2. 遗传算法的基本原理遗传算法是模拟自然界生物进化过程的一种优化算法。

其基本原理可以概括为：选择、交叉和变异。

（1）选择：根据问题的目标函数，以适应度函数来评估个体的优劣程度，并按照适应度值进行选择，优秀的个体被保留下来用于下一代。

（2）交叉：从选出的个体中随机选择两个个体，进行基因的交换，以产生新的个体。

交叉算子的选择及实现方式会对算法效果产生很大的影响。

（3）变异：对新生成的个体进行基因的变异操作，以保证算法的搜索能够足够广泛、全面。

通过选择、交叉和变异操作，不断迭代生成新一代的个体，遗传算法能够逐步优化解，并最终找到问题的全局最优解。

3. 实验设计与实施（1）问题定义：给定一组城市和每对城市之间的距离数据，要求找到一条路径，访问所有城市一次并回到起点，使得旅行距离最短。

（2）数据集准备：选择适当规模的城市数据集，包括城市坐标和每对城市之间的距离，用于验证遗传算法的性能。

（3）遗传算法的实现：根据遗传算法的基本原理，设计相应的选择、交叉和变异操作，确定适应度函数的定义，以及选择和优化参数的设置。

（4）实验流程：a. 初始化种群：随机生成初始种群，每个个体表示一种解（路径）。

b. 计算适应度：根据适应度函数，计算每个个体的适应度值。

c. 选择操作：根据适应度值选择一定数量的个体，作为下一代的父代。

d. 交叉操作：对父代进行交叉操作，生成新的个体。

e. 变异操作：对新生成的个体进行变异操作，以增加搜索的多样性。

第28卷 第8期2007年8月半 导 体 学 报CH IN ESE JO U R NA L O F SEM ICO ND U CT O R SV ol.28 N o.8Aug.,2007*模拟集成电路国家重点实验室基金资助项目(批准号:9140C 09040206DZ061221) 通信作者.Em ail:youhailong@126.co m 2006 12 19收到,2007 03 26定稿2007中国电子学会基于遗传算法的Kriging 元模型及其在模拟集成电路优化设计中的应用*游海龙贾新章 王少熙(西安电子科技大学微电子学院宽禁带半导体材料与器件教育部重点实验室,西安 710071)摘要:提出了建立电路K rig ing 元模型,并与遗传算法相结合确定电路参数,优化电路的方法.相对传统多项式回归模型,K riging 模型更适合电路仿真的实验类型;利用遗传算法,解决了基于Kr ig ing 元模型电路系统的全局优化问题.最后将该方法应用于带隙基准电路设计,取得令人满意的结果.关键词:模拟集成电路;Kr ig ing 元模型;最优化;遗传算法EEAC C:2570中图分类号:T P302 文献标识码:A 文章编号:0253 4177(2007)08 1325 051 引言现代集成电路的开发周期要求模拟集成电路的优化设计方法更加高效,基于传统EDA 工具的电路参数优化设置,存在迭代次数多、不收敛等问题;另外,由于传统数值优化算法容易局部收敛,使得电路优化设计结果并不是设计空间内的全局最优解[1].将电路性能指标的元模型与数值优化方法结合对电路进行优化设计已经成为解决上述问题的一种可行方法[2,3].建立电路性能指标与设计参数直接、简单的函数关系,即元模型(Metam odel,近似模型),利用简单、直接的函数关系模型代替电学与物理原模型,将问题简化,减少系统仿真成本,能够大大提高电路优化设计效率.选择合适的优化算法,能够容易地获得电路在设计空间内的全局最优解.将实验设计(design o f experime nt,D OE)与仿真实验相结合是构造电路元模型的主要途径[4].构造元模型的传统方法主要是多项式回归分析与部分因子实验相结合.这一类传统方法一般用于实际、非仿真系统,如农业、工程等.该方法是建立在重复实验、随机组合以及区组化原则基础上的.而电路仿真实验不同于真实的物理、化学实验,在给定的条件下,输出值确定,不存在物理实验的随机误差,并不需要考虑实验的重复性、随机以及区组化问题,如图1所示.因此传统多项式回归模型以及对应的实验设计类型并不是最好的选择[5,6].特别是多项式模型对于参数较多的情况,如9个,由于模型形式复杂,参数估计需要较大的实验规模,并且很难有效近似原有电路.本文探讨一种Krig ing 元模型与遗传算法相结合的电路优化设计方法,以解决利用传统EDA 工具优化电路出现的效率低、不收敛等问题.相对传统的多项式模型以及实验设计方法,该方法能够利用较少的实验次数,建立电路系统更有效的近似模型,利用遗传算法得到模型全局最优解,优化电路性能,从而确定参数大小.最后以带隙基准电压源的优化设计为例,应用该方法实现了电路性能指标的优化.2 Kriging 元模型2.1 电路仿真实验的特点电路仿真实验,是一种无误差的计算机实验,因此,重复性实验对它没有意义.对于这种无误差、无重复电路仿真实验,在模型上与真实的物理实验有很大的区别,如图1所示.对于电路仿真实验可以通过回归方法得到预测趋势线,但是在无误差存在条件下,该模型并没有明确的实际意义.因此常采用一种空间统计方法,如Krig ing 模型来分析仿真实验数据.Krig ing 模型是一种估计方差最小的无偏估计模型.该方法最早由南非地质学者Krig e 于1951年提出,在被引入仿真实验领域之前主要广泛应用于地质界,用来确定矿产储量分布.它能够提供一种精确的插值,即对于样本内输入条件下,模型预测输出值等于仿真值.与多项式模型相比,它能够提供更好半 导 体 学 报第28卷图1 回归模型(a)与Kriging模型(b)的区别Fig.1 Difference betw een reg ression model(a)and Kr ig ing mo del(b)的全局预测.对于给定输入条件、输出值确定的仿真实验,Krig ing更具优势,因此常常应用于计算机辅助设计领域[4,5].2 2 Kriging模型基本理论Kriging模型假设系统的响应值与自变量之间的实际关系可以表示成如下的形式f(x)=g(x)+z(x)(1)其中 g(x)是确定性部分,称为确定性漂移,一般用多项式表示;z(x)称为涨落,它具有如下的统计特性:E[z(x)]=0V ar[z(x)]= 2E[z(x i),z(x j)]= 2R( ,x i,x j)(2)式中 R( ,x i,x j)是以 为参数的相关函数,R( , x i,x j)中常用的核函数为高斯函数:r(d k)=exp(- k d2k)(3)其中 d k是表征待测点与样本点之间距离关系的量; k是核函数在样本点第k方向的常数参量,各个方向 k的值可以相同,也可以不同,对应各向同性和各向异性问题.此处取d k=|x k i-x k j|,(j=i, ,m;i=1, ,n)其中x k i,x k j为样本点i,j在k方向的向量.经过推导,模型的预测值为:f(x)=f(x)T*+r(x)T!*(4)该式就是用于预测系统输出的Kr iging模型的表达式.对于给定的样本点,*和!*的值都可以通过计算确定,因此构造Kriging模型时只需要确定f(x)和r(x).其中f(x)为回归多项式,它由训练模型的样本量而定,通常为一阶或二阶多项式;而当r(x)选择为高斯函数时,由相关模型参数 确定.因此,构造Kriging模型时需要确定模型参数包括f(x)、核函数r(x)形式以及参数 ,详细推导过程可参阅文献[5,6].2.3 遗传算法与Kriging模型结合的电路优化设计Krig ing模型是一种基于黑匣(black box)的插值模型,不具有明确的显函数形式,模型的信息很少.不同的系统,Kriging模型可能是非线性、多形态以及不连续的.用于工程优化设计的传统数值优化方法包括最快下降法、共轭梯度法、二次规划、模式搜索法等.这些方法具有效率高等优点,但是它们需要目标函数的梯度、可导等信息,同时具有对于起始点的选取非常敏感,很有可能收敛于局部最优点等缺点.利用遗传算法(GA)进行多参数优化时,GA 的搜索是从初始种群开始,而不是从单个解开始,避免了对起始点过于依赖而造成优化结果的局部化;另外,不需要求导或其他辅助知识,而只需要影响搜索方向的目标函数和响应的适值函数[7].基于遗传算法容易获得目标函数的全局最优解.因此,为了解决基于Krig ing模型的电路优化问题,本文采用遗传算法电路进行优化设计,确定电路参数的设置.本文将遗传算法与Krig ing模型结合用于电路优化与设计的流程如下:(1)建立电路参数指标与元件的Kriging元模型;(2)建立电路优化的评价函数,将多目标问题转换为单目标;(3)依据评价函数,建立遗传算法进化目标!!!适值函数(fitness function);(4)在元件参数变化空间,产生初始种群;(5)将种群代入Kriging模型构成的适值函数,计算与评估适值函数,(6)根据评估结果,选取父种群,交差,变异,生成下一代;(7)判断适值函数是否收敛,如不收敛,则返回(5);如果收敛,退出,输出优化结果.通过该方法,解决了基于Kriging模型的电路全局优化,反过来在利用遗传算法优化电路中采用Krig ing模型代替电路仿真,节省了遗传算法迭代和进化成本,使效率得到很大提高.3 应用实例!!!一种带隙基准电压源优化设计与参数设置本文讨论的带隙基准电压源核心电路原理图如1326第8期游海龙等: 基于遗传算法的K r ig ing元模型及其在模拟集成电路优化设计中的应用图2 一种带隙基准电压源核心电路F ig.2 M ain circuit o f the band g ap v oltage r eference图2所示.该电路目标就是在电路运行环境变化时能够提供一个稳定的电压.衡量带隙基准电路有两个重要指标,即电压抑制比(PSRR,db)以及温度系数(T C,ppm/∀),这里期望通过电路元件参数设置,使电路具有最大的PSRR与最小的TC[8].根据电路优化要求,考虑如下电路设计参数的设置:包括4个电阻R1,R2,R3,R4,分别表示为电路优化中的变量v1,v2,v3,v4;而8个MOS管的长宽比:M1,M2,M3,M4,M5,M6,M7,M8,分别表示为v5, ,v12,电路优化的参数变化范围如表1所示.因此电路优化设计就是通过实验设计建立PSRR,TC的Kriging模型,基于模型寻找合适v参数设置,对电路进行多目标优化.3.1 目标函数与实验变量根据电路优化设计要求,将PSRR,TC作为目标函数,而v作为实验变量.通过电路分析可知,v2 =v3,v8=v9,v10=v11.因此实际上需要建立一个9输入、2输出的Kriging模型.表1 电路参数变化范围及实验变量变化范围优化设计结果T able1 Range o f par ameters and r esults o f optimization 实验变量变化范围优化设计结果1v1/k∀240,3603212v2=v3/k∀300~4503953v4/k∀100~1501444v50.8~1.2 1.05v60.8~1.2 1.06v70.8~1.2 1.17v8=v910~1511.08v10=v110.4~0.60.49v120.4~0.60.63.2 拉丁超立方体抽样与数据采集由经验发现传统的实验设计抽样,往往存在堆积点的问题,所得模型也不能代表整个参数变化区域[7].在西方,拉丁超立方抽样(Latin hypercube sam pling,LH S)广泛应用于仿真实验中.它是由M cKa y等人于1979年专门为仿真实验提出的一种实验设计类型.它使输入组合相对均匀地填满整个实验区间,因此被称作充满空间设计.在抽取的样本点中,每个实验变量水平只使用一次,如果一个参数几乎不影响响应指标,而被从实验变量设置中删除,实验设计仍然是没有任何点是重合的拉丁超立方设计.LHS具有的充满空间特性,使它成为构造Krig ing模型最为主要的设计类型[6],关于LH S的详细讨论可参阅文献[9].由于LHS的实验规模具有相当大的弹性,选择多少实验次数并没有理论指导,根据经验一般选取实验变量个数3,4倍实验次数.这里从建立Krig ing 模型需要出发,由于Krig ing模型中的f(x),一般用多项式表示,需要足够的实验次数进行参数估计.同时参数 的优化选择对实验也提出要求.因此,基于模型需要采用实验变量为9,实验次数为52的拉丁超立方实验.传统响应曲面实验设计已经很难提供有效方案,基于小复合Draper/Lin方法的响应曲面方法最小实验次数也需要63个[10].建立抽样方案后,基于H y nix的0 50#m CM OS工艺模型,通过H spice对电路进行仿真实验,采集数据.3.3 电路的Kriging元模型根据(4)式,利用电路目标参数的Krig ing模型进行响应预测时,需要确定f(x)和核函数r(x)以及参数 .这里采用1阶多项式来确定f(x),核函数采用高斯函数, 参数初始值假设为各向同性,大小为1.Krig ing模型是一种精确插值模型,即在样本点上预测值与仿真实验值相等.因此,需要额外数据来验证模型.为了反映模型在整个实验空间的预测精度,通过另一种充满空间的设计方法均匀实验设计构造了20组实验组合来验证模型.采用判定系数R2来衡量模型预测值与仿真真实值偏差,R2越大越好,1表示预测值与实际值基本吻合[10].本模型的PSRR和T C的判定系数R2分别为96 72%和88 68%.图3是模型预测值与电路仿真结果的对比.可以看出,Kr ig ing模型预测结果能较好地反映真实的电路输出结果的趋势,与仿真实验结果基本吻合.3.4 电路的优化与参数设置该电路系统的优化为一个多目标、多维、非线1327半 导 体 学 报第28卷图3 Krigin g模型预测值与Hs pice仿真值对比 (a)PSRR;(b)TCFig.3 Compariso n of K r iging model and H spice simu latio n (a)P SR R;(b)T C性、有界数值优化问题.多目标优化问题的基本方法是评价函数方法.这里将传统的评价函数方法中的理想点法和线性加权法相结合构造评价函数,将多目标问题转化为单目标问题.构造的评价函数为:∃(f^(x))=%1(f^PSR R(x)-f*PS RR)2+%2(f^TC(x)-f*TC)2(5)其中 f*PSRR,f*T C为单个目标函数的最优值,即为值域中的一个理想点;%1,%2为加权系数.该方法构造的评价函数不仅将多目标优化转化为单目标优化问题,同时通过加权函数解决了不同函数模型预测精度的差异对评价函数的影响.需要强调的是,f^PSRR, f^TC是电路性能指标PSRR以及TC的Kr ig ing元模型的预测结果,而不是电路数值模型的仿真结果,即在优化过程中利用Krig ing元模型预测来代替电路实际仿真,这是本文采用Kriging元模型的电路优化设计方法与传统基于仿真软件的电路优化设计的区别.首先通过遗传算法确定PSRR以及T C的单目标最优值.基于简单遗传算法[8],分别求得PSRR最图4 遗传算法寻优跟踪图F ig.4 Diag ram of g enet ic alg or ithms大值为84 11,以及T C最小值为7 06.通过图3的拟合情况,PSRR与T C相对偏差数量级关系,确定%1=1,%2=0 05.然后构造多目标评价函数的适值函数,遗传算法主要参数确定如下:初始种群为40,交叉概率为0 6,变异概率为0 08.优化结果如图4所示,经过20次左右的迭代,求得目标函数∃(f^ (x))最小值为4 775,同时获得优化条件,优化后的参数设置如表1所示.电路性能指标PSRR,TC优化的模型预测结果与H spice仿真结果如表2所示.从表2以及图3可见,TC的Kriging模型在极值点附近预测能力相对较差,这与Kr ig ing模型是一种空间插值模型有关.极值点很可能出现于空间断点,也就是说在极值点附近,抽样量不够,造成模型在极值点附近预测精度不够,这是由于拉丁超立方抽样方法是一种均匀抽样引起的.由于Kriging模型能够提供趋势预测,而不影响对极值点寻找.4 结语提出了基于Krig ing元模型(近似模型)与遗传算法结合的模拟集成电路优化设计与参数生成方法.该方法中,Kriging模型相对传统多项式模型更适合计算机仿真实验特点,所需的仿真成本较低,同时具有较高的精度,基于遗传算法的优化解决了Krig ing这类插值模型的优化问题.所提出的方法应用于一种带隙基准电压源电路优化设计,通过理想点与线性加权法相结合构造电路的评价函数,实现了电路的多目标优化,获得了令人满意的结果.表2 在电路预测优化点上模型预测值与实际输出值比较T able2 Co mpar ison of calculated and simulat ed results模型预测值Hs pice仿真值PSRR/dB79.7079.941328第8期游海龙等: 基于遗传算法的K r ig ing元模型及其在模拟集成电路优化设计中的应用参考文献[1] Biirm en A,Puhan J,Burm en T T.Robus t design and optimization of operating amplifiers.IEEE Pr oceedings of International C on feren ce on Indu strial T ools,2003:745[2] Carr oll J,Chang K.Statistical com puter aided des ign for micr ow ave circuits.IEEE T ran s M icr ow T heory Tech,1996,44(1):24[3] Gao Xuelian,S hi Yin.Generation of polynomial res ponse s urface m odels for s izing of an an alog IC.Chinese Journal ofS emicon ductors,2005,26(11):2241(in Chinese)[高雪莲,石寅.利用正多项式响应曲面模型实现模拟电路参数自动生成.半导体学报,2005,26(11):2241][4] You H ailong,Jia Xinz han g,Zhang Xiaob o,et al.Study onthe m ethod of th e design of experiment integrated w ith s imulation for constructing th e integrated circuit metamodel.ActaElectronic S inica,2006,34(6):1159(in Chinese)[游海龙,贾新章,张小波,等.试验设计与仿真相结合构造集成电路元模型的方法研究.电子学报,2006,34(6):1159][5] Sim pson T W,M anery T M,Korte J J,et paris on ofrespons e surface an d Kriging models for m ultidisciplinary d esign optimiz ation.7th AIAA/U SAF/NASA/ISS OM O symposium on M ultidisciplinary Analysis&Optimiz ation,1998:381[6] Kleijnen J P C.An overview of th e design an analysis of simulation experiments for s ens itivity an alys is.European J ou rnalof Operational Res earch,2005,164(2):287[7] Xuan G N,Ch eng R W,Yu Y J.Genetic algorithm s and engineering optimiz ation.Beijing:T singhua U nivers ity Press,2003(in C hinese)[玄光男,程润伟,于韵杰.遗传算法与工程优化.北京:清华大学出版社,2003][8] Razavi B.Design of analog CM OS integrated circuits.T rans lated b y Chen Guican,Chen g Jun,Zhang Ruizhi,et al.Xi#an:Xi#an Jiaotong U nivers ity Press,2003(in Chinese)[拉扎维B.模拟CM OS集成电路设计.陈贵灿,程军,张瑞智,等译.西安:西安交通大学出版社,2003][9] Fang Kaitai.Uniform design:theory,meth od and application s.Application of S tatistics and M anagement,2004,23(3):69(in C hinese)[方开泰.试验均匀试验设计的理论、方法和应用:历史回顾.数理统计与管理,2004,23(3):69][10] M ontgomery Douglas C.Design and analys is of experiments.New York:Wiley,1997Kriging Metamodel Based on Genetic Algorithms and Its Applicationin Analog IC Optimization*You H ailong ,Jia Xinzhang,and Wang Shao xi(K ey L aboratory of th e M inistr y of Ed ucation f or W ide B an d Gap S emicondu ctor M aterials and De v ice s,S ch ool of M icr oelectronics,X id ian Univ ersity,X i#an 710071,China)Abstract:W e pr esent a m ethod o f co nstr ucting the K riging met amo de l o f cir cuits a nd c ombining it w ith genetic a lg or ithms (G A)to o pt imize a circuit and deter mine the par ameter pa red w ith the polyno mial re gre ssion model,the K riging m odel is m or e suitable t o the cir cuit simulatio n ex per iments.U sing G A,the pro blem o f the circ uit g lo ba l optimiza tio n is solve d ba sed on the Kr ig ing me tamo de l.T he me thod is applied to the o ptim izat io n design of the band gap vo lta ge re fer ence,a nd the result show s tha t the presented m etho d is ef fective.Key words:analo g IC;K r ig ing m etamo del;o ptim ization;g enetic alg or ithm sEEAC C:2570Article ID:0253 4177(2007)08 1325 05*Project supp orted by the Found ation o f National Laboratory of An alog In tegrated Circuits(No.9140C09040205DZ061221)C orresponding author.E mail:youh ailong@Received19December2006,revised man us cript receiv ed26M ar ch2007 2007Ch inese In stitute of Electr onics1329。

遗传算法实验报告遗传算法实验报告引言：遗传算法是一种模拟生物进化过程的优化算法，通过模拟自然选择、遗传变异和交叉等操作，逐步优化问题的解。

本实验旨在探究遗传算法在解决优化问题中的应用，并通过实验验证其效果。

一、实验背景遗传算法最早由美国科学家约翰·霍兰德于20世纪60年代提出，其灵感来源于达尔文的进化论。

遗传算法通过基因编码、适应度评估、选择、交叉和变异等操作，模拟了进化过程中的遗传和变异，从而找到问题的最优解。

二、实验目的本实验旨在通过遗传算法解决一个经典的优化问题，验证其在解决实际问题中的有效性。

同时，对遗传算法的参数设置和操作过程进行调整和优化，以提高算法的性能。

三、实验步骤1. 问题定义：选择一个经典的优化问题，例如旅行商问题（TSP）或背包问题。

2. 解空间建模：将问题的解表示为染色体，设计基因编码方式。

3. 适应度函数定义：根据问题的特点，设计一个能够评估染色体解的适应度函数。

4. 初始化种群：随机生成一组初始染色体，作为种群。

5. 选择操作：根据适应度函数，选择一部分较优秀的染色体作为父代。

6. 交叉操作：通过交叉操作，生成新的子代染色体。

7. 变异操作：对子代染色体进行变异操作，引入新的基因变异。

8. 适应度评估：计算新的子代染色体的适应度。

9. 父代替换：根据适应度函数，选择一部分较优秀的子代染色体替换掉父代染色体。

10. 终止条件判断：判断是否满足终止条件，若满足则结束算法，否则返回步骤5。

11. 输出结果：输出最优解及其适应度值。

四、实验结果与分析通过实验，我们得到了一组优化问题的最优解，并计算出其适应度值。

通过观察实验结果，我们可以发现遗传算法在解决优化问题中的有效性。

同时，我们还可以通过调整遗传算法的参数和操作过程，进一步提高算法的性能。

五、实验总结通过本次实验，我们深入了解了遗传算法的原理和应用。

遗传算法作为一种优化算法，具有较强的适应性和鲁棒性，在解决实际问题中具有广泛的应用前景。

基于遗传算法的路径优化方法研究及其实现引言：路径优化是一个常见的优化问题，它在很多领域都有广泛的应用，比如物流配送、车辆路径规划、网络路由等。

而遗传算法是一种模拟生物进化过程的启发式优化算法，通过模拟自然选择和遗传机制来搜索最优解。

本文将围绕基于遗传算法的路径优化方法展开研究，并提出一种实现方案。

一、遗传算法基础概念1.1 遗传算法原理遗传算法源于对达尔文生物进化理论的模拟，通过模拟生物的遗传、变异、适应性选择等过程来优化问题的解。

1.2 遗传算法流程遗传算法的基本流程包括初始化种群、选择操作、交叉操作、变异操作和终止条件判断等步骤。

1.3 遗传算法参数遗传算法的性能受到参数选择的影响，其中包括种群大小、交叉概率、变异概率等。

二、路径优化问题描述2.1 问题定义路径优化问题是指在给定的图中，找到一条路径使得满足一定的约束条件的情况下，路径的总长度最短。

2.2 适应度函数为了能够将路径优化问题转化为遗传算法的优化问题，我们需要定义一个适应度函数来衡量每个个体（路径）的优劣。

三、基于遗传算法的路径优化方法3.1 编码设计在遗传算法中，需要将问题的解（路径）进行编码。

常见的编码方式包括二进制编码、浮点数编码和排列编码等。

根据问题的特点选择合适的编码方式。

3.2 初始化种群在遗传算法中，初始化种群的质量直接影响到算法的性能。

一般情况下，可以根据问题的约束条件和启发式方法来生成初始种群。

3.3 选择操作选择操作是遗传算法中最为重要的一步，目的是根据适应度函数的值选择较优的个体。

常见的选择方法包括轮盘赌选择、锦标赛选择等。

3.4 交叉操作交叉操作是遗传算法的特点之一，通过交叉两个个体的染色体来生成新的个体。

在路径优化问题中，可以采用部分映射交叉、顺序交叉等方式进行操作。

3.5 变异操作变异操作是为了增加种群的多样性，防止算法陷入局部最优解。

在路径优化问题中，可以通过交换、插入、反转等方式进行变异操作。

3.6 终止条件判断终止条件判断是遗传算法运行的结束条件。

基于遗传算法的流量控制系统设计与实现一、概述随着网络负载的增加，流量控制逐渐成为了一项重要的技术。

现有的流量控制系统，一般依赖于手动设置阈值等参数来调整系统性能。

但由于网络环境和负载变化的不确定性，这种方式难以保证控制效果的一致性。

因此，本文提出了一种基于遗传算法的流量控制系统的设计与实现，通过自适应调整参数，来优化系统性能和提高控制效果。

二、设计原理遗传算法是一种通过模拟生物演化过程，不断优化求解的优化算法。

它模拟了自然选择和遗传机制，逐步筛选出更优的解决方案。

在流量控制系统中，我们可以把具体的参数，如阈值、检测周期、队列长度等看作是染色体上的基因。

通过对这些基因进行操作，来不断优化系统性能。

三、系统模块为了将遗传算法应用于流量控制系统，我们设计了以下几个模块：1. 数据采集模块：监测网络流量的大小和变化趋势，把采集到的数据进行分析。

2. 参数传递模块：将数据传递到遗传算法模块中，让算法来决策参数的变化和调整。

3. 遗传算法模块：根据数据的变化，不断优化流量控制系统的参数，寻找到最佳的解决方案。

4. 控制模块：根据算法得出的结果，来进行队列排序、流量控制等操作，以达到优化系统性能的目的。

四、遗传算法流程1. 初始化种群：对于每个可能的参数组合，都随机生成一组初始数据。

2. 适应度函数计算：通过数据采集模块采集数据，计算每个样本的适应度值。

3. 选择操作：根据轮盘赌方法，按照适应度大小来选择出下一代种群，从而让优秀的个体有更多的机会遗传到下一代。

4. 交叉操作：使用单点交叉算法，让两个个体染色体交换一部分，产生新的个体。

5. 变异操作：以一定的概率来改变某个个体的单个基因值，从而增加样本的多样性。

6. 新一代种群生成：通过选择、交叉、变异操作，生成新一代种群。

7. 判断停止条件：如果达到了停止条件，就输出当前最优解；否则，重新进入第二步，继续迭代。

五、实验结果由于网络环境和负载变化的不确定性，我们在测试中采集了多组数据，并进行了统计。

《改进遗传算法及其在TSP问题中的应用》篇一一、引言遗传算法是一种基于自然进化理论的搜索启发式算法，广泛应用于组合优化问题。

旅行商问题（Traveling Salesman Problem，简称TSP）作为典型的组合优化问题之一，吸引了众多研究者的关注。

本文旨在探讨改进遗传算法及其在TSP问题中的应用，通过分析现有遗传算法的优缺点，提出一种改进的遗传算法，并在TSP问题中验证其有效性和优越性。

二、遗传算法概述遗传算法模拟自然进化过程，通过种群个体的选择、交叉和变异等操作，实现全局搜索和优化。

其基本步骤包括初始化种群、计算个体适应度、选择操作、交叉操作和变异操作等。

三、现有遗传算法在TSP问题中的局限性在TSP问题中，遗传算法面临着多个挑战。

一方面，搜索空间随城市数量急剧增长；另一方面，由于问题的复杂性，传统遗传算法容易陷入局部最优解。

此外，传统遗传算法在处理城市间的距离计算和路径优化时，往往无法有效平衡全局搜索和局部搜索。

四、改进的遗传算法设计针对上述问题，本文提出一种改进的遗传算法。

该算法主要从以下几个方面进行优化：1. 初始化种群策略：采用更精细的编码方式，使个体更好地表示路径。

同时，引入随机性因素，扩大搜索空间。

2. 适应度函数设计：针对TSP问题，设计更为合理的适应度函数，将城市间的距离和路径长度综合考虑，提高搜索效率。

3. 选择操作：采用多种选择策略相结合的方式，如轮盘赌选择、锦标赛选择等，提高种群的多样性。

4. 交叉操作：引入多种交叉方式，如单点交叉、多点交叉和均匀交叉等，提高算法的搜索能力。

5. 变异操作：在变异过程中引入扰动机制，增加种群的活跃度，避免陷入局部最优解。

五、实验设计与结果分析为了验证改进的遗传算法在TSP问题中的有效性，本文设计了多组实验。

实验中，我们采用了不同规模的TSP问题实例（如城市数量从几十到几百不等），并与其他遗传算法进行比较。

实验结果表明，改进的遗传算法在TSP问题上具有更好的性能。