《智能计算》教学课件-第二章-遗传算法.ppt

第2章 遗传算法 武汉大学计算机学院 2.1 遗传算法的基本结构 在遗传算法中，在对规模为N的种群初始化和对种群中个体计算适应值后，按照基于个体适应值的某个概率函数选择N个父体，适应值较大的个体被选择作为父体的可能性较大。通过杂交，N个父体产生N个后代，N个后代以一定的概率进行变异，并都存活下来，形成下一代种群。在遗传算法中，杂交算子是一个主要的遗传算子，而以较小的概率对孩子进行变异。 2.1 遗传算法的基本结构 2.2 一个例子 考虑下面的优化问题： 目标函数的三维图形如下图所示。 2.2 一个例子 2.2 一个例子 1．个体的编码 问题的可能解为实数对 的形式。我们将问题的可能解编码为二进制位串。为此，首先将每个变量编码为二进制位串，然后将表示各个变量的二进制数串连接起来便得到问题可能解的一种表示。表示每个变量的二进制位串的长度取决于变量的定义域和所要求的精度。 设 ，所要求的精度为小数点后t位。这要求将区间划分为至少 份。假设表示变量 的位串的长度用 表示，则 可取为满足下列不等式的最小整数m： 2.2 一个例子 即有 将的二进制表示转换为十进制可按下式计算： 其中 表示变量 的二进制子串 对应的十制数。 2.2 一个例子 对于上面的优化问题，假定所要求的精度为小数点后4位，那么由 知，表示变量 的二进制位串的长度为 。 由 知，表示变量 的二进制位串的长度为 。 2.2 一个例子 表示问题解的二进制位串如下图所示: 其中前18位表示变量 ，后15位表示变量 。 2.2 一个例子 例如给定下列33位二进制位串 那么前18位所表示的变量 的值为： 2.2 一个例子 2.2 一个例子 2.2 一个例子 2.2 一个例子 3．计算适应值 在本例中，这是一个最大值问题，我们直接取目标函数 作为适应函数 。 计算一个染色体的适应值的过程由下面两步组成： (1) 将该染色体转换为所表示的问题可能解； (2) 计算个体的适应值。 2.2 一个例子 例如 2.2 一个例子 4．父体选择 采用轮盘赌选择(Roulette Wheel Selection)。轮盘赌选择是遗传算法中使用最多的选择策略之一。 轮盘赌选择模拟博彩游戏中的轮盘赌。 一个轮盘被划分为N个扇形，每个扇形 表示种群中的一个染色体，而每个扇 形的面积与它所表示的染色体的适应 值成正比。 2.2 一个例子 为了选择种群中的个体，设想有一个指针指向轮盘，转动轮盘，当轮盘停止后，指针所指向的染色体被选择。因此一个染色体的适应值越大，表示该染色体的扇形面积就越大，因此它被选择的可能性也就越大。 轮盘赌选择可以如下实现： (1)计算种群中所有染色体适应值之和： 2.2 一个例子 (2) 计算每个染色体的选择概率 (3) 计算每个染色体的累计概率 (4) 转动轮盘N次，从中选出N个染色体。 2.2 一个例子 选择过程可如下实现： 用[0,1]中的一个随机数r来模拟转动一次轮盘，轮盘停止转动后指针所指向的位置。若 ，这说明指针指向第一个扇形，这时选择第一个染色体 ，一般若 ，这说明指针指向第k个扇形，这时选择第k个染色体。 2.2 一个例子 若种群中各染色体的累计概率如下： 现在转动圆盘20次，每一次选择一个染色体。假定所产生[0,1]中的20个随机数为 2.2 一个例子 第一个随机数=0.513870比 大，但比 小，故所选择的第一个染色体为 ；第二个随机数=0.175741比 大，但比 小，故所选择的第二个染色体为 ；如此进行下去，所选择的20个染色体为： 2.2 一个例子 轮盘赌选择算法如下所示。 其中random生成[0,1]上的一个随机数。 2.2 一个例子 5．遗传算子 遗传算子有两种：杂交算子和变异算子。 杂交算子：使用单点杂交。该方法对两个父体进行杂交，杂交后产生两个后代个体。 单点杂交过程如下：设二进制位串的长度为L，随机地产生一个整数pos作为杂交点的位置, ，然后将两个父体在该杂交点右边的子串进行交换，生成两个后代个体。 2.2 一个例子 单点杂交的示意图。 2.2 一个例子 杂交算子的应用过程：从步骤4中产生的父体中，按一定的概率pc从中挑选出若干个染色体进行杂交。首先从[0