遗传算法的生物学基础.ppt

《遗传算法的生物学基础.ppt》由会员分享，可在线阅读，更多相关《遗传算法的生物学基础.ppt（27页珍藏版）》请在金锄头文库上搜索。

1、第一章第一章 绪论绪论1.1 1.1 遗传算法的生物学基础遗传算法的生物学基础遗传算法的生物学基础遗传算法的生物学基础 生物在自然界中的生存繁衍，显示出了其对自然环境的自适应能力。受其启发，生物在自然界中的生存繁衍，显示出了其对自然环境的自适应能力。受其启发， 人们致力于对生物各种生存特性的机理研究和行为模拟，为人工自适应系统的设计人们致力于对生物各种生存特性的机理研究和行为模拟，为人工自适应系统的设计 和开发提供了广阔的前景。和开发提供了广阔的前景。遗传算法遗传算法(Genetic Algorithms，简称简称GAs)就是这种生物就是这种生物 行为的计算机模拟中令人瞩目的重要成果。基于对生

2、物遗传和进化过程的计算机模行为的计算机模拟中令人瞩目的重要成果。基于对生物遗传和进化过程的计算机模 拟，遗传算法使得各种人工系统具有优良的自适应能力和优化能力。拟，遗传算法使得各种人工系统具有优良的自适应能力和优化能力。 遗传算法所借鉴的生物学基础就是生物的遗传和进化。遗传算法所借鉴的生物学基础就是生物的遗传和进化。1.1.1 1.1.1 遗传与变异遗传与变异遗传与变异遗传与变异 遗传遗传遗传遗传( (Heredity)Heredity) 世间的生物从其父代继承特性或性状，这种生命现象就称世间的生物从其父代继承特性或性状，这种生命现象就称为为 遗传遗传(Heredity)，由于遗传的作用，使得

3、人们可以种瓜得瓜、由于遗传的作用，使得人们可以种瓜得瓜、 种豆得豆，也使得鸟仍然是在天空中飞翔，鱼仍然是在水中邀种豆得豆，也使得鸟仍然是在天空中飞翔，鱼仍然是在水中邀 游。游。整理发布 构成生物的基本结构和功能的单位是构成生物的基本结构和功能的单位是细胞细胞(Ce11)。 细胞中含有的一种微小的丝状化合物称为细胞中含有的一种微小的丝状化合物称为染色体染色体(Chromosome)，生物的所有生物的所有遗遗 传信息传信息都包含在这个复杂而又微小的染色体中。都包含在这个复杂而又微小的染色体中。 基因基因 经过生物学家的研究，控制并决定生物遗传性状的经过生物学家的研究，控制并决定生物遗传性状的染色体

4、染色体主要是由一种叫做脱主要是由一种叫做脱 氧核糖核酸氧核糖核酸(deoxyribonucleic acid 简称简称DNA)的物质所构成。的物质所构成。 DNA在染色体中有在染色体中有 规则地排列着，它是个大分子的有机聚合物，其基本结构单位是核苷酸，规则地排列着，它是个大分子的有机聚合物，其基本结构单位是核苷酸，许多核苷许多核苷 酸通过磷酸二酯键相结合形成一个长长的链状结构，两个链状结构再通过碱基间的氢键有酸通过磷酸二酯键相结合形成一个长长的链状结构，两个链状结构再通过碱基间的氢键有 规律地扭合在一起，相互卷曲起来形成一种双螺旋结构。规律地扭合在一起，相互卷曲起来形成一种双螺旋结构。基因就是

5、基因就是DNA长链结构中占有一长链结构中占有一 定位置的基本遗传单位。定位置的基本遗传单位。 遗传信息遗传信息是由是由基因基因(Gene)组成的，生物的各种性状由其相应的基因所控制。组成的，生物的各种性状由其相应的基因所控制。 基因是遗传的基本单位基因是遗传的基本单位。细胞通过分裂具有自我复制的能力，在细胞分裂的过。细胞通过分裂具有自我复制的能力，在细胞分裂的过 程中，其程中，其遗传基因遗传基因也同时被复制到下一代，从而其性状也被下一代所继承。也同时被复制到下一代，从而其性状也被下一代所继承。 遗传基因在染色体中所占据的位置称为遗传基因在染色体中所占据的位置称为基因座基因座(Locus)； 同

6、一基因座可能有的全部基因称为同一基因座可能有的全部基因称为等位基因等位基因(Allele)； 某种生物所特有的基因及其构成形式称为该生物的某种生物所特有的基因及其构成形式称为该生物的基因型基因型(Genotype)； 而该生物在环境中呈现出的相应的性状称为该生物的而该生物在环境中呈现出的相应的性状称为该生物的表现型表现型(Phenotype)； 一个细胞核中所有染色体所携带的遗传信息的全体称为一个一个细胞核中所有染色体所携带的遗传信息的全体称为一个基因组基因组(Genome)。生物的遗传方式：生物的遗传方式：生物的遗传方式：生物的遗传方式： 1. 1. 复制复制复制复制 生物的主耍遗传方式是复

