《人工智能及其应用》课件第6章 智能计算

第6章

智能计算

有些人担心人工智能的出现会令人类感到自卑，但任何有头脑的人单是观察花朵就应该能感到自己的渺小。——艾伦·凯6.1进化算法6.1.1进化算法的概念

进化算法（EvolutionaryAlgorithms，EA）是基于自然选择和自然遗传等生物进化机制的一种搜索算法。

进化算法是以达尔文的进化论思想为基础，通过模拟生物进化过程与机制的求解问题的自组织、自适应的人工智能技术，是一类借鉴生物界自然选择和自然遗传机制的随机搜索算法。6.1.2进化算法的生物机理

生物遗传物质的主要载体是染色体（Chromosome），DNA是其中最主要的遗传物质。

染色体中基因的位置称作基因座，而基因所取的值又叫等位基因。

基因和基因座决定了染色体的特征，也决定了生物个体（individual）的性状。如头发的颜色是黑色、棕色或者金黄色等。6.1.3进化算法的设计原则（1）适用性原则该算法所能适用的问题种类，它取决于算法所需的限制与假定。优化问题的不同，则相应的处理方式也不同。（2）可靠性原则算法对于所设计的问题，以适当的精度求解其中大多数问题的能力。因为演化计算的结果带有一定的随机性和不确定性，所以，在设计算法时应尽量经过较大样本的检验，以确认算法是否具有较大的可靠度。（3）收敛性原则

指算法能否收敛到全局最优。在收敛的前提下，希望算法具有较快的收敛速度。6.1.3进化算法的设计原则（4）稳定性原则

指算法对其控制参数及问题的数据的敏感度。在设计算法时应尽量使得算法对一组固定的控制参数能在较广泛的问题的数据范围内解题，而且对一组给定的问题数据，算法对其控制参数的微小扰动不很敏感。（5）生物类比原则

因为进化算法的设计思想是基于生物演化过程的，所以那些在生物界被认为是有效的方法及操作可以通过类比的方法引入到算法中，有时会带来较好的结果。6.2基本遗传算法

6.2基本遗传算法6.2.2编码

遗传算法中包含了五个基本要素：

参数编码、初始群体的设定、适应度函数的设计、遗传操作设计和控制参数设定。

由于遗传算法不能直接处理问题空间的参数，因此，必须通过编码将要求解的问题表示成遗传空间的染色体或者个体。6.2.2编码

6.2.2编码

6.2.2编码2.实数编码

为克服二进制编码的缺点，对问题的变量是实向量的情形，可以直接采用实数编码。

实数编码是用若干实数表示一个个体，然后在实数空间上进行遗传操作。采用实数表达法不必进行数制转换，可直接在解的表现型上进行遗传操作。从而可引入与问题领域相关的启发式信息来增加算法的搜索能力。3.多参数级联编码

对于多参数优化问题的遗传算法，常采用多参数级联编码。

把每个参数先进行二进制编码得到子串，再把这些子串连成一个完整的染色体。

多参数级联编码中的每个子串对应各自的编码参数，所以，可以有不同的串长度和参数的取值范围。6.2.3群体设定1.初始种群的产生

遗传算法中初始群体中的个体可以是随机产生的，但最好采用如下策略设定：①根据问题固有知识，设法把握最优解所占空间在整个问题空间中的分布范围，然后，在此分布范围内设定初始群体。②先随机产生一定数目的个体，然后从中挑选最好的个体加入初始群体中。这种过程不断迭代，直到初始群体中个体数目达到了预先确定的规模。6.2.3群体设定

6.2.4适应度函数

6.2.4适应度函数

6.2.4适应度函数

6.2.5选择

1.个体选择概率分配方法

在遗传算法中，哪个个体被选择进行交叉是按照概率进行的。

适应度大的个体被选择的概率大，但不是说一定能够被选上。同样，适应度小的个体被选择的概率小，但也可能被选上。所以，首先要根据个体的适应度确定被选择的概率。6.2.5选择

6.2.5选择

