遗传算法及其函数优化应用

遗传算法综述及简单应用实例

1、遗传算法简介

1.1遗传算法的产生与发展

1.2生物进化理论和遗传学的基本知识

1.3模式定理

1.4遗传算法的特点

1.5基本遗传算法

1.5.1基本遗传算法流程

1.5.2算法中的一些控制参数

1.5.3基本遗传算法实例

1.6遗传算法的应用

2、遗传算法应用实例3、遗传算法改进1、遗传算法简介

产生60年代中期，美国Michigan大学的J.H.Holland教授提出借鉴生物自然遗传的基本原理用于自然和人工系统的自适应行为研究和串编码技术；1967年，他的学生J.D.Bagley在博士论文中首次提出“遗传算法(Genetic

Algorithms)”一词；1975年，Holland出版了著名的“AdaptationinNaturalandArtificialSystems”，标志遗传算法的诞生。1.1遗传算法的产生与发展（1/3）

1、遗传算法简介

发展70年代初，Holland提出了“模式定理”（SchemaTheorem），一般认为是“遗传算法的基本定理”，从而奠定了遗传算法研究的理论基础；1985年，在美国召开了第一届遗传算法国际会议，并且成立了国际遗传算法学会(ISGA，InternationalSocietyofGeneticAlgorithms)；1.1遗传算法的产生与发展

(2/3)1、遗传算法简介

发展1988年，Holland的学生D.J.Goldherg出版了“GeneticAlgorithmsinSearch,Optimization,andMachineLearning”，对遗传算法及其应用作了全面而系统的论述；1991年，L.Davis编辑出版了《Handbookofgeneticalgorithms》，其中包括了遗传算法在工程技术和社会生活中大量的应用实例。

1.1遗传算法的产生与发展(3/3)1、遗传算法简介

遗传学基本概念与术语染色体（chromosome）：问题中个体的某种字符串形式的编码表示。基因（gene）：字符串中的字符。基因座（locus）：遗传基因在染色体中所占据的位置；等位基因（allele）：同一基因座可能有的全部基因；个体（individual）：指染色体带有特征的实体；种群（population）：个体的集合；种群规模（populationsize）:种群内个体的个数。1.2生物进化理论和遗传学的基本知识(1/5)

1111111

11101111、遗传算法简介

遗传学基本概念与术语基因型（genotype）：遗传因子组合的模型；表现型（phenotype）：由染色体决定性状的外部表现；适应度（fitness）：度量某个物种对于生存环境的适应程度。对生存环境适应程度较高的物种将获得更多的繁殖机会，而对生存环境适应程度较低的物种，其繁殖机会就会相对较少，甚至逐渐灭绝;选择（selection）：以一定的概率从种群中选择若干个体的操作；

1.2生物进化理论和遗传学的基本知识(2/5)

1、遗传算法简介

遗传学基本概念与术语复制（reproduction）：细胞在分裂时，遗传物质DNA通过复制而转移到新产生的细胞中，新的细胞就继承了旧细胞的基因;交叉（crossover）：在两个染色体的某一相同位置处基因分别交叉组合形成两个新的染色体；变异（mutation）：在细胞进行复制时可能以很小的概率产生某些复制差错，从而使DNA发生某种变异，产生出新的染色体，这些新的染色体表现出新的性状;1.2生物进化理论和遗传学的基本知识(3/5)

1、遗传算法简介

遗传学基本概念与术语编码（coding）：表现型到基因型的映射；解码（decoding）：从基因型到表现型的映射。

1.2生物进化理论和遗传学的基本知识(4/5)

基因型：0111表现型：0.637197个体（染色体）基因解码编码编码原则完备性（completeness）：问题空间的所有解都能表示为所设计的基因型；健全性（soundness）：任何一个基因型都对应于一个可能解；非冗余性（non-redundancy）：问题空间和GA空间一一对应。上述三个规范虽带有普遍性，但缺乏具体的指导思想，相比之下，Dejong提出较为客观明确的编码评估准则：（1）有意义积木块编码规则：所定编码应当易于生成与所求问题想关的短距和低阶的积木块。（2）最小字符集编码规则：所定编码应采用最小字符集以使问题得到自然的表示或描述。多种编码方式特点二进制编码；浮点数编码；格雷码编码；符号编码；复数编码；DNA编码等。1、遗传算法简介

1.2生物进化理论和遗传学的基本知识(5/5)

模式

将种群中的个体即基因串中的相似样板称为模式。在二进制编码的串中，模式是基于三个字符集（0，1，*）的字符串，符号*代表任意字符，即0或1。如模式*1*描述了一个四个元的子集{010，011，110，111}。1.3模式定理(1/8)1、遗传算法简介

