第七章 遗传算法应用举例

基本遗传算法及应用举例遗传算法(Genetic Algorithms)是一种借鉴生物界自然选择和自然遗传机制的随机、高度并行、自适应搜索算法。

遗传算法是多学科相互结合与渗透的产物。

目前它已发展成一种自组织、自适应的多学科技术。

针对各种不同类型的问题，借鉴自然界中生物遗传与进化的机理，学者们设计了不同的编码方法来表示问题的可行解，开发出了许多不同环境下的生物遗传特征。

这样由不同的编码方法和不同的遗传操作方法就构成了各种不同的遗传算法。

但这些遗传算法有共同的特点，即通过对生物的遗传和进化过程中的选择、交叉、变异机理的模仿来完成对最优解的自适应搜索过程。

基于此共同点，人们总结出了最基本的遗传算法——基本遗传算法。

基本遗传算法只使用选择、交叉、变异三种基本遗传操作。

遗传操作的过程也比较简单、容易理解。

同时，基本遗传算法也是其他一些遗传算法的基础与雏形。

1．1．1 编码方法用遗传算法求解问题时，不是对所求解问题的实际决策变量直接进行操作，而是对表示可行解的个体编码的操作，不断搜索出适应度较高的个体，并在群体中增加其数量，最终寻找到问题的最优解或近似最优解。

因此，必须建立问题的可行解的实际表示和遗传算法的染色体位串结构之间的联系。

在遗传算法中，把一个问题的可行解从其解空间转换到遗传算法所能处理的搜索空间的转换方法称之为编码。

反之，个体从搜索空间的基因型变换到解空间的表现型的方法称之为解码方法。

编码是应用遗传算法是需要解决的首要问题，也是一个关键步骤。

迄今为止人们已经设计出了许多种不同的编码方法。

基本遗传算法使用的是二进制符号0和1所组成的二进制符号集｛0，1｝，也就是说，把问题空间的参数表示为基于字符集｛0，1｝构成的染色体位串。

每个个体的染色体中所包含的数字的个数L 称为染色体的长度或称为符号串的长度。

一般染色体的长度L 为一固定的数，如X=10011100100011010100表示一个个体，该个体的染色体长度L=20。

1.比较分析()()210sin +=x x x f π，[]2,1-∈x2. Schaffer 函数 F6： ()()[]222212221221001.00.15.0sin5.0,xxx x x x f ++-+-=，100100≤≤-i x ，2,1=i该函数是由J.D.Schaffer 等提出的,它有无限个局部极大点，只有一个全局最大值点()10,0=f，此函数最大值峰周围有一圈脊，它们的取值均为0.990283，由于它的强烈振荡图6-8 Schaffer 函数 F6图像Fig.6-8 image of Schaffer function F6性质以及它的全局最优点被次优点所包围的特性使得一般算法很难找到它的全局最优点,因此很容易停滞在局部极大点。

本文采用具有变动搜索空间能力的子空间更新遗传算法有效地解决此问题。

3. Schaffer 函数 F2:()()[]22221222122101.00.15.0sin5.0,xxx x x x f ++-++=,100100≤≤-i x ,2,1=i图6-1 Schaffer 函数 F2图像 Fig.6-1 image of Schaffer function F2虽然该函数在其定义域内只有一个全局最小值点()00,0=f 。

但由于变量的取值范围大,采用传统的直接搜索法求解时,因搜索空间太大而无法求得全局最优解,采用 SGA 搜索时,由于其局部搜索能力差,因而需要设置相当大的种群规模,需耗费巨大的计算量以得到全局最优解。

如何有效地求解这类搜索空间巨大的全局优化问题一直是人们关注的一个焦点。

本文采用加强局部搜索能力的子空间更新遗传算法有效地解决此问题。

