遗传算法(GeneticAlgorithm)PPT课件VIP

2020/5/22，1，遗传算法(GeneticAlgorithm )，演进算法(EvolutionaryAlgorithm )，2020/5/22，2，遗传算法(GA )，Darwin(1859):“物被选择到天上， 适者生存”John Holland (universityofmichigan，1975) AdaptationinNaturalandArtificialSystem遗传算法作为一种有效的工具，广泛应用于解决优化问题。 遗传算法是一种基于自然群体遗传进化机制的自适应全局优化概率搜索算法。 抛弃传统的探索方式，模拟自然界的生物进化过程，用人工方法随机化探索目标空间。 2020/5/22，3，遗传算法模拟自然选择和自然遗传过程中发生的繁殖交叉基因突变现象，每次迭代保留一组候选解，以某个指标从解群中选择较好的个体，利用基因运算符(选择交叉突变)组合这些个体，生成下一代候选解群，某个收敛指标遗传算法的检索机制，2020/5/22，4，遗传算法(GA )，2020/5/22，5，Wehaveadream！ 什么？ IamatthetopHeightis .Iamnotatthetop.Myhighisbetter！ Iwillcontinue，遗传算法(GA )，GA-第0代，2020/5/22，6，Deadone，Newone，遗传算法(GA )，GA-第1代，2020/5/22，7，Notatthetop，ComeUp！ 什么？ 什么？ 遗传算法(GA )，GA-第？ 代替，2020/5/22，8，IamtheBEST！ 什么？ 什么？ 遗传算法(GA )，GA-第n代，2020/5/22，9，适宜生存(SurvivaloftheFittest)GA主要是“适宜生存”的良好解保留，差的解淘汰，遗传算法(GA )，2020/5/22，10，生物进化与遗传算法的对应关系遗传算法的基本操作如下：选择部(selection):根据个体的适配值，按照一定规则或方法，从t代的集合P(t )中选择一些优良的个体来遗传到下一代的集合P(t 1)。 交叉(crossover):将群P(t )内的个体随机地成对，并针对每个个体以某种概率Pc (交叉概率，称为crossvoerrate )在它们之间交换部分染色体。 变异(mutation):对于集团P(t )的各个个体，将某一概率Pm (变异概率，称为mutationrate )的基因座的基因值变为其他等位基因。 2020/5/22，12，如何设计和编码遗传算法？ 如何建立早期种群？ 自适应函数的定义方法如何进行遗传操作(复制、交叉、变异)？ 如何创造下一代种群？ 停止标准的定义方法、2020/5/22、13、编码、2020/5/22、14、选择(复制)操作对于以与适应值成比例的概率将当前种群的染色体复制到新种群的主要思想：的适应值较高的染色体来说是较大的选择(复制) 有机会1 :“轮盘赌”选择(Roulettewheelselection )将种群中所有染色体的适应值相加，染色体适应值按其比例变化为选择概率Ps，0和总和之间的随机数m从种群中编号为1的染色体开始，将其适应值与后续染色体的适应值相加，m，220 选择直到22以上，将种群规模设为Nxi，则在种群中选择第I条染色体、染色体xi的概率、2020/5/22 16、选择(Selection )、染色体在适应值中所占的比例、轮盘选择、2020/5/22、17、选择(Selection )、 选择染色体的概率，选择的染色体，2020/5/22，18，选择(Selection )，将轮盘上的片分配给一组染色体，每个片的大小与染色体的适应值成比例地从一组中选择一个染色体可以看作轮盘旋转模拟“轮盘赌”算法： r=random (0，1 )，s=0，i=0； 对于其中选择了s=s-p (Xi )、i=i 1并且旋转(2)xi的染色体，输出I到期(2020/5/22，19，选择的其它选择方法：随机扫描采样局部选择(Localselection )截断选择(truncateselection )投标选择(Tournamentselection )的特征：通过选择操作得到的新组称为交配池，交配池是现代和下一代之间的中间组，其规模为初始组选择操作的效果是提高集团的平均适应值(低适应值个体被淘汰，有选择高适应值个体的倾向)，但这也会损害集团的多样性。 在选择操作中不会产生新的个体，集团中最佳个体的适应值不会改变。、2020/5/22、20、交叉(crossover，Recombination )、遗传交叉(杂交、杂交、有效性重组)操作发生在两个染色体之间，从被称为父母的两个父染色体杂交后，产生具有父母基因一部分的两个新染色体，用于探索空间的新选择(复制)操作作用于一个染色体，交叉操作作用于从交配池中随机选择的两个个体(交叉概率Pc )。 交叉产生两个子染色体，他们与父母不同，而且互不相同，每个子染色体都有父母染色体的基因。 2020/5/22，21，单点交叉(1-pointcrossover )，在父母染色体上随机分离一个交叉点位置为交叉点位置的父母染色体交叉点位置右侧的基因代码，产生两个子染色体交叉概率Pc的一般范围为(60%，90% )，平均约80%，交叉点位置，2020/5/22，22交叉(crossover，Recombination )，单点交叉操作不会改变能够产生与母染色体完全不同的子染色体的母染色体的相同基因。 但是，当父母染色体相同时，交叉操作不起作用。 当交叉概率Pc=50%时，交配池50%的染色体(一半的染色体)进行交叉操作，其馀50%的染色体进行选择(复制)操作。 GA利用选择和交叉操作，可以构建具有更高平均适应值和更好染色体的群体，在2020/5/22，23，变异概率Pm下改变染色体的某个基因，用二进制码编码，变异的基因从0变为1，或者从1变为0。 变异概率Pm通常介于1/种群的规模和1/染色体的长度之间，平均约为1-2%，变异基因、变异基因、2020/5/22.24.变异(Mutation )通过选择和交叉操作，变异操作是GA中的次要操作，但它可以恢复集体丢失的多样性在GA执行的开始阶段，染色体的某个特定部位的值1可能与良好的性能密切相关联，即，在搜索空间中初始染色体的该部位的值1可能一致地产生很高的适应值。 由于较高的适应值与染色体中该位置的值1相联系，选择操作会损害群体的遗传多样性。 在某种程度上，值0将从整个群体中的该位置消失，但全局最优解可能在染色体中的该位置变为0。 如果搜索范围实际上被限定为包括全局最优化解的部分的搜索空间，则正好达到该全局最优化解所需的比特值0。 另外，2020/5/22、25、自适应函数(FitnessFunction )、GA在搜索中不依赖外部信息，仅根据自适应函数利用集团中每个染色体(个体)的自适应值进行搜索。 染色体适应值的大小决定该染色体被遗传到下一代群体的概率。 染色体适应值越大，该染色体被遗传到下一代的概率也越大，相反，染色体的适应值越小，该染色体被遗传到下一代的概率也越小。 因此，自适应函数的选择很重要，直接影响GA的收敛速度和是否找到最佳解。 为群体中的每条染色体计算自适应值的自适应函数一般从目标函数转换为2020/5/22，自适应函数(FitnessFunction )，自适应函数的一般形式：直接将目标函数转换为自适应函数时，目标函数最大化问题： Fitness(f(x)=f(x ) 目标函数最小化问题： Fitness(f(x)=-f(x )缺点：(1)由于在轮盘选择中可能不满足概率非负要求(2)某些世代可能求解的函数值的分布存在较大差异，所以所得评估自适应值不利于表示群的评估性能，其可能影响算法的性能、2020/5/22、自适应函数(FitnessFunction )、边界构造法、2020/5/22、28、停止基准(TerminationCriteria )、种群中个体的最大适应值超过设定值的种群中的个体的平均适应值超过设定值的种群中的进化代数超过设定值的20 22、29、基本步骤(StepbyStep )、(1)随机生成初始种群(2)计算各种群中的每个个体的适应度值，判断是否满足停止条件，当不满足时转移到(3)步骤，当不满足时转移到(6)步骤(3) 根据个体适应值决定的某个规则选择进入下一代的个体(4)以交叉概率Pc进行交叉操作，生成新个体(5)以变异概率Pm进行变异操作，生成新个体(6)将在个体群中适应度值最佳的染色体作为问题的满足解或最佳解输出。 流程图2020/5/22、30、流程图2020/5/22、31、基本遗传算法(SimpleGeneticAlgorithms，简称SGA )是统一的最基本遗传算法，表示选择、交叉点、 仅使用变异这3种基本遗传算子，遗传演化的操作过程简单易懂，是其他遗传算法的原型和基础，它不仅为各种遗传算法提供了基本框架，而且具有一定的应用价值。2020/5/22、32、SGA伪代码描述、procedureegenerticalgorithmbegint=0； 初始化p的(t )计算p (t )的自适应值的while (不满足停止标准) dobegint=t 1； 从P(t-1 )中选择P(t )的%selection重组P(t) %crossoverandmutation计算P(t )的适应值：结束、2020/5/22、33、应用遗传算法、函数优化函数优化或遗传算法的典型对于一些非线性、多模型和多目标函数优化问题，其他优化方法难以求解，但遗传算法可以很容易地得到良好的结果。 遗传算法提供了求解复杂系统优化问题的共同框架，不依赖于问题的具体领域，问题类型具有较强的鲁棒性，因此被广泛应用于许多学科。 下面是遗传算法的一些主要应用领域。 2020/5/22，34，遗传算法的应用，组合优化遗传算法是求解组合优化问题满意度的最佳工具之一，实践证明，遗传算法对组合优化问题中的NP完整性问题非常有效。 例如，遗传算法成功地解决了旅行者问题(TravelingSalesmanProblem，TSP )、背包问题(KnapsackProblem )、装箱问题(BinPackingProblem )等。 生产计划问题生产计划问题在很多情况下确立的数学模型难以正确求解，即使经过一些简化后可以求解，由于简化过多，求解结果与实际相差甚远。 目前，遗传算法已成为解决复杂调度问题的有效工具。 2020/5/22，35，遗传算法的应用，自动控制遗传算法已经在基于遗传算法的模糊控制器优化设计，基于遗传算法的参数识别，基于遗传算法的模糊控制规则学习，利用遗传算法机器人智能控制机器人是一个复杂而难以精确建模的人工系统，但遗传算法的起源源于人工适应系统的研究，因此机器人智能控制自然成为遗传算法的重要应用领域。 2020/5/22，36，遗传算法的应用，图像处理和模式识别图像处理和模式识别是计算机视觉的重要研究领域。 在图像处理过程中，扫描、特征提取、图像分割等必然存在若干误差，这些误差会影响图像处理的效果。 如何最小化这些误差是实用计算机视觉的重要要求，遗传算法常用于这些图像处理中的优化计算。 人工生命的人工生命是利用计算机和机器等人工媒体，具有自然生物系统特有行为的人工系统。 自我组织能力和自我学习能力是人工生命的两个重要特征。人工生命与遗传算法有着密切的关系，基于遗传算法的演化模型是研究人工生命现象的重要理论基础。 2020/5/22，37，遗传算法的应用，遗传程序设计Koza发展了遗传程序设计的概念，采用以LISP语言表示的编码方法，基于对一个树结构的遗传操作自动生成了计算机程序。 基于机器学习遗传算法的机器学习应用于很多领域。 例如，基于遗传算法的机器学习也可以用于人工神经网络的网络结构优化设计以调节人工神经网络的连接权限。 分类器系统在多机器人路径规划系统中成功。2020/5/22、SGA实例1 :函数的最大值、SGA参数：编码方案：二进制代码e.g.000000； 0110113； 1111131种群规模：4随机初始群体“拨号赌”略有杂交，选择二进制变异，求出函数f(x)=x2的最大值，x为自然数且为0x31 .手动完成演示SGA过程，2020/5/22，39，SGA实例1 ma 2020/5/22.40 SGA实例1 maxx 23360交叉操作、2020/5/22.41、SGA实例1 maxx 23360变异操作、2020/5/22、SGA实例23360连续函数最大值、202