模式阶和定义距

模式H中确定位置的个数称为模式H的模式阶，记作O(H)，如O(011*1*)=4；O(0******)=1。很明显前者与后者相比，所匹配的串的个数要少一些，即确定性更高。因此，模式阶用来反映不同模式间确定性的差异，模式阶越高，模式的确定性就越高，所匹配的样本个数就越少。

模式H中第一个确定位置和最后一个确定位置之间的距离称为模式的定义距，记作δ(H)，如δ(011*1**)=4。阶数相同的模式会有不同的性质，定义距就反映了这种性质的差异。定义距越短模式越不易遭到破坏。1.3模式定理(2/8)

1、遗传算法简介

1.3模式定理(3/8)

模式定理（schematheorem）假设在第t代，群体A(t)中模式H所能匹配的样本数为m，记作m(H,t)。在选择中一个串是根据其适应度进行复制的。更确切的说，一个串是以如下概率进行选择的。1、遗传算法简介

模式定理（schematheorem）

当群体大小为n

时，且两个个体互不相同，则模式在第t+1代中的样本数为：

其中f(H)是在第t代，模式H

的串的平均适应度；

而整个种群的平均适应度为1、遗传算法简介

1.3模式定理(4/8)

模式定理（schematheorem）假设某一特定模式适应度值一直保持在种群平均适应度以上一个cf

（c为一常数），则模式的选择生长方程为在种群平均值以上（以下）的模式将按指数增长（衰减）的方式复制。¯1、遗传算法简介

1.3模式定理(5/8)

模式定理（schematheorem）

考虑交叉操作，模式H

被破坏的概率为

δ(H)/(l-1)，模式H

生存概率为1-δ(H)/(l-1)，若交叉操作发生的概率为pc，因此对于模式H

的生存概率计算为：

同时考虑选择、交叉操作对模式的影响，可得：H1=*1****0H2=***10*01、遗传算法简介

1.3模式定理(6/8)

模式定理（schematheorem）

考虑变异操作，单个等位基因存活的概率为

1-pm

，当模式H

中O(H)个确定位都存活时，模式H

才被保留，存活概率为：

同时考虑选择、交叉和变异操作对模式的影响，可得：1.3模式定理(7/8)H1=*1****0H2=***10*01、遗传算法简介

模式定理（schematheorem）

模式定理：在遗传算子选择、交叉、变异的作用下，具有低阶、短定义距以及平均适应度高于种群平均适应度的模式在子代中呈指数增长。具有低阶、短定义距以及平均适应度高于种群平均适应度的模式被定义为积木块。积木块假设（buildingblockhypothesis）

遗传算法通过短定义距、低阶及高平均适应度的模式（积木块），在遗传操作作用下相互结合，最终接近全局最优解。编码原则1.3模式定理(8/8)1、遗传算法简介

1遗传算法简介

①

遗传算法的处理对象不是参数（优化问题的参变量）本身，而是对参数集进行了编码的个体。这种编码操作，使得遗传算法可直接对结构对象进行操作（所谓结构对象泛指集合、序列、矩阵、树、图、链和表等各种一维或高维结构形式）。这一特点使得遗传算法具有广泛的应用领域，例如：通过对连接矩阵的操作，遗传算法可用来对神经网络结构或参数加以优化。通过对集合的操作，遗传算法可实现对规则集合或知识库的精练而达到高质量的机器学习目的。通过对树结构的操作，遗传算法可得到用于分类的最佳结构树。通过对任务序列的操作，遗传算法可用于任务规划，而通过对操作序列的处理，遗传算法可自动构造顺序控制系统。

②遗传算法的基本作用对象是多个可行解的集合，而非单个可行解。它是采用同时处理群体中多个个体的方法，即同时对搜索空间中的多个解进行评估。这一特点使遗传算法具有较好的全局搜索性能，减少了陷于局部优解的可能性。同时这又使得遗传算法本身具有良好的并行性。1.4遗传算法的特点（1/2）③遗传算法仅用适应度函数值来评估个体，而无须搜索空间的知识或其它辅助信息。遗传算法的适应度函数不仅不受连续可微的约束，而且其定义域可以任意设定。对适应度函数的唯一要求是，对于输入可计算出能够进行比较的非负输出。遗传算法的这一特点使它的应用范围极大拓宽，使之可广泛应用于目标函数不可微、不连续、非规划、极其复杂或无解析表达式等类优化问题。④遗传算法不是采用确定性规则，而是采用概率的变迁规则来指导它的搜索方向。遗传算法执行选择、交叉、变异等类似生物进化过程的简单随机操作，具有极强的鲁棒性。需要指出，遗传算法采用概率仅仅是作为一种工具来引导其搜索过程朝着搜索空间的更优的解的区域移动。因此尽管看起来它是一种盲目的搜索方法，但实际上有明确的搜索方向。1遗传算法简介

