人工智能及其应用chapter6_071103课件

1、6.1 遗传算法及其数学基础标准遗传算法及基本术语 模式定理人工智能及其应用1标准遗传算法及基本术语标准遗传算法基本流程：参数编码初始群体设定适应度函数的设计遗传操作: 选择、交叉、变异控制参数设定进化停止准则 人工智能及其应用2模式定理模式 基于三值字符集0,1,*所产生的可描述某种结构相似性的字符串称为模式。模式是描述个体字符串集的模板。模式的阶 模式H中确定位置（位）的个数称为该模式的阶，记为O(H)。 模式的定义距 模式H中第一个确定位置和最后一个确定位置之间的距离称为该模式的定义距，记为 。人工智能及其应用3模式定理选择操作对模式的影响 交叉操作对模式的影响变异操作对模式的影响人工智

2、能及其应用4模式定理经选择、交叉、变异操作后,子代中模式H的数目为： 模式定理： 在遗传算子选择、交叉和变异的作用下，具有低阶、短定义距以及平均适应度高于群体平均适应度的模式，在子代中将以指数级增长。人工智能及其应用5模式定理积木块假设： 低阶、短距、高平均适应度的模式（积木块）在遗传算子的作用下相互结合，能生成高阶、长距、高平均适应度的模式，并最终生成全局最优解。 模式定理保证了较优模式的样本数呈指数级增长，从而满足了寻找最优解的必要条件，即遗传算法存在着寻找全局最优解的可能性。而积木块假设则指出，遗传算法具备寻找到全局最优解的能力，即积木块在遗传算子的作用下，能生成高阶、长距、高平均适应度

3、的模式，并最终生成全局最优解。人工智能及其应用66.2 遗传算法的设计 编码 初始群体设定 适应度函数选择算子交叉算子变异算子人工智能及其应用7编码二进制编码十进制编码Gray编码多参数映射编码可变长度染色体编码多维染色体编码人工智能及其应用8初始群体设定群体规模的确定:群体规模大个体多样性高陷入局部解的危险小。但是规模太大计算量加大。如果群体规模小遗传算法在搜索空间中的分布范围受限搜索过程可能提前停止于未成熟阶段(引起未成熟收敛) 必须保持群体的多样性。人工智能及其应用9初始群体设定初始群体的生成：遗传算法中，初始群体中的个体可以根据具体的编码方法、在尽可能满足群体多样性的前提下随机产生。先

4、随机生成一定数目的个体，然后从中挑选出性能优良的个体加入到群体中。重复该过程，直至满足群体规模。 人工智能及其应用10适应度函数将目标函数映射为适应度函数：如果待求解问题是使目标函数最小，则GA中可采用如下变换：当原目标函数是求最大化的利润或效用函数时，可以按照下式变换： 人工智能及其应用11适应度函数适应度调整： 线性调整 线性调整出现非负现象 人工智能及其应用12选择算子适应度比例法: 也称为轮盘赌法。群体中适应度值大的个体被选择的概率大，而适应度值低的个体被选择概率低。人工智能及其应用13选择算子最佳个体保存法(精英选择法): 群体中适应度最高的个体不经过遗传操作，直接复制到下一代群体中

5、群体中。排序选择方法: 根据适应度的大小对个体进行排序，然后把事先设计好的概率表分配给个体，作为各自的选择概率。 个体的选择概率与其适应度无直接关系，仅与其在群体中的排序相关。 人工智能及其应用14选择算子联赛选择方法: 从群体中任意选择一定数量的个体（称为联赛规模），将其中适应度最高的个体保存到下一代。反复执行该过程，直到保存到下一代的个体数目达到预先设定的数目为止。联赛规模一般取2。人工智能及其应用15交叉算子单点交叉多点交叉 人工智能及其应用16交叉算子一致交叉 通过屏蔽字来决定新个体对父辈个体基因位的继承。 屏蔽字可以随机生成，由于概率的因素，会使模式被破坏的机率增加。人工智能及其应用

6、17变异算子基本变异算子 对二值编码，随机选择c个基因位作为待变异位置，然后根据设定的变异概率pm 对这些基因位的值进行取反操作，即1变为0，0变为1。逆转变异算子 随机挑选两个逆转点，然后将两个逆转点之间的基因值按变异概率逆向排列。 人工智能及其应用18变异算子自适应变异算子 变异概率不固定，它随群体中个体的多样性自适应调整。群体多样性越大，变异概率越小；多样性越差，变异概率越大。 如：可根据交叉所得的两个新个体的Hamming距进行变异概率的调整，Hamming距越小，变异概率越大；Hamming距越大，变异概率越小。 人工智能及其应用196.3 改进的遗传算法 微种群算法 双种群算法 自

7、适应遗传算法人工智能及其应用20微种群算法算法步骤:(1) 在群体中随机选择n个个体组成微群体。(2) 计算适应度并确定最好的个体，直接遗传到下一代，保证优良的模式信息不致丢失。(3) 按照联赛选择策略确定其余个体。(4) 以概率1进行交叉运算，以加速产生确定位高的模式。这样处理之后可以保证有足够多的种类。(5) 检验收敛条件，如果收敛则转(1)；否则转至(2)。人工智能及其应用21双种群算法基本思想:用两个群体分工协作解决多模态函数寻优时的矛盾。 (1)全局种群，用于寻找可能存在最优解的区域； (2)局部种群，用于搜索全局种群划分的区域，找到 该区域中的最优解。两个种群的特点：全局搜索种群注

8、重搜索未知区域，要求被处理的信息多、处理速度快，但对精度要求不高，不能陷入局部最小点；局部种群注重搜索有局部最优解的区域，搜索范围较小，要求搜索速度快。人工智能及其应用22自适应遗传算法基本思想：当个体适应度趋于一致或局部最优时，增加交叉和变异概率；当群体个体适应度比较分散时，减少交叉和变异概率。对于适应度高于群体平均适应度值的个体，选择较低的交叉和变异概率；对于适应度低于群体平均适应度的个体，选择较高的交叉和变异概率。人工智能及其应用236.4 协进化算法 协进化算法基本流程代表个体的选择人工智能及其应用24协进化算法基本流程特点: 协进化算法包含多个群体，分别表示不同的物种，进化过程中各群

9、体间相互关联。协进化算法分为:协作型协进化竞争型协进化人工智能及其应用25协进化算法基本流程协进化算法流程协进化算法与传统的遗传算法基本相同。差异在于各群体中个体适应度的计算方法。人工智能及其应用26协进化算法基本流程协进化算法中个体适应度的计算：(1) 选择待评价群体P ；(2) 从其它群体中选择代表个体；(3) 对群体P中每个个体i，进行如下操作： 1) 将个体i与其它种群中挑选出的代表个体组合形成问题的解； 2) 根据定义的适应度函数计算组合解的适应度f ； 3) 将f 赋值给个体i 。(4) 判断是否所有群体均被评价，若是则结束；否则选择未评价的群体，转(1)。人工智能及其应用27代表个体的选择最优选择法方法：选择当前群体中适应度值最高的个体为代表个体。优点：进化效率比较高。缺点：容易陷入局部