《第九章 基因算法》由会员分享，可在线阅读，更多相关《第九章 基因算法（75页珍藏版）》请在金锄头文库上搜索。
1、第九章 遗传算法（Genetic Algorithm, GA）一、概述 一、概述An EA is an iterative procedure which evolves a population of individuals Each individual is a candidate solution to a given problem Each individual is evaluated by a fitness function, which measures the quality of its candidate solution At each iteration (gen
2、eration): The best individuals are selected Genetic operators are applied to selected individuals in order to produce new individuals (offspring) New individuals are evaluated by fitness function Basic Ideas of Evolutionary Algorithms (EAs)Basic Flow Chart of EAs create initial populationcompute fit
3、ness select best individuals (based on fitness)modify best individuals, producing offspring compute fitness of offspringNstop?YReturn best individual (solution)一、概述 What is evolution? Evolution is a gradual process of change in the genetic composition of a population, as a result of natural selectio
4、n acting on genetic variation among individuals Basic Elements of an Evolutionary Process: Reproduction with inheritance Genetic variation (usually produced by random modifications) Natural selection (survival of the fittest) Evolutionary Biology一、概述遗传遗传 学 GA 染色体（Chromosome） 数据、数组组、位串 基因（gene） 位 等位基
5、因（allele） 特性值值 基因座（locus） 串中位置 基因型（genotype） 解结结构（基因空间间） 表现现型（phenotype） 解结结构（问题问题 空间间） 遗传算法是模拟遗传选择，优胜劣汰，适者生存的 生物进化过程的计算模型。它是由美国Michigan 大 学的J. Holland教授于1975年首先提出的。 遗传和变异是决定生物进化的内在因素。生物体通 过对基因的复制和交叉的操作使其性状的遗传得到 选择和控制，使生物界的物种能够保持相对的稳定 ；同时，通过基因组合、基因变异等操作产生丰富 多样的新性状，新物种，推动了生物的进化和发展 。 GA是一种新的全局优化随机搜索算法
6、。GA搜索不依 赖梯度信息，简单通用、鲁棒性强，适合并行分布 处理，应用范围广，尤其适用于解决传统方法难以 解决的复杂和非线性问题。二、遗传算法初始群体评估每个个体选择交叉结束是否优解？开始解编码评估函数遗传操作标准的遗传算法是具有“ 生成 + 检测 （generate-and-test） 迭代过程的搜索算法。遗传算法通过迭代进化， 从一群初始解找到所期望 的解新群体变异 遗传算法（SGA）l 爬山法或梯度法仅能到 达局部最优解GA versus “Traditional” search/optimization algorithmsl 模拟退火算法允许以一定 的概率降低到较小的适应 度，从而
7、获得越过低谷， 爬上全局高峰的机会二、遗传算法l GA或EAs 是一种多点并行分布式全局优化搜索算法二、遗传算法 多点并行搜索 基本上不用搜索空间的知识，仅用适应度函数来评估。适应度函数不 受连续可谓的约束，对定义域可以任意设置。对适应函数唯一要求是输 出为正，以便比较。 GA不是直接处理问题参数，而是对参数集进行编码后进行处理。为此 ，GA可直接对结构对象进行操作。如集合、序、列、矩阵、树、图、链 和表等一维或二维甚至三维结构对象，扩大了应用范围。 通过对权矩阵的操作，GA可以对NN的权甚至结构进行优化。 通过对集合的操作，GA可以实现规则集或知识库的自适应优化 通过对树的操作，GA可得到用
8、于分类的最佳决策树。 GA不是采用确定规则，而是采用概率的搜索规则。但是，GA不是一种 盲目搜索方法，而是有明确的搜索方向。 增量式进化 遗传算法的特点二、遗传算法尤其当： 其他各种方法太慢或过 于复杂 求解的问题类似于GA已 成功应用的问题 搜索空间太大且包含相 当多的局部解 多目标优化 变化环境或噪声环境 GA应用：二、遗传算法三、SGA Encoding technique (gene, chromosome) Initialization procedure (creation) Evaluation function (environment) Selection of parent
9、s (reproduction) Genetic operators (mutation, crossover) Parameter settings (practice and art) SGA中的关键要素13三、SGA SGA采用二进制编码，这是最简单也较常用的个体表 示方法 Chromosomes could be: Bit strings (0101 . 1100) Real numbers (43.2 -33.1 . 0.0 89.2) Permutations of element (E11 E3 E7 . E1 E15) Lists of rules (R1 R2 R3 . R2
10、2 R23) Program elements (genetic programming) . any data structure .nRepresentation（encoding）三、SGAEvaluationEvaluated generationgenerationnEvaluation： GA基本上不用外部信息，仅用适应度函数来评估每个个体 。 评估时需要decoding，即把genotype解转换为phenotype 解，以便利用评估函数或适应函数。X(=39) Coding and decoding解（个体）在问题空间和遗传空间的转换，即phenotype解和genotype解
11、之间的转换。三、SGA 利用赌轮（ roulette wheel）法 fitness proportionate expected no. of representatives of each individual is proportional to its fitnessn选择（Selection）三、SGAf1f2f3f4f5f6f7n=7roulette wheel三、SGA根据概率的大小 将将圆盘分为 n个 扇形，每个扇形的 大小为 选择时转动轮盘 ，参考点r落到扇 形i则选择个体i 。 从一对父辈产生一对子辈 单点交叉 交叉概率 pc typically in range 0.5,
12、 1.0 Crossover 是GA最本质的遗传算子: 在进化中，能加速搜索 能形成schemata的有效组合(subsolutions on different chromosomes)nCrossover(recombination)三、SGAOne-Point Cross-Over三、SGAparentsChildren bitwise mutation probability of mutation: pm equal probability for each gene/bit typically chosen to be smallrang: 0.001, 0.1 few mutat
13、ions per individual depends on nature of problemnMutation三、SGABefore: (1 1 1 1 0 1 1 0)After: (1 1 1 0 0 1 1 0)Before: (1.38 -69.4 326.44 0.1)After: (1.38 -67.5 326.44 0.1)三、SGAExamples: 三、SGA representation each chromosome contain 8 ”genes”,coding for letters fitness-functionfitness be the number o
14、f correct lettersexample2：problem : correctly spelling “SEQUENCE” with GACrossoverand mutation三、SGA Typically, the populations average fitness will initially increase rapidly, and then gradually converge四、 GA的理论概述 模式(schema)基于字符集0,1,*所产生的能描述具有某些结 构相似性的0，1字符串例：模式H 0*1 描述了具有相似结构的四个个 体0001， 0011， 0111，
15、0101显然，一个个体可有包含多个模式，一个模式可 以存在于多个个体中，如果说最优个体（解）对应一个明确的字符串或 模式，那么遗传算子作用就是使群体中的个体模式 不断地向优解逼近。 模式阶( schema order)模式H中有确定值的基因座个数称为模式H的阶 O(H)如： 模式011*1*的阶数O(H)=4 模式0*的阶数O(H)=1显然，一个模式的阶数越低，其生存能力越强 定义距(defining length)模式H中第一个有确定值的基因座和最后一个有确定 值的基因座之间的距离(H)如： 模式011*1*的定义距(H)=4 模式0*的定义距(H)=0显然，一个模式的阶数越低，其生存能力越强四、 GA的理论概述遗传算子对模式的影响着眼某个模式H，考虑遗传操作（再生、交叉和变 异）对包含该模式的个体数的影响 再生（reproducti
