人工智能遗传算法

计算智能计算智能是信息科学和生命科学相互交叉的前沿领域,是现代科学技术发展的一个重要体现。

计算智能涉及神经网络、模糊逻辑、进化计算和人工生命等领域，它的研究和发展反映了当代科学技术多学科交叉与集成的重要发展趋势。贝兹德克于1994年提出了一种A，B，C智能模型，从而表示ABC与神经网络、模式识别和智能之间的关系：

A：Artificial

,表示人工的、符号的（非生物的）

B：Biological,表示生物的

C：Computational,表示计算的

计算智能是一种智力方式的底层认知，它与人工智能的区别是认知层次从中层下降到底层而已。中层系统含有知识，底层系统没有知识。

关于A，B，C智能计算智能与人工智能的区别与联系NN

NeuralNetwork神经网络PR

PatternRecognition模式识别计算智能系统与人工智能系统当一个系统只涉及数值（底层）数据，含有模式识别部分，不应用于人工智能意义上的知识，而且系统能够呈现出：（1）计算适应性（2）计算容错性（3）接近人的计算速度（4）计算误差率与人接近则该系统就是计算智能系统。当一个智能计算系统以非数值方式并加上知识，即为人工智能系统。神经计算（NeuralComputation）神经计算研究的进展1943年麦卡洛奇和皮茨提出神经网络模型的概念（称为MP模型）20世纪60年代威德罗和霍夫提出了自适应线性元件。60年代末到80年代初初与研究的低潮期80年代后又大发展遗传算法

遗传算法简称GA（GeneticAlgorithms）是1975年由美国Michigan(密歇根州)大学的J.Holland教授提出的模拟自然界生物遗传学（孟德尔）和生物进化论（达尔文）通过人工方式所构造的一类并行随机搜索最优化方法，是对生物进化过程进行的一种数学仿真，是进化计算的重要形式。1、遗传算法

在生物系统中，进化被认为是一种成功的自适应方法，具有很好的健壮性。其主要特点是(1)直接对结构对象进行操作，不存在求导和函数连续性的限定；(2)具有内在的隐含并行性和更好的全局寻优能力；(3)采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。遗传算法已被广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。它是现代有关计算智能中的关键技术之一。