4. Needle-in-a-haystack 函数：（李敏强，2002） ()()()22222205.00.3,y x y x y x f ++⎪⎪⎭⎫ ⎝⎛++=，12.512.5≤≤-ix，2,1=i图6-15 Needle-in-a-haystack 函数图像Fig.6-15 image of Needle-in-a-haystack function此函数有4个局部极值点函数值均为2748.78，只有一个全局最大值()36000,0=f ，极值点跨度较大，该函数将形成不同严重程度的GA 欺骗问题，当模式欺骗性将搜索过程引向欺骗引子，SGA 只能在局部极值点邻域内搜索，最终收敛于局部极值点（4个局部极值点的随机选择），当遗传算子克服了模式欺骗之后，则将群体搜索方向扭转到全局最优解所在的邻域，最终收敛于全局最优解。

遗传算法的详解及应用遗传算法（Genetic Algorithm，GA）是一种模拟自然选择和遗传过程的算法。

在人工智能和优化问题中得到了广泛的应用。

本文将详细介绍遗传算法的基本原理和优化过程，并探讨它在实际应用中的价值和局限性。

一、遗传算法的基本原理遗传算法的基本原理是通过模拟生物进化的过程来寻找一个问题的最优解。

在遗传算法中，优秀的解决方案（也称为个体，Individual）在进化中拥有更高的生存几率，而劣质的解决方案则很快被淘汰。

在遗传算法的过程中，每个个体由若干个基因组成，每个基因代表某种特定的问题参数或者状态。

通过遗传算法，我们可以找到问题最优的解或者其中一个较优解。

遗传算法的基本流程如下：1. 初始化群体（Population）：首先，我们需要随机生成一组初始解作为群体的个体。

这些个体被称为染色体（chromosome），每一个染色体都由一些基因（gene）组成。

所以我们可以认为群体是由很多染色体组成的。

2. 选择操作（Selection）：选择运算是指从群体中选出一些个体，用来繁殖后代。

其目的是让优秀的个体留下更多的后代，提高下一代的平均适应度。

在选择操作中，我们通常采用轮盘赌选择（Roulette Wheel Selection）法、锦标赛（Tournament）法、排名选择（Ranking Selection）法等方法。

3. 交叉操作（Crossover）：交叉运算是指随机地从两个个体中选出一些基因交换，生成新的染色体。

例如，我们可以将染色体A和B中的第三个基因以后的基因交换，从而产生两个新的染色体。

4. 变异操作（Mutation）：变异运算是指随机改变染色体中的个别基因，以增加多样性。

例如，我们随机将染色体A的第三个基因改变，从而产生一个新的染色体A'。

5. 适应度评估（Fitness Evaluation）：适应度评估是指给每一个个体一个适应度分数，该分数是问题的目标函数或者优化函数。

遗传算法简单案例那咱们就来个超级简单又有趣的遗传算法案例，就说培育超级英雄花朵吧！一、问题设定。

想象一下，我们要培育一种超级英雄花朵，这种花朵有三个特性：花瓣颜色（可以是红色、蓝色或者紫色）、花朵大小（小、中、大）、花香程度（淡香、浓香、超香）。

这就像是花朵的基因一样，每种特性就是一个基因片段。

二、初始种群。

我们先随便搞出一些花朵个体来作为初始种群。

比如说：花朵1：花瓣颜色是红色，花朵大小是小的，花香程度是淡香。

花朵2：花瓣颜色是蓝色，花朵大小是中的，花香程度是浓香。

花朵3：花瓣颜色是紫色，花朵大小是大的，花香程度是超香。

花朵4：花瓣颜色是红色，花朵大小是中的，花香程度是淡香。

这就好比是最初的一群小生物，各有各的特点。

三、适应度评估。

那怎么知道哪种花朵更接近我们理想中的超级英雄花朵呢？这就需要适应度评估啦。

咱们设定一下，我们理想的超级英雄花朵是花瓣颜色为紫色（因为超级神秘）、花朵大小是大的（看起来霸气）、花香程度是超香（迷人得很）。

然后我们给每个花朵打个分，就看它离这个理想状态有多近。

