算法导论课件第24讲算法高级讲座1章节

《算法导论课件第24讲算法高级讲座1章节》由会员分享，可在线阅读，更多相关《算法导论课件第24讲算法高级讲座1章节（56页珍藏版）》请在金锄头文库上搜索。

1、算法高级讲座1,绪论 1.1 遗传算法的生物学基础 生物在自然界中的生存繁衍，显示出了其对自然环境的自适应能力。受其启发， 人们致力于对生物各种生存特性的机理研究和行为模拟，为人工自适应系统的设计 和开发提供了广阔的前景。遗传算法(Genetic Algorithms，简称GAs)就是这种生物 行为的计算机模拟中令人瞩目的重要成果。基于对生物遗传和进化过程的计算机模 拟，遗传算法使得各种人工系统具有优良的自适应能力和优化能力。 遗传算法所借鉴的生物学基础就是生物的遗传和进化。 1.1.1 遗传与变异 遗传(Heredity) 世间的生物从其父代继承特性或性状，这种生命现象就称为 遗传(Here

2、dity)，由于遗传的作用，使得人们可以种瓜得瓜、 种豆得豆，也使得鸟仍然是在天空中飞翔，鱼仍然是在水中邀 游。, 构成生物的基本结构和功能的单位是细胞(Ce11)。 细胞中含有的一种微小的丝状化合物称为染色体(Chromosome)，生物的所有遗 传信息都包含在这个复杂而又微小的染色体中。 基因 经过生物学家的研究，控制并决定生物遗传性状的染色体主要是由一种叫做脱 氧核糖核酸(deoxyribonucleic acid 简称DNA)的物质所构成。 DNA在染色体中有 规则地排列着，它是个大分子的有机聚合物，其基本结构单位是核苷酸，许多核苷 酸通过磷酸二酯键相结合形成一个长长的链状结构，两个链

3、状结构再通过碱基间的氢键有 规律地扭合在一起，相互卷曲起来形成一种双螺旋结构。基因就是DNA长链结构中占有一 定位置的基本遗传单位。 遗传信息是由基因(Gene)组成的，生物的各种性状由其相应的基因所控制。 基因是遗传的基本单位。细胞通过分裂具有自我复制的能力，在细胞分裂的过 程中，其遗传基因也同时被复制到下一代，从而其性状也被下一代所继承。, 遗传基因在染色体中所占据的位置称为基因座(Locus)； 同一基因座可能有的全部基因称为等位基因(Allele)； 某种生物所特有的基因及其构成形式称为该生物的基因型(Genotype)； 而该生物在环境中呈现出的相应的性状称为该生物的表现型(Phen

4、otype)； 一个细胞核中所有染色体所携带的遗传信息的全体称为一个基因组(Genome)。,生物的遗传方式： 1. 复制 生物的主耍遗传方式是复制。遗传过程中，父代的遗传物质DNA被复制到子 代。即细胞在分裂时，遗传物质DNA通过复制(Reproduction)而转移到新生的细 胞中，新细胞就继承了旧细胞的基因。 2. 交叉 有性生殖生物在繁殖下一代时，两个同源染色体之间通过交叉(Crossover)而重 组，亦即在两个染色体的某一相同位置处DNA被切断，其前后两串分别交义组合 而形成两个新的染色体。 3. 变异 在进行细胞复制时，虽然概率很小，仅仅有可能产生某些复制差错，从而使 DNA发生

5、某种变异(Mutation)，产生出新的染色体。这些新的染色体表现出新的 性状。 如此这般，遗传基因或染色体在遗传的过程中由于各种各样的原因而发生变化。,1.1.2 进化 地球上的生物，都是经过长期进化而形成的。根据达尔文的自然选择学说，地 球上的生物具有很强的繁殖能力。在繁殖过程中，大多数生物通过遗传，使物种 保持相似的后代；部分生物由于变异，后代具有明显差别，甚至形成新物种。正 是由于生物的不断繁殖后代，生物数目大量增加，而自然界中生物赖以生存的资 源却是有限的。因此，为了生存，生物就需要竞争。生物在生存竞争中，根据对 环境的适应能力，适者生存，不适者消亡。自然界中的生物，就是根据这种优胜