7、制。遗传过程中，父代的遗传物质生物的主耍遗传方式是复制。遗传过程中，父代的遗传物质DNA被复制到子被复制到子 代。即细胞在分裂时，遗传物质代。即细胞在分裂时，遗传物质DNA通过复制通过复制(Reproduction)而转移到新生的细而转移到新生的细 胞中，新细胞就继承了旧细胞的基因。胞中，新细胞就继承了旧细胞的基因。 2. 2. 交叉交叉交叉交叉 有性生殖生物在繁殖下一代时，两个同源染色体之间通过交叉有性生殖生物在繁殖下一代时，两个同源染色体之间通过交叉(Crossover)而重而重 组，亦即在两个染色体的某一相同位置处组，亦即在两个染色体的某一相同位置处DNA被切断，其前后两串分别交义组合被

8、切断，其前后两串分别交义组合 而形成两个新的染色体。而形成两个新的染色体。 3. 3. 变异变异变异变异 在进行细胞复制时，虽然概率很小，仅仅有可能产生某些复制差错，从而使在进行细胞复制时，虽然概率很小，仅仅有可能产生某些复制差错，从而使 DNA发生某种变异发生某种变异(Mutation)，产生出新的染色体。这些新的染色体表现出新的产生出新的染色体。这些新的染色体表现出新的 性状。性状。 如此这般，遗传基因或染色体在遗传的过程中由于各种各样的原因而发生变化。如此这般，遗传基因或染色体在遗传的过程中由于各种各样的原因而发生变化。 1.1.2 1.1.2 进化进化进化进化 地球上的生物，都是经过长

9、期进化而形成的。根据达尔文的自然选择学说，地地球上的生物，都是经过长期进化而形成的。根据达尔文的自然选择学说，地 球上的生物具有很强的繁殖能力。在繁殖过程中，大多数生物通过遗传，使物种球上的生物具有很强的繁殖能力。在繁殖过程中，大多数生物通过遗传，使物种 保持相似的后代；部分生物由于变异，后代具有明显差别，甚至形成新物种。正保持相似的后代；部分生物由于变异，后代具有明显差别，甚至形成新物种。正 是由于生物的不断繁殖后代，生物数目大量增加，而自然界中生物赖以生存的资是由于生物的不断繁殖后代，生物数目大量增加，而自然界中生物赖以生存的资 源却是有限的。因此，为了生存，生物就需要竞争。生物在生存竞争

10、中，根据对源却是有限的。因此，为了生存，生物就需要竞争。生物在生存竞争中，根据对 环境的适应能力，适者生存，不适者消亡。环境的适应能力，适者生存，不适者消亡。自然界中的生物，就是根据这种优胜自然界中的生物，就是根据这种优胜 劣汰的原则，不断地进行进化。劣汰的原则，不断地进行进化。 生物的进化是以集团的形式共同进行的，这样的一个团体称为生物的进化是以集团的形式共同进行的，这样的一个团体称为群体群体(Population)， 或称为种群。或称为种群。 组成群体的单个生物称为组成群体的单个生物称为个体个体(Individual)， 每一个个体对其生存环境都有不同的每一个个体对其生存环境都有不同的适应

11、能力适应能力，这种适应能力称为个体的，这种适应能力称为个体的适应度适应度(Fitness)。1.1.3 1.1.3 遗传与进化的系统观遗传与进化的系统观遗传与进化的系统观遗传与进化的系统观 虽然人们还未完全揭开遗传与进化的奥秘，即没有完全掌握其机制、也不完全虽然人们还未完全揭开遗传与进化的奥秘，即没有完全掌握其机制、也不完全 清楚染色体编码和译码过程的细节，更不完全了解其控制方式，但遗传与进化的清楚染色体编码和译码过程的细节，更不完全了解其控制方式，但遗传与进化的 以下几个特点却为人们所共识：以下几个特点却为人们所共识： (1) 生物的所有遗传信息都包含在其染色体中，染色体决定了生物的性状；生

12、物的所有遗传信息都包含在其染色体中，染色体决定了生物的性状； (2) 染色体是由基因及其有规律的排列所构成的，遗传和进化过程发生在染色体上；染色体是由基因及其有规律的排列所构成的，遗传和进化过程发生在染色体上； (3) 生物的繁殖过程是由其基因的复制过程来完成的；生物的繁殖过程是由其基因的复制过程来完成的； (4) 通过同源染色体之间的交叉或染色体的变异会产生新的物种，使生物呈现新的通过同源染色体之间的交叉或染色体的变异会产生新的物种，使生物呈现新的 性状。性状。 (5) 对环境适应性好的基因或染色体经常比适应性差的基因或染色体有更多的机会对环境适应性好的基因或染色体经常比适应性差的基因或染色

13、体有更多的机会 遗传到下一代。遗传到下一代。1.2 1.2 遗传算法简介遗传算法简介遗传算法简介遗传算法简介 遗传算法是模拟生物在自然环境下的遗传和进化过程而形成的一种自适应全局遗传算法是模拟生物在自然环境下的遗传和进化过程而形成的一种自适应全局 优化概率搜索方法优化概率搜索方法。 它最早由美国密西根大学的它最早由美国密西根大学的H.Holland教授提出，起源于教授提出，起源于60年代年代对自然和人工对自然和人工 自适应系统的研究；自适应系统的研究； 1967年年，Bagley发表了关于遗传算法应用的论文，在其论文中首次使用发表了关于遗传算法应用的论文，在其论文中首次使用“遗传遗传算法（算法