1.个体选择概率分配方法(2）排序方法

排序方法(Rank-based-Model）是计算每个个体的适应度后，根据适应度大小顺序对群体中个体进行排序，然后把事先设计好的概率按排序分配给个体，作为各自的选择概率。

在排序方法中，选择概率仅仅取决于个体在种群中的序位，不是实际的适应度值。排在前面的个体有较多的被选择的机会。6.2.5选择

2.选择个体方法

选择操作是根据个体的选择概率确定哪些个体被选择进行交叉、变异等操作，基本的选择方法如下。（1）轮盘赌选择

轮盘赌选择（RouletteWheelSelection）策略在遗传算法中使用得最多。

在轮盘赌选择方法中先按个体的选择概率产生一个轮盘，轮盘每个区的角度与个体的选择概率成比例，然后产生一个随机数，它落入转盘的哪个区域就选择相应的个体交叉。6.2.5选择(3）最佳个体保存方法

最佳个体保存方法或称为精英选拔方法（ElitistModel）是把群体中适应度最高的一个或者多个个体不进行交叉而直接复制到下一代中，保证遗传算法终止时得到的最后结果一定是历代出现过的最高适应度的个体。

使用这种方法能够明显提高遗传算法的收敛速度，但可能使种群过快收敛，从而只找到局部最优解。

保留种群个体总数的2%~5%的适应度最高的个体，效果最为理想。在使用其他选择方法时，一般都同时使用最佳个体保存方法，以保证不会丢失最优个体。6.2.6交叉

当两个生物机体配对或者复制时，它们的染色体相互混合，产生一对由双方基因组成的新的染色体。这一过程称为交叉（Crossover）或者重组（Recombination）。

交叉得到的后代可能继承了上代的优良基因，其后代会比它们的父母更加优秀，但也可能继承了上代的不良基因，其后代则会比它们的父母差，难以生存，甚至不能再复制自己。

越能适应环境的后代越能继续复制自己并将其基因传给后代。由此形成一种趋势：每一代总是比其父母一代生存和复制得更好。6.2.6交叉1.基本的交叉算子（1）一点交叉

一点交叉（Single-pointCrossover）又称为简单交叉。

在个体串中随机设定一个交叉点，实行交叉时，该点前或后的两个个体的部分结构进行互换，并生成两个新的个体。（2）二点交叉

二点交叉(Two-pointCrossover）的操作与一点交叉类似，只是设置了两个交叉点(仍然是随机设定），将两个交叉点之间的码串相互交换。

类似于二点交叉，可以采用多点交叉（Multiple-pointCrossover）。6.2.6交叉2.修正的交叉方法

对交叉、变异等遗传操作进行适当地修正，使其满足优化问题的约束条件。

例如，在TSP问题中采用部分匹配交叉（PartiallyMatchedCrossover，PMX），顺序交叉（OrderCrossover，OX）和循环交叉（Cyclecrossover，CX）等。这些方法对于其他一些问题也同样适用。6.2.7变异

6.2.7变异

6.2.8遗传算法的步骤

6.3遗传算法的应用

6.4群智能算法

由简单个体组成的群落与环境以及个体之间的互动行为，称为群体智能。受动物群体智能启发的算法称为群智能（SwarmIntelligence，SI）算法。

群智能算法包括：粒子群优化算法、蚁群算法和人工免疫算法。

粒子群优化算法起源于对简单社会系统的模拟。最初设想是用粒子群优化算法模拟鸟群觅食的过程，但后来发现它是一种很好的优化工具。

蚁群算法是对蚂蚁群采集食物过程的模拟，已经成功地运用在很多离散优化问题上。6.4.1粒子群优化算法

6.4.1粒子群优化算法

6.4.1粒子群优化算法

6.4.2蚁群算法1蚁群算法基本模型

蚁群优化算法的第一个应用是著名的旅行商问题（TSP），Dorigo等人充分利用了蚁群搜索食物的过程与旅行商问题之间的相似性通过人工模拟蚂蚁搜索食物的过程。

通过个体之间的信息交流与相互协作最终找到从蚁穴到食物源的最短路径，来求解旅行商问题。6.4.2蚁群算法

6.4.2蚁群算法

6.4.2蚁群算法

6.4.2蚁群算法蚁群算法求解旅行商问题

6.4.2蚁群算法蚁群算法求解旅行商问题

6.4.2蚁群算法蚁群算法求解旅行商问题的解：

6.5小结

遗传算法主要借用生物进化中“适者生存”的规律。遗传算法的设计包括编码、适应度函数选择、控制参数、交叉与变异等