1.4遗传算法的特点(2/2)1遗传算法简介

遗传算法的基本思路

1.5基本遗传算法1遗传算法简介

1.5.1基本遗传算法流程(1/2)

遗传算法基本流程框图生成初始种群计算适应度选择-复制交叉变异生成新一代种群终止?结束1遗传算法简介

1.5.1基本遗传算法流程(2/2)（1）在搜索空间U上定义一个适应度函数f(x)，给定种群规模N，交叉率Pc和变异率Pm，代数T；（2）随机产生U中的N个个体组成初始种群S={s1,s2,…,sN}，置代数计数器t=1；（3）计算S中每个个体的适应度f()；（4）若终止条件满足，则取S中适应度最大的个体作为所求结果，算法结束。（5）按选择概率P(xi)所决定的选中机会，每次从S中随机选定1个个体并将其染色体复制，共做N次，然后将复制所得的N个染色体组成群体S1；（6）按交叉率Pc所决定的参加交叉的染色体数c，从S1中随机确定c个染色体，配对进行交叉操作，并用产生的新染色体代替原染色体，得群体S2；（7）按变异率Pm所决定的变异次数m，随机确定m个染色体，分别进行变异操作，并用产生的新染色体代替原染色体，得群体S3；（8）将群体S3作为新一代种群，即用S3代替S，t=t+1，转（3）；1遗传算法简介

1.5.2算法中的一些控制参数:

（1/23）适应度函数(fitnessfunction)：

问题中的全体个体与其适应度之间的一个对应关系。它一般是一个实值函数。该函数就是遗传算法中指导搜索的评价函数。适应度函数越大，解的质量越好。

由于适应度函数要比较排序并在此基础上计算选择概率，因此，对适应度函数的唯一要求是，针对输入可计算出能加以比较的非负结果。适应度函数评估是选择操作的依据，适应度函数设计直接影响到遗传算法的性能。1.5.2算法中的一些控制参数:

（2/23）适应度函数(fitnessfunction)：(1)当优化目标是求函数最大值，并且目标函数总取正值时，可以直接设定个体的适应度函数F(x)就等于相应的目标函数值f(x)，即：当求目标函数最小值的优化问题，理论上只需简单地对其增加一个负号即可，即：但实际优化问题中的目标函数值有正也有负，优化目标有求函数最值，也有求函数最小值，显然如上所述保证不了所有情况下个体的适应度都是非负数这个要求。对此，可采用以下方式进行转换。1遗传算法简介

1遗传算法简介

1.5.2算法中的一些控制参数:

（3/23）系数可以是一个合适的输入值，也可以采用迄今为止进化过程中函数值的最大值或当前群体中函数的最大值，也可以是前K代中函数的最大值。最好与群体无关。基本遗传算法一般用以下两种方式计算个体适应度函数方法一：对于求目标函数最小值的优化问题：

对于求目标函数最大值的优化问题：Cmin可以是合适的输入值，或是当前一代或前K代中的函数最小值，也可以是群体方差的函数。适应度函数(fitnessfunction)：1遗传算法简介

1.5.2算法中的一些控制参数:

（4/23）方法二：若目标函数为最大化问题：若目标函数为最小化问题：

c为目标函数的保守估计值。适应度函数(fitnessfunction)：

应用遗传算法来处理小规模群体时常常出现一些不利于优化的结果。在进化初期，通常会出现一些超常的个体。这些异常个体有可能在群体中占的比例很大，可能因个体竞争力太突出控制整个选择过程而导致未成熟收敛现象。此外，在遗传进化过程往往会出现平均适应度已接近最佳个体适应度，这种情况下，个体间竞争力减弱，最佳个体和其它大多数个体在选择过程中有几乎相等的选择机会，从而使有目标的优化过程趋于无目标的随机漫游过程。显然，对于未成熟收敛现象，我们应该通过缩小相应的适应度函数值来降低异常个体的竞争力。对于随机漫游现象，我们应该通过放大相应的适度度函数值来提高个体间的竞争力。这种对适应度函数的缩放调整称为适应度定标。适应度的定标大致分为：线性定标、σ截断、乘幂标。1遗传算法简介