14、（ Genetic Algorithm）”一词。一词。 70年代年代 De Jong基于遗传算法的思想在计算机上进行了大量的纯数值函数优化基于遗传算法的思想在计算机上进行了大量的纯数值函数优化 计算实验。计算实验。 在一系列研究工作的基础上，在一系列研究工作的基础上，80年代年代由由Goldberg进行归纳总结，形成了遗传算进行归纳总结，形成了遗传算法的基本框架。法的基本框架。 1.2.1 1.2.1 遗传算法概要遗传算法概要遗传算法概要遗传算法概要 对于一个求函数最大值的优化问题（求最小值也类同），一般可描述为下述数对于一个求函数最大值的优化问题（求最小值也类同），一般可描述为下述数 学规划

15、模型：学规划模型： max f(X) (1-1) s.t. X R (1-2) R U (1-3) 其中：其中： Xx1,x2,xnT为决策变量，为决策变量， f(X)为目标函数，为目标函数， 式式(1-2)、(1-3)为约束为约束 条件，条件， U是基本空间，是基本空间， R是是U的一个子集。的一个子集。 满足约束条件的解满足约束条件的解X称为可行解；称为可行解； 集合集合R表示由所有满足约束条件的解所组成的一个集合，叫做可行解集合。表示由所有满足约束条件的解所组成的一个集合，叫做可行解集合。 它们之间的关系如图所示。它们之间的关系如图所示。 对于上述最优化问题，目标函数和约束条件种类繁多，

16、有的是线性的，有的是非对于上述最优化问题，目标函数和约束条件种类繁多，有的是线性的，有的是非 线性的；有的是连续的，有的是离散的；有的是单峰值的，有的是多峰值的。随着线性的；有的是连续的，有的是离散的；有的是单峰值的，有的是多峰值的。随着 研究的深入，人们逐渐认识到在很多复杂情况下要想完全精确地求出其最优解既不研究的深入，人们逐渐认识到在很多复杂情况下要想完全精确地求出其最优解既不 可能，也不现实，因而求出其近似最优解或满意解是人们的主要着眼点之一。可能，也不现实，因而求出其近似最优解或满意解是人们的主要着眼点之一。 总的来说，求最优解或近似最优解的方法主要有三种：总的来说，求最优解或近似最优

17、解的方法主要有三种： 枚举法、启发式算法和搜索算法。枚举法、启发式算法和搜索算法。 随着问题种类的不同，以及问题规模的扩大，要寻求到一种能以有限的代价来随着问题种类的不同，以及问题规模的扩大，要寻求到一种能以有限的代价来 解决上述最优化问题的通用方法仍是个难题。而遗传算法却为我们解决这类问题解决上述最优化问题的通用方法仍是个难题。而遗传算法却为我们解决这类问题 提供了一个有效的途径和通用框架，开创了一种新的提供了一个有效的途径和通用框架，开创了一种新的全局优化搜索算法全局优化搜索算法。遗传算法中：遗传算法中：遗传算法中：遗传算法中： 将将n维决策向量维决策向量Xx1,x2,xnT用用n个记号个

18、记号Xi(i=1,2,n)所组成的符号串所组成的符号串X来来去示：去示： Xxlx2xn Xx1，x2， ,xnT 把每一个把每一个xi看作一个遗传基因看作一个遗传基因，这样，这样，X就可看做是由就可看做是由n个遗传基因所组成的一个个遗传基因所组成的一个 染色体。染色体。 这里的等位基因可以是一组整数。也可以是某一范围内的实数值，或者是纯粹的这里的等位基因可以是一组整数。也可以是某一范围内的实数值，或者是纯粹的 一个记号。最简单的等位基因是由一个记号。最简单的等位基因是由0和和1这两个整数组成的，这两个整数组成的，相应的染色体就可相应的染色体就可 表示为一个二进制符号串。表示为一个二进制符号串

19、。 这种编码所形成的排列形式这种编码所形成的排列形式X是个体的是个体的基因型基因型，与它对应的与它对应的X值是个体的值是个体的表现型表现型。 对于每一个个体对于每一个个体X，要按照一定的规则确定出其要按照一定的规则确定出其适应度适应度，个体的适应度与其对应，个体的适应度与其对应 的个体表现型的个体表现型X的目标函数值相关联，的目标函数值相关联，X越接近于目标函数的最优点，其适应度越接近于目标函数的最优点，其适应度越大；反之，其适应度越小。越大；反之，其适应度越小。 遗传算法中，决策变量遗传算法中，决策变量X组成了问题的解空间。对问题最优解的搜索是通过对组成了问题的解空间。对问题最优解的搜索是通

20、过对染色体染色体X的搜索过程来进行的。从而所有的染色体的搜索过程来进行的。从而所有的染色体X就组成了问题的搜索空间。就组成了问题的搜索空间。 生物的进化是以集团为主体的。与此相对应，遗传算法的运算对象是由生物的进化是以集团为主体的。与此相对应，遗传算法的运算对象是由M个个个个 体所组成的集合，称为体所组成的集合，称为群体（或称种群群体（或称种群）。与生物一代一代的自然进化过程相类）。与生物一代一代的自然进化过程相类 似，遗传算法的运算过程也是一个反复迭代过程：似，遗传算法的运算过程也是一个反复迭代过程： 第第t代群体记做代群体记做 P(t)， 经过一代遗传和进化后，得到经过一代遗传和进化后，得