比如说花朵3就比较接近理想状态，它花瓣颜色对了，花朵大小对了，花香程度也对了，那它的适应度就比较高。

花朵1呢，可能适应度就比较低，因为只有花香程度这一点比较符合，花瓣颜色和花朵大小都不太理想。

四、选择操作。

根据适应度来选择哪些花朵可以留下后代。

就像是一场选美比赛，但是是按照我们的超级英雄花朵标准来选的。

适应度高的花朵就有更多机会被选中，比如说花朵3就可能被选中两次，因为它很接近理想状态。

而花朵1可能就比较难被选中。

五、交叉操作。

被选中的花朵就可以繁殖啦。

咱们就做个简单的交叉操作，就像爸爸妈妈把自己的基因传给孩子一样。

比如说花朵3（紫色、大、超香）和花朵4（红色、中、淡香）繁殖后代。

那可能花瓣颜色就从花朵3取，花朵大小从花朵4取，花香程度再从花朵3取，这样就得到了一个新的花朵：花瓣颜色是紫色，花朵大小是中的，花香程度是超香。

遗传算法在实际中的应用
遗传算法是一种通过模拟生物进化过程求解优化问题的算法。

它是一种全局优化方法，适用于解决各种复杂的问题。

在实际应用中，遗传算法已被广泛应用于多个领域，如工程、金融、生物、物流等。

在工程领域，遗传算法可以用于设计优化、参数优化、生产优化等方面。

例如，可以通过遗传算法来优化机械结构的设计，使其在结构强度、重量等方面得到最佳的平衡。

在车辆制造领域，遗传算法可以优化车辆的性能、减少排放等问题。

在金融领域，遗传算法可以用于优化投资组合、预测股市趋势等方面。

例如，可以通过遗传算法来构建最优的投资组合，以实现最大的收益。

在生物领域，遗传算法可以用于解决分子结构预测、基因序列分析等问题。

例如，可以通过遗传算法来预测蛋白质的三维结构，帮助寻找新的药物设计。

在物流领域，遗传算法可以用于优化货物运输路线、降低运输成本等方面。

例如，可以通过遗传算法来计算最短的货运路线，以实现最大的物流效益。

总之，遗传算法在实际应用中已被证明是一种有效的优化算法，可以在各个领域中解决复杂的优化问题。

- 1 -。

遗传算法的应用
遗传算法是一种模拟自然选择和遗传机制的优化算法，可
以在搜索和优化问题中应用。

以下是遗传算法的一些常见
应用：
1. 优化问题：遗传算法可以应用于各种优化问题，例如参
数优化、函数最大或最小化、资源分配等。

通过建立适当
的适应度函数和遗传操作，可以在搜索空间中寻找最优解。

2. 机器学习：遗传算法可以用于机器学习中的特征选择、
模型调优等任务。

通过遗传算法的迭代搜索过程，可以找
到最佳的特征集合或模型参数。

3. 调度问题：遗传算法可以应用于调度问题，如任务调度、旅行商问题等。

通过设计合适的编码方式和适应度函数，
可以优化调度方案，提高效率。

4. 组合优化问题：遗传算法在组合优化问题中也有广泛应用，如图着色问题、背包问题等。

通过遗传算法的搜索特性，可以找到组合问题的最优解或近似最优解。

5. 游戏：遗传算法可以用于训练游戏代理程序，如迷宫求解、棋类游戏等。

通过遗传算法的优化过程，可以训练出具有高水平的游戏智能的代理程序。

总的来说，遗传算法可以应用于各种搜索和优化问题，特别是那些复杂且难以在可接受的时间范围内找到最优解的问题。

它具有较好的鲁棒性和全局搜索能力，适用于多种领域。