适应度函数(fitnessfunction)：1.5.2算法中的一些控制参数:

（5/23）1遗传算法简介适应度函数的线性变换法

f’=α*f+β

系数的确定满足以下条件：①f’avg=favg②f’max=cmultf’avg

cmult=1.0~2.0，α和β取适当值，以保证适应度值非负。1.5.2算法中的一些控制参数:

（6/23）

适应度函数及其尺度变换

1遗传算法简介适应度函数的幂函数变换法

f’=fkk与所求优化问题相关，而且在算法过程中可按需要修正。该定标方式同Gillies提出，他曾在机器视觉实验中采用了此方法，当时，取k＝1.005

适应度函数及其尺度变换

适应度函数的指数变换法f’=e-afa决定了复制的强制性。a越大，大适应度的个体被复制的强制性就越弱。1.5.2算法中的一些控制参数:

（7/23）1.5.2算法中的一些控制参数:

（8/23）遗传算子（geneticoperator）选择算子：用选择运算来实现对群体中的个体进得优胜劣汰，适应度高的个体被遗传到下一代种群中的概率就大.选择算子就是某种选择方法，从父代群体中选一些个体遗传到下一代。目前常用的选择算子有以下几种：（1）适应度比例方法（fitnessproportionalmodel）这是目前遗传算法中最基本也是最常用的选择方法。它也叫做赌轮或蒙特卡罗选择。在该方法中，各个个体的选择概率和基适应度值成比例。选择概率用下式求出：

其中：群体规模为M，为个体i的适应度值。1遗传算法简介

1.5.2算法中的一些控制参数:

（9/23）遗传算子（geneticoperator）选择算子：用选择运算来实现对群体中的个体进得优胜劣汰，适应度高的个体被遗传到下一代种群中的概率就大.选择算子就是某种选择方法，从父代群体中选一些个体遗传到下一代。目前常用的选择算子有以下几种：（1）适应度比例方法（fitnessproportionalmodel）

这是目前遗传算法中最基本也是最常用的选择方法。它也叫做赌轮或蒙特卡罗选择。在该方法中，各个个体的选择概率和基适应度值成比例。选择概率用下式求出：

其中：群体规模为M，为个体i的适应度值。1遗传算法简介

（2）随机遍历抽样法（stochasticuniversalsampling）

此方法与轮盘赌选择法基本相似，是对它的一种改进，特点是只要进行一次轮盘旋转。其采用均匀分布且个数等于种群规模的旋转指针，等距离选择个体，其中第一个指针位置由［0，1/M］区间的均匀随机数决定，提供了零偏差和最小个体扩展。1遗传算法简介

1.5.2算法中的一些控制参数:

（10/23）（3）局部选择法（localselection）

在局部选择法中，每个个体处于一个约束环境中，称为局部邻集（而其它选择方法中视整个种群为个体之邻集），个体仅与其临近个体产生交叉，该邻集的定义由种群的分布结构给出，邻集可被当作潜在的交配伙伴。1遗传算法简介

1.5.2算法中的一些控制参数:

（11/23）

线性邻集两对角邻集（4）最佳个体保存方法（elitistmodel）该方法的思想是把群体中适应度最高的个体不进行配对交叉而直接复制到下一代中。此种选择又称为复制。此方法能使进化过程中某一代的最优解不被交叉和变异破坏，但可能会急速增加局部最优个体的基因而导致限入局部最优解。该方法的全局搜索能力差，一般都与其他选择方法结合使用。（5）期望值方法（expectedvaluemodel）该方法首先计算群体中每个个体在下一代生存的期望数目：若某个个体要参与配对和交叉，则它在下一代中的生存期望数目减去0.5；若不参与配对和交叉，则减1。若一个个体的期望值小于0，则不参与选择。实验表明，这期望值方法更优。（6）排序选择法（rank-basedmodel）指在计算每个个体的适应度后，根据适应度大小对群体中个体排序，然后把事先设计好的概率表按序分配给个体，作为各自的选择概率。1遗传算法简介

1.5.2算法中的一些控制参数:

（12/23）（7）联赛选择方法（tournamentselectionmodel）该方法的操作思想是从群体中任意选择一定数目的个体（一般选2个），其中适应度最高的个体保存到下一代，这个过程反复执行，直到保存到一一代的个体数达到预先设定的数目为止。（8）排挤方法（crowdingmodel）采用该方法时，新生成的子代将替代或排挤相似的旧父代个体。该方法可提高群体的多样性。交叉算子：交叉就是指把两个父代个体的部分结构加以替换重组而生成新个体的操作。通过交叉，遗传算法的搜索能力得以飞跃提高。以下介绍几种基本交叉方法：（1）一点交叉（one-pointcrossover）一点交叉又称为简单交叉，在个体串中随机设定一个交叉点，该点前或后的两个个体的部分结构进行互换，并生成两个新的个体，如下图所示。