21、到 t+1 代群体，记做代群体，记做 P(t+1), 这个群体不断地经过遗传和进化操作，并且每次都按照优胜劣汰的规则将适应这个群体不断地经过遗传和进化操作，并且每次都按照优胜劣汰的规则将适应 度较高的个体更多地遗传到下一代，这样最终在群体中将会得到一个优良的个体度较高的个体更多地遗传到下一代，这样最终在群体中将会得到一个优良的个体 X，它所对应的表现型它所对应的表现型X将达到或接近于问题的最优解将达到或接近于问题的最优解X*。1.2.2 1.2.2 遗传策法的运算过程遗传策法的运算过程遗传策法的运算过程遗传策法的运算过程选择选择选择选择( (复制复制复制复制) )： 根据各个个体的适应度，按照

22、一根据各个个体的适应度，按照一 定的规则或方法，从第定的规则或方法，从第t代群体代群体P(t) 中选择出一些优良的个体遗传到下中选择出一些优良的个体遗传到下 一代群体一代群体P(t+1)中；中；交叉交叉交叉交叉： 将群体将群体P(t)内的各个个体随机搭配内的各个个体随机搭配 成对，对每一对个体，以某个概率成对，对每一对个体，以某个概率 (称为交叉概率）交换它们之间的称为交叉概率）交换它们之间的 部分染色体；部分染色体；变异变异变异变异： 对群体对群体P(t)中的每一个个体，以中的每一个个体，以某一概率某一概率(称为变异概率称为变异概率)改变某改变某 一个或某一些基因座上的基因值一个或某一些基因

23、座上的基因值为其他基因值。为其他基因值。实际问题参数集实际问题参数集编码编码群体群体t计算适值计算适值运算：复制运算：复制 交叉交叉 变异变异群体群体t+1满足要求？满足要求？解码解码改善或解决实际问题改善或解决实际问题群体群体t+1群体群体tYN1.2.3 1.2.3 遗传算法的手工模拟计算示例遗传算法的手工模拟计算示例遗传算法的手工模拟计算示例遗传算法的手工模拟计算示例 为更好地理解遗传算法的运算过程，下面用手工计算来简单地模拟遗传算法的各为更好地理解遗传算法的运算过程，下面用手工计算来简单地模拟遗传算法的各 个主要执行步骤。个主要执行步骤。 例：求下述二元函数的最大值：例：求下述二元函数

24、的最大值： 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) (1) 个体编码个体编码个体编码个体编码 遗传算法的运算对象是表示个体的符号串，所以必须把变量遗传算法的运算对象是表示个体的符号串，所以必须把变量 x1, x2 编码为一种编码为一种 符号串符号串。本题中，用无符号二进制整数来表示。本题中，用无符号二进制整数来表示。 因因 x1, x2 为为 0 7之间的整数，所以分别用之间的整数，所以分别用3位无符号二进制整数来表示，将它位无符号二进制整数来表示，将它 们连接在一起所组成的们连接在一起所组成的6位无符号二

25、进制数就形成了个体的基因型，表示一个可位无符号二进制数就形成了个体的基因型，表示一个可 行解。行解。 例如，基因型例如，基因型 X101110 所对应的表现型是：所对应的表现型是：x 5，6 。 个体的表现型个体的表现型x和基因型和基因型X之间可通过编码和解码程序相互转换。之间可通过编码和解码程序相互转换。 (2) (2) 初始群体的产生初始群体的产生初始群体的产生初始群体的产生 遗传算法是对群体进行的进化操作，需要给其淮备一些表示起始搜索点的初始遗传算法是对群体进行的进化操作，需要给其淮备一些表示起始搜索点的初始 群体数据。群体数据。 本例中，群体规模的大小取为本例中，群体规模的大小取为4，

26、即群体由，即群体由4个个体组成，每个个体可通过随机个个体组成，每个个体可通过随机 方法产生。方法产生。 如：如：011101，101011，011100，111001 (3) (3) 适应度汁算适应度汁算适应度汁算适应度汁算 遗传算法中以个体适应度的大小来评定各个个体的优劣程度，从而决定其遗传遗传算法中以个体适应度的大小来评定各个个体的优劣程度，从而决定其遗传 机会的大小。机会的大小。 本例中，目标函数总取非负值，并且是以求函数最大值为优化目标，故可直接本例中，目标函数总取非负值，并且是以求函数最大值为优化目标，故可直接 利用目标函数值作为个体的适应度。利用目标函数值作为个体的适应度。 (4)

27、 (4) 选择运算选择运算选择运算选择运算 选择运算选择运算(或称为复制运算或称为复制运算)把当前群体中适应度较高的个体按某种规则或模型把当前群体中适应度较高的个体按某种规则或模型遗传到下一代群体中。一般要求适应度较高的个体将有更多的机会遗传到下一代遗传到下一代群体中。一般要求适应度较高的个体将有更多的机会遗传到下一代 群体中。群体中。 本例中，我们采用与适应度成正比的概率来确定各个个体复制到下一代群体中本例中，我们采用与适应度成正比的概率来确定各个个体复制到下一代群体中 的数量。其具体操作过程是：的数量。其具体操作过程是： 先计算出群体中所有个体的适应度的总和先计算出群体中所有个体的适应度的

