遗传算法XX讲解材料

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