遗传算法天津大学ppt课件.ppt

《遗传算法天津大学ppt课件.ppt》由会员分享，可在线阅读，更多相关《遗传算法天津大学ppt课件.ppt（98页珍藏版）》请在三一办公上搜索。

1、智能计算的国际期刊,IEEE Transactions on Evolutionary ComputationApplied Soft ComputingSoft ComputingIEEE Transactions on Systems, Man and CyberneticsIEEE Transactions on Neural Networks Artificial Intelligence IEEE Computational Intelligence Magazine IEEE Transactions on Computational Intelligence and AI in

2、GamesNeural NetworksExpert Systems with ApplicationsMachine LearningComputers and Operations ResearchOperations Research,2,参考书 1 李敏强，寇纪淞，林丹，李书全著. 遗传算法的基本理论与应用. 北京：科学出版社，2004.2 邢文训, 谢金星. 现代优化计算方法. 北京: 清华大学出版社, 2005.3 王凌. 智能优化算法及其应用. 北京: 清华大学出版社, 2001.,3,4王小平, 曹立明. 遗传算法理论、应用与软件实现. 西安: 西安交通大学出版社, 2002.

3、5黄席樾等. 现代智能算法理论及应用. 北京：科学出版社, 2005.6高尚, 杨静宇. 群智能算法及其应用. 北京: 中国水利水电出版社, 2006.,4,授课方式,教师讲授专题报告学生讨论教师讲授：(专题报告+学生讨论)=2：1考试：闭卷、开卷或者大作业成绩=平时（30%）+考试（70%）,5,学生报告及讨论 （每人15+5分钟）,遗传算法 3次（基本+高级+应用）模拟退火 1次 （基本原理）禁忌搜索 1次 （基本原理）模拟退火和禁忌搜索算法应用 1次蚁群算法 1次 （基本原理）粒子群优化 1次 （基本原理）蚁群算法和粒子群优化应用 1次,6,内容安排,遗传算法模拟退火 禁忌搜索蚁群算法粒

4、子群优化,7,智能计算的基本思想,智能计算（软计算）就是借用自然界生物规律的启迪，根据其原理，模仿设计求解问题的算法。人工神经网络技术、遗传算法、进化规划、模拟退火技术和群智能技术等。 “仿生学”在计算智能的发展中起到了很大的推动作用（锯子）。从自然的规律中得到启迪,利用其原理进行算法设计，就是智能计算的思想。模仿海豚皮而构造的“海豚皮游泳衣”；依照鲸鱼皮构造，造成一个薄膜蒙在飞机的表面(节能3%)；依照蜘蛛的行走发明液压步行机。,8,智能优化算法及其特点,智能优化算法又称为现代启发式算法，是一种具有全局优化性能、通用性强、且适合于并行处理的算法。这种算法一般具有严密的理论依据，而不是单纯凭借

5、专家经验，理论上可以在一定的时间内找到最优解或近似最优解。 它们的共同特点：都是从任一解出发，按照某种机制，以一定的概率在整个求解空间中探索最优解。由于它们可以把搜索空间扩展到整个问题空间，因而具有全局优化性能。,9,第一章 导言,一.最优化的重要性二.传统优化方法的基本步骤三步曲三.传统优化方法的局限性四.实际问题中对最优化方法的要求五.智能优化算法的产生与发展六.应用前景局限性和研究方向、注意事项,10,人类的一切活动都是认识世界和改造世界的过程 即： 认识世界 改造世界 (建模) (优化)例：水电站建设,一.最优化的重要性（1）,11,一切学科都是建模与优化在某个特定领域中的应用概念模型

