1、6.1 遗传算法及其数学基础标准遗传算法及基本术语 模式定理人工智能及其应用1标准遗传算法及基本术语标准遗传算法基本流程：标准遗传算法基本流程：n参数编码参数编码n初始群体设定初始群体设定n适应度函数的设计适应度函数的设计n遗传操作遗传操作:选择、交叉、变异选择、交叉、变异n控制参数设定控制参数设定n进化停止准则进化停止准则 问题分析及解的编码初始群体P(t)的设定，t=1计算群体中各个体适应度通过遗传操作存优去劣：选择、交叉、变异新群体P(t+1)满足进化停止准则？最优个体解码P(t)=P(t+1)t =t+1NY结束开始人工智能及其应用2模式定理n模式模式 基于三值字符集基于三值字符集0,
2、1,0,1,*所产生的可描述某种结构相所产生的可描述某种结构相似性的字符串称为模式。模式是描述个体字符串集的模似性的字符串称为模式。模式是描述个体字符串集的模板。板。n模式的阶模式的阶 模式模式H H中确定位置（位）的个数称为该模式的阶，记中确定位置（位）的个数称为该模式的阶，记为为O(H)O(H)。n模式的定义距模式的定义距 模式模式H H中第一个确定位置和最后一个确定位置之间的中第一个确定位置和最后一个确定位置之间的距离称为该模式的定义距，记为距离称为该模式的定义距，记为 。)(H人工智能及其应用3模式定理n选择操作对模式的影响选择操作对模式的影响 n交叉操作对模式的影响交叉操作对模式的影
3、响n变异操作对模式的影响变异操作对模式的影响jfHfntHmtHm/)(),()1,(fHftHmtHm/)(),()1,(mHOmsPHOPP)(1)1()()1/()(1lHPPcs人工智能及其应用4模式定理n经选择、交叉、变异操作后经选择、交叉、变异操作后,子代中模式子代中模式H的的数目为：数目为：)()1/()(1)/)(),()1,(mcPHOlHPfHftHmtHmn模式定理：模式定理：在遗传算子选择、交叉和变异的作用下，具有低在遗传算子选择、交叉和变异的作用下，具有低阶、短定义距以及平均适应度高于群体平均适应度的阶、短定义距以及平均适应度高于群体平均适应度的模式，在子代中将以指数
4、级增长。模式，在子代中将以指数级增长。人工智能及其应用5模式定理n积木块假设：积木块假设：低阶、短距、高平均适应度的模式（积木块）在遗传低阶、短距、高平均适应度的模式（积木块）在遗传算子的作用下相互结合，能生成高阶、长距、高平均适算子的作用下相互结合，能生成高阶、长距、高平均适应度的模式，并最终生成全局最优解。应度的模式，并最终生成全局最优解。模式定理保证了较优模式的样本数呈指数级增长，从模式定理保证了较优模式的样本数呈指数级增长，从而满足了寻找最优解的必要条件，即遗传算法存在着寻而满足了寻找最优解的必要条件，即遗传算法存在着寻找全局最优解的可能性。而积木块假设则指出，遗传算找全局最优解的可能
5、性。而积木块假设则指出，遗传算法具备寻找到全局最优解的能力，即积木块在遗传算子法具备寻找到全局最优解的能力，即积木块在遗传算子的作用下，能生成高阶、长距、高平均适应度的模式，的作用下，能生成高阶、长距、高平均适应度的模式，并最终生成全局最优解。并最终生成全局最优解。人工智能及其应用66.2 遗传算法的设计 编码 初始群体设定 适应度函数选择算子交叉算子变异算子人工智能及其应用7编码n二进制编码二进制编码n十进制编码十进制编码nGray编码编码n多参数映射编码多参数映射编码n可变长度染色体编码可变长度染色体编码n多维染色体编码多维染色体编码人工智能及其应用8初始群体设定n群体规模的确定群体规模的
6、确定:v群体规模群体规模大大个体多样性个体多样性高高陷入局部解的陷入局部解的危险小危险小。但是规模太大但是规模太大计算量加大。计算量加大。v如果群体规模如果群体规模小小遗传算法在搜索空间中的分布范围遗传算法在搜索空间中的分布范围受限受限搜索过程可能搜索过程可能提前停止提前停止于未成熟阶段于未成熟阶段(引起未引起未成熟收敛成熟收敛)必须保持群体的多样性。必须保持群体的多样性。人工智能及其应用9初始群体设定n初始群体的生成：初始群体的生成：v遗传算法中，初始群体中的个体可以根据具体的遗传算法中，初始群体中的个体可以根据具体的编码方法、在尽可能满足群体多样性的前提下随编码方法、在尽可能满足群体多样性
7、的前提下随机产生。机产生。v先随机生成一定数目的个体，然后从中挑选出性先随机生成一定数目的个体，然后从中挑选出性能优良的个体加入到群体中。重复该过程，直至能优良的个体加入到群体中。重复该过程，直至满足群体规模。满足群体规模。人工智能及其应用10适应度函数n将目标函数映射为适应度函数：将目标函数映射为适应度函数：v如果待求解问题是使目标函数最小，则如果待求解问题是使目标函数最小，则GA中可采中可采用如下变换：用如下变换：v当原目标函数是求最大化的利润或效用函数时，当原目标函数是求最大化的利润或效用函数时，可以按照下式变换：可以按照下式变换：elseCxgxgCxf,0)(),()(maxmaxe
8、lseCxuCxuxf,00)(,)()(minmin人工智能及其应用11适应度函数n适应度调整：适应度调整：线性调整线性调整 线性调整出现非负现象线性调整出现非负现象 0minfmaxfavgfmin favg favg2 f)(xf)(xf0minfmaxfavgfmin favg favg fC)(xf)(xf人工智能及其应用12选择算子n适应度比例法适应度比例法:也称为轮盘赌法。群体中适应度值大的个体被选择的也称为轮盘赌法。群体中适应度值大的个体被选择的概率大，而适应度值低的个体被选择概率低。概率大，而适应度值低的个体被选择概率低。njjisiffP1/14.4%49.2%5.5%30
9、.9%人工智能及其应用13选择算子n最佳个体保存法最佳个体保存法(精英选择法精英选择法):):群体中适应度最高的个体不经过遗传操作，直接复制群体中适应度最高的个体不经过遗传操作，直接复制到下一代群体中群体中。到下一代群体中群体中。n排序选择方法排序选择方法:根据适应度的大小对个体进行排序，然后把事先设计根据适应度的大小对个体进行排序，然后把事先设计好的概率表分配给个体，作为各自的选择概率。好的概率表分配给个体，作为各自的选择概率。个体的选择概率与其适应度无直接关系，仅与其在群个体的选择概率与其适应度无直接关系，仅与其在群体中的排序相关。体中的排序相关。人工智能及其应用14选择算子n联赛选择方法
10、联赛选择方法:从群体中任意选择一定数量的个体（称为联赛规从群体中任意选择一定数量的个体（称为联赛规模），将其中适应度最高的个体保存到下一代。反复模），将其中适应度最高的个体保存到下一代。反复执行该过程，直到保存到下一代的个体数目达到预先执行该过程，直到保存到下一代的个体数目达到预先设定的数目为止。联赛规模一般取设定的数目为止。联赛规模一般取2 2。人工智能及其应用15交叉算子n单点交叉单点交叉n多点交叉多点交叉 配对个体个体个体0 1 0 11 1 11 0 1 00 0 00 1 0 1 0 0 01 0 1 0 1 1 1新个体新个体AB AB交叉点配对个体个体个体1 0 0 11 1 1
11、0 0 1 10 0 00 1 0 0 0 1 1 1 1 11 0 1 1 0 0 1 0 0 0新个体新个体AB AB交叉点1交叉点20 1 01 0 1人工智能及其应用16交叉算子n一致交叉一致交叉 通过屏蔽字来决定新个体对父辈个体基因位的继承。通过屏蔽字来决定新个体对父辈个体基因位的继承。屏蔽字可以随机生成，由于概率的因素，会使模式被屏蔽字可以随机生成，由于概率的因素，会使模式被破坏的机率增加。破坏的机率增加。个体个体0 1 0 0 0 1 1 1 1 11 0 1 1 0 0 1 0 0 0新个体新个体AB AB屏蔽字1 1 0 0 0 0 1 1 0 11 0 0 0 0 1 1
12、0 1 00 1 1 1 0 0 1 1 0 1人工智能及其应用17变异算子n基本变异算子基本变异算子 对二值编码，随机选择对二值编码，随机选择c个基因位作为待变异位置，然个基因位作为待变异位置，然后根据设定的变异概率后根据设定的变异概率p pm m 对这些基因位的值进行取反操对这些基因位的值进行取反操作，即作，即1 1变为变为0 0，0 0变为变为1 1。n逆转变异算子逆转变异算子 随机挑选两个逆转点，然后将两个逆转点之间的基因随机挑选两个逆转点，然后将两个逆转点之间的基因值按变异概率逆向排列。值按变异概率逆向排列。个体1 1 0 1 0 01 1 10 1 0 0 0 1 0 1 1 1
13、1 1新个体A A逆转点1逆转点20 1 0人工智能及其应用18变异算子n自适应变异算子自适应变异算子 变异概率不固定，它随群体中个体的多样性自适应调变异概率不固定，它随群体中个体的多样性自适应调整。群体多样性越大，变异概率越小；多样性越差，变整。群体多样性越大，变异概率越小；多样性越差，变异概率越大。异概率越大。如：可根据交叉所得的两个新个体的如：可根据交叉所得的两个新个体的Hamming距进行距进行变异概率的调整，变异概率的调整，Hamming距越小，变异概率越大；距越小，变异概率越大；Hamming距越大，变异概率越小。距越大，变异概率越小。人工智能及其应用196.3 改进的遗传算法 微
14、种群算法双种群算法 自适应遗传算法人工智能及其应用20微种群算法n算法步骤算法步骤:(1)在群体中随机选择在群体中随机选择n n个个体组成微群体。个个体组成微群体。(2)计算适应度并确定最好的个体，直接遗传到下一代，计算适应度并确定最好的个体，直接遗传到下一代，保证优良的模式信息不致丢失。保证优良的模式信息不致丢失。(3)按照联赛选择策略确定其余个体。按照联赛选择策略确定其余个体。(4)以概率以概率1 1进行交叉运算，以加速产生确定位高的模式。进行交叉运算，以加速产生确定位高的模式。这样处理之后可以保证有足够多的种类。这样处理之后可以保证有足够多的种类。(5)检验收敛条件，如果收敛则转检验收敛
15、条件，如果收敛则转(1)；否则转至；否则转至(2)。人工智能及其应用21双种群算法n基本思想基本思想:用两个群体分工协作解决多模态函数寻优时的矛盾。用两个群体分工协作解决多模态函数寻优时的矛盾。(1)(1)全局种群，用于寻找可能存在最优解的区域；全局种群，用于寻找可能存在最优解的区域；(2)(2)局部种群，用于搜索全局种群划分的区域，找到局部种群，用于搜索全局种群划分的区域，找到 该该区域中的最优解。区域中的最优解。n两个种群的特点：两个种群的特点：v全局搜索种群注重搜索未知区域，要求被处理的信息全局搜索种群注重搜索未知区域，要求被处理的信息多、处理速度快，但对精度要求不高，不能陷入局部多、处
16、理速度快，但对精度要求不高，不能陷入局部最小点；最小点；v局部种群注重搜索有局部最优解的区域，搜索范围较局部种群注重搜索有局部最优解的区域，搜索范围较小，要求搜索速度快。小，要求搜索速度快。人工智能及其应用22自适应遗传算法n基本思想：基本思想：v当个体适应度趋于一致或局部最优时，增加交叉和变当个体适应度趋于一致或局部最优时，增加交叉和变异概率；异概率；v当群体个体适应度比较分散时，减少交叉和变异概率。当群体个体适应度比较分散时，减少交叉和变异概率。v对于适应度高于群体平均适应度值的个体，选择较低对于适应度高于群体平均适应度值的个体，选择较低的交叉和变异概率；的交叉和变异概率；v对于适应度低于
17、群体平均适应度的个体，选择较高的对于适应度低于群体平均适应度的个体，选择较高的交叉和变异概率。交叉和变异概率。人工智能及其应用236.4 协进化算法 协进化算法基本流程代表个体的选择人工智能及其应用24协进化算法基本流程n特点特点:协进化算法包含多个群体，分别表示不同的物种，协进化算法包含多个群体，分别表示不同的物种，进化过程中各群体间相互关联。进化过程中各群体间相互关联。n协进化算法分为协进化算法分为:v协作型协进化协作型协进化v竞争型协进化竞争型协进化人工智能及其应用25协进化算法基本流程n协进化算法流程协进化算法流程v协进化算法与传协进化算法与传统的遗传算法基统的遗传算法基本相同。本相同
18、。v差异在于各群体差异在于各群体中个体适应度的中个体适应度的计算方法。计算方法。初始化过程：1.设定群体个数 Smax 及个体编码方式；2.确定各群体的规模；3.进化代数 Gen=1。计算新个体其适应度值对选取的个体进行遗传操作（交叉、变异）i=1 由父代和子代个体共同组成新的群体YNi=i+1YNGen=Gen+1开 始根据协进化理论计算种群 i 中的个体适应度根据种群 i 中的个体适应度值进行选择操作i Smax?满足进化结束条件?结 束人工智能及其应用26协进化算法基本流程n协进化算法中个体适应度的计算：协进化算法中个体适应度的计算：(1)(1)选择待评价群体选择待评价群体P P；(2)
19、(2)从其它群体中选择代表个体；从其它群体中选择代表个体；(3)(3)对群体对群体P P中每个个体中每个个体i i，进行如下操作：，进行如下操作：1)1)将个体将个体i i与其它种群中挑选出的代表个体组合形成与其它种群中挑选出的代表个体组合形成问题的解；问题的解；2)2)根据定义的适应度函数计算组合解的适应度根据定义的适应度函数计算组合解的适应度f f；3)3)将将f f 赋值给个体赋值给个体i i 。(4)(4)判断是否所有群体均被评价，若是则结束；否则选择判断是否所有群体均被评价，若是则结束；否则选择未评价的群体，转未评价的群体，转(1)1)。人工智能及其应用27代表个体的选择n最优选择法
20、最优选择法v方法：方法：选择当前群体中适应度值最高的个体为代表选择当前群体中适应度值最高的个体为代表个体。个体。v优点：优点：进化效率比较高。进化效率比较高。v缺点：缺点：容易陷入局部解，而且可能无法搜索到全局容易陷入局部解，而且可能无法搜索到全局最优解。最优解。人工智能及其应用28代表个体的选择n随机选择法随机选择法 v方法方法:代表个体完全随机地从群体中选择。代表个体完全随机地从群体中选择。v分为分为:固定随机选择、不固定随机选择。固定随机选择、不固定随机选择。v优点：优点：可扩大搜索范围，保持个体的多样性，提可扩大搜索范围，保持个体的多样性，提供较多的搜索方向，避免进化过程陷于局部解。供较多的搜索方向，避免进化过程陷于局部解。v缺点：缺点：进化效率较低，不容易收敛。进化效率较低，不容易收敛。人工智能及其应用29
