遗传算法—一种基于仿生学的计算方法.ppt

爬山的模拟 x y fitness min max search space 不断地通过交叉变异以及选择来达到爬山的效果 爬山的模拟 x y fitness min max search space 不断地通过交叉变异以及选择来达到爬山的效果 爬山的模拟 x y fitness min max search space 最终达到最优 其他复杂函数 * * 遗传算法的应用 * * 计 算 机 系 遗传算法—一种基于仿生学的计算方法 * * 什么是遗传算法（Genetic Algorithm） 生物进化 生命自从在地球上诞生以来，就开始了漫长的生物演化历程，低级、简单的生物类型逐渐发展为高级、复杂的生物类型。这一过程已经由古生物学、胚胎学和比较解剖学等方面的研究工作所证实。生物进化的原因自古至今有着各种不同的解释，其中被人们广泛接受的是达尔文的自然选择学说。 达尔文 * * 1825年至1828年在爱丁大学学医，后进入剑桥大学学习神学。1831年从剑桥大学毕业后，以博物学家的身份乘海军勘探船“贝格尔号（Beagle）”作历时5年（1831－1836）的环球旅行，观察和搜集了动物、植物和地质等方面的大量材料，经过归纳整理和综合分析，形成了生物进化的概念。1859年出版《物种起源（On? the Origin of Species）》一书，全面提出以自然选择（Theory of Natural Selection）为基础的进化学说。该书出版震动当时的学术界，成为生物学史上的一个转折点。自然选择的进化学说对各种唯心的神造论、目的论和物种不变论提出根本性的挑战。使当时生物学各领域已经形成的概念和观念发生根本性的改变。 达尔文（Charles Robert Darwin，1809－1882）英国博物学家，进化论的奠基人。1809年2月12日，出生于英国医生家庭。 自然选择学说 * * 自然选择学说认为，生物要生存下去，就必须进行生存斗争。生存斗争包括种内斗争、种间斗争以及生物与无机环境之间的斗争三个方面。在生存斗争中，具有有利变异(mutation)的个体容易存活下来，并且有更多的机会将有利变异传给后代，具有不利变异的个体容易被淘汰，产生后代的机会也少得多。因此，凡是在生存斗争中获胜的个体都是对环境适应性比较强的。达尔文把这种在生存斗争中适者生存、不适者淘汰的过程叫做自然选择。达尔文的自然选择学说表明，遗传和变异是决定生物进化的内在因素。 遗传算法的起源 * * 20世纪60年代中期，美国Michigan（密西根）大学的John Holland提出了位串编码技术，这种编码既适合于变异又适合杂交操作，并且他强调将杂交作为主要的遗传操作。随后，Holland将该算法用于自然和人工系统的自适应行为的研究之中，并于1975年出版其开创性的著作《Adaptation in Natural and Artificial Systems》。后来，Holland与他的学生们将该算法加以推广并应用到优化及机器学习等问题之中，而且正式定名为遗传算法。遗传算法的通用编码技术及简单有效的遗传操作为其广泛的应用和成功奠定了基础。 遗传算法出现的目的 解决经典数学方法无法有效地求出 最优解的复杂的、大规模的难题。 * * 遗传算法实现之基础 计算机计算 随机数 迭代（循环） * * 遗传算法之有效性保证 用计算机模拟自然杂交与变异的过程 用计算机模拟自然选择的过程 * * 遗传算法的基本概念 * * 考虑如下优化问题： 这里f是X上的一个正值函数，即对任意x∈X，f(x)0。X是问题的解空间，即问题的所有可能解全体。它可以是一个有限集合(如组合优化问题)，也可以是实空间Rn的一个子集(如连续优化问题)等。 对以上问题，我们通常用两类方法来求解之，一类是解析法，通过一定的手段直接计算出问题的解，另一类是迭代法，给出问题的一个初始猜测，然后从此初始点出发，逐步迭代，直至达到停机条件。演化算法也是一种迭代法，但它有别于传统的迭代法。 遗传算法的步骤 确定编码方案 确定适应值函数 选择策略的确定 遗传算子的设计 确定算法的终止准则 控制参数的选取 编程上机运行 * * 特点：随机地、迭代地、不厌其烦地去寻找最优解！ 遗传算法流程图 * * 开始 随机初始化种群P(0),t?0 计算P(0)中每个个体的适应值 终止? 杂交 计算P(t)中每个个体的适应值 变异 择优生成新种群（选择） t?t+1 输出t代优良品种 输出最优个体 结束 遗传算法的循环过程 * * 实例 * * 目标及其目标函数： 显然在区间[-1，1]上在x=0处达到最大。 (1)确定编码方案 * * 变量作为实数，可以视为演化算法的表现型形式。从表现型到