第八章 遗传算法精选文档.ppt

1本讲稿第一页，共五十四页 GA的基本思想来源于Darwin的进化论和Mendel的遗传学说。Darwin的进化论认为每一物种在不断的发展过程中都是越来越适应环境。物种的每个个体的基本特征被后代所继承，但后代又不完全同于父代，这些新的变化，若适应环境，则被保留下来。在某一环境中也是那些更能适应环境的个体特征能被保留下来，这就是适者生存的原理。p遗传算法的由来遗传算法的由来2本讲稿第二页，共五十四页达尔文进化论达尔文进化论3本讲稿第三页，共五十四页同样的，人类也是一代比一代聪明，可以说人类近百年同样的，人类也是一代比一代聪明，可以说人类近百年创造的文明比人类前面几千年创造的文明还要多。创造的文明比人类前面几千年创造的文明还要多。4本讲稿第四页，共五十四页因此：我们得到的结论是：因此：我们得到的结论是：生物一代比一代优生物一代比一代优p生物虽然一代比一代优，但并不是说后一代与前一代没有任何的生物虽然一代比一代优，但并不是说后一代与前一代没有任何的关系，后一代或多或少总与前一代有些相同，也有一些不同。关系，后一代或多或少总与前一代有些相同，也有一些不同。p生物的后一代总是或多或少的继承了前一代的一些特性，这就生物的后一代总是或多或少的继承了前一代的一些特性，这就叫遗传。而后一代又不完全像前一代，这叫变异。叫遗传。而后一代又不完全像前一代，这叫变异。p生物在进化的过程中既有遗传，又有变异，生物就是在这样的遗生物在进化的过程中既有遗传，又有变异，生物就是在这样的遗传、变异的作用那个下，一代一代的繁衍下去，而且得到的是一代传、变异的作用那个下，一代一代的繁衍下去，而且得到的是一代比一代优。比一代优。5本讲稿第五页，共五十四页8.1 遗传算法的基本概念遗传算法的基本概念 1.1.个体与种群个体与种群 个体就是模拟生物个体而对问题中的对象 （一般就是问题的解）的一种称呼，一个个 体也就是搜索空间中的一个点。种群(population)就是模拟生物种群而由若 干个体组成的群体,它一般是整个搜索空间 的一个很小的子集。6本讲稿第六页，共五十四页 2.2.适应度与适应度函数适应度与适应度函数 适应度(fitness)就是借鉴生物个体对环境的 适应程度,而对问题中的个体对象所设计的 表征其优劣的一种测度。适应度函数(fitness function)就是问题中的 全体个体与其适应度之间的一个对应关系。它一般是一个实值函数。该函数就是遗传算 法中指导搜索的评价函数。7本讲稿第七页，共五十四页3.3.染色体与基因染色体与基因染色体（chromosome）就是问题中个体的某种字符串形式的编码表示。字符串中的字符也就称为基因（gene）。例如：个体 染色体 9 -1001 染色体长度l=4 （2，5，6）-010 101 110 l=38本讲稿第八页，共五十四页遗传算法基本概念和术语遗传算法基本概念和术语l进化（evolution）生物在其延续生存的过程中，逐渐适应其生存环境，使得其品质不断得到改良，这种生命现象称为进化。生物的进化是以种群的形式进行的。9本讲稿第九页，共五十四页4.4.遗传操作遗传操作亦称遗传算子(genetic operator)，就是关于染色体的运算。遗传算法中有三种遗传操作:选择-复制(selection-reproduction)交叉(crossover，亦称交换、交配或杂交)变异(mutation，亦称突变)10本讲稿第十页，共五十四页遗传算法基本概念和术语遗传算法基本概念和术语l选择（选择（selectionselection）按照一定概率随机地选择两对个体进行繁殖(即生成后继状态)遗传算法在很大程度上是一种偶然性现象，随机过程在其中起重要作用。一般而言，选择的过程是一种基于适应度的优胜劣汰的过程。11本讲稿第十一页，共五十四页l复制复制(又称繁殖又称繁殖)是从一个旧种群(old population)中选择生命力强的个体位串(或称字符串)产生新种群的过程。或者说，复制是个体位串根据其目标函数(即适应度函数)拷贝自己的过程。根据位串的适应度值拷贝位串意味着，具有较高适应度值的位串更有可能在下一代中产生一个或多个后代。显然，这个操作是模仿自然选择现象，将达尔文的适者生存理论应用于位串的复制，适应度值是该位串被复制或被淘汰的决定因素。8.1 遗传算法基本原理遗传算法基本原理12本讲稿第十二页，共五十四页选择-复制通常做法是：对于一个规模为N的种群S,按每个染色体xiS的选择概率P(xi)所决定的选中机会,分N次从S中随机选定N个染色体,并进行复制。这里的选择概率P(xi)的计算公式为13本讲稿第十三页，共五十四页遗传算法基本概念和术语遗传算法基本概念和术语l交叉（交叉（crossovercrossover）有性生殖生物在繁殖下一代时，两个同源染色体通过交叉而重组，亦即在两个染色体的某一相同位置处DNA被切断，其前后两串分别交叉组合形成两个新的染色体。这个过程又称基因重组（recombination），俗称“杂交”。14本讲稿第十四页，共五十四页交叉 就是互换两个染色体某些位上的基因。s1=01000101,s2=10011011可以看做是原染色体s1和s2的子代染色体。例如,设染色体 s1=01001011,s2=10010101,交换其后4位基因,即15本讲稿第十五页，共五十四页遗传算法基本概念和术语遗传算法基本概念和术语l变异（变异（mutation）在细胞进行复制时可能以很小的概率产生某些复制差错，从而使DNA发生某种变异，产生出新的染色体，这些新的染色体表现出新的性状。16本讲稿第十六页，共五十四页l变异变异 就是改变染色体某个(些)位上的基因。（0变为变为1或或1变为变为0）例如,设染色体 s=11001101将其第三位上的0变为1,即 s=11001101 11101101=s。s也可以看做是原染色体s的子代染色体。其中变异的位置是随机的。其中变异的位置是随机的。17本讲稿第十七页，共五十四页遗传学相关概念遗传学相关概念 遗传学遗传算法数学1个体要处理的基本对象、结构也就是可行解2群体个体的集合被选定的一组可行解3染色体个体的表现形式可行解的编码4基因染色体中的元素编码中的元素5基因位某一基因在染色体中的位置元素在编码中的位置6适应值个体对于环境的适应程度，或在环境压力下的生存能力可行解所对应的适应函数值7种群被选定的一组染色体或个体根据入选概率定出的一组可行解8选择从群体中选择优胜的个体，淘汰劣质个体的操作保留或复制适应值大的可行解，去掉小的可行解18本讲稿第十八页，共五十四页遗传学相关概念遗传学相关概念 遗传学遗传算法数学9交叉一组染色体上对应基因段的交换根据交叉原则产生的一组新解10交叉概率染色体对应基因段交换的概率（可能性大小）闭区间0,1上的一个值，一般为0.650.9011变异染色体水平上基因变化编码的某些元素被改变12变异概率染色体上基因变化的概率（可能性大小）开区间(0,1)内的一个值,一般为0.0010.0113进化、适者生存个体进行优胜劣汰的进化，一代又一代地优化目标函数取到最大值，最优的可行解19本讲稿第十九页，共五十四页函数极值的求解问题函数极值的求解问题由由数学分析数学分析可知，一个在闭区间可知，一个在闭区间a,b上连续的函数必上连续的函数必存在最大最小值，而且最大最小值可以通过以下方式得到：存在最大最小值，而且最大最小值可以通过以下方式得到：求出求出y=f（x）这个函数在）这个函数在a,b上所有的导数为上所有的导数为0的点、不可导点、的点、不可导点、区间的端点。区间的端点。计算所有以上点的函数值，进行比较，则最大的必定是最大值点、计算所有以上点的函数值，进行比较，则最大的必定是最大值点、最小的必定是最小值点。最小的必定是最小值点。对于导数为对于导数为0的点，还可以通过二阶导数来判断是极小还是极的点，还可以通过二阶导数来判断是极小还是极大值。大值。20本讲稿第二十页，共五十四页求函数求函数 的极值的极值很显然：利用导数求函数的极值只能针对那些简单的函数很显然：利用导数求函数的极值只能针对那些简单的函数才可以那样做，如果函数比较复杂，则无法利用求导数的才可以那样做，如果函数比较复杂，则无法利用求导数的方法求函数的极值。方法求函数的极值。求导数可能比较困难；求导数可能比较困难；即使求出导数，求导数为即使求出导数，求导数为0的点也相当的困难。的点也相当的困难。是否不需要利用函数的导数，也可以求函数的极值？是否不需要利用函数的导数，也可以求函数的极值？关于不需要利用导数就可以直接求函数的极值的方法，现关于不需要利用导数就可以直接求函数的极值的方法，现在有几种比较好的算法，在有几种比较好的算法，遗传算法遗传算法就是其中的一种，它不就是其中的一种，它不需要利用导数，只要有函数的表达式就可以求函数的极值。需要利用导数，只要有函数的表达式就可以求函数的极值。21本讲稿第二十一页，共五十四页我们得到的结论是：我们得到的结论是：生物一代比一代优生物一代比一代优目的：模仿生物遗传的方式设计一个求解函数极值的算法。目的：模仿生物遗传的方式设计一个求解函数极值的算法。例如：求例如：求y=x2的最小值的最小值1.任取一些值任取一些值2 5 -4 8 -10 12称为第一代，其实就是自变量称为第一代，其实就是自变量x的任意一些值。的任意一些值。它们的函数值分别为它们的函数值分别为4 25 16 64 100 144.22本讲稿第二十二页，共五十四页生物有染色体，根据染色体进行遗传与变异，从而得到下生物有染色体，根据染色体进行遗传与变异，从而得到下一代。一代。2.人为的构造这些染色体，用人为的构造这些染色体，用5位二进制表示，第一位表示正负位二进制表示，第一位表示正负号，号，0表示正、表示正、1表示负。表示负。2 5 -4 8 -10 12 00010 00101 10100 01000 11010 01100 遗传（杂交）遗传（杂交）00001 00110 10100 01000 11000 01110 1 6 -4 8 -8 1623本讲稿第二十三页，共五十四页 遗传（杂交）遗传（杂交）00001 00110 10100 01000 11000 01110变异得到第二代，产生变异的概率很小，一般变异的概率变异得到第二代，产生变异的概率很小，一般变异的概率8%，即每一位的，即每一位的0或或1都有都有8%的可能编码的可能编码1或者或者0第二代：第二代：00001 00100 10100 01000 11000 01110 1 4 -4 8 -8 16对应的函数值对应的函数值 1 16 16 64 64 169第二代比第一代好第二代比第一代好24本讲稿第二十四页，共五十四页第二代：第二代：00001 00100 10100 01000 11000 01110 遗传（杂交）遗传（杂交）00000 00101 10100 01000 11010 01100 变异变异第三代：第三代：00000 00101 10100 01010 11010 01100 0 5 -4 10 -10 12就已经得到了函数的最小值点就已经得到了函数的最小值点x=0，结束。，结束。25本讲稿第二十五页，共五十四页以上就是遗传算法求解最优问题的简单设计，是模仿生物以上就是遗传算法求解最优问题的简单设计，是模仿生物的遗传机制而设计的算法，是最基本形式的遗传算法。的遗传机制而设计的算法，是最基本形式的遗传算法。遗传算法的不同形式：（对基本遗传做出一些改动）遗传算法的不同形式：（对基本遗传做出一些改动）由于遗传算法是模拟生物的遗传与变异机制而设计的，而由于遗传算法是模拟生物的遗传与变异机制而设计的，而生物的遗传与变异是通过染色体来进行，所以生物的遗传与变异是通过染色体来进行，所以遗传算法必须遗传算法必须编码编码，因此，不同的编码机制就得到不同形式的遗传算法，因此，不同的编码机制就得到不同形式的遗传算法，从而，不同的遗传算法的第一个区别就是编码不同。从而，不同的遗传算法的第一个区别就是编码不同。26本讲稿第二十六页，共五十四页第一：编码不同得到的遗传算法就不一样。第一：编码不同得到的遗传算法就不一样。例如：上面这个例子是用例如：上面这个例子是用5位编码，其实，我们也可以采位编码，其实，我们也可以采用用6位编码、也可以采用位编码、也可以采用7位或位或100位编码都可以。位编码都可以。习题：采用习题：采用6位编码位编码采用不同的编码方法就得到不同的遗传算法。采用不同的编码方法就得到不同的遗传算法。问题：采用什么编码好呢？问题：采用什么编码好呢？这个问题到现在为止还没有答案，很多对遗传算法进行这个问题到现在为止还没有答案，很多对遗传算法进行研究的人，就是对各种各样的编码方法进行研究，看哪研究的人，就是对各种各样的编码方法进行研究，看哪种编码更好。种编码更好。27本讲稿第二十七页，共五十四页 遗传算法是模拟生物的遗传算法是模拟生物的遗传与变异遗传与变异机制而设计的，遗传算法的机制而设计的，遗传算法的两个基本运算就是遗传两个基本运算就是遗传杂交、变异杂交、变异。因此不同的选择。因此不同的选择遗传杂遗传杂交方式交方式与不同的与不同的变异方式变异方式就得到不同的遗传算法。就得到不同的遗传算法。第二：不同的杂交方法得到不同的遗传算法。第二：不同的杂交方法得到不同的遗传算法。例如：上面例子是每个个体都参与杂交。其实，我们知道自然界例如：上面例子是每个个体都参与杂交。其实，我们知道自然界中的法则是优胜劣汰。并不是每个个体都能找到伴侣。只有那些中的法则是优胜劣汰。并不是每个个体都能找到伴侣。只有那些好的，才能找到伴侣，同样的，这里也可以这样做。先看哪些个好的，才能找到伴侣，同样的，这里也可以这样做。先看哪些个体是好的，哪些个体是差的，让好的个体多杂交，把那些差的直体是好的，哪些个体是差的，让好的个体多杂交，把那些差的直接淘汰。接淘汰。哪些个体是好的，哪些个体是差的，怎么区分呢？哪些个体是好的，哪些个体是差的，怎么区分呢？28本讲稿第二十八页，共五十四页 求函数的最小值？求函数的最小值？2 5 -4 8 -10 12 00010 00101 10100 01000 11010 01100函数值分别为函数值分别为 4 25 16 64 100 144因为是要求函数的最小值，所以显然函数值越小越好，函数因为是要求函数的最小值，所以显然函数值越小越好，函数值越大越不好。所以最好的点是值越大越不好。所以最好的点是2，最差的点是，最差的点是12，因此，因此，可以直接淘汰可以直接淘汰12，而让，而让2这个点多杂交一次，因此杂交这一这个点多杂交一次，因此杂交这一步可以这样做：步可以这样做：2 5 -4 8 -10 2 00010 00101 10100 01000 11010 0001029本讲稿第二十九页，共五十四页上面只是给出了遗传算法的一种基本的形式，而不上面只是给出了遗传算法的一种基本的形式，而不同的编码方法与不同的杂交策略可以变形出各种同的编码方法与不同的杂交策略可以变形出各种各样的遗传算法。各样的遗传算法。同样，还有不同的变异方式也得到不同的算法。同样，还有不同的变异方式也得到不同的算法。30本讲稿第三十页，共五十四页在进行遗传算法操作时：上面第一种方法是两两交在进行遗传算法操作时：上面第一种方法是两两交叉遗传，而第二种做法是先淘汰最差，用一个最叉遗传，而第二种做法是先淘汰最差，用一个最好的去代替最差，再进行交叉遗传，好的去代替最差，再进行交叉遗传，也可以删除两个最差，用两个好一点的取代。也可以删除两个最差，用两个好一点的取代。2 5 -4 8 -10 12 00010 00101 10100 01000 11010 01100淘汰一个最差的淘汰一个最差的 2 5 -4 8 -10 2 00010 00101 10100 01000 11010 00010淘汰两个最差的淘汰两个最差的 2 5 -4 8 2 2 00010 00101 10100 01000 00010 0001031本讲稿第三十一页，共五十四页1.到底淘汰几个最差的？又用哪些好的取代差到底淘汰几个最差的？又用哪些好的取代差的，这些是可以有不同的数目的，这些数就叫的，这些是可以有不同的数目的，这些数就叫控控制参数制参数。2.选择不同的控制参数（控制策略），算法就不一样。选择不同的控制参数（控制策略），算法就不一样。例如不删除最差，每个都一样的交叉遗传，与删除最例如不删除最差，每个都一样的交叉遗传，与删除最差，用好的代替差的，算法不一样。差，用好的代替差的，算法不一样。3.还有一个控制参数就是在进行变异操作时，选多还有一个控制参数就是在进行变异操作时，选多少个进行变异，有选少个进行变异，有选8%的个体进行变异，也有选的个体进行变异，也有选5%的个数进行变异。这个百分数通常称为的个数进行变异。这个百分数通常称为变异率变异率。32本讲稿第三十二页，共五十四页可以把遗传算法的基本形式描述为：可以把遗传算法的基本形式描述为：Begina.生成初始种群，选择适当的编码方式；生成初始种群，选择适当的编码方式；b.通过计算群体中各个体的适应度对群体进行评通过计算群体中各个体的适应度对群体进行评价；价；c.While未达到要求的目标未达到要求的目标do begin a.选择繁殖下一代群体的各个体选择繁殖下一代群体的各个体 b.执行杂交操作执行杂交操作 c.执行变异操作执行变异操作 d.对群体进行评价对群体进行评价 endend33本讲稿第三十三页，共五十四页例例 1.设设 f(x)=-x2+2x+0.5，求，求 max f(x),x-1,2。遗传算法的实际应用遗传算法的实际应用 我们将通过这个简单的求最值问题来详细给出遗传算法的整个过程。（1）编码和产生初始群体）编码和产生初始群体u 首先需要确定编码的策略，也就是说如何把-1,2 区间内的数用计算机语言表示出来。编码就是从表现型到基因型的映射，编码时要注意以下三个原则：n 完备性：问题空间中所有点（潜在解）都能成为GA编码空间中的点（染色体位串）的表现型；n 健全性：GA编码空间中的染色体位串必须对应问题空间中的某一潜在解；n 非冗余性：染色体和潜在解必须一一对应34本讲稿第三十四页，共五十四页编码编码u 我们采用二进制形式来解决编码问题，即将某个变量值代表的个体表示为一个0,1二进制串。串的长度取决于求解的精度，例如假设求解精度为保留六位小数，由于区间-1,2 的长度为 3，则必须将该区间分为 3 106 等分。因为 2213 106222，所以编码所用的二进制串至少需要22位。n 二进制串（b21b20b19b1b0）与 a,b 内实数的一一映射：二进制串十进制数a,b 内实数b21b20b19b1b035本讲稿第三十五页，共五十四页编码编码转化到-1,2 内的实数为：例例.二进制串 a=其对应的十进制数为：36本讲稿第三十六页，共五十四页产生初始群体产生初始群体u 随机的产生一个初始群体。pop1=，%a1 ，%a2 ，%a3%a4这里假设初始群体的个体数为 4。n 转化成-1,2 之间的十进制数即为：下面就需要解决每个染色体个体的适应值pop1=1.523032,0.574022,-0.697235,0.24723837本讲稿第三十七页，共五十四页适应函数适应函数（2）定义适应函数和适应值由于目标函数 f(x)在-1,2 内的值有正有负，所以必须通过建立适应函数与目标函数的映射关系，保证映射后的适应值非负，而且目标函数的优化方向应对应于适应值增大的方向，也为以后计算各个体的入选概率打下基础。n 定义适应函数：为了便于计算，这里的 Fmin 采用了一个特定的输入值 例：例：如果取如果取 Fmin=-1，则，则 f(x)=1 对应的适应值为对应的适应值为 g(x)=238本讲稿第三十八页，共五十四页适应函数和适应值适应函数和适应值n 上述随机产生的初始群体，取 Fmin=-1，则，则它们的目标函数值和适应值分别为：f(pop1)=1.226437,1.318543,-1.380607,0.933350g(pop1)=2.226437,2.318543,0,1.93335039本讲稿第三十九页，共五十四页选择标准选择标准（3）确定选择标准u 用适应值比例来作为入选概率。u 设给定的规模为 n 的群体 pop=a1,a2,.,an，个体 ai 的适应值为 g(ai)，则其入选概率为n 上述随机产生的初始群体，它们的入选概率分别为：p(pop1)=g(pop1)/sum(g(pop1)=0.343675,0.357892,0,0.29843340本讲稿第四十页，共五十四页产生种群产生种群（4）产生种群u 将入选概率大的个体选入种群，淘汰概率小的个体，并用概率最大的个体补入种群，得到与原群体大小同样的种群。newpop1=，%a1 ，%a2 ，%a2%a4n 在上述随机产生的初始群体中，淘汰掉 a3，再加入 a2，得到新的种群：41本讲稿第四十一页，共五十四页交叉交叉（5）交叉u 交叉也就是将一组染色体上对应的基因段交换得到新的染色体，然后得到新的染色体组，组成新的群体。n 将前面得到的 newpop1 的四个个体两两配对，重复的不配对，进行交叉（可以在任一位进行交叉）：新的群体 jchpop142本讲稿第四十二页，共五十四页变异变异（6）变异u 变异就是通过一个小概率改变染色体位串上的某个基因。n 现把 jchpop1 中第 3 个个体中的第 9 位改变，就产生了变异，得到了新的群体 pop2：pop2=,然后重复上述的选择、交叉、变异，直到满足终止条件为止然后重复上述的选择、交叉、变异，直到满足终止条件为止 43本讲稿第四十三页，共五十四页终止条件终止条件（7）终止条件u 遗传算法的终止条件有两类常见条件：n 采用设定最大（遗传）代数的方法，一般可设定为 50代，此时就可能得出最优解此种方法简单易行，但可能不是很精确（Matlab程序参见附录1）n 根据个体的差异来判断，通过计算种群中基因多样性测度，即所有基因位相似程度来进行控制44本讲稿第四十四页，共五十四页遗传算法的收敛性遗传算法的收敛性 q 遗传算法通过对这些操作的适当设计和运行，可以实现兼顾全局搜索和局部搜索的所谓均衡搜索均衡搜索的具体实现图示45本讲稿第四十五页，共五十四页遗传算法的收敛性遗传算法的收敛性 q 遗传算法虽然可以实现均衡的搜索，并且在许多复杂问题的求解中往往能得到满意的结果，但是该算法的全局优化收敛性的理论分析尚待解决。目前普遍认为，标准遗传算法并不保证全局最优收敛。但是，在一定的约束条件下，遗传算法可以实现这一点。定理 1 1 如果变异概率为 ，交叉概率为 ，同时采用比例选择法(按个体适应度占群体适应度的比例进行复制)，则标准遗传算法的变换矩阵 P 是基本的。46本讲稿第四十六页，共五十四页遗传算法的收敛性遗传算法的收敛性 定理 2 2 标准遗传算法（参数如定理1）不能收敛至全局最优解。q 标准遗传算法是不能收敛至全局最最优解，对标准遗传算法作一些改进，就能够保证其收敛性。q 最佳个体保存方法（elitist model）的思想是把群体中适应度最高的个体不进行配对交叉而直接复制到下一代中。设时刻 t(第 t 代)时，群体中 a*(t)为最佳个体，并设 A(t+1)为新一代群体，若 A(t+1)中不存在 a*(t)，则把 a*(t)作为 A(t+1)中的第 n+1 个个体(其中，n 为群体大小)47本讲稿第四十七页，共五十四页最佳个体保存方法最佳个体保存方法 q 该方法的优点：确保进化过程中某一代的最优解不被交叉和变异操作所破坏。q 使用策略：与其他选择方法结合使用。q 该方法的缺点：局部最优个体的遗传基因会急速增加而使进化有可能限于局部解，即该方法的全局搜索能力差，它更适合单峰性质的搜索空间搜索，而不是多峰性质的空间搜索。48本讲稿第四十八页，共五十四页最佳个体保存方法最佳个体保存方法 定理 4具有定理 1 所示参数，且在选择前保留当前最优解的遗传算法可收敛于全局最优解。定理 3具有定理 1 所示参数，且在选择后保留当前最优值的遗传算法最终能收敛到全局最优解。49本讲稿第四十九页，共五十四页实验举例实验举例 例例 1.设设 f(x)=-x2+2x+0.5，求，求 max f(x),x-1,2。解：解：群体中包含六个染色体，每个染色体用 22 位码表示，变异概率为 0.01，变量区间为-1,2，取 Fmin=-2，遗传代数为 50 代，运用第一种终止条件（指定遗传代数）的 Matlab 程序为Count,Result,BestMember=Genetic1(22,6,-x*x+2*x+0.5,-1,2,-2,0.01,50)50本讲稿第五十页，共五十四页（1）GA是对问题参数的编码（染色体）进行操作，而不是参数本是对问题参数的编码（染色体）进行操作，而不是参数本身。身。（2）GA计算简单，便于计算机编程，功能强。计算简单，便于计算机编程，功能强。（3）GA是从问题解的串集开始搜索，而不是从单个解开始，更有利于是从问题解的串集开始搜索，而不是从单个解开始，更有利于搜索到全局最优解。搜索到全局最优解。（4）GA使用对象函数值（即适应值）这一信息进行搜索，而不使用对象函数值（即适应值）这一信息进行搜索，而不需导数等其它信息。需导数等其它信息。（5）GA的复制、交叉、变异这三个算子都是由概率决定的，而非确定的复制、交叉、变异这三个算子都是由概率决定的，而非确定性的。性的。（6）GA算法具有隐含的并行性，因而可通过大规模并行计算来提高算法具有隐含的并行性，因而可通过大规模并行计算来提高计算速度。计算速度。（7）GA更适合大规模复杂问题的优化，但解决简单问题效率并不高。更适合大规模复杂问题的优化，但解决简单问题效率并不高。遗传算法的特点遗传算法的特点51本讲稿第五十一页，共五十四页（1）问题编码）问题编码 问题编码就是如何将优化问题描述成串的形式，需要考虑编码方问题编码就是如何将优化问题描述成串的形式，需要考虑编码方法和串长等。法和串长等。（2）对象函数的确定。）对象函数的确定。对象函数用于评价各串的性能。函数优化问题可直接将函数本身对象函数用于评价各串的性能。函数优化问题可直接将函数本身作为对象函数。作为对象函数。（3）GA算法本身参数的确定。算法本身参数的确定。种群数目、交换概率、变异概率种群数目、交换概率、变异概率 等。等。应用应用GA的几个要点的几个要点52本讲稿第五十二页，共五十四页 遗传算法广泛应用于人工智能、机器学习、知识工程、遗传算法广泛应用于人工智能、机器学习、知识工程、函数优化、自动控制、模式识别、图像处理、生物工程等函数优化、自动控制、模式识别、图像处理、生物工程等众多领域。目前，遗传算法正在向其它学科和领域渗透，众多领域。目前，遗传算法正在向其它学科和领域渗透，正在形成遗传算法、神经网络和模糊控制相结合，从而构正在形成遗传算法、神经网络和模糊控制相结合，从而构成一种新型的智能控制系统整体优化的结构形式。成一种新型的智能控制系统整体优化的结构形式。53本讲稿第五十三页，共五十四页下课了下课了 !54本讲稿第五十四页，共五十四页