yjl.m :简单一元函数优化实例，利用遗传算法计算下面函数的最大值f (x) =xsin( 10 二* x) 2.0，x • [-1,2]选择二进制编码，种群中个体数目为40,每个种群的长度为20，使用代沟为0.9,最大遗传代数为25len lbub scale lbin译码矩阵结构: FieldD code译码矩阵说明:len -包含在Chrom中的每个子串的长度，注意sum(len)=length(Chrom);lb、ub -行向量，分别指明每个变量使用的上界和下界；code -二进制行向量，指明子串是怎样编码的，code(i)=1为标准二进制编码，code(i)=0则为格雷编码；scale -二进制行向量，指明每个子串是否使用对数或算术刻度，scale(i)=0为算术刻度，scale(i)=1则为对数刻度；lbin、ubin -二进制行向量，指明表示范围中是否包含每个边界，选择lbin=0或ubin=0,表示从范围中去掉边界；lbin=1或ubin=1则表示范围中包含边界；注：增加第22 行：variable=bs2rv(Chrom, FieldD);否则提示第26 行plot(variable(l), Y, 'bo');中variable(I)越界yj2.m :目标函数是De Jong函数，是一个连续、凸起的单峰函数，它的M文件objfun1包含在GA工具箱软件中，De Jong函数的表达式为：n2f (x) = ' X j , 一512 乞X j E 512i d这里n是定义问题维数的一个值，本例中选取n=20，求解min f (x)，程序主要变量：NIND (个体的数量)：=40;MAXGEN (最大遗传代数)：=500；NVAR (变量维数)：=20 ；PRECI (每个变量使用多少位来表示)：=20；GGAP (代沟)：=0.9注：函数objfun1.m 中switch改为switch1，否则提示出错，因为switch为matlab保留字，下同！yj3.m :多元多峰函数的优化实例，Shubert函数表达式如下，求min f (x)【shubert.m 】f(x 「X 2)= 7 i cos[( i T)*X t i]*7 i cos[( i ■ 1) * x 2 - i] ,- 10 乞 X t , x 2 乞 10i丄i注：第10行各变量的上下限改为[-10;10]，原来为[-3;3];第25行改为：[Y, l]=min(ObjV);原来为[Y, I]=min(ObjVSel);以此将染色体的个 体值与shubert()函数值对应起来， 原表达式不具有 shubert()函数自变量和应变量的对应关系yj4.m :收获系统最优控制，收获系统(Harvest)是一个一阶的离散方程，表达式为x(k T) = a*x(k) - u (k) , k =1, 2,…，N-s.t. x(0)为初始条件x(k)三R 为状态变量u(k 厂R ■为控制输入变量精确优化解:用遗传算法对此问题求解， x(0) =100 , > -1.1，控制步骤N=20 ,决策变量u (k) 个数 NVAR=20, u(k) •二[0,200 ]注：第 20行语句原为：Chrom=crtrp(NIND,FieldDD);改为：Chrom=crtrp(SUBPOP*NIND,FieldDD);运行提示：Warning: File: D:\MA TLAB6p5\toolbox\gatbx\CRTRP .M Line: 34 Column: 19 Variable 'nargin' has bee n previously used as a function n ame. (Type "warni ngoff MATLAB:mir_warni ng_variable_used_as_fu nctio n"tosuppress this warnin g.)yj5.m :装载系统的最优问题，装载系统是一个二维系统，表达式如下X 1 ( k ' 1) = X 2 (k)丄 丄1x 2(k -1) =2 * x 2 (k) —X t (k)^u(k)N目标函数： 1Nf (x,u) - -X t (N 1)u (k)2N k 亠N _1理论最优解： min f (x, u) = _ 1 ■_ - — k 23 6N 2 N k 二目标函数: Nf(x,u)工 J u(k)k40.4 20x( N ) - x(0)k =1, 2,…，Nmax f (x)=Nx(0)(a -1) ~N 」 a (a -1)用遗传算法对此问题求解，x(0) =[0 0],控制步骤N=20,决策变量u(k)个数NVAR=20 , u(k)三[0,10]注：增加第32-35行语句，功能为实现每隔MIGGEN=20代，以迁移率MIGR=0.2在子种群之间迁移个体，增加这几行语句之前求得目标函数最小值为-0.1538，增加这几行语句之后求得目标函数最小值为-0.1544，目标函数理论最优值为-0.1544.yj6.m :离散二次线性系统最优控制问题，其一维二阶线性系统表达式如下：x(k 1)=a*x(k) b*u(k) , k =1, 2,…，N目标函数：N2 2 2f(x,u) =q*x(n 亠1)亠二[s * x( k)亠r*u(k)]k z1参数设置：求min f (x, u)yj7.m :目标分配问题描述为：m个地空导弹火力单元对n批空袭目标进行目标分配。