遗传算法是以达尔文的自然选择学说为基础发展起来的。自然选择学说包括以下三个方面：1、遗传算法（1）遗传：这是生物的普遍特征，亲代把生物信息交给子代，子代总是和亲代具有相同或相似的性状。生物有了这个特征，物种才能稳定存在。（2）变异：亲代和子代之间以及子代的不同个体之间的差异，称为变异。变异是随机发生的，变异的选择和积累是生命多样性的根源。（3）生存斗争和适者生存：具有适应性变异的个体被保留下来，不具有适应性变异的个体被淘汰，通过一代代的生存环境的选择作用，性状逐渐逐渐与祖先有所不同，演变为新的物种。遗传算法将““优胜劣汰，，适者生存””的生物进化化原理引入优优化参数形成成的编码串群群体中，按所所选择的适应应度函数并通通过遗传中的的复制、交叉叉及变异对个个体进行筛选选，适应度高高的个体被保保留下来，组组成新的群体体，新的群体体既继承了上上一代的信息息，又优于上上一代。这样样周而复始，，群体中个体体适应度不断断提高，直到到满足一定的的条件。遗传传算法的算法法简单，可并并行处理，并并能到全局最最优解。如：爱斯基摩摩人，非洲原始部落落2、遗传算法的的基本操作为为：（1）复制（ReproductionOperator）复制是从一个个旧种群中选选择生命力强强的个体位串串产生新种群群的过程。具具有高适应度的位串更有可可能在下一代代中产生一个个或多个子孙孙。复制操作可以以通过随机方方法来实现。。首先产生0~1之间均匀分布布的随机数，，若某串的复复制概率为40%，则当产生的的随机数在0.40~1.0之间时，该串串被复制，否否则被淘汰。。（2）交叉（CrossoverOperator）复制操作能从从旧种群中选选择出优秀者者，但不能创创造新的染色色体。而交叉叉模拟了生物物进化过程中中的繁殖现象象，通过两个个染色体的交交换组合，来来产生新的优优良品种。交叉的过程为为：在匹配池池中任选两个个染色体，随随机选择一点点或多点交换换点位置；交交换双亲染色色体交换点右右边的部分，，即可得到两两个新的染色色体数字串。。交叉体现了自自然界中信息息交换的思想想。交叉有单单点交叉、两两点交叉、还还有一致交叉叉、顺序交叉叉和周期交叉叉。单点交叉叉是最基本的的方法，应用用较广。它是是指染色体切切断点有一处处，例：（3）变异(MutationOperator)变异运算用来来模拟生物在在自然的遗传传环境中由于于各种偶然因因素引起的基基因突变，它它以很小的概概率随机地改改变遗传基因因（表示染色色体的符号串串的某一位））的值。在染染色体以二进进制编码的系系统中，它随随机地将染色色体的某一个个基因由1变为0，或由0变为1。若只有选择和和交叉，而没没有变异，则则无法在初始始基因组合以以外的空间进进行搜索，使使进化过程在在早期就陷入入局部解而进进入终止过程程，从而影响响解的质量。。为了在尽可可能大的空间间中获得质量量较高的优化化解，必须采采用变异操作作。17设自变量x介于0～31，求其其二次函数数的最大值值，即：maxf(x)=x2,x∈∈[0,31]3、遗传算法法示例--f(x)=x2极大值问题题5001000031xf(x)当然，利用用简单的代代数运算，，很容易求求出该问题题的解。现现在改用遗遗传算法求求解，遗传传算法通常常包括下述述内容：18（1）编码遗传算法首首先要对实实际问题进进行编码，，用字符串串表达问题题。这种字字符串相当当于遗传学学中的染色色体。每一一代所产生生的字符串串个体总和称称为群体。为了实现现的方便，，通常字符符串长度固固定，字符符选0或1。本例中，利利用5位二二进制数表表示x值，采用随随机产生的的方法，假假设得出拥拥有四个个个体的初始始群体，即即：01101，11000，01000，10011。x值相应为13，24，8，19。个体编号初始群体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.22412019（2）计算算适应度衡量字符串串（染色体体）好坏的的指标是适应度，它也就是是遗传算法法的目标函函数。本例中适应应度比较简简单，用x2计算。表中还列出出了当前适适应度的总总和∑f(xi)及平均值f，即：∑f(xi)=f(x1)+f(x2)+f(x3)+f(x4)=1170f=∑∑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表示每个个个体的相对适应度度，它反映了了个体之间间的相对优优劣性。如如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.001.970.22412021（3）复制制为了将已有有的群体变变为下一代代群体，遗遗传算法仿仿效进化论论中“自然然选择、适适者生存””的原则，，从旧群体体中选择优优良个体进进行复制。。选择的依依据是个体体适应度的的大小，适适应度大的的个体接受受复制，使使之繁殖；；适应度小小的个体则则删除掉，，遭到淘汰汰。22（3）复制制在本例中，，根据相对对适应度的的大小对个个体进行取取舍，2号号个体性能能最优，予予以复制繁繁殖。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)平均值f最大值最小值1170293576641.000.250.490.064.001.001.970.22412023（3）复制制从表中的第第4列可以以看出，复复制后产生生的新一代代群体的平平均适应度度明显增加加，由原来来的293增加到421。造造成平均适适应度增加加的原因有有二：1）淘汰原原来最差的的个体。使使最小适应应度由原来来的64增增加到169。2）增加了了优良个体体（2号））的个数，，使适应度度累计值增增加。个体编号复制后群体xi复制后适应度f(xi)交换对象交换位置交换后群体复制后适应度f(xi)1234（1）01101（2）11000（2）11000（4）10011132424191695765763612号1号4号3号443301100110011101110000144625729256总计平均值最大值最小值1682421576361175443972925624（4）交换换通过复制产产生的新群群体，其性性能得到改改善，然而而它不能产产生新的个个体。为了了产生新的的个体，遗遗传算法仿仿照生物学学中杂交的的方法，对对染色体（（字符串））的某些部部分进行交交叉换位。。被交换的的母体都选选自经过复复制产生的的新一代个个体（优胜胜者）。25（4）交换换本例中，利利用随机配配对的方法法，决定1号和2号号个体、3号和4号号个体分别别交换，如如表中第5列。再利利用随机定定位的方法法，确定这这两对母体体交叉换位位的位置分分别从字符符长度的第第4位及第第3位开始始。如：3号、4号号个体从字字符长度第第3位开始始交换。交交换开始的的位置称交换点。个体编号复制后群体xi复制后适应度f(xi)交换对象交换位置交换后群体复制后适应度f(xi)123401101110001100010011132424191695765763612号1号4号3号443301100110011101110000144625729256总计平均值最大值最小值168242157636117544397292561100010011110111000026（4）交换换从表中可以以看出，交交换后出现现优异个体体3号，其其适应度高高达729，大大高高于交换前前的最大值值（576）。与此此同时，平平均适应度度也从原来来的421提高到439，说说明交换后后的群体正正朝优良方方向发展。。个体编号复制后群体xi复制后适应度f(xi)交换对象交换位置交换后群体复制后适应度f(xi)123401101110001100010011132424191695765763612号1号4号3号443301100110011101110000144625729256总计平均值最大值最小值1682421576361175443972925627（5）突变变遗传算法模模仿生物学学中基因突突变的方法法，将个体体字符串某某位符号进进行逆变，，即由1变变为0或由由0变为1。例如，，下式左侧侧的个体于于第3位突突变，得到到新个体如如右侧所示示。上述（2））～（5））反复执行行，直至得得出满意的的最优解。。由上可知，，遗传算法法参考生物物中有关进进化与遗传传的过程，，利用复制制、交换、、突变等操操作，不断断循环执行行，逐渐逼近全全局最优解解。遗传算法中中，个体是是否进行突突变以及在在哪个部位位突变，都都由事先给给定的概率率决定。通通常，突变变概率很小小，约为0.008，本例的的第一代中中就没有发发生突变。。100001010028从数学角度度看，遗传传算法实质质上是一种种搜索寻优优技术。它它从某一初初始群体出出发，遵照照一定的操操作规则，，不断迭代代计算，逐逐步逼近最最优解。这这种搜索技技术，有如如下特点：：4、遗传算法的的基本特征征从上述简单单例子可以以看出，遗遗传算法仿仿照生物进进化和遗传传的规律，，利用复制制、交换、、突变等操操作，使优优胜者繁殖殖，劣败者者消失，一一代一代地地重复同样样的操作，，最终找出出最优解。。29（1）智能能式搜索遗传算法的的搜索策略略，既不是是盲目式的的乱搜索，也不是穷举式的全面搜索索，它是有有指导的搜搜索。指导导遗传算法法执行搜索索的依据是是适应度，也就是它它的目标函函数。利用用适应度，，使遗传算算法逐步逼逼近目标值值。（2）渐进进式优化遗传算法利利用复制、、交换、突突变等操作作，使新一一代的结果果优越于旧旧一代，通通过不断迭迭代，逐渐渐得出最优优的结果，，它是一种种反复迭代代的过程。。4、遗传算法的的基本特征征30（3）全局局最优解遗传算法由由于采用交交换、突变变等操作，，产生新的的个体，扩扩大了搜索索范围，使使得搜索得得到的优化化结果是全全局最优解解而不是局局部最优解解。（4）黑箱箱式结构遗传算法根根据所解决决问题的特特性，进行行编码和选选择适应度度。一旦完完成字符串串和适应度度的表达，，其余的复复制、交换换、突变等等操作都可可按常规手手续执行。。个体的编编码如同输输入，适应应度如同输输出。因此此遗传算法法从某种意意义上讲是是一种只考考虑输入与与输出关系系的黑箱问问题。4、遗传算法的的基本特征征31（5）通用用性强传统的优化化算法，需需要将所解解决的问题题用数学式子表示，常常常要求解该该数学函数数的一阶导导数或二阶阶导数。采采用遗传算算法，只用用编码及适适应度表示示问题，并并不要求明明确的数学学方程及导导数表达式式。因此，，遗传算法法通用性强强，可应用用于离散问问题及函数数关系不明明确的复杂杂问题，有有人称遗传传算法是一一种框架型算法法，它只有一一些简单的的原则要求求，在实施施过程中可可以赋予更更多的含义义。（6）并行行式算法遗传算法是是从初始群群体出发，，经过复制制、交换、、突变等操操作，产生生一组新的的群体。每每次迭代计计算，都是是针对一组组个体同时时进行，而而不是针对对某个个体体进行。因因此，尽管管遗传算法法是一种搜搜索算法，，但是由于于采用这种种并行机理理，搜索速速度很高。。这种并行行式计算是是遗传算法法的一个重重要特征。。4、遗传算法的的基本特征征32遗传算法受受生物进化化与遗传的的启发，形形成一种独独特的优化化方式，因因此，遗传传算法的运运算原则常常常与生物物进化及遗遗传学说吻吻合，而且且其术语也也常常仿效效生物学的的术语。遗传算法的的运算基础础是字符串串，它就相相当于生物物学中的染染色体。字符串由一一系列字符符组成，每每个字符都都有特定的的含义，反反应所解决决问题的某某个特征，，这就相当当于基因，，即染色体体DNA的片段。在进行交换换、突变操操作时，遗遗传算法只只涉及到字字符串某些些片段，这这就类似于于遗传过程程只涉及某某些基因而而不是整个个染色体。。5、遗传算法的的生物学含含义33遗传学很注注重等位基因，它是反映映生物某一一形态所对对应的基因因。在遗传传算法的字字符串中，，每个字符符都反映问问题的某一一特性，这这也就相当当于等位基基因，至于于等位基因因的位置，，也就相当当于该字符符在字符串串中的位置置。在遗传学中中，杂交产产生的子代代里显现出出亲本的性性状，称作作显性性状状，未显现现出来的亲亲本性状叫叫作隐性性性状。控制制显性性状状的基因是是显性基因，用大写英英文字母表表示。控制制隐性性状状的基因是是隐性基因，用小写英英文字母表表示。在遗遗传算法中中，模仿这这种大、小小字母表达达方式，对对显性基因因和隐性基基因采取不不同的操作作。5、遗传算法的的生物学含含义34生物学术语语在遗传算算法中的对对应意义如如下表。序号生物学遗传算法123456染色体（Chromosome）基因（Gene）等位基因（Allele）基因位置（Locus）基因型（Genotype）表现型（Phenotype）字符串字符对应的字符字符的位置字符串结构字符串含义5、遗传算法的的生物学含含义35根据前面所所讲的示例例，可以看看出遗传算算法的实施施过程中包包括编码、、产生群体体、计算适适应度、复复制、交换换、突变等等操作。遗传算法的的详细流程程如下图。。6、遗传算法的的工作步骤骤36Gen：遗传（迭迭代）的代代次。表明明遗传算法法反复执行行的次数，，即已产生生群体的代代次数目。。M：群群体体中中拥拥有有的的个个体体数数目目。。i：已已处处理理个个体体的的累累计计数数，，当当i等于于M，表表明明这这一一代代的的个个体体已已全全部部处处理理完完毕毕，，需需要要转转入入下下一一代代群群体体。。交叉叉率率Pc就是是参参加加交交叉叉运运算算的的染染色色体体个个数数占占全全体体染染色色体体总总数数的的比比例例，，记记为为Pc,取取值值范范围围一一般般为为0.4～～0.99。。变异异率率Pm是指指发发生生变变异异的的基基因因位位数数所所占占全全体体染染色色体体的的基基因因总总位位数数的的比比例例，，记记为为Pm，，取取值值范范围围一一般般为为0.0001～～0.1。。复制制概概率率Pt用于于控控制制复复制制与与淘淘汰汰的的个个体体数数目目。。Pc