1遗传算法简介

1.5.2算法中的一些控制参数:

（13/23）（2）二点交叉（two-pointcrossover）二点交叉的操作与一点交叉类似，只是设置两个交叉点，两个交叉点之间的码串相互交换，分别生成新个体，举例如下：（3）多点交叉（multi-pointcrossover）多点交叉是前述两种交叉的推广，有时又被称为广义交叉。一般情况多点交叉比较少用。（4）一致交叉（uniformcrossover）一致交叉是指通过设置屏蔽字来决定新个体的基因继承两个旧个体中的哪个个体的对应基因，又称为均匀交叉。当屏蔽字的位为0时，新个体A’继承旧个体A中对应的基因；1遗传算法简介

1.5.2算法中的一些控制参数:

（14/23）单点交叉A；1011011100A’：1011011111B：0001110011B’：0001110000双点交叉A:1011011A’:1001011B:0001000B’:0011000当屏蔽字为1时，新个体A’继承旧个体B中对应的基因，由此生成一个完整的新个体A’，反之得到新个体B’，举例如下：（5）基它交叉方法针对各个问题的不同，可以提出多种交叉方法，如二维交叉，MessayGA中的交叉，树结构交叉以及TSP问题中的部分匹配交叉，顺序交叉和周期交叉等。交叉概率：指的就是群体中参与交叉的个体数目占群体规模的比重。用Pc来表示。1遗传算法简介

1.5.2算法中的一些控制参数:

（15/23）旧个体A001111旧个体B111100屏蔽字010101新个体A’011110新个体B‘101101实值重组离散重组子个体的每个变量可以按等概率随机地挑选父个体。父个体1

12

25

5父个体2

123434子个体1

1234

5子个体2

12

4341遗传算法简介

1.5.2算法中的一些控制参数:

（16/23）实值重组中间重组

子个体＝父个体1＋α×（父个体2－父个体1）

α是比例因子，由[-d,1+d]上均匀分布地随机数产生。一般取d=0.25。子代的每个变量均产生一个α

。1遗传算法简介

1.5.2算法中的一些控制参数:

（17/23）实值重组中间重组

父个体1

12255父个体2

123434子个体1子个体2α值样本1

0.51.1-0.1α值样本2

0.10.80.512＋0.5×（123－12）=67.567.525＋1.1×（4－25）=1.91.92.112＋0.1×（123－12）=23.123.18.219.51遗传算法简介

1.5.2算法中的一些控制参数:

（18/23）实值重组中间重组

1遗传算法简介

1.5.2算法中的一些控制参数:

（19/23）实值重组线性重组

父个体1

12255父个体2

123434子个体1子个体2α值样本1

0.5α值样本2

0.112＋0.5×（123－12）=67.567.525＋0.5×（4－25）=14.514.519.512＋0.1×（123－12）=23.123.122.97.91遗传算法简介

1.5.2算法中的一些控制参数:

（20/23）实值重组线性重组

1遗传算法简介

1.5.2算法中的一些控制参数:

（21/23）变异算子：变异算子的基本内容是对群体中的个体串的某些基因座上的基因值作变动。就二进值码串而言，就是将基因座上的基因值取反。（1）基本变异算子基本变异算子是指对群体中的个体码串随机挑一个或多个基因并对这些基因值做变动，二进制码串中的变异操作如下：

A：1010101010A’:1010001010（2）逆转算子（inversionoperator）在个体码串中随机挑选两个逆转点，然后将两点间的基因值以逆转概率逆向排序。二进制码串的逆转操作如下：1遗传算法简介

1.5.2算法中的一些控制参数:

（22/23）变异点基本位变异A：101101000A’:100101100逆转点逆转（3）自适应变异算子（adaptivemutationoperator）该算子与基本变异算子的操作内容类似，唯一不同的是变异概率Pm不是固定不变的，而是随群体中个体的多样性程度而自适应调整的。一般是根据交叉得到的两个新个体的海明距离进行变化。海明距越小，Pm越大，反之Pm越小。变异概率：1遗传算法简介

1.5.2算法中的一些控制参数:

（23/23）变异是针对个体的某一个或某一些基因座上的基因值执行的，因此变异概率Pm也是针对基因而言，即：Pm=BM·l

