《人工智能-9遗传算法.pptx》由会员分享，可在线阅读，更多相关《人工智能-9遗传算法.pptx（97页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、计算智能计算智能是信息科学和生命科学相互交叉的前沿领域,是现代科学技术发展的一个重要体现。计算智能涉及神经网络、模糊逻辑、进化计算和人工生命等领域，它的研究和发展反映了当代科学技术多学科交叉与集成的重要发展趋势。贝兹德克于1994年提出了一种A，B，C智能模型，从而表示ABC与神经网络、模式识别和智能之间的关系：A：Artificial,表示人工的、符号的（非生物的）B：Biological,表示生物的C：Computational,表示计算的计算智能是一种智力方式的底层认知，它与人工智能的区别是认知层次从中层下降到底层而已。中层系统含有知识，底层系统没有知识。关于A，B，C智能计算智能与人工
2、智能的区别与联系NN Neural Network 神经网络PR Pattern Recognition 模式识别计算智能系统与人工智能系统当一个系统只涉及数值（底层）数据，含有模式识别部分，不应用于人工智能意义上的知识，而且系统能够呈现出：（1）计算适应性（2）计算容错性（3）接近人的计算速度（4）计算误差率与人接近则该系统就是计算智能系统。当一个智能计算系统以非数值方式并加上知识，即为人工智能系统。神经计算（Neural Computation）神经计算研究的进展1943年麦卡洛奇和皮茨提出神经网络模型的概念（称为MP模型）20世纪60年代威德罗和霍夫提出了自适应线性元件。60年代末到80
3、年代初初与研究的低潮期80年代后又大发展遗传算法 遗遗传传算算法法简简称称GAGA（Genetic Genetic AlgorithmsAlgorithms）是是19751975年年由由美美国国Michigan(Michigan(密歇根州)大大学学的的J.J.HollandHolland教教授授提提出出的的模模拟拟自自然然界界生生物物遗遗传传学学（孟孟德德尔尔）和和生生物物进进化化论论（达达尔尔文文）通通过过人人工工方方式式所所构构造造的的一一类类并并行行随随机机搜搜索索最最优优化化方方法法，是是对对生生物物进进化化过过程程进进行的一种数学仿真，是进化计算的重要形式。行的一种数学仿真，是进化计
4、算的重要形式。1 1、遗传算法、遗传算法 在生物系统中，进化被认为是一种成功的自适应方法，具有很好的健壮性。其主要特点是(1)直接对结构对象进行操作，不存在求导和函数连续性的限定；(2)具有内在的隐含并行性和更好的全局寻优能力；(3)采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。遗传算法已被广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。它是现代有关计算智能中的关键技术之一。遗遗传传算算法法是是以以达达尔尔文文的的自自然然选选择择学学说说为为基基础础发发展展起起来来的的。自自然然选择学说包括以下三个方面：选择学说包括以下三个
5、方面：1 1、遗传算法、遗传算法（1 1）遗遗传传：这这是是生生物物的的普普遍遍特特征征，亲亲代代把把生生物物信信息息交交给给子子代代，子子代代总总是是和和亲亲代代具具有有相相同同或或相相似似的的性性状状。生生物物有有了了这这个个特特征征，物物种种才才能稳定存在。能稳定存在。（2 2）变变异异：亲亲代代和和子子代代之之间间以以及及子子代代的的不不同同个个体体之之间间的的差差异异，称称为为变变异异。变变异异是是随随机机发发生生的的，变变异异的的选选择择和和积积累累是是生生命命多多样样性性的的根根源。源。（3 3）生生存存斗斗争争和和适适者者生生存存：具具有有适适应应性性变变异异的的个个体体被被保
6、保留留下下来来，不不具具有有适适应应性性变变异异的的个个体体被被淘淘汰汰，通通过过一一代代代代的的生生存存环环境境的的选选择择作作用，性状逐渐逐渐与祖先有所不同，演变为新的物种。用，性状逐渐逐渐与祖先有所不同，演变为新的物种。遗遗传传算算法法将将“优优胜胜劣劣汰汰，适适者者生生存存”的的生生物物进进化化原原理理引引入入优优化化参参数数形形成成的的编编码码串串群群体体中中，按按所所选选择择的的适适应应度度函函数数并并通通过过遗遗传传中中的的复复制制、交交叉叉及及变变异异对对个个体体进进行行筛筛选选，适适应应度度高高的的个个体体被被保保留留下下来来，组组成成新新的的群群体体，新新的的群群体体既既继
7、继承承了了上上一一代代的的信信息息，又又优优于于上上一一代代。这这样样周周而而复复始始，群群体体中中个个体体适适应应度度不不断断提提高高，直直到到满满足足一一定定的的条条件件。遗遗传传算算法法的的算算法法简简单单，可可并并行行处处理理，并并能到全局最优解。能到全局最优解。如：爱斯基摩人，如：爱斯基摩人，非洲原始部落非洲原始部落2 2、遗传算法的基本操作为：、遗传算法的基本操作为：（1 1）复制（）复制（Reproduction OperatorReproduction Operator）复复制制是是从从一一个个旧旧种种群群中中选选择择生生命命力力强强的的个个体体位位串串产产生生新新种种群群的的
8、过过程程。具具有有高高适适应应度度的的位位串串更更有有可可能能在在下下一一代代中中产产生一个或多个子孙。生一个或多个子孙。复复制制操操作作可可以以通通过过随随机机方方法法来来实实现现。首首先先产产生生0101之之间间均均匀匀分分布布的的随随机机数数，若若某某串串的的复复制制概概率率为为40%40%，则则当当产产生生的随机数在的随机数在0.401.00.401.0之间时，该串被复制，否则被淘汰。之间时，该串被复制，否则被淘汰。（2 2）交叉（）交叉（Crossover OperatorCrossover Operator）复复制制操操作作能能从从旧旧种种群群中中选选择择出出优优秀秀者者，但但不不
9、能能创创造造新新的的染染色色体体。而而交交叉叉模模拟拟了了生生物物进进化化过过程程中中的的繁繁殖殖现现象象，通通过过两两个染色体的交换组合，来产生新的优良品种。个染色体的交换组合，来产生新的优良品种。交交叉叉的的过过程程为为：在在匹匹配配池池中中任任选选两两个个染染色色体体，随随机机选选择择一一点点或或多多点点交交换换点点位位置置；交交换换双双亲亲染染色色体体交交换换点点右右边边的的部部分分，即可得到两个新的染色体数字串。即可得到两个新的染色体数字串。交叉体现了自然界中信息交换的思想。交叉交叉体现了自然界中信息交换的思想。交叉有单点交叉、两点交叉、还有一致交叉、顺有单点交叉、两点交叉、还有一致
10、交叉、顺序交叉和周期交叉。单点交叉是最基本的方序交叉和周期交叉。单点交叉是最基本的方法，应用较广。它是指染色体切断点有一处，法，应用较广。它是指染色体切断点有一处，例：例：（3 3）变异）变异(Mutation Operator)(Mutation Operator)变变异异运运算算用用来来模模拟拟生生物物在在自自然然的的遗遗传传环环境境中中由由于于各各种种偶偶然然因因素素引引起起的的基基因因突突变变，它它以以很很小小的的概概率率随随机机地地改改变变遗遗传传基基因因（表表示示染染色色体体的的符符号号串串的的某某一一位位）的的值值。在在染染色色体体以以二二进进制制编编码码的的系系统统中中，它它随
11、随机机地地将将染染色色体体的的某某一个基因由一个基因由1 1变为变为0 0，或由，或由0 0变为变为1 1。若若只只有有选选择择和和交交叉叉，而而没没有有变变异异，则则无无法法在在初初始始基基因因组组合合以以外外的的空空间间进进行行搜搜索索，使使进进化化过过程程在在早早期期就就陷陷入入局局部部解解而而进进入入终终止止过过程程，从从而而影影响响解解的的质质量量。为为了了在在尽尽可可能能大大的的空空间间中中获获得得质质量量较较高高的的优优化化解，必须采用变异操作。解，必须采用变异操作。17设自变量设自变量 x x 介于介于0 03131，求其二次函数的最大值，即：，求其二次函数的最大值，即：max
12、 f(x)=x max f(x)=x2 2,x 0,31,x 0,313 3、遗传算法示例、遗传算法示例-f(x)=x-f(x)=x2 2 极大值问题极大值问题5001000 0 31 xf(x)当然，利用简单的代数运算，很容易求出该问题的解。现当然，利用简单的代数运算，很容易求出该问题的解。现在改用遗传算法求解，遗传算法通常包括下述内容：在改用遗传算法求解，遗传算法通常包括下述内容：18（1 1）编码）编码 遗传算法首先要对实际问题进行编码，用字符串表达问题。这种字遗传算法首先要对实际问题进行编码，用字符串表达问题。这种字符串相当于遗传学中的染色体。每一代所产生的字符串符串相当于遗传学中的染
13、色体。每一代所产生的字符串个体总和称为群体个体总和称为群体。为了实现的方便，通常字符串长度固定，字符选为了实现的方便，通常字符串长度固定，字符选0 0或或1 1。本例中，利用本例中，利用5 5位二进制数表示位二进制数表示x x值，采用随机产生的方法，假设得值，采用随机产生的方法，假设得出拥有四个个体的初始群体，即：出拥有四个个体的初始群体，即：0110101101，1100011000，0100001000，1001110011。x x值相值相应为应为1313，2424，8 8，1919。个体编号初始群体xi适应度f(xi)f(xi)/f(xi)f(xi)/fMp123401101110000
14、1000100111324819169576643610.140.490.060.310.581.970.221.231201总计f(xi)平均值f最大值最小值1170293576641.000.250.490.064.001.001.970.22412019（2）计算适应度）计算适应度 衡量字符串（染色体）好坏的指标是衡量字符串（染色体）好坏的指标是适应度适应度，它也就是遗传算，它也就是遗传算法的目标函数。法的目标函数。本例中适应度比较简单，用本例中适应度比较简单，用x2计算。计算。表中还列出了当前适应度的总和表中还列出了当前适应度的总和f(xi)及平均值及平均值f，即：，即：f(xi)=f
15、(x1)+f(x2)+f(x3)+f(x4)=1170 f=f(xi)/4=292.5(293)f(x1)/f=169/293=0.57679.个体编号初始群体xi适应度f(xi)f(xi)/f(xi)f(xi)/fMp1234011011100001000100111324819169576643610.140.490.060.310.581.970.221.231201总计f(xi)平均值f最大值最小值1170293576641.000.250.490.064.001.001.970.22412020（2）计算适应度）计算适应度 表中第表中第6列的列的 f(xi)/f 表示每个个体的表示每
16、个个体的相对适应度相对适应度，它反映了个，它反映了个体之间的相对优劣性。如体之间的相对优劣性。如2号个体的号个体的 f(xi)/f 值最高（值最高（1.97），为优），为优良个体，良个体，3号个体最低（号个体最低（0.22），为不良个体。），为不良个体。个体编号初始群体xi适应度f(xi)f(xi)/f(xi)f(xi)/fMp12345671234011011100001000100111324819169576643610.140.490.060.310.581.970.221.231201总计f(xi)平均值f最大值最小值1170293576641.000.250.490.064.001
17、.001.970.22412021（3）复制）复制 为了将已有的群体变为下一代群体，遗传算法仿效为了将已有的群体变为下一代群体，遗传算法仿效进化论中进化论中“自然选择、适者生存自然选择、适者生存”的原则，从旧群体中的原则，从旧群体中选择优良个体进行复制。选择的依据是个体适应度的大选择优良个体进行复制。选择的依据是个体适应度的大小，适应度大的个体接受复制，使之繁殖；适应度小的小，适应度大的个体接受复制，使之繁殖；适应度小的个体则删除掉，遭到淘汰。个体则删除掉，遭到淘汰。22（3）复制）复制 在本例中，根据相对适应度的大小对个体进行取舍，在本例中，根据相对适应度的大小对个体进行取舍，2号个体号个体
18、性能最优，予以复制繁殖。性能最优，予以复制繁殖。3号个体性能最差，将它删除，使之死号个体性能最差，将它删除，使之死亡，表中的亡，表中的M表示传递给下一代的个体数目，其中表示传递给下一代的个体数目，其中2号个体占号个体占2个，个，3号个体为号个体为0，1号、号、4号个体保持为号个体保持为1个。个。这样，就产生了下一代群体。这样，就产生了下一代群体。个体编号初始群体xi适应度f(xi)f(xi)/f(xi)f(xi)/fMp1234011011100001000100111324819169576643610.140.490.060.310.581.970.221.231201总计f(xi)平均值
19、f最大值最小值1170293576641.000.250.490.064.001.001.970.22412023（3）复制）复制 从表中的第从表中的第4列可以看出，复制后产生的新一代群体的平均适应列可以看出，复制后产生的新一代群体的平均适应度明显增加，由原来的度明显增加，由原来的293增加到增加到421。造成平均适应度增加的原因有。造成平均适应度增加的原因有二：二：1）淘汰原来最差的个体。使最小适应度由原来的）淘汰原来最差的个体。使最小适应度由原来的64增加到增加到169。2）增加了优良个体（）增加了优良个体（2号）的个数，使适应度累计值增加。号）的个数，使适应度累计值增加。个体编号复制后群
20、体xi复制后适应度f(xi)交换对象交换位置交换后群体复制后适应度f(xi)1234（1）01101（2）11000（2）11000（4）10011132424191695765763612号1号4号3号443301100110011101110000144625729256总计平均值最大值最小值1682421576361175443972925624（4）交换）交换 通过复制产生的新群体，其性能得到改善，然通过复制产生的新群体，其性能得到改善，然而它不能产生新的个体。为了产生新的个体，遗传而它不能产生新的个体。为了产生新的个体，遗传算法仿照生物学中杂交的方法，对染色体（字符串）算法仿照生物学
21、中杂交的方法，对染色体（字符串）的某些部分进行交叉换位。被交换的母体都选自经的某些部分进行交叉换位。被交换的母体都选自经过复制产生的新一代个体（优胜者）。过复制产生的新一代个体（优胜者）。25（4）交换）交换 本例中，利用随机配对的方法，决定本例中，利用随机配对的方法，决定1号和号和2号个体、号个体、3号和号和4号个号个体分别交换，如表中第体分别交换，如表中第5列。再利用随机定位的方法，确定这两对母列。再利用随机定位的方法，确定这两对母体交叉换位的位置分别从字符长度的第体交叉换位的位置分别从字符长度的第4位及第位及第3位开始。如：位开始。如：3号、号、4号个体从字符长度第号个体从字符长度第3位
22、开始交换。交换开始的位置称位开始交换。交换开始的位置称交换点交换点。个体编号复制后群体xi复制后适应度f(xi)交换对象交换位置交换后群体复制后适应度f(xi)123401101110001100010011132424191695765763612号1号4号3号443301100110011101110000144625729256总计平均值最大值最小值168242157636117544397292561100010011110111000026（4）交换）交换 从表中可以看出，交换后出现优异个体从表中可以看出，交换后出现优异个体3号，其适应度高达号，其适应度高达729，大大高于交换前的最
23、大值（大大高于交换前的最大值（576）。与此同时，平均适应度也从原来）。与此同时，平均适应度也从原来的的421提高到提高到439，说明交换后的群体正朝优良方向发展。，说明交换后的群体正朝优良方向发展。个体编号复制后群体xi复制后适应度f(xi)交换对象交换位置交换后群体复制后适应度f(xi)123401101110001100010011132424191695765763612号1号4号3号443301100110011101110000144625729256总计平均值最大值最小值1682421576361175443972925627（5）突变）突变 遗传算法模仿生物学中基因突变的方法，
24、将个体字符串某位符号遗传算法模仿生物学中基因突变的方法，将个体字符串某位符号进行逆变，即由进行逆变，即由1变为变为0或由或由0变为变为1。例如，下式左侧的个体于第。例如，下式左侧的个体于第3位位突变，得到新个体如右侧所示。突变，得到新个体如右侧所示。上述（上述（2）（）（5）反复执行，直至得出满意的最优解。）反复执行，直至得出满意的最优解。由上可知，遗传算法参考生物中有关进化与遗传的过程，利用复由上可知，遗传算法参考生物中有关进化与遗传的过程，利用复制、交换、突变等操作，不断循环执行，制、交换、突变等操作，不断循环执行，逐渐逼近全局最优解逐渐逼近全局最优解。遗传算法中，个体是否进行突变以及在哪
25、个部位突变，都由遗传算法中，个体是否进行突变以及在哪个部位突变，都由事先给定的概率决定。通常，突变概率很小，约为事先给定的概率决定。通常，突变概率很小，约为0.008，本例的，本例的第一代中就没有发生突变。第一代中就没有发生突变。100001010028 从数学角度看，遗传算法实质上是一种搜索寻优技从数学角度看，遗传算法实质上是一种搜索寻优技术。它从某一初始群体出发，遵照一定的操作规则，不术。它从某一初始群体出发，遵照一定的操作规则，不断迭代计算，逐步逼近最优解。这种搜索技术，有如下断迭代计算，逐步逼近最优解。这种搜索技术，有如下特点：特点：4 4、遗传算法的基本特征遗传算法的基本特征 从上述
26、简单例子可以看出，遗传算法仿照生物进化从上述简单例子可以看出，遗传算法仿照生物进化和遗传的规律，利用复制、交换、突变等操作，使优胜和遗传的规律，利用复制、交换、突变等操作，使优胜者繁殖，劣败者消失，一代一代地重复同样的操作，最者繁殖，劣败者消失，一代一代地重复同样的操作，最终找出最优解。终找出最优解。29（1）智能式搜索）智能式搜索 遗传算法的搜索策略，既不是盲目式的遗传算法的搜索策略，既不是盲目式的乱搜索乱搜索，也不是，也不是穷举式穷举式的全面搜索，它是有指导的搜索。指导遗传算法执行的全面搜索，它是有指导的搜索。指导遗传算法执行搜索的依据是搜索的依据是适应度适应度，也就是它的目标函数。利用适
27、应度，也就是它的目标函数。利用适应度，使遗传算法逐步逼近目标值。使遗传算法逐步逼近目标值。（2）渐进式优化）渐进式优化 遗传算法利用复制、交换、突变等操作，使新一代的结遗传算法利用复制、交换、突变等操作，使新一代的结果优越于旧一代，通过不断迭代，逐渐得出最优的结果，它果优越于旧一代，通过不断迭代，逐渐得出最优的结果，它是一种反复迭代的过程。是一种反复迭代的过程。4 4、遗传算法的基本特征遗传算法的基本特征30（3）全局最优解）全局最优解 遗传算法由于采用交换、突变等操作，产生新的个遗传算法由于采用交换、突变等操作，产生新的个体，扩大了搜索范围，使得搜索得到的优化结果是全局体，扩大了搜索范围，使
28、得搜索得到的优化结果是全局最优解而不是局部最优解。最优解而不是局部最优解。（4）黑箱式结构）黑箱式结构 遗传算法根据所解决问题的特性，进行编码和选择遗传算法根据所解决问题的特性，进行编码和选择适应度。一旦完成字符串和适应度的表达，其余的复制、适应度。一旦完成字符串和适应度的表达，其余的复制、交换、突变等操作都可按常规手续执行。个体的编码如交换、突变等操作都可按常规手续执行。个体的编码如同输入，适应度如同输出。因此遗传算法从某种意义上同输入，适应度如同输出。因此遗传算法从某种意义上讲是一种只考虑输入与输出关系的黑箱问题。讲是一种只考虑输入与输出关系的黑箱问题。4 4、遗传算法的基本特征遗传算法的
29、基本特征31（5）通用性强）通用性强 传统的优化算法，需要将所解决的问题用传统的优化算法，需要将所解决的问题用数学式子数学式子表表示，常常要求解该数学函数的一阶导数或二阶导数。采用示，常常要求解该数学函数的一阶导数或二阶导数。采用遗传算法，只用编码及适应度表示问题，并不要求明确的遗传算法，只用编码及适应度表示问题，并不要求明确的数学方程及导数表达式。因此，遗传算法通用性强，可应数学方程及导数表达式。因此，遗传算法通用性强，可应用于离散问题及函数关系不明确的复杂问题，有人称遗传用于离散问题及函数关系不明确的复杂问题，有人称遗传算法是一种算法是一种框架型算法框架型算法，它只有一些简单的原则要求，在
30、，它只有一些简单的原则要求，在实施过程中可以赋予更多的含义。实施过程中可以赋予更多的含义。（6）并行式算法）并行式算法 遗传算法是从初始群体出发，经过复制、交换、突变遗传算法是从初始群体出发，经过复制、交换、突变等操作，产生一组新的群体。每次迭代计算，都是针对一等操作，产生一组新的群体。每次迭代计算，都是针对一组个体同时进行，而不是针对某个个体进行。因此，尽管组个体同时进行，而不是针对某个个体进行。因此，尽管遗传算法是一种搜索算法，但是由于采用这种并行机理，遗传算法是一种搜索算法，但是由于采用这种并行机理，搜索速度很高。这种并行式计算是遗传算法的一个重要特搜索速度很高。这种并行式计算是遗传算法
31、的一个重要特征。征。4 4、遗传算法的基本特征遗传算法的基本特征32 遗传算法受生物进化与遗传的启发，形成一种独特的优遗传算法受生物进化与遗传的启发，形成一种独特的优化方式，因此，遗传算法的运算原则常常与生物进化及遗传化方式，因此，遗传算法的运算原则常常与生物进化及遗传学说吻合，而且其术语也常常仿效生物学的术语。学说吻合，而且其术语也常常仿效生物学的术语。遗传算法的运算基础是字符串，它就相当于生物学中的遗传算法的运算基础是字符串，它就相当于生物学中的染色体。染色体。字符串由一系列字符组成，每个字符都有特定的含义，字符串由一系列字符组成，每个字符都有特定的含义，反应所解决问题的某个特征，这就相当
32、于基因，即染色体反应所解决问题的某个特征，这就相当于基因，即染色体DNA的片段。的片段。在进行交换、突变操作时，遗传算法只涉及到字符串某在进行交换、突变操作时，遗传算法只涉及到字符串某些片段，这就类似于遗传过程只涉及某些基因而不是整个染些片段，这就类似于遗传过程只涉及某些基因而不是整个染色体。色体。5 5、遗传算法的生物学含义遗传算法的生物学含义33 遗传学很注重遗传学很注重等位基因等位基因，它是反映生物某一形态所对应的基因。，它是反映生物某一形态所对应的基因。在遗传算法的字符串中，每个字符都反映问题的某一特性，这也在遗传算法的字符串中，每个字符都反映问题的某一特性，这也就相当于等位基因，至于
33、等位基因的位置，也就相当于该字符在就相当于等位基因，至于等位基因的位置，也就相当于该字符在字符串中的位置。字符串中的位置。在遗传学中，杂交产生的子代里显现出亲本的性状，称作显在遗传学中，杂交产生的子代里显现出亲本的性状，称作显性性状，未显现出来的亲本性状叫作隐性性状。控制显性性状的性性状，未显现出来的亲本性状叫作隐性性状。控制显性性状的基因是基因是显性基因显性基因，用大写英文字母表示。控制隐性性状的基因是，用大写英文字母表示。控制隐性性状的基因是隐性基因隐性基因，用小写英文字母表示。在遗传算法中，模仿这种大、，用小写英文字母表示。在遗传算法中，模仿这种大、小字母表达方式，对显性基因和隐性基因采
34、取不同的操作。小字母表达方式，对显性基因和隐性基因采取不同的操作。5 5、遗传算法的生物学含义遗传算法的生物学含义34 生物学术语在遗传算法中的对应意义如下表。生物学术语在遗传算法中的对应意义如下表。序号生物学遗传算法123456染色体（Chromosome）基因（Gene）等位基因（Allele）基因位置（Locus）基因型（Genotype）表现型（Phenotype）字符串字符对应的字符字符的位置字符串结构字符串含义5 5、遗传算法的生物学含义遗传算法的生物学含义35 根据前面所讲的示例，可以看出遗传算法的根据前面所讲的示例，可以看出遗传算法的实施过程中包括编码、产生群体、计算适应度、实
35、施过程中包括编码、产生群体、计算适应度、复制、交换、突变等操作。复制、交换、突变等操作。遗传算法的详细流程如下图。遗传算法的详细流程如下图。6 6、遗传算法的工作步骤遗传算法的工作步骤36Gen：遗传（迭代）的代次。表明遗传算法反复执行的次数，即已产生群体的代次数目。M：群体中拥有的个体数目。i：已处理个体的累计数，当i等于M，表明这一代的个体已全部处理完毕，需要转入下一代群体。交叉率 Pc 就是参加交叉运算的染色体个数占全体染色体总数的比例，记为Pc,取值范围一般为0.40.99。变异率 Pm 是指发生变异的基因位数所占全体染色体的基因总位数的比例，记为Pm，取值范围一般为0.00010.1
36、。复制概率 Pt 用于控制复制与淘汰的个体数目。Pc Pt Pm No No Yes Gen：=0 随机产生初始群体 满足终止条件 计算群体中各个体的适应度 i：=0 i：=M?选择遗传算子及概率 根据适应度选择两个个体 i：=i+1 执行交换 将两个交换结果添入新群体 i：=i+1 将复制结果添入新群体 执行复制 根据适应度选择一个个体 将突变结果添入新群体 执行突变 Gen：=Gen+1 输出结果 结束 Yes 37概括地讲，遗传算法主要执行以下四步：概括地讲，遗传算法主要执行以下四步：（1）随机地建立由字符串组成的初始群体；随机地建立由字符串组成的初始群体；（2）计算各个体的适应度；计算
37、各个体的适应度；（3）根据遗传概率，利用下述操作产生新群体：根据遗传概率，利用下述操作产生新群体：1）复制复制。将已有的优良个体复制后添入新群体中，删除劣。将已有的优良个体复制后添入新群体中，删除劣 质个体；质个体；2）交换交换。将选出的两个个体进行交换，所产生的新个体添。将选出的两个个体进行交换，所产生的新个体添 入新群体中。入新群体中。3）突变突变。随机地改变某一个体的某个字符后添入新群体中。随机地改变某一个体的某个字符后添入新群体中。（4）反复执行（反复执行（2）、（）、（3）后，一旦达到终止条件，）后，一旦达到终止条件，选择最佳个体作为遗传算法的结果。选择最佳个体作为遗传算法的结果。3
38、8 遗传算法的工作对象是字符串，因此对字符串的遗传算法的工作对象是字符串，因此对字符串的编码有两点要求：一是字符串要反映所研究问题的性编码有两点要求：一是字符串要反映所研究问题的性质；二是字符串的表达要便于计算处理。质；二是字符串的表达要便于计算处理。遗传算法关键问题遗传算法关键问题（1 1）编码）编码 遗传算法常常用二进制的遗传算法常常用二进制的0/1字符编码。当问题比字符编码。当问题比较简单，例如只描述高较简单，例如只描述高/低、大低、大/小等布尔型性质时，小等布尔型性质时，每一位每一位0/1变量就代表一个性质。变量就代表一个性质。例如，某事物只涉及到贵例如，某事物只涉及到贵/贱、大贱、大
39、/小及好小及好/坏时，我们可用坏时，我们可用三位三位0/1字符表示，并规定第字符表示，并规定第1位字符代表贵位字符代表贵/贱，第贱，第2位字符代表位字符代表大大/小，第小，第3位字符代表好位字符代表好/坏。如坏。如111代表贵代表贵-大大-好，而好，而100代表贵代表贵-小小-好。好。39 当问题的性质要用数值描述时，则编码变成用二当问题的性质要用数值描述时，则编码变成用二进制数表示十进制数。例如，用进制数表示十进制数。例如，用4位位0/1字符串表示字符串表示1 16。根据排列计算，长度（位数）为根据排列计算，长度（位数）为L的的0/1字符串，可以表达字符串，可以表达2*2*2 2=2L 种情
40、况。如种情况。如果所描述性质的最小值不是果所描述性质的最小值不是0时，即性质介于时，即性质介于UminUmax之间，为了减小字符串长度，可以之间，为了减小字符串长度，可以采用映射的方法，用采用映射的方法，用2L个二进制数表示个二进制数表示 Umin，Umax。这时，令。这时，令L个个0表示表示Umin，L个个1 表表示示Umax，其中，其中L大小取决于（大小取决于（Umax Umin），），其余的数则用线性插值决定。例如，对于其余的数则用线性插值决定。例如，对于 16，31 的十进制数，我们可以用的十进制数，我们可以用4位二进制位二进制0/1字符在字符在 0000，1111 范围内表示。范围内
41、表示。（1 1）编码）编码Umin 00Umax 11 40 对于兼有多种性质的问题，可以采用长字符串顺对于兼有多种性质的问题，可以采用长字符串顺序分别表示。例如，可选序分别表示。例如，可选25位位0/1字符串表示物体的体字符串表示物体的体积、重量及颜色，其中前积、重量及颜色，其中前10位数表示体积量，中间位数表示体积量，中间10位数表示重量，后位数表示重量，后5位数表示颜色。位数表示颜色。在遗传算法中，字符串的长度常常是固定的，以在遗传算法中，字符串的长度常常是固定的，以便按统一的方式执行操作。个别研究者采用不等长的便按统一的方式执行操作。个别研究者采用不等长的字符串，这时就需要跟踪记录，经
42、常调整操作方式，字符串，这时就需要跟踪记录，经常调整操作方式，比较烦琐。比较烦琐。从生物学角度看，编码就相当于选择遗传物质，从生物学角度看，编码就相当于选择遗传物质，它是研究遗传的基础。同样，在遗传算法中编码也是它是研究遗传的基础。同样，在遗传算法中编码也是一项基础性工作。一项基础性工作。（1 1）编码）编码41 在遗传算法中，衡量个体优劣的尺度是在遗传算法中，衡量个体优劣的尺度是适应度适应度。根据适应度的大小，决定某些个体是繁殖或是消亡。根据适应度的大小，决定某些个体是繁殖或是消亡。因此，适应度是驱动遗传算法的动力。从生物学角度因此，适应度是驱动遗传算法的动力。从生物学角度讲，适应度相当于讲
43、，适应度相当于“生存竞争，适者生存生存竞争，适者生存”的生物生的生物生存能力，在遗传过程中具有重要意义。存能力，在遗传过程中具有重要意义。通常，适应度是通常，适应度是费用、赢利、方差费用、赢利、方差等目标的表达等目标的表达式。在运用过程中可以借鉴以下经验。式。在运用过程中可以借鉴以下经验。（2 2）适应度）适应度42统一表达形式统一表达形式 在实际问题中，有时希望适应度越大越好（如赢利、劳在实际问题中，有时希望适应度越大越好（如赢利、劳动生产率），有时要求适应度越小越好（费用、方差）。为动生产率），有时要求适应度越小越好（费用、方差）。为了使遗传算法有通用性，这种最大、最小值问题宜统一表达。了
44、使遗传算法有通用性，这种最大、最小值问题宜统一表达。通常都统一按最大值问题处理，而且不允许适应度小于通常都统一按最大值问题处理，而且不允许适应度小于0。对于最小值问题，其适应度按下式转换：对于最小值问题，其适应度按下式转换：f(x)=Cmax-g(x)当当g(x)Cmax0 其他情况其他情况f(x)：转换后的适应度。：转换后的适应度。g(x)：最小值问题下的适应度。：最小值问题下的适应度。Cmax：足够大的常数，可取：足够大的常数，可取g(x)的最大值。的最大值。（2 2）适应度）适应度43统一表达形式统一表达形式 为了保证适应度不出现负值，对于有可能产生负为了保证适应度不出现负值，对于有可能
45、产生负值的最大值问题，可以采用下式进行变换：值的最大值问题，可以采用下式进行变换：f(x)=U(x)+Cmin 当当U(x)+Cmin 00 其他情况其他情况f(x)：变换后的适应度。变换后的适应度。U(x)：最大值问题下的适应度。：最大值问题下的适应度。Cmin：足够大的常数。：足够大的常数。（2 2）适应度）适应度44适应度缩放适应度缩放 在执行遗传算法的初始阶段，各个个体的适应度比较离散，在执行遗传算法的初始阶段，各个个体的适应度比较离散，某些个体的适应度会很高或很低。对于个别适应度很高的个体，会某些个体的适应度会很高或很低。对于个别适应度很高的个体，会连续多次被复制；对于适应度很低的个
46、体，会过早被舍弃。这种不连续多次被复制；对于适应度很低的个体，会过早被舍弃。这种不正常的取舍，对于个体数目不多的群体尤为严重，会把遗传算法的正常的取舍，对于个体数目不多的群体尤为严重，会把遗传算法的搜索引向误区搜索引向误区，过早地收敛于，过早地收敛于局部最优解局部最优解。为了克服这种缺陷，需。为了克服这种缺陷，需要采用适应度缩放技术，将适应度按下式变换：要采用适应度缩放技术，将适应度按下式变换：f ：缩放后的适应度。缩放后的适应度。f：原来的适应度。：原来的适应度。a、b：系数。：系数。f=a*f+b 利用这种缩放技术，缩小（放大）原来最大（最利用这种缩放技术，缩小（放大）原来最大（最小）的适
47、应度，从而可以减弱离散现象。小）的适应度，从而可以减弱离散现象。（2 2）适应度）适应度45 复制是遗传算法的基本算子，它将优良个体在下一代新群复制是遗传算法的基本算子，它将优良个体在下一代新群体中繁殖，体现了体中繁殖，体现了“适者生存适者生存”的自然选择原则。的自然选择原则。个体是否被复制的依据是其适应度的大小，适应度大者个体是否被复制的依据是其适应度的大小，适应度大者被复制，小者被淘汰，使新群体中的个体总数与原来群体相被复制，小者被淘汰，使新群体中的个体总数与原来群体相同。同。在遗传算法中，常常采用在遗传算法中，常常采用J.Holland教授提出的教授提出的轮盘赌方轮盘赌方式式选择复制对象
48、。选择复制对象。（3 3）复制）复制46 表中第一行说明有表中第一行说明有10个个体参与选择，第二行表示各个体的个个体参与选择，第二行表示各个体的适应度，第三行标记适应度的累计值，总值为适应度，第三行标记适应度的累计值，总值为76。然后，在。然后，在 0，76 区间内产生均匀分布的随机数，如第四行所示。依次序将第三区间内产生均匀分布的随机数，如第四行所示。依次序将第三行的累计适应度与随机数相比较，其值大于或等于随机数的第一行的累计适应度与随机数相比较，其值大于或等于随机数的第一个个体列为入选的复制对象。例如，第一个随机数是个个体列为入选的复制对象。例如，第一个随机数是23，除了，除了1号、号、
49、2号个体外，其余个体的累计适应度均大于号个体外，其余个体的累计适应度均大于23，然而，然而3号个体累计号个体累计值为值为27，是第一个大于，是第一个大于23的个体，所以它入选。的个体，所以它入选。个体序号12345678910适应度8217721211737适应度累计值8102734364859666976随机数2349761312757被选中的个体37103137轮盘选择示例：轮盘选择示例：（3 3）复制）复制47（1）依次累计群体内各个体的适应度，得相应的累计）依次累计群体内各个体的适应度，得相应的累计值值Si，最后一个累计值为，最后一个累计值为Sn；（2）在）在 0，Sn 区间内产生均匀
50、分布的随机数区间内产生均匀分布的随机数R；（3）依次用）依次用Si与与R相比较，第一个出现相比较，第一个出现Si大于或等于大于或等于R的个体的个体i被选为复制对象；被选为复制对象；（4）重复（）重复（2）、（）、（3），直至满足所需要的个体数目。），直至满足所需要的个体数目。上述选择过程，可描述如下：上述选择过程，可描述如下：（3 3）复制）复制48 因此，适应度因此，适应度fi越大，越大，Si的距离越大，随机数落的距离越大，随机数落在这个区间的可能性越大，第在这个区间的可能性越大，第i个个体被选中的机会也个个体被选中的机会也越多。如下图所示。越多。如下图所示。表面上看，复制个体的选择是随机的