GA-遗传算法简介概述课件

遗传算法GeneticAlgorithm遗传算法GeneticAlgorithm主要内容一、遗传算法概述二、遗传算法的基本操作三、遗传算法原理四、遗传算法的应用主要内容一、遗传算法概述现代智能优化算法遗传算法禁忌算法蚁群算法粒子群算法细菌算法混沌算法TSGAACOPSOBCCOA自由搜索算法FS现代智能优化算法遗禁蚁粒细混TSGAACOPSOBCCOA自1、遗传算法起源

遗传算法(GeneticAlgorithm,GA)是由美国的J.Holland教授于1975年在他的专著《自然界和人工系统的适应性》中首先提出的，它是一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法。GA来源于达尔文的进化论、魏茨曼的物种选择学说和孟德尔的群体遗传学说。其基本思想是模拟自然界遗传机制和生物进化论而形成的一种过程搜索全局最优解的算法。一、遗传算法概述1、遗传算法起源遗传算法(Gene2、生物进化理论和遗传学基本知识

一、遗传算法概述(1)达尔文的自然选择说遗传（heredity）：

子代和父代具有相同或相似的性状，保证物种的稳定性变异（variation）：

子代与父代,子代不同个体之间总有差异，是生命多样性的根源生存斗争和适者生存：

具有适应性变异的个体被保留，不具适应性变异的个体被淘汰2、生物进化理论和遗传学基本知识一、遗传算法概述(1)达一、遗传算法概述2、生物进化理论和遗传学基本知识

(2)遗传学基本概念和术语基因(gene)：染色体的一个片段染色体(Chromosome)：问题中个体的某种字符串形式的编码表示种群(Population)：个体的集合,该集合内的个体数称为种群的大小基因型(genetype)：基因组合的模型，染色体的内部表现表现型(phenotype)：染色体决定性状的外部表现111

1

111

111

0

111个体染色体9----1001一、遗传算法概述2、生物进化理论和遗传学基本知识(2)遗一、遗传算法概述2、生物进化理论和遗传学基本知识

(2)遗传学基本概念和术语进化(evolution)：个体逐渐适应生存环境，不断改良品质的过程适应度(fitness)：反映个体性能的一个数量值编码(coding)：从表现型到基因型的映射解码(decoding)：从基因型到表现性的映射适应度函数(fitnessfunction):

问题中的全体个体与其适应度之间的一个对应关系,一般是一个实值函数。该函数就是遗传算法中指导搜索的评价函数。一、遗传算法概述2、生物进化理论和遗传学基本知识(2)遗1选择-复制(selection-reproduction)二、遗传算法的基本操作选择-复制指的就是以一定的概率从种群中选择若干个体并进行复制的操作轮盘赌选择（roulettewheelselection）随机遍历抽样（stochasticuniversalselection）局部选择（localselection）截断选择（truncationselection）锦标赛选择（tournamentselection）

选择概率P(xi)的计算公式为:常用选择-复制方法：按比例的适应度分配方法1选择-复制(selection-reproduction1选择-复制(selection-reproduction)二、遗传算法的基本操作例：轮盘赌选择

解(1)计算选择概率和累计概率

个体染色体适应度选择概率累计概率1000110000080.0869570.0869572010111100150.0543480.1413043000000010120.0217390.16304341001110100100.1086960.2717395101010101070.0760870.34782661110010110120.1304350.4782617100101101150.0543480.53260981100000001190.2065220.73913091001110100100.1086960.847826100001010011140.1521741.0000001选择-复制(selection-reproduction1选择-复制(selection-reproduction)二、遗传算法的基本操作个体染色体适应度选择概率累计概率1000110000080.0869570.0869572010111100150.0543480.1413043000000010120.0217390.16304341001110100100.1086960.2717395101010101070.0760870.34782661110010110120.1304350.4782617100101101150.0543480.53260981100000001190.2065220.73913091001110100100.1086960.847826100001010011140.1521741.000000复制操作能从旧种群中选择出优秀者，但不能创造新的染色体！(2)在0-1之间产生一个随机数

0.50789360.07022110.54592980.78456790.44693060.29119850.71634080.27190140.37143560.85464110淘汰1选择-复制(selection-reproduction2交叉(crossover)——基因重组二、遗传算法的基本操作

交叉就是互换两个染色体某些位上的基因

s1′=01000101,s2′=10011011可以看做是原染色体s1和s2的子代染色体

例：设染色体s1=01001011,s2=10010101,交换其后4位基因,即单点交叉2交叉(crossover)——基因重组二、遗传算法的基本2交叉(crossover)——基因重组二、遗传算法的基本操作

其它常用的交叉方法：

多点交叉（multiple-pointcrossover）均匀交叉（uniformcrossover）部分匹配交叉（PartiallyMatchedCrossover）顺序交叉（OrderedCrossover）循环交叉（CycleCrossover）交叉模拟了生物进化过程中的繁殖现象，通过两个染色体的交换组合，来产生新的优良品种！2交叉(crossover)——基因重组二、遗传算法的基本3变异(mutation)变异就是改变染色体某个(些)位上的基因例如，设染色体s=11001101，将其第三位上的0变为1,即

s=11001101→11101101=s′。

s′也可以看做是原染色体s的子代染色体变异运算用来模拟生物在自然的遗传环境中由于各种偶然因素引起的基因突变.若只有选择和交叉，而没有变异，则无法在初始基因组合以外的空间进行搜索，使进化过程在早期就陷入局部解而进入终止过程，从而影响解的质量!二、遗传算法的基本操作3变异(mutation)变异就是改变染色体某个(些)位上三、遗传算法的原理标准遗传算法流程框图遗传算子适者生存种群繁殖关键三、遗传算法的原理标准遗传算法流程框图遗传算子适者生存种群繁三、遗传算法的原理算法中的一些控制参数：

种群规模：最大换代数：交叉率(crossoverrate)：参加交叉运算的染色体个数占全体染色体总数的比例，记为Pc取值范围一般为0.4～0.99

变异率(mutationrate)：发生变异的基因位数所占全体染色体的基因总位数的比例，记为Pm

取值范围一般为0.0001～0.1三、遗传算法的原理算法中的一些控制参数：三、遗传算法的原理标准遗传算法(Standardgeneticalgorithm,SGA)Step1

在搜索空间U上定义一个适应度函数f(x)，给定种群规模N，交叉率Pc和变异率Pm，代数T；Step2

随机产生U中的N个个体s1,s2,…,sN，组成初始种群S={s1,s2,…,sN}，置代数计数器t=1；Step3

计算S中每个个体的适应度f(x)；

Step4若终止条件满足，则取S中适应度最大的个体作为所求结果，算法结束。否则，转Step5；三、遗传算法的原理标准遗传算法(StandardgenetStep5

按选择概率P(xi)所决定的选中机会，每次从S中随机选定1个个体并将其复制，共做N次，然后将复制所得的N个染色体组成群体S1；Step6

按交叉率Pc所决定的参加交叉的染色体数c，从S1中随机确定c个染色体，配对进行交叉操作，并用产生的新染色体代替原染色体，得群体S2；Step7按变异率Pm所决定的变异次数m，从S2中随机确定m个染色体，分别进行变异操作，并用产生的新染色体代替原染色体，得群体S3；Step8

将群体S3作为新一代种群，即用S3代替S，t=t+1，转步Step3；三、遗传算法的原理标准遗传算法(Standardgeneticalgorithm,SGA)Step5按选择概率P(xi)所决定的选中机会，每次从S四、遗传算法的应用1、遗传算法的应用领域（1）组合优化（2）函数优化（3）自动控制（4）生产调度（5）图像处理（6）机器学习（7）人工生命（8）数据挖掘四、遗传算法的应用1、遗传算法的应用领域（1）组合优化2、遗传算法的应用举例四、遗传算法的应用例：求下列一元函数的最大值：

x∈[-1,2]，求解结果精确到6位小数。2、遗传算法的应用举例四、遗传算法的应用例：求下列一元函数的四、遗传算法的应用用微分法求解：即：

解有无穷多个

(i=1,2,…及i=-1,-2,…)是一个接近于0的实数递减序列当i为奇数时xi对应局部极大值点，i为偶数时xi对应局部极小值x19即为区间[-1,2]内的最大值点此时，函数最大值f(x19）比f(1.85)=3.85稍大四、遗传算法的应用用微分法求解：即：解有无穷多个四、遗传算法的应用用遗传算法求解：

分析：由于区间长度为3，求解结果精确到6位小数，因此可将自变量定义区间划分为3×106等份。又因为221<3×106<222，所以本例的二进制编码长度至少需要22位，编码过程实质上是将区间[-1，2]内对应的实数值转化为一个二进制串（b21b20…b0）。求解过程：(1)编码表现型：x基因型：二进制编码，串长22位四、遗传算法的应用用遗传算法求解：分析：由于区间长度为几个术语基因型：1000101110110101000111表现型：0.637197编码解码个体（染色体）基因几个术语基因型：100010111011010100011四、遗传算法的应用(2)生成初始种群用遗传算法求解：方式：随机生成长度为22的二进制制串数量：种群的大小(规模)，如30，50，…111101001110000101100011001100111010101011101010100011110010000100101111001001110011100100011001010011000000110000011010010000000000……四、遗传算法的应用(2)生成初始种群用遗传算法求解：方式：随四、遗传算法的应用(3)计算适应度用遗传算法求解：不同的问题有不同的适应度计算方法，本例直接用目标函数作为适应度函数②计算x的函数值(适应度)：①将某个个体转化为[-1,2]区间的实数：s=<1000101110110101000111>x=0.637197(4)遗传操作选择：轮盘赌选择法交叉：单点交叉变异：小概率变异四、遗传算法的应用(3)计算适应度用遗传算法求解：四、遗传算法的应用用遗传算法求解：(5)模拟结果设置的参数：种群大小50,交叉概率0.75变异概率0.05,最大代数200

得到的最佳个体：smax=<1111001100111011111100>xmax=1.8506f(xmax)=3.8503世代数自变量适应度11.44953.449491.83953.7412171.85123.8499301.85053.8503501.85063.8503801.85063.85031201.85063.85032001.85063.8503