第七章-遗传算法.pdf

第七章 遗传算法 7.1 问题概述 应用微分学方法、运筹学方法求解最优化问题已经很广泛，如产品排产问题、运输调度问题、 最优库存量问题，等等。 这些方法在变量较少、目标与约束条件较少的情况是有效的。对于多 目标下，问题的变量较大与约束条件较多的情况，应用这些方法将存在一定的局限性，甚至由于 难以满足条件可能出现无解。例如多目标下多种证券的最优组合投资问题，多目标下多个生产工 艺参数的最优控制问题，都涉及到求一组较优参数的问题，并以此作为计划或控制的依据。特别 地，许多问题在全局最优解难以获取时，实际只需要求满意解就可以解决问题，此时遗传算法就 显示了较好的优势。 7.2 遗传算法概述 7.2.1 基本概念 遗传算法的基础是基于 Darwin 的进化论和Mendel 的遗传学说。Darwin 进化论最重要的是适 者生存原理。它认为每一物种在发展中越来越适应环境。物种每个个体的基本特征由后代所继承， 但后代又会产生一些异于父代的新变化。在环境变化时，只有那些能适应环境的个体特征方能保 留下来。 Mendel 遗传学说最重要的是基因遗传原理。它认为遗传以密码方式存在细胞中，并以基因形 式包含在染色体内。每个基因有特殊的位置并控制某种特殊性质。所以，每个基因产生的个体对 环境具有某种适应性。基因突变和基因杂交可产生更适应于环境的后代。经过存优去劣的自然淘 汰，适应性高的基因结构得以保存下来。 由于遗传算法是由进化论和遗传学机理而产生的直接有哪些信誉好的足球投注网站优化方法；故而在这个算法中要用 到各种进化和遗传学的概念。一些主要概念如下： (1) 串(String)：它是个体(Individual)的形式，在算法中为二进制串，并且对应于遗传学中的 染色体(Chromosome)。 (2) 群体(Population)：个体的集合称为群体，串是群体的元素。 (3) 群体规模(Population Size)：在群体中个体的数量称为群体规模，又称群体的大小。 (4) 基因(Gene)：基因是串中的元素，基因用于表示个体的特征。例如有一个串 S＝1011， 则其中的 1，0，1，1 这 4 个元素分别称为基因。它们的值称为等位基因(Alletes) 。 247 (5) 基因位置(Gene Position)：一个基因在串中的位置称为基因位置，有时也简称基因位。基 因位置由串的左向右计算，例如在串 S＝1101 中，0 的基因位置是 3 。基因位置对应于 遗传学中的地点(Locus) 。 S (6) 串结构空间 S ：在串中，基因任意组合所构成的串的集合。基因操作是在结构空间中进 行的。串结构空间对应于遗传学中的基因型(Genotype)的集合。 P (7) 参数空间 S ：这是串空间在物理系统中的映射，它对应于遗传学中的表现型(Phenotype) 的集合。 (8) 适应度(Fitness)：表示某一个体对于环境的适应程度。 遗传算法的主要思想，是把在解空间寻找最优解的问题，通过编码形式把解转换为生物空间 对应的染色体（或个体），应用生物空间遗传机理，如交叉、变异等，对染色体或基因进行遗传 进化，使进化后的染色体具有好性质，再对染色体解码转换为解空间对应的解，使这样的解逐步 逼近局部乃至全局最优解。解空间与生物空间的对应见图 7.1 。 x 编码为X 解空间 生物空间 {x | x 是解，x (a,b)} Z={X|X 是染色体} 评价 x 的可行性与 对 X 进行 目标函数 选择、交叉、变异