28、总和 fi ( i=1.2,M ); 其次计算出每个个体的相对适应度的大小其次计算出每个个体的相对适应度的大小 fi / fi ，它即为每个个体被遗传它即为每个个体被遗传 到下一代群体中的概率，到下一代群体中的概率， 每个概率值组成一个区域，全部概率值之和为每个概率值组成一个区域，全部概率值之和为1； 最后再产生一个最后再产生一个0到到1之间的随机数，依据该随机数出现在上述哪一个概率区之间的随机数，依据该随机数出现在上述哪一个概率区 域内来确定各个个体被选中的次数。域内来确定各个个体被选中的次数。0124%24%17%35%1#2#3#4#个体编号个体编号初始群体初始群体p(0)适值适值占总数

29、的百分比占总数的百分比总和总和1234011101101011011100111001343425500.240.240.170.351431选择次数选择次数选择结果选择结果1102011101111001101011111001 x1 x2 3 5 5 3 3 4 7 1(5) (5) 交叉运算交叉运算交叉运算交叉运算 交叉运算是遗传算法中交叉运算是遗传算法中产生新个体产生新个体的主要操作过程，它以某一概率相互交换某的主要操作过程，它以某一概率相互交换某 两个个体之间的部分染色体。两个个体之间的部分染色体。 本例采用单点交叉的方法，其具体操作过程是：本例采用单点交叉的方法，其具体操作过程是：

30、 先对群体进行随机配对；先对群体进行随机配对； 其次随机设置交叉点位置；其次随机设置交叉点位置； 最后再相互交换配对染色体之间的部分基因。最后再相互交换配对染色体之间的部分基因。选择结果选择结果01 110111 10011010 111110 01配对情况配对情况交叉点位置交叉点位置个体编号个体编号12341-23-41-2：23-4：4交叉结果交叉结果011001 111101101001111011 可以看出，其中新产生的个体可以看出，其中新产生的个体“111101”、“111011”的适应度较原来两个的适应度较原来两个个体个体 的适应度都要高。的适应度都要高。(6) (6) 变异运算变

31、异运算变异运算变异运算 变异运算是对个体的某一个或某一些基因座上的基因值按某一较小的概率进变异运算是对个体的某一个或某一些基因座上的基因值按某一较小的概率进 行改变，它行改变，它也是产生新个体也是产生新个体的一种操作方法。的一种操作方法。 本例中，我们采用基本位变异的方法来进行变异运算，其具体操作过程是：本例中，我们采用基本位变异的方法来进行变异运算，其具体操作过程是： 首先确定出各个个体的基因变异位置，下表所示为随机产生的变异点位置，首先确定出各个个体的基因变异位置，下表所示为随机产生的变异点位置， 其中的数字表示变异点设置在该基因座处；其中的数字表示变异点设置在该基因座处； 然后依照某一概

32、率将变异点的原有基因值取反。然后依照某一概率将变异点的原有基因值取反。对群体对群体P(t)进行一轮选择、交叉、变异运算之后可得到新一代的群体进行一轮选择、交叉、变异运算之后可得到新一代的群体p(t+1)。个体编号个体编号1234交叉结果交叉结果011001 111101101001111011变异结果变异结果变异点变异点4526011101 111111111001111010子代群体子代群体p(1)011101 111111111001111010 从上表中可以看出，群体经过一代进化之后，其适应度的最大值、平均值都得从上表中可以看出，群体经过一代进化之后，其适应度的最大值、平均值都得 到了明

33、显的改进。事实上，这里已经找到了最佳个体到了明显的改进。事实上，这里已经找到了最佳个体“111111”。 注意注意注意注意 需要说明的是，表中有些栏的数据是随机产生的。这里为了更好地说明问题，需要说明的是，表中有些栏的数据是随机产生的。这里为了更好地说明问题， 我们特意选择了一些较好的数值以便能够得到较好的结果，而在实际运算过程中我们特意选择了一些较好的数值以便能够得到较好的结果，而在实际运算过程中 有可能需要一定的循环次数才能达到这个最优结果。有可能需要一定的循环次数才能达到这个最优结果。个体编号个体编号子群体子群体p(1)适值适值占总数的百分比占总数的百分比总和总和1234011101 1

34、11111111001111010349850530.140.420.210.232351 x1 x2 3 5 7 7 7 1 7 2个体编号个体编号初始群体初始群体p(0) 适值适值fi(x1,x2)占总数的百分比占总数的百分比fi / f1234011101101011011100111001343425500.240.240.170.35 x1 x2 3 5 5 3 3 4 7 1 fi=143fmax=50f=35.75选择结果选择结果011101111001101011111001配对情况配对情况交叉点位置交叉点位置1-23-41-2：23-4：4交叉结果交叉结果011001 111

