《遗传算法(geneticalgorithm)..》由会员分享，可在线阅读，更多相关《遗传算法(geneticalgorithm)..（49页珍藏版）》请在金锄头文库上搜索。
1、2019/8/19,遗传算法(Genetic Algorithm),进化算法(Evolutionary Algorithm),2019/8/19,遗传算法(GA),Darwin(1859): “物竟天择，适者生存” John Holland (university of Michigan, 1975) Adaptation in Natural and Artificial System 遗传算法作为一种有效的工具，已广泛地应用于最优化问题求解之中。 遗传算法是一种基于自然群体遗传进化机制的自适应全局优化概率搜索算法。它摒弃了传统的搜索方式，模拟自然界生物进化过程，采用人工的方式对目标空间进行
2、随机化搜索。,2019/8/19,遗传算法模拟自然选择和自然遗传过程中发生 的繁殖、交叉和基因突变现象，在每次迭代中 都保留一组候选解，并按某种指标从解群中选 取较优的个体，利用遗传算子(选择、交叉和变 异)对这些个体进行组合，产生新一代的候选解 群，重复此过程，直到满足某种收敛指标为止。,遗传算法的搜索机制,2019/8/19,遗传算法(GA),2019/8/19,We have a dream!,I am at the top Height is .,I am not at the top. My high is better!,I will continue,遗传算法(GA),GA-第0
3、代,2019/8/19,Dead one,New one,遗传算法(GA),GA-第1代,2019/8/19,Not at the top, Come Up!,遗传算法(GA),GA-第?代,2019/8/19,I am the BEST !,遗传算法(GA),GA-第N代,2019/8/19,适者生存(Survival of the Fittest) GA主要采用的进化规则是“适者生存” 较好的解保留，较差的解淘汰,遗传算法(GA),2019/8/19,生物进化与遗传算法对应关系,2019/8/19,遗传算法的基本操作,选择(selection): 根据各个个体的适应值，按照一定的规则或方法
4、，从第t代群体P(t)中选择出一些优良的个体遗传到下一代群体P(t+1)中。 交叉(crossover): 将群体P(t)内的各个个体随机搭配成对，对每一个个体，以某个概率Pc (称为交叉概率，crossvoer rate)交换它们之间的部分染色体。 变异(mutation): 对群体P(t)中的每一个个体，以某一概率Pm(称为变异概率，mutation rate)改变某一个或一些基因座上基因值为其它的等位基因。,2019/8/19,如何设计遗传算法,如何进行编码？ 如何产生初始种群？ 如何定义适应函数？ 如何进行遗传操作(复制、交叉、变异)？ 如何产生下一代种群？ 如何定义停止准则？,201
5、9/8/19,编码(Coding),2019/8/19,选择(Selection),选择(复制)操作把当前种群的染色体按与适应值成正比例的概率复制到新的种群中 主要思想: 适应值较高的染色体体有较大的选择(复制)机会 实现1：”轮盘赌”选择(Roulette wheel selection) 将种群中所有染色体的适应值相加求总和，染色体适应值按其比例转化为选择概率Ps 产生一个在0与总和之间的的随机数m 从种群中编号为1的染色体开始，将其适应值与后续染色体的适应值相加，直到累加和等于或大于m,2019/8/19,选择(Selection),设种群的规模为N xi是i为种群中第i个染色体,染色体
6、xi被选概率,2019/8/19,选择(Selection),染色体的适应值和所占的比例,轮盘赌选择,2019/8/19,选择(Selection),染色体被选的概率,被选的染色体,2019/8/19,选择(Selection),轮盘上的片分配给群体的染色体，使得每一个片的大小与对于染色体的适应值成比例 从群体中选择一个染色体可视为旋转一个轮盘，当轮盘停止时，指针所指的片对于的染色体就时要选的染色体。 模拟“轮盘赌” 算法： r=random(0, 1)，s=0，i=0； 如果sr，则转(4)； s=s+p(xi)，i=i+1, 转(2) xi即为被选中的染色体，输出I 结束,2019/8/1
7、9,选择(Selection),其他选择法： 随机遍历抽样(Stochastic universal sampling) 局部选择(Local selection) 截断选择(Truncation selection) 竞标赛选择(Tournament selection) 特点：选择操作得到的新的群体称为交配池，交配池是当前代和下一代之间的中间群体，其规模为初始群体规模。选择操作的作用效果是提高了群体的平均适应值(低适应值个体趋于淘汰，高适应值个体趋于选择)，但这也损失了群体的多样性。选择操作没有产生新的个体，群体中最好个体的适应值不会改变。,2019/8/19,交叉(crossover,
8、Recombination),遗传交叉(杂交、交配、有性重组)操作发生在两个染色体之间，由两个被称之为双亲的父代染色体，经杂交以后，产生两个具有双亲的部分基因的新的染色体，从而检测搜索空间中新的点。 选择(复制)操作每次作用在一个染色体上，而交叉操作每次作用在从交配池中随机选取的两个个体上(交叉概率Pc)。 交叉产生两个子染色体，他们与其父代不同，且彼此不同, 每个子染色体都带有双亲染色体的遗传基因。,2019/8/19,单点交叉(1-point crossover),在双亲的父代染色体中随机产生一个交叉点位置 在交叉点位置分离双亲染色体 互换交叉点位置右边的基因码产生两个子代染色体 交叉概率
9、Pc 一般范围为(60%, 90%)，平均约80%,交叉点位置,2019/8/19,交叉(crossover, Recombination),单点交叉操作可以产生与父代染色体完全不同的子代染色体；它不会改变父代染色体中相同的基因。但当双亲染色体相同时，交叉操作是不起作用的。,假如交叉概率Pc 50%,则交配池中50%的染色体(一半染色体) 将进行交叉操作，余下的50%的染色体进行选择(复制)操作。,GA利用选择和交叉操作可以产生具有更高平均适应值和更好染色体的群体,2019/8/19,变异(Mutation),以变异概率Pm改变染色体的某一个基因,当以二进制编码时，变异的基因由0变成1，或者由
10、1变成0。 变异概率Pm 一般介于1/种群规模与1/染色体长度之间，平均约1-2%,变异基因,变异基因,2019/8/19,变异(Mutation),比起选择和交叉操作，变异操作是GA中的次要操作，但它在恢复群体中失去的多样性方面具有潜在的作用。 在GA执行的开始阶段，染色体中一个特定位上的值1可能与好的性 能紧密联系，即搜索空间中某些初始染色体在那个位上的值1可能一 致产生高的适应值。因为越高的适应值与染色体中那个位上的值1相联 系，选择操作就越会使群体的遗传多样性损失。 等到达一定程度时，值0会从整个群体中那个位上消失，然而全局最 优解可能在染色体中那个位上为0。如果搜索范围缩小到实际包含
11、全局 最优解的那部分搜索空间，在那个位上的值0就可能正好是到达全局最 优解所需要的。,2019/8/19,适应函数(Fitness Function),GA在搜索中不依靠外部信息，仅以适应函数为依据，利用群体中每个染色体(个体)的适应值来进行搜索。以染色体适应值的大小来确定该染色体被遗传到下一代群体中的概率。染色体适应值越大，该染色体被遗传到下一代的概率也越大；反之，染色体的适应值越小，该染色体被遗传到下一代的概率也越小。因此适应函数的选取至关重要，直接影响到GA的收敛速度以及能否找到最优解。 群体中的每个染色体都需要计算适应值 适应函数一般由目标函数变换而成,2019/8/19,适应函数(F
12、itness Function),适应函数常见形式： 直接将目标函数转化为适应函数 若目标函数为最大化问题： Fitness(f(x) = f(x) 若目标函数为最小化问题： Fitness(f(x) = -f(x),缺点: (1)可能不满足轮盘赌选择中概率非负的要求 (2)某些代求解的函数值分布上相差很大，由此得到的评价适应值可能不利于体现群体的评价性能，影响算法的性能。,2019/8/19,适应函数(Fitness Function),界限构造法,2019/8/19,停止准则(Termination Criteria),种群中个体的最大适应值超过预设定值 种群中个体的平均适应值超过预设定值
13、 种群中个体的进化代数超过预设定值,2019/8/19,基本步骤(Step by Step),(1) 随机产生初始种群; (2) 计算种群体中每个个体的适应度值,判断是否满足停止条件，若不满足，则转第(3)步,否则转第(6)步; (3) 按由个体适应值所决定的某个规则选择将进入下一代的个体; (4) 按交叉概率Pc进行交叉操作,生产新的个体; (5) 按变异概率Pm进行变异操作,生产新的个体; (6) 输出种群中适应度值最优的染色体作为问题的满意解或最优解。,2019/8/19,流程图(Flow Chart),2019/8/19,基本遗传算法,基本遗传算法（Simple Genetic Alg
14、orithms, 简称SGA）是一种统一的最基本的遗传算法，它只 使用选择、交叉、变异这三种基本遗传算子，其遗传 进化操作过程简单，容易理解，是其他一些遗传算法 的雏形和基础，它不仅给各种遗传算法提供了一个基 本框架，同时也具有一定的应用价值。,2019/8/19,SGA伪码描述,Procedure Genetic Algorithm begin t = 0 ; 初始化 P(t) ; 计算 P(t) 的适应值 ; while (不满足停止准则) do begin t = t+1 ; 从P(t-1)中选择 P(t) ; % selection 重组 P(t) ; % crossover and
15、mutation 计算 P(t) 的适应值; end end,2019/8/19,遗传算法的应用,函数优化 函数优化是遗传算法的经典应用领域，也是对遗传算法进行性能测试评价的常用算例。对于一些非线性、多模型、多目标的函数优化问题，用其他优化方法较难求解，而遗传算法却可以方便地得到较好的结果。,遗传算法提供了一种求解复杂系统优化问题的通用框 架，它不依赖于问题的具体领域，对问题的种类有很 强的鲁棒性，所以广泛应用于很多学科。下面列举一 些遗传算法的主要应用领域。,2019/8/19,遗传算法的应用,组合优化 遗传算法是寻求组合优化问题满意解的最佳工具之一，实践证明，遗传算法对于组合优化问题中的N
16、P完全问题非常有效。例如，遗传算法已经在求解旅行商问题(Traveling Salesman Problem , TSP)、背包问题(Knapsack Problem)、装箱问题(Bin Packing Problem) 等方面得到成功的应用。 生产调度问题 生产调度问题在很多情况下所建立起来的数学模型难以精确求解，即使经过一些简化之后可以进行求解也会因简化得太多而使求解结果与实际相差太远。现在遗传算法已经成为解决复杂调度问题的有效工具。,2019/8/19,遗传算法的应用,自动控制 遗传算法已经在自动控制领域中得到了很好的应用，例如基于遗传算法的模糊控制器的优化设计、基于遗传算法的参数辨识、基于遗传算法的模糊控制规则的学习、利用遗传算法进行人工神经网络的结构优化设计和权值学习等。 机器人智能控制 机器人是一类复杂的难以精确建模的人工系统，而遗传算法的起源就来自于对人工自适应系统的研究，所以机器人智能控制自然成为遗传算法的一个重要应用