式中：B——每代中变异的基因数目；

M——每代中群体拥有的个体数目

λ——个体中基因串长度。例：利用遗传算法求解区间［0,31］上的二次函数y=x2的最大值。

y=x2

31

XY1遗传算法简介

1.5.3基本遗传算法实例（1/5）1遗传算法简介

1.产生初始种群2.计算适应度1.5.3基本遗传算法实例（2/5）01101(13)11000

(24)01000

(8)10011

(19)169576643611遗传算法简介

1.5.3基本遗传算法实例（3/5）串编号随机产生初始群体X（无符号整数）适应度f(x)=x2选择概率适应度期望值实际计算（来自赌轮）复制后配对库交叉位置（随机选择）新一代群体X值适应度f(x)=x21011011316901101401100121442110002457611000411001256253010008641100021101127729410011193611001121000016256总和1754平均293439最大576729169169+576+64+3610.140.490.060.311.000.250.49169169+576+64+36141.970.221.234.001.001.9712014120.581遗传算法简介

1.5.3基本遗传算法实例（4/5）s40.31s20.49s10.14s30.06比例选择法（赌轮选择法）在算法中赌轮选择法可用下面的子过程来模拟:

①在［0,1］区间内产生一个均匀分布的随机数r。②若r≤q1,则染色体x1被选中。③若qk-1<r≤qk(2≤k≤N),则染色体xk被选中。其中的qi称为染色体xi(i=1,2,…,n)的积累概率,其计算公式为1遗传算法简介

1.5.3基本遗传算法实例（5/5）

设从区间［0,1］中产生4个随机数如下:r1=0.450126,r2=0.110347r3=0.572496,r4=0.98503

染色体

适应度选择概率积累概率选中次数s1=011011690.140.141s2=110005760.490.632s3=01000640.060.690s4=100113610.311.001淘汰1遗传算法简介

函数优化函数优化是遗传算法的经典应用领域，也是对遗传算法进行性能评价的常用算例。很]多人构造出了各种各样的复杂形式的测试函数。有连续函数也有离散函数，有凸函数也有凹函数，有低维函数也有高维函数，有确定函数也有随机函数，有单峰值函数也有多峰值函数等。用这些几何特性各具特色的函数来评价遗传算法的性能，更能反映算法的本质效果而对于一些非线性、多模型、多目标的函数优化问题，用其他优化方法较难求解。而遗传算法却可以方便地得到较好的结果。组合优化组合优化是指在离散的、有限的数学结构上，寻找一个满足给定约束条件并使其目标函数值达到最大或最小的解。一般来说，组合优化问题通常带有大量的局部极值点，往往是不可微的、不连续的、多维的、有约束条件的、高度非线性的NP完全问题。因此，精确的求解组合优化问题的全局最优解一般是不可能的。而遗传算法作为一种新型的随机化搜索、优化方法，已在诸多典型组合优化问题，如求解旅行商问题、背包问题、装箱问题、布局优化、图形划分问题等各种具有np难度的等问题中显示了良好的性能和效果。1.6遗传算法的应用（1/7）

遗传算法与神经网络遗传算法的提出使神经网络的训练有了一个崭新的面貌，用遗传算法优化神经网络，可以使得神经网络具有自进化、自适应能力，从而构造出进化的神经网，它主要包括三个方面：连接权的进化、网络结构的进化，学习规则的进化。遗传算法与模糊集理论关于模糊推理规则的优化，以前主要采用神经网络方法。但神经网络由于存在网络规模和网络结构较为复杂以及学习收敛性问题，因此引入了遗传算法研究模糊集规则的优化及隶属度函数的调整。主要方法为先由遗传算法产生大致的模糊模型，然后由增量规则进行调整，获得优化的模糊模型。1遗传算法简介

1.6遗传算法的应用(2/7)1遗传算法简介

遗传算法与机器学习学习能力是高级自适应系统所具备的能力之一，基于遗传算法的机器学习，特别是分类器系统，在很多领域中都得到了应用。例如，遗传算法被用于学习模糊控制规则，利用遗传算法来学习隶属度函数，从而更好地改进了模糊系统的性能；基于遗传算法的机器学习可用来调整人工神经网络的连接权，也可用于人工神经网络结构优化设计；分类器系统也在学习式多机器人路径规划系统中得到了成功的应用。遗传算法与并行处理遗传算法固有的并行性和大规模并行机的快速发展，促使许多研究者开始研究遗传算法的并行化问题。遗传算法与并行计算机的结合，能把并行机的高速性和遗传算法固有的并行性两者的长处彼此结合起来。1.6遗传算法的应用(3/7)1遗传算法简介