6、(定性) 结构模型(图) 数学模型 智能模型,一.最优化的重要性（2）,12,最优化理论的发展极值理论；运筹学的兴起(Operation Research)；数学规划：线性规划(LP)；非线性规划(NLP)；动态规划(PP)；马尔托夫规划(MDP)；排队轮；决策论；存储论。最优化理论在国民经济中的广泛应用,一.最优化的重要性（3）,13,二.传统优化方法的基本步骤,14,对问题中目标函数、约束函数有很高的要求有显式表达，线性、连续、可微，且高阶可微;只从一个初始点出发，难以进行并行、网络计算，难以提高计算效率；最优性达到的条件太苛刻问题的函数为凸，可行域为凸；在非双凸条件下，没有跳出局部最优解

7、的能力。,三.传统优化方法的局限性,15,对问题的描述要宽松(目标和约束函数) 可以用一段程序来描述(程序中带判断、循环)，函数可以非连续、非凸、非可微、非显式；并不苛求最优解通常满意解、理想解就可以了；计算快速、高效,可随时终止(根据时间定解的质量)；能够处理数据、信息的不确定性(如数据的模糊性，事件的随机性)。,四.实际问题中对最优化方法的要求,16,1975年holland提出遗传算法(Genetic Algorithm)1977年Glouer提出禁忌搜索算法(Tabu Search)1982年Kirkpatrick提出模拟退火算法 (Simulated Annealing)人工神经元网

8、络（Neural Network）1995年Dorigo提出蚁群算法（Ant Colony Optimization),五.智能优化算法的产生与发展（1）,17,1995年Kennedy & Eherhart提出粒子群优化 (Particle Swarm Optimization)其它文化算法(Cultural Algorithm)人工生命算法(Artificial-Life Algorithm),五.智能优化算法的产生与发展（2）,18,我们统称以上算法为人工生命计算 (Artificial Life Computation)人工生命计算 + 模糊逻辑 (Fuzzy Logic)=软计算(S

9、oft Computation)人工生命计算 + 进化编程 = 进化算法 (Evolutionary computation),五.智能优化算法的产生与发展（3）,19,应用前景十分广阔国民经济的各个领域局限性不能保证最优解，理论上不完备,六.应用前景局限性和研究方向、注意事项,20,研究方向及注意事项以应用为主，扩大面向新问题的应用；不要刻意做理论研究;算法改进表现在以下几个方面：问题的描述、编码方法、算法构造及可行性修复策略;要进行大量的上机计算；算例的选取，以下算例的说服力降序排列：网上的测试用例、文献中的例子、实际例子、随机产生的例子、自己编的例子;如何检验算法的好坏：比较计算速度、可

10、解规模、 (从不同的随机种子出发)达优率。,六.应用前景局限性和研究方向、注意事项,21,个人介绍,本科毕业设计内容是什么？研究生期间的主要学术工作、解决思路？对智能计算方法的掌握程度如何？,第二章 遗传算法,进化计算基本遗传算法遗传算法应用案例遗传算法的特点和优势遗传算法原理,2.1 进化计算,进化计算简介 进化计算是研究仿照生物进化自然选择过程中所表现出来的优先规律和方法，它用来解决，对复杂的工程技术领域或其他领域提出的而传统优化理论和方法又难以解决的优化问题。进化计算包括四个方面内容： 遗传算法（Genetic Algorithm） 进化规则（Evolutionary programmi

11、ng） 进化策略（Evolutionary Strategy） 遗传规划 树图结构编码,从进化算法对决策变量编码方案的不同来看，可以有固定长度的编码（静态编码）和可变长度的编码（动态编码）,2.1 进化计算,进化计算的诞生 （1）1990年，遗传算法开始与进化规划和进化策略有所交流。 （2）1992年，进化规划和进化策略这两个不同领域的研究人员首次接触到对方的研究工作，提出了“进化计算”（EC）的方法。 （3）1993年，进化计算这一专业领域的第一份国际性杂志进化计算在美国问世。 （4）1994年，IEEE神经网络委员会主持召开了第一届进化计算国际会议，以后每年举行一次。此外，此会每三年与IE

