遗传算法GeneticAlgorithm专题知识讲座

1、遗传算法GeneticAlgorithm专题知识讲座遗传算法GeneticAlgorithm专题知识讲座第1页2022/9/4遗传算法(GA)Darwin(1859): “物竟天择，适者生存”John Holland (university of Michigan, 1975) Adaptation in Natural and Artificial System遗传算法作为一个有效工具，已广泛地应用于最优化问题求解之中。遗传算法是一个基于自然群体遗传进化机制自适应全局优化概率搜索算法。它摒弃了传统搜索方式，模拟自然界生物进化过程，采取人工方式对目标空间进行随机化搜索。遗传算法GeneticA

2、lgorithm专题知识讲座第2页2022/9/4 遗传算法模拟自然选择和自然遗传过程中发生繁殖、交叉和基因突变现象，在每次迭代中都保留一组候选解，并按某种指标从解群中选取较优个体，利用遗传算子(选择、交叉和变异)对这些个体进行组合，产生新一代候选解群，重复此过程，直到满足某种收敛指标为止。遗传算法搜索机制遗传算法GeneticAlgorithm专题知识讲座第3页2022/9/4局部全局遗传算法(GA)遗传算法GeneticAlgorithm专题知识讲座第4页2022/9/4We have a dream!I am at the topHeight is .I am not at the to

3、p.My high is better!I will continue遗传算法(GA)GA-第0代遗传算法GeneticAlgorithm专题知识讲座第5页2022/9/4Dead oneNew one遗传算法(GA)GA-第1代遗传算法GeneticAlgorithm专题知识讲座第6页2022/9/4Not at the top, Come Up!遗传算法(GA)GA-第?代遗传算法GeneticAlgorithm专题知识讲座第7页2022/9/4I am the BEST !遗传算法(GA)GA-第N代遗传算法GeneticAlgorithm专题知识讲座第8页2022/9/4适者生存(Su

4、rvival of the Fittest)GA主要采取进化规则是“适者生存”很好解保留，较差解淘汰遗传算法(GA)遗传算法GeneticAlgorithm专题知识讲座第9页2022/9/4生物进化与遗传算法对应关系生物进化遗传算法适者生存适应函数值最大解被保留概率最大个体问题一个解染色体解编码基因编码元素群体被选定一组解种群依据适应函数选择一组解交叉以一定方式由双亲产生后代过程变异编码一些分量发生改变过程环境适应函数遗传算法GeneticAlgorithm专题知识讲座第10页2022/9/4遗传算法基础操作选择(selection): 依据各个个体适应值，按照一定规则或方法，从第t代群体P(

5、t)中选择出一些优良个体遗传到下一代群体P(t+1)中。 交叉(crossover): 将群体P(t)内各个个体随机搭配成对，对每一个个体，以某个概率Pc (称为交叉概率，crossvoer rate)交换它们之间个别染色体。变异(mutation): 对群体P(t)中每一个个体，以某一概率Pm(称为变异概率，mutation rate)改变某一个或一些基因座上基因值为其它等位基因。遗传算法GeneticAlgorithm专题知识讲座第11页2022/9/4怎样设计遗传算法怎样进行编码？怎样产生初始种群？怎样定义适应函数？怎样进行遗传操作(复制、交叉、变异)？怎样产生下一代种群？怎样定义停顿准

6、则？遗传算法GeneticAlgorithm专题知识讲座第12页2022/9/4编码(Coding)表现型空间编码(Coding)解码(Decoding)基因型空间 = 0,1L0111010010100010011001001010010001遗传算法GeneticAlgorithm专题知识讲座第13页2022/9/4选择(Selection)选择(复制)操作把当前种群染色体按与适应值成正百分比概率复制到新种群中 主要思想: 适应值较高染色体体有较大选择(复制)机会实现1：”轮盘赌”选择(Roulette wheel selection)将种群中全部染色体适应值相加求总和，染色体适应值按其百

