遗传算法原理与应用课件

《遗传算法原理与应用课件》由会员分享，可在线阅读，更多相关《遗传算法原理与应用课件（85页珍藏版）》请在装配图网上搜索。

1、遗传算法原理与应用遗传算法原理与应用组员：余静芝 许冰 孙纯轶 杨美艳 厉云丹 提纲提纲一、遗传算法概述一、遗传算法概述 二、遗传算法原理二、遗传算法原理三、遗传算法的应用三、遗传算法的应用 生物在自然界中的生存繁衍，显示出了其对自然环境的自生物在自然界中的生存繁衍，显示出了其对自然环境的自适应能力。受其启发，人们致力于对生物各种生存特性的机理适应能力。受其启发，人们致力于对生物各种生存特性的机理研究和行为模拟，为人工自适应系统的设计和开发提供了广阔研究和行为模拟，为人工自适应系统的设计和开发提供了广阔的前景。的前景。遗传算法遗传算法(Genetic Algorithms(Genetic Al

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

3、称为遗传(Heredity)(Heredity)，由于遗传的作用，由于遗传的作用，使得人们可以种瓜得瓜、种豆得豆，也使得鸟仍然是在天空中使得人们可以种瓜得瓜、种豆得豆，也使得鸟仍然是在天空中飞翔，鱼仍然是在水中飞翔，鱼仍然是在水中 游。游。变异（变异（variationvariation）虽然说子代遗传了父代的各种特性，但虽然说子代遗传了父代的各种特性，但是总会出现与父代不一样的性状，这就可以说是变异。由于变是总会出现与父代不一样的性状，这就可以说是变异。由于变异的存在，没有两个同种生物是完全一样的，或者说，没有两异的存在，没有两个同种生物是完全一样的，或者说，没有两片叶子是一样的。片叶子是一

4、样的。遗传算法与生物进化之间的对应关系遗传算法与生物进化之间的对应关系遗传算法遗传算法生物进化生物进化适应函数适应函数环境环境适应值函数适应值函数适应性适应性适应性函数值最大的解被保留的概率最大适应性函数值最大的解被保留的概率最大选择选择问题的一个解问题的一个解个体个体解的编码解的编码染色体染色体编码的元素编码的元素基因基因被选定的一组解被选定的一组解群体群体根据适应函数选择的一组解（以编码形式表示）根据适应函数选择的一组解（以编码形式表示）种群种群以一定的方式由双亲产生后代的过程以一定的方式由双亲产生后代的过程交配交配编码的某些分量发生变化的过程编码的某些分量发生变化的过程变异变异 遗传算法

5、（遗传算法（Genetic AlgorithmGenetic Algorithm）是模拟达尔文生物进）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法，它最初由是一种通过模拟自然进化过程搜索最优解的方法，它最初由美国美国MichiganMichigan大学大学J.HollandJ.Holland教授于教授于19751975年首先提出来的，并年首先提出来的，并出版了颇有影响的专著出版了颇有影响的专著Adaptation in Natural and Adaptation in Na

6、tural and Artificial SystemsArtificial Systems，GAGA这个名称才逐渐为人所知，这个名称才逐渐为人所知，J.HollandJ.Holland教授所提出的教授所提出的GAGA通常为简单遗传算法（通常为简单遗传算法（SGASGA）。）。遗传算法是从代表问题可能潜在的解集的一个种群遗传算法是从代表问题可能潜在的解集的一个种群（populationpopulation）开始的，而一个种群则由经过基因（）开始的，而一个种群则由经过基因（genegene）编码的一定数目的个体编码的一定数目的个体(individual)(individual)组成。每个个体实际

7、上组成。每个个体实际上是染色体是染色体(chromosome)(chromosome)带有特征的实体。带有特征的实体。遗传算法的定义遗传算法的定义染色体作为遗传物质的主要载体，即多个基因的集合，其内部染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现（即基因型）是某种基因组合，它决定了个体的形状的外表现（即基因型）是某种基因组合，它决定了个体的形状的外部表现，如黑头发的特征是由染色体中控制这一特征的某种基部表现，如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。因此，在一开始需要实现从表现型到基因型的因组合决定的。因此，在一开始需要实现从表现型到基因型的映射即编码工作。由于仿

8、照基因编码的工作很复杂，我们往往映射即编码工作。由于仿照基因编码的工作很复杂，我们往往进行简化，如二进制编码，初代种群产生之后，按照适者生存进行简化，如二进制编码，初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代（和优胜劣汰的原理，逐代（generationgeneration）演化产生出越来越好）演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度（的近似解，在每一代，根据问题域中个体的适应度（fitnessfitness）大小选择（大小选择（selectionselection）个体，并借助于自然遗传学的遗传算）个体，并借助于自然遗传学的遗传算子（子（genetic oper

9、atorsgenetic operators）进行组合交叉（）进行组合交叉（crossovercrossover）和变异）和变异（mutationmutation），产生出代表新的解集的种群。这个过程将导致），产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码（代种群中的最优个体经过解码（decodingdecoding），可以作为问题近），可以作为问题近似最优解。似最优解。遗传算法计算优化的过程就如同生物学上生物遗传进化的遗传算法计算优化的过程就如同生物学上生物遗传进化

10、的过程，主要有三个基本操作（或算子）：过程，主要有三个基本操作（或算子）：选择（选择（SelectionSelection）交叉（交叉（CrossoverCrossover）变异（变异（MutationMutation）选择选择(复制复制)：根据各个个体的适应度，按照一定的规则或方法，从第根据各个个体的适应度，按照一定的规则或方法，从第t t代群体代群体P(t)P(t)中选择出一些优良的个体遗传到下中选择出一些优良的个体遗传到下 一代群体一代群体P(t+1)P(t+1)中；中；交叉：交叉：将群体将群体P(t)P(t)内的各个个体随机搭配成对，对每一对个体，内的各个个体随机搭配成对，对每一对个体

11、，以某个概率以某个概率(称为交叉称为交叉 概率）交换它们之间的部分染色体；概率）交换它们之间的部分染色体；变异：变异：对群体对群体P(t)P(t)中的每一个个体，以某一概率中的每一个个体，以某一概率(称为变异概称为变异概率率)改变某一个或某一些基因座上的基因值为其他基因值。改变某一个或某一些基因座上的基因值为其他基因值。依据适应函数值的大小，选择操作从规模为依据适应函数值的大小，选择操作从规模为N N的群体中随的群体中随机地选择若干染色体构成种群，种群的规模可以与原来群体机地选择若干染色体构成种群，种群的规模可以与原来群体的规模的规模 一致，也可以不一致。若假设二一致，也可以不一致。若假设二

12、者规模一致，但二者规模一致，但二者并不完全相同，因为适应函数值大的染色体可能会多次被者并不完全相同，因为适应函数值大的染色体可能会多次被从群体选出，而适应值小的染色体可能会失去被选中的机会。从群体选出，而适应值小的染色体可能会失去被选中的机会。因此，一些适应函数值大的染色体可能会重复出现在种群因此，一些适应函数值大的染色体可能会重复出现在种群中，而一些适应函数值小的染色体则可能被淘汰。中，而一些适应函数值小的染色体则可能被淘汰。一、遗传算法概述一、遗传算法概述1 1、智能优化算法、智能优化算法2 2、基本遗传算法、基本遗传算法3 3、遗传算法的特点、遗传算法的特点1 1、智能优化算法、智能优化

13、算法 智能优化算法又称为现代启发式算法，智能优化算法又称为现代启发式算法，是一种具有全局优化性能、通用性强、是一种具有全局优化性能、通用性强、且适合于并行处理的算法。这种算法一且适合于并行处理的算法。这种算法一般具有严密的理论依据，而不是单纯凭般具有严密的理论依据，而不是单纯凭借专家经验，理论上可以在一定的时间借专家经验，理论上可以在一定的时间内找到最优解或近似最优解。内找到最优解或近似最优解。常用的智能优化算法常用的智能优化算法 （1 1）遗传算法）遗传算法 （Genetic AlgorithmGenetic Algorithm，简称简称GAGA）（2 2）模拟退火算法）模拟退火算法（Sim

14、ulated AnnealingSimulated Annealing，简称简称SASA）（3 3）禁忌搜索算法）禁忌搜索算法（TabuTabu Search Search，简称简称TSTS）智能优化算法的特点智能优化算法的特点 它们的共同特点：都是从任一解出发，它们的共同特点：都是从任一解出发，按照某种机制，以一定的概率在整个求解按照某种机制，以一定的概率在整个求解空间中探索最优解。由于它们可以把搜索空间中探索最优解。由于它们可以把搜索空间扩展到整个问题空间，因而具有全局空间扩展到整个问题空间，因而具有全局优化性能。优化性能。遗传算法的搜索机制遗传算法的搜索机制 遗传算法模拟自然选择和自然遗

15、传过遗传算法模拟自然选择和自然遗传过程中发生的繁殖、交叉和基因突变现象，在程中发生的繁殖、交叉和基因突变现象，在每次迭代中都保留一组候选解，并按某种指每次迭代中都保留一组候选解，并按某种指标从解群中选取较优的个体，利用遗传算子标从解群中选取较优的个体，利用遗传算子(选择、交叉和变异选择、交叉和变异)对这些个体进行组合，对这些个体进行组合，产生新一代的候选解群，重复此过程，直到产生新一代的候选解群，重复此过程，直到满足某种收敛指标为止。满足某种收敛指标为止。遗传算法的具体步骤遗传算法的具体步骤选择编码策略，把参数集合（可行解集合）转换染色体结选择编码策略，把参数集合（可行解集合）转换染色体结构空

16、间；构空间；定义适应函数，便于计算适应值；定义适应函数，便于计算适应值；确定遗传策略，包括选择群体大小，选择、交叉、变异方确定遗传策略，包括选择群体大小，选择、交叉、变异方法以及确定交叉概率、变异概率等遗传参数；法以及确定交叉概率、变异概率等遗传参数；随机产生初始化群体；随机产生初始化群体；计算群体中的个体或染色体解码后的适应值；计算群体中的个体或染色体解码后的适应值；按照遗传策略，运用选择、交叉和变异算子作用于群体，按照遗传策略，运用选择、交叉和变异算子作用于群体，形成下一代群体；形成下一代群体；判断群体性能是否满足某一指标，或者已完成预定的迭代判断群体性能是否满足某一指标，或者已完成预定的

17、迭代次数，不满足则返回第五步，或者修改遗传策略再返次数，不满足则返回第五步，或者修改遗传策略再返回第六步回第六步2 2、基本遗传算法、基本遗传算法 基本遗传算法（基本遗传算法（Simple Genetic Simple Genetic AlgorithmsAlgorithms，简称，简称SGASGA，又称简单遗传算法，又称简单遗传算法或标准遗传算法），是由或标准遗传算法），是由GoldbergGoldberg总结出总结出的一种最基本的遗传算法，其遗传进化操的一种最基本的遗传算法，其遗传进化操作过程简单，容易理解，是其它一些遗传作过程简单，容易理解，是其它一些遗传算法的雏形和基础。算法的雏形和基

18、础。基本遗传算法的组成基本遗传算法的组成 （1 1）编码（产生初始种群）编码（产生初始种群）（2 2）适应度函数）适应度函数（3 3）遗传算子（选择、交叉、变异）遗传算子（选择、交叉、变异）（4 4）运行参数）运行参数 编码编码 GA GA是通过某种编码机制把对象抽是通过某种编码机制把对象抽象为由特定符号按一定顺序排成的串。象为由特定符号按一定顺序排成的串。正如研究生物遗传是从染色体着手，正如研究生物遗传是从染色体着手，而染色体则是由基因排成的串。而染色体则是由基因排成的串。SGASGA使用二进制串进行编码。使用二进制串进行编码。基本遗传算法的算法描述基本遗传算法的算法描述Procedure

19、GAProcedure GABeginBegin initialize P(0);initialize P(0);t=0;t=0;while(t=T)do while(t=T)do for i=1 to M do for i=1 to M do Evaluate fitness of P(t);Evaluate fitness of P(t);end for end for for i=1 to M do for i=1 to M do Select operation to P(t);Select operation to P(t);end for end for for i=1 to M/

20、2 do for i=1 to M/2 do Crossover operation to P(t);Crossover operation to P(t);end for end for for i=1 to M do for i=1 to M do Mutation operation to P(t);Mutation operation to P(t);end for end for for i=1 to M do for i=1 to M do P(t+1)=P(t);P(t+1)=P(t);end for end for t=t+1 t=t+1 end while end while

21、endend函数优化示例函数优化示例 求下列一元函数的最大值求下列一元函数的最大值：x-1,2 x-1,2 ，求解结果精确到，求解结果精确到6 6位小数。位小数。0.2)10sin()(xxxfSGASGA对于本例的编码对于本例的编码 由于区间长度为由于区间长度为3 3，求解结果精确到，求解结果精确到6 6位小位小数，因此可将自变量定义区间划分为数，因此可将自变量定义区间划分为3 310106 6等等份。又因为份。又因为2 22121 3 310106 6 2 22222 ，所以本例的，所以本例的二进制编码长度至少需要二进制编码长度至少需要2222位，本例的编码过位，本例的编码过程实质上是将区

22、间程实质上是将区间-1-1，22内对应的实数值转内对应的实数值转化为一个二进制串（化为一个二进制串（b21b20b0b21b20b0）。）。几个术语几个术语 基因型：基因型：1000101110110101000111编码解码个体（染色体）基因初始种群初始种群 SGA SGA采用随机方法生成若干个个体的采用随机方法生成若干个个体的集合，该集合称为初始种群。初始种群集合，该集合称为初始种群。初始种群中个体的数量称为种群规模。中个体的数量称为种群规模。适应度函数适应度函数 遗传算法对一个个体（解）的好坏遗传算法对一个个体（解）的好坏用适应度函数值来评价，适应度函数值越用适应度函数值来评价，适应度函

23、数值越大，解的质量越好。适应度函数是遗传算大，解的质量越好。适应度函数是遗传算法进化过程的驱动力，也是进行自然选择法进化过程的驱动力，也是进行自然选择的唯一标准，它的设计应结合求解问题本的唯一标准，它的设计应结合求解问题本身的要求而定。身的要求而定。选择算子选择算子 遗传算法使用选择运算来实现对群体中的个遗传算法使用选择运算来实现对群体中的个体进行优胜劣汰操作：适应度高的个体被遗传到体进行优胜劣汰操作：适应度高的个体被遗传到下一代群体中的概率大；适应度低的个体，被遗下一代群体中的概率大；适应度低的个体，被遗传到下一代群体中的概率小。选择操作的任务就传到下一代群体中的概率小。选择操作的任务就是按

24、某种方法从父代群体中选取一些个体，遗传是按某种方法从父代群体中选取一些个体，遗传到下一代群体。到下一代群体。SGASGA中选择算子采用轮盘赌选择方中选择算子采用轮盘赌选择方法。法。轮盘赌选择方法轮盘赌选择方法轮盘赌选择又称比例选择算子，它的基本思想轮盘赌选择又称比例选择算子，它的基本思想是：各个个体被选中的概率与其适应度函数值大小是：各个个体被选中的概率与其适应度函数值大小成正比。设群体大小为成正比。设群体大小为n n，个体，个体i i 的适应度为的适应度为 F Fi i，则个体则个体i i 被选中遗传到下一代群体的概率为：被选中遗传到下一代群体的概率为：niiiiFFP1/（1 1）计算群体

25、中所有个体的适应度函数值（需要计算群体中所有个体的适应度函数值（需要解码）；解码）；（2 2）利用比例选择算子的公式，计算每个个体被利用比例选择算子的公式，计算每个个体被选中遗传到下一代群体的概率；选中遗传到下一代群体的概率；（3 3）采用模拟赌盘操作（即生成采用模拟赌盘操作（即生成0 0到到1 1之间的随机之间的随机数与每个个体遗传到下一代群体的概率进行匹配）数与每个个体遗传到下一代群体的概率进行匹配）来确定各个个体是否遗传到下一代群体中。来确定各个个体是否遗传到下一代群体中。以以赌轮盘赌轮盘的方式來看，把一的方式來看，把一个轮盘个轮盘分成若干分成若干扇形扇形，面积面积越大的越大的编号编号，

26、越容易，越容易中奖中奖，因此，因此奖金会奖金会比較低。比較低。以以适应性函数适应性函数來看來看，其其值值越大者所越大者所占占的的面积面积就越大，就越大，其其选中选中的的机率机率就越大就越大。交叉算子交叉算子 所谓交叉运算，是指对两个相互配对的染色所谓交叉运算，是指对两个相互配对的染色体依据交叉概率体依据交叉概率 P Pc c 按某种方式相互交换其部分按某种方式相互交换其部分基因，从而形成两个新的个体。交叉运算是遗传基因，从而形成两个新的个体。交叉运算是遗传算法区别于其他进化算法的重要特征，它在遗传算法区别于其他进化算法的重要特征，它在遗传算法中起关键作用，是产生新个体的主要方法。算法中起关键作

27、用，是产生新个体的主要方法。SGASGA中交叉算子采用单点交叉算子。中交叉算子采用单点交叉算子。单点交叉运算单点交叉运算 交叉前：交叉前：00000|0111000000001000000000|0111000000001000011100|0000011111100010111100|00000111111000101交叉后：交叉后：00000|0000011111100010100000|0000011111100010111100|0111000000001000011100|01110000000010000交叉点交叉点 在基因组中的随机在基因组中的随机选择一个位置，然后选择一个位置，

28、然后交换两父代个体中该交换两父代个体中该位置后面的所以基因位置后面的所以基因来产生后代个体。来产生后代个体。交叉前：交叉前：00000|01110|00000001000000000|01110|00000001000011100|00000|11111100010111100|00000|111111000101交叉后：交叉后：00000|01110|00000001000000000|01110|00000001000011100|00000|11111100010111100|00000|111111000101交叉点交叉点交叉点交叉点 在基因组中随机选择两个位置，然后交换两在基因组中随

29、机选择两个位置，然后交换两个父代个体中处于两个位置之间的基因来产生后个父代个体中处于两个位置之间的基因来产生后代个体。代个体。交叉前：交叉前：00000|01110|00000|00100|0000000|01110|00000|00100|0011100|00000|11111|10001|0111100|00000|11111|10001|01交叉后：交叉后：00000|00000|00000|10001|0000000|00000|00000|10001|0011100|01110|11111|00100|0111100|01110|11111|00100|01 均匀交叉又称均匀交叉又称

30、“驻点交叉驻点交叉”，在交叉前先进行基因的变异，在交叉前先进行基因的变异检测，通过后再行交叉。检测，通过后再行交叉。交叉点交叉点变异算子变异算子 所谓变异运算，是指依据变异概率所谓变异运算，是指依据变异概率 P Pm m 将将个体编码串中的某些基因值用其它基因值来替个体编码串中的某些基因值用其它基因值来替换，从而形成一个新的个体。遗传算法中的变换，从而形成一个新的个体。遗传算法中的变异运算是产生新个体的辅助方法，它决定了遗异运算是产生新个体的辅助方法，它决定了遗传算法的局部搜索能力，同时保持种群的多样传算法的局部搜索能力，同时保持种群的多样性。交叉运算和变异运算的相互配合，共同完性。交叉运算和

31、变异运算的相互配合，共同完成对搜索空间的全局搜索和局部搜索。成对搜索空间的全局搜索和局部搜索。SGASGA中中变异算子采用基本位变异算子。变异算子采用基本位变异算子。基本位变异算子基本位变异算子 基本位变异算子是指对个体编码串随机基本位变异算子是指对个体编码串随机指定的某一位或某几位基因作变异运算。对指定的某一位或某几位基因作变异运算。对于基本遗传算法中用二进制编码符号串所表于基本遗传算法中用二进制编码符号串所表示的个体，若需要进行变异操作的某一基因示的个体，若需要进行变异操作的某一基因座上的原有基因值为座上的原有基因值为0 0，则变异操作将其变，则变异操作将其变为为1 1；反之，若原有基因值

32、为；反之，若原有基因值为1 1，则变异操作，则变异操作将其变为将其变为0 0。基本位变异算子的执行过程基本位变异算子的执行过程变异前：变异前：00000111000000001110000 0000010000000010000变异后：变异后：00000111000000001110001 1000010000000010000变异点变异点（1 1）M M ：种群规模种群规模 （2 2）T T ：遗传运算的终止进化代数遗传运算的终止进化代数 （3 3）P Pc c ：交叉概率交叉概率 （4 4）P Pm m：变异概率变异概率 SGASGA的框图的框图 产生初始群体产生初始群体是否满足停止准则是

33、否满足停止准则是是输出结果并结束输出结果并结束计算个体适应度值计算个体适应度值比例选择运算比例选择运算单点交叉运算单点交叉运算基本位变异运算基本位变异运算否否产生新一代群体产生新一代群体执行执行M/2M/2次次（1 1）群体搜索，易于并行化处理；）群体搜索，易于并行化处理；（2 2）不是盲目穷举，而是启发式搜索；）不是盲目穷举，而是启发式搜索；（3 3）适应度函数不受连续、可微等条件的约）适应度函数不受连续、可微等条件的约束，适用范围很广。束，适用范围很广。二、遗传算法原理1 1、遗传算法的数学基础、遗传算法的数学基础2 2、遗传算法的收敛性分析、遗传算法的收敛性分析3 3、遗传算法的改进、遗

34、传算法的改进1 1、遗传算法的数学基础、遗传算法的数学基础（1 1）模式定理）模式定理 （2 2）积木块假设）积木块假设 模式是指种群个体基因串中的相似样模式是指种群个体基因串中的相似样板，它用来描述基因串中某些特征位相同板，它用来描述基因串中某些特征位相同的结构。在二进制编码中，模式是基于三的结构。在二进制编码中，模式是基于三个字符集个字符集(0,1,(0,1,*)的字符串，符号的字符串，符号*代表任代表任意字符，即意字符，即 0 0 或者或者 1 1。定义定义1 1：模式：模式 H H 中确定位置的个数称为模式中确定位置的个数称为模式 H H 的阶，记作的阶，记作O(H)O(H)。例如。例

35、如O(10O(10*1)=3 1)=3。定义定义2 2：模式：模式 H H 中第一个确定位置和最后一中第一个确定位置和最后一个确定位置之间的距离称为模式个确定位置之间的距离称为模式 H H 的定的定义距，记作义距，记作(H(H)。例如。例如(10(10*1)=4 1)=4。模式的阶和定义距的含义模式的阶和定义距的含义 模式阶用来反映不同模式间确定性的模式阶用来反映不同模式间确定性的差异，模式阶数越高，模式的确定性就差异，模式阶数越高，模式的确定性就越高，所匹配的样本数就越少。在遗传越高，所匹配的样本数就越少。在遗传操作中，即使阶数相同的模式，也会有操作中，即使阶数相同的模式，也会有不同的性质，

36、而模式的定义距就反映了不同的性质，而模式的定义距就反映了这种性质的差异。这种性质的差异。模式定理模式定理模式定理：具有低阶、短定义距以及模式定理：具有低阶、短定义距以及平均适应度高于种群平均适应度的模式在平均适应度高于种群平均适应度的模式在子代中呈指数增长。子代中呈指数增长。模式定理保证了较优的模式（遗传算法模式定理保证了较优的模式（遗传算法的较优解）的数目呈指数增长，为解释遗的较优解）的数目呈指数增长，为解释遗传算法机理提供了数学基础。传算法机理提供了数学基础。从模式定理可看出，有高平均适应度、短从模式定理可看出，有高平均适应度、短定义距、低阶的模式，在连续的后代里获得至定义距、低阶的模式，

37、在连续的后代里获得至少以指数增长的串数目，这主要是因为选择使少以指数增长的串数目，这主要是因为选择使最好的模式有更多的复制，交叉算子不容易破最好的模式有更多的复制，交叉算子不容易破坏高频率出现的、短定义长的模式，而一般突坏高频率出现的、短定义长的模式，而一般突变概率又相当小，因而它对这些重要的模式几变概率又相当小，因而它对这些重要的模式几乎没有影响。乎没有影响。积木块假设：遗传算法通过短定义距、低阶积木块假设：遗传算法通过短定义距、低阶以及高平均适应度的模式（积木块），在遗传操以及高平均适应度的模式（积木块），在遗传操作下相互结合，最终接近全局最优解。作下相互结合，最终接近全局最优解。模式定理

38、保证了较优模式的样本数呈指数增长，模式定理保证了较优模式的样本数呈指数增长，从而使遗传算法找到全局最优解的可能性存在；从而使遗传算法找到全局最优解的可能性存在；而积木块假设则指出了在遗传算子的作用下，能而积木块假设则指出了在遗传算子的作用下，能生成全局最优解。生成全局最优解。2 2、遗传算法的收敛性分析、遗传算法的收敛性分析 遗传算法要实现全局收敛，首先要求任遗传算法要实现全局收敛，首先要求任意初始种群经有限步都能到达全局最优解，意初始种群经有限步都能到达全局最优解，其次算法必须由保优操作来防止最优解的其次算法必须由保优操作来防止最优解的遗失。与算法收敛性有关的因素主要包括遗失。与算法收敛性有

39、关的因素主要包括种群规模、选择操作、交叉概率和变异概种群规模、选择操作、交叉概率和变异概率。率。收敛性的影响收敛性的影响 通常，种群太小则不能提供足够的采通常，种群太小则不能提供足够的采样点，以致算法性能很差；种群太大，样点，以致算法性能很差；种群太大，尽管可以增加优化信息，阻止早熟收敛尽管可以增加优化信息，阻止早熟收敛的发生，但无疑会增加计算量，造成收的发生，但无疑会增加计算量，造成收敛时间太长，表现为收敛速度缓慢。敛时间太长，表现为收敛速度缓慢。收敛性的影响收敛性的影响 选择操作使高适应度个体能够以更大的选择操作使高适应度个体能够以更大的概率生存，从而提高了遗传算法的全局收敛概率生存，从而

40、提高了遗传算法的全局收敛性。如果在算法中采用最优保存策略，即将性。如果在算法中采用最优保存策略，即将父代群体中最佳个体保留下来，不参加交叉父代群体中最佳个体保留下来，不参加交叉和变异操作，使之直接进入下一代，最终可和变异操作，使之直接进入下一代，最终可使遗传算法以概率使遗传算法以概率1 1收敛于全局最优解。收敛于全局最优解。收敛性的影响收敛性的影响 交叉操作用于个体对，产生新的个体，交叉操作用于个体对，产生新的个体，实质上是在解空间中进行有效搜索。交叉实质上是在解空间中进行有效搜索。交叉概率太大时，种群中个体更新很快，会造概率太大时，种群中个体更新很快，会造成高适应度值的个体很快被破坏掉；概率

41、成高适应度值的个体很快被破坏掉；概率太小时，交叉操作很少进行，从而会使搜太小时，交叉操作很少进行，从而会使搜索停滞不前，造成算法的不收敛。索停滞不前，造成算法的不收敛。收敛性的影响收敛性的影响变异操作是对种群模式的扰动，有利变异操作是对种群模式的扰动，有利于增加种群的多样性于增加种群的多样性 。但是，变异概率太。但是，变异概率太小则很难产生新模式，变异概率太大则会小则很难产生新模式，变异概率太大则会使遗传算法成为随机搜索算法。使遗传算法成为随机搜索算法。遗传算法本质上是对染色体模式所进行遗传算法本质上是对染色体模式所进行的一系列运算，即通过选择算子将当前种群的一系列运算，即通过选择算子将当前种

42、群中的优良模式遗传到下一代种群中，利用交中的优良模式遗传到下一代种群中，利用交叉算子进行模式重组，利用变异算子进行模叉算子进行模式重组，利用变异算子进行模式突变。通过这些遗传操作，模式逐步向较式突变。通过这些遗传操作，模式逐步向较好的方向进化，最终得到问题的最优解。好的方向进化，最终得到问题的最优解。3 3、遗传算法的改进、遗传算法的改进 遗传欺骗问题：在遗传算法进遗传欺骗问题：在遗传算法进化过程中，有时会产生一些超常的个体，化过程中，有时会产生一些超常的个体，这些个体因竞争力太突出而控制了选择这些个体因竞争力太突出而控制了选择运算过程，从而影响算法的全局优化性运算过程，从而影响算法的全局优化

43、性能，导致算法获得某个局部最优解。能，导致算法获得某个局部最优解。遗传算法的改进途径遗传算法的改进途径（1 1）对编码方式的改进）对编码方式的改进 （2 2）对遗传算子）对遗传算子 的改进的改进（3 3）对控制参数的改进）对控制参数的改进 （4 4）对执行策略的改进）对执行策略的改进 二进制编码优点在于编码、解码操作二进制编码优点在于编码、解码操作简单，交叉、变异等操作便于实现，缺点简单，交叉、变异等操作便于实现，缺点在于精度要求较高时，个体编码串较长，在于精度要求较高时，个体编码串较长，使算法的搜索空间急剧扩大，遗传算法的使算法的搜索空间急剧扩大，遗传算法的性能降低。格雷编码克服了二进制编码

44、的性能降低。格雷编码克服了二进制编码的不连续问题不连续问题，浮点数编码改善了遗传算法，浮点数编码改善了遗传算法的计算复杂性的计算复杂性。对遗传算子对遗传算子 的改进的改进排序选择排序选择 均匀交叉均匀交叉 逆序变异逆序变异（1 1）对群体中的所有个体对群体中的所有个体按其适应度大小进行降序排按其适应度大小进行降序排序；序；（2 2）根据具体求解问题，根据具体求解问题，设计一个概率分配表，将各设计一个概率分配表，将各个概率值按上述排列次序分个概率值按上述排列次序分配给各个个体；配给各个个体；（3 3）以各个个体所分配到以各个个体所分配到的概率值作为其遗传到下一的概率值作为其遗传到下一代的概率，基

45、于这些概率用代的概率，基于这些概率用赌盘选择法来产生下一代群赌盘选择法来产生下一代群体。体。排序选择排序选择 均匀交叉均匀交叉 逆序变异逆序变异（1 1）随机产生一个与个体随机产生一个与个体编码长度相同的二进制屏蔽编码长度相同的二进制屏蔽字字P=WP=W1 1W W2 2W Wn n ；（2 2）按下列规则从按下列规则从A A、B B两两个父代个体中产生两个新个个父代个体中产生两个新个体体X X、Y Y：若：若W Wi i=0=0，则，则X X的第的第i i个基因继承个基因继承A A的对应基因，的对应基因，Y Y的第的第i i个基因继承个基因继承B B的对应基的对应基因；若因；若W Wi i=

46、1=1，则，则A A、B B的第的第i i个基因相互交换，从而生成个基因相互交换，从而生成X X、Y Y的第的第i i个基因。个基因。对遗传算子的改进对遗传算子的改进排序选择排序选择 均匀交叉均匀交叉 逆序变异逆序变异变异前：变异前：3 4 8|7 9 6 5|2 13 4 8|7 9 6 5|2 1变异前：变异前：3 4 8|5 6 9 7|2 13 4 8|5 6 9 7|2 1SchafferSchaffer建议的最优参数范围是：建议的最优参数范围是：M=20-100M=20-100，T=100-500T=100-500，P Pc c =0.4-0.9=0.4-0.9，P Pm m =0

47、.001-0.01=0.001-0.01。SrinvivasSrinvivas等人提出自适应遗传算法，即等人提出自适应遗传算法，即P PC C和和P Pm m能够随适应度自动改变，当种群的各个个体能够随适应度自动改变，当种群的各个个体适应度趋于一致或趋于局部最优时，使二者增加，适应度趋于一致或趋于局部最优时，使二者增加，而当种群适应度比较分散时，使二者减小，同时而当种群适应度比较分散时，使二者减小，同时对适应值高于群体平均适应值的个体，采用较低对适应值高于群体平均适应值的个体，采用较低的的P PC C和和P Pm m，使性能优良的个体进入下一代，而低，使性能优良的个体进入下一代，而低于平均适应

48、值的个体，采用较高的于平均适应值的个体，采用较高的P PC C和和P Pm m，使性，使性能较差的个体被淘汰能较差的个体被淘汰 。混合遗传算法混合遗传算法免疫遗传算法免疫遗传算法小生境遗传算法小生境遗传算法单亲遗传算法单亲遗传算法并行遗传算法并行遗传算法三、遗传算法的应用1 1、遗传算法的应用领域、遗传算法的应用领域2 2、遗传算法的应用示例、遗传算法的应用示例1 1、遗传算法的应用领域、遗传算法的应用领域（1 1）组合优化）组合优化 （2 2）函数优化）函数优化 （3 3）自动控制）自动控制 （4 4）生产调度）生产调度 （5 5）图像处理）图像处理 （6 6）机器学习）机器学习 （7 7）

49、人工生命）人工生命 （8 8）数据挖掘）数据挖掘 遗传算法提供了一种求解复杂系统优化间题的通用框架，它遗传算法提供了一种求解复杂系统优化间题的通用框架，它不依赖于问题的具体领域，对问题的种类有很强的鲁棒性，所以不依赖于问题的具体领域，对问题的种类有很强的鲁棒性，所以广泛应用于很多学科。下面是遗传算法的一些主要应用领域：广泛应用于很多学科。下面是遗传算法的一些主要应用领域：随着问题规模的增大，组合优化问题的搜索空间也急剧扩大，随着问题规模的增大，组合优化问题的搜索空间也急剧扩大，有时在目前的计算机上用枚举法很难或甚至不可能求出其精确最有时在目前的计算机上用枚举法很难或甚至不可能求出其精确最优解。

50、对这类复杂问题，人们己意识到应把主要精力放在寻求其优解。对这类复杂问题，人们己意识到应把主要精力放在寻求其满意解上，而遗传算法是寻求这种满意解的最佳工具之一。实践满意解上，而遗传算法是寻求这种满意解的最佳工具之一。实践证明，遗传算法对于组合优化中的证明，遗传算法对于组合优化中的NPNP完全问题非常有效。完全问题非常有效。例如，遗传算法已经在求解旅行商问题、背包问题、装箱问例如，遗传算法已经在求解旅行商问题、背包问题、装箱问题、图形划分问题等方面得到成功的应用。题、图形划分问题等方面得到成功的应用。函数优化是遗传算法的经典应用领域，也是对遗传算法进行函数优化是遗传算法的经典应用领域，也是对遗传算

51、法进行性能评价的常用算例。性能评价的常用算例。对于一些非线性、多模型、多目标的函数优化问题，对于一些非线性、多模型、多目标的函数优化问题，用其他优化方法较难求解，用遗传算法可以方便地得到较好的结用其他优化方法较难求解，用遗传算法可以方便地得到较好的结果。果。在自动控制领域中很多与优化相关的问题需要求解，遗传在自动控制领域中很多与优化相关的问题需要求解，遗传算法已在其中得到了初步的应用，并显示出了良好的效果。算法已在其中得到了初步的应用，并显示出了良好的效果。例如用遗传算法进行航空控制系统的优化、使用遗传算法例如用遗传算法进行航空控制系统的优化、使用遗传算法设计空间交会控制器、基于遗传算法的模糊

52、控制器的优化设设计空间交会控制器、基于遗传算法的模糊控制器的优化设计、基于遗传算法的参数辨识、基于遗传算法的模糊控制规计、基于遗传算法的参数辨识、基于遗传算法的模糊控制规则的学习、利用遗传算法进行人工神经网络的结构优化设计则的学习、利用遗传算法进行人工神经网络的结构优化设计和权值学习等，都显示出了遗传算法在这些领域中应用的可和权值学习等，都显示出了遗传算法在这些领域中应用的可能性。能性。生产调度问题在很多情况下所建立起来的数学模型难以生产调度问题在很多情况下所建立起来的数学模型难以精确求解，即使经过一些简化之后可以进行求解，也会因简精确求解，即使经过一些简化之后可以进行求解，也会因简化得太多而

53、使得求解结果与实际相差甚远。而目前在现实生化得太多而使得求解结果与实际相差甚远。而目前在现实生产中也主要是靠一些经验来进行调度。产中也主要是靠一些经验来进行调度。现在遗传算法已成为解决复杂调度问题的有效工具，在单现在遗传算法已成为解决复杂调度问题的有效工具，在单件生产车间调度、流水线生产车间调度、生产规划、任务分件生产车间调度、流水线生产车间调度、生产规划、任务分配等方面遗传算法都得到了有效的应用。配等方面遗传算法都得到了有效的应用。学习能力是高级自适应系统所应具备的能力之一。基于遗学习能力是高级自适应系统所应具备的能力之一。基于遗传算法的机器学习，传算法的机器学习，特别是分类器系统，在很多领

54、域中都得到了应用。例如，遗特别是分类器系统，在很多领域中都得到了应用。例如，遗传算法被用于学习传算法被用于学习 模糊控制规则，利用遗传算法来学习隶属度函数，从而更好模糊控制规则，利用遗传算法来学习隶属度函数，从而更好地改进了模糊系统地改进了模糊系统 的性能；基于遗传算法的机器学习可用来调整人工神经网络的性能；基于遗传算法的机器学习可用来调整人工神经网络的连接权，也可用的连接权，也可用 于人工神经网络的网络结构优化设计；分类器系统也在学习于人工神经网络的网络结构优化设计；分类器系统也在学习式多机器人路径规式多机器人路径规 划系统中得到了成功的应用。划系统中得到了成功的应用。图像处理是计算机视觉中

55、的一个重要研究领域。在图像处理图像处理是计算机视觉中的一个重要研究领域。在图像处理过程中，如扫描、过程中，如扫描、特征提取、图像分割等不可避免地会存在一些误差，这些误特征提取、图像分割等不可避免地会存在一些误差，这些误差会影响图像处理的效果。如何使这些误差最小是使计算机视觉差会影响图像处理的效果。如何使这些误差最小是使计算机视觉达到实用化的重要要求。达到实用化的重要要求。遗传算法在这些图像处理中的优化计算方面找到了用武之地，遗传算法在这些图像处理中的优化计算方面找到了用武之地，日前已在模式识别、图像恢复、图像边缘特征提取等方面得到了日前已在模式识别、图像恢复、图像边缘特征提取等方面得到了应用。

56、应用。人工生命是用计算机、机械等人工媒体模拟或构造出的具有人工生命是用计算机、机械等人工媒体模拟或构造出的具有自然生物系统特自然生物系统特 有行为的人造系统。自组织能力和自学习能力是人工生命的有行为的人造系统。自组织能力和自学习能力是人工生命的两大主要特征。人工生命与遗传算法有着密切的关系，基于遗传两大主要特征。人工生命与遗传算法有着密切的关系，基于遗传算法的进化模型是研究人工生命现象的重要基础理论。算法的进化模型是研究人工生命现象的重要基础理论。（8 8）数据挖掘）数据挖掘 数据挖掘是近几年出现的数据库技术，数据挖掘是近几年出现的数据库技术，它能够从大型数据库中提取隐含的、先前未知的、有潜它

57、能够从大型数据库中提取隐含的、先前未知的、有潜在应用价值的知识和规则。许多数据挖掘问题可看成是在应用价值的知识和规则。许多数据挖掘问题可看成是搜索问题，数据库看作是搜索空间，挖掘算法看作是搜搜索问题，数据库看作是搜索空间，挖掘算法看作是搜索策略。因此，应用遗传算法在数据库中进行搜索，对索策略。因此，应用遗传算法在数据库中进行搜索，对随机产生的一组规则进行进化随机产生的一组规则进行进化.直到数据库能被该组规直到数据库能被该组规则覆盖，从而挖掘出隐含在数据库中的规则。则覆盖，从而挖掘出隐含在数据库中的规则。SunilSunil已已成功地开发了一个基于遗传算法的数据挖掘下具。利用成功地开发了一个基于

58、遗传算法的数据挖掘下具。利用该工具对两个飞机失事的真实数据库进行了数据挖掘实该工具对两个飞机失事的真实数据库进行了数据挖掘实验，结果表明遗传算法是进行数据挖掘的有效方法之一。验，结果表明遗传算法是进行数据挖掘的有效方法之一。对遗传算法的改进很多，其中有马尔科夫链模型，有对遗传算法的改进很多，其中有马尔科夫链模型，有编码方式的改进，选择算子、变异算子和交换算子的改编码方式的改进，选择算子、变异算子和交换算子的改进，有种群规模动态性上的改动，最有特点的改进就是进，有种群规模动态性上的改动，最有特点的改进就是并行化改进。并行化改进利用的遗传算法的固有并行性。并行化改进。并行化改进利用的遗传算法的固有

59、并行性。2 2、遗传算法的应用示例、遗传算法的应用示例 弹药装载问题（弹药装载问题（Ammunition Loading Problem，简称，简称ALP），就是在），就是在满足各类通用弹药运输规程和安全性的满足各类通用弹药运输规程和安全性的前提下，如何将一批通用弹药箱装入军前提下，如何将一批通用弹药箱装入军用运输工具，使得通用弹药的装载效率用运输工具，使得通用弹药的装载效率达到最大值的问题。达到最大值的问题。AGSAAAGSAA的基本原理的基本原理在弹药装载中，考虑到模拟退火算法在弹药装载中，考虑到模拟退火算法的基本思想是跳出局部最优解，将模拟退的基本思想是跳出局部最优解，将模拟退火思想引入

60、遗传算法，应用改进型遗传算火思想引入遗传算法，应用改进型遗传算法和模拟退火算法相结合，构建自适应遗法和模拟退火算法相结合，构建自适应遗传模拟退火算法（传模拟退火算法（AGSAAAGSAA），从而综合了全），从而综合了全局优化和局部搜索的特点，为解决弹药装局优化和局部搜索的特点，为解决弹药装载这一组合优化问题提供了新的思路。载这一组合优化问题提供了新的思路。AGSAAAGSAA的编码方式的编码方式AGSAAAGSAA采用二进制编码方式，每一个二采用二进制编码方式，每一个二进制位对应一个待装弹药箱，若为，表进制位对应一个待装弹药箱，若为，表示该弹药箱装入运输工具，为则不装。示该弹药箱装入运输工具，

61、为则不装。AGSAAAGSAA的解码和适应度函数的解码和适应度函数AGSAAAGSAA采用弹药装载的启发式算法来解采用弹药装载的启发式算法来解码，解码后最终确定装入运输工具的弹药码，解码后最终确定装入运输工具的弹药箱。适应度函数主要考虑两个方面，即载箱。适应度函数主要考虑两个方面，即载重率和积载率，对这两个因素加权，来计重率和积载率，对这两个因素加权，来计算适应度函数值。算适应度函数值。弹药装载的启发式算法弹药装载的启发式算法（1 1）定位规则（）定位规则（Locating ruleLocating rule）定位规则是指用来确定当前待装弹药箱在定位规则是指用来确定当前待装弹药箱在运输工具剩余

62、装载空间中摆放位置的规则。运输工具剩余装载空间中摆放位置的规则。（2 2）定序规则（）定序规则（Ordering ruleOrdering rule）定序规则是指用来确定弹药箱放入运输工定序规则是指用来确定弹药箱放入运输工具装载空间先后顺序的规则。具装载空间先后顺序的规则。遗传算子的选择遗传算子的选择AGSAAAGSAA的选择算子采用轮盘赌选择算的选择算子采用轮盘赌选择算子，并结合最优保存策略；变异算子采子，并结合最优保存策略；变异算子采用基本位变异算子；同时，在变异运算用基本位变异算子；同时，在变异运算之后，增加退火算子，以增强算法的局之后，增加退火算子，以增强算法的局部搜索能力；交叉概率和

63、变异概率为自部搜索能力；交叉概率和变异概率为自适应概率，以提高种群的进化效率。适应概率，以提高种群的进化效率。交叉算子的选择交叉算子的选择 由于由于AGSAAAGSAA是采用将弹药箱的编号排列成是采用将弹药箱的编号排列成串来进行编码的，如果个体交叉采用传统方式串来进行编码的，如果个体交叉采用传统方式进行，就有可能使个体的编码产生重复基因进行，就有可能使个体的编码产生重复基因（即一个弹药箱编号在一个个体中出现两次以（即一个弹药箱编号在一个个体中出现两次以上），从而产生不符合条件的个体，因此，上），从而产生不符合条件的个体，因此，AGSAAAGSAA采用的是部分映射交叉算子。采用的是部分映射交叉算

64、子。部分映射交叉算子部分映射交叉算子交叉前：交叉前：8 7|4 3|1 2 6 58 7|4 3|1 2 6 5交叉后：交叉后：8 3|6 7|1 2 4 58 3|6 7|1 2 4 5遗传算法的应用实例遗传算法的应用实例遗传算法旅行商问题遗传算法旅行商问题旅行商问题：一个旅行者要去很多城市，每个城市只去一次，旅行商问题：一个旅行者要去很多城市，每个城市只去一次，问：该怎么走路线最短？问：该怎么走路线最短？这个问题可以转化为：随机给这个问题可以转化为：随机给n n个点，如何连线这个点，如何连线这n n个点，使得个点，使得连线最短？连线最短？这个问题是遗传算法的经典问题这个问题是遗传算法的经典

65、问题 哈哈哈哈我试着写了一个程序来我试着写了一个程序来解决。解决。采用的策略是：采用的策略是：1.1.精英主义：每次有精英主义：每次有2 2个最优解直接进入下一代。个最优解直接进入下一代。2.2.轮盘赌选择生育：每次对每一代的个体进行一次轮询，如果轮盘赌选择生育：每次对每一代的个体进行一次轮询，如果不适应度不适应度 某个随机数，那么选择这个个体进行生育。某个随机数，那么选择这个个体进行生育。3.3.单性繁殖：因为基因组的基因是互斥的且有序的，所以不单性繁殖：因为基因组的基因是互斥的且有序的，所以不适合两性繁殖。适合两性繁殖。4.4.交换变异：变异的方式为交换变异：变异的方式为随机选择两个不同位

66、置的基随机选择两个不同位置的基因，交换位置。因，交换位置。遗传算法的目的，就是找到一个可能最优的解！为了达到这遗传算法的目的，就是找到一个可能最优的解！为了达到这个目的，他先对解进行随机搜索，然后选中几个解中较优的个目的，他先对解进行随机搜索，然后选中几个解中较优的解，进行一些变换，然后再次从这些变换后的解中搜寻较优解，进行一些变换，然后再次从这些变换后的解中搜寻较优解，变换解，变换n n次之后，有可能得到非常优秀的解。次之后，有可能得到非常优秀的解。所以说，遗传算法是建立在最优解与较优解的差别小的基础所以说，遗传算法是建立在最优解与较优解的差别小的基础上的，也可以说，是建立在父母漂亮，小孩很有可能也漂亮上的，也可以说，是建立在父母漂亮，小孩很有可能也漂亮的理论基础上的。的理论基础上的。另外，遗传算法也是拼人品的算法，他得出的很有可能是局另外，遗传算法也是拼人品的算法，他得出的很有可能是局部最优解，而不是全局最优解。部最优解，而不是全局最优解。运行结果运行结果主要程序：主要程序：void cGAMachine:SetupNextGeneration()void cGAMachine:S