12、EE神经网络国际会议、IEEE模糊系统国际会议在同一地点先后连续举行，共同称为IEEE计算智能国际会议。,进化计算的理论研究与应用现状,由于Holland及其同事的长期努力，在遗传算法的数学基础方面做了许多工作，如提出了“模式定理”，证明了一些遗传算法的收敛性等；因此遗传算法的理论研究成果相对成熟些。建立进化计算的数学模型，奠定进化计算的理论基础，更深刻地认识进化计算的本质。, 进化算法的理论研究,有关进化计算的理论基础主要研究以下一些问题：, 进化计算的数学模型和理论基础，如算法的复杂性分析、算法的收敛性和收敛速度等。 确定特别适合采用进化计算方法求解的问题类型，以及采用进化计算方法求解效果

13、不太明显的问题类型。, 从理论上和实际计算效果两方面比较进化计算方法与其他优化方法的计算效果。, 进化计算方法与其他优化方法结合，提出新的混合算法。 探索在非优化类问题中如何使用进化计算方法。 从生物进化或自然界的各种现象中获得新的启发，提出新的方法，或对现有的进化计算方法进行改进。 进化计算方法在计算机上的有效实施方案，如进化计算的并行算法等。, 进化算法的实际应用研究,进化计算的一些典型的应用领域如下：, 复杂的非线性最优化问题：对具有多个局部极值的非线性最优化问题。普通的优化方法一般难以找到全局最优解，而进化计算方法可以克服这一缺点，找到全局最优解。, 复杂的组合规划或整数规划问题：大多

14、数组合规划或整数规划问题属于NP问题，难以找到有效的求解方法；进化计算方法广泛用于求解这类问题，在可以承受的计算时间内求得满意的近似解如旅行商问题、装箱问题等。 生物学：进化计算起源于对生物现象的模拟，现在又反过来用于生物学的研究，如利用进化算法研究小生境理论和生物物种的形成等。 计算机科学：进化算法广泛用于计算机科学的研究，如用于图像处理和自动识别以及文档自动处理等。, 工程应用：进化算法越来越多地用于工程实际，如通讯网络的优化设计、超大规模集成电路的布线、飞机外形的设计等。 社会科学：进化计算在社会科学的许多领域也有广泛应用，如人类行为规范进化过程的模拟、人口迁移模型的建立等。,一般来说，

