遗传算法简介.ppt

遗传算法 遗传算法的基本思想是基于Darwin进化论和Mendel的遗传学说的 Darwin进化论最重要的是适者生存原理 它认为每一物种在发展中越来越适应环境 物种每个个体的基本特征由后代所继承 但后代又会产生一些异于父代的新变化 在环境变化时 只有那些能适应环境的个体特征方能保留下来 Mendel遗传学说最重要的是基因遗传原理 它认为遗传以基因形式包含在染色体内 每个基因有特殊的位置并控制某种特殊性质 所以 每个基因产生的个体对环境具有某种适应性 基因突变和基因杂交可产生更适应于环境的后代 经过存优去劣的自然淘汰 适应性高的基因结构得以保存下来 遗传与进化的系统观 生物的所有遗传信息都包含在染色体中 染色体决定生物的性状 染色体是由基因及其有规律的排列构成 遗传进化过程发生在染色体上 生物的繁衍由基因的复制过程完成 通过同源染色体之间的交叉或染色体的变异会产生新物种 使生物呈现新性状 对环境适应性好的基因比适应性差的基因有更多机会遗传到下一代 遗传算法的基本概念 由于遗传算法是由进化论和遗传学机理而产生的直接搜索优化方法 故而在这个算法中要用到各种进化和遗传学的概念 这些概念如下 串 String 它是个体 Individual 的形式 在算法中为二进制串 并且对应于遗传学中的染色体 Chromosome 群体 Population 个体的集合称为群体 串是群体的元素 群体大小 PopulationSize 在群体中个体的数量称为群体的大小 遗传算法的基本概念 基因 Gene 基因是串中的元素 用于表示个体的特征 例如有一个串S 1011 则其中的1 0 1 1这4个元素分别称为基因 它们的值称为等位基因 Alletes 基因位置 GenePosition 一个基因在串中的位置称为基因位置 有时也简称基因位 基因位置由串的左向右计算 例如在串S 1101中 0的基因位置是3 基因位置对应于遗传学中的地点 Locus 基因特征值 GeneFeature 在用串表示整数时 基因的特征值与二进制数的权一致 例如在串S 1011中 基因位置3中的1 它的基因特征值为2 基因位置1中的1 它的基因特征值为8 遗传算法的基本概念 串结构空间SS在串中 基因任意组合所构成的串的集合 基因操作是在结构空间中进行的 串结构空间对应于遗传学中的基因型 Genotype 的集合 参数空间SP这是串空间在物理系统中的映射 它对应于遗传学中的表现型 Phenotype 的集合 非线性它对应遗传学中的异位显性 Epistasis 适应度 Fitness 表示某一个体对于环境的适应程度 遗传算法的基本实现 编码 GA在进行搜索之前先将解空间的解数据表示成遗传空间的基因型数据 这些数据的不同组合便构成了不同的点 初始群体的生成 随机产生N个初始串结构数据 每个串结构数据称为一个个体 N个个体构成了一个群体 GA以这N个串结构数据作为初始点开始迭代 适应性值评估检测 适应性函数表明个体或解的优劣性 不同的问题 适应性函数的定义方式也不同 遗传算法的基本实现 选择 选择的目的是为了从当前群体中选出优良的个体 使它们有机会作为父代为下一代繁殖子孙 遗传算法通过选择过程体现这一思想 进行选择的原则是适应性强的个体为下一代贡献一个或多个后代的概率大 选择实现了达尔文的适者生存原则 交换 交换操作是遗传算法中最主要的遗传操作 通过交换操作可以得到新一代个体 新个体组合了其父辈个体的特性 交换体现了信息交换的思想 变异 变异首先在群体中随机选择一个个体 对于选中的个体以一定的概率随机地改变串结构数据中某个串的值 同生物界一样 GA中变异发生的概率很低 通常取值在0 001 0 01之间 变异为新个体的产生提供了机会 遗传算法的基本实现 GA的计算过程为 选择编码方式 产生初始群体 计算初始群体的适应性值 如果不满足条件 选择交换变异计算新一代群体的适应性值 一 遗传算法的描述 例子 为四个连锁饭店寻找最好的经营决策 其中一个经营饭店的决策包括要做出以下三项决定 1 价格汉堡包的价格应该定在50美分还是1美元 2 饮料和汉堡包一起供应的应该是酒还是可乐 3 服务速度饭店应该提供慢的还是快的服务 目的 找到这三个决定的组合以产生最高的利润 共有8种表示方案 用遗传算法解这个问题的第一步就是选取一个适当的表示方案 表1饭店问题的表示方案 其中的4个 群体规模N 4 表2初始群体中经营决策的适应值 一个简单的遗传算法由选择 交叉 变异三个算子组成 表3使用选择算子后产生的交叉池 1 选择算子 比例选择 2 交叉算子 采用单点交叉 作用过程 a 产生一个在1到l 1之间的随机数ib 配对的两个串相互对应的交换从i 1到l的位段 例如 从交叉池中选择编号为1和2的串进行交叉 且交叉点选在2 用分隔符 表示 交叉算子作用的结果为 01 101011 0111 对交叉池中指定百分比的个体应用交叉算子 假设交叉概率pc 50 交叉池中余下的50 个体仅进行复制运算 即复制概率pr 50 表4使用复制和交叉算子的作用结果 遗传算法利用复制和交叉算子可以产生具有更高平均适应值和更好个体的群体 3 变异算子 以一个很小的概率pm随机改变染色体串上的某些位 对于二进制串 就是将相应位上的0变为1或将1变为0 例如 选交叉池中编号为4的串进行变异 且变异点在2 则010000 变异算子相对而言 是次要算子 但在恢复群体中失去的多样性方面具有潜在的作用 小结 上述遗传算法描述了从第0代产生第1代的过程 然后遗传算法迭代地执行这个过程 直到满足某个停止准则 在每一代中 算法首先计算群体中每个个体的适应值 然后利用适应值信息 遗传算法分别以概率pc pr和pm执行交叉 复制和变异操作 从而产生新的群体 应用遗传算法求解问题需完成四个主要步骤 1 确定表示方案 2 确定适应值度量 3 确定控制算法的参数和变量 4 确定指定结果的方法和停止运行的准则 基本遗传算法的构成要素 1 染色体编码方法最常用的是二进制编码 对于离散性变量直接编码 对于连续性变量先离散化后再编码 2 适应度函数评估函数 用来评估一个染色体的优劣的绝对值 适应度函数 评估一个染色体相对整个群体的优劣的相对值的大小 3 遗传算子复制算子 交叉算子 变异算子 4 基本遗传算法运行参数 N 群体大小 即群体中所含个体的数量 一般取20 100 T 遗传算法的终止进化代数 一般取100 500 pc 交叉概率 一般取0 25 0 75 pm 变异概率 一般取0 01 0 2 pr 复制概率 三 基本遗传算法的一般框架 算法过程 1 随机产生一个由确定长度的特征串组成的初始群体 2 对串群体迭代地执行下面的步 i 和步 ii 直到满足停止准则 i 计算群体中每个个体的适应值 ii 应用复制 杂交和变异算子产生下一代群体 3 把在任一代中出现地最好的个体串指定为遗传算法的执行结果 这个结果可以表示问题的一个解 或近似解 定理 收敛性定理 如果在代的演化过程中 遗传算法保留最好的解 并且算法以交叉和变异作为随机化算子 则对于一个全局优化问题 随着演化代数趋向于无穷 遗传算法将以概率1找到全局最优解 遗传算法极限特性的分析表明算法能够对搜索空间进行持续的搜索 因此遗传算法特别适合于在全局优化问题中应用 遗传算法的特点 1 搜索过程不直接作用在变量上 而是在参数集进行了编码的个体 此编码操作 使得遗传算法可直接对结构对象 集合 序列 矩阵 树 图 链和表 进行操作 不存在求导和函数连续性的限定 2 遗传算法不是从单个点 而是从一个点的群体开始搜索 同时利用了多个搜索点的信息 3 具有内在的隐并行性和较好的全局寻优能力 4 采用概率寻优方法 能自动获取搜索过程中的有关知识并用于指导优化 自适应地调整搜索方向 不需要确定的规则 5 鲁棒性 数据挖掘 数据挖掘的概念 网络之后的下一个技术热点是什么 让我们来看一些身边俯拾即是的现象 纽约时报 由60年代的10 20版扩张至现在的100 200版 最高曾达1572版 然而在现实社会中 人均日阅读时间通常为30 45分钟 只能浏览一份24版的报纸 大量信息在给人们带来方便的同时也带来了一大堆问题 第一是信息过量 难以消化 第二是信息真假难以辨识 第三是信息安全难以保证 第四是信息形式不一致 难以统一处理 人们开始提出一个新的口号 要学会抛弃信息 人们开始考虑 如何才能不被信息淹没 而是从中及时发现有用的知识 提高信息利用率 数据挖掘的概念 数据爆炸但知识贫乏另一方面 随着数据库技术的迅速发展以及数据库管理系统的广泛应用 人们积累的数据越来越多 激增的数据背后隐藏着许多重要的信息 人们希望能够对其进行更高层次的分析 以便更好地利用这些数据 目前的数据库系统可以高效地实现数据的录入 查询 统计等功能 但无法发现数据中存在的关系和规