遗传算法小论文

安徽大学安徽大学 遗传算法期末小论文遗传算法期末小论文 题题 目 目 遗传算法的原理及其发展应用前景遗传算法的原理及其发展应用前景 学生姓名 学生姓名 朱邵成朱邵成 学号 学号 Z15201030 院 系 院 系 电气工程与自动化学院电气工程与自动化学院 专业 专业 模式识别模式识别 教师姓名 教师姓名 吴燕玲吴燕玲 教师所在单位 教师所在单位 安徽大学电气工程与自动化学院安徽大学电气工程与自动化学院 完成时间 完成时间 2016 年年 6 月月 生物的进化是一个奇妙的优化过程 它通过选择淘汰 突然变异 基因遗 传等规律产生适应环境变化的优良物种 遗传算法是根据生物进化思想而启发 得出的一种全局优化算法 遗传算法的概念最早是由 Bagley J D 在 1967 年提出的 而开始遗传算法的理 论和方法的系统性研究的是 1975 年 这一开创性工作是由 Michigan 大学的 J H Holland 所实行 当时 其主要目的是说明自然和人工系统的自适应过程 遗传算法简称 GA Genetic Algorithm 在本质上是一种不依赖具体问题的直 接搜索方法 遗传算法在模式识别 神经网络 图像处理 机器学习 工业优 化控制 自适应控制 生物科学 社会科学等方面都得到应用 在人工智能研 究中 现在人们认为 遗传算法 自适应系统 细胞自动机 混沌理论与人工 智能一样 都是对今后十年的计算技术有重大影响的关键技术 一 遗传算法的基本概念一 遗传算法的基本概念 遗传算法的基本思想是基于 Darwin 进化论和 Mendel 的遗传学说的 Darwin 进化论最重要的是适者生存原理 它认为每一物种在发展中越来越适应 环境 物种每个个体的基本特征由后代所继承 但后代又会产生一些异于父代 的新变化 在环境变化时 只有那些熊适应环境的个体特征方能保留下来 Mendel 遗传学说最重要的是基因遗传原理 它认为遗传以密码方式存在细胞中 并以基因形式包含在染色体内 每个基因有特殊的位置并控制某种特殊性质 所以 每个基因产生的个体对环境具有某种适应性 基因突变和基因杂交可产 生更适应于环境的后代 经过存优去劣的自然淘汰 适应性高的基因结构得以 保存下来 由于遗传算法是由进化论和遗传学机理而产生的直接搜索优化方法 故而在这 个算法中要用到各种进化和遗传学的概念 这些概念如下 一 串 String 它是个体 Individual 的形式 在算法中为二进制串 并且对应于遗传学 中的染色体 Chromosome 二 群体 Population 个体的集合称为群体 串是群体的元素 三 群体大小 Population Size 在群体中个体的数量称为群体的大小 四 基因 Gene 基因是串中的元素 基因用于表示个体的特征 例如有一个串 S 1011 则其中的 1 0 1 1 这 4 个元素分别称为基因 它们的值称为等位基因 Alletes 五 基因位置 Gene Position 一个基因在串中的位置称为基因位置 有时也简称基因位 基因位置由串 的左向右计算 例如在串 S 1101 中 0 的基因位置是 3 基因位置对应于遗传 学中的地点 Locus 六 基因特征值 Gene Feature 在用串表示整数时 基因的特征值与二进制数的权一致 例如在串 S 1011 中 基因位置 3 中的 1 它的基因特征值为 2 基因位置 1 中的 1 它的基因特 征值为 8 七 串结构空间 SS 在串中 基因任意组合所构成的串的集合 基因操作是在结构空间中进行 的 串结构空间对应于遗传学中的基因型 Genotype 的集合 八 参数空间 SP 这是串空间在物理系统中的映射 它对应于遗传学中的表现型 Phenotype 的集合 九 非线性 它对应遗传学中的异位显性 Epistasis 十 适应度 Fitness 表示某一个体对于环境的适应程度 遗传算法还有一些其它的概念 这些概念在介绍遗传算法的原理和执行过程时 再进行说明 二 遗传算法的步骤和意义二 遗传算法的步骤和意义 1 初始化 选择一个群体 即选择一个串或个体的集合 bi i 1 2 n 这个初始 的群体也就是问题假设解的集合 一般取 n 30 160 通常以随机方法产生串或个体的集合 bi i 1 2 n 问题的最优解将通过 这些初始假设解进化而求出 2 选择 根据适者生存原则选择下一代的个体 在选择时 以适应度为选择原则 适应度准则体现了适者生存 不适应者淘汰的自然法则 给出目标函数 f 则 f bi 称为个体 bi 的适应度 以为选中 bi 为下一代个体的 次数 显然 1 适应度较高的个体 繁殖下一代的数目较多 2 适应度较小的个体 繁殖下一代的数目较少 甚至被淘汰 这样 就产生了对环境适应能力较强的后代 对于问题求解角度来讲 就 是选择出和最优解较接近的中间解 3 交叉 对于选中用于繁殖下一代的个体 随机地选择两个个体的相同位置 按交 叉概率 P 在选中的位置实行交换 这个过程反映了随机信息交换 目的在于 产生新的基因组合 也即产生新的个体 交叉时 可实行单点交叉或多点交叉 例如有个体 S1 100101 S2 010111 选择它们的左边 3 位进行交叉操作 则有 S1 010101 S2 100111 一般而言 交叉幌宰 P 取值为 0 25 0 75 4 变异 根据生物遗传中基因变异的原理 以变异概率 Pm 对某些个体的某些位执行 变异 在变异时 对执行变异的串的对应位求反 即把 1 变为 0 把 0 变为 1 变异概率 Pm 与生物变异极小的情况一致 所以 Pm 的取值较小 一般取 0 01 0 2 例如有个体 S 101011 对其的第 1 4 位置的基因进行变异 则有 S 001111 单靠变异不能在求解中得到好处 但是 它能保证算法过程不会产 生无法进化的单一群体 因为在所有的个体一样时 交叉是无法产生新的个体 的 这时只能靠变异产生新的个体 也就是说 变异增加了全局优化的特质 5 全局最优收敛 Convergence to the global optimum 当最优个体的适应度达到给定的阀值 或者最优个体的适应度和群体适应 度不再上升时 则算法的迭代过程收敛 算法结束 否则 用经过选择 交叉 变异所得到的新一代群体取代上一代群体 并返回到第 2 步即选择操作处继续 循环执行 三 三 遗传算法的应用遗传算法的应用 遗传算法在很多领域都得到应用 从神经网络研究的角度上考虑 最关心 的是遗传算法在神经网络的应用 在遗传算法应用中 应先明确其特点和关键 问题 才能对这种算法深入了解 灵活应用 以及进一步研究开发 一 遗传算法的特点 1 遗传算法从问题解的中集开始嫂索 而不是从单个解开始 这是遗传算法与传统优化算法的极大区别 传统优化算法是从单个初始值 迭代求最优解的 容易误入局部最优解 遗传算法从串集开始搜索 复盖面大 利于全局择优 2 遗传算法求解时使用特定问题的信息极少 容易形成通用算法程序 由于遗传算法使用适应值这一信息进行搜索 并不需要问题导数等与问题 直接相关的信息 遗传算法只需适应值和串编码等通用信息 故几乎可处理任 何问题 3 遗传算法有极强的容错能力 遗传算法的初始串集本身就带有大量与最优解甚远的信息 通过选择 交 叉 变异操作能迅速排除与最优解相差极大的串 这是一个强烈的滤波过程 并且是一个并行滤波机制 故而 遗传算法有很高的容错能力 4 遗传算法中的选择 交叉和变异都是随机操作 而不是确定的精确规则 这说明遗传算法是采用随机方法进行最优解搜索 选择体现了向最优解迫 近 交叉体现了最优解的产生 变异体现了全局最优解的复盖 5 遗传算法具有隐含的并行性 遗传算法的基础理论是图式定理 它的有关内容如下 1 图式 Schema 概念 一个基因串用符号集 0 1 表示 则称为一个因式 其中 可以是 0 或 1 例如 H 1x x 0 x x 是一个图式 2 图式的阶和长度 图式中 0 和 1 的个数称为图式的阶 并用 0 H 表示 图式中第 1 位数字和 最后位数字间的距离称为图式的长度 并用 H 表示 对于图式 H 1x x0 x x 有 0 H 2 H 4 3 Holland 图式定理 低阶 短长度的图式在群体遗传过程中将会按指数规律增加 当群体的大 小为 n 时 每代处理的图式数目为 0 n3 遗传算法这种处理能力称为隐含并行性 Implicit Parallelism 它说明遗传 算法其内在具有并行处理的特质 二 遗传算法的应用关键 遗传算法在应用中最关键的问题有如下 3 个 1 串的编码方式 这本质是问题编码 一般把问题的各种参数用二进制编码 构成子串 然 后也就是说 变异增加了全局优化的特质 5 全局最优收敛 Convergence to the global optimum 当最优个体的适应度达到给定的阀值 或者最优个体的适应度和群体适应 度不再上升时 则算法的迭代过程收敛 算法结束 否则 用经过选择 交叉 变异所得到的新一代群体取代上一代群体 并返回到第 2 步即选择操作处继续 循环执行 三 遗传算法在神经网络中的应用三 遗传算法在神经网络中的应用 遗传算法在神经网络中的应用主要反映在 3 个方面 网络的学习 网络的 结构设计 网络的分析 1 遗传算法在网络学习中的应用 在神经网络中 遗传算法可用于网络的学习 这时 它在两个方面起作用 1 学习规则的优化 用遗传算法对神经网络学习规则实现自动优化 从而提高学习速率 2 网络权系数的优化 用遗传算法的全局优化及隐含并行性的特点提高权系数优化速度 2 遗传算法在网络设计中的应用 用遗传算法设计一个优秀的神经网络结构 首先是要解决网络结构的编码 问题 然后才能以选择 交叉 变异操作得出最优结构 编码方法主要有下列 3 种 1 直接编码法 这是把神经网络结构直接用二进制串表示 在遗传算法中 染色体 实 质上和神经网络是一种映射关系 通过对 染色体 的优化就实现了对网络的 优化 2 参数化编码法 参数化编码采用的编码较为抽象 编码包括网络层数 每层神经元数 各 层互连方式等信息 一般对进化后的优化 染色体 进行分析 然后产生网络 的结构 3 繁衍生长法 这种方法不是在 染色体 中直接编码神经网络的结构 而是把一些简单 的生长语法规则编码入 染色体 中 然后 由遗传算法对这些生长语法规则 不断进行改变 最后生成适合所解的问题的神经网络 这种方法与自然界生物 地生长进化相一致 3 遗传算法在网络分析中的应用 遗传算法可用于分析神经网络 神经网络由于有分布存储等特点 一般难 以从其拓扑结构直接理解其功能 遗传算法可对神经网络进行功能分析 性质 分析 状态分析 遗传算法虽然可以在多种领域都有实际应用 并且也展示了它潜力和宽广 前景 但是 遗传算法还有大量的问题需要研究 目前也还有各种不足 首先 在变量多 取值范围大或无给定范围时 收敛速度下降 其次 可找到最优解 附近 但无法精确确定最扰解位置 最后 遗传算法的参数选择尚未有定量方 法 对遗传算法 还需要进一步研究其数学基础理论 还需要在理论上证明它 与其它优化技术的优劣及原因 还需研究硬件化的遗传算法 以及遗传算法的 通用编程和形式等 四 总结四 总结 遗传算法作为一种非确定性的拟自然算法 为复杂系统的优化提供了一种 新的方法 在许多学科领域具有广泛的应用价值 但有关算法的研究 对已经 研究较为深入的热点关注度较高 而对潜在研究热点和迅速发展起来的研究热 点关注度不足 综观遗传算法在算法改进及应用方面的研究现状 它已经成为 目前 计算智能领域的热点之一 但是还有一些不足 总体而言 以下几方面的工作 尤其值得进一步探讨 a 遗传算法与优化技术的融合 对遗传算法的大范围群体搜索性能与快速收敛的局部优化方法进行混 合 从而产生有效的全局优化方法 b 算法的改进以及新型算法的提出 遗传算法虽然是一种有效的全局搜索方法 但在理论和应用研究 上也存在着许多不足和缺陷 针对具体的研究和工程应用 对算法进行改进是 很有必要的 c 混合遗传算法 其实质是将不同算法的优点有机结合 改善单纯遗传算法