人工智能-9遗传算法

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

计算智能涉及神经网络、模糊逻辑、进化计算和人工生命等领域，它的研究和发展反映了当代科学技术多学科交叉与集成的重要发展趋势。贝兹德克于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）编码Umin

0…0…Umax

1…1

40对于兼有多种性质的问题，可以采用长字符串顺序分别表示。例如，可选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）终止条件7遗传算法的应用领域（1）函数优化。

函数优化是遗传算法的经典应用领域，也是遗传算法进行性能评价的常用算例。尤其是对非线性、多模型、多目标的函数优化问题，采用其他优化方法较难求解，而遗传算法却可以得到较好的结果。（2）组合优化。随着问题的增大，组合优化问题的搜索空间也急剧扩大，采用传统的优化方法很难得到最优解。遗传算法是寻求这种满意解的最佳工具。例如，遗传算法已经在求解旅行商问题、背包问题、装箱问题、图形划分问题等方面得到成功的应用。（3）生产调度问题在很多情况下，采用建立数学模型的方法难以对生产调度问题进行精确求解。在现实生产中多采用一些经验进行调度。遗传算法是解决复杂调度问题的有效工具，在单件生产车间调度、流水线生产车间调度、生产规划、任务分配等方面遗传算法都得到了有效的应用。（4）自动控制。在自动控制领域中有很多与优化相关的问题需要求解，遗传算法已经在其中得到了初步的应用。例如，利用遗传算法进行控制器参数的优化、基于遗传算法的模糊控制规则的学习、基于遗传算法的参数辨识、基于遗传算法的神经网络结构的优化和权值学习等。（5）机器人例如，遗传算法已经在移动机器人路径规划、关节机器人运动轨迹规划、机器人结构优化和行为协调等方面得到研究和应用。（6）图像处理遗传算法可用于图像处理过程中的扫描、特征提取、图像分割等的优化计算。目前遗传算法已经在模式识别、图像恢复、图像边缘特征提取等方面得到了应用。

利用遗传算法求Rosenbrock函数的极大值8遗传算法应用--求函数极值

用长度为10位的二进制编码串来分别表示两个变量x1,x2。10位二进制编码串可以表示从0到1023之间的1024个不同的数，故将x1,x2的定义域离散化为1023个均等的区域，包括两个端点在内共有1024个不同的离散点。从离散点-2.048到离散点2.048，分别对应于从0000000000(0)到1111111111(1023)之间的二进制编码。编码

将x1,x2分别表示的两个10位长的二进制编码串连接在一起，组成一个20位长的二进制编码串，它就构成了这个函数优化问题的染色体编码方法。使用这种编码方法，解空间和遗传算法的搜索空间就具有一一对应的关系。例如：表示一个个体的基因型，其中前10位表示x1，后10位表示x2。确定解码方法：解码时需要将20位长的二进制编码串切断为两个10位长的二进制编码串，然后分别将它们转换为对应的十进制整数代码，分别记为y1和y2。依据个体编码方法和对定义域的离散化方法可知，将代码y转换为变量x的解码公式为

例如，对个体

它由两个代码所组成上述两个代码经过解码后，可得到两个实际的值确定个体评价方法：由于Rosenbrock函数的值域总是非负的，并且优化目标是求函数的最大值，故可将个体的适应度直接取为对应的目标函数值，即选个体适应度的倒数作为目标函数设计遗传算子：选择运算使用比例选择算子，交叉运算使用单点交叉算子，变异运算使用基本位变异算子。确定遗传算法的运行参数：群体大小M=80，终止进化代数G=100，交叉概率Pc=0.60，变异概率Pm=0.10。

采用上述方法进行仿真，经过200步迭代，当时，Rosenbrock函数具有极大值，极大值为3880.3。演讲完毕，谢谢观看！附录资料：人工智能简介​AboutTeachingPlan基本要求：人工智能是计算机科学中涉及研究、设计和应用智能机器的一个分支，是目前迅速发展的一门新兴学科，新思想新方法层出不穷。其基本思想是利用机器来模仿和执行人脑的功能，如判断、推理、证明、识别、感知、理解、设计、思考、规划、学习和问题求解等思维活动。对于培养学生计算机技术的应用能力，开阔思路和视野，有重要意义。

​AboutTeachingPlan因此，要求学生掌握知识表示和问题求解的几种常用方法，尤其是不确定性推理；掌握机器学习基本概念，了解几种机器学习方法尤其是神经网络学习方法；掌握专家系统的概念，了解专家系统设计方法，掌握一些智能控制方法，了解国内外人工智能研究尤其是机器人的最新进展；具有一定的人工智能编程设计能力（利用Lisp或Prolog语言）。​AboutTeachingPlan课程内容以及学时分配人工智能引论(1) 人工智能概念及与计算机的关系，研究途径、内容和应用领域概况介绍，其他最新材料。符号主义、连接主义、行为主义三大流派人工智能数学基础(1)知识表示方法（2） 状态空间法、问题归约法，谓词逻辑法、产生式表示法（动物识别系统）；CLIPS语言；语义网络法、框架法（这是结构化表示）；剧本、过程、Petri网、面向对象的表示。​AboutTeachingPlan 搜索技术和策略（3-4）状态空间法，盲目搜索和启发式搜索，A*算法；海伯伦理论、消解原理和策略；与\或形推理和搜索策略；其他求解技术。 不确定推理技术（3-4）主观Bayes理论；可信度方法和证据理论；系统组织技术；非单调推理；Rete快速算法；模糊推理技术；基于语义网络和框架不确定推理； 专家系统（2）专家系统概念、结构和知识获取；黑板模型、知识组织、管理及系统建造和开发工具；专家系统举例及编程。

