智能技术课程课件

遗传算法（GeneticAlgorithm）

NaturalComputing1、算法起源2、基本术语和遗传算子3、模式定理4、遗传算法的应用11/17/2022智能技术课程－－叶东毅遗传算法（GeneticAlgorithm）

Natura1算法起源遗传算法（简称GA）的基本思想起源于生物体的遗传进化。生物的进化是发生在作为生物体结构编码的染色体上，染色体主要是由DNA和蛋白质组成，其中DNA又是最主要的遗传物质，它储存着遗传信息，可以准确地复制，也能够发生突变，并可通过控制蛋白质的合成而控制生物的性状。生物的遗传特性，使生物界的物种能够保持相对的稳定；生物的变异特性，使生物个体产生新的性状，以至于形成了新的物种，推动了生物的进化和发展。遗传算法正是模拟这一过程，通过向自然学习来求解问题。11/17/2022智能技术课程－－叶东毅算法起源遗传算法（简称GA）的基本思想起源于生物体的遗传进化2算法起源1975年，美国Michigan大学的Holland教授出版了系统论述遗传算法的第一本专著，标志着遗传算法的诞生。80年代，遗传算法得到了广泛应用与研究。1989年，D.J.Goldberg出版了他的著作，对遗传算法作了系统的阐述，确立了现代遗传算法的基础。

11/17/2022智能技术课程－－叶东毅算法起源1975年，美国Michigan大学的Holland3基本遗传算法是一种概率搜索算法，利用编码技术作用于称为染色体（chromosome）的二进制数串，模拟由这些串组成的群体的进化过程。类似于自然进化，遗传算法通过作用于染色体上的基因，寻找好的染色体来求解问题。遗传算法通过有组织的然而是随机的信息交换来重新结合那些适应性好的串。虽是一类随机算法，但又不是简单的随机走动，它可以有效利用已有的信息来搜寻那些有希望改善解质量的串。与自然界相似，遗传算法对求解问题本身一无所知，它所需要的仅是对算法所产生的每个染色体进行评价，并基于适应值来选择染色体，使适应性好的染色体比适应性差的染色体有更多的繁殖机会。11/17/2022智能技术课程－－叶东毅基本遗传算法是一种概率搜索算法，利用编码技术作用于称为染色体4基本术语和遗传算子定义1

将待解决问题的解变量用某种编码技术编制成特定形式的数字串，称这个数字串为染色体（chromosome）；数字串的每位数字码称为基因（gene）（基本GA中，采用二进制编码串），串的长度即为染色体的长度定义2

由一定数目的同等长度染色体组成的集合称为一个种群（population）；相应的染色体称为种群的一个个体（individual）定义3

根据拟定的函数对个体性质评价的一种度量，称为个体的适应值或适应度（fitness）11/17/2022智能技术课程－－叶东毅基本术语和遗传算子定义1将待解决问题的解变量用某种编码技术5基本术语和遗传算子定义4

对两个个体进行部分基因互换，产生两个新个体的操作，称为交叉或杂交运算（crossover）定义5

对个体的某些基因进行改变，产生新个体的操作，称作变异运算（mutation）定义6