Pt

Pm

NoNoYesGen：=0随机产生初始群体满足终止条件

计算群体中各个体的适应度i：=0i：=M?选择遗传算子及概率根据适应度选择两个个体i：=i+1执行交换将两个交换结果添入新群体

i：=i+1将复制结果添入新群体

执行复制根据适应度选择一个个体将突变结果添入新群体执行突变

Gen：=Gen+1

输出结果结束Yes37概括括地地讲讲，，遗遗传传算算法法主主要要执执行行以以下下四四步步：：（1））随机机地地建建立立由由字字符符串串组组成成的的初初始始群群体体；；（2））计算算各各个个体体的的适适应应度度；；（3））根据据遗遗传传概概率率，，利利用用下下述述操操作作产产生生新新群群体体：：1））复制制。将将已已有有的的优优良良个个体体复复制制后后添添入入新新群群体体中中，，删删除除劣劣质个个体体；；2））交换换。将将选选出出的的两两个个个个体体进进行行交交换换，，所所产产生生的的新新个个体体添添入新新群群体体中中。。3））突变变。随随机机地地改改变变某某一一个个体体的的某某个个字字符符后后添添入入新新群群体体中中。。（4））反复复执执行行（（2））、、（（3））后后，，一一旦旦达达到到终终止止条条件件，，选择择最最佳佳个个体体作作为为遗遗传传算算法法的的结结果果。。38遗传传算算法法的的工工作作对对象象是是字字符符串串，，因因此此对对字字符符串串的的编编码码有有两两点点要要求求：：一一是是字字符符串串要要反反映映所所研研究究问问题题的的性性质质；；二二是是字字符符串串的的表表达达要要便便于于计计算算处处理理。。遗传传算算法法关关键键问问题题（1）编编码码遗传传算算法法常常常常用用二二进进制制的的0/1字字符符编编码码。。当当问问题题比比较较简简单单，，例例如如只只描描述述高高/低低、、大大/小小等等布布尔尔型型性性质质时时，，每每一一位位0/1变变量量就就代代表表一一个个性性质质。。例如，某事物物只涉及到贵贵/贱、大/小及好/坏坏时，我们可可用三位0/1字符表示示，并规定第第1位字符代代表贵/贱，，第2位字符符代表大/小小，第3位字字符代表好/坏。如111代表贵-大-好，而而100代表表贵-小-好好。39当问题的性质质要用数值描描述时，则编编码变成用二二进制数表示示十进制数。。例如，用4位0/1字字符串表示1～16。根据排列计算算，长度（位位数）为L的0/1字符符串，可以表表达2*2*2‥‥2=2L种情况。如果果所描述性质质的最小值不不是0时，即即性质介于Umin～Umax之间，为了减减小字符串长长度，可以采采用映射的方方法，用2L个二进制数表表示[Umin，Umax]。这时，令令L个0表示Umin，L个1表示Umax，其中L大小取决于（（Umax—Umin），其余的数数则用线性插插值决定。例例如，对于[16，31]的十十进制数，我我们可以用4位二进制0/1字符在在[0000，1111]范围围内表示。（1）编码Umin0…0…Umax1…140对于兼有多种种性质的问题题，可以采用用长字符串顺顺序分别表示示。例如，可可选25位0/1字符串串表示物体的的体积、重量量及颜色，其其中前10位位数表示体积积量，中间10位数表示示重量，后5位数表示颜颜色。在遗传算法中中，字符串的的长度常常是是固定的，以以便按统一的的方式执行操操作。个别研研究者采用不不等长的字符符串，这时就就需要跟踪记记录，经常调调整操作方式式，比较烦琐琐。从生物学角度度看，编码就就相当于选择择遗传物质，，它是研究遗遗传的基础。。同样，在遗遗传算法中编编码也是一项项基础性工作作。（1）编码41在遗传算法中中，衡量个体体优劣的尺度度是适应度。根据适应度度的大小，决决定某些个体体是繁殖或是是消亡。因此此，适应度是是驱动遗传算算法的动力。。从生物学角角度讲，适应应度相当于““生存竞争，，适者生存””的生物生存存能力，在遗遗传过程中具具有重要意义义。通常，适应度度是费用、赢利、、方差等目标的表达达式。在运用用过程中可以以借鉴以下经经验。（2）适应度42<1>统一表达形式式在实际问题中中，有时希望望适应度越大大越好（如赢赢利、劳动生生产率），有有时要求适应应度越小越好好（费用、方方差）。为了了使遗传算法法有通用性，，这种最大、、最小值问题题宜统一表达达。通常都统统一按最大值值问题处理，，而且不允许许适应度小于于0。对于最小值问问题，其适应应度按下式转转换：f(x)=Cmax-g(x)当g(x)<Cmax0其他情况f(x)：转换后的适适应度。g(x)：最小值问题题下的适应度度。Cmax：足够大的常常数，可取g(x)的最大值。（2）适应度43<1>统一表达形式式为了保证适应应度不出现负负值，对于有有可能产生负负值的最大值值问题，可以以采用下式进进行变换：f(x)=U(x)+Cmin