遗传算法与人工生命人工生命是用计算机、机械等人工媒体模拟或构造出的具有自然生物系统特有行为的人造系统。自组织能力和自学习能力是人工生命的两大主要特征。人工生命与遗传算法有着密切的关系。基于遗传算法的进化模型是研究人工生命现象的重要基础理论。虽然人工生命的研究尚处于启蒙阶段，但遗传算法已在其进化模型、学习模型、行为模型、自组织模型等方面显示出了初步的应用能力，并且必将得到更为深入的应用和发展。人工生命与遗传算法相辅相成，遗传算法为人工生命的研究提供一个有效的工具，人工生命的研究也必将促进遗传算法的进一步发展。1.6遗传算法的应用(4/7)

遗传算法与生产调度问题生产调度问题在很多情况下建立起来的数学模型难以精确求解，即使经过一些简化之后可以进行求解.也会因简化得太多而使得求解结果与实际相差甚远。目前在现实生产中主要是靠一些经验来进行调度。现在遗传算法已成为解决复杂调度问题的有效工具。在单件生产车间调度、流水线生产间调度、生产规划、任务分配等方面遗传算法都得到了有效的应用。

.遗传算法与自动控制在自动控制领域中有很多与优化相关的问题需要求解。遗传算法已在其中得到了初步的应用，并显示出良好的效果。例如用遗传算法进行航空控制系统的优化、使用遗传算法设计空间交会控制器、基于遗传算法的模糊控制器的优化设计、基于遗传算法的参数辨识、基于遗传算法的模糊控制规则的学习、利用遗传算法进行人工神经网络的结构优化设计和权值学习等。都显出了遗传算法在这此领域中应用的可能性。

1遗传算法简介

1.6遗传算法的应用(5/7)

遗传算法与机器人学机器人是一类复杂的难以精确建模的人工系统，而遗传算法的起源就来自于人工自适应系统的研究。所以，机器人学理所当然地成为遗传算法的一个重要应用领域。例如，遗传算法已经在移动机器人路径规划、关节机器人运动轨迹规划、机器人逆运动学求解、细胞机器人的结构优化和行为协调等方而得到研究和应用。遗传算法与图像处理图像处理是计算机视觉中的一个重要研究领域。在图像处理过程中，如扫描、特征提取、图像分割等不可避免地会存在一此误差，从而影响图像的效果。如何使这些误差最小是使计算机视觉达到实用化的重要要求。遗传算法在这些图像处理中的优化计算方面找到了用武之地。目前已在模式识别(包括汉字识别)、图像恢复、图像边缘特征提取等方而得到了应用。数据挖掘sunil已成功地开发了一个基于遗传算法的数据挖掘下具。利用该工具对两个飞机失事的真实数据库进行了数据挖掘实验，结果表明遗传算法是进行数据挖掘的有效方法之一。

1遗传算法简介

1.6遗传算法的应用(6/7)

遗传编程

1989年，美国standford大学的koza教授发展了遗传编程的概念,其基本思想是:采用树型结构表示计算机程序,运用遗传算法的思想,通过自动生成计算机程序来解决问题。虽然遗传编程的理论尚未成热,应用也有一些限制,但它已成功地应用于人工智能、机器学习等领域。目前公开的遗传编程实验系统有十多个。例如，koza开发的adf系统，while开发的gpelst系统等。

1遗传算法简介

1.6遗传算法的应用(7/7)

2.遗传算法应用实例

问题的提出

一元函数求最大值：2.1简单函数优化的实例

2遗传算法应用实例

问题的提出

用微分法求取f(x)的最大值：解有无穷多个：

2.1简单函数优化的实例

问题的提出当i为奇数时xi对应局部极大值点，i为偶数时xi对应局部极小值。x19即为区间[-1,2]内的最大值点：此时，函数最大值f(x19)比f(1.85)=3.85稍大。

4.2.1简单函数优化的实例

2遗传算法应用实例

2遗传算法应用实例

编码

表现型：x

基因型：二进制编码（串长取决于求解精度）

串长与精度之间的关系：若要求求解精度到6位小数，区间长度为2-(-1)＝3，即需将区间分为3/0.000001=3×106等份。所以编码的二进制串长应为22位。

2.1简单函数优化的实例

产生初始种群产生的方式：随机产生的结果：长度为22的二进制串产生的数量：种群的大小（规模），如30，50，…100011100100100100010000011010010000000000……2.1简单函数优化的实例

2遗传算法应用实例