35、101101001111011选择次数选择次数1102变异结果变异结果变异点变异点4526011101 111111111001111010子代群体子代群体p(1) 适值适值fi(x1,x2)占总数的百分比占总数的百分比fi / f011101 111111111001111010349850530.140.420.210.23 x1 x2 3 5 7 7 7 1 7 2 fi=253fmax=98f=58.751.3 1.3 遗传算法的发展遗传算法的发展遗传算法的发展遗传算法的发展 进化算法与其他科学技术一样，都经历一段成长过程，逐渐发展壮大。此过程可进化算法与其他科学技术一样，都经历一段成

36、长过程，逐渐发展壮大。此过程可 大致分为三个时期：萌芽期、成长期和发展期。大致分为三个时期：萌芽期、成长期和发展期。 (1) (1) 萌芽期萌芽期萌芽期萌芽期 (50 (50年代后期至年代后期至年代后期至年代后期至7070年代初期年代初期年代初期年代初期) ) 50年代后期，一些生物学家着手采用电子计算机模拟生物的遗传系统，尽管这年代后期，一些生物学家着手采用电子计算机模拟生物的遗传系统，尽管这些工作纯粹是研究生物现象，但其中已使用现代遗传算法的一些标识方式。些工作纯粹是研究生物现象，但其中已使用现代遗传算法的一些标识方式。 1965年，德国的年，德国的L.Rechenberg等人正式提出等人

37、正式提出进化策略的方法化策略的方法，当当时的的进化策略只化策略只 有一个个体，而有一个个体，而且且进化操作也只有化操作也只有变异异一种。一种。 1965年，美国的年，美国的L.j.Fogel正式提出正式提出进化化规划，在划，在计算中采用多个个体算中采用多个个体组成的群成的群 体体，而而且且只运用只运用变异异操作。操作。 60年代期年代期间，间，美国美国J.H.Holland在研究自适在研究自适应系系统时，提出系，提出系统本身与外部本身与外部环境境 相互相互协调的的遗传算法算法。1968年年，J.H.Holland教授又提出模式理教授又提出模式理论，它成，它成为遗传 算法的算法的主主要理要理论基

38、基础。 1967年，年，Bagley发表了关于遗传算法应用的论文，在其论文中首次使用发表了关于遗传算法应用的论文，在其论文中首次使用“遗传算遗传算 法（法（ Genetic Algorithm）”一词。一词。 (2) (2) 成长期成长期成长期成长期 (70 (70年代中期至年代中期至年代中期至年代中期至8080年代末期年代末期年代末期年代末期) ) 1975年，年，J.H.Holland教授的专著自然界和人工系统的适应性教授的专著自然界和人工系统的适应性(Adaptation in Natural and Artificial System)正式出版，全面地介绍了遗传算法，人们常常正式出版，

39、全面地介绍了遗传算法，人们常常 把这一事件视作遗传算法问世的标志，把这一事件视作遗传算法问世的标志， Holland也被视作遗传算法的创始人。也被视作遗传算法的创始人。 1975年，年，De.Jong在其博士论文中结合模式定理进行了大量的纯数值函数优化计在其博士论文中结合模式定理进行了大量的纯数值函数优化计 算实验，树立了遗传算法的工作框架，得到了一些重要且具有指导意义的结论。算实验，树立了遗传算法的工作框架，得到了一些重要且具有指导意义的结论。 1987年，美国年，美国D.Lawrence总结人们长期从事遗传算法的经验，公开出版遗传总结人们长期从事遗传算法的经验，公开出版遗传 算法和模拟退火

40、算法和模拟退火(Genetic Algorithm and Simulated Annealing)一书，以论文一书，以论文 集形式用大量实例介绍遗传算法。集形式用大量实例介绍遗传算法。 1985年，作为年，作为Holland的学生，的学生，D.E.Goldberg博士出版专著遗传算法博士出版专著遗传算法搜索、搜索、 优化及机器学习优化及机器学习(Genetic Algorithmsin Search，Optimization and Machine Learning)，全面、系统地介绍遗传算法，使这一技术得到普及与推广。该书全面、系统地介绍遗传算法，使这一技术得到普及与推广。该书 被人们视为