当U(x)+Cmin>00其他情况f(x)：变换后的的适应度。U(x)：最大值问题题下的适应度度。Cmin：足够大的常常数。（2）适应度44<2>适应度缩放在执行遗传算算法的初始阶阶段，各个个个体的适应度度比较离散，，某些个体的的适应度会很很高或很低。。对于个别适适应度很高的的个体，会连连续多次被复复制；对于适适应度很低的的个体，会过过早被舍弃。。这种不正常常的取舍，对对于个体数目目不多的群体体尤为严重，，会把遗传算算法的搜索引向误区区，过早地收敛敛于局部最优解。为了克服这这种缺陷，需需要采用适应应度缩放技术术，将适应度度按下式变换换：f'：缩放后的的适应度。f：原来的适应应度。a、b：系数。f'=a*f+b利用这种缩放放技术，缩小小（放大）原原来最大（最最小）的适应应度，从而可可以减弱离散散现象。（2）适应度45复制是遗传算算法的基本算算子，它将优优良个体在下下一代新群体体中繁殖，体体现了“适者者生存”的自自然选择原则则。个体是否被复复制的依据是是其适应度的的大小，适应应度大者被复复制，小者被被淘汰，使新新群体中的个个体总数与原原来群体相同同。在遗传算法中中，常常采用用J.Holland教授提出的轮盘赌方式选择复制对象象。（3）复制46表中第一行说说明有10个个个体参与选选择，第二行行表示各个体体的适应度，，第三行标记记适应度的累累计值，总值值为76。然然后，在[0，76]区间内产产生均匀分布布的随机数，，如第四行所所示。依次序序将第三行的的累计适应度度与随机数相相比较，其值值大于或等于于随机数的第第一个个体列列为入选的复复制对象。例例如，第一个个随机数是23，除了1号、2号个个体外，其余余个体的累计计适应度均大大于23，然然而3号个体体累计值为27，是第一一个大于23的个体，所所以它入选。。个体序号12345678910适应度8217721211737适应度累计值8102734364859666976随机数2349761312757被选中的个体37103137轮盘选择示例例：（3）复制47（1）依次累累计群体内各各个体的适应应度，得相应应的累计值Si，最后一个累累计值为Sn；（2）在[0，Sn]区间内产生均均匀分布的随随机数R；（3）依次用用Si与R相比较，第一一个出现Si大于或等于R的个体i被选为复制对对象；（4）重复（（2）、（3），直至满满足所需要的的个体数目。。上述选择过程程，可描述如如下：（3）复制48因此，适应度度fi越大，△Si的距离越大，，随机数落在在这个区间的的可能性越大大，第i个个体被选中中的机会也越越多。如下图图所示。表面上看，复复制个体的选选择是随机的的。但是，选选择时是依据据相邻两个适适应度累计值值的差值△Si：△Si=Si–Si-1=fifi表示第i个个体的适应应度（3）复制49轮盘（赌）选选择原理S2S1S3S4SiSn-1Sn…图中的指针固固定不动，外外圈的圆环可可以任意转动动，圆环中每每段对应于适适应度的大小小。从统计意意义上讲，适适应度大的个个体被复制的的机会越大。。当然，适应应度小的个体体尽管被复制制的概率小，，但仍有可能能被“破格””复制，这样样就增加个体体的多样性，，便于执行交交换及突变。。所以，轮盘盘选择方法既既体现“适者者生存”原则则，又保持个个体性态多种种多样。（3）复制50选择复制个体体的随机方法法还有别的形形式，不过轮轮盘选择法是是最常用的方方法。每代群体中，，被复制的个个体数目由复复制概率Pt控制，Pt常取0.1～～0.2，也也就是说，群群体中有10%个体被复复制，相应地地有10%个个体被淘汰，，以保持群体体大小。（3）复制51下表是是个体体两两两交换换的示示例，，字符符串内内的下下横线线代表表交换换点的的位置置，交交换点点及其其后面面的字字符串串两两两互换换。在遗传传算法法中，，交换换是产产生新新个体体的主主要手手段。。它仿仿照生生物学学中杂杂交的的原理理，将将两个个个体体（染染色体体）的的部分分字符符（基基因））互相相交换换。序号交换前交换后12亲代1：111111亲代2：000000子代1：111100子代2：00001134亲代1：101101亲代2：001100子代1：101100子代2：001101（4）交换换52执行交交换的的个体体是随随机选选择的的。首首先，，要确确定交交换的的概率率Pc，大致致为0.5～0.8左右右。这这就是是说，，约50%～80%的个个体要要执行行交换换。然然后，，采用用上述述轮盘盘选择择的方方法，，按适适应度度大小小选择择被交交换的的个体体，依依次两两两进进行交交换。。交换点点的选选择也也是随随机的的。假假设字字符串串长度度为L，则在在[0，，L]区间内内产生生随机机整数数，该该整数数便是是交换换点的的位置置。需需要注注意的的是，，交换换点不不能选选在第第一个个字符符上。。因此此，长长度为为L的字符符串，，可供供选择择的交交换点点为（（L-1）个。。根据交交换点点数目目的不不同，，可分分为一点交交换和多点交换换，前者者只选选取一一个交交换点点，该该点之之后的的字符符全部部参加加交换换。后后者选选择两两个或或多个个交换换点，，只有有两点点间的的字符符才参参加交交换。。当字字符串串长度度大时时，常常采用用两点点交换换。此此外还还有多点交交换，即对对长字字符串串实行行多段段交换换。（4）交换换53通过交交换，，子代代的字字符串串不同同于亲亲代。。有时时，这这种差差别很很明显显，如如表中中的第第一组组个体体，被被交换换部分分完全全不一一样。。有时时，这这种差差别却却不大大，如如表中中的第第二组组个体体，被被交换换的三三个字字符中中只有有最后后一个个字符符发生生变化化。后后一种种情况况说明明交换换后产产生的的个体体，其其性态态变化化不大大。尽尽管如如此，，交换换仍然然是遗遗传算算法产产生新新个体体的主主要手手段。。正是是有了了交换换操作作，群群体的的性态态才多多种多多样。。序号交换前交换后12亲代1：111111亲代2：000000子代1：111100子代2：00001134亲代1：101101亲代2：001100子代1：101100子代2：001101传统的的优化化算法法，例例如动动态规规划法法、个个体性性态不不能增增添，，只能能在原原有的的个体体群体体中择择优，，从而而限制制了搜搜索寻寻优的的范围围。因因此，，可以以说，，如果果没有有交换换，遗遗传算算法就就失去去了其其优越越性。。（4）交换换54突变是是遗传传算法法中产产生新新个体体的另另一种种方法法，它它是将将某一一个体体的某某一位位字符符进行行补运运算，，使0变为为1，，或使使1变变为0。突变个个体的的选择择以及及突变变位置置的确确定，，都是是采用用随机机的方方法产产生。。首先先，确确定突突变概概率Pm，Pm通常较较小，，约为为0.001～～0.01。也也就是是说，，1000个字字符中中有1～10个个发生生突变变。然然后，，针对对每个个字符符在[0，1]之间间产生生三位位有效效数的的均匀匀分布布随机机数。。若Pm=0.008，凡凡是随随机数数小于于0.008所所对应应的字字符，，将实实现突突变。。示例例如下下：（5）突变变55表中有有三个个字符符长度度为4的旧旧个体体。对对应每每个字字符，，依次次产生生[0，，1]区区间均均匀分分布的的随机机数12个个。表表中只只有2号个个体的的第3个字字符以以及3号个个体的的第4个字字符需需要发发生突突变，，因为为它们们对应应的随随机数数小于于0.008。。序号旧个体随机数新字符新个体1231010110000100.8010.1020.2660.3730.1200.0960.0050.8400.7600.4730.8940.00111101011100011（5）突变变56随机确确定突突变的的位置置后，，执行行突变变的方方法有有两种种。一一种是是直接接产生生突变变，将将表中中的2号和和3号号旧个个体分分别改改写作作1110及0011。。另一种种方法法，按按50%的的概率率随机机产生生新字字符0或1。表表中2号个个体产产生的的新字字符为为0，，与需需要突突变的的第三三行字字符恰恰好一一样，，因此此新个个体等等同于于旧个个体。。表中中3号号个体体产生生的新新字符符（1）不不同于于待突突变的的原来来字符符（0），，因此此新个个体不不同于于旧个个体。。很明明显，，后一一种突突变方方法的的突变变概率率仅为为前一一种方方法的的50%。。通常常建议议采用用后一一种方方法，，增加加突变变的随随机性性。序号旧个体随机数新字符新个体1231010110000100.8010.1020.2660.3730.1200.0960.0050.8400.7600.4730.8940.00101101011000011（5）突变变57还有一一种执执行突突变的的方法法，是是根据据给定定的概概率Pm1。随机机选择择突变变的个个体。。当被被突变变的个个体选选中后后，在在字长长范围围内用用均匀匀分布布的随随机数数选择择突变变的字字符，，使该该个体体发生生突变变。然然而，，这时时的概概率Pm1，不同同于突突变概概率Pm，后者者是针针对字字符而而言，，前者者是针针对个个体。。遗传传算法法中讨讨论的的正是是字符符的突突变概概率Pm，两者者间的的关系系与字字长L有关。。尽管突突变和和交换换都能能产生生新个个体，，但是是在遗遗传算算法中中，交交换的的作用用远比比突变变重要要。（5）突变变58遗传算算法是是一种种反复复迭代代的搜搜索方方法，，它通通过多多次进进化逐逐渐逼逼近最最优解解而不不是恰恰好等等于最最优解解，因因此需需要确确定终终止条条件。。其一,最常用用的终终止方方法是是规定定遗传传（迭迭代））的代代次。。刚开开始时时，迭迭代次次数小小一些些，如如规定定100次次。然然后视视情况况逐渐渐增加加次数数，可可达到到上千千次。。（6）终止条件件59当目标函数数是方差这这一类有最最优目标值值的问题时时，可采用用控制偏差差的方法实实现终止。。一旦遗传传算法得出出的目标函函数值（适适应度）与与实际目标标值之差小小于允许值值后，算法法终止，即即：f(x)：遗传算算法得出的的目标函数数值。f*：实际目标标值。△：足够小的的数。|f(x)–f*|≤△（6）终止条件件60第三种终止止方法是检检查适应度度的变化。。在遗传算算法后期，，一旦最优优个体的适适应度没有有变化或变变化很小时时，即令计计算终止。。遗传算法的的另一个重重要参数是是每代群体体中的个体体数。很明明显，个体体数目越多多，搜索范范围越广，，容易获取取全局最优优解。然而而个体数目目太多，每每次迭代时时间也长。。通常，个个体数目可可取100-1000之间。（6）终止条件