6、 劣汰的原则，不断地进行进化。 生物的进化是以集团的形式共同进行的，这样的一个团体称为群体(Population)， 或称为种群。 组成群体的单个生物称为个体(Individual)， 每一个个体对其生存环境都有不同的适应能力，这种适应能力称为个体的适应度(Fitness)。,1.1.3 遗传与进化的系统观 虽然人们还未完全揭开遗传与进化的奥秘，即没有完全掌握其机制、也不完全 清楚染色体编码和译码过程的细节，更不完全了解其控制方式，但遗传与进化的 以下几个特点却为人们所共识： (1) 生物的所有遗传信息都包含在其染色体中，染色体决定了生物的性状； (2) 染色体是由基因及其有规律的排列所构成的

7、，遗传和进化过程发生在染色体上； (3) 生物的繁殖过程是由其基因的复制过程来完成的； (4) 通过同源染色体之间的交叉或染色体的变异会产生新的物种，使生物呈现新的 性状。 (5) 对环境适应性好的基因或染色体经常比适应性差的基因或染色体有更多的机会 遗传到下一代。,1.2 遗传算法简介 遗传算法是模拟生物在自然环境下的遗传和进化过程而形成的一种自适应全局 优化概率搜索方法。 它最早由美国密西根大学的H.Holland教授提出，起源于60年代对自然和人工 自适应系统的研究； 1967年，Bagley发表了关于遗传算法应用的论文，在其论文中首次使用“遗传算法（ Genetic Algorithm

8、）”一词。 70年代 De Jong基于遗传算法的思想在计算机上进行了大量的纯数值函数优化 计算实验。 在一系列研究工作的基础上，80年代由Goldberg进行归纳总结，形成了遗传算法的基本框架。,1.2.1 遗传算法概要 对于一个求函数最大值的优化问题（求最小值也类同），一般可描述为下述数 学规划模型： max f(X) (1-1) s.t. XR (1-2) RU (1-3) 其中： Xx1,x2,xnT为决策变量， f(X)为目标函数， 式(1-2)、(1-3)为约束 条件， U是基本空间， R是U的一个子集。 满足约束条件的解X称为可行解； 集合R表示由所有满足约束条件的解所组成的一个

9、集合，叫做可行解集合。 它们之间的关系如图所示。,对于上述最优化问题，目标函数和约束条件种类繁多，有的是线性的，有的是非 线性的；有的是连续的，有的是离散的；有的是单峰值的，有的是多峰值的。随着 研究的深入，人们逐渐认识到在很多复杂情况下要想完全精确地求出其最优解既不 可能，也不现实，因而求出其近似最优解或满意解是人们的主要着眼点之一。 总的来说，求最优解或近似最优解的方法主要有三种： 枚举法、启发式算法和搜索算法。 随着问题种类的不同，以及问题规模的扩大，要寻求到一种能以有限的代价来 解决上述最优化问题的通用方法仍是个难题。而遗传算法却为我们解决这类问题 提供了一个有效的途径和通用框架，开创

10、了一种新的全局优化搜索算法。,遗传算法中： 将n维决策向量Xx1,x2,xnT用n个记号Xi(i=1,2,n)所组成的符号串X来去示： Xxlx2xn Xx1，x2， ,xnT 把每一个xi看作一个遗传基因，这样，X就可看做是由n个遗传基因所组成的一个 染色体。 这里的等位基因可以是一组整数。也可以是某一范围内的实数值，或者是纯粹的 一个记号。最简单的等位基因是由0和1这两个整数组成的，相应的染色体就可 表示为一个二进制符号串。 这种编码所形成的排列形式X是个体的基因型，与它对应的X值是个体的表现型。 对于每一个个体X，要按照一定的规则确定出其适应度，个体的适应度与其对应 的个体表现型X的目标

11、函数值相关联，X越接近于目标函数的最优点，其适应度越大；反之，其适应度越小。 遗传算法中，决策变量X组成了问题的解空间。对问题最优解的搜索是通过对染色体X的搜索过程来进行的。从而所有的染色体X就组成了问题的搜索空间。,生物的进化是以集团为主体的。与此相对应，遗传算法的运算对象是由M个个 体所组成的集合，称为群体（或称种群）。与生物一代一代的自然进化过程相类 似，遗传算法的运算过程也是一个反复迭代过程： 第t代群体记做 P(t)， 经过一代遗传和进化后，得到 t+1 代群体，记做 P(t+1), 这个群体不断地经过遗传和进化操作，并且每次都按照优胜劣汰的规则将适应 度较高的个体更多地遗传到下一代