7、分比转化为选择概率Ps产生一个在0与总和之间随机数m从种群中编号为1染色体开始，将其适应值与后续染色体适应值相加，直到累加和等于或大于m遗传算法GeneticAlgorithm专题知识讲座第14页2022/9/4选择(Selection)设种群规模为Nxi是i为种群中第i个染色体AC1/6 = 17%3/6 = 50%B2/6 = 33%fitness(A) = 3fitness(B) = 1fitness(C) = 2染色体xi被选概率遗传算法GeneticAlgorithm专题知识讲座第15页2022/9/4选择(Selection)染色体适应值和所占百分比轮盘赌选择遗传算法Genetic

8、Algorithm专题知识讲座第16页2022/9/4选择(Selection)随机数234913 386 27所选号码 26 2 51 4所选染色体110000001111000011000111010010染色体编号 1 2 3 4 5 6染色体011101100000100100100110000011适应度 8 152 5 128被选概率0.160.30.040.10. 240.16适应度累计 8 23 25 30 42 50染色体被选概率被选染色体遗传算法GeneticAlgorithm专题知识讲座第17页2022/9/4选择(Selection)轮盘上片分配给群体染色体，使得每一个

9、片大小与对于染色体适应值成百分比从群体中选择一个染色体可视为旋转一个轮盘，当轮盘停顿时，指针所指片对于染色体就时要选染色体。模拟“轮盘赌” 算法：r=random(0, 1)，s=0，i=0；假如sr，则转(4)；s=s+p(xi)，i=i+1, 转(2)xi即为被选中染色体，输出I结束遗传算法GeneticAlgorithm专题知识讲座第18页2022/9/4选择(Selection)其它选择法：随机遍历抽样(Stochastic universal sampling)局部选择(Local selection)截断选择(Truncation selection)竞标赛选择(Tournamen

10、t selection)特点：选择操作得到新群体称为交配池，交配池是当前代和下一代之间中间群体，其规模为初始群体规模。选择操作作用效果是提升了群体平均适应值(低适应值个体趋于淘汰，高适应值个体趋于选择)，但这也损失了群体多样性。选择操作没有产生新个体，群体中最好个体适应值不会改变。遗传算法GeneticAlgorithm专题知识讲座第19页2022/9/4交叉(crossover, Recombination)遗传交叉(杂交、交配、有性重组)操作发生在两个染色体之间，由两个被称之为双亲父代染色体，经杂交以后，产生两个含有双亲个别基因新染色体，从而检测搜索空间中新点。选择(复制)操作每次作用在一

11、个染色体上，而交叉操作每次作用在从交配池中随机选取两个个体上(交叉概率Pc)。交叉产生两个子染色体，他们与其父代不一样，且彼此不一样, 每个子染色体都带有双亲染色体遗传基因。遗传算法GeneticAlgorithm专题知识讲座第20页2022/9/4单点交叉(1-point crossover)在双亲父代染色体中随机产生一个交叉点位置在交叉点位置分离双亲染色体交换交叉点位置右边基因码产生两个子代染色体交叉概率Pc 普通范围为(60%, 90%)，平均约80%11111111父代1111000000000000子代111100000000000011111111交叉点位置遗传算法GeneticA

12、lgorithm专题知识讲座第21页2022/9/4交叉(crossover, Recombination)单点交叉操作能够产生与父代染色体完全不一样子代染色体；它不会改变父代染色体中相同基因。但当双亲染色体相同时，交叉操作是不起作用。假如交叉概率Pc 50%,则交配池中50%染色体(二分之一染色体)将进行交叉操作，余下50%染色体进行选择(复制)操作。GA利用选择和交叉操作能够产生含有更高平均适应值和更加好染色体群体遗传算法GeneticAlgorithm专题知识讲座第22页2022/9/4变异(Mutation)以变异概率Pm改变染色体某一个基因,当以二进制编码时，变异基因由0变成1，或者

13、由1变成0。变异概率Pm 普通介于1/种群规模与1/染色体长度之间，平均约1-2%11010100父代01010101子代变异基因变异基因遗传算法GeneticAlgorithm专题知识讲座第23页2022/9/4变异(Mutation)比起选择和交叉操作，变异操作是GA中次要操作，但它在恢复群体中失去多样性方面含有潜在作用。 在GA执行开始阶段，染色体中一个特定位上值1可能与好性能紧密联络，即搜索空间中一些初始染色体在那个位上值1可能一致产生高适应值。因为越高适应值与染色体中那个位上值1相联系，选择操作就越会使群体遗传多样性损失。 等抵达一定程度时，值0会从整个群体中那个位上消失，然而全局最