41、遗传算法的教科书。被人们视为遗传算法的教科书。 1985年，在美国举行第一届遗传算法国际学术会议年，在美国举行第一届遗传算法国际学术会议(International Conference on Genetic Algorithms，简称简称ICGA），），与会者交流运用遗传算法的经验。随后，与会者交流运用遗传算法的经验。随后， 1987，1989，1991，1993，l 995及及l 997年，每年，每2年左右都举行一次这种会议。年左右都举行一次这种会议。(3) (3) 发展期发展期发展期发展期(90(90年代以后年代以后年代以后年代以后) 90年代，遗传算法不断地向广度和深度发展。年代，遗传

42、算法不断地向广度和深度发展。 1991年，年，D.Lawrence出版遗传算法手册出版遗传算法手册(Handbook of Genetic Algorithms )一书，一书，详尽地介绍遗传算法的工作细节。详尽地介绍遗传算法的工作细节。 1996年年 Z.Michalewicz的专著遗传算法的专著遗传算法 + 数据结构数据结构 = 进化程序进化程序深入讨论了遗深入讨论了遗传算法的各种专门问题。传算法的各种专门问题。 同年，同年，T.Back的专著进化算法的理论与实践：进化策略、进化规划、遗传算法的专著进化算法的理论与实践：进化策略、进化规划、遗传算法 深入阐明进化算法的许多理论问题。深入阐明进

43、化算法的许多理论问题。 1992年，年，Koza出版专著遗传规划出版专著遗传规划应用自然选择法则的计算机程序设计应用自然选择法则的计算机程序设计(Genetic Programming:on the Programming of Computer by Means of Natural Selection)，该书全面介绍了遗传规划的原理及应用实例，标明遗传规划己成为该书全面介绍了遗传规划的原理及应用实例，标明遗传规划己成为进化算法的一个重要分支。进化算法的一个重要分支。Koza本人也被视作遗传规划的奠基人。本人也被视作遗传规划的奠基人。 1994年，年，Koza又出版第二部专著遗传规划又出版第

44、二部专著遗传规划：可再用程序的自动发现可再用程序的自动发现(Genetic Programming :Automatic Discovery of Reusable Programs)，提出自动定义函提出自动定义函数的新概念，在遗传规划中引入子程序的新技术。数的新概念，在遗传规划中引入子程序的新技术。 同年，同年，K.E.Kinnear主编遗传规划进展主编遗传规划进展(Advances in Genetic Programming)，汇集许多研究工作者有关应用遗传规划的经验和技术。汇集许多研究工作者有关应用遗传规划的经验和技术。 90年代期间，有关遗传算法的国际会议也比较活跃，见下表。年代期间

45、，有关遗传算法的国际会议也比较活跃，见下表。 我国开展遗传算法研究，主要在我国开展遗传算法研究，主要在90年代。目前，已成为继专家系统、人工神年代。目前，已成为继专家系统、人工神 经网络之后有关人工智能方面的第三个热点课题。经网络之后有关人工智能方面的第三个热点课题。1.4 1.4 遗传算法的应用遗传算法的应用遗传算法的应用遗传算法的应用 遗传算法提供了一种求解复杂系统优化间题的通用框架，它不依赖于问题的具遗传算法提供了一种求解复杂系统优化间题的通用框架，它不依赖于问题的具 体领域，对问题的种类有很强的鲁棒性，所以广泛应用于很多学科体领域，对问题的种类有很强的鲁棒性，所以广泛应用于很多学科。下

46、面是遗传下面是遗传 算法的一些主要应用领域：算法的一些主要应用领域： (1) (1) 函数优化函数优化函数优化函数优化 函数优化是遗传算法的经典应用领域，也是对遗传算法进行性能评价的常用函数优化是遗传算法的经典应用领域，也是对遗传算法进行性能评价的常用算例。算例。 对于一些非线性、多模型、多目标的函数优化问题，用其他优化方法较难求对于一些非线性、多模型、多目标的函数优化问题，用其他优化方法较难求解，用遗传算法可以方便地得到较好的结果。解，用遗传算法可以方便地得到较好的结果。 (2) (2) 组合优化组合优化组合优化组合优化 随着问题规模的增大，组合优化问题的搜索空间也急剧扩大，有时在目前的计随

47、着问题规模的增大，组合优化问题的搜索空间也急剧扩大，有时在目前的计算机上用枚举法很难或甚至不可能求出其精确最优解。对这类复杂问题，人们己算机上用枚举法很难或甚至不可能求出其精确最优解。对这类复杂问题，人们己意识到应把主要精力放在寻求其满意解上意识到应把主要精力放在寻求其满意解上，而遗传算法是寻求这种满意解的最佳而遗传算法是寻求这种满意解的最佳工具之一。实践证明，遗传算法对于组合优化中的工具之一。实践证明，遗传算法对于组合优化中的NP完全问题非常有效。完全问题非常有效。 例如，遗传算法已经在求解旅行商问题、背包问题、装箱问题、图形划分问题例如，遗传算法已经在求解旅行商问题、背包问题、装箱问题、图

48、形划分问题等方面得到成功的应用。等方面得到成功的应用。 (3) (3) 生产调度问题生产调度问题生产调度问题生产调度问题 生产调度问题在很多情况下所建立起来的数学模型难以精确求解，即使经过一生产调度问题在很多情况下所建立起来的数学模型难以精确求解，即使经过一些简化之后可以进行求解，也会因简化得太多而使得求解结果与实际相差甚远。些简化之后可以进行求解，也会因简化得太多而使得求解结果与实际相差甚远。而目前在现实生产中也主要是靠一些经验来进行调度。而目前在现实生产中也主要是靠一些经验来进行调度。 现在遗传算法已成为解决复杂调度问题的有效工具，在单件生产车间调度、流现在遗传算法已成为解决复杂调度问题的

49、有效工具，在单件生产车间调度、流水线生产车间调度、生产规划、任务分配等方面遗传算法都得到了有效的应用。水线生产车间调度、生产规划、任务分配等方面遗传算法都得到了有效的应用。 (4) (4) 自动控制自动控制自动控制自动控制 在自动控制领域中很多与优化相关的问题需要求解，遗传算法已在其中得到了在自动控制领域中很多与优化相关的问题需要求解，遗传算法已在其中得到了初步的应用，并显示出了良好的效果。初步的应用，并显示出了良好的效果。 例如用遗传算法进行航空控制系统的优化、使用遗传算法设计空间交会控制器、例如用遗传算法进行航空控制系统的优化、使用遗传算法设计空间交会控制器、基于遗传算法的模糊控制器的优化

50、设计、基于遗传算法的参数辨识、基于遗传算基于遗传算法的模糊控制器的优化设计、基于遗传算法的参数辨识、基于遗传算法的模糊控制规则的学习、利用遗传算法进行人工神经网络的结构优化设计和权法的模糊控制规则的学习、利用遗传算法进行人工神经网络的结构优化设计和权值学习等，都显示出了遗传算法在这些领域中应用的可能性。值学习等，都显示出了遗传算法在这些领域中应用的可能性。(5) (5) 机器人学机器人学机器人学机器人学 机器人是一类复杂的难以精确建模的人工系统，而遗传算法的起源就来自于对机器人是一类复杂的难以精确建模的人工系统，而遗传算法的起源就来自于对人工自适应系统的研究，所以机器人学理所当然地成为遗传算法

51、的一个重要应用人工自适应系统的研究，所以机器人学理所当然地成为遗传算法的一个重要应用领域。领域。 例如，遗传算法已经在移动机器人路径规划、关节机器人运动轨迹规划、机器例如，遗传算法已经在移动机器人路径规划、关节机器人运动轨迹规划、机器 人逆运动学求解、细胞机器人的结构优化和行为协调等方面得到研究和应用。人逆运动学求解、细胞机器人的结构优化和行为协调等方面得到研究和应用。 (6) (6) 图像处理图像处理图像处理图像处理 图像处理是计算机视觉中的一个重要研究领域。在图像处理过程中，如扫描、图像处理是计算机视觉中的一个重要研究领域。在图像处理过程中，如扫描、 特征提取、图像分割等不可避免地会存在一

52、些误差，这些误差会影响图像处理的特征提取、图像分割等不可避免地会存在一些误差，这些误差会影响图像处理的效果。如何使这些误差最小是使计算机视觉达到实用化的重要要求。效果。如何使这些误差最小是使计算机视觉达到实用化的重要要求。 遗传算法在这些图像处理中的优化计算方面找到了用武之地，日前已在模式识遗传算法在这些图像处理中的优化计算方面找到了用武之地，日前已在模式识别、图像恢复、图像边缘特征提取等方面得到了应用。别、图像恢复、图像边缘特征提取等方面得到了应用。(7) (7) 人工生命人工生命人工生命人工生命 人工生命是用计算机、机械等人工媒体模拟或构造出的具有自然生物系统特人工生命是用计算机、机械等人

53、工媒体模拟或构造出的具有自然生物系统特 有行为的人造系统。自组织能力和自学习能力是人工生命的两大主要特征。人工有行为的人造系统。自组织能力和自学习能力是人工生命的两大主要特征。人工生命与遗传算法有着密切的关系，基于遗传算法的进化模型是研究人工生命现象生命与遗传算法有着密切的关系，基于遗传算法的进化模型是研究人工生命现象的重要基础理论。的重要基础理论。 虽然人工生命的研究尚处于启蒙阶段但遗传算法已在其进化模型、学习模虽然人工生命的研究尚处于启蒙阶段但遗传算法已在其进化模型、学习模 型、行为模型、自组织模型等方面显示出了初步的应用能力，并且必将得到更为型、行为模型、自组织模型等方面显示出了初步的应

54、用能力，并且必将得到更为 深入的应用和发展。人工生命与遗传算法相辅相成，遗传算法为人工生命的研究深入的应用和发展。人工生命与遗传算法相辅相成，遗传算法为人工生命的研究 提供了一个有效的工具，人工生命的研究也必将促进遗传算法的进一步发展。提供了一个有效的工具，人工生命的研究也必将促进遗传算法的进一步发展。 (8) (8) 遗传编程遗传编程遗传编程遗传编程 Koza发展了遗传编程的概念，他使用了以发展了遗传编程的概念，他使用了以LISP语言所表示的编码方法，基于语言所表示的编码方法，基于 对一种树型结构所进行的遗传操作来自动生成计算机程序。虽然遗传编程的理论对一种树型结构所进行的遗传操作来自动生成

55、计算机程序。虽然遗传编程的理论尚未成熟，应用也有一些限制，但它已成功地应用于人工智能、机器学习等领域。尚未成熟，应用也有一些限制，但它已成功地应用于人工智能、机器学习等领域。 (9) (9) 机器学习机器学习机器学习机器学习 学习能力是高级自适应系统所应具备的能力之一。基于遗传算法的机器学习，学习能力是高级自适应系统所应具备的能力之一。基于遗传算法的机器学习， 特别是分类器系统，在很多领域中都得到了应用。例如，遗传算法被用于学习特别是分类器系统，在很多领域中都得到了应用。例如，遗传算法被用于学习 模糊控制规则，利用遗传算法来学习隶属度函数，从而更好地改进了模糊系统模糊控制规则，利用遗传算法来学习隶属度函数，从而更好地改进了模糊系统 的性能；基于遗传算法的机器学习可用来调整人工神经网络的连接权，也可用的性能；基于遗传算法的机器学习可用来调整人工神经网络的连接权，也可用 于人工神经网络的网络结构优化设计；分类器系统也在学习式多机器人路径规于人工神经网络的网络结构优化设计；分类器系统也在学习式多机器人路径规 划系统中得到了成功的应用。划系统中得到了成功的应用。