1、第第6 6章章 智能计算智能计算 有些有些人担心人工智能的出现会令人类感到人担心人工智能的出现会令人类感到自卑，但任何有头脑的人单是观察花朵就应该自卑，但任何有头脑的人单是观察花朵就应该能感到自己的渺小。能感到自己的渺小。艾伦凯6.16.1进化算法进化算法6.1.16.1.1进化算法的概念进化算法的概念 进化算法进化算法（Evolutionary AlgorithmsEvolutionary Algorithms，EAEA）是基于自然）是基于自然选择和自然遗传等生物进化机制的一种搜索算法选择和自然遗传等生物进化机制的一种搜索算法。进化进化算法是以达尔文的进化论思想为基础，通过模拟生物算法是以达
2、尔文的进化论思想为基础，通过模拟生物进化过程与机制的求解问题的自组织、自适应的人工智能技术，进化过程与机制的求解问题的自组织、自适应的人工智能技术，是一类借鉴生物界自然选择和自然遗传机制的随机搜索算法是一类借鉴生物界自然选择和自然遗传机制的随机搜索算法。6.1.26.1.2进化算法的生物机理进化算法的生物机理 生物生物遗传物质的主要载体是染色体遗传物质的主要载体是染色体（ChromosomeChromosome），），DNADNA是其中最主要的遗传物质是其中最主要的遗传物质。染色体染色体中基因的位置称作基因座，而基因所取中基因的位置称作基因座，而基因所取的值又叫等位基因的值又叫等位基因。基因基
3、因和基因座决定了染色体的特征，也决定了和基因座决定了染色体的特征，也决定了生物个体（生物个体（individualindividual）的性状。如头发的颜色是）的性状。如头发的颜色是黑色、棕色或者金黄色等。黑色、棕色或者金黄色等。6.1.36.1.3进化算法的设计原则进化算法的设计原则（1 1）适用性）适用性原则原则 该该算法所能适用的问题种类，它取决于算法所需的限制与假定。优化问题的不算法所能适用的问题种类，它取决于算法所需的限制与假定。优化问题的不同，则相应的处理方式也不同。同，则相应的处理方式也不同。（2 2）可靠性）可靠性原则原则 算法算法对于所设计的问题，以适当的精度求解其中大多数问
4、题的能力。因为演化对于所设计的问题，以适当的精度求解其中大多数问题的能力。因为演化计算的结果带有一定的随机性和不确定性，所以，在设计算法时应尽量经过较大样计算的结果带有一定的随机性和不确定性，所以，在设计算法时应尽量经过较大样本的检验，以确认算法是否具有较大的可靠度。本的检验，以确认算法是否具有较大的可靠度。（3 3）收敛性）收敛性原则原则 指指算法能否收敛到全局最优。在收敛的前提下，希望算法具有较快的收敛速度。算法能否收敛到全局最优。在收敛的前提下，希望算法具有较快的收敛速度。6.1.36.1.3进化算法的设计原则进化算法的设计原则（4 4）稳定性）稳定性原则原则 指指算法对其控制参数及问题
5、的数据的敏感度算法对其控制参数及问题的数据的敏感度。在。在设计算法时应尽量使设计算法时应尽量使得算法对一组固定的控制参数能在较广泛的问题的数据范围内解题，而且得算法对一组固定的控制参数能在较广泛的问题的数据范围内解题，而且对一组给定的问题数据，算法对其控制参数的微小扰动不很敏感。对一组给定的问题数据，算法对其控制参数的微小扰动不很敏感。（5 5）生物类比）生物类比原则原则 因为因为进化算法的设计思想是基于生物演化过程的，所以那些在生物界进化算法的设计思想是基于生物演化过程的，所以那些在生物界被认为是有效的方法及操作可以通过类比的方法引入到算法中，有时会带被认为是有效的方法及操作可以通过类比的方
6、法引入到算法中，有时会带来较好的结果。来较好的结果。6.26.2基本遗传算法基本遗传算法6.26.2基本遗传算法基本遗传算法6.2.26.2.2编码编码 遗传遗传算法中包含了五个基本算法中包含了五个基本要素要素：参数参数编码、初始群体的设定、适应度函数的设计、遗传操作编码、初始群体的设定、适应度函数的设计、遗传操作设计和控制参数设定。设计和控制参数设定。由于遗传算法不能直接处理问题空间的参数，因此，必须通由于遗传算法不能直接处理问题空间的参数，因此，必须通过编码将要求解的问题表示成遗传空间的染色体或者个体。过编码将要求解的问题表示成遗传空间的染色体或者个体。6.2.26.2.2编码编码6.2.
7、26.2.2编码编码6.2.26.2.2编码编码2.2.实数编码实数编码 为克服二进制编码的缺点，对问题的变量是实向量的情形，可以直接采为克服二进制编码的缺点，对问题的变量是实向量的情形，可以直接采用实数编码用实数编码。实数实数编码是用若干实数表示一个个体，然后在实数空间上进行遗传操作。编码是用若干实数表示一个个体，然后在实数空间上进行遗传操作。采用实数表达法不必进行数制转换，可直接在解的表现型上进行遗传操作。采用实数表达法不必进行数制转换，可直接在解的表现型上进行遗传操作。从而可从而可引入与引入与问题领域相关的启发式信息来增加算法的搜索能力问题领域相关的启发式信息来增加算法的搜索能力。3.3
8、.多参数级联编码多参数级联编码 对于多参数优化问题的遗传算法，常采用多参数级联编码对于多参数优化问题的遗传算法，常采用多参数级联编码。把把每个参数先进行二进制编码得到子串，再把这些子串连成一个完整的每个参数先进行二进制编码得到子串，再把这些子串连成一个完整的染色体染色体。多多参数级联编码中的每个子串对应各自的编码参数，所以，可以有不同参数级联编码中的每个子串对应各自的编码参数，所以，可以有不同的串长度和参数的取值范围。的串长度和参数的取值范围。6.2.36.2.3群体设定群体设定1.1.初始种群的产生初始种群的产生 遗传算法中初始群体中的个体可以是随机产生的，但最好采用如下策略遗传算法中初始群
9、体中的个体可以是随机产生的，但最好采用如下策略设定：设定：根据问题固有知识，设法把握最优解所占空间在整个问题空间中的分布范根据问题固有知识，设法把握最优解所占空间在整个问题空间中的分布范围，然后，在此分布范围内设定初始群体。围，然后，在此分布范围内设定初始群体。先随机产生一定数目的个体，然后从中挑选最好的个体加入初始群体中。先随机产生一定数目的个体，然后从中挑选最好的个体加入初始群体中。这种过程不断迭代，直到初始群体中个体数目达到了预先确定的规模。这种过程不断迭代，直到初始群体中个体数目达到了预先确定的规模。6.2.36.2.3群体设定群体设定6.2.46.2.4适应度函数适应度函数6.2.4
10、6.2.4适应度函数适应度函数6.2.46.2.4适应度函数适应度函数6.2.56.2.5选择选择 1.1.个体选择概率分配方法个体选择概率分配方法 在遗传算法中，哪个个体被选择进行交叉是按照概率进行的在遗传算法中，哪个个体被选择进行交叉是按照概率进行的。适应适应度大的个体被选择的概率大，但不是说一定能够被选上。同样，适度大的个体被选择的概率大，但不是说一定能够被选上。同样，适应度小的个体被选择的概率小，但也可能被选上。所以，首先要根据个体的应度小的个体被选择的概率小，但也可能被选上。所以，首先要根据个体的适应度确定被选择的概率适应度确定被选择的概率。6.2.56.2.5选择选择6.2.56.
11、2.5选择选择 1.1.个体选择概率分配方法个体选择概率分配方法 (2 (2）排序方法）排序方法 排序方法排序方法(Rank-based-Model(Rank-based-Model）是计算每个个体的适应度后，根据适应度）是计算每个个体的适应度后，根据适应度大小顺序对群体中个体进行排序，然后把事先设计好的概率按排序分配给个大小顺序对群体中个体进行排序，然后把事先设计好的概率按排序分配给个体，作为各自的选择概率体，作为各自的选择概率。在在排序方法中，选择概率仅仅取决于个体在种群中的序位，不是实际的排序方法中，选择概率仅仅取决于个体在种群中的序位，不是实际的适应度值。排在前面的个体有较多的被选择的
12、机会。适应度值。排在前面的个体有较多的被选择的机会。6.2.56.2.5选择选择 2.2.选择个体方法选择个体方法 选择操作是根据个体的选择概率确定哪些个体被选择进行交叉、变异等选择操作是根据个体的选择概率确定哪些个体被选择进行交叉、变异等操作操作，基本基本的选择方法如下。的选择方法如下。（1 1）轮盘赌选择）轮盘赌选择 轮盘赌选择（轮盘赌选择（Roulette Wheel SelectionRoulette Wheel Selection）策略在遗传算法中使用得最）策略在遗传算法中使用得最多多。在在轮盘赌选择方法中先按个体的选择概率产生一个轮盘，轮盘每个区的轮盘赌选择方法中先按个体的选择概率
13、产生一个轮盘，轮盘每个区的角度与个体的选择概率成比例，然后产生一个随机数，它落入转盘的哪个区角度与个体的选择概率成比例，然后产生一个随机数，它落入转盘的哪个区域就选择相应的个体交叉。域就选择相应的个体交叉。6.2.56.2.5选择选择(3 3）最佳个体保存方法）最佳个体保存方法 最佳最佳个体保存方法或称为精英选拔方法（个体保存方法或称为精英选拔方法（Elitist ModelElitist Model）是把群体中适）是把群体中适应度最高的一个或者多个个体不进行交叉而直接复制到下一代中，保证遗传应度最高的一个或者多个个体不进行交叉而直接复制到下一代中，保证遗传算法终止时得到的最后结果一定是历代出
14、现过的最高适应度的个体算法终止时得到的最后结果一定是历代出现过的最高适应度的个体。使用使用这种方法能够明显提高遗传算法的收敛速度，但可能使种群过快收这种方法能够明显提高遗传算法的收敛速度，但可能使种群过快收敛，从而只找到局部最优解敛，从而只找到局部最优解。保留保留种群个体总数的种群个体总数的2%5%2%5%的适应度最高的个体，效果最为理想。在使用的适应度最高的个体，效果最为理想。在使用其他选择方法时，一般都同时使用最佳个体保存方法，以保证不会丢失最优其他选择方法时，一般都同时使用最佳个体保存方法，以保证不会丢失最优个体。个体。6.2.66.2.6交叉交叉 当当两个生物机体配对或者复制时，它们的
15、染色体相互混合，产生一对由两个生物机体配对或者复制时，它们的染色体相互混合，产生一对由双方基因组成的新的染色体。这一过程称为交叉（双方基因组成的新的染色体。这一过程称为交叉（CrossoverCrossover）或者重组）或者重组（RecombinationRecombination）。交叉交叉得到的后代可能继承了上代的优良基因，其后代会比它们的父母更得到的后代可能继承了上代的优良基因，其后代会比它们的父母更加优秀，但也可能继承了上代的不良基因，其后代则会比它们的父母差，难加优秀，但也可能继承了上代的不良基因，其后代则会比它们的父母差，难以生存，甚至不能再复制自己以生存，甚至不能再复制自己。越
16、越能适应环境的后代越能继续复制自己并将其基因传给后代。由此形成能适应环境的后代越能继续复制自己并将其基因传给后代。由此形成一种趋势：每一代总是比其父母一代生存和复制得更好。一种趋势：每一代总是比其父母一代生存和复制得更好。6.2.66.2.6交叉交叉1 1.基本的交叉算子基本的交叉算子（1 1）一点交叉）一点交叉 一点交叉（一点交叉（Single-point CrossoverSingle-point Crossover）又称为简单交叉）又称为简单交叉。在在个体串中随机设定一个交叉点，实行交叉时，该点前或后的两个个体个体串中随机设定一个交叉点，实行交叉时，该点前或后的两个个体的部分结构进行互换
17、，并生成两个新的个体。的部分结构进行互换，并生成两个新的个体。（2 2）二点交叉）二点交叉 二点交叉二点交叉(Two-point Crossover(Two-point Crossover）的操作与一点交叉类似，只是设置了）的操作与一点交叉类似，只是设置了两个交叉点两个交叉点(仍然是随机设定），将两个交叉点之间的码串相互交换仍然是随机设定），将两个交叉点之间的码串相互交换。类似于类似于二点交叉，可以采用多点交叉（二点交叉，可以采用多点交叉（Multiple-point CrossoverMultiple-point Crossover）。）。6.2.66.2.6交叉交叉2.2.修正的交叉方法修
18、正的交叉方法 对对交叉、变异等遗传操作进行适当地修正，使其满足优化问题的约束条交叉、变异等遗传操作进行适当地修正，使其满足优化问题的约束条件件。例如例如，在，在TSPTSP问题中采用部分匹配交叉（问题中采用部分匹配交叉（Partially Matched CrossoverPartially Matched Crossover，PMXPMX），顺序交叉（），顺序交叉（Order CrossoverOrder Crossover，OXOX）和循环交叉（）和循环交叉（Cycle crossoverCycle crossover，CXCX）等。这些方法对于其他一些问题也同样适用。）等。这些方法对于其
19、他一些问题也同样适用。6.2.76.2.7变异变异6.2.76.2.7变异变异6.2.86.2.8遗传算法的步骤遗传算法的步骤6.36.3遗传算法的应用遗传算法的应用 6.46.4群智能算法群智能算法 由由简单个体组成的群落与环境以及个体之间的互动行为，简单个体组成的群落与环境以及个体之间的互动行为，称为称为群体智能群体智能。受动物群体智能启发的算法称为受动物群体智能启发的算法称为群智能群智能（Swarm IntelligenceSwarm Intelligence，SISI）算法）算法。群群智能算法包括：粒子群优化算法、蚁群算法和人工免疫算法智能算法包括：粒子群优化算法、蚁群算法和人工免疫算
20、法。粒子群粒子群优化算法起源于对简单社会系统的模拟。最初设想是用粒子群优优化算法起源于对简单社会系统的模拟。最初设想是用粒子群优化算法模拟鸟群觅食的过程，但后来发现它是一种很好的优化工具化算法模拟鸟群觅食的过程，但后来发现它是一种很好的优化工具。蚁蚁群算法是对蚂蚁群采集食物过程的模拟，已经成功地运用在很多离散群算法是对蚂蚁群采集食物过程的模拟，已经成功地运用在很多离散优化问题上。优化问题上。6.4.16.4.1粒子群优化算法粒子群优化算法6.4.16.4.1粒子群优化算法粒子群优化算法6.4.16.4.1粒子群优化算法粒子群优化算法6.4.26.4.2蚁群算法蚁群算法1 1 蚁群算法基本模型蚁
21、群算法基本模型 蚁群优化算法的第一个应用是著名的旅行商问题（蚁群优化算法的第一个应用是著名的旅行商问题（TSPTSP），），DorigoDorigo等人充等人充分利用了蚁群搜索食物的过程与旅行商问题之间的相似性通过人工模拟蚂蚁分利用了蚁群搜索食物的过程与旅行商问题之间的相似性通过人工模拟蚂蚁搜索食物的搜索食物的过程过程。通过通过个体之间的信息交流与相互协作最终找到从蚁穴到食物源的最短路个体之间的信息交流与相互协作最终找到从蚁穴到食物源的最短路径，来求解旅行商问题径，来求解旅行商问题。6.4.26.4.2蚁群算法蚁群算法6.4.26.4.2蚁群算法蚁群算法6.4.26.4.2蚁群算法蚁群算法6.
22、4.26.4.2蚁群算法蚁群算法蚁蚁群群算法求解旅行商问题算法求解旅行商问题 6.4.26.4.2蚁群算法蚁群算法蚁蚁群群算法求解旅行商问题算法求解旅行商问题 6.4.26.4.2蚁群算法蚁群算法蚁蚁群群算法求解旅行商问题的解：算法求解旅行商问题的解：6.56.5小结小结 遗传遗传算法主要借用生物进化中算法主要借用生物进化中“适者生存适者生存”的规律。遗传算法的设计包的规律。遗传算法的设计包括编码、适应度函数选择、控制参数、交叉与变异等遗传算子。括编码、适应度函数选择、控制参数、交叉与变异等遗传算子。个体选择概率的常用分配方法有适应度比例方法、排序方法等。选择个个体选择概率的常用分配方法有适应
23、度比例方法、排序方法等。选择个体方法主要有轮盘赌选择方法、锦标赛选择方法、最佳个体保存方法等。体方法主要有轮盘赌选择方法、锦标赛选择方法、最佳个体保存方法等。群智能算法与进化算法既有相同之处，也有明显的不同之处。相同之处：群智能算法与进化算法既有相同之处，也有明显的不同之处。相同之处：首先，首先，ECEC和和SISI都是受自然现象的启发，基于抽取出的简单自然规则而发展出都是受自然现象的启发，基于抽取出的简单自然规则而发展出的计算模型的计算模型。其次其次，两者又都是基于种群的方法，且种群中的个体之间、个体与环境，两者又都是基于种群的方法，且种群中的个体之间、个体与环境之间存在相互作用。之间存在相互作用。
