遗传算法课件

遗传算法函数优化问题无约束优化问题有约束优化问题组合优化问题旅行商TSP问题背包问题混合离散优化问题混沌法MILP模型-----分支定界法

MINLP模型:MILP+NLP罚函数凑整智能化算法:遗传进化(GeneticAlgorithms)进化规划(EvolutionProgram)

鹰策略（EagleStrategy）群体智能(Swaarm

Intelligence）蚁群优化（AntColonyOpt

）粒子群优化算法（Particale

SwaarmOpt）差分进化（DifferentialEvolution)1.概述

遗传算法的概念最早是由BagleyJ.D在1967年提出的；而开始遗传算法的理论和方法的系统性研究的是1975年，这一开创性工作是由Michigan大学的J.H.Holland所实行。当时，其主要目的是说明自然和人工系统的自适应过程。

2.遗传算法的基本思想遗传算法的基本思想是基于Darwin进化论Mendel遗传学说

Darwin进化论最重要的是适者生存原理。它认为每一物种群体在发展中越来越适应环境。物种每个个体的基本特征由后代所继承，但后代又会产生一些异于父代的新变化。在环境变化时，只有那些能适应环境的个体特征方能保留下来。

鹿与长颈鹿：2.1Darwin进化论2.2Mendel的遗传学说Mendel遗传学说:该学说是最重要的是基因遗传原理，它认为遗传以密码方式存在细胞中，并以基因形式包含在染色体的DNA内（双螺旋结构）。每个基因有特殊的位置并控制某种特殊性质；所以，每个基因产生的个体对环境具有某种适应性。遗传与变异：基因杂交和基因突变可产生更适应于环境的后代。经过存优去劣的自然淘汰，适应性高的基因结构得以保存下来。3.遗传算法的基本概念

由于遗传算法是由进化论和遗传学机理而产生的直接搜索优化方法；故在这个算法中要用到各种遗传学和进化的概念。这些概念如下：串(String)群体(Population)群体大小(PopulationSize)基因(Gene)基因位置(GenePosition)基因特征值(GeneFeature)串结构空间SS参数空间SP非线性适应度(Fitness)交配（crossover）变异（mutation）3.1串(String)

它是个体(Individual)的形式,并且对应于遗传学中的染色体(Chromosome)。3.2群体(Population)

个体的集合称为群体，串是群体的元素。3.3群体大小(PopulationSize)

在群体中个体的数量称为群体的大小。

3.4基因(Gene)

基因是串中的元素，基因用于表示个体的特征。

例如：串S＝1011，则其中的1，0，1，1这4个元素分别称为基因。它们的值称为等位基因(Alletes)。3.5基因位置(GenePosition)

一个基因在串中的位置称为基因位置，有时也简称基因位。基因位置由串的左向右计算例如：在串S＝1101中，0的基因位置是3。基因位置对应于遗传学中的地点(Locus)。3.6基因特征值(GeneFeature)

在用串表示整数时，基因的特征值与二进制数的权一致；例如在串S=1011中，基因位置3中的1，它的基因特征值为2；基因位置1中的1，它的基因特征值为8。3.7串结构空间SS

在串中，基因任意组合所构成的串的集合。基因操作是在结构空间中进行的。串结构空间对应于遗传学中的基因型(Genotype)的集合。3.8参数空间SP

这是串空间在物理系统中的映射，它对于遗传学中的表现型(Phenotype)的集合。3.9非线性

它对应遗传学中的异位显性(Epistasis)。3.10适应度(Fitness)