12、，这样最终在群体中将会得到一个优良的个体 X，它所对应的表现型X将达到或接近于问题的最优解X*。,1.2.2 遗传策法的运算过程 选择(复制)： 根据各个个体的适应度，按照一 定的规则或方法，从第t代群体P(t) 中选择出一些优良的个体遗传到下 一代群体P(t+1)中； 交叉： 将群体P(t)内的各个个体随机搭配 成对，对每一对个体，以某个概率 (称为交叉概率）交换它们之间的 部分染色体； 变异： 对群体P(t)中的每一个个体，以某一概率(称为变异概率)改变某 一个或某一些基因座上的基因值为其他基因值。,1.2.3 遗传算法的手工模拟计算示例 为更好地理解遗传算法的运算过程，下面用手工计算来简

13、单地模拟遗传算法的各 个主要执行步骤。 例：求下述二元函数的最大值： max f(x1,x2)=x12+x22 s.t. x1 1,2,3,4,5,6,7 x2 1,2,3,4,5,6,7 (1) 个体编码 遗传算法的运算对象是表示个体的符号串，所以必须把变量 x1, x2 编码为一种 符号串。本题中，用无符号二进制整数来表示。 因 x1, x2 为 0 7之间的整数，所以分别用3位无符号二进制整数来表示，将它 们连接在一起所组成的6位无符号二进制数就形成了个体的基因型，表示一个可 行解。 例如，基因型 X101110 所对应的表现型是：x 5，6 。 个体的表现型x和基因型X之间可通过编码和

14、解码程序相互转换。,(2) 初始群体的产生 遗传算法是对群体进行的进化操作，需要给其淮备一些表示起始搜索点的初始 群体数据。 本例中，群体规模的大小取为4，即群体由4个个体组成，每个个体可通过随机 方法产生。 如：011101，101011，011100，111001 (3) 适应度汁算 遗传算法中以个体适应度的大小来评定各个个体的优劣程度，从而决定其遗传 机会的大小。 本例中，目标函数总取非负值，并且是以求函数最大值为优化目标，故可直接 利用目标函数值作为个体的适应度。 (4) 选择运算 选择运算(或称为复制运算)把当前群体中适应度较高的个体按某种规则或模型遗传到下一代群体中。一般要求适应度

15、较高的个体将有更多的机会遗传到下一代 群体中。,本例中，我们采用与适应度成正比的概率来确定各个个体复制到下一代群体中 的数量。其具体操作过程是： 先计算出群体中所有个体的适应度的总和 fi ( i=1.2,M ); 其次计算出每个个体的相对适应度的大小 fi / fi ，它即为每个个体被遗传 到下一代群体中的概率， 每个概率值组成一个区域，全部概率值之和为1； 最后再产生一个0到1之间的随机数，依据该随机数出现在上述哪一个概率区 域内来确定各个个体被选中的次数。,(5) 交叉运算 交叉运算是遗传算法中产生新个体的主要操作过程，它以某一概率相互交换某 两个个体之间的部分染色体。 本例采用单点交叉

16、的方法，其具体操作过程是： 先对群体进行随机配对； 其次随机设置交叉点位置； 最后再相互交换配对染色体之间的部分基因。,可以看出，其中新产生的个体“111101”、“111011”的适应度较原来两个个体 的适应度都要高。,(6) 变异运算 变异运算是对个体的某一个或某一些基因座上的基因值按某一较小的概率进 行改变，它也是产生新个体的一种操作方法。 本例中，我们采用基本位变异的方法来进行变异运算，其具体操作过程是： 首先确定出各个个体的基因变异位置，下表所示为随机产生的变异点位置， 其中的数字表示变异点设置在该基因座处； 然后依照某一概率将变异点的原有基因值取反。,对群体P(t)进行一轮选择、交叉、变异运算之后可得到新一代的群体p(t+1)。,从上表中可以看出，群体经过一代进化之后，其适应度的最大值、平均值都得 到了明显的改进。事实上，这