14、优解可能在染色体中那个位上为0。假如搜索范围缩小到实际包含全局最优解那个别搜索空间，在那个位上值0就可能恰好是抵达全局最优解所需要。遗传算法GeneticAlgorithm专题知识讲座第24页2022/9/4适应函数(Fitness Function)GA在搜索中不依靠外部信息，仅以适应函数为依据，利用群体中每个染色体(个体)适应值来进行搜索。以染色体适应值大小来确定该染色体被遗传到下一代群体中概率。染色体适应值越大，该染色体被遗传到下一代概率也越大；反之，染色体适应值越小，该染色体被遗传到下一代概率也越小。所以适应函数选取至关主要，直接影响到GA收敛速度以及能否找到最优解。群体中每个染色体都

15、需要计算适应值适应函数普通由目标函数变换而成遗传算法GeneticAlgorithm专题知识讲座第25页2022/9/4适应函数(Fitness Function)适应函数常见形式：直接将目标函数转化为适应函数若目标函数为最大化问题： Fitness(f(x) = f(x)若目标函数为最小化问题： Fitness(f(x) = -f(x)缺点: (1)可能不满足轮盘赌选择中概率非负要求 (2)一些代求解函数值分布上相差很大，由此得到评价适应值可能不利于表达群体评价性能，影响算法性能。遗传算法GeneticAlgorithm专题知识讲座第26页2022/9/4适应函数(Fitness Funct

16、ion)界限结构法 目标函数为最大化问题其中Cmin为f(x)最小预计值 目标函数为最小化问题其中Cmaxn为f(x)最大预计值遗传算法GeneticAlgorithm专题知识讲座第27页2022/9/4停顿准则(Termination Criteria)种群中个体最大适应值超出预设定值种群中个体平均适应值超出预设定值种群中个体进化代数超出预设定值遗传算法GeneticAlgorithm专题知识讲座第28页2022/9/4基础步骤(Step by Step)(1) 随机产生初始种群;(2) 计算种群体中每个个体适应度值,判断是否满足停顿条件，若不满足，则转第(3)步,不然转第(6)步;(3)

17、按由个体适应值所决定某个规则选择将进入下一代个体;(4) 按交叉概率Pc进行交叉操作,生产新个体;(5) 按变异概率Pm进行变异操作,生产新个体;(6) 输出种群中适应度值最优染色体作为问题满意解或最优解。遗传算法GeneticAlgorithm专题知识讲座第29页2022/9/4流程图(Flow Chart)遗传算法GeneticAlgorithm专题知识讲座第30页2022/9/4基础遗传算法基础遗传算法（Simple Genetic Algorithms,简称SGA）是一个统一最基础遗传算法，它只使用选择、交叉、变异这三种基础遗传算子，其遗传进化操作过程简单，轻易了解，是其它一些遗传算法

18、雏形和基础，它不但给各种遗传算法提供了一个基本框架，同时也含有一定应用价值。遗传算法GeneticAlgorithm专题知识讲座第31页2022/9/4SGA伪码描述Procedure Genetic Algorithm begint = 0 ;初始化 P(t) ;计算 P(t) 适应值 ;while (不满足停顿准则) do begin t = t+1 ; 从P(t-1)中选择 P(t) ; % selection 重组 P(t) ; % crossover and mutation 计算 P(t) 适应值; end end遗传算法GeneticAlgorithm专题知识讲座第32页2022

19、/9/4遗传算法应用函数优化 函数优化是遗传算法经典应用领域，也是对遗传算法进行性能测试评价常见算例。对于一些非线性、多模型、多目标函数优化问题，用其它优化方法较难求解，而遗传算法却能够方便地得到很好结果。遗传算法提供了一个求解复杂系统优化问题通用框架，它不依赖于问题详细领域，对问题种类有很强鲁棒性，所以广泛应用于很多学科。下面列举一些遗传算法主要应用领域。遗传算法GeneticAlgorithm专题知识讲座第33页2022/9/4遗传算法应用组合优化 遗传算法是寻求组合优化问题满意解最正确工具之一，实践证实，遗传算法对于组合优化问题中NP完全问题非常有效。比如，遗传算法已经在求解旅行商问题(

20、Traveling Salesman Problem , TSP)、背包问题(Knapsack Problem)、装箱问题(Bin Packing Problem) 等方面得到成功应用。生产调度问题 生产调度问题在很多情况下所建立起来数学模型难以准确求解，即使经过一些简化之后能够进行求解也会因简化得太多而使求解结果与实际相差太远。现在遗传算法已经成为处理复杂调度问题有效工具。遗传算法GeneticAlgorithm专题知识讲座第34页2022/9/4遗传算法应用自动控制 遗传算法已经在自动控制领域中得到了很好应用，比如基于遗传算法含糊控制器优化设计、基于遗传算法参数辨识、基于遗传算法含糊控制规

21、则学习、利用遗传算法进行人工神经网络结构优化设计和权值学习等。机器人智能控制 机器人是一类复杂难以准确建模人工系统，而遗传算法起源就来自于对人工自适应系统研究，所以机器人智能控制自然成为遗传算法一个主要应用领域。 遗传算法GeneticAlgorithm专题知识讲座第35页2022/9/4遗传算法应用图象处理和模式识别 图像处理和模式识别是计算机视觉中一个主要研究领域。在图像处理过程中，如扫描、特征提取、图像分割等不可防止地存在一些误差，这些误差会影响图像处理效果。怎样使这些误差最小是使计算机视觉到达实用化主要要求，遗传算法在这些图像处理中优化计算方面得到了很好应用。人工生命 人工生命是用计算

22、机、机械等人工媒体模拟或结构出含有自然生物系统特有行为人造系统。自组织能力和自学习能力是人工生命两大主要特征。人工生命与遗传算法有着亲密关系，基于遗传算法进化模型是研究人工生命现象主要理论基础。遗传算法GeneticAlgorithm专题知识讲座第36页2022/9/4遗传算法应用遗传程序设计 Koza发展了遗传程序设计概念，他使用了以LISP语言所表示编码方法，基于对一个树形结构所进行遗传操作来自动生成计算机程序。 机器学习 基于遗传算法机器学习，在很多领域中都得到了应用。比如基于遗传算法机器学习可用来调整人工神经网络连接权，也能够用于人工神经网络网络结构优化设计。分类器系统在多机器人路径规

23、划系统中得到了成功应用。遗传算法GeneticAlgorithm专题知识讲座第37页2022/9/4SGA实例1：函数最值SGA参数:编码方式: 二进制码 e.g. 000000; 01101 13; 1111131种群规模: 4随机初始群体“转盘赌”选择一点杂交, 二进制变异 求函数f(x)=x2最大值，x为自然数且0 x31.手工方式完成演示SGA过程遗传算法GeneticAlgorithm专题知识讲座第38页2022/9/4SGA实例1 max x2 : 选择操作遗传算法GeneticAlgorithm专题知识讲座第39页2022/9/4SGA实例1 max x2 : 交叉操作遗传算法G

24、eneticAlgorithm专题知识讲座第40页2022/9/4SGA实例1 max x2 : 变异操作遗传算法GeneticAlgorithm专题知识讲座第41页2022/9/4SGA实例2 : 连续函数最值求以下函数最大值：遗传算法GeneticAlgorithm专题知识讲座第42页2022/9/4SGA实例2 : 编码高精度 编码 x,y 0,1L 必须可逆(一个表现型对应一个基因型) 解码算子：: 0,1L x,y 染色体长度L决定可行解最大精度长染色体(慢进化) 实数问题：变量z为实数，怎样把a1,aL 0,1Lzx,y遗传算法GeneticAlgorithm专题知识讲座第43页2022/9/4SGA实例2 : 编码设定求解准确到6位小数，因区间长度位2-(-1)=3,则需将区间分为3X106等份。因 2097152221 3X1062224194304。故编码二进制串长L=22。将一个二进制串(b21b20b0)转化为10进制数：e.g. -1; 2 1.627 888 1.627888 = -1+3x(1110000000111111000101) 2 /(222-1) = -1+3