人工智能程序设计（1）人工智能语言基本机制：LISP和PROLOG。​AboutTeachingPlan 模式识别导论（3）模式识别专题：概率模式识别。模式识别专题：结构模式识别 机器学习（1）：机械,解释经验,事例,归纳,概念,类比学习等；统计,结构,模糊模式识别。 专题讲座（3次） 1)神经网络基本理论和应用 (史奎凡课程：安排于人工智能理论与应用课程内)； 2)智能体（Agent）； 3)自然语言处理； 4)智能控制和机器人科学 智能控制的结构理论和研究领域，智能控制系统及应用示例；机器人规划、机器视觉和自然语言理解等。​AboutTeachingPlan 实践：1) 搜索技术和策略2) 不确定推理技术3) 专家系统：动物识别系统4) 模式识别技术5) 调研： 搜索技术和策略、不确定推理技术、统计模式识别、机器学习等四个领域进展报告。​ChapterOne:BriefIntroductiontoArtificialIntelligence1.WhatisAI?人工智能（ArtificialIntelligence,AI）是当前科学技发展的一门前沿学科，同时也是一门新思想，新观念，新理论，新技术不断出现的新兴学科以及正在发展的学科。它是在计算机科学，控制论，信息论，神经心理学，哲学，语言学等多种学科研究的基础发展起来的，因此又可把它看作是一门综合性的边缘学科。它的出现及所取得的成就引起了人们的高度重视,并取得了很高的评价。有的人把它与空间技术，原子能技术一起并誉为20世纪的三大科学技术成就。​Intelligence智能是知识与智力的总合。 知识——智能行为的基础； 智力——获取知识并运用知识求解问题的能力。智能具有以下特征：(1)具有感知能力——指人们通过视觉、听觉、触觉、味觉、嗅觉等感觉器官感知外部世界的能力；(2)具有记忆与思维的能力——这是人脑最重要的功能，亦是人之所以有智能的根本原因；(3)具有学习能力及自适应能力；(4)具有行为能力。ArtificialIntelligence人工智能——计算机科学的一个分支，是智能计算机系统，即人类智慧在机器上的模拟，或者说是人们使机器具有类似于人的智慧（对语言能理解、能学习、能推理）。​2.BriefHistoryofAI (1) 孕育（1956年前）古希腊的Aristotle（亚里士多德）（前384-322），给出了形式逻辑的基本规律。英国的哲学家、自然科学家Bacon（培根）（1561-1626），系统地给出了归纳法。“知识就是力量”德国数学家、哲学家Leibnitz（布莱尼茨）（1646-1716）。提出了关于数理逻辑的思想，把形式逻辑符号化，从而能对人的思维进行运算和推理。做出了能做四则运算的手摇计算机英国数学家、逻辑学家Boole（布尔）（1815-1864）实现了布莱尼茨的思维符号化和数学化的思想，提出了一种崭新的代数系统——布尔代数。​美籍奥地利数理逻辑学家Godel（哥德尔）（1906-1978），证明了一阶谓词的完备性定；任何包含初等数论的形式系统，如果它是无矛盾的，那么一定是不完备的。意义在于，人的思维形式化和机械化的某种极限，在理论上证明了有些事是做不到的。英国数学家Turing(图灵)（1912-1954）,1936年提出了一种理想计算机的数学模型（图灵机），1950年提出了图灵试验，发表了“计算机与智能”的论文。图灵奖。美国数学家Mauchly，1946发明了电子数字计算机ENIAC美国神经生理学家McCulloch，建立了第一个神经网络数学模型。美国数学家Shannon（香农）,1948年发表了《通讯的数学理论》，代表了“信息论”的诞生。​ (2) 形成（1956-1969）1956年提出了“ArtificialIntelligence（人工智能）”1956年夏由麻省理工学院的J.McCarthy、M.L.Minsky,IBM公司信息研究中心的N.Rochester,贝尔实验室的C.E.Shannon共同发起，邀请了Moore,Samuel,Selfridge,Solomonff,Simon,Newell等人，10位数学家、信息学家、心理学家、神经生理学家、计算机科学家，在Dartmouth大学召开了一次关于机器智能的研讨会，会上McCarthy提议正式采用了ArtificialIntelligence（人工智能）这一术语。这次会议，标志着人工智能作为一门新兴学科正式诞生了。 McCarthy（麦卡锡）——人工智能之父。这次会议之后的10年间，人工智能的研究取得了许多引人瞩目的成就.机器学习方面：塞缪尔于1956年研制出了跳棋程序，该程序能从棋谱中学习，也能从下棋实践中提高棋艺；​在定理证明方面：王浩于1958年在IBM机上证明了《数学原理》中有关命题演算的全部定理（220条），还证明了谓词演算中150条定理85%；1965年，鲁宾逊（Robinson）提出了消解原理；在模式识别方面：1959年塞尔夫里奇推出了一个模式识别程序；1965年罗伯特（Robert）编制出可辨别积木构造的程序；在问题求解方面：1960年纽厄尔等人通过心理学试验总结出了人们求解问题的思维规律，编制了通用问题求解程序GPS,可以用来求解11种不同类型的问题；在专家系统方面：斯坦福大学的费根鲍姆（E.A.Feigenbaum）自1965年开始进行专家系统DENDRAL（化学分析专家系统），1968年完成并投入使用；在人工智能语言方面：1960年McCarthy等人建立了人工智能程序设计语言Lisp，该语言至今仍是建造智能系统的重要工具；1969年成立了国际人工智能联合会议（InternationalJointConferencesOnArtificialIntelligence）​ (3) 发展（1970年以后）70年代，开始从理论走向实践，解决一些实际问题。同时很快就发现问题：归结法费时、下棋赢不了全国冠军、机器翻译一团糟。以Feigenbaum为首的一批年轻科学家改变了战略思想，1977年提出知识工程的概念，以知识为基础的专家咨询系统开始广泛的应用。著名专家系统的有：DENDRAL化学分析专家系统（斯坦福大学1968）MACSYMA符号数学专家系统（麻省理工1971）MYCIN诊断和治疗细菌感染性血液病的专家咨询系统（斯坦福大学1973）CASNET(CausalASsciationalNetwork)诊断和治疗青光眼的专家咨询系统（拉特格尔斯（Rutgers）大学70年代中）CADUCEUS(原名INTERNIST)医疗咨询系统（匹兹堡大学）；HEARSAYI和II语音理解系统（卡内基-梅隆大学）PROSPECTOR地质勘探专家系统（斯坦福大学1976）XCON计算机配置专家系统（卡内基-梅隆大学1978）​•80年代，人工智能发展达到阶段性的顶峰。•87,89年世界大会有６－７千人参加。硬件公司有上千个。并进行Lisp硬件、Lisp机的研究。•在专家系统及其工具越来越商品化的过程中,国际软件市场上形成了一门旨在生产和加工知识的新产业——知识产业。应该说，知识工程和专家系统是近十余年来人工智能研究中最有成就的分支之一。•同年代，1986年Rumlhart领导的并行分布处理研究小组提出了神经元网络的反向传播学习算法，解决了神经网络的根本问题之一。从此，神经网络的研究进入新的高潮。•90年代，计算机发展趋势为小型化、并行化、网络化、智能化。•人工智能技术逐渐与数据库、多媒体等主流技术相结合，并融合在主流技术之中，旨在使计算机更聪明、更有效、与人更接近。•日本政府于1992年结束了为期十年的称为“知识信息处理体统”的第五代计算机系统研究开发计划。并开始了为期十年的实况计算（RealWordComputing）计划。​3.ResearchObjectsandMainContents