15、进化计算的求解过程应包括以下几个步骤： 给定一组初始解； 评价当前这组解的性能(即对目标满足的优劣程度如何)； 按的解的性能从当前这组解中选择一定数量的解作为迭代后 解的基础； 对所得到的解进行操作(如基因重组和突变)，作为迭代后的 解； 若这些解已满足要求，则停止；否则，将这些迭代得到的解作 为当前解，返回。,进化算法的一般框架,进化算法它是一种具有“鲁棒性”的方法，它能适应不同的环境、不同的问题，并且在大多数情况下都能得到比较满意解。古典搜索方法主要有以下3类： 基于导数的方法：包括直接法(如爬山法等)和间接法(即 求导数为零的点）。这类方法首先要求导数存在并容易得到； 其次，这类方法一般

16、是一种局部搜索方法，而不是一种全局搜 索方法。 枚举法：包括完全枚举法、隐式枚举法(分枝定界法)、动态规划法等。 随机搜索方法：在问题空间中随机选定一定数量的点，从中选优。,进化算法的特点及与古典搜索方法的比较,2.2 基本遗传算法,遗传算法（genetic algorithms，GA）：一类借鉴生物界自然选择和自然遗传机制的随机搜索算法,非常适用于处理传统搜索方法难以解决的复杂和非线性优化问题。 遗传算法可广泛应用于组合优化、机器学习、自适应控制、规划设计和人工生命等领域。,遗传算法的发展历史,1962年，Fraser提出了自然遗传算法。1965年，Holland首次提出了人工遗传操作的重要

17、性。 1967年，Bagley首次提出了遗传算法这一术语。1970年，Cavicchio把遗传算法应用于模式识别中。 1971年，Hollstien在论文计算机控制系统中人工遗传自适应方法中阐述了遗传算法用于数字反馈控制的方法。 1975年，美国J. Holland出版了自然系统和人工系统的适配；DeJong完成了重要论文遗传自适应系统的行为分析。 20世纪80年代以后，遗传算法进入兴盛发展时期。,遗传算法的基本原则,遗传算法设计的基本内容,基本概念 1. 个体与种群 个体就是模拟生物个体而对问题中的对象 （一般就是问题的解）的一种称呼，一个个 体也就是搜索空间中的一个点。 种群(popula

18、tion)就是模拟生物种群而由若 干个体组成的群体, 它一般是整个搜索空间 的一个很小的子集。,2. 适应度与适应度函数 适应度(fitness)就是借鉴生物个体对环境的 适应程度,而对问题中的个体对象所设计的 表征其优劣的一种测度。 适应度函数(fitness function)就是问题中的 全体个体与其适应度之间的一个对应关系。 它一般是一个实值函数。该函数就是遗传算 法中指导搜索的评价函数。,3. 染色体与基因染色体（chromosome）就是问题中个体的某种字符串形式的编码表示。字符串中的字符也就称为基因（gene）。 例如： 个体 染色体 9 - 1001 （2，5，6）- 010

19、101 110,4. 遗传操作亦称遗传算子(genetic operator)，就是关于染色体的运算。遗传算法中有三种遗传操作: 选择-复制(selection-reproduction) 交叉(crossover，亦称交换、交配或杂交) 变异(mutation，亦称突变),选择-复制通常做法是：对于一个规模为N的种群S,按每个染色体xiS的选择概率P(xi)所决定的选中机会, 分N次从S中随机选定N个染色体, 并进行复制。,得到选择概率后，我们采用旋轮法(Roulette Wheel) 令 ，随机产生 当 ，选择个体,如下图所示:注： 优良种得到较多的繁殖机会，后代很像 ； 而很可能失去繁殖

20、的机会。,交叉 就是互换两个染色体某些位上的基因。,s1=01000101, s2=10011011可以看做是原染色体s1和s2的子代染色体。,例如, 设染色体 s1=01001011, s2=10010101, 交换其后4位基因, 即,交叉(Crossover)单切点交叉随机产生一个断点(Cutting Point)1，n-1例：,双切点交叉(交换中间段)例：不是所有点都交叉，设定一个交叉概率 ，一般为0.9,变异 就是改变染色体某个(些)位上的基因。 例如, 设染色体 s=11001101将其第三位上的0变为1, 即 s=11001101 11101101= s。 s也可以看做是原染色体s

21、的子代染色体。,2.2 基本遗传算法,算法中的一些控制参数： 种群规模 最大代数 交叉率(crossover rate)就是参加交叉运算的染色体个数占全体染色体总数的比例，记为Pc,取值范围一般为0.40.99。 变异率(mutation rate)是指发生变异的基因位数所占全体染色体的基因总位数的比例，记为Pm，取值范围一般为0.00010.1。,基本遗传算法步1 在搜索空间U上定义一个适应度函数f(x)，给定种群规模N，交叉率Pc和变异率Pm，代数T； 步2 随机产生U中的N个个体s1, s2, , sN，组成初始种群S=s1, s2, , sN，置代数计数器t=1； 步3 计算S中每个个

22、体的适应度f() ；步4 若终止条件满足，则取S中适应度最大的个体作为所求结果，算法结束。,步5 按选择概率P(xi)所决定的选中机会，每次从S中随机选定1个个体并将其染色体复制，共做N次，然后将复制所得的N个染色体组成群体S1； 步6 按交叉率Pc所决定的参加交叉的染色体数c，从S1中随机确定c个染色体，配对进行交叉操作，并用产生的新染色体代替原染色体，得群体S2；,步7 按变异率Pm所决定的变异次数m，从S2中随机确定m个染色体，分别进行变异操作，并用产生的新染色体代替原染色体，得群体S3；步8 将群体S3作为新一代种群，即用S3代替S，t = t+1，转步3；,解空间与编码空间的转换遗传

23、运算是对编码空间操作的，所以要进行两个空间的转换。,2.3 遗传算法应用举例,例2.1 利用遗传算法求解区间0,31上的二次函数y=x2的最大值。,分析 原问题可转化为在区间0, 31中搜索能使y取最大值的点a的问题。那么，0, 31 中的点x就是个体, 函数值f(x)恰好就可以作为x的适应度，区间0, 31就是一个(解)空间 。这样, 只要能给出个体x的适当染色体编码, 该问题就可以用遗传算法来解决。,解(1) 设定种群规模,编码染色体，产生初始种群。 将种群规模设定为4；用5位二进制数编码染色体；取下列个体组成初始种群S1: s1= 13 (01101), s2= 24 (11000) s

24、3= 8 (01000), s4= 19 (10011) (2) 定义适应度函数, 取适应度函数：f (x)=x2,(3) 计算各代种群中的各个体的适应度, 并对其染色体进行遗传操作,直到适应度最高的个体(即31（11111）)出现为止。 ,首先计算种群S1中各个体 s1= 13(01101), s2= 24(11000) s3= 8(01000), s4= 19(10011)的适应度f (si) 。 容易求得 f (s1) = f(13) = 132 = 169 f (s2) = f(24) = 242 = 576 f (s3) = f(8) = 82 = 64 f (s4) = f(19)

25、 = 192 = 361,再计算种群S1中各个体的选择概率。,选择概率的计算公式为,由此可求得 P(s1) = P(13) = 0.14 P(s2) = P(24) = 0.49 P(s3) = P(8) = 0.06 P(s4) = P(19) = 0.31,赌轮选择示意, 赌轮选择法,在算法中赌轮选择法可用下面的子过程来模拟: 在0, 1区间内产生一个均匀分布的随机数r。 若rq1,则染色体x1被选中。 若qk-1rqk(2kN), 则染色体xk被选中。 其中的qi称为染色体xi (i=1, 2, , n)的积累概率, 其计算公式为,选择-复制,设从区间0, 1中产生4个随机数如下: r1

26、 = 0.450126, r2 = 0.110347 r3 = 0.572496, r4 = 0.98503,于是，经复制得群体：s1 =11000（24）, s2 =01101（13） s3 =11000（24）, s4 =10011（19）,交叉 设交叉率pc=100%，即S1中的全体染色体都参加交叉运算。 设s1与s2配对，s3与s4配对。分别交换后两位基因，得新染色体： s1=11001（25）, s2=01100（12） s3=11011（27）, s4=10000（16）,变异 设变异率pm=0.001。 这样，群体S1中共有 540.001=0.02位基因可以变异。 0.02位显

27、然不足1位，所以本轮遗传操作不做变异。,于是，得到第二代种群S2： s1=11001（25）, s2=01100（12） s3=11011（27）, s4=10000（16）,第二代种群S2中各染色体的情况,假设这一轮选择-复制操作中，种群S2中的4个染色体都被选中，则得到群体：,s1=11001（25）, s2= 01100（12） s3=11011（27）, s4= 10000（16）,做交叉运算，让s1与s2，s3与s4 分别交换后三位基因，得,s1 =11100（28）, s2 = 01001（9） s3 =11000（24）, s4 = 10011（19）,这一轮仍然不会发生变异。,

28、于是，得第三代种群S3： s1=11100（28）, s2=01001（9） s3=11000（24）, s4=10011（19）,第三代种群S3中各染色体的情况,设这一轮的选择-复制结果为： s1=11100（28）, s2=11100（28） s3=11000（24）, s4=10011（19）,做交叉运算，让s1与s4，s2与s3 分别交换后两位基因，得,s1=11111（31）, s2=11100（28） s3=11000（24）, s4=10000（16）,这一轮仍然不会发生变异。,于是，得第四代种群S4： s1=11111（31）, s2=11100（28） s3=11000（24

29、）, s4=10000（16）,显然，在这一代种群中已经出现了适应度最高的染色体s1=11111。于是，遗传操作终止，将染色体“11111”作为最终结果输出。然后，将染色体“11111”解码为表现型，即得所求的最优解：31。 将31代入函数y=x2中，即得原问题的解，即函数y=x2的最大值为961。,Y,例 2.2 用遗传算法求解TSP。 分析 由于其任一可能解 一个合法的城市序列，即n个城市的一个排列，都可以事先构造出来。于是，我们就可以直接在解空间（所有合法的城市序列）中搜索最佳解。这正适合用遗传算法求解。,（1）定义适应度函数 我们将一个合法的城市序列s=（c1, c2, , cn, c

30、n+1）(cn+1就是c1)作为一个个体。这个序列中相邻两城之间的距离之和的倒数就可作为相应个体s的适应度，从而适应度函数就是,（2）对个体s=（c1, c2, , cn, cn+1）进行编码。但对于这样的个体如何编码却不是一件直截了当的事情。因为如果编码不当，就会在实施交叉或变异操作时出现非法城市序列即无效解。 例如，对于5个城市的TSP，我们用符号A、B、C、D、E代表相应的城市，用这5个符号的序列表示可能解即染色体。,然后进行遗传操作。设 s1=（A, C, B, E, D, A），s2=（A, E, D, C, B, A）实施常规的交叉或变异操作，如交换后三位，得 s1=（A,C,B,

31、C,B,A）， s2=（A,E,D,E,D,A）或者将染色体s1第二位的C变为E，得 s1=（A, E, B, E, D, A） 可以看出，上面得到的s1， s2和s1都是非法的城市序列。,为此，对TSP必须设计合适的染色体和相应的遗传运算。 事实上，人们针对TSP提出了许多编码方法和相应的特殊化了的交叉、变异操作，如顺序编码或整数编码、随机键编码、部分映射交叉、顺序交叉、循环交叉、位置交叉、反转变异、移位变异、互换变异等等。从而巧妙地用遗传算法解决了TSP。,2.4 遗传算法的特点与优势,遗传算法的主要特点 遗传算法一般是直接在解空间搜索, 而不像图搜索那样一般是在问题空间搜索, 最后才找到

32、解。 遗传算法的搜索随机地始于搜索空间的一个点集, 而不像图搜索那样固定地始于搜索空间的初始节点或终止节点, 所以遗传算法是一种随机搜索算法。,遗传算法总是在寻找优解, 而不像图搜索那样并非总是要求优解, 而一般是设法尽快找到解, 所以遗传算法又是一种优化搜索算法。 遗传算法的搜索过程是从空间的一个点集(种群)到另一个点集(种群)的搜索,而不像图搜索那样一般是从空间的一个点到另一个点地搜索。 因而它实际是一种并行搜索, 适合大规模并行计算,而且这种种群到种群的搜索有能力跳出局部最优解。,遗传算法的适应性强, 除需知适应度函数外, 几乎不需要其他的先验知识。 遗传算法长于全局搜索, 它不受搜索空

33、间的限制性假设的约束,不要求连续性, 能以很大的概率从离散的、多极值的、 含有噪声的高维问题中找到全局最优解。,遗传算法的应用遗传算法在人工智能的众多领域便得到了广泛应用。例如，机器学习、聚类、控制（如煤气管道控制）、规划（如生产任务规划）、设计（如通信网络设计、布局设计）、调度（如作业车间调度、机器调度、运输问题）、配置（机器配置、分配问题）、组合优化（如TSP、背包问题）、函数的最大值以及图像处理和信号处理等等。,另一方面，人们又将遗传算法与其他智能算法和技术相结合，使其问题求解能力得到进一步扩展和提高。例如，将遗传算法与模糊技术、神经网络相结合，已取得了不少成果。,对遗传算法的进一步研究

34、将涉及到模式定理和隐性、并行性等内容。有兴趣的同学可参阅有关专著。,2.5 遗传算法原理,1、遗传算法的数学基础 2、遗传算法的收敛性分析 3、遗传算法的改进,1、遗传算法的数学基础,（1）模式定理 （2）积木块假设,模式,模式是指种群个体基因串中的相似样板，它用来描述基因串中某些特征位相同的结构。在二进制编码中，模式是基于三个字符集(0,1,*)的字符串，符号*代表任意字符，即 0 或者 1。 模式示例：10*1,两个定义,定义1：模式 H 中确定位置的个数称为模式 H 的阶，记作O(H)。例如O(10*1)=3 。定义2：模式 H 中第一个确定位置和最后一个确定位置之间的距离称为模式 H

35、的定义距，记作(H)。例如(10*1)=4 。,模式的阶和定义距的含义,模式阶用来反映不同模式间确定性的差异，模式阶数越高，模式的确定性就越高，所匹配的样本数就越少。在遗传操作中，即使阶数相同的模式，也会有不同的性质，而模式的定义距就反映了这种性质的差异。,模式定理,模式定理：具有低阶、短定义距以及平均适应度高于种群平均适应度的模式在子代中呈指数增长。模式定理保证了较优的模式（遗传算法的较优解）的数目呈指数增长，为解释遗传算法机理提供了数学基础。,模式定理,从模式定理可看出，有高平均适应度、短定义距、低阶的模式，在连续的后代里获得至少以指数增长的串数目，为什么？主要是因为选择使最好的模式有更多

36、的复制，交叉算子不容易破坏高频率出现的、短定义距的模式，而一般变异概率又相当小，因而它对这些重要的模式几乎没有影响。,积木块假设,积木块假设：遗传算法通过短定义距、低阶以及高平均适应度的模式（积木块），在遗传操作下相互结合，最终接近全局最优解。模式定理保证了较优模式的样本数呈指数增长，从而使遗传算法找到全局最优解的可能性存在；而积木块假设则指出了在遗传算子的作用下，能生成全局最优解。,2、遗传算法的收敛性分析,遗传算法要实现全局收敛，首先要求任意初始种群经有限步都能到达全局最优解，其次算法必须由保优操作来防止最优解的遗失。与算法收敛性有关的因素主要包括种群规模、选择操作、交叉概率和变异概率。,

37、种群规模对收敛性的影响,通常，种群太小则不能提供足够的采样点，以致算法性能很差；种群太大，尽管可以增加优化信息，阻止早熟收敛的发生，但无疑会增加计算量，造成收敛时间太长，表现为收敛速度缓慢。种群太小。,选择操作对收敛性的影响,选择操作使高适应度个体能够以更大的概率生存，从而提高了遗传算法的全局收敛性。如果在算法中采用最优保存策略，即将父代群体中最佳个体保留下来，不参加交叉和变异操作，使之直接进入下一代，最终可使遗传算法以概率1收敛于全局最优解。,交叉概率对收敛性的影响,交叉操作用于个体对，产生新的个体，实质上是在解空间中进行有效搜索。交叉概率太大时，种群中个体更新很快，会造成高适应度值的个体很快被破坏掉；概率太小时，交叉操作很少进行，从而会使搜索停滞不前，造成算法的不收敛。,变异概率对收敛性的影响,变异操作是对种群模式的扰动，有利于增加种群的多样性 。但是，变异概率太小则很难产生新模式，变异概率太大则会使遗传算法成为随机搜索算法。,