《chapter3遗传算法》由会员分享，可在线阅读，更多相关《chapter3遗传算法（38页珍藏版）》请在金锄头文库上搜索。
1、游戏人工智能,遗传算法（Genetic Algorithm）,遗传算法定义（1/2）,遗传算法是从代表问题可能潜在的解集的一个种群（population）开始的，而一个种群则由经过基因（gene）编码的一定数目的个体(individual)组成。每个个体实际上是染色体(chromosome)带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现（即基因型）是某种基因组合，它决定了个体的形状的外部表现，如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。,遗传算法定义(2/2),因此，在一开始需要实现从表现型到基因型的映射即编码工作。由于仿照基因编码的工作很复杂，我们
2、往往进行简化，如二进制编码，初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代（generation）演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度（fitness）大小选择（selection）个体，并借助于自然遗传学的遗传算子（genetic operators）进行组合交叉（crossover）和变异（mutation），产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码（decoding），可以作为问题近似最优解。,遗传算法共同特征,遗传算法是解决搜索问题的一种通用算法，对于各种通用问题都可以使用。
3、搜索算法的共同特征为： 首先组成一组候选解； 依据某些适应性条件测算这些候选解的适应度； 根据适应度保留某些候选解，放弃其他候选解； 对保留的候选解进行某些操作，生成新的候选解。,遗传算法工作过程,首先，确定一种编码方法。将问题的任何一个潜在可行解能够编码表示成为一个“数字”染色体。 创建一个由随机的染色体（不同的候选解）组成的初始群体，并以强适应性为目的培育后代个体，进行进化。 进化过程中要加入少量变异。 直到找到解或者无法进化。,遗传算法结果,可能最终收敛到最优解 可能得到的不是最优解 也可能得不到解,遗传算法,1）检查每个染色体，看它解决问题的性能怎样，并相应的为它分配一个适应性分数。
4、2）从当前群体选出2个成员，选出的概率正比于染色体的适应性，适应分愈高，被选中的概率愈大。常用方法是赌轮选择法（roulette wheel selection） 3）按照预先设定的杂交率（crossover rate），从每个选中染色体一个随机确定的点上进行杂交（crossover） 4）按照预定的变异率（mutation rate），通过对被选染色体的位的循环，把相应的位实行翻转（flip） 5）重复2，3，4步，直到新的群体被创建出来。,算法说明：,把包含5步的一次循环称为一个世代或代（generation） 把整个循环称为一个时代（epoch） 可行解用二进制位进行编码。每个染色体是一
5、组随机的二进制位。二进制位长度在整个群体中一样。例如： 01110011010100001111 通过译码就代表当前问题的一个解。初始群体通常情况比较糟。,遗传算法的核心,选择： 根据各个个体的适应度，按照一定的规则或方法，从第t代群体P(t)中选择出一些优良的个体遗传到下 一代群体P(t+1)中； 交叉： 将群体P(t)内的各个个体随机搭配成对，对每一对个体，以某个概率(称为交叉概率）交换它们之间的部分染色体； 变异： 对群体P(t)中的每一个个体，以某一概率(称为变异概率)改变某一个或某一些基因座上的基因值为其他基因值。,赌轮选择法,染色体被选中的几率和它们的适应性分数成比例，适应性分数越
6、高的染色体，被选中的概率也越大。 但不保证适应性分数最高的染色体成员一定能选入下一代，仅说明它有最大的概率被选中。 全体成员的适应性分数由一张类似于赌博所用的转轮形状饼图来表示,每个染色体按适应性分数分得相应的一个扇区，适应性分数越高，所占区域面积越大。 旋转轮盘，并把一个小球抛入其中，直到轮盘停止时，看小球停在哪一部分，就选中它对应的那个染色体。,常用的选择方法,轮盘赌选择 随机竞争选择 最佳保留选择 无回放随机选择 确定式选择 无回放余数随机选择 均匀选择 最优保存策略 随机联赛选择 排挤选择。,杂交率（1/2）,杂交率就是用来确定两个染色体进行局部位的互换以产生两个新的子代的概率。 这一
7、数值经常取在0.7左右比较理想。当然，具体问题要具体分析。 每次从群体中选择两个染色体，同时生成0和1之间的一个随机数，然后根据此数据的值来确定两个染色体是否需要进行杂交。 如果数值低于杂交率（通常0.40.99），就进行杂交，否则不杂交。,杂交率（2/2）,杂交过程中，沿着染色体的长度随机选择一个位置，并把此位置之后的所有位进行互换。 11110001010011100101 10011101001111010011 假设随机选择的位置是12，则杂交后的结果为： 111100010100 11010011 100111010011 11100101,交叉算法,单点交叉 两点交叉 多点交叉 均
8、匀交叉 算术交叉。 交叉算法是产生新个体的主要算法，它决定了遗传算法的全局搜索能力。,变异率,变异率（突变率）：就是在一个染色体中将位实行翻转的几率。 翻转：0变1，1变0 这个值通常都是很低的。比如0.001 通常在0.00010.1 杂交之后，要从头到尾检查子代染色体的各个位，并按所规定的几率对其中某些位实行翻转（突变）。,变异前： 000001110000000010000 变异后： 000001110001000010000,变异点,变异的算法,适合于二进制编码和浮点数编码个体的几种变异算子 基本位变异 均匀变异 边界变异 非均匀变异 高斯近似变异 变异本身是一种随机算法，只是产生新个
9、体的辅助算法，它决定了遗传算法的局部搜索能力。,遗传算法的特点（1/3）,(1)遗传算法从问题解的串集开始嫂索，而不是从单个解开始。这是遗传算法与传统优化算法的极大区别。传统优化算法是从单个初始值迭代求最优解的；容易误入局部最优解。遗传算法从串集开始搜索，覆盖面大，利于全局择优。 (2)许多传统搜索算法都是单点搜索算法，容易陷入局部的最优解。遗传算法同时处理群体中的多个个体，即对搜索空间中的多个解进行评估，减少了陷入局部最优解的风险，同时算法本身易于实现并行化。,遗传算法的特点（2/3）,(3)遗传算法基本上不用搜索空间的知识或其它辅助信息，而仅用适应度函数值来评估个体，在此基础上进行遗传操作
10、。适应度函数不仅不受连续可微的约束，而且其定义域可以任意设定。这一特点使得遗传算法的应用范围大大扩展。 (4)遗传算法不是采用确定性规则，而是采用概率的变迁规则来指导他的搜索方向。,遗传算法的特点（3/3）,(5)具有自组织、自适应和自学习性。遗传算法利用进化过程获得的信息自行组织搜索时，硬度大的个体具有较高的生存概率，并获得更适应环境的基因结构。,遗传算法的应用（1/3）,函数优化。 函数优化是遗传算法的经典应用领域，也是遗传算法进行性能评价的常用算例，许多人构造出了各种各样复杂形式的测试函数：连续函数和离散函数、凸函数和凹函数、低维函数和高维函数、单峰函数和多峰函数等。对于一些非线性、多模
11、型、多目标的函数优化问题，用其它优化方法较难求解，而遗传算法可以方便的得到较好的结果。,遗传算法的应用（2/3）,组合优化 随着问题规模的增大，组合优化问题的搜索空间也急剧增大，有时在目前的计算上用枚举法很难求出最优解。对这类复杂的问题，人们已经意识到应把主要精力放在寻求满意解上，而遗传算法是寻求这种满意解的最佳工具之一。实践证明，遗传算法对于组合优化中的NP问题非常有效。例如遗传算法已经在求解旅行商问题、 背包问题、装箱问题、图形划分问题等方面得到成功的应用。,遗传算法的应用（3/3）,此外，GA也在生产调度问题、自动控制、机器人学、图象处理、人工生命、遗传编码和机器学习等方面获得了广泛的运
12、用。,遗传算法应用帮助Bob回家,问题：,这是一个寻找路径问题。 寻找路径问题是游戏人工智能的一块“神圣基石”，使用非常广泛。 问题：一个迷宫，左边有一个入口，右边有一个出口，并有一些障碍物散布在其中。假设有一个虚拟的人Bob，要他从入口到出口。帮助他寻找路径，并且避免与所有障碍物相碰撞。,迷宫图,迷宫的计算机表示：,用二维数组来存储迷宫。用0表示开放的空间，用1表示墙壁或障碍物，5为入口，8为出口。,迷宫的二维数组,为染色体编码（1/2）,Bob行动分为四个方向：东，南，西，北。 编码后的染色体代表这四个方向信息的一个字符串。,为染色体编码（2/2）,一个二进制字符串 11111001101
13、1101110010101 代表的基因就是： 11,11,10,01,10,11,10,11,10,01,01,01 译码为十进制： 3,3,2,1,2,3,2,3,2,1,1,1 代表的方向就是： 北,北,西,南,西,北,西,北,西,南,南,南,说明,初始，Bob置于迷宫的入口，然后依据染色体译出的方向一步步走。如果某个方向碰壁或遇到障碍物，忽略该指令继续执行下一条指令。 直到用完所有方向或Bob到达出口为止。 适应性度量：一个染色体的适应性要看它能让Bob走到离出口的远近程度。让好的来产生后代，期待它们的子孙中能有比这一次走的离出口更近一点。,适应性分数的计算：,Bob距离出口的距离。 D
14、iffX=abs（posX-EndX） DiffY=abs（posY-EndY） Diff=DiffX+DiffY+1 FitnessScores=1/Diff 如果Bob到达出口，DiffX+DiffY=0,参数说明,杂交率选为0.7（0.40.99） 变异率选为0.001（0.00010.1） 染色体长度为70：表示Bob最大可能移动数目为35步。 群体规模：140（10200之间选定） 赌轮选择法：在整个适应性分数范围内随机选取一个实数，通过循环以考察各个染色体，把它们适应性分数累加起来，直到累加和大于选取的实数值，选择该基因组。,函数优化示例,求下列一元函数的最大值：,x-1,2 ，求解结果精确到6位小数。,SGA对于本例的编码,由于区间长度为3，求解结果精确到6位小数，因此可将自变量定义区间划分为3106等份。又因为221 3106 222 ，所以本例的二进制编码长度至少需要22位，本例的编码过程实质上是将区间-1，2内对应的实数值转化为一个二进制串（b21b20b0）。,几个术语,基因型：1000101110110101000111,表现型：1.288967,编码,解码,个体（染色体）,基因,SGA的框图,
