1、人工智能人工智能2016年秋季本章内容本章内容 概述概述 演化计算演化计算 模糊模糊计算计算本章内容本章内容 概述概述 演化计算演化计算 模糊模糊计算计算 计算计算智能智能（Computational Intelligence，CI） 计算计算智能是在智能是在神经网络（神经网络（Neural Networks,NN）、演化计算、演化计算（Evolutionary Computation,EC）及模糊系统（）及模糊系统（Fuzzy System,FS）这这3个领域发展相对成熟的基础上形成的一个统一个领域发展相对成熟的基础上形成的一个统一的学科概念的学科概念。 什么什么是计算智能是计算智能如果一个
2、系统仅处理低层的数值数据，含有模式识别部件，如果一个系统仅处理低层的数值数据，含有模式识别部件，没有使用人没有使用人工智能意义上的知识工智能意义上的知识，且具有，且具有计算适应性、计算容错力、接近人的计算计算适应性、计算容错力、接近人的计算速度速度和和近似于人的误差率近似于人的误差率这这4 4个特性，则它是计算智能的。个特性，则它是计算智能的。 神经网络神经网络是一种对人类智能的是一种对人类智能的结构模拟结构模拟方法，它是通过方法，它是通过对大量人工神经元的广泛并行互联，构造人工神经网络对大量人工神经元的广泛并行互联，构造人工神经网络系统去模拟生物神经系统的智能机理。系统去模拟生物神经系统的智
3、能机理。 演化演化计算计算是一种对人类智能的是一种对人类智能的演化模拟演化模拟方法，它是通过方法，它是通过对生物遗传和演化过程的认识，用进化算法去模拟人类对生物遗传和演化过程的认识，用进化算法去模拟人类智能的进化规律的。智能的进化规律的。 模糊模糊计算计算是一种对人类智能的是一种对人类智能的逻辑模拟逻辑模拟方法，它是通过方法，它是通过对人类处理模糊现象的认知能力的认识，用模糊逻辑去对人类处理模糊现象的认知能力的认识，用模糊逻辑去模拟人类的智能行为的。模拟人类的智能行为的。本章内容本章内容 概述概述 演化计算演化计算 模糊模糊计算计算7演化计算（演化计算（Evolutionary Evoluti
4、onary Computation,ECComputation,EC）：）：在在基因和种群层次上模拟自然界生物进化过程与机制的问题基因和种群层次上模拟自然界生物进化过程与机制的问题求解技术和计算模型求解技术和计算模型。思想思想源于源于生物遗传学生物遗传学和和适者生存适者生存的的自然规律自然规律基于基于达尔文（达尔文（DarwinDarwin）的进化论和孟德尔（）的进化论和孟德尔（MendelMendel）的遗传）的遗传变异理论变异理论典型代表：典型代表：遗传遗传算法（算法（Genetic AlgorithmGenetic Algorithm，GAGA）进化进化策略（策略（Evolutionar
5、y Evolutionary Strategy,ESStrategy,ES）进化进化规划（规划（Evolutionary Evolutionary Programming,EPProgramming,EP）遗传遗传规划（规划（Genetic Genetic Programming,GPProgramming,GP）演化演化计算计算 达尔文的达尔文的自然选择学说自然选择学说是一种被人们广泛接受的生物进是一种被人们广泛接受的生物进化化学说：学说： 生物要生存下去，就必须进行生存斗争。 具有有利变异的个体容易存活有利变异的个体容易存活下来，并且有更多的机会将有利变异传给后代；具有不利变异的个体就容易
6、不利变异的个体就容易被淘汰被淘汰，产生后代的机会也少的多。：自然选择。 遗传和变异遗传和变异是决定生物进化的内在因素。（相对稳定+新的物种）演化演化计算计算9 孟德尔基因遗传原理孟德尔基因遗传原理 遗传以密码方式存在细胞中，并以基因基因形式包含在染色染色体体内。 每个基因有特殊的位置并控制某种特殊性质；所以，每个基因产生的个体对环境具有某种适应性。 基因突变和基因杂交基因突变和基因杂交可产生更适应于环境的后代。演化演化计算计算10一一种模拟自然界生物进化过程与机制进行种模拟自然界生物进化过程与机制进行问题求解的自组织、自适应的问题求解的自组织、自适应的随机搜索随机搜索技术技术。 演化规则：演化
7、规则：“物竞天择、适者生存物竞天择、适者生存” 演化操作：演化操作：演化计算及其生物学基础演化计算及其生物学基础 遗传遗传算法的基本思想是算法的基本思想是从初始种群出发，采用优胜劣汰、适从初始种群出发，采用优胜劣汰、适者生存的自然法则选择个体，并通过杂交、变异来产生新一者生存的自然法则选择个体，并通过杂交、变异来产生新一代种群，如此逐代进化，直到满足目标代种群，如此逐代进化，直到满足目标为止为止 基本概念：基本概念：种群种群（Population）：多个备选解的集合。个体（个体（Individual）：）：种群中的单个元素，通常由一个用于描述其基本遗传结构的数据结构来表示。例如，长度为L 的0
8、、1串染色体染色体（Chromos）：对个体仿照基因编码进行编码后所得到的编码串。染色体中的每一位称为基因，染色体上由若干个基因构成的一个有效信息段称为基因组。遗传算法遗传算法 基本概念：基本概念：适应度（适应度（Fitness）函数）函数：用来对种群中各个个体的环境适应性进行度量的函数，函数值是遗传算法实现优胜劣汰的主要依据遗传操作（遗传操作（Genetic Operator）：作用于种群而产生新的种群的操作。 选择选择（Selection） 交叉交叉（Cross-over） 变异变异（Mutation） 遗传算法遗传算法遗传遗传算法主要由算法主要由染色体编码、初始种群设定、适应度函数设定、
9、遗传操作染色体编码、初始种群设定、适应度函数设定、遗传操作设计设计等几大部分所组成等几大部分所组成，算法基本步骤：算法基本步骤： 1. 选择编码策略，将问题搜索空间中每个可能的点用相应的编码策略表示出来，即形成染色体；2.2. 定义定义遗传策略遗传策略，包括种群规模包括种群规模N N，交叉、变异方法，以及选择概，交叉、变异方法，以及选择概率率PrPr、交叉概率、交叉概率PcPc、变异概率、变异概率PmPm等遗传参数；等遗传参数；3. 令t=0，随机选择N个染色体初始化种群P(0)；4.4. 定义定义适应度函数适应度函数f f；5. 计算P(t)中每个染色体的适应值；6. t=t+1；7. 运用
10、选择算子，从P(t-1)中得到P(t)；8. 对P(t)中的每个染色体，按概率Pc参与交叉；9. 对染色体中的基因，以概率Pm参与变异运算；10. 判断群体性能是否满足预先设定的终止标准，若不满足返回(5)。遗传算法遗传算法计算种群中各个个体的适应度，并进行评价满足终止条件吗？终止选择交叉变异Y编码和生成初始种群N选择遗传算法遗传算法适应函数 环境适应函数值 适应性适应函数值最大的解被保留的概率最大 适者生存问题的一个解 个体解的编码 染色体编码的元素 基因被选定的一组解 群体根据适应函数选择的一组解（以编码形式表示） 种群以一定的方式由双亲产生后代的过程 繁殖编码的某些分量发生变化的过程 变
11、异遗传遗传算法与生物进化之间对应关系算法与生物进化之间对应关系 二进制编码二进制编码（Binary encodingBinary encoding） 二进制编码二进制编码是将原问题的结构变换为染色体的位串结构。是将原问题的结构变换为染色体的位串结构。假设某一假设某一参数的取值范围是参数的取值范围是AA，BB，ABAB。用长度为用长度为L L的二进制编码的二进制编码串来表示该参串来表示该参数，将数，将AA，BB等分成等分成2 2L L- -1 1个子部分，记每一个等分的长度为个子部分，记每一个等分的长度为。例：假设例：假设变量变量x x的定义域的定义域为为 5 5，10)10)，要求的计算精度为
12、要求的计算精度为1010-5-5，则需要将，则需要将55，10)10)至少分为至少分为10000001000000个等长小区间，每个小区间用一个二进制串表示。于是，串长个等长小区间，每个小区间用一个二进制串表示。于是，串长至少等于至少等于2020，原因是，原因是： 524288=2524288=2191910000002100000022020=1048576 =1048576 这样这样，对应于区间，对应于区间55，10)10)内内满足精度要求的每个值满足精度要求的每个值x x，都可用一个，都可用一个2020位编码的二进制串位编码的二进制串来表示。来表示。 例如，例如，7 7和和8 8的二进制
13、数分别为的二进制数分别为01110111和和10001000，当算，当算法从法从7 7改进到改进到8 8时，就必须改变所有的位。时，就必须改变所有的位。 遗传编码遗传编码 格格雷编码（雷编码（Gray encodingGray encoding）要求要求两个连续整数的编码之间只能有一个码位不同，其余码位都是完全两个连续整数的编码之间只能有一个码位不同，其余码位都是完全相同的相同的。有效有效地解决地解决了海明了海明悬崖悬崖问题。问题。基本原理：基本原理：二进制码二进制码-格雷码（编码）：从最右边一位起，依次将每一位与格雷码（编码）：从最右边一位起，依次将每一位与左边一位异或左边一位异或(XOR)
14、(XOR)，作为对应格雷码该位的值，最左边一位不变；，作为对应格雷码该位的值，最左边一位不变；格雷码格雷码- -二进制码（解码）：从左边第二位起，将每位与左边一二进制码（解码）：从左边第二位起，将每位与左边一位位解码后解码后的值异或，作为该位解码后的值，最左边一位依然不变。的值异或，作为该位解码后的值，最左边一位依然不变。遗传编码遗传编码 符号编码（符号编码（Symbol encoding）个体个体染色体编码串中的基因值取自一个无数值含义、而只有代码染色体编码串中的基因值取自一个无数值含义、而只有代码含义的符号集含义的符号集。nwww,.,21由于是回路，记由于是回路，记wn+1= w1。它其
15、实是它其实是1，n的一个循环排列。的一个循环排列。要注意要注意w1， w2， wn是互不相同的是互不相同的。遗传编码遗传编码例如，对于例如，对于TSP问题，采用符号编码方法，按一条回路中城市的次序问题，采用符号编码方法，按一条回路中城市的次序进行编码，一般情况是从城市进行编码，一般情况是从城市w1开始，依次经过城市开始，依次经过城市w2 ， wn，最后回到城市最后回到城市w1，我们就有如下编码表示，我们就有如下编码表示：适应适应度函数度函数是一个用于对个体的适应性进行度量的函数是一个用于对个体的适应性进行度量的函数。个体个体的适的适应度值越大，它被遗传到下一代种群中的应度值越大，它被遗传到下一
16、代种群中的概率越大概率越大常用常用的适应度函数的适应度函数原始原始适应度适应度函数函数: : 直接直接将待求解问题的目标函数将待求解问题的目标函数f(x)f(x)定义为遗传算法定义为遗传算法的适应度函数的适应度函数。 例如：求最大值例如：求最大值 时，时，f(x)f(x)即为即为x x的原始适应度函数的原始适应度函数。：能够直接反映出待求解问题的最初求解目标， 缺点：缺点：有可能出现适应度值为负的情况)(max,xfbax适应度函数适应度函数 TSPTSP的目标是路径总长度为最短，路径总长度的目标是路径总长度为最短，路径总长度可作为可作为TSPTSP问题的适应度函数问题的适应度函数：njjjn
17、wwdwwwf1121),(1).(适应度函数适应度函数标准标准适应度函数适应度函数 在遗传算法中，一般要求适应度函数非负，并其适应度值越大越好。这就往往需要对原始适应函数进行某种变换，将其转换为标准的度量方式，以满足进化操作的要求，这样所得到的适应度函数被称为标准适应度函数fNormal(x)。 例：例：对对极小化问题，其标准适应度函数可定义为极小化问题，其标准适应度函数可定义为其中，其中，f fmaxmax (x)(x)是原始适应函数是原始适应函数f(x)f(x)的一个上界。如果的一个上界。如果f fmaxmax (x)(x) 未知，则可用当前未知，则可用当前代或到目前为止各演化代中的代或
18、到目前为止各演化代中的f(x)f(x)的最大值来代替的最大值来代替。 f fmaxmax (x)(x) 是会随着进化代数是会随着进化代数的增加而不断变化的的增加而不断变化的。 否则0)()(当)()()(maxmaxxfxfxfxfxf适应度函数适应度函数 极大化极大化问题问题 对极大化问题，其标准适应度函数可定义为对极大化问题，其标准适应度函数可定义为其中，其中，f fminmin(x)(x)是原始适应函数是原始适应函数f(x)f(x)的一个下界。如果的一个下界。如果f fminmin(x)(x) 未知，未知，则可用当前代或到目前为止各演化代中的则可用当前代或到目前为止各演化代中的f(x)f
19、(x)的最小值来代替。的最小值来代替。 否则当0)()()()()(minminxfxfxfxfxf适应度函数适应度函数遗传遗传算法中的基本遗传操作包括选择、交叉和算法中的基本遗传操作包括选择、交叉和变异。变异。选择选择(selection)(selection)操作操作: : 根据选择概率按某种策略从当前种群中挑选出一定数目的个体，使它们能够有更多的机会被遗传到下一代中常用常用的选择策略可分为的选择策略可分为比例选择、排序选择和竞技选择比例选择、排序选择和竞技选择三种三种类型。类型。 比例选择比例选择基本基本思想是：各个个体被选中的概率与其适应度大小成思想是：各个个体被选中的概率与其适应度大
20、小成正比正比。基本遗传操作基本遗传操作轮盘赌选择轮盘赌选择个体被选中的概率取决于该个体的相对适应度。而相对适应度的定义为：其中，P(xi)是个体xi的相对适应度，即个体xi被选中的概率；f(xi)是个体xi的原始适应度；是种群的累加适应度。轮盘轮盘赌选择算法的基本思想是：根据每个个体的选择概率赌选择算法的基本思想是：根据每个个体的选择概率P(xi)将一个圆盘将一个圆盘分成分成N个扇区，其中第个扇区，其中第i个扇区的中心角为个扇区的中心角为：并再设立一个固定指针。当进行选择时，可以假想转动圆盘，若圆盘静并再设立一个固定指针。当进行选择时，可以假想转动圆盘，若圆盘静止时指针指向第止时指针指向第i个
21、扇区，则选择个体个扇区，则选择个体i。1()()()iiNjjf xP xf x1()22()()iiNijjf xp xfx基本遗传操作基本遗传操作P(x1)P(x2)P(xN)P(xi)2p(xi)从从统计角度看，个体的适统计角度看，个体的适应度值越大，其对应的扇应度值越大，其对应的扇区的面积越大，被选中的区的面积越大，被选中的可能性也越大。这种方法可能性也越大。这种方法有点类似于发放奖品使用有点类似于发放奖品使用的轮盘，并带有某种赌博的轮盘，并带有某种赌博的意思，因此亦被称为轮的意思，因此亦被称为轮盘赌选择。盘赌选择。基本遗传操作基本遗传操作交叉交叉(crossover)(crossov
22、er)操作操作: : 按照按照某种方式对选择的父代个体的染色某种方式对选择的父代个体的染色体的部分基因进行交配重组，从而形成新的个体体的部分基因进行交配重组，从而形成新的个体。常见常见的交叉操作：的交叉操作：二进制交叉二进制交叉：二进制编码二进制编码情况下所采用的交叉操作，它主要情况下所采用的交叉操作，它主要包括：包括：单点交叉单点交叉两两点点交叉交叉多多点点交叉交叉均均匀交叉匀交叉基本遗传操作基本遗传操作单点单点交叉交叉先在两个父代个体的编码串中随机设定一个交叉点随机设定一个交叉点，然后对这两个父代个体交叉点前面或后面部分的基因进行交换交叉点前面或后面部分的基因进行交换，并生成子代中的两个新
23、的个体。假设假设两个父代的个体串分别是：两个父代的个体串分别是： X=x1 x2 xk xk+1 xn Y=y1 y2 yk yk+1 yn随机随机选择第选择第k位为交叉点位为交叉点，交叉，交叉后生成的两个新的个体是：后生成的两个新的个体是： X= x1 x2 xk yk+1 yn Y= y1 y2 yk xk+1 xn 设有设有两个父代的个体串两个父代的个体串A=0 0 1 1 0 1 和和B=1 1 0 0 1 0 ，若随机交叉点为，若随机交叉点为4，则则交叉后生成的两个新的个体是：交叉后生成的两个新的个体是： A= 0 0 1 1 1 1 B= 1 1 0 0 0 0 基本遗传操作基本遗
24、传操作两点交叉两点交叉先在两个父代个体的编码串中随机设定两个交叉点随机设定两个交叉点，然后再按这两个交按这两个交叉点进行部分基因交换叉点进行部分基因交换，生成子代中的两个新的个体。假设假设两个父代的个体串分别是：两个父代的个体串分别是： X=x1 x2 xi xj xn Y=y1 y2 yi yj ,yn随机随机设定第设定第i、j位为两个交叉点（其中位为两个交叉点（其中ijn），交叉），交叉后生成的两个新的后生成的两个新的个体是：个体是： X= x1 x2 xi yi+1 yj xj+1 xn Y= y1 y2 yi xi+1 xj yj+1 yn 例例: 设有设有两个父代的个体串两个父代的个
25、体串A= 0 0 1 1 0 1 和和B= 1 1 0 0 1 0 ，若随机交叉，若随机交叉点为点为3和和5，则交叉后的两个新的个体是：，则交叉后的两个新的个体是： A= 0 0 1 0 1 1 B= 1 1 0 1 0 0 基本遗传操作基本遗传操作均匀交叉均匀交叉先随机生成一个与父串具有相同随机生成一个与父串具有相同长度长度的二进制串（交叉模版），然后再再利用该模版对两个父串进行交叉利用该模版对两个父串进行交叉，即将模版中1对应的位进行交换，而0对应的位不交换，依此生成子代中的两个新的个体。事实上，这种方法对父串中的每一位都是以相同的概率随机进行交叉的。例5.10 设有两个父代的个体串A=0
26、01101和B=110010，若随机生成的模版T=010011，则交叉后的两个新的个体是A=011010和B=100101。即 A： 0 0 1 1 0 1 B： 1 1 0 0 1 0 T： 0 1 0 0 1 1 A： 0 1 1 1 1 0 B：1 0 0 0 0 1基本遗传操作基本遗传操作实值交实值交叉叉在在实数编码情况下所采用的交叉操作，主要包括实数编码情况下所采用的交叉操作，主要包括离散交叉离散交叉和和算术算术交叉交叉部分部分离散离散交叉交叉：先在两个父代个体的编码向量中随机选择一部分分量，然后对这部分分量进行交换，生成子代中的两个新的个体。整体交叉：整体交叉：对两个父代个体的编码
27、向量中的所有分量，都以1/2的概率进行交换，从而生成子代中的两个新的个体。假设假设两个父代个体的两个父代个体的n维实向量分别是维实向量分别是 X=x1x2 xixkxn和和Y=y1y2yiykyn，若随机选择对第，若随机选择对第k个分量以后的所有分量进行交换，个分量以后的所有分量进行交换，则生成的两个新的个体向量是：则生成的两个新的个体向量是： X= x1 x2 xk yk+1 yn Y= y1 y2 yk xk+1 xn 基本遗传操作基本遗传操作变异变异(Mutation)(Mutation)操作操作: : 对选中对选中个体的染色体中的某些基因进行变个体的染色体中的某些基因进行变动，以形成新
28、的个体。遗传算法中的变异操作增加了算法的动，以形成新的个体。遗传算法中的变异操作增加了算法的局部局部随机搜索随机搜索能力，从而可以维持种群的多样性。能力，从而可以维持种群的多样性。变异虽然可以带来群体的多样性，但因其具有很强的破坏性，因此变异虽然可以带来群体的多样性，但因其具有很强的破坏性，因此一般通过一个很小的变异概率来控制它的使用。一般通过一个很小的变异概率来控制它的使用。 根据个体编码方式的不同，变异操作可分为二进制变异和实值变异根据个体编码方式的不同，变异操作可分为二进制变异和实值变异两种类型。两种类型。 二进制变异二进制变异先随机地产生一个变异位，然后将该变异位置上的基因值由“0”变
29、为“1”，或由“1”变为“0”，产生一个新的个体。 例例5.12 设变异前的个体为设变异前的个体为A=0 0 1 1 0 1，若随机产生的，若随机产生的变异位置变异位置是是2，则该个体的第，则该个体的第2位由位由“0”变为变为“1”。 变异后的新的个体是变异后的新的个体是A= 0 1 1 1 0 1 。基本遗传操作基本遗传操作实值变异实值变异用用另外一个在规定范围内的随机实数去替换原变异位置上的基因值，产另外一个在规定范围内的随机实数去替换原变异位置上的基因值，产生一个新的个体。最常用的实值变异操作有生一个新的个体。最常用的实值变异操作有: 基于基于次序的次序的变异变异: 先随机地产生两个变异
30、位置，然后交换这两个变异位置上的基因。 例例: 设设选中的个体向量选中的个体向量D=20 12 16 19 21 30，若随机产生的两个变异位置分，若随机产生的两个变异位置分别时别时2和和4，则变异后的新的个体向量是：，则变异后的新的个体向量是： D= 20 19 16 12 21 30基本遗传操作基本遗传操作 精英主义精英主义 （ElitismElitism） 仅仅从产生的子代中选择基因去构造新的种群可能会丢失掉上一代种群中的很多信息。也就是说当利用交叉和变异产生新的一代时，我们有很大的可能把在某 个中间步骤中得到的最优解丢失。 使用精英主义（Elitism）方法，在每一次产生新的一代时，我
31、们首先把当前最优解原封不动的复制到新的当前最优解原封不动的复制到新的一代中一代中，其他步骤不变。这样任何时刻产生的一个最优解都可以存活到遗传算法结束。 上述各种算子的实现是多种多样的，而且许多新的算子正在不断地提出，以改进GA某些性能。基本遗传操作基本遗传操作例例5.15 用遗传算法求用遗传算法求函数函数 f(x)=x2 的的最大值，其中最大值，其中x为为0，31间的整数。间的整数。 解解： (1) 编码编码 由于x的定义域是区间0，31上的整数，由5位二进制数即可全部表示。因此，可采用二进制编码方法，其编码串的长度为5。 例如，用二进制串00000来表示x=0,11111来表示x=31等。其
32、中的0和1为基因值。 (2) 生成初始种群生成初始种群 若假设给定的种群规模N=4，则可用4个随机生成的长度为5的二进制串作为初始种群。再假设随机生成的初始种群（即第0代种群）为： s01=0 1 1 0 1 s02=1 1 0 0 1 s03=0 1 0 0 0 s04=1 0 0 1 0遗传算法应用遗传算法应用(3) 计算适应度计算适应度 要计算个体的适应度，首先应该定义适应度函数。由于本例是求f(x)的最大值，因此可直接用f(x)来作为适应度函数。即： f(s)=f(x)其中的二进制串s对应着变量x的值。根据此函数，初始种群中各个个体的适应值及其所占比例为。可以看出，在4个个体中S02的
33、适应值最大，是当前最佳个体。编号编号个体串（染色体）个体串（染色体）x x适应值适应值百分比百分比% %累计百分比累计百分比% %选中次数选中次数S010110101101131316916914.4414.4414.4414.441 1S021100111001252562562552.8852.8867.1867.182 2S0301000010008 864645.415.4172.5972.590 0S041001010010181832432427.4127.411001001 1遗传算法应用遗传算法应用（4 4) ) 选择操作选择操作假设采用轮盘赌方式选择个体，且依次生成的4个随机
34、数（相当于轮盘上指针所指的数）为0.85、0.32、0.12和0.46，经选择后得到的新的种群为： S01=10010 S02=11001 S03=01101 S04=11001其中，染色体11001在种群中出现了2次，而原染色体01000则因适应值太小而被淘汰 14% 53% 5% 27% -|-|-|-*-| 个体1 个体2 个体3 0.85 个体4随机数为0.85落在了个体4的端内.本次选择了个体4. 遗传算法应用遗传算法应用 (5) 交叉交叉 假设交叉概率Pi为50%，则种群中只有1/2的染色体参与交叉。若规定种群中的染色体按顺序两两配对交叉，且有S01与S02交叉，S03与S04不交
35、叉，则交叉情况为：可见，经交叉后得到的新的种群为： S01=10001 S02=11010 S03=01101 S04=11001编号编号个体串（染色体）个体串（染色体）交叉对象交叉对象交叉位交叉位 子代子代 适应值适应值S011001010010S023 31001000101289289S021100111001S013 31101101010676676S030110101101S04N N0110101101169169S041100111001S03N N1100111001625625遗传算法应用遗传算法应用 (6) 变异变异 变异概率Pm一般都很小，假设本次循环中没有发生变异，则
36、变异前的种群即为进化后所得到的第1代种群。即： S11=10001 S12=11010 S13=01101 S14=11001然后然后，对第，对第1代种群重复上述代种群重复上述(4)-(6)的的操作，选择情况如下：操作，选择情况如下： 其中若假设按轮盘赌选择时依次生成的4个随机数为0.14、0.51、0.24和0.82，经选择后得到的新的种群为： S11=10001 S12=11010 S13=11010 S14=11001可以看出，染色体11010被选择了2次，而原染色体01101则因适应值太小而被淘汰。 遗传算法应用遗传算法应用编号编号个体串（染色体）个体串（染色体） x适应值适应值百分比
37、百分比%累计百分比累计百分比%选中次数选中次数S111000110001272728928916.4316.4316.43716.4371 1S121101011010262667667638.4338.4354.8654.862 2S13011010110113131691699.619.6164.4764.470 0S141100111001252562562535.5335.531001001 1对第1代种群，其交叉情况：可见，经杂交后得到的新的种群为： S11=10010 S12=11001 S13=11001 S14=11010 可以看出，第可以看出，第3位基因均为位基因均为0，已经
38、不可能通过交配达到最优解。这种过早，已经不可能通过交配达到最优解。这种过早陷入局部最优解的现象称为早熟。为解决这一问题，需要采用变异操作陷入局部最优解的现象称为早熟。为解决这一问题，需要采用变异操作。编号编号个体串（染色体）个体串（染色体）交叉对象交叉对象交叉位交叉位子代子代适应值适应值S1110001S12310010324S1211010S11311001625S1311010S14211001625S1411001S13211010675遗传算法应用遗传算法应用 对第1代种群，其变异情况： 它是通过对S14的第3位的变异来实现的。变异后所得到的第2代种群为： S21=10010 S22=
39、11001 S23=11001 S24=11110 接着，再对第2代种群同样重复上述(4)-(6)的操作： 编号编号个体串（染色体）个体串（染色体）是否变异是否变异变异位变异位子代子代适应值适应值S1110010N10010324S1211001N11001625S1311001N11001625S1411010Y311110900遗传算法应用遗传算法应用 对第2代种群，同样重复上述(4)-(6)的操作。 其中若假设按轮盘赌选择时依次生成的4个随机数为0.42、0.15、0.59和0.91，经选择后得到的新的种群为： S21=11001 S22=10010 S23=11001 S24=1111
40、0编号编号个体串（染色体）个体串（染色体）x适应值适应值百分比百分比%累计百分比累计百分比%选中次数选中次数S21100101832423.9223.921S22110012562522.1246.041S23110012562522.1268.161S24111103090031.841001遗传算法应用遗传算法应用 对第2代种群，其交叉情况： 这时，函数的最大值已经出现，其对应的染色体为11111，经解码后可知问题的最优解是在点x=31处。 求解过程结束。编号编号个体串（染色个体串（染色体）体）交叉对象交叉对象交叉位交叉位子代子代适应值适应值 S211100111001 S223 3110
41、1101010676676 S221001010010 S213 31001000101289289 S231100111001 S244 4110011000 0576576 S241111011110 S234 4111111111 1961961遗传算法应用遗传算法应用例子：例子：8 8皇后问题皇后问题l目标：任何一个皇后都不会攻击到其他的皇后（皇后可以攻击和它在同一行、同一列或同一对角线上的皇后）l适应度函数取作可以彼此攻击的皇后对的数目（忽略障碍）8 8皇后的例子，其中每个状态用一个长度为皇后的例子，其中每个状态用一个长度为8 8的字符串来表示，适应度函数取的字符串来表示，适应度函数
42、取作不作不相互攻击的皇后对数目。相互攻击的皇后对数目。l问题表示：从问题表示：从k k个随机生成的状态（种群）开始个随机生成的状态（种群）开始l每个个体用一个有限长度的字符串表示每个个体用一个有限长度的字符串表示- -通常用通常用0 0，1 1表示表示每列八个皇后的位置：如每列八个皇后的位置：如*876543213 2 7 5 3 4 1 1011 010 111 101 011 100 001 001例子：例子：8 8皇后问题皇后问题l通过把两个父状态结合来生成后继通过把两个父状态结合来生成后继例子：例子：8 8皇后问题皇后问题遗传算法遗传算法特点特点自组织、自适应和自学习性自组织、自适应和
43、自学习性概率转移准则，非确定性规则概率转移准则，非确定性规则确定进化方案后，算法将利用进化过程中得到的信息确定进化方案后，算法将利用进化过程中得到的信息自行组织搜索自行组织搜索；基于自然的选择策略，优胜劣汰；基于自然的选择策略，优胜劣汰；遗传算法很快就能找到良好的解，即使是在很复杂的解空间中遗传算法很快就能找到良好的解，即使是在很复杂的解空间中采用随机方法进行最优解搜索，选择体现了向最优解迫近交叉体现了最优解的产生，变异体现了全局最优解的复盖本质并行性本质并行性-群体群体搜索搜索算法算法本身非常适合大规模并行，本身非常适合大规模并行，各种群分别独立进化各种群分别独立进化，不需要相互间，不需要相
44、互间交换信息；二是可以交换信息；二是可以同时搜索解空间的多个区域同时搜索解空间的多个区域并相互间交流信息，并相互间交流信息，使得演化计算能使得演化计算能以较少的计算获得较大的收益以较少的计算获得较大的收益。遗传算法特点遗传算法特点不需要其他知识，只需要影响搜索方向的目标函数和相应的不需要其他知识，只需要影响搜索方向的目标函数和相应的适应度适应度函数函数对待对待求解问题的指标函数没有什么特殊的要求，如不要求连续性、求解问题的指标函数没有什么特殊的要求，如不要求连续性、导数存在、单峰值等假设导数存在、单峰值等假设容易容易形成通用算法程序形成通用算法程序遗传遗传算法不能解决那些算法不能解决那些“大海
45、捞针大海捞针”的问题，所谓的问题，所谓“大海捞针大海捞针”问问题题就是没有一个确切的适应度函数表征个体好坏的问题就是没有一个确切的适应度函数表征个体好坏的问题，遗传算法，遗传算法对这类问题无法找到收敛的路径对这类问题无法找到收敛的路径。应用应用广泛广泛遗传算法擅长解决的问题是全局最优化问题，例如，解决时间表安遗传算法擅长解决的问题是全局最优化问题，例如，解决时间表安排问题就是它的一个特长，很多安排时间表的软件都使用遗传排问题就是它的一个特长，很多安排时间表的软件都使用遗传算法算法遗传算法特点遗传算法特点理论上证明算法的收敛性很困难理论上证明算法的收敛性很困难多用于解决实际问题多用于解决实际问题
46、汽车设计，包括材料选择、多目标汽车组件设计、减轻汽车设计，包括材料选择、多目标汽车组件设计、减轻重量等。重量等。机电系统设计。机电系统设计。分布计算机网络的拓扑结构。分布计算机网络的拓扑结构。电路设计，此类用途的遗传算法叫做进化电路。电路设计，此类用途的遗传算法叫做进化电路。移动通讯优化结构。移动通讯优化结构。煤气管道的最优控制、通信网络链接长度的优化问题、煤气管道的最优控制、通信网络链接长度的优化问题、铁路运输计划优化、喷气式收音机涡轮机的设计、铁路运输计划优化、喷气式收音机涡轮机的设计、VLSIVLSI版面设计、键盘排列优化版面设计、键盘排列优化抓到老鼠的猫都是好猫抓到老鼠的猫都是好猫本章
47、内容本章内容 概述概述 演化计算演化计算 模糊模糊计算计算模糊模糊计算计算美国加州大学美国加州大学扎德扎德( (ZadehZadeh) )教授于教授于19651965年提出的模糊集合与模年提出的模糊集合与模糊逻辑理论是模糊计算的数学基础糊逻辑理论是模糊计算的数学基础。 发表了文章模糊集 (Fuzzy sets，Information and Control, 8, 338-353) 主要用来处理现实世界中因模糊而引起的不确定性。 模糊理论已经在推理、控制、决策等方面得到了非常广泛的应用 模糊模糊计算计算 “模糊不是罪过模糊不是罪过”： 模糊模糊 ”糊涂糊涂”, , “朦胧朦胧”, , ” ”傻
48、冒傻冒”, , “ “痴呆痴呆” 取得取得精确数据不可能或很困难精确数据不可能或很困难 例如：例如：粒种子肯定不能叫一堆，粒也不是，粒也不是粒种子肯定不能叫一堆，粒也不是，粒也不是那那么多少粒种子叫一堆呢？适当的界限在哪里呢？我们能否说么多少粒种子叫一堆呢？适当的界限在哪里呢？我们能否说粒种子不叫一堆，而粒种子叫一堆呢粒种子不叫一堆，而粒种子叫一堆呢？ 没有没有必要获取精确数据必要获取精确数据 例如：例如：要要从一片西瓜地里找出一个最大的西瓜，那是件很麻烦的事。从一片西瓜地里找出一个最大的西瓜，那是件很麻烦的事。必须必须 把西瓜地里所有的西瓜都找出来，再比较一下，才知道哪个西把西瓜地里所有的西
49、瓜都找出来，再比较一下，才知道哪个西瓜最大。西瓜越多，工作量就越大。如果按通常说的，到西瓜地里瓜最大。西瓜越多，工作量就越大。如果按通常说的，到西瓜地里去找一个较大的西瓜，这时精确去找一个较大的西瓜，这时精确的问题就转的问题就转化成模糊的问题，反而化成模糊的问题，反而容易多了。由此可见，适当的模糊能使问题得到简化。容易多了。由此可见，适当的模糊能使问题得到简化。 清晰清晰的的概念概念: : 对象对象是否属于这个概念是明确的是否属于这个概念是明确的。 例如例如；人、自然数、；人、自然数、正方形。正方形。 模糊性的概念：对象从属的界限是模糊的，随判断人的思维模糊性的概念：对象从属的界限是模糊的，随
50、判断人的思维而定而定 “最大的最大的”与与“较大的较大的”都是有区别的两个概念。都是有区别的两个概念。但是但是它们的它们的区别区别都是逐渐的，而不是突变的都是逐渐的，而不是突变的，两者之间并不存在明确的界限，两者之间并不存在明确的界限 一个人一个人很高或很胖，但是很高或很胖，但是究竟多少究竟多少厘米才算高，多少千克才算厘米才算高，多少千克才算胖呢？高和胖都很模糊。胖呢？高和胖都很模糊。 饭什么时候才算熟了？衣服什么样才能算洗干净？饭什么时候才算熟了？衣服什么样才能算洗干净？ 例如：例如：美不美？早不早美不美？早不早？便宜？便宜不便宜不便宜？ 在客观世界中，上述的模糊概念要比清晰概念多得多。在客