遗传算法在多目标优化问题中的应用案例分享摘要：遗传算法是一种模拟自然遗传和进化过程的优化算法，多目标优化是在存在多个冲突目标的情况下寻找最优解的问题。

本文将介绍遗传算法在多目标优化问题中的应用案例，并分析其优势和挑战。

引言：多目标优化问题是现实世界中常见问题的一个重要类别，例如资源分配、路径优化、产品设计等。

与单一目标优化问题不同，多目标优化问题涉及到多个冲突目标之间的权衡，寻找一个解决方案使得各个目标都能取得较好的性能是一项困难的任务。

在解决多目标优化问题中，传统的优化算法常常难以取得令人满意的结果。

而遗传算法作为一种模拟生物进化过程的优化算法，能够有效处理多目标优化问题，因此在实际应用中得到广泛的应用。

1. 遗传算法简介遗传算法是通过模拟生物的遗传和进化过程来搜索问题的最优解的一种启发式算法。

其基本过程包括选择、交叉、变异和替换等操作。

通过不断的迭代，遗传算法能够搜索到全局最优解或接近最优解的解空间。

2. 多目标优化问题多目标优化问题涉及到多个冲突目标之间的权衡，需要在多个目标之间寻找一种平衡解。

例如，对于资源分配问题，要同时考虑成本和效益等多个目标。

传统的单一目标优化算法在解决多目标问题上存在局限性，不能找到全局最优解。

3. 遗传算法在多目标优化问题中的应用案例3.1 雷达布局问题雷达布局问题是在给定区域内部署有限数量的雷达，以覆盖可能的目标点，并同时最小化雷达的数量和成本。

由于雷达的位置、数量和覆盖范围等因素之间存在多个冲突目标，传统的优化算法难以找到最优解。

研究者们利用遗传算法进行求解，通过精心设计的编码方式和适应度函数，能够得到较好的布局方案。

3.2 电力系统优化电力系统优化是在满足电力需求和系统运行的前提下，最小化电力系统的总成本和损耗等目标。

由于电力系统涉及到多个冲突目标，如满足负荷需求和降低发电成本，传统的优化算法很难找到最佳解。

研究者们利用遗传算法进行电力系统优化，能够得到较优的方案，同时平衡各个目标的权衡。

遗传算法能解决什么问题
遗传算法主要是用来求解最优化问题的。

一般来讲可以求解函数的最大、最小值问题，还可以结合其它一些方法解决（非）线性回归、分类问题等等。

但遗传算法有两个缺点，一是时间长，二是初值的选择会影响收敛的效果。

它的本质，实际上还是随机搜索算法，还是属于所谓的蒙特卡罗式的方法。

遗传算法的应用比较广泛，可用于解决数值优化、组合优化、机器学习、智能控制、人工生命、图像处理、模式识别等领域的问题。

比较具体多是：函数最值问题、旅行商问题、背包问题、车辆路径问题、生产排程问题、选址问题等。

一、遗传算法的原理1.自然遗传与遗传算法①遗传：子代总是和亲代具有相同或相似的性状。

有了这个特征物种才能稳定存在②变异：亲代和子代之间已经子代不同个体之间的差异，称为变异，变异是随机发生的，变异的选择和积累是生命多样性的根源。