计算适应度不同的问题有不同的适应度计算方法本例：直接用目标函数作为适应度函数①将某个体转化为[-1,2]区间的实数：s=<0111>→x=0.637197②计算x的函数值（适应度）：f(x)=xsin(10πx)+2.0=2.5863452.1简单函数优化的实例

2遗传算法应用实例

计算适应度

二进制与十进制之间的转换：

第一步，将一个二进制串（b21b20…b0）转化为10进制数：

第二步，x’对应的区间[-1,2]内的实数：

2.1简单函数优化的实例

(0000000000000000000000)→-1(1111)→2x=umin+(

bi·2i-1)

·

λi=1Umax

umin2l

12遗传算法应用实例

遗传操作

选择：轮盘赌选择法；交叉：单点交叉；变异：小概率变异2.1简单函数优化的实例

2遗传算法应用实例

模拟结果设置的参数：种群大小50；交叉概率0.75；变异概率0.05；最大代数200。得到的最佳个体：smax=<1100>;xmax=1.8506;f(xmax)=3.8503;2.1简单函数优化的实例

2遗传算法应用实例

模拟结果

进化的过程：

2.1简单函数优化的实例

世代数自变量适应度11.44953.449491.83953.7412171.85123.8499301.85053.8503501.85063.8503801.85063.85031201.85063.85032001.85063.85032遗传算法应用实例

运行程序

2遗传算法应用实例

2.1简单函数优化的实例

运行程序

2.1简单函数优化的实例

2遗传算法应用实例

运行程序

2遗传算法应用实例

2.1简单函数优化的实例

运行程序

2.1简单函数优化的实例

2遗传算法应用实例

2遗传算法应用实例约束最优化问题（ConstrainedOptimizationProblems）

2.2解决带约束的函数优化问题

解决途径将有约束问题转化为无约束问题（罚函数法，penaltyfunctionmethod），历史较长；改进无约束问题的方法，使之能用于有约束的情况（梯度投影算法），发展较晚。遗传算法解决有约束问题的关键是对约束条件的处理（直接按无约束问题处理是行不通的：随机生成的初始点中可能有大量不可行解；遗传算子作用于可行解后可能产生不可行解）。2遗传算法应用实例2.2解决带约束的函数优化问题

罚函数法将罚函数包含到适应度评价中：

关键是如何设计罚函数，需要谨慎地在过轻或过重惩罚之间找到平衡，针对不同问题设计罚函数。2遗传算法应用实例2.2解决带约束的函数优化问题

罚函数法评价函数的构造：加法

乘法2.2解决带约束的函数优化问题

2遗传算法应用实例罚函数法罚函数分类：定量惩罚——简单约束问题变量惩罚——复杂约束问题，包含两个部分：可变惩罚率和违反约束的惩罚量。违反约束程度——随违反约束程度变得严重而增加惩罚压力，静态惩罚；进化迭代次数——随着进化过程的进展而增加惩罚压力，动态惩罚。2遗传算法应用实例2.2解决带约束的函数优化问题

TSPBenchmark问题

4194;3784;5467;2562;764;299;6858;7144;5462;8369;6460;1854;2260;8346;9138;2538;2442;5869;7171;7478;8776;1840;1340;827;6232;5835;4521;4126;4435;4502.3解决组合优化问题

2遗传算法应用实例TSPBenchmark问题

编码：直接采用解的表示形式，30位（30个城市）长，每位代表所经过的城市序号（无重复）；

适应度函数：个体所代表的路径距离的倒数；

选择：轮盘赌方法

2.3解决组合优化问题

2遗传算法应用实例TSPBenchmark问题

交叉：有序交叉法

1）随机选取两个交叉点；

2）两个父个体交换中间部分；

3）替换交换后重复的城市序号。X1:98|45671|320X2:87|14032|965X1’:98|14032|320X2’:87|45671|965X1’:98|14032|756X2’:83|45671|9022遗传算法应用实例2.3解决组合优化问题

TSPBenchmark问题

变异：随机选择同一个个体的两个点进行交换；初始参数：种群规模100

交叉概率0.8

变异概率0.8

终止代数20002遗传算法应用实例2.3解决组合优化问题

TSPBenchmark问题

运行结果：2遗传算法应用实例2.3解决组合优化问题

TSPBenchmark问题运行结果：2遗传算法应用实例2.3解决组合优化问题

TSPBenchmark问题运行结果：2遗传算法应用实例2.3解决组合优化问题

TSPBenchmark问题运行结果：2遗传算法应用实例2.3解决组合优化问题

TSPBenchmark问题运行结果：2遗传算法应用实例