第6章遗传算法研究.ppt

第六章 遗传算法 6.1遗传算法概述 6.2基本遗传算法 6.3遗传算法数学基础 6.4遗传算法的改进 6.1 遗传算法概述 一、简介 遗传算法(Genetic Algorithms, GA)是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概率搜索算法. 遗传算法吸取了自然生物系统“适者生存”的进化理论，将达尔文的进化理论引入人工系统串结构的改造中，使得串结构及其携带的信息发生有组织的而又是随机的变换和组合，并使该过程按物种进化规律来操作运行，设法使物种的优良品质在组合中加以保留，从而不断产生出更佳的个体后代。 6.1 遗传算法概述 二、发展简史 20世纪50年代，生物学家Fraser试图通过计算的方法来模拟生物界“遗传与选择”的进化过程 。 20世纪60年代，1975年Holland教授出版了遗传算法历史上的经典著作《Adaptation in Natural and Artificial Systems》，首次提出遗传算法的概念 。 20世纪80年代，迅速发展 ，1989年，Holland的学生Goldberg出版了《Genetic Algorithms in Search ,Optimization and Machine Learning》 一书，为这一领域奠定了坚实的科学基础。 20世纪90年代，随着计算机技术的发展，遗传算法在各个领域得到了广泛的应用。不同领域的专家、学者根据各自的实际问题，构造出了多种能很好地解决行业问题新的遗传算法。 6.1 遗传算法概述 三、遗传算法的特点 全局性 并行性和高效性 鲁棒性 普适性和易扩性 简明性 6.2 基本遗传算法 一、基本原理 1、基本术语 染色体：遗传物质的主要载体，指多个遗传因子的集合。 个体：指染色体带有特征的实体称个体 种群：染色体带有特征个体的集合称为群体，该集合内的个体书称为群体的大小。 编码：从表现型到遗传子型的映射称为编码 适应度：各个个体对各自适应环境的程度称为适应度。 选择：指决定以一定的概率从群体中选择若干对个体的操作称为选择。 交叉：把两个染色体换组的操作称为交叉，又称重组。 变异：让遗传因子以一定的概率变化的操作称为变异 解码：从遗传子型到表现型的映射称为解码 6.2 基本遗传算法 2、基本原理与流程 6.2 基本遗传算法 3、遗传算法的基本操作 设有函数 ,用遗传算法求其自变量x在区间[0，31]取整数时最大值 （1）初始种群 （2）复制 根据目标函数适应度的计算，从初始种群中挑选适应度高的个体进行复制。通常可把目标函数制定成获得的利益、利润、功效等指标的量度函数。这里，可把目标函数值确定为适应值。 适应值相当于自然界中的一个生物为了生存所具备的各项能力的大小，决定了该染色体被复制还是被淘汰。 6.2 基本遗传算法 6.2 基本遗传算法 根据上表数据，对应轮盘赌转盘的随机方法，绘制出轮盘赌转盘。 6.2 基本遗传算法 旋转4次轮盘，就产生4个染色体，这4个染色体是上一代种群中有选择的复制，有的可能被复制一次或多次，有的则可能被淘汰。 （3）交叉 不但复制出优秀的染色体，而且还要创造出新的染色体。交叉操作模拟生物进化过程的繁殖现象，通过两个染色体的交换组合，从而产生新的优良品种。 交叉步骤：（1）将复制产生的染色体随机两两匹配，称之为双亲的染色体；（2）将双亲的染色体进行交叉繁殖。 6.2 基本遗传算法 （4）变异 以很小的概率随机地改变遗传基因的值，模拟生物在自然环境中，由于某种偶然因素引起的基因突变。假设只有复制和交叉，没有变异操作，就无法在初始基因族组以外的空间进行搜索，可能使进化过程较早陷入局部解而失去某种特殊的进化途径。 对于二进制编码表示的染色体数字符串中，随机地将染色体的某一个基因，即染色体的数字符串的某一位的数值由1变成0，或由0变成1。 变异的概率比较小，通常取千分之一二，但变异操作增加了基因类型的多样性，使搜索能在尽可能大的空间进行，得到更优化的解。 假设变异概率为0.001，则对于种群总共有20个基因位，期望的变异串位数为20X0.001=0.02位，所以这里没有基因位数值的改变。 6.2 基本遗传算法 二、遗传算法的设计与实现 1、编码 利用遗传算法进行问题求解时,首先确定问题的目标函数和变量,然后对其进行编码。这样做主要是因为在遗传算法中,问题的解是用数字串来表示的，而遗传操作算子也是直接对串进行操作的。编码方式常用的有二进制