③生存斗争和逝者生存：具有适应性变异的个体被保留下来，不具有适应性变异的个体被淘汰，通过一代代的生存环境的选择作用，性状逐渐与祖先有所不同，演变成新的物种。

④自然界对进化中的生物群体提供及时的反馈信息，或称为外界对生物的评价，评价反映了生物的生存机会。

⑤生物进化是一个不断循环的过程，本质上是一种优化过程。

⑥遗传物质以基因的形式排列在染色体上，每个基因有特殊的位置并控制生物的某些特性。

不同的基因组合产生的个体对环境的适应性不一样。

（对应具体问题，把问题可能解编码成向量---染色体，向量的每个元素就是基因）例如：个体染色体9 ---- 1001（2，5，6）---- 010 101 1102.遗传算法①将“优胜劣汰，适者生存”的生物进化原理引入到求解优化问题中。

②从某一随机产生的初始群体出发③按照变异等遗传操作规则不断地迭代④根据每一个体的适应度，保留优良品种，引导搜索过程向最优解逼近。

⑤在这一过程中，通过随机重组编码位串中重要的基因，使新一代的位串集合优于老一代的位串集合，群体中的个体不断进化，逐渐接近最优解，最终达到求解问题的目的。

二、遗传算法的步骤1.步骤：①选择编码策略，把参数集合X和域转换成位串结构空间S；②定义适应函数f(X);③确定遗传策略，包括选择群体大小n，选择、交叉、变异方法，以及确定交叉概率、变异概率等遗传参数；④随机初始化生成群体P；⑤计算群体中个体位串解码后的适应值f(X)⑥按照遗传策略，运用选择（选择的目的是把优化的个体直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。

选择操作是建立在群体中个体的适应度评估基础上的）、交叉（所谓交叉是指把两个父代个体的部分结构加以替换重组而生成新个体的操作。

遗传算法经典实例遗传算法（GeneticAlgorithm）是一种启发式算法，用于解决最优问题，和模拟生物进化类似，其特点是快速搜索，但是搜索的结果可能不是最优解。

它的优点是不需要专业的数学分析，而且它能够自动生成可行的解是处理复杂问题时，解决模糊、离散、多目标和非凸优化问题的有力工具之一。

遗传算法也称为遗传进化算法(GEA)。

一般来说，遗传算法由三大部分组成：初始化、评价和改进。

在初始化的过程中，需要产生一组随机的解，又称为种群，作为遗传算法的输入。

然后，评价和改进过程将对每一组解进行评价，给出一个目标函数值。

根据该值，算法会选择出个体中最优的解；接着，算法会根据某种选择策略，改进个体，以应对更优的解。

在这里，我们要介绍的是遗传算法的三个经典实例：蒙特卡罗搜索（Monte Carlo Search）、穷举法（Exhaustive Enumeration）和全局尺度搜索（Global Scale Search）。

蒙特卡罗搜索是一种以随机生成的解作为初始状态，每次改变这些解的某个变量，以达到全局最优解的搜索方法。

蒙特卡罗搜索的实现简单，但是结果的精确度可能较低，因此一般在解决复杂问题时不能使用它。

穷举法是一种从给定的域中搜索最优解的方法，它需要枚举所有可能的解，从而找出最优解。

不过，当问题规模较大时，这种方法可能会耗费极大的时间，并且难以适用于复杂问题。

全局尺度搜索是一种启发式搜索，它将搜索空间分割成多个子空间，并且在每一个子空间中运行算法。

它能够有效地探测全局的最优解，并且在处理复杂问题时，具有较高的搜索效率。

除此之外，还有一种多维空间搜索方法，它可以利用改进后的解作为新的解进行搜索，从而获得更优的解。

与其他搜索方法不同，它能够在少量的步骤中完成搜索，因此具有较高的搜索效率。

总而言之，遗传算法的三种经典实例都具有自身的优点，同时又能够有效地处理复杂问题。

如果要解决一定的最优化问题，我们可以根据不同的环境，结合上述三种搜索方法，在较短的时间内获得更优的解。