人工智能遗传算法三

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,计算智能,计算智能是信息科学和生命科学相互交叉的前沿领域,是现代科学技术发展的一个重要体现。,计算智能涉及神经网络、模糊逻辑、进化计算和人工生命等领域，它的研究和发展反映了当代科学技术多学科交叉与集成的重要发展趋势。,贝兹德克于,1994,年提出了一种,A,，,B,，,C,智能模型，从而表示,ABC,与神经网络、模式识别和智能之间的关系：,A,：,Artificial,表示人工的、符号的（非生物的）,B,：,Biological ,表示生物的,C,：,Computational,表示计算的,计算智能是一种智力方式的底层认知，它与人工智能的区别是认知层次从中层下降到底层而已。中层系统含有知识，底层系统没有知识。,关于,A,，,B,，,C,智能,计算智能与人工智能的区别与联系,NN,Neural Network,神经网络,PR,Pattern Recognition,模式识别,计算智能系统与人工智能系统,当一个系统只涉及数值（底层）数据，含有模式识别部分，不应用于人工智能意义上的知识，而且系统能够呈现出：,（,1,）计算适应性,（,2,）计算容错性,（,3,）接近人的计算速度,（,4,）计算误差率与人接近,则该系统就是计算智能系统。,当一个智能计算系统以非数值方式并加上知识，即为人工智能系统。,神经计算（,Neural Computation,）,神经计算研究的进展,1943,年麦卡洛奇和皮茨提出神经网络模型的概念（称为,MP,模型）,20,世纪,60,年代威德罗和霍夫提出了自适应线性元件。,60,年代末到,80,年代初初与研究的低潮期,80,年代后又大发展,遗传算法,遗传算法简称,GA,（,Genetic Algorithms,）是,1975,年由美国,Michigan(,密歇根州,),大学的,J.,Holland,教授提出的模拟自然界生物遗传学（孟德尔）和生物进化论（达尔文）通过人工方式所构造的一类并行随机搜索最优化方法，是对生物进化过程进行的一种数学仿真，是进化计算的重要形式。,1,、遗传算法,在生物系统中，进化被认为是一种成功的自适应方法，具有很好的健壮性,。,其主要特点是,(1),直接对结构对象进行操作，不存在求导和函数连续性的限定；,(2),具有内在的隐含并行性和更好的全局寻优能力；,(3),采用概率化的寻优方法，能自动获取和指导优化的搜索空间，,自适应地调整搜索方向，不需要确定的规则。,遗传算法已被广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。它是现代有关计算智能中的关键技术之一。,遗传算法是以达尔文的自然选择学说为基础发展起来的。自然选择学说包括以下三个方面：,1,、遗传算法,（,1,）遗传,：,：这是,生,生物的,普,普遍特,征,征，亲,代,代把生,物,物信息,交,交给子,代,代，子,代,代总是,和,和亲代,具,具有相,同,同或相,似,似的性,状,状。生,物,物有了,这,这个特,征,征，物,种,种才能,稳,稳定存,在,在。,（,2,）变异,：,：亲代,和,和子代,之,之间以,及,及子代,的,的不同,个,个体之,间,间的差,异,异，称,为,为变异,。,。变异,是,是随机,发,发生的,，,，变异,的,的选择,和,和积累,是,是生命,多,多样性,的,的根源,。,。,（,3,）生存,斗,斗争和,适,适者生,存,存：具,有,有适应,性,性变异,的,的个体,被,被保留,下,下来，,不,不具有,适,适应性,变,变异的,个,个体被,淘,淘汰，,通,通过一,代,代代的,生,生存环,境,境的选,择,择作用,，,，性状,逐,逐渐逐,渐,渐与祖,先,先有所,不,不同，,演,演变为,新,新的物,种,种。,遗传算,法,法将“,优,优胜劣,汰,汰，适,者,者生存,”,”的生,物,物进化,原,原理引,入,入优化,参,参数形,成,成的编,码,码串群,体,体中，,按,按所选,择,择的适,应,应度函,数,数并通,过,过遗传,中,中的复,制,制、交,叉,叉及变,异,异对个,体,体进行,筛,筛选，,适,适应度,高,高的个,体,体被保,留,留下来,，,，组成,新,新的群,体,体，新,的,的群体,既,既继承,了,了上一,代,代的信,息,息，又,优,优于上,一,一代。,这,这样周,而,而复始,，,，群体,中,中个体,适,适应度,不,不断提,高,高，直,到,到满足,一,一定的,条,条件。,遗,遗传算,法,法的算,法,法简单,，,，可并,行,行处理,，,，并能,到,到全局,最,最优解,。,。,如：爱,斯,斯基摩,人,人，,非洲原,始,始部落,2,、遗传,算,算法的,基,基本操,作,作为：,（,1,）复制,（,（,ReproductionOperator,）,复制是,从,从一个,旧,旧种群,中,中选择,生,生命力,强,强的个,体,体位串,产,产生新,种,种群的,过,过程。,具,具有高适应,度,度的位串,更,更有可,能,能在下,一,一代中,产,产生一,个,个或多,个,个子孙,。,。,复制操,作,作可以,通,通过随,机,机方法,来,来实现,。,。首先,产,产生,01,之间均,匀,匀分布,的,的随机,数,数，若,某,某串的,复,复制概,率,率为,40%,，则当,产,产生的,随,随机数,在,在,0.401.0,之间时,，,，该串,被,被复制,，,，否则,被,被淘汰,。,。,（,2,）交叉,（,（,CrossoverOperator,）,复制操,作,作能从,旧,旧种群,中,中选择,出,出优秀,者,者，但,不,不能创,造,造新的,染,染色体,。,。而交,叉,叉模拟,了,了生物,进,进化过,程,程中的,繁,繁殖现,象,象，通,过,过两个,染,染色体,的,的交换,组,组合，,来,来产生,新,新的优,良,良品种,。,。,交叉的,过,过程为,：,：在匹,配,配池中,任,任选两,个,个染色,体,体，随,机,机选择,一,一点或,多,多点交,换,换点位,置,置；交,换,换双亲,染,染色体,交,交换点,右,右边的,部,部分，,即,即可得,到,到两个,新,新的染,色,色体数,字,字串。,交叉体,现,现了自,然,然界中,信,信息交,换,换的思,想,想。交,叉,叉有单,点,点交叉,、,、两点,交,交叉、,还,还有一,致,致交叉,、,、顺序,交,交叉和,周,周期交,叉,叉。单,点,点交叉,是,是最基,本,本的方,法,法，应,用,用较广,。,。它是,指,指染色,体,体切断,点,点有一,处,处，例,：,：,（,3,）变异,(MutationOperator),变异运,算,算用来,模,模拟生,物,物在自,然,然的遗,传,传环境,中,中由于,各,各种偶,然,然因素,引,引起的,基,基因突,变,变，它,以,以很小,的,的概率,随,随机地,改,改变遗,传,传基因,（,（表示,染,染色体,的,的符号,串,串的某,一,一位）,的,的值。,在,在染色,体,体以二,进,进制编,码,码的系,统,统中，,它,它随机,地,地将染,色,色体的,某,某一个,基,基因由,1,变为,0,，或由,0,变为,1,。,若只有,选,选择和,交,交叉，,而,而没有,变,变异，,则,则无法,在,在初始,基,基因组,合,合以外,的,的空间,进,进行搜,索,索，使,进,进化过,程,程在早,期,期就陷,入,入局部,解,解而进,入,入终止,过,过程，,从,从而影,响,响解的,质,质量。,为,为了在,尽,尽可能,大,大的空,间,间中获,得,得质量,较,较高的,优,优化解,，,，必须,采,采用变,异,异操作,。,。,17,设自变,量,量,x,介于0,31,，,，求其,二,二次函,数,数的最,大,大值，,即,即：,maxf(x)= x,2,x0,31,3,、遗传,算,算法示,例,例,-f(x) =x,2,极大值,问,问题,500,1000,0,31,x,f (x),当然，,利,利用简,单,单的代,数,数运算,，,，很容,易,易求出,该,该问题,的,的解。,现,现在改,用,用遗传,算,算法求,解,解，遗,传,传算法,通,通常包,括,括下述,内,内容：,18,（,1）编,码,码,遗传算,法,法首先,要,要对实,际,际问题,进,进行编,码,码，用,字,字符串,表,表达问,题,题。这,种,种字符,串,串相当,于,于遗传,学,学中的,染,染色体,。,。每一,代,代所产,生,生的字,符,符串个体总,和,和称为,群,群体。为了,实,实现的,方,方便，,通,通常字,符,符串长,度,度固定,，,，字符,选,选0或1。,本例中,，,，利用5位二,进,进制数,表,表示,x,值，采,用,用随机,产,产生的,方,方法，,假,假设得,出,出拥有,四,四个个,体,体的初,始,始群体,，,，即：01101，11000，01000，10011。,x,值相应,为,为13,，,，24,，,，8，19。,个体编号,初始群体,x,i,适应度,f(x,i,),f(x,i,)/f(x,i,),f(x,i,)/f,M,p,1,2,3,4,01101,11000,01000,10011,13,24,8,19,169,576,64,361,0.14,0.49,0.06,0.31,0.58,1.97,0.22,1.23,1,2,0,1,总计,f(x,i,),平均值,f,最大值,最小值,1170,293,576,64,1.00,0.25,0.49,0.06,4.00,1.00,1.97,0.22,4,1,2,0,19,（2）,计,计算适,应,应度,衡量字,符,符串（,染,染色体,）,）好坏,的,的指标,是,是适应度，它也,就,就是遗,传,传算法,的,的目标,函,函数。,本例中,适,适应度,比,比较简,单,单，用,x,2,计算。,表中还,列,列出了,当,当前适,应,应度的,总,总和,f(x,i,),及平均,值,值,f,，即：,f(x,i,) =f(x,1,) +f(x,2,) +f(x,3,) +f(x,4,) =1170,f =,f(x,i,) /4 =292.5(293),f(x,1,)/f,=169/293=0.57679.,个体编号,初始群体,x,i,适应度,f(x,i,),f(x,i,)/f(x,i,),f(x,i,)/f,M,p,1,2,3,4,01101,11000,01000,10011,13,24,8,19,169,576,64,361,0.14,0.49,0.06,0.31,0.58,1.97,0.22,1.23,1,2,0,1,总计,f(x,i,),平均值,f,最大值,最小值,1170,293,576,64,1.00,0.25,0.49,0.06,4.00,1.00,1.97,0.22,4,1,2,0,20,（2）,计,计算适,应,应度,表中第6列的,f(x,i,)/f,表示每,个,个个体,的,的相对适,应,应度，它反,映,映了个,体,体之间,的,的相对,优,优劣性,。,。如2,号,号个体,的,的,f(x,i,)/f,值最高,（,（1.97）,，,，为优,良,良个体,，,，3号,个,个体最,低,低（0.22,）,），为,不,不良个,体,体。,个体编号,初始群体,x,i,适应度,f(x,i,),f(x,i,)/f(x,i,),f(x,i,)/f,M,p,1,2,3,4,5,6,7,1,2,3,4,01101,11000,01000,10011,13,24,8,19,169,576,64,361,0.14,0.49,0.06,0.31,0.58,1.97,0.22,1.23,1,2,0,1,总计,f(x,i,),平均值,f,最大值,最小值,1170,293,576,64,1.00,0.25,0.49,0.06,4.00,1.00,1.97,0.22,4,1,2,0,21,（3）,复,复制,为了将,已,已有的,群,群体变,为,为下一,代,代群体,，,，遗传,算,算法仿,效,效进化,论,论中“,自,自然选,择,择、适,者,者生存,”,”的原,则,则，从,旧,旧群体,中,中选择,优,优良个,体,体进行,复,复制。,选,选择的,依,依据是,个,个体适,应,应度的,大,大小，,适,适应度,大,大的个,体,体接受,复,复制，,使,使之繁,殖,殖；适,应,应度小,的,的个体,则,则删除,掉,掉，遭,到,到淘汰,。,。,22,（3）,复,复制,在本例,中,中，根,据,据相对,适,适应度,的,的大小,对,对个体,进,进行取,舍,舍，2,号,号个体,性,性能最,优,优，予,以,以复制,繁,繁殖。3号个,体,体性能,最,最差，,将,将它删,除,除，使,之,之死亡,，,，表中,的,的,M,表示传,递,递给下,一,一代的,个,个体数,目,目，其,中,中2号,个,个体占2个，3号个,体,体为0,，,，1号,、,、4号,个,个体保,持,持为1,个,个。,这样，,就,就产生,了,了下一,代,代群体,。,。,个体编号,初始群体,x,i,适应度,f(x,i,),f(x,i,)/f(x,i,),f(x,i,)/f,M,p,1,2,3,4,01101,11000,01000,10011,13,24,8,19,169,576,64,361,0.14,0.49,0.06,0.31,0.58,1.97,0.22,1.23,1,2,0,1,总计,f(x,i,),平均值,f,最大值,最小值,1170,293,576,64,1.00,0.25,0.49,0.06,4.00,1.00,1.97,0.22,4,1,2,0,23,（3）,复,复制,从表中,的,的第4,列,列可以,看,看出，,复,复制后,产,产生的,新,新一代,群,群体的,平,平均适,应,应度明,显,显增加,，,，由原,来,来的293增,加,加到421。,造,造成平,均,均适应,度,度增加,的,的原因,有,有二：,1）淘,汰,汰原来,最,最差的,个,个体。,使,使最小,适,适应度,由,由原来,的,的64,增,增加到169,。,。,2）增,加,加了优,良,良个体,（,（2号,）,）的个,数,数，使,适,适应度,累,累计值,增,增加。,个体,编号,复制后群体,x,i,复制后,适应度,f(x,i,),交换对象,交换位置,交换后群体,复制后,适应度,f(x,i,),1,2,3,4,（,1,）,01101,（,2,）,11000,（,2,）,11000,（,4,）,10011,13,24,24,19,169,576,576,361,2,号,1,号,4,号,3,号,4,4,3,3,01100,110,01,110,11,10000,144,625,729,256,总计,平均值,最大值,最小值,1682,421,576,361,1754,439,729,256,24,（4）,交,交换,通过复,制,制产生,的,的新群,体,体，其,性,性能得,到,到改善,，,，然而,它,它不能,产,产生新,的,的个体,。,。为了,产,产生新,的,的个体,，,，遗传,算,算法仿,照,照生物,学,学中杂,交,交的方,法,法，对,染,染色体,（,（字符,串,串）的,某,某些部,分,分进行,交,交叉换,位,位。被,交,交换的,母,母体都,选,选自经,过,过复制,产,产生的,新,新一代,个,个体（,优,优胜者,）,）。,25,（4）,交,交换,本例中,，,，利用,随,随机配,对,对的方,法,法，决,定,定1号,和,和2号,个,个体、3号和4号个,体,体分别,交,交换，,如,如表中,第,第5列,。,。再利,用,用随机,定,定位的,方,方法，,确,确定这,两,两对母,体,体交叉,换,换位的,位,位置分,别,别从字,符,符长度,的,的第4,位,位及第3位开,始,始。如,：,：3号,、,、4号,个,个体从,字,字符长,度,度第3,位,位开始,交,交换。,交,交换开,始,始的位,置,置称交换点。,个体,编号,复制后群体,x,i,复制后,适应度,f(x,i,),交换对象,交换位置,交换后群体,复制后,适应度,f(x,i,),1,2,3,4,01101,11000,11000,10011,13,24,24,19,169,576,576,361,2,号,1,号,4,号,3,号,4,4,3,3,01100,11001,11011,10000,144,625,729,256,总计,平均值,最大值,最小值,1682,421,576,361,1754,439,729,256,11,0,00,10,0,11,11,0,11,10,0,00,26,（4）,交,交换,从表中,可,可以看,出,出，交,换,换后出,现,现优异,个,个体3,号,号，其,适,适应度,高,高达729，,大,大大高,于,于交换,前,前的最,大,大值（576,）,）。与,此,此同时,，,，平均,适,适应度,也,也从原,来,来的421提,高,高到439，,说,说明交,换,换后的,群,群体正,朝,朝优良,方,方向发,展,展。,个体,编号,复制后群体,x,i,复制后,适应度,f(x,i,),交换对象,交换位置,交换后群体,复制后,适应度,f(x,i,),1,2,3,4,01101,11000,11000,10011,13,24,24,19,169,576,576,361,2,号,1,号,4,号,3,号,4,4,3,3,01100,11001,11011,10000,144,625,729,256,总计,平均值,最大值,最小值,1682,421,576,361,1754,439,729,256,27,（5）,突,突变,遗传算,法,法模仿,生,生物学,中,中基因,突,突变的,方,方法，,将,将个体,字,字符串,某,某位符,号,号进行,逆,逆变，,即,即由1,变,变为0,或,或由0,变,变为1,。,。例如,，,，下式,左,左侧的,个,个体于,第,第3位,突,突变，,得,得到新,个,个体如,右,右侧所,示,示。,上述（2）,（,（5）,反,反复执,行,行，直,至,至得出,满,满意的,最,最优解,。,。,由上可,知,知，遗,传,传算法,参,参考生,物,物中有,关,关进化,与,与遗传,的,的过程,，,，利用,复,复制、,交,交换、,突,突变等,操,操作，,不,不断循,环,环执行,，,，逐渐逼,近,近全局,最,最优解。,遗传算,法,法中，,个,个体是,否,否进行,突,突变以,及,及在哪,个,个部位,突,突变，,都,都由事,先,先给定,的,的概率,决,决定。,通,通常，,突,突变概,率,率很小,，,，约为0.008，,本,本例的,第,第一代,中,中就没,有,有发生,突,突变。,10,0,00,10,1,00,28,从数学,角,角度看,，,，遗传,算,算法实,质,质上是,一,一种搜,索,索寻优,技,技术。,它,它从某,一,一初始,群,群体出,发,发，遵,照,照一定,的,的操作,规,规则，,不,不断迭,代,代计算,，,，逐步,逼,逼近最,优,优解。,这,这种搜,索,索技术,，,，有如,下,下特点,：,：,4,、遗传算,法,法的基,本,本特征,从上述,简,简单例,子,子可以,看,看出，,遗,遗传算,法,法仿照,生,生物进,化,化和遗,传,传的规,律,律，利,用,用复制,、,、交换,、,、突变,等,等操作,，,，使优,胜,胜者繁,殖,殖，劣,败,败者消,失,失，一,代,代一代,地,地重复,同,同样的,操,操作，,最,最终找,出,出最优,解,解。,29,（1）,智,智能式,搜,搜索,遗传算,法,法的搜,索,索策略,，,，既不,是,是盲目,式,式的乱搜索，也不,是,是穷举式的全面,搜,搜索，,它,它是有,指,指导的,搜,搜索。,指,指导遗,传,传算法,执,执行搜,索,索的依,据,据是适应度，也就,是,是它的,目,目标函,数,数。利,用,用适应,度,度，使,遗,遗传算,法,法逐步,逼,逼近目,标,标值。,（2）,渐,渐进式,优,优化,遗传算,法,法利用,复,复制、,交,交换、,突,突变等,操,操作，,使,使新一,代,代的结,果,果优越,于,于旧一,代,代，通,过,过不断,迭,迭代，,逐,逐渐得,出,出最优,的,的结果,，,，它是,一,一种反,复,复迭代,的,的过程,。,。,4,、遗传算,法,法的基,本,本特征,30,（3）,全,全局最,优,优解,遗传算,法,法由于,采,采用交,换,换、突,变,变等操,作,作，产,生,生新的,个,个体，,扩,扩大了,搜,搜索范,围,围，使,得,得搜索,得,得到的,优,优化结,果,果是全,局,局最优,解,解而不,是,是局部,最,最优解,。,。,（4）,黑,黑箱式,结,结构,遗传算,法,法根据,所,所解决,问,问题的,特,特性，,进,进行编,码,码和选,择,择适应,度,度。一,旦,旦完成,字,字符串,和,和适应,度,度的表,达,达，其,余,余的复,制,制、交,换,换、突,变,变等操,作,作都可,按,按常规,手,手续执,行,行。个,体,体的编,码,码如同,输,输入，,适,适应度,如,如同输,出,出。因,此,此遗传,算,算法从,某,某种意,义,义上讲,是,是一种,只,只考虑,输,输入与,输,输出关,系,系的黑,箱,箱问题,。,。,4,、遗传算,法,法的基,本,本特征,31,（5）,通,通用性,强,强,传统的,优,优化算,法,法，需,要,要将所,解,解决的,问,问题用数学式,子,子表示，,常,常常要,求,求解该,数,数学函,数,数的一,阶,阶导数,或,或二阶,导,导数。,采,采用遗,传,传算法,，,，只用,编,编码及,适,适应度,表,表示问,题,题，并,不,不要求,明,明确的,数,数学方,程,程及导,数,数表达,式,式。因,此,此，遗,传,传算法,通,通用性,强,强，可,应,应用于,离,离散问,题,题及函,数,数关系,不,不明确,的,的复杂,问,问题，,有,有人称,遗,遗传算,法,法是一,种,种框架型,算,算法，它只,有,有一些,简,简单的,原,原则要,求,求，在,实,实施过,程,程中可,以,以赋予,更,更多的,含,含义。,（6）,并,并行式,算,算法,遗传算,法,法是从,初,初始群,体,体出发,，,，经过,复,复制、,交,交换、,突,突变等,操,操作，,产,产生一,组,组新的,群,群体。,每,每次迭,代,代计算,，,，都是,针,针对一,组,组个体,同,同时进,行,行，而,不,不是针,对,对某个,个,个体进,行,行。因,此,此，尽,管,管遗传,算,算法是,一,一种搜,索,索算法,，,，但是,由,由于采,用,用这种,并,并行机,理,理，搜,索,索速度,很,很高。,这,这种并,行,行式计,算,算是遗,传,传算法,的,的一个,重,重要特,征,征。,4,、遗传算,法,法的基,本,本特征,32,遗传算,法,法受生,物,物进化,与,与遗传,的,的启发,，,，形成,一,一种独,特,特的优,化,化方式,，,，因此,，,，遗传,算,算法的,运,运算原,则,则常常,与,与生物,进,进化及,遗,遗传学,说,说吻合,，,，而且,其,其术语,也,也常常,仿,仿效生,物,物学的,术,术语。,遗传算,法,法的运,算,算基础,是,是字符,串,串，它,就,就相当,于,于生物,学,学中的,染,染色体,。,。,字符串,由,由一系,列,列字符,组,组成，,每,每个字,符,符都有,特,特定的,含,含义，,反,反应所,解,解决问,题,题的某,个,个特征,，,，这就,相,相当于,基,基因，,即,即染色,体,体,DNA,的片段,。,。,在进行,交,交换、,突,突变操,作,作时，,遗,遗传算,法,法只涉,及,及到字,符,符串某,些,些片段,，,，这就,类,类似于,遗,遗传过,程,程只涉,及,及某些,基,基因而,不,不是整,个,个染色,体,体。,5,、遗传算,法,法的生,物,物学含,义,义,33,遗传学,很,很注重等位基,因,因，它是,反,反映生,物,物某一,形,形态所,对,对应的,基,基因。,在,在遗传,算,算法的,字,字符串,中,中，每,个,个字符,都,都反映,问,问题的,某,某一特,性,性，这,也,也就相,当,当于等,位,位基因,，,，至于,等,等位基,因,因的位,置,置，也,就,就相当,于,于该字,符,符在字,符,符串中,的,的位置,。,。,在遗传,学,学中，,杂,杂交产,生,生的子,代,代里显,现,现出亲,本,本的性,状,状，称,作,作显性,性,性状，,未,未显现,出,出来的,亲,亲本性,状,状叫作,隐,隐性性,状,状。控,制,制显性,性,性状的,基,基因是显性基,因,因，用大,写,写英文,字,字母表,示,示。控,制,制隐性,性,性状的,基,基因是隐性基,因,因，用小,写,写英文,字,字母表,示,示。在,遗,遗传算,法,法中，,模,模仿这,种,种大、,小,小字母,表,表达方,式,式，对,显,显性基,因,因和隐,性,性基因,采,采取不,同,同的操,作,作。,5,、遗传算,法,法的生,物,物学含,义,义,34,生物学,术,术语在,遗,遗传算,法,法中的,对,对应意,义,义如下,表,表。,序号,生物学,遗传算法,1,2,3,4,5,6,染色体（,Chromosome）,基因（,Gene）,等位基因（,Allele）,基因位置（,Locus）,基因型（,Genotype）,表现型（,Phenotype）,字符串,字符,对应的字符,字符的位置,字符串结构,字符串含义,5,、遗传算,法,法的生,物,物学含,义,义,35,根据前,面,面所讲,的,的示例,，,，可以,看,看出遗,传,传算法,的,的实施,过,过程中,包,包括编,码,码、产,生,生群体,、,、计算,适,适应度,、,、复制,、,、交换,、,、突变,等,等操作,。,。,遗传算,法,法的详,细,细流程,如,如下图,。,。,6,、遗传算,法,法的工,作,作步骤,36,Gen,：遗传,（,（迭代,）,）的代,次,次。表,明,明遗传,算,算法反,复,复执行,的,的次数,，,，即已,产,产生群,体,体的代,次,次数目,。,。,M,：群体,中,中拥有,的,的个体,数,数目。,i,：已处理,个,个体的累,计,计数，当,i,等于,M,，表明这,一,一代的个,体,体已全部,处,处理完毕,，,，需要转,入,入下一代,群,群体。,交叉率Pc就是参加,交,交叉运算,的,的染色体,个,个数占全,体,体染色体,总,总数的比,例,例，记为,P,c,取值,范,范围一般,为,为0.4,0.99。,变异率Pm是指发生,变,变异的基,因,因位数所,占,占全体染,色,色体的基,因,因总位数,的,的比例，,记,记为Pm,，,，取值范,围,围一般为0.00010.1。,复制概率,Pt,用于控制,复,复制与淘,汰,汰的个体,数,数目。,P,c,P,t,P,m,No,No,Yes,Gen,：,=0,随机产生初始群体,满足终止条件,计算群体中各个体的适应度,i,：,=0,i,：,=M?,选择遗传算子及概率,根据适应度选择两个个体,i,：,=i+1,执行交换,将两个交换结果添入新群体,i,：,=i+1,将复制结果添入新群体,执行复制,根据适应度选择一个个体,将突变结果添入新群体,执行突变,Gen,：,=Gen+1,输出结果,结束,Yes,37,概括地讲,，,，遗传算,法,法主要执,行,行以下四,步,步：,（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 =2,L,种情况。,如,如果所描,述,述性质的,最,最小值不,是,是0时，,即,即性质介,于,于,U,min,U,max,之间，为,了,了减小字,符,符串长度,，,，可以采,用,用映射的,方,方法，用2,L,个二进制,数,数表示,U,min,，,U,max,。这时,，,，令,L,个0表示,U,min,，,L,个1 表,示,示,U,max,，其中,L,大小取决,于,于（,U,max, U,min,），其余,的,的数则用,线,线性插值,决,决定。例,如,如，对于 16,，,，31的十进,制,制数，我,们,们可以用4位二进,制,制0/1,字,字符在0000，1111 ,范,范围内表,示,示。,（,1,）编码,U,min,00,U,max,11,40,对于兼有,多,多种性质,的,的问题，,可,可以采用,长,长字符串,顺,顺序分别,表,表示。例,如,如，可选25位0/1字符,串,串表示物,体,体的体积,、,、重量及,颜,颜色，其,中,中前10,位,位数表示,体,体积量，,中,中间10,位,位数表示,重,重量，后5位数表,示,示颜色。,在遗传算,法,法中，字,符,符串的长,度,度常常是,固,固定的，,以,以便按统,一,一的方式,执,执行操作,。,。个别研,究,究者采用,不,不等长的,字,字符串，,这,这时就需,要,要跟踪记,录,录，经常,调,调整操作,方,方式，比,较,较烦琐。,从生物学,角,角度看，,编,编码就相,当,当于选择,遗,遗传物质,，,，它是研,究,究遗传的,基,基础。同,样,样，在遗,传,传算法中,编,编码也是,一,一项基础,性,性工作。,（,1,）编码,41,在遗传算,法,法中，衡,量,量个体优,劣,劣的尺度,是,是适应度。根据适,应,应度的大,小,小，决定,某,某些个体,是,是繁殖或,是,是消亡。,因,因此，适,应,应度是驱,动,动遗传算,法,法的动力,。,。从生物,学,学角度讲,，,，适应度,相,相当于“,生,生存竞争,，,，适者生,存,存”的生,物,物生存能,力,力，在遗,传,传过程中,具,具有重要,意,意义。,通常，适,应,应度是费用、赢,利,利、方差等目标的,表,表达式。,在,在运用过,程,程中可以,借,借鉴以下,经,经验。,（,2,）适应度,42,统一表达,形,形式,在实际问,题,题中，有,时,时希望适,应,应度越大,越,越好（如,赢,赢利、劳,动,动生产率,）,），有时,要,要求适应,度,度越小越,好,好（费用,、,、方差）,。,。为了使,遗,遗传算法,有,有通用性,，,，这种最,大,大、最小,值,值问题宜,统,统一表达,。,。通常都,统,统一按最,大,大值问题,处,处理，而,且,且不允许,适,适应度小,于,于0。,对于最小,值,值问题，,其,其适应度,按,按下式转,换,换：,f (x) =,C,max,- g (x),当,g(x)0,0,其他情况,f(x),： 变换,后,后的适应,度,度。,U(x),：最大值,问,问题下的,适,适应度。,C,min,：足够大,的,的常数。,（,2,）适应度,44,适应度缩,放,放,在执行遗,传,传算法的,初,初始阶段,，,，各个个,体,体的适应,度,度比较离,散,散，某些,个,个体的适,应,应度会很,高,高或很低,。,。对于个,别,别适应度,很,很高的个,体,体，会连,续,续多次被,复,复制；对,于,于适应度,很,很低的个,体,体，会过,早,早被舍弃,。,。这种不,正,正常的取,舍,舍，对于,个,个体数目,不,不多的群,体,体尤为严,重,重，会把,遗,遗传算法,的,的搜索引向,误,误区，过早地,收,收敛于局部最优,解,解。为了克,服,服这种缺,陷,陷，需要,采,采用适应,度,度缩放技,术,术，将适,应,应度按下,式,式变换：,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的,个,个体，所,以,以它入选,。,。,个体序号,1,2,3,4,5,6,7,8,9,10,适应度,8,2,17,7,2,12,11,7,3,7,适应度累计值,8,10,27,34,36,48,59,66,69,76,随机数,23,49,76,13,1,27,57,被选中的个体,3,7,10,3,1,3,7,轮盘选择,示,示例：,（,3,）复制,47,（1）依,次,次累计群,体,体内各个,体,体的适应,度,度，得相,应,应的累计,值,值,S,i,，最后一,个,个累计值,为,为,S,n,；,（2）在 0，,S,n,区间内产,生,生均匀分,布,布的随机,数,数,R,；,（3）依,次,次用,S,i,与,R,相比较，,第,第一个出,现,现,S,i,大于或等,于,于,R,的个体,i,被选为复,制,制对象；,（4）重,复,复（2）,、,、（3）,，,，直至满,足,足所需要,的,的个体数,目,目。,上述选择,过,过程，可,描,描述如下,：,：,（,3,）复制,48,因此，适,应,应度,f,i,越大，,S,i,的距离越,大,大，随机,数,数落在这,个,个区间的,可,可能性越,大,大，第,i,个个体被,选,选中的机,会,会也越多,。,。如下图,所,所示。,表面上看,，,，复制个,体,体的选择,是,是随机的,。,。但是，,选,选择时是,依,依据相邻,两,两个适应,度,度累计值,的,的差值,S,i,：,S,i,=,S,i,S,i-1,=,f,i,f,i,表示第,i,个个体的适,应,应度,（,3,）复制,49,轮盘（赌）,选,选择原理,S,2,S,1,S,3,S,4,S,i,S,n-1,S,n,图中的指针,固,固定不动，,外,外圈的圆环,可,可以任意转,动,动，圆环中,每,每段对应于,适,适应度的大,小,小。从统计,意,意义上讲，,适,适应度大的,个,个体被复制,的,的机会越大,。,。当然，适,应,应度小的个,体,体尽管被复,制,制的概率小,，,，但仍有可,能,能被“破格,”,”复制，这,样,样就增加个,体,体的多样性,，,，便于执行,交,交换及突变,。,。所以，轮,盘,盘选择方法,既,既体现“适,者,者生存”原,则,则，又保持,个,个体性态多,种,种多样。,（,3,）复制,50,选择复制个,体,体的随机方,法,法还有别的,形,形式，不过,轮,轮盘选择法,是,是最常用的,方,方法。,每代群体中,，,，被复制的,个,个体数目由,复,复制概率,P,t,控制，,P,t,常取0.1,0.2，,也,也就是说，,群,群体中有10%个体被,复,复制，相应,地,地有10%,个,个体被淘汰,，,，以保持群,体,体大小。,（,3,）复制,51,下表是个体,两,两两交换的,示,示例，字符,串,串内的下横,线,线代表交换,点,点的位置，,交,交换点及其,后,后面的字符,串,串两两互换,。,。,在遗传算法,中,中，交换是,产,产生新个体,的,的主要手段,。,。它仿照生,物,物学中杂交,的,的原理，将,两,两个个体（,染,染色体）的,部,部分字符（,基,基因）互相,交,交换。,序号,交换前,交换后,1,2,亲代,1,：,1 1 1 1,1,1,亲代,2,：,0 0 0 0,0,0,子代,1,：,1 1 1 1,0,0,子代,2,：,0 0 0 0,1,1,3,4,亲代,1,：,1 0 1,1,0 1,亲代,2,：,0 0 1,1,0 0,子代,1,：,1 0 1,1,0 0,子代,2,：,0 0 1,1,0 1,（,4,）交换,52,执行交换的,个,个体是随机,选,选择的。首,先,先，要确定,交,交换的概率,P,c,，大致为0.50.8左右。这,就,就是说，约50%80%的个体,要,要执行交换,。,。然后，采,用,用上述轮盘,选,选择的方法,，,，按适应度,大,大小选择被,交,交换的个体,，,，依次两两,进,进行交换。,交换点的选,择,择也是随机,的,的。假设字,符,符串长度为,L,，则在0，,L ,区间内产生,随,随机整数，,该,该整数便是,交,交换点的位,置,置。需要注,意,意的是，交,换,换点不能选,在,在第一个字,符,符上。因此,，,，长度为,L,的字符串，,可,可供选择的,交,交换点为（,L-1,）个。,根据交换点,数,数目的不同,，,，可分为一点交换和多点交换，前者只选,取,取一个交换,点,点，该点之,后,后的字符全,部,部参加交换,。,。后者选择,两,两个或多个,交,交换点，只,有,有两点间的,字,字符才参加,交,交换。当字,符,符串长度大,时,时，常采用,两,两点交换。,此,此外还有多点交换，即对长字,符,符串实行多,段,段交换。,（,4,）交换,53,通过交换，,子,子代的字符,串,串不同于亲,代,代。有时，,这,这种差别很,明,明显，如表,中,中的第一组,个,个体，被交,换,换部分完全,不,不一样。有,时,时，这种差,别,别却不大，,如,如表中的第,二,二组个体，,被,被交换的三,个,个字符中只,有,有最后一个,字,字符发生变,化,化。后一种,情,情况说明交,换,换后产生的,个,个体，其性,态,态变化不大,。,。尽管如此,，,，交换仍然,是,是遗传算法,产,产生新个体,的,的主要手段,。,。正是有了,交,交换操作，,群,群体的性态,才,才多种多样,。,。,序号,交换前,交换后,1,2,亲代,1,：,1 1 1 1,1,1,亲代,2,：,0 0 0 0,0,0,子代,1,：,1 1 1 1,0,0,子代,2,：,0 0 0 0,1,1,3,4,亲代,1,：,1 0 1,1,0 1,亲代,2,：,0 0 1,1,0 0,子代,1,：,1 0 1,1,0 0,子代,2,：,0 0 1,1,0 1,传统的优化,算,算法，例如,动,动态规划法,、,、个体性态,不,不能增添，,只,只能在原有,的,的个体群体,中,中择优，从,而,而限制了搜,索,索寻优的范,围,围。因此，,可,可以说，如,果,果没有交换,，,，遗传算法,就,就失去了其,优,优越性。,（,4,）交换,54,突变是遗传,算,算法中产生,新,新个体的另,一,一种方法，,它,它是将某一,个,个体的某一,位,位字符进行,补,补运算，使0变为1，,或,或使1变为0。,突变个体的,选,选择以及突,变,变位置的确,定,定，都是采,用,用随机的方,法,法产生。首,先,先，确定突,变,变概率,P,m,，,P,m,通常较小，,约,约为0.0010.01。也就,是,是说，1000个字符,中,中有110个发生突,变,变。然后，,针,针对每个字,符,符在 0,，,，1 之,间,间产生三位,有,有效数的均,匀,匀分布随机,数,数。若,P,m,= 0.008，凡是,随,随机数小于0.008,所,所对应的字,符,符，将实现,突,突变。示例,如,如下：,（,5,）突变,55,表中有三个,字,字符长度为4的旧个体,。,。对应每个,字,字符，依次,产,产生 0,，,，1 区,间,间均匀分布,的,的随机数12个。表中,只,只有2号个,体,体的第3个,字,字符以及3,号,号个体的第4个字符需,要,要发生突变,，,，因为它们,对,对应的随机,数,数小于0.008。,序号,旧个体,随机数,新字符,新个体,1,2,3,1010,1100,0010,0.801 0.102 0.266 0.373,0.120 0.096,0.005,0.840,0.760 0.473 0.894,0.001,1,1,1010,11,1,0,001,1,（,5,）突变,56,随机确定突,变,变的位置后,，,，执行突变,的,的方法有两,种,种。一种是,直,直接产生突,变,变，将表中,的,的2号和3,号,号旧个体分,别,别改写作1110及0011。,另一种方法,，,，按50%,的,的概率随机,产,产生新字符0或1。表,中,中2号个体,产,产生的新字,符,符为0，与,需,需要突变的,第,第三行字符,恰,恰好一样，,因,因此新个体,等,等同于旧个,体,体。表中3,号,号个体产生,的,的新字符（1）不同于,待,待突变的原,来,来字符（0,）,），因此新,个,个体不同于,旧,旧个体。很,明,明显，后一,种,种突变方法,的,的突变概率,仅,仅为前一种,方,方法的50%。通常建,议,议采用后一,种,种方法，增,加,加突变的随,机,机性。,序号,旧个体,随机数,新字符,新个体,1,2,3,1010,1100,0010,0.801 0.102 0.266 0.373,0.120 0.096 0.005 0.840,0.760 0.473 0.894 0.001,0,1,1010,1100,0011,（,5,）突变,57,还有一种执,行,行突变的方,法,法，是根据,给,给定的概率,P,m1,。随机选择,突,突变的个体,。,。当被突变,的,的个体选中,后,后，在字长,范,范围内用均,匀,匀分布的随,机,机数选择突,变,变的字符，,使,使该个体发,生,生突变。然,而,而，这时的,概,概率,P,m1,，不同于突,变,变概率,P,m,，后者是针,对,对字符而言,，,，前者是针,对,对个体。遗,传,传算法中讨,论,论的正是字,符,符的突变概,率,率,P,m,，两者间的,关,关系与字长,L,有关。,尽管突变和,交,交换都能产,生,生新个体，,但,但是在遗传,算,算法中，交,换,换的作用远,比,比突变重要,。,。,（,5,）突变,58,遗传算法是,一,一种反复迭,代,代的搜索方,法,法，它通过,多,多次进化逐,渐,渐逼近最优,解,解而不是恰,好,好等于最优,解,解，因此需,要,要确定终止,条,条件。,其一,最常用的终,止,止方法是规,定,定遗传（迭,代,代）的代次,。,。刚开始时,，,，迭代次数,小,小一些，如,规,规定100,次,次。然后视,情,情况逐渐增,加,加次数，可,达,达到上千次,。,。,（,6,）终止条件,59,当目标函数,是,是方差这一,类,类有最优目,标,标值的问题,时,时，可采用,控,控制偏差的,方,方法实现终,止,止。一旦遗,传,传算法得出,的,的目标函数,值,值（适应度,）,）与实际目,标,标值之差小,于,于允许值后,，,，算法终止,，,，即：,f(x),： 遗传算,法,法得出的目,标,标函数值。,f,*,：实际目标,值,值。,：足够小的,数,数。,| f(x) f,*,| ,（,6,）终止条件,60,第三种终止,方,方法是检查,适,适应度的变,化,化。在遗传,算,算法后期，,一,一旦最优个,体,体的适应度,没,没有变化或,变,变化很小时,，,，即令计算,终,终止。,遗传算法的,另,另一个重要,参,参数是每代,群,群体中的个,体,体数。很明,显,显，个体数,目,目越多，搜,索,索范围越广,，,，容易获取,全,全局最优解,。,。然而个体,数,数目太多，,每,每次迭代时,间,间也长。通,常,常，个体数,目,目可取100,-1000,之间。,（,6,）终止条件,7,遗传算法的,应,应用领域,（,1,）函数优化,。,。,函数优化是,遗,遗传算法的,经,经典应用领,域,域，也是遗,传,传算法进行,性,性能评价的,常,常用算例。,尤,尤其是对非,线,线性、多模,型,型、多目标,的,的函数优化,问,问题，采用,其,其他优化方,法,法较难求解,，,，而遗传算,法,法却可以得,到,到较好的结,果,果。,（,2,）组合优化,。,。,随着问题的,增,增大，组合,优,优化问题的,搜,搜索空间也,急,急剧扩大，,采,采用传统的,优,优化方法很,难,难得到最优,解,解。遗传算,法,法是寻求这,种,种满意解的,最,最佳工具。,例,例如，遗传,算,算法已经在,求,求解旅行商,问,问题、背包,问,问题、装箱,问,问题、图形,划,划分问题等,方,方面得到成,功,功的应用。,（,3,）生产调度,问,问题,在很多情况,下,下，采用建,立,立数学模型,的,的方法难以,对,对生产调度,问,问题进行精,确,确求解。在,现,现实生产中,多,多采用一些,经,经验进行调,度,度。遗传算,法,法是解决复,杂,杂调度问题,的,的有效工具,，,，在单件生,产,产车间调度,、,、流水线生,产,产车间调度,、,、生产规划,、,、任务分配,等,等方面遗传,算,算法都得到,了,了有效的应,用,用。,（,4,）自动控制,。,。,在自动控制,领,领域中有很,多,多与优化相,关,关的问题需,要,要求解，遗,传,传算法已经,在,在其中得到,了,了初步的应,用,用。例如，,利,利用遗传算,法,法进行控制,