表示某一个体对于环境的适应程度。3.11交配(Crossover）通过交配原则产生一组新串的过程。3.12变异(mutation）串的某一个分量发生变化的过程。4.遗传算法的原理遗传算法GA把问题的解表示成“染色体”，在算法中也即是以二进制编码的串。在执行遗传算法之前，给出一群“染色体”，也即是假设解。把这些假设解置于问题的“环境”中，并按适者生存的原则，从中选择出较适应环境的“染色体”进行复制，再通过交叉，变异过程产生更适应环境的新一代“染色体”群。这样，一代一代地进化，最后就会收敛到最适应环境的一个“染色体”上，它就是问题的最优解。5.遗传算法所解决的问题

典型的遗传算法CGA(CanonicalGeneticAlgorithm)通常用于解决下面这一类的静态最优化问题：

考虑对于一群长度为L的二进制编码bi（i＝1，2，…，n）；有

bi∈{0,1}L

给定目标函数f，有f(bi)，并且

0<f(bi)<∞同时

f(bi)≠f(bi+1)求满足下式

max{f(bi)|bi∈{0,1}L}的bi。

显然，遗传算法是一种最优化方法，它通过进化和遗传机理，从给出的原始解群中，不断进化产生新的解，最后收敛到一个特定的串bi处，即求出最优解。6.遗传算法的构成要素6.1选择(Selection)

这是从群体中选择出较适应环境的个体。这些选中的个体用于繁殖下一代。故有时也称这一操作为再生(Reproduction)。由于在选择用于繁殖下一代的个体时，是根据个体对环境的适应度而决定其繁殖量的，故而有时也称为非均匀再生(differentialreproduction)。6.2.交配(Crossover)

这是在选中用于繁殖下一代的个体中，对两个不同的个体的相同位置的基因进行交换，从而产生新的个体。

6.3.变异(Mutation)

这是在选中的个体中，对个体中的某些基因执行异向转化。在串bi中，如果某位基因为1，产生变异时就是把它变成0；反亦反之。7.遗传算法的步骤和意义7.1初始化7.2选择7.3交配7.4变异7.5全局最优收敛(Convergencetotheglobaloptimum)7.1.初始化选择一个群体，即选择一个串或个体的集合bi，i=1，2，...n。这个初始的群体也就是问题假设解的集合。一般取n＝30-160。通常以随机方法产生串或个体的集合bi,i＝1，2，...n。问题的最优解将通过这些初始假设解进化而求出。7.2.选择根据适者生存原则选择下一代的个体。在选择时，以适应度为选择原则。适应度准则体现了适者生存，不适应者淘汰的自然法则。给出目标函数f，则f(bi)称为个体bi的适应度。

为选中bi为下一代个体的次数。显然．从上式可知：(1)适应度较高的个体，繁殖下一代的数目较多。(2)适应度较小的个体，繁殖下一代的数目较少；

甚至被淘汰。这样，就产生了对环境适应能力较强的后代。对于问题求解角度来讲，就是选择出和最优解较接近的中间解7.3.交配

对于选中用于繁殖下一代的个体，随机地选择两个个体的相同位置，按交配概率pc

。在选中的位置实行交换。这个过程反映了随机信息交换；目的在于产生新的基因组合，也即产生新的个体。例如有个体S1=100101S2=010111选择它们的左边3位进行交配操作，则有S1=010101S2=100111一般而言，交配概率pc

。取值为0.25—0.75。7.4.变异根据生物遗传中基因变异的原理，以变异概率Pm对某些个体的某些位执行变异。在变异时，对执行变异的串的对应位求反，即把1变为0，把0变为1。变异概率Pm与生物变异极小的情况一致，所以，Pm的取值较小，一般取0.01-0.2。

例如有个体S＝101011。对其的第1，4位置的基因进行变异，则有S'=001111单靠变异不能在求解中得到好处。但是，它能保证算法过程不会产生无法进化的单一群体。因为在所有的个体一样时，交叉是无法产生新的个体的，这时只能靠变异产生新的个体。也就是说，变异增加了全局优化的特质。7.5.全局最优收敛(Convergencetotheglobaloptimum)当最优个体的适应度达到给定的阀值，或者最优个体的适应度和群体适应度不再上升时，则算法的迭代过程收敛、算法结束。否则，用经过选择、交叉、变异所得到的新一代群体取代上一代群体，并返回到第2步即选择操作处继续循环执行。此图表示了遗传算法的执行过程下面让我们看一个具体例子为四个连锁饭店寻找最好的经营决策，其中一个经营饭店的决策包括要做出以下三项决定：（1）价格汉堡包的价格应该定在50美分还是1美元？（2）饮料和汉堡包一起供应的应该是酒还是可乐？（3）服务速度饭店应该提供慢的还是快的服务？目的：找到这三个决定的组合以产生最高的利润。

饭店编号

价格

饮料

速度二进制表示1

高

可乐

快0112

高

酒

快0013

低

可乐

慢1104

高

可乐

慢010表1饭店问题的表示方案（其中的4个）

初始化

第0代i

串xi

适应值f（xi）10113200113110640102

总和12

最小值1

平均值3.00

最大值6表2初始群体中经营决策的适应值

第0代

交配池i

串xi适应值f（xi）f（xi）/f（xi）

串f（xi）101130.250113200110.081106311060.501106401020.170102

总和1217

最小值12

平均值3.004.25

最大值66选择

第0代

交配池

第1代i

串xi适应值f（xi）f（xi）/f（xi）

串f（xi）杂交点xif（xi）101130.25011320102200110.08110621117311060.501106

－1106401020.170102

－0102

总和121717最小值122平均值3.004.254.25最大值667交配

变异算子：以一个很小的概率pm随机改变染色体串上的某些位。对于二进制串，就是将相应位上的0变为1或将1变为0。

例如：选交配池中编号为4的串进行变异，且变异点在2，则

010000

变异算子相对而言，是次要算子，但在恢复群体中失去的多样性方面具有潜在的作用。例题小结述遗传算法描述了从第0代产生第1代的过程，然后遗传算法迭代地执行这个过程，直到满足某个停止准则。在每一代中，算法首先计算群体中每个个体地适应值，然后利用适应值信息，遗传算法分别以概率pc

、pr和pm

执行交配，选择和变异操作，从而产生新的群体。8.遗传算法应用中的关键问题8.1．串的编码方式8.2．适应函数的确定8.3．遗传算法自身参数设定8.1.串的编码方式这本质是问题编码。

①二进制编码（binaryencoding）采用0，1二进制进行编码其优点有使算法的三个算子构造比较简单，诸如前面简单遗传算法的交配，变异非常简单。对一些优化问题有其表示简单和直观的优越性。

问题的解是一个0-1向量，1表示装包，0表示不装。也是可以按照（x1,x2,……xn

）地取值形式形成一个自然编码。这样的编码很直观且易于遗传算法的应用。例如0-1背包问题

二进制编码的缺点：由于Hamming悬崖的存在，二进制编码对于函数的优化问题存在严重的缺陷。Hamming悬崖是指表现型空间中距离很小的的个体可能有很大的Hamming距离。举例说明，个体01111111和10000000属于表现型空间中的相邻点（最小Euclidean距离点），但他们却在基因型空间具有最大的Hamming距离。为了翻越Hamming悬崖，个体的所有位需要同时进行改变。有杂交和变异实现翻越Hamming悬崖的可能性极小。在这种情况下。二进制编码无法维持表现型空间中点的位置。②实数编码（real-numberencoding）实数编码对于函数优化问题最为有效。关于实数编码在函数优化和约束优化比二进制编码更有效的说法，已经得到广泛的验证。由于实数编码基因型空间中的拓扑结构与其表现型空间中的拓扑结构一致，因此很容易从传统优化方法中借鉴好的技巧来形成有效的遗传算子。③整数和字母排列编码

（literalpermutationencoding）整数和字母排列编码对于组合优化问题最为有效。由于组合优化问题最关键的是要寻找满足约束项目的最佳排列和组合，因此字母排列编码对于这类问题是最为有效的。对于更为复杂的现实问题，用合适的数据结构来表示基因的等位基因，可以有效抓住问题的本质。在这种情况下，基因可能是n维数组或更为复杂的数据结构。8.2.适应函数的确定（1)简单适应函数简单适应函数是目标函数的简单变形。若

f(x)为目标函数，适应函数的取法优化目标为最大时

fitness(x)=f(x)优化目标为最小时

fitness(x)=M-f(x),M>cmax

简单适应函数的的优点是构造简单,与目标函数直接相关。（2）非线性加速适应函数有时采用简单适应函数适应值改进的速度非常慢。可将适应函数同目标函数具有相同的变化趋势，但变化速度更快的适应函数进行替代。其构造方法为:其中M是一个充分大的数，fmax是当前的最优目标值。选取M的策略是；初始迭代时，M同第一大与第二大目标的差值的倒数尽量接近以避免早熟，后期迭代中逐步扩大差距。也可以在早期的迭代中用简单的适应函数，而后期用加速的方法。（3）线性加速适应函数

对非线性加速的思想进一步系统化得到线性加速适应函数。线型加速适应函数为:其中α、β按下方程确定：

其中所有的xi(i=1,2,……,m)为当前的代群中的染色体。上面第一个方程表示平均值变换后不变，第二个方程表示将当前最优值放大到平均值的M倍。选取M的策略是：

当目标群相差较大时，M不要过大，以便遗传的随机性；当遗传的一个群体目标值接近时，逐步扩大M。（4）排序适应函数将同一代群体中的m个染色体按目标函数知从小到大排列，重将这些染色体按目标值从小到大记为1至m。直接取分布概率为这样避开了对目标函数进行线性，非线性等加速适应函数的早熟可能，使每一代当前最好解以最大的概率2/（m+1）遗传3.遗传算法自身参数设定

遗传算法自身参数有3个，即群体大小n、交配概率Pc和变异概率Pm。群体大小n太小时难以求出最优解，太大则增长收敛时间。一般n＝30-160。交配概率Pc太小时难以向前搜索，太大则容易破坏高适应值的结构。一般取Pc=0.25-0.75。变异概率Pm太小时难以产生新的基因结构，太大使遗传算法成了单纯的随机搜索。一般取Pm＝0.01—0.2。9.遗传算法的数学理论

几个相关的定义：

1.模式——是一个相同的构形，它描述的是一个串的子集，这个集合中串之间在某些位上相同。例如，添加符号*表示不确定字母，即0或1，考虑串长为7的模式H＝*11*0**，则串A＝0111000是模式H的一个表示，对于基数为k的字母表，每一个串有（k＋1）l个模式

2.模式的阶—出现在模式中确定位置的数目。在二进制中，一个模式的阶就是所有的1或0的数目。例如:模式H＝*11*0**的阶为33.