计算智能理论讲义遗传算法绪论.ppt

计算智能理论——遗传算法 第一章 遗传算法绪论 谢娟英 xiejuany@snnu.edu.cn 计算智能的分支 进化计算 进化计算核心思想的渊源 进化计算技术的核心思想源于：生物进化过程（从简单到复杂，从低级到高级）本身是一个自然的、并行发生的、稳健的优化过程。这一优化过程的目标是对环境的自适应性，生物种群通过“优胜劣汰”及遗传变异来达到进化（优化）的目的。依据达尔文的自然选择与孟德尔的遗传变异理论，生物的进化是通过繁殖、变异、竞争和选择这四种基本形式实现的。因而，如果把待解决的问题理解为对某个目标函数的的全局优化，则进化计算既是建立在模拟上述生物进化过程基础上的随机搜索优化技术。 根据这一观点，遗传算法、进化策略与进化规划等均可解释为进化计算的不同执行策略，他们分别从基因的层次和种群的层次实现对生物进化过程的模拟。 进化计算的特点及其应用 特点： 具有鲜明的生物背景 适用于任意函数类 应用： 由于其上述特点，进化计算自60年代中期以来引起众多领域的普遍关注，被广泛应用于机器学习、人工神经网络、程序自动生成、专家系统的知识库维护等一系列超大规模、高等非线性、不连续、多峰函数的优化。 遗传算法—仿生算法 遗传算法是一种更为宏观意义下的仿生算法，它模仿的机制是一切生命与智能的产生与进化过程。它通过模拟达尔文的“优胜劣汰、适者生存” 原理鼓励产生好的结构，通过模仿孟德尔的遗传变异理论在迭代过程中保持已有的结构，同时寻找更好的结构。 遗传算法是借鉴生物的自然选择和遗传进化机制而开发出的一种全局优化自适应概率搜索算法。 遗传算法使用群体搜索技术，通过对当前群体施加选择、交叉、变异等一系列遗传操作，从而产生出新一代的群体，并逐步使群体进化到包含或接近最优解的状态。 遗传算法的特点 作为一种随机优化与搜索方法，遗传算法有如下特点： 并行性: 遗传算法的操作对象是一组可行解，而非单个可行解；搜索轨道有多条，而非单条，因而具有良好的并行性。 通用性：只需利用目标函数的取值信息，而无需梯度等高价信息，适用于大规模、高度非线性的不连续多峰函数的优化及无解析表达式的目标函数的优化。 全局优化性能和稳健性：其择优机制是一种“软”决策，加上其良好的并行性，使它具有良好的全局优化性能和稳健性。 可操作性和简单性：遗传算法操作的可行解集是经过编码的，目标函数可解释为编码化个体（可行解）的适应性，因而具有良好的可操作性和简单性。 遗传算法的应用 遗传算法由于具有思想简单、易于实现、应用效果明显等优点而被众多应用领域所接受，并在自适应控制、组合优化、模式识别、机器学习、人工生命、管理决策等领域得到了广泛的应用。 遗传算法呈现出一种通用的算法框架，该框架不依赖于问题的种类。 遗传算法是一种具有较强鲁棒性的优化算法，特别是对于一些大型、复杂非线性系统，它更表现出了比其他传统算法更加独特和优越的性能。 隐含并行性和全局搜索特性是遗传算法的两大显著特征。 1.1 遗传算法的生物学基础 1.1 遗传算法的生物学基础 1.1 遗传算法的生物学基础 DNA中，遗传信息在一条长链上按一定的模式排列，亦即进行了编码。 基因座(Locus)：遗传基因在染色体中占据的位置。 等位基因(Allele): 同一基因座可能有的全部基因。 基因型(Genotype): 某种生物所特有的基因及其构成形式称为该生物的基因型。 表现型(Phenotype)：生物在环境中呈现出的相应性状称为该生物的表现型。 基因组(Genome): 一个细胞中所有染色体所携带的遗传信息的全体称为一个基因组。 1.1 遗传算法的生物学基础 细胞在分裂时，遗传物质DNA通过复制(Reproduction)而转移到新产生的细胞中，新细胞继承了旧细胞的基因。有性生殖生物在繁殖下一代时，两个同源染色体之间通过交叉(Crossover)而重组，亦即在两个染色体的某一相同位置处DNA被切断，其前后两串分别交叉组合而形成两个新的染色体。另外在进行细胞复制时，虽然概率很小，但也有可能产生某些复制差错，从而使DNA发生某种变异(Mutation)，产生出新的染色体。这些新染色体表现出新的性状。如此这般，遗传基因或染色体在遗传的过程中由于各种各样的原因而发生变化。 1.1 遗传算法的生物学基础 进化：生物在其延续生存的过程中，逐渐适应于其生存环境，使得其品质不断得到改良，这种生命现象成为进化(Evolution)。 生物的进化以集团的形式共同进行，这样一个团体称为群体(Population)， 组成群体的单个生物称为个体(individual)，每个个体对其生存环境都有不同的适应能力，这种适应能力称为个体的适应度(Fitness)。 1.1 遗传算法的生物学基础 达尔文的自然选择学说(Natural Selection)认