(1)人工智能的研究目标

人工智能的长期研究目标：构造智能计算机。

人工智能的近期研究目标：使现有的电子计算机更聪明，更有用，使它不仅能做一般的数值计算及非数值信息的数据处理，而且能运用知识处理问题，能模拟人类的部分智能行为。​(2)人工智能研究的基本内容

1.机器感知以机器视觉与机器听觉为主。机器感知是机器获取外部信息的基本途径，是使机器具有智能不可或缺的组成部分，对此人工智能中已形成两个专门的研究领域——

模式识别和自然语言理解。2.机器思维指通过感知的外部信息及机器内部的各种工作信息进行有目的的处理。主要开展以下几方面的研究：(1)知识表示(2)知识的组织，累计，管理技术(3)知识的推理(4)各种启发式搜索及控制策略(5)神经网络，人脑的结构及其工作原理​3.机器学习

使计算能自动获取知识，能直接向书本学习，能通过与人谈话学习，能通过对环境的观察学习，并能在实践中自我完善。4.机器行为机器行为主要指计算机的表达能力，即“说”、“写”、“画”等，对智能机器人，还应该有人的四肢功能，即能走路，能取物，能操作等。5.智能系统及智能计算机的构造技术​4.ResearchObjectsandMainContents人工智能面世以来，其研究途径存在两种不同的观点：以符号处理为核心的方法——主张通过运用计算机科学的方法进行研究，实现人工智能在计算机的模拟。以网络连接为主的连接机制方法——主张用生物学的方法进行研究，搞清楚人类智能的本质。(1)以符号处理为核心的方法该方法起源于纽厄尔等人的通用问题求解系统（GPS），用于模拟人类求解问题的心理过程，逐