从当前种群中选出优良的个体，使之有机会作为父代繁殖下一代的操作，称作选择运算（selection），或复制运算（reproduction）11/17/2022智能技术课程－－叶东毅基本术语和遗传算子定义4对两个个体进行部分基因互换，产6基本遗传算子：以二进制编码为例单点交叉:(随机投点）X=100110100;X’=010110100;Y=010111011；Y’=100111011；两点交叉：X=100110100;X’=010110011;Y=010111011；Y’=100111100；

或者X”=100111100;Y”=010110011；11/17/2022智能技术课程－－叶东毅基本遗传算子：以二进制编码为例单点交叉:(随机投点）11/7基本遗传算子：以二进制编码为例单点变异:(随机投点）X=100110100;X’=101110100;Y=010111011；Y’=110111011；多点变异：X=100110100;X’=110100101;Y=010111011；Y’=100111111；

11/17/2022智能技术课程－－叶东毅基本遗传算子：以二进制编码为例单点变异:(随机投点）11/8基本遗传算子：以二进制编码为例个体选择复制:(赌轮原则）设种群规模为4个体fitness概率选择选择X111/12X2X1X221/6X3X3X331/4X4X3X461/2X4X4X4X3X2X1RouletteWheelSelection11/17/2022智能技术课程－－叶东毅基本遗传算子：以二进制编码为例个体选择复制:(赌轮原则）个9标准遗传算法（SGA）

考虑全局优化问题（P）max{f(x)：x∈DRn→R1}遗传算法基于以下两条基本策略求解问题（P）：（a）对于给定的目标函数f，它使用f的任一适应值函数（换言之，一个值域非负、与f有相同极点的函数）；（b）它不直接作用于实向量x，而是作用于x的某种编码（最常见的为定长二进制数串编码）。所以，对于取定f的任一适应值函数F和固定长度为L的二进制数串编码，遗传算法实质上是通过求解组合优化问题

（P’）max{F(x)：x∈S}来求解问题（P）的，这里S={0，1}L为D的编码空间（即D中所有实变量的长度为L的二进制数串编码全体）。11/17/2022智能技术课程－－叶东毅标准遗传算法（SGA）11/10/2022智能技术课程－－叶10Step1

初始化：1.1指定种群规模N，杂交概率Pc

，变异概率Pm及终止进化准则；1.2随机生成初始种群X(0)=(X1(0)，X2(0)，…，XN(0))∈SN，置k=0。Step2种群进化：2.1（选择）依据Xi(k)的适应值，随机、独立、重复地从X(k)中选取N个个体为母体；2.2（交叉）依概率Pc独立地对所选N个母体执行杂交，以产生新的N个中间个体；2.3（变异）依概率Pm独立地对交叉生成的N个中间个体执行变异，从而生成新一代种群X(k+1)=(X1(k+1)，X2(k+1)，…，XN(k+1))11/17/2022智能技术课程－－叶东毅Step1初始化：11/10/2022智能技术课程－－叶11Step3

终止检验：如果X（k+1）已满足预设的进化终止原则，则停止；否则，置k=k+1，转Step2。常见的终止条件有：1、,其中δ为给定的常数，与具体问题的求解精度有关；2、整个群体仅由某个个体生成；3、进化次数超过预定的值。

11/17/2022智能技术课程－－叶东毅Step3终止检验：11/10/2022智能技术课程－－12常见的选择机制1.

赌轮选择（roulettewheelselection）；2.最佳保留（elitistmodel）；3．期望值模型（expectedvaluemodel）选择机制;

在该模型选择机制中，先按期望值Q的整数部分安排个体被选中的次数，而对期望值Q的小数部分可按下述几种方式进行处理：（1）

确定方式;（2）

赌轮方式;（3）

贝努利试验（BernoulliTrials）方式11/17/2022智能技术课程－－叶东毅常见的选择机制1.赌轮选择（roulettewheel13遗传算法的改进——精英策略采用精英策略(优、劣解同时保留)的遗传算法是保持当前一个最好解和最差解；最好解(thefittest)不参与交叉和变异操作；最差解不参加交叉操作，但参加变异操作；11/17/2022智能技术课程－－叶东毅遗传算法的改进——精英策略采用精英策略(优、劣解同时保留)的14Step1初始化：随机产生一个规模为N的初始种群，其中每个个体为二进制位串的形式。Step2

计算适应值并按序排列：计算种群中每个个体的适应值，并把个体按适应值从小到大排列。Step3

选择：把适应值最大、最小的个体按1:1选择，另外的N-2个个体根据每个个体的相对适应值，计算每个个体被选择的概率，进行选择操作。Step4

交叉：从上述选择后的种群中，除了最优、最差两个个体外，随机选择两个染色体，按一定的交叉概率Pc进行基因变换，交换的位置随机选取。Step5

变异：从种群中，除了最优、最差两个个体外，随机选择一个染色体，按一定的变异概率Pm进行基因变异；对最差的个体按增大后的变异概率kPm(k取10-20)进行基因变异。Step6

若达到预设的进化代数，则算法停止，否则，转Step2.11/17/2022智能技术课程－－叶东毅Step1初始化：随机产生一个规模为N的初始种群，其中每个15模式定理定义：

基于三值字符集{0，1，*}所产生的能描述具有某些结构相似性的0、1字符串集的字符串称作模式。模式是二值符号串的一种扩展，其中基因的取值可为0，1或*。符号“*”称作“无关符”，表示一种随意的情况，也就是说基因的取值可以是1也可以是0。例如（*01*00）、（******）和（100101）都是长为6位的二值符号串的模式。11/17/2022智能技术课程－－叶东毅模式定理定义：基于三值字符集{0，1，*}所产生的能描述16包含个体与隐含模式如果一个个体X符合模式H，就称X属于H，或H包含X。如：H=10*0**;包含：101011,100001,…,给定一个个体X,如果X属于模式H，也称H为X隐含的模式。如：X=101011,它隐含的模式有H1=1*****,H2=*01**1,H3=10**11,…,11/17/2022智能技术课程－－叶东毅包含个体与隐含模式如果一个个体X符合模式H，就称X属于H，或17定义：

模式H中确定位置的个数称作该模式的模式阶，记作O(H)。比如模式011*0*的阶是4，而模式0*****为1。显然一个模式的阶数越高，其包含的样本数就越少，因而确定性也就越高。定义：

模式H中第一个确定位置和最后一个确定位置之间的距离称作该模式的定义距，记作δ(H)。比如模式011*1*的定义距是4，而模式0*****的定义距为0。11/17/2022智能技术课程－－叶东毅定义：模式H中确定位置的个数称作该模式的模式阶，记作O(H18模式阶和定义距描述了模式的基本性质。下面讨论模式在遗传操作下的变化。令A(t)表示第t代中串的群体，以Aj(j=1,2,···,n)表示一代中第j个个体串。1、选择操作对模式的作用假设在t代，群体A(t)中模式H所包含的个体数为m(H，t)。在选择运算中，一个串是根据其适应度进行复制的。即以概率Pi=fi/(∑fj）进行选择的，其中fi是个体Ai(t)适应度。则模式H在第t+1代中包含的个体数为（从概率角度）其中，f(H),f(t)分别是模式H（在A(t)中）和群体A(t)的适应度平均值。11/17/2022智能技术课程－－叶东毅模式阶和定义距描述了模式的基本性质。下面讨论模式在遗传操作19可见，模式的增长（减少）依赖于模式的平均适应度与群体平均适应度之比：那些平均适应度高于群体平均适应度的模式将在下一代中增长；而那些平均适应度低于群体平均适应度的模式将在下一代中减少。现在，假定模式H的平均适应度一直高于群体平均适应度(设至少为1+c倍），c为正的常数，则有即，在选择算子作用下，平均适应度高于群体平均适应度的模式将呈指数级增长；而低于群体平均适应度的模式将呈指数级减少。11/17/2022智能技术课程－－叶东毅可见，模式的增长（减少）依赖于模式的平均适应度与群体平均适应202．模式在交叉算子作用下的变化考虑一个长度为6的串以及隐含其中的两个模式：A=010110

H1=*1***0H2

=***11*

假定A被选中进行交叉，不妨设交叉点为3，即A=010110H1=*1***0H2=***11*11/17/2022智能技术课程－－叶东毅2．模式在交叉算子作用下的变化11/10/2022智能技术课21模式在交叉算子作用下的变化A=010110B=101001A’=101110B’=010001H1=*1***0

H2=***11*显然，H1被破坏，而H2依然存在11/17/2022智能技术课程－－叶东毅模式在交叉算子作用下的变化11/10/2022智能技术课程－22模式H1的定义距为4，那么交叉点在l

－1=5个位置上随机产生时，H1遭到破坏的概率是Pd=δ(H1)/(l－1)=4/5，换句话说，其生存概率为1/5；模式H2的定义距是1，则H2遭破坏的概率是

Pd=δ(H2

)/(l－1)=1/5，即生存概率是4/5。一般地讲，当交叉点落在定义距之外时，模式H才能生存。在简单交叉（单点交叉）下的H的生存概率Ps=1－δ(H)/(l－1)11/17/2022智能技术课程－－叶东毅模式H1的定义距为4，那么交叉点在l－1=5个位置上随机产23由于交叉本身也是以一定的概率Pc发生的，所以模式H的生存概率为如果与A进行交叉的串在位置2，6上有一位与A相同，则H1将被保留。因此，以上公式只是生存概率的一个下界，即有：这个公式描述了模式在交叉算子作用下的生存概率。如果考虑模式H在选择和交叉算子的共同作用下的变化。则有11/17/2022智能技术课程－－叶东毅由于交叉本身也是以一定的概率Pc发生的，所以模式H的生存概率243．模式在变异算子作用下的变化

考虑变异操作。串的某一位置发生改变的概率为Pm，故该位置不变的概率为1－Pm，而模式H在变异运算作用下若要不受破坏，则其中所有的确定位置必须保持不变。因此模式H保持不变的概率为其中O(H)为模式H的阶数。当Pm<<1时，模式H在变异算子作用下的生存概率为11/17/2022智能技术课程－－叶东毅3．模式在变异算子作用下的变化11/10/2022智能技术课25综合三种算子对模式H的影响，有如下的生存概率估计：模式定理在遗传算子选择、交叉和变异的作用下，具有低阶、短定义距以及平均适应度高于群体平均适应度的模式在子代中将得以(指数级)增长。

结论：在一定前提下，遗传算法以概率为1收敛到全局最优解！11/17/2022智能技术课程－－叶东毅综合三种算子对模式H的影响，有如下的生存概率估计：模式定理126遗传算法的应用染色体编码：视具体问题而定，可以整数序列串，也可以实数序列。适应值函数的定义，如何评估？交叉算子的本质：保持父代基因段或信息；变异算子的本质：新解的实质多样性；如何定义这2个演化算子，使之保持解的可行性？（特别是约束情况下？）参数设定问题。11/17/2022智能技术课程－－叶东毅遗传算法的应用染色体编码：视具体问题而定，可以整数序列串，也27SAT问题（无约束）F(x)：布尔变量x=(x1,…,xn)的合取范式.问题：找到x=(x1,…,xn)的一个真值指派，使得F(x)=TRUE(or1).例如：F(x)=（x1x3）（x2x5x6）（

x4x5）取x=(1,0,0,0,0,1)，则F(x)=0；取x=(1,0,0,0,0,0)，则F(x)=1；求得一个解！11/17/2022智能技术课程－－叶东毅SAT问题（无约束）F(x)：布尔变量x=(x1,…28编码和适应值函数二进制编码：直接用原问题的变量编码；适应值：直接采用问题的目标函数F(x)?要么F(x)=1，找到解；要么F(x)=0，此时，如何区别不同个体的质量呢？如何引导选择过程呢？适应值函数的合理确定问题！！F(x)=

f1(x)

f2(x)…fp(x);fi(x)为析取项;适应值函数：Q(x)=Boolean(fi(x))；0Q(x)p如果Q(x)=p,则x为一个解；可以有其他（可能更好）的方式定义适应值函数。11/17/2022智能技术课程－－叶东毅编码和适应值函数二进制编码：直接用原问题的变量编码；F(x)29对称全通路TSP问题（含约束）城市编号（顶点）序列为染色体（整数编码）：X=123…n的某一个排列，这样最自然！如何定义交叉、变异呢？简单交换或变异导致不可行的解：12435+23154=12154+23435

适应值函数：距离总和。采用二进制编码？按照边，但是需要判断顶点集合的重叠性。同时，边数远远多于顶点数。另外，面临演化算子的设计问题。不合适！11/17/2022智能技术课程－－叶东毅对称全通路TSP问题（含约束）城市编号（顶点）序列为染色体（30X=123456789;Y=324695781X’=123456798

Y’=324691

7581、基于次序的交叉：在父代随机选取一组位置，强加到另一个上2、基于位置的交叉：X=123456789;Y=324695781X’=312495687；Y’17/2022智能技术课程－－叶东毅X=123456789;Y=31X=123456789;4：7，5：9，6：8Y=324798651X’=123798465Y’=3274568913、部分映射交叉：在父代随机选取一组位置，段内元对应对交换变异算子：1、随机选2个元素，将第二元置于第一元之前；X=123456789，X’=1245367892、随机选2个元素，交换位置；X=123456789，X’=12645378911/17/2022智能技术课程－－叶东毅X=123456789;432图着色问题（混合算法）

---贪心+遗传给定每个顶点具有加权的图和n种颜色,图着色问题：从n种颜色的集合中选择一种颜色到任一个顶点上，但要满足任何一条边关联的一对顶点不具有相同的颜色。未着色的顶点为无色的。着色顶点的加权总和为着色方案的分数。求具有最高分数的着色方案。这是NP-完全问题。11/17/2022智能技术课程－－叶东毅图着色问题（混合算法）

---贪心+遗33贪心策略按照加权大小顺序对顶点排序；按照该顺序取每个顶点，并为其指定它能够具有的第一个合法颜色。该算法速度快，有时可以获得最优解。11/17/2022智能技术课程－－叶东毅贪心策略按照加权大小顺序对顶点排序；11/10/2022智能347-362-83-144-131-126-105-911/17/2022智能技术课程－－叶东毅7-362-83-144-131-126-105-911/1357-362-83-144-131-126-105-9n

=1,Score=36;Bestsolution!Greedyideawins!11/17/2022智能技术课程－－叶东毅7-362-83-144-131-126-105-9n=1367-152-83-144-131-126-105-911/17/2022智能技术课程－－叶东毅7-152-83-144-131-126-105-911/1377-152-83-144-131-126-105-9n

=1,Score=15;Notbest!Greedyideafails!11/17/2022智能技术课程－－叶东毅7-152-83-144-131-126-105-9n=1387-152-83-144-131-126-105-9n

=1,Score=35;Best!11/17/2022智能技术课程－－叶东毅7-152-83-144-131-126-105-9n=1397-152-83-144-131-126-105-9n

=2,Score=66;Best!11/17/2022智能技术课程－－叶东毅7-152-83-144-131-126-105-9n=2407-152-83-144-131-126-105-9n

=3,Score=81;Best!Again,greedyideawins!11/17/2022智能技术课程－－叶东毅7-152-83-144-131-126-105-9n=341混合遗传算法编码：有序顶点序列（整数串）适应值函数：依照贪心策略，对给定的顶点序列进行着色，求出相应的分数作为适应值；应用遗传算法进行演化，每得到新的一代，都按照贪心策略产生相应的着色方案，直至找到一个满意的着色方案。杂交算子和变异算子可以类似TSP问题那样设计。11/17/2022智能技术课程－－叶东毅混合遗传算法编码：有序顶点序列（整数串）11/10/20224211/17/2022智能技术课程－－叶东毅11/10/2022智能技术课程－－叶东毅43遗传算法（GeneticAlgorithm）

NaturalComputing1、算法起源2、基本术语和遗传算子3、模式定理4、遗传算法的应用11/17/2022智能技术课程－－叶东毅遗传算法（GeneticAlgorithm）

Natura44算法起源遗传算法（简称GA）的基本思想起源于生物体的遗传进化。生物的进化是发生在作为生物体结构编码的染色体上，染色体主要是由DNA和蛋白质组成，其中DNA又是最主要的遗传物质，它储存着遗传信息，可以准确地复制，也能够发生突变，并可通过控制蛋白质的合成而控制生物的性状。生物的遗传特性，使生物界的物种能够保持相对的稳定；生物的变异特性，使生物个体产生新的性状，以至于形成了新的物种，推动了生物的进化和发展。遗传算法正是模拟这一过程，通过向自然学习来求解问题。11/17/2022智能技术课程－－叶东毅算法起源遗传算法（简称GA）的基本思想起源于生物体的遗传进化45算法起源1975年，美国Michigan大学的Holland教授出版了系统论述遗传算法的第一本专著，标志着遗传算法的诞生。80年代，遗传算法得到了广泛应用与研究。1989年，D.J.Goldberg出版了他的著作，对遗传算法作了系统的阐述，确立了现代遗传算法的基础。

11/17/2022智能技术课程－－叶东毅算法起源1975年，美国Michigan大学的Holland46基本遗传算法是一种概率搜索算法，利用编码技术作用于称为染色体（chromosome）的二进制数串，模拟由这些串组成的群体的进化过程。类似于自然进化，遗传算法通过作用于染色体上的基因，寻找好的染色体来求解问题。遗传算法通过有组织的然而是随机的信息交换来重新结合那些适应性好的串。虽是一类随机算法，但又不是简单的随机走动，它可以有效利用已有的信息来搜寻那些有希望改善解质量的串。与自然界相似，遗传算法对求解问题本身一无所知，它所需要的仅是对算法所产生的每个染色体进行评价，并基于适应值来选择染色体，使适应性好的染色体比适应性差的染色体有更多的繁殖机会。11/17/2022智能技术课程－－叶东毅基本遗传算法是一种概率搜索算法，利用编码技术作用于称为染色体47基本术语和遗传算子定义1

将待解决问题的解变量用某种编码技术编制成特定形式的数字串，称这个数字串为染色体（chromosome）；数字串的每位数字码称为基因（gene）（基本GA中，采用二进制编码串），串的长度即为染色体的长度定义2

由一定数目的同等长度染色体组成的集合称为一个种群（population）；相应的染色体称为种群的一个个体（individual）定义3

根据拟定的函数对个体性质评价的一种度量，称为个体的适应值或适应度（fitness）11/17/2022智能技术课程－－叶东毅基本术语和遗传算子定义1将待解决问题的解变量用某种编码技术48基本术语和遗传算子定义4

对两个个体进行部分基因互换，产生两个新个体的操作，称为交叉或杂交运算（crossover）定义5

对个体的某些基因进行改变，产生新个体的操作，称作变异运算（mutation）定义6

从当前种群中选出优良的个体，使之有机会作为父代繁殖下一代的操作，称作选择运算（selection），或复制运算（reproduction）11/17/2022智能技术课程－－叶东毅基本术语和遗传算子定义4对两个个体进行部分基因互换，产49基本遗传算子：以二进制编码为例单点交叉:(随机投点）X=100110100;X’=010110100;Y=010111011；Y’=100111011；两点交叉：X=100110100;X’=010110011;Y=010111011；Y’=100111100；

或者X”=100111100;Y”=010110011；11/17/2022智能技术课程－－叶东毅基本遗传算子：以二进制编码为例单点交叉:(随机投点）11/50基本遗传算子：以二进制编码为例单点变异:(随机投点）X=100110100;X’=101110100;Y=010111011；Y’=110111011；多点变异：X=100110100;X’=110100101;Y=010111011；Y’=100111111；

11/17/2022智能技术课程－－叶东毅基本遗传算子：以二进制编码为例单点变异:(随机投点）11/51基本遗传算子：以二进制编码为例个体选择复制:(赌轮原则）设种群规模为4个体fitness概率选择选择X111/12X2X1X221/6X3X3X331/4X4X3X461/2X4X4X4X3X2X1RouletteWheelSelection11/17/2022智能技术课程－－叶东毅基本遗传算子：以二进制编码为例个体选择复制:(赌轮原则）个52标准遗传算法（SGA）

考虑全局优化问题（P）max{f(x)：x∈DRn→R1}遗传算法基于以下两条基本策略求解问题（P）：（a）对于给定的目标函数f，它使用f的任一适应值函数（换言之，一个值域非负、与f有相同极点的函数）；（b）它不直接作用于实向量x，而是作用于x的某种编码（最常见的为定长二进制数串编码）。所以，对于取定f的任一适应值函数F和固定长度为L的二进制数串编码，遗传算法实质上是通过求解组合优化问题

（P’）max{F(x)：x∈S}来求解问题（P）的，这里S={0，1}L为D的编码空间（即D中所有实变量的长度为L的二进制数串编码全体）。11/17/2022智能技术课程－－叶东毅标准遗传算法（SGA）11/10/2022智能技术课程－－叶53Step1

初始化：1.1指定种群规模N，杂交概率Pc

，变异概率Pm及终止进化准则；1.2随机生成初始种群X(0)=(X1(0)，X2(0)，…，XN(0))∈SN，置k=0。Step2种群进化：2.1（选择）依据Xi(k)的适应值，随机、独立、重复地从X(k)中选取N个个体为母体；2.2（交叉）依概率Pc独立地对所选N个母体执行杂交，以产生新的N个中间个体；2.3（变异）依概率Pm独立地对交叉生成的N个中间个体执行变异，从而生成新一代种群X(k+1)=(X1(k+1)，X2(k+1)，…，XN(k+1))11/17/2022智能技术课程－－叶东毅Step1初始化：11/10/2022智能技术课程－－叶54Step3

终止检验：如果X（k+1）已满足预设的进化终止原则，则停止；否则，置k=k+1，转Step2。常见的终止条件有：1、,其中δ为给定的常数，与具体问题的求解精度有关；2、整个群体仅由某个个体生成；3、进化次数超过预定的值。

11/17/2022智能技术课程－－叶东毅Step3终止检验：11/10/2022智能技术课程－－55常见的选择机制1.

赌轮选择（roulettewheelselection）；2.最佳保留（elitistmodel）；3．期望值模型（expectedvaluemodel）选择机制;

在该模型选择机制中，先按期望值Q的整数部分安排个体被选中的次数，而对期望值Q的小数部分可按下述几种方式进行处理：（1）

确定方式;（2）

赌轮方式;（3）

贝努利试验（BernoulliTrials）方式11/17/2022智能技术课程－－叶东毅常见的选择机制1.赌轮选择（roulettewheel56遗传算法的改进——精英策略采用精英策略(优、劣解同时保留)的遗传算法是保持当前一个最好解和最差解；最好解(thefittest)不参与交叉和变异操作；最差解不参加交叉操作，但参加变异操作；11/17/2022智能技术课程－－叶东毅遗传算法的改进——精英策略采用精英策略(优、劣解同时保留)的57Step1初始化：随机产生一个规模为N的初始种群，其中每个个体为二进制位串的形式。Step2

计算适应值并按序排列：计算种群中每个个体的适应值，并把个体按适应值从小到大排列。Step3

选择：把适应值最大、最小的个体按1:1选择，另外的N-2个个体根据每个个体的相对适应值，计算每个个体被选择的概率，进行选择操作。Step4

交叉：从上述选择后的种群中，除了最优、最差两个个体外，随机选择两个染色体，按一定的交叉概率Pc进行基因变换，交换的位置随机选取。Step5

变异：从种群中，除了最优、最差两个个体外，随机选择一个染色体，按一定的变异概率Pm进行基因变异；对最差的个体按增大后的变异概率kPm(k取10-20)进行基因变异。Step6

若达到预设的进化代数，则算法停止，否则，转Step2.11/17/2022智能技术课程－－叶东毅Step1初始化：随机产生一个规模为N的初始种群，其中每个58模式定理定义：

基于三值字符集{0，1，*}所产生的能描述具有某些结构相似性的0、1字符串集的字符串称作模式。模式是二值符号串的一种扩展，其中基因的取值可为0，1或*。符号“*”称作“无关符”，表示一种随意的情况，也就是说基因的取值可以是1也可以是0。例如（*01*00）、（******）和（100101）都是长为6位的二值符号串的模式。11/17/2022智能技术课程－－叶东毅模式定理定义：基于三值字符集{0，1，*}所产生的能描述59包含个体与隐含模式如果一个个体X符合模式H，就称X属于H，或H包含X。如：H=10*0**;包含：101011,100001,…,给定一个个体X,如果X属于模式H，也称H为X隐含的模式。如：X=101011,它隐含的模式有H1=1*****,H2=*01**1,H3=10**11,…,11/17/2022智能技术课程－－叶东毅包含个体与隐含模式如果一个个体X符合模式H，就称X属于H，或60定义：

模式H中确定位置的个数称作该模式的模式阶，记作O(H)。比如模式011*0*的阶是4，而模式0*****为1。显然一个模式的阶数越高，其包含的样本数就越少，因而确定性也就越高。定义：

模式H中第一个确定位置和最后一个确定位置之间的距离称作该模式的定义距，记作δ(H)。比如模式011*1*的定义距是4，而模式0*****的定义距为0。11/17/2022智能技术课程－－叶东毅定义：模式H中确定位置的个数称作该模式的模式阶，记作O(H61模式阶和定义距描述了模式的基本性质。下面讨论模式在遗传操作下的变化。令A(t)表示第t代中串的群体，以Aj(j=1,2,···,n)表示一代中第j个个体串。1、选择操作对模式的作用假设在t代，群体A(t)中模式H所包含的个体数为m(H，t)。在选择运算中，一个串是根据其适应度进行复制的。即以概率Pi=fi/(∑fj）进行选择的，其中fi是个体Ai(t)适应度。则模式H在第t+1代中包含的个体数为（从概率角度）其中，f(H),f(t)分别是模式H（在A(t)中）和群体A(t)的适应度平均值。11/17/2022智能技术课程－－叶东毅模式阶和定义距描述了模式的基本性质。下面讨论模式在遗传操作62可见，模式的增长（减少）依赖于模式的平均适应度与群体平均适应度之比：那些平均适应度高于群体平均适应度的模式将在下一代中增长；而那些平均适应度低于群体平均适应度的模式将在下一代中减少。现在，假定模式H的平均适应度一直高于群体平均适应度(设至少为1+c倍），c为正的常数，则有即，在选择算子作用下，平均适应度高于群体平均适应度的模式将呈指数级增长；而低于群体平均适应度的模式将呈指数级减少。11/17/2022智能技术课程－－叶东毅可见，模式的增长（减少）依赖于模式的平均适应度与群体平均适应632．模式在交叉算子作用下的变化考虑一个长度为6的串以及隐含其中的两个模式：A=010110

H1=*1***0H2

=***11*

假定A被选中进行交叉，不妨设交叉点为3，即A=010110H1=*1***0H2=***11*11/17/2022智能技术课程－－叶东毅2．模式在交叉算子作用下的变化11/10/2022智能技术课64模式在交叉算子作用下的变化A=010110B=101001A’=101110B’=010001H1=*1***0

H2=***11*显然，H1被破坏，而H2依然存在11/17/2022智能技术课程－－叶东毅模式在交叉算子作用下的变化11/10/2022智能技术课程－65模式H1的定义距为4，那么交叉点在l

－1=5个位置上随机产生时，H1遭到破坏的概率是Pd=δ(H1)/(l－1)=4/5，换句话说，其生存概率为1/5；模式H2的定义距是1，则H2遭破坏的概率是

Pd=δ(H2

)/(l－1)=1/5，即生存概率是4/5。一般地讲，当交叉点落在定义距之外时，模式H才能生存。在简单交叉（单点交叉）下的H的生存概率Ps=1－δ(H)/(l－1)11/17/2022智能技术课程－－叶东毅模式H1的定义距为4，那么交叉点在l－1=5个位置上随机产66由于交叉本身也是以一定的概率Pc发生的，所以模式H的生存概率为如果与A进行交叉的串在位置2，6上有一位与A相同，则H1将被保留。因此，以上公式只是生存概率的一个下界，即有：这个公式描述了模式在交叉算子作用下的生存概率。如果考虑模式H在选择和交叉算子的共同作用下的变化。则有11/17/2022智能技术课程－－叶东毅由于交叉本身也是以一定的概率Pc发生的，所以模式H的生存概率673．模式在变异算子作用下的变化

考虑变异操作。串的某一位置发生改变的概率为Pm，故该位置不变的概率为1－Pm，而模式H在变异运算作用下若要不受破坏，则其中所有的确定位置必须保持不变。因此模式H保持不变的概率为其中O(H)为模式H的阶数。当Pm<<1时，模式H在变异算子作用下的生存概率为11/17/2022智能技术课程－－叶东毅3．模式在变异算子作用下的变化11/10/2022智能技术课68综合三种算子对模式H的影响，有如下的生存概率估计：模式定理在遗传算子选择、交叉和变异的作用下，具有低阶、短定义距以及平均适应度高于群体平均适应度的模式在子代中将得以(指数级)增长。

结论：在一定前提下，遗传算法以概率为1收敛到全局最优解！11/17/2022智能技术课程－－叶东毅综合三种算子对模式H的影响，有如下的生存概率估计：模式定理169遗传算法的应用染色体编码：视具体问题而定，可以整数序列串，也可以实数序列。适应值函数的定义，如何评估？交叉算子的本质：保持父代基因段或信息；变异算子的本质：新解的实质多样性；如何定义这2个演化算子，使之保持解的可行性？（特别是约束情况下？）参数设定问题。11/17/2022智能技术课程－－叶东毅遗传算法的应用染色体编码：视具体问题而定，可以整数序列串，也70SAT问题（无约束）F(x)：布尔变量x=(x1,…,xn)的合取范式.问题：找到x=(x1,…,xn)的一个真值指派，使得F(x)=TRUE(or1).例如：F(x)=（x1x3）（x2x5x6）（

x4x5）取x=(1,0,0,0,0,1)，则F(x)=0；取x=(1,0,0,0,0,0)，则F(x)=1；求得一个解！11/17/2022智能技术课程－－叶东毅SAT问题（无约束）F(x)：布尔变量x=(x1,…71编码和适应值函数二进制编码：直接用原问题的变量编码；适应值：直接采用问题的目标函数F(x)?要么F(x)=1，找到解；要么F(x)=0，此时，如何区别不同个体的质量呢？如何引导选择过程呢？适应值函数的合理确定问题！！F(x)=

f1(x)

f2(x)…fp(x);fi(x)为析取项;适应值函数：Q(x)=Boolean(fi(x))；0Q(x)p如果Q(x)=p,则x为一个解；可以有其他（可能更好）的方式定义适应值函数。11/17/2022智能技术课程－－叶东毅编码和适应值函数二进制编码：直接用原问题的变量编码；F(x)72对称全通路TSP问题（含约束）城市编号（顶点）序列为染色体（整数编码）：X=123…n的某一个排列，这样最自然！如何定义交叉、变异呢？简单交换或变异导致不可行的解：12435+23154=12154+23435

适应值函数：距离总和。采用二进制编码？按照边，但是需要判断顶点集合的重叠性。同时，边数远远多于顶点数。另外，面临演化