遗传算法ppt课件.ppt
《遗传算法ppt课件.ppt》由会员分享,可在线阅读,更多相关《遗传算法ppt课件.ppt(64页珍藏版)》请在三一文库上搜索。
1、遗传算法简介,遗传算法,1 基本概念 2 选择算子 3 交叉算子 4 变异算子 5 基本遗传算法 6 基本实现技术 7 遗传算法应用,遗传算法,生物进化 自然法则 优胜劣汰 适者生存 有性繁殖 基因通过有性繁殖不断进行混合和重组 遗传算法 从生物界按照自然选择和有性繁殖、遗传变异的自然进化现象中得到启发,而设计的一种优化搜索算法,遗传算法,应用 函数优化 组合优化:旅行商、图形化分 生产调度:车间调度、生产规划 自动控制:控制器、参数辨识 机器人智能控制:机器人路径规划、运动轨迹规划 图像处理与模式识别:特征提取、图像分割 人工生命:进化模型、学习模型、行为模型 遗传程序设计 机器学习,1 基
2、本概念,个体 个体就是模拟生物个体而对问题中的对象(一般就是问题的解)的一种称呼 一个个体也就是搜索空间中的一个点 种群 种群(population)就是模拟生物种群而由若 干个体组成的群体 它一般是整个搜索空间的一个很小的子集 通过对种群实施遗传操作,使其不断更新换代而实现对整个论域空间的搜索,1 基本概念,适应度(fitness) 借鉴生物个体对环境的适应程度,而对问题中的个体对象所设计的表征其优劣的一种测度 适应度函数(fitness function) 问题中的全体个体与其适应度之间的一个对应关系 一般是一个实值函数,且一般大于零 该函数就是遗传算法中指导搜索的评价函数,1 基本概念,
3、染色体(chromosome) 染色体是由若干基因组成的位串(生物学) 个体对象由若干字符串组成来表示(遗传算法) 遗传算法(genetic algorithm) 染色体就是问题中个体的某种字符串形式的编码表示 染色体以字符串来表示 基因是字符串中的一个个字符,个体 染色体 9 - 1001 (2,5,6)- 010 101 110,1 基本概念,遗传算子(genetic operator) 选择(selection) 交叉(crossover) 变异(mutation),2 选择算子,选择算子 模拟生物界优胜劣汰的自然选择法则的一种染色体运算 从种群中选择适应度较高的染色体进行复制,以生成下
4、一代种群 算法: 个体适应度计算 在被选集中每个个体具有一个选择概率 选择概率取决于种群中个体的适应度及其分布 个体适应度计算,即个体选择概率计算 个体选择方法 按照适应度进行父代个体的选择,2 选择算子,个体适应度计算 按比例的适应度计算(proportional fitness assignment) 基于排序的适应度计算(rank-based fitness assignment) 个体选择方法 轮盘赌选择(roulette wheel selection) 随机遍历抽样(stochastic universal sampling) 局部选择(local selection) 截断选择(
5、truncation selection) 锦标赛选择(tournament selection),2.1 按比例的适应度计算,算法: 对一个规模为N的种群S,按每个染色体xiS的选择概率P(xi)所决定的选中机会,分N次从S中随机选择N个染色体,并进行复制 其中: f为适应度函数 f(xi)为xi的适应度,优胜劣汰 概率越高,随机选中概率越大 概率越高,选中次数越多 适应度高的染色体后代越多,2.2 轮盘赌选择,原理: 做一个单位圆,然后按各个染色体的选择概率将圆面划分为相应的扇形区域 转动轮盘,轮盘静止时指针指向某一扇区,即为选中扇区,相应的个体/染色体即被选中,2.2 轮盘赌选择,算法:
6、 在0, 1区间,产生一个均匀分布的伪随机数r 若rq1,则染色体1被选中 若qk-1 rqk(2 kN),则染色体k被选中 其中 qi为染色体xi(i=1, 2, , n)的累积概率 一个染色体xi被选中的次数,可由期望值e(xi)来确定 为种群S中全体染色体的平均适应度,2.2 轮盘赌选择,上述轮盘选择过程,可描述如下: . 顺序累计群体内各个体的适应度,得相应的累计值Si,最后一个累计值为Sn . 在0, Sn区间内产生均匀分布的随机数r . 依次用Si与r比较,第一个出现Si大于或等于r的个体j被选为复制对象 . 重复 、 项,直至新群体的个体数目等于父代群体的规模,3 交叉算子,交叉
7、算子 交叉又称重组,是按概率交换两个个体的某一位或几位,体现信息的交换 组合出新的个体,实现在串行空间上的有效搜索 生成新个体的主要方法,3 交叉算子,单点杂交 产生一个在1到L1之间的随机数i 配对的两个串相互对应的交换从i1到L的位段,3 交叉算子,例3.1 设染色体s1 = 1011 0111 00 染色体s2 = 0001 1100 11 交换其后2位基因,4 变异算子,变异算子 突变 改变染色体某个/些位上的基因 随机化算子,生成新个体 次要算子,但在恢复群体中失去的多样性方面具有潜在的作用,4 变异算子,例1 设染色体s = 1011 0111 00,5 基本遗传算法,遗传算法 对
8、种群中的染色体反复做三种遗传操作 使其朝着适应度增高的方向不断更新换代,直至出现了适应度满足目标条件的染色体为止 算法拓展 遗传算法在自然与社会现象模拟、工程计算等方面得到了广泛的应用 基本遗传算法是Holland提出的一种统一的最基本的遗传算法,简称SGA(Simple Genetic Algorithm )、CGA(Canonical Genetic Algorithm) 其它的“GA类”算法称为GAs(Genetic Algorithms),可以把GA看作是GAs的一种特例,5 基本遗传算法,参数 种群规模 种群的大小,用染色体个数表示 最大换代数 种群更新换代的上限,也是算法终止一个条
9、件 交叉率Pc 参加交叉运算的染色体个数占全体染色体总数的比例 取值范围:0.4-0.99 变异率Pm 发生变异的基因位数占全体染色体的基因总位数的比例 取值范围:0.0001-0.1 染色体编码 长度L,5 基本遗传算法,算法,步1 :在论域空间U上定义一个适应度函数f(x),给定种群规模N,交叉率Pc, 变异率Pm,代数Gen 步2: 随机产生U中的N个染色体s1,s2sN, 组成初始种群S=s1,s2sN,置代 数t=1 步3:若终止条件满足,则取S中适应度最大的染色体作为所求结果,算法结束 步4:计算S中每个染色体的适应度f() 步5: 按选择概率p(si)所决定的选中机会,每次从S中
10、随机选中1个染色体并将 其复制,共做N次,然后将复制得到的N染色体组成群体S1 步6 :按Pc所决定的参加交叉的染色体数c,从S1中随机确定c个染色体,配对 进行交叉操作,并用产生的染色体代替原染色体,组成群体S2 步7 :按Pm所决定的变异次数m,从S2中随机确定m个染色体,分别进行变异 操作,并用产生的新染色体代替原染色体,组成群体S3 步8 :将群体S3作为新种群,即用S3代替S, Gen = Gen +1,转步3,5 流程图,6 基本实现技术,编码方法 二进制编码 格雷编码 编码规则 应使用能易于产生与所求问题相关的且具有低阶、短定义长度模式的编码方案 应使用能使问题得到自然表示或描述
11、的具有最小编码字符集的编码方案,6 基本实现技术,适应值函数 适应值函数必须是正数 出现负数时应进行变换,常用变换方式有三种: 线性比例法:g(x) = a*f(x)+b (b0) 指数比例法:g(x) = exp(a f(x) (a0) 幂指数比例法:g(x) = (f(x)a (a为偶数),7 算法举例,例2 利用遗传算法求解区间0,31上的二次函数y=x2的最大值 分析 原问题转化为0,31中寻找能使y取最大值的点x 区间0,31为论域空间/解空间 x为个体对象 函数f(x)= x2 可作为适应度函数,7 算法举例,解: 定义适应度函数,编码染色体 适应度函数取f(x)= x2 用5位二
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 遗传 算法 ppt 课件
链接地址:https://www.31doc.com/p-2206503.html