《遗传算法2017-7》由会员分享，可在线阅读，更多相关《遗传算法2017-7（62页珍藏版）》请在金锄头文库上搜索。
1、遗 传 算 法,Genetic Algorithms,太原理工大学 数学学院 刘晓峰,数学建模一般的步骤和方法,层次分析法 量纲分析法图论法 微分方程 蒙特卡洛法 差值拟合法 回归分析法 数学规划,2018/9/26,2,概率统计 数值分析,运筹学 机器学习,GA与计算机其余相关学科的关系,2018/9/26,3,生物在自然界中的生存繁衍，显示出了其对自然环境的自适应能力。受其启发，学者致力于对生物各种生存特性的机理研究和行为进行模拟。遗传算法(Genetic Algorithms，GA)就是这种生物行为的计算机模拟中令人瞩目的重要成果(人工免疫/人工神经网络)。基于对生物遗传和进化过程的计算
2、机模拟，遗传算法使得各种人工系统具有优良的自适应能力和优化能力；它是模拟达尔文生物进化论的自然选择和孟德尔遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。遗传算法所借鉴的生物学基础就是生物的遗传和进化。,遗传算法的起源,最早由美国密西根大学的J.Holland教授提出，起源于60年代对自然和人工自适应系统的研究1967年，Bagley发表了关于遗传算法应用的论文，在其论文中首次使用“遗传算法（ Genetic Algorithm）”一词70年代 De Jong基于遗传算法的思想在计算机上进行了大量的纯数值函数优化计算实验在一系列研究工作的基础上，80年代由Gol
3、dberg进行归纳总结，形成了遗传算法的基本框架,遗传算法发展,1. 复制生物的主要遗传方式是复制。遗传过程中，父代的遗传物质DNA被复制到子代。即细胞在分裂时，遗传物质 DNA 通过复制而转移到新生的细胞中，新细胞就继承了旧细胞的基因。2. 交叉有性生殖生物在繁殖下一代时，两个同源染色体之间通过交叉(Crossover) 而重组，即在两个染色体的某一相同位置处DNA被切断，其前后两串分别交叉组合而形成两个新的染色体。3. 变异在进行细胞复制时，虽然概率很小，仅仅有可能产生某些复制差错，从而使 DNA 发生某种变异 (Mutation)，产生出新的染色体。这些新的染色体表现出新的性状。如此这般
4、，遗传基因(或染色体)在遗传的过程中由于各种各样的原因而发生变化。,生物的遗传方式,遗传算法的进化形式和单位,生物的进化是以集团的形式共同进行的，这样的一个团体称为群体/种群(Population) 组成群体的单个生物体称为个体(Individual)/染色体(Chromosome)，每一个个体对其生存环境都有不同的适应能力，这种适应能力称为个体的适应度(Fitness) 物竞天择 个体的基因(Gene)是遗传的基本单位 遗传基因在染色体中所占据的位置称为基因座 同一基因座可能有的全部基因称为等位基因(Allele),2018/9/26,遗传算法的简单原理,遗传算法将问题域中的可能解看做是群体
5、的一个个体或染色体，并将所有个体编码成符号串形式 模拟达尔文的遗传选择和自然淘汰的生物进化过程，对群体反复进行基于遗传学的操作（选择、交叉和变异），根据预定的目标适应度函数对每个个体进行评价 依据适者生存、优胜劣汰的进化规则，不断得到更优的群体，同时以全局并行搜索方式来搜索优化群体中的最优个体，求得满足要求的最优解,2018/9/26,8,遗传算法是模拟生物在自然环境下的遗传和进化过程而形成的一种自适应全局优化概率搜索方法。,袋鼠与珠穆朗玛峰的假想实验,在遗传算法中，假设将很多只袋鼠降落到喜马拉雅山脉的任意地方，这些袋鼠并不知道它们被设想寻找珠穆朗玛峰，休闲地活着。 但每过几年，就在海拔较低的
6、一些地方射杀一些袋鼠，并希望存活下来的那些是多产的，并在那里生儿育女。 这个实验进行N年之后,2018/9/26,9,2018/9/26,10,对求函数最大值的优化问题（或最小值），可描述为下述数学规划模型：max f(X) (1-1)s.t. XR (1-2)RU (1-3) 其中：Xx1,x2,xnT为决策变量， f(X)为目标函数，式(1-2)、(1-3)为约束条件，U是基本空间，R是U的一个子集。满足约束条件的解X称为可行解； 集合R表示由所有满足约束条件的解所组成的一个集合，叫做可行解集合。,优化问题,遗传算法在函数优化中的应用,例：利用遗传算法求解区间0,31上的二次函数y=x2的
7、最大值，x为自然数。将每一个自然数看成一个生命体，通过进化，看谁能生存下来，谁就是所寻找的数字，即问题的解。,y=x2,31 X,Y,0,2018/9/26,12,求解过程,将每一个数作为一个生命体，就必须给其赋予一定的基因，这个过程叫做编码。可以将变量x编码成5位长的二进制无符号整数表达形式，例如：x=13 (01101), 即数13的基因为 01101。,编码,1,2,2018/9/26,13,解的编码,2018/9/26,14,求解过程,将每一个数作为一个生命体，就必须给其赋予一定的基因，这个过程叫做编码。可以将变量x编码成5位长的二进制无符号整数表达形式，例如：x=13 (01101)
8、, 即数13的基因为 01101。由于遗传的需要，必须设定一些初始的生物群体，让其作为生物繁殖的第一代。为了保证生物的多样性和竞争的公平性，初始种群的所有个体都是通过随机方法产生的。,编码,1,2,初始种群的生成,2018/9/26,15,2018/9/26,16,生物的进化服从适者生存、优胜劣汰的规则。因此必须规定什么样的基因是“优”的，什么样的基因是“劣”的，称为适应度函数。显然，定义 为适应度函数，然后计算所有个体的适应度值。,适应度计算,3,4,2018/9/26,17,解码,计算适应度,2018/9/26,18,生物的进化服从适者生存、优胜劣汰的规则。因此必须规定什么样的基因是“优”
9、的，什么样的基因是“劣”的，称为适应度函数。显然，定义 为适应度函数，然后计算所有个体的适应度值。选择运算就是优胜劣汰的过程，把当前群体中适应度较高的个体按某种规则或模型遗传到下一代群体中，一般适应度较高的个体将有更多的机会遗传到下一代群体中。 选择是一个概率选择的过程，基因差的不一定会被淘汰。,适应度计算,选择,3,4,2018/9/26,19,为了产生新的个体，种群中进行交叉繁殖。以某一概率选出两个个体，相互交换一部分基因，就形成了两个新的个体。,交叉,5,2018/9/26,20,交叉位,Pcross,cross,父代个体,子代个体,交叉概率,连续改变个体多个基因位上的遗传信息,1,2,
10、1,2,2018/9/26,21,为了产生新的个体，种群中进行交叉繁殖。以某一概率选出两个个体，相互交换一部分基因，就形成了两个新的个体。变异运算是将个体基因中的某一位以一定的小概率发生变化，也可以产生新的个体。,交叉,5,6,变异,2018/9/26,22,变异位,Pmutate,mutate,父代个体,子代个体,变异概率,2018/9/26,23,为了产生新的个体，种群中进行交叉繁殖。以某一概率选出两个个体，相互交换一部分基因，就形成了两个新的个体。变异运算是将个体基因中的某一位以一定的小概率发生变化，也可以产生新的个体。,交叉,5,6,变异,这样就经过了一代进化，通过上述步骤不断地循环进
11、化，种群中的个体基因便逐渐地趋向最优。,2018/9/26,24,Y,2018/9/26,25,遗传算法流程图,2018/9/26,26,步1 在搜索空间U上定义一个适应度函数f(x)，给定种群规模N，交叉率Pc 和变异率Pm，代数T；,基本遗传算法步骤,步2 随机产生U中的N个个体s1, s2, , sN，组成初始种群S=s1, s2, , sN，置代数计数器 t=1；步3 计算S 中每个个体的适应度 f( ) ；步4 若终止条件满足，则取S中适应度最大的个体作为所求结果，算法结束。,步5 否则，按选择概率P(xi)所决定的选中机会，每次从S 中随机选定1个个体并将其染色体复制，共做 N 次
12、，然后将复制所得的 N 个染色体组成群体 S1 ；,步7 按变异率Pm所决定的变异次数m，从S2中随机确定m个染色体，分别进行变异操作，并用产生的新染色体代替原染色体，得群体S3；步8 将群体S3作为新一代种群，即用S3代替S，t = t+1，转步3。,步6 按交叉率Pc所决定的参加交叉的染色体数c，从S1中随机确定c 个染色体，配对进行交叉操作，并用产生的新染色体代替原染色体，得群体 S2 ；,基本遗传算法步骤,基本遗传算法的运行参数,M：群体大小，群体规模POP，即群体中所含个体的数量，一般取为20-100 T：遗传运算的终止进化代数，一般取为100-500 pc：交叉概率(crossov
13、er rate)，就是参加交叉运算的染色体个数占全体染色体总数的比例，记为Pc，一般取为0.5-0.9 pm：变异概率(mutation rate)，是指发生变异的基因位数所占全体染色体的基因总位数的比例，记为Pm，一般取为 0.0001-0.1 说明：这4个运行参数对遗传算法的求解结果和求解效率都有一定的影响，但目前尚无合理选择它们的理论依据。在遗传算法的实际应用中，往往需要经过多次试算后才能确定出这些参数合理的取值大小或取值范围。,适应度收敛曲线,遗传算法工具箱,遗传算法的工具箱有很多种： Genetic Algorithm Tool 简称GATOOL-GADS Genetic Algor
14、ithm Optimization Tool 简称GAOT Genetic Algorithm Toolbox 简称GATBX Simple Genetic Algorithm 1002 简称SGA1002 Main function Comparation Of Genetic Algorithm Toolbox base Matlab,gatbx工具箱版本查看, v=ver(gatbx) v = Name: Genetic Algorithm ToolboxVersion: 1.2Release: Date: 15-Apr-94,遗传算法与直接搜索工具箱GADS,GADS工具箱是一系列函数
15、的集合，它们扩展了优化工具箱和MATLAB数值计算环境的性能。使得用户能够求解那些标准优化工具箱范围之外的各种优化问题。,所有的工具箱函数都是m文件，可以使用type function name 查看函数代码也可以通过编写自己的m文件来实现和扩展GADS工具箱的性能。 遗传算法、直接搜索工具箱和优化工具箱是紧密结合在一起的。用户可以用GADS工具箱来寻找最佳起始点，然后利用优化工具箱或其它程序来进一步寻找最优解。,Matlab自带遗传算法工具箱GADS,工具箱具有两种使用方式： (1)以命令行方式调用遗传算法函数ga。 (2)通过图形用户界面使用遗传算法工具箱。,命令行方式：x fval=ga(fitnessfun, nvars, options) fitnessfun是求最小值的适应度函数句柄； nvars是适应度函数的独立变量的个数； options是一个包含遗传算法选项设置、属性参数的结构，如果没有特别改写，则ga使用它本身的默认选项值；可以通过函数gaoptimset修改设置； x最终值到达的点； fval适应度函数的最终值,
