《第三章遗传算法在优化中的应用精选PPT.ppt》由会员分享，可在线阅读，更多相关《第三章遗传算法在优化中的应用精选PPT.ppt（74页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第三章遗传算法在优化中的应用第1页，本讲稿共74页3.1 3.1 无约束优化无约束优化无约束优化是指在没有任何约束的前提下极大或极小化某个无约束优化是指在没有任何约束的前提下极大或极小化某个目标函数的问题。无约束优化问题可描述为：目标函数的问题。无约束优化问题可描述为：或或这里这里S S称为搜索空间，称为搜索空间，称为目标函数。称为目标函数。第2页，本讲稿共74页3.1 3.1 无约束优化无约束优化l定义定义3.1 3.1 对最小化问题，设对最小化问题，设 ，若存在，若存在 使得对任使得对任 且且 时，有时，有 则称则称 是是 在在S S上的一个局部最优解，而称上的一个局部最优解，而称 为一个
2、为一个局部最优值。局部最优值。l定义定义3.2 3.2 对最小化问题，设对最小化问题，设 ，若对任，若对任 有有 则称则称 是是 在在S S上的一个全局最优解，而称上的一个全局最优解，而称 为一个全局最为一个全局最优值。优值。第3页，本讲稿共74页 3.1 3.1 无约束优化无约束优化l考虑下面的考虑下面的Ackley函数优化问题：函数优化问题：l当当n=2n=2时时,目标函数的三维图形如下图所示。目标函数的三维图形如下图所示。第4页，本讲稿共74页3.1 3.1 无约束优化无约束优化第5页，本讲稿共74页 3.2 一个例子一个例子1个体的编码个体的编码 采用实数向量编码，每一个个体是一实数对
3、采用实数向量编码，每一个个体是一实数对 .2.适应函数：该优化问题是一个极小化问题，可对目标函数适应函数：该优化问题是一个极小化问题，可对目标函数作简单变换得到适应函数，譬如取作简单变换得到适应函数，譬如取3.选择策略：采用随机通用采样选择策略：采用随机通用采样.4.杂交算子：采用整体算术杂交杂交算子：采用整体算术杂交。给定两个父体，产生一个随机数，经杂交后得到两个后代给定两个父体，产生一个随机数，经杂交后得到两个后代个体个体第6页，本讲稿共74页 3.2 一个例子一个例子 ,产生一个随机数产生一个随机数 ，经杂交后得到，经杂交后得到两个后代个体两个后代个体 5.变异算子：采用非均匀变异。变异
4、算子：采用非均匀变异。6.参数设置：种群规模参数设置：种群规模 ，最大代数，最大代数 ，杂交，杂交概率概率 ，变异概率，变异概率 .7.初始化：随机产生初始种群。初始化：随机产生初始种群。8.终止条件：算法运行所指定的最大代数后终止。终止条件：算法运行所指定的最大代数后终止。第7页，本讲稿共74页3.3 3.3 约束优化约束优化l约束优化问题可描述为：约束优化问题可描述为：其中其中 都是定义在都是定义在 上的上的实函数，搜索空间为目标函数的定义域，通常为实函数，搜索空间为目标函数的定义域，通常为n维矩形：维矩形：。第8页，本讲稿共74页 3.3 3.3 约束优化约束优化l常用的约束处理技术。常
5、用的约束处理技术。1拒绝法拒绝法 拒绝法抛弃所有在演化过程中产生的不可行染色体。拒绝法抛弃所有在演化过程中产生的不可行染色体。2修复法修复法 修复法是通过一个修复程序对不可行个体进行修复，使之修复法是通过一个修复程序对不可行个体进行修复，使之成为可行个体。该方法在求解一些组合优化问题时经常使成为可行个体。该方法在求解一些组合优化问题时经常使用。用。第9页，本讲稿共74页3.3 3.3 约束优化约束优化l对对0-1背包问题，我们可以设计一个简单的修复程序。若背包问题，我们可以设计一个简单的修复程序。若 是一个不可行个体，即有是一个不可行个体，即有 ，其修复过程如下：，其修复过程如下：(1)将将
6、的物品按价值的物品按价值-重量比从大到小排序；重量比从大到小排序；(2)按上述次序选择物品，直到背包不能再装为止。按上述次序选择物品，直到背包不能再装为止。l修复后的个体可以只用作评估，也可以用来替代原个体进入修复后的个体可以只用作评估，也可以用来替代原个体进入种群。种群。第10页，本讲稿共74页3.3 3.3 约束优化约束优化3 3算子修正法算子修正法算子修正法是指设计专门的遗传算子来保持种群中个体的可行算子修正法是指设计专门的遗传算子来保持种群中个体的可行性。性。譬如对譬如对TSPTSP问题，若使用排列编码的话，则需要设计杂问题，若使用排列编码的话，则需要设计杂交算子和变异算子，使得排列经
7、过杂交算子或变异算子交算子和变异算子，使得排列经过杂交算子或变异算子的作用后仍然是排列。的作用后仍然是排列。4 4惩罚函数法惩罚函数法惩罚函数法是一种常用的处理约束条件的方法。本质上惩罚函数法是一种常用的处理约束条件的方法。本质上它是通过惩罚不可行解，将约束问题转化为无约束问题。它是通过惩罚不可行解，将约束问题转化为无约束问题。第11页，本讲稿共74页3.3 3.3 约束优化约束优化惩罚技术通过对目标函数加上一个惩罚项以构成一个广义目惩罚技术通过对目标函数加上一个惩罚项以构成一个广义目标函数的方式将约束优化问题转化为无约束优化问题，使得标函数的方式将约束优化问题转化为无约束优化问题，使得遗传算
8、法在惩罚项的作用下找到原问题的最优解。遗传算法在惩罚项的作用下找到原问题的最优解。广义目标函数具有如下形式：广义目标函数具有如下形式：其中其中 是目标函数，是目标函数，是惩罚函数。是惩罚函数。对于极小（极大）化问题，惩罚函数应具有这样的性质：对非对于极小（极大）化问题，惩罚函数应具有这样的性质：对非可行解可行解x有有 ，而对可行解，而对可行解x有有 ，即不，即不产生惩罚。产生惩罚。第12页，本讲稿共74页 3.3 3.3 约束优化约束优化 下面我们假定所讨论的问题是极小化问题下面我们假定所讨论的问题是极小化问题。对于形如对于形如 的约束条件，许多方法用函数的约束条件，许多方法用函数 来构造惩罚
9、函数，来构造惩罚函数，按照下面的方式度量对第按照下面的方式度量对第i个约束的违背程度：个约束的违背程度：第13页，本讲稿共74页3.3 3.3 约束优化约束优化(1)(1)静态惩罚函数静态惩罚函数 静态惩罚函数具有下列形式：静态惩罚函数具有下列形式：其中其中 是预先指定的常数，称为惩罚系数。是预先指定的常数，称为惩罚系数。d d是一个是一个常数，通常取常数，通常取d=1d=1或或2 2。第14页，本讲稿共74页3.3 3.3 约束优化约束优化l选择适当的惩罚系数并不是一件容易的事。选择适当的惩罚系数并不是一件容易的事。l若惩罚系数选择过大，则将会由于太注重解的可行性而较早地收若惩罚系数选择过大
10、，则将会由于太注重解的可行性而较早地收敛到某个局部最优解；若这些惩罚系数选择过小，则有可能使得敛到某个局部最优解；若这些惩罚系数选择过小，则有可能使得不可行解在种群中占统治地位，从而使算法花费过多的时间在非不可行解在种群中占统治地位，从而使算法花费过多的时间在非可行区域中搜索，而且有可能收敛到非可行域。可行区域中搜索，而且有可能收敛到非可行域。第15页，本讲稿共74页3.3 3.3 约束优化约束优化一一种种较较好好的的方方法法是是对对每每个个约约束束，根根据据该该约约束束的的违违反反程程度度来来确确定定惩惩罚罚系系数数。该该A.S.Homaifar等等提提出出了了一一种种基基于于这这种种思思想
11、想构构造造惩惩罚罚函函数数的的方方法法。其详细描述如下：其详细描述如下：l 对每个约束，确定对每个约束，确定 个区间个区间 以度量该约束的违反程度；以度量该约束的违反程度；l 对每个约束及违反程度，建立一个惩罚系数对每个约束及违反程度，建立一个惩罚系数 使得违反程度越高，惩罚系数越大；使得违反程度越高，惩罚系数越大；第16页，本讲稿共74页3.3 3.3 约束优化约束优化l 惩罚函数由下式给出：惩罚函数由下式给出：这里这里 由由 的偏离程度来决定。的偏离程度来决定。若若 ，则，则 。l 该方法的优点是简单、直接、易于实现。但该方法的性能在很大程该方法的优点是简单、直接、易于实现。但该方法的性能
12、在很大程度上依赖于惩罚系数度上依赖于惩罚系数 的选取。对具有的选取。对具有m个约束的问题，需要确定个个约束的问题，需要确定个 参数。即参数。即 个待确定区间的端点，个待确定区间的端点，个惩罚系数。个惩罚系数。第17页，本讲稿共74页3.3 3.3 约束优化约束优化 (2)动态惩罚函数动态惩罚函数 静态惩罚函数中的惩罚系数静态惩罚函数中的惩罚系数 是固定不变是固定不变 的。一的。一种替代的方法是使种替代的方法是使 随着演化代数的变化而变化。随着演化代数的变化而变化。Joines和和Houck提出了如下形式的动态惩罚函数：提出了如下形式的动态惩罚函数：其中其中t为当前演化代数，为当前演化代数，都为
13、正常数，通常取都为正常数，通常取 。第18页，本讲稿共74页3.3 3.3 约束优化约束优化(3)自适应惩罚函数自适应惩罚函数 自适应惩罚函数的目的是希望利用演化搜索中的反馈信息自适应地自适应惩罚函数的目的是希望利用演化搜索中的反馈信息自适应地调节惩罚系数，从而避免对惩罚系数的不恰当设置。调节惩罚系数，从而避免对惩罚系数的不恰当设置。由由BeanBean和和Hadj-AlouaneHadj-Alouane提出的一种自适应惩罚函数的形式提出的一种自适应惩罚函数的形式如下：如下：其中其中 与演化代数有关与演化代数有关.第19页，本讲稿共74页3.3 3.3 约束优化约束优化 譬如可取譬如可取 ，并
14、且在每一演化代按下列公式更新：，并且在每一演化代按下列公式更新：其中其中 表示在第表示在第i i代时上述广义目标函数值是最好的个代时上述广义目标函数值是最好的个体，体，且，且 以避免循环，以避免循环，k k是一个正常数。是一个正常数。第20页，本讲稿共74页3.4应用实例应用实例l例例3.1 3.1 考虑下列优化问题：考虑下列优化问题：l该问题是一个约束优化问题，用静态惩罚函数来处理约束。该问题是一个约束优化问题，用静态惩罚函数来处理约束。第21页，本讲稿共74页3.4应用实例应用实例l对于约束条件对于约束条件 ，将违反约束的程度划分为四个等级，将违反约束的程度划分为四个等级，不同的等级采用不
15、同的惩罚系数不同的等级采用不同的惩罚系数 ，具体如下：，具体如下：第22页，本讲稿共74页3.4应用实例应用实例l对于约束条件对于约束条件 ，将违反约束的程度划分为四个等级，不，将违反约束的程度划分为四个等级，不同的等级采用不同的惩罚系数同的等级采用不同的惩罚系数 ，具体如下：，具体如下：l惩罚函数为惩罚函数为l广义目标函数定义为广义目标函数定义为 第23页，本讲稿共74页3.4应用实例应用实例l遗传算法设计如下：遗传算法设计如下：(1)(1)编码：采用实数向量编码；编码：采用实数向量编码；(2)(2)适应函数：适应函数取为适应函数：适应函数取为 (3)(3)选择策略：采用随机通用采样；选择策
16、略：采用随机通用采样；(4)(4)杂交算子：采用整体算术杂交；杂交算子：采用整体算术杂交；(5)(5)变异算子：采用非均匀变异；变异算子：采用非均匀变异；第24页，本讲稿共74页3.4应用实例应用实例 (6)(6)控制参数的确定：种群规模控制参数的确定：种群规模 ，最大代数，最大代数 ，杂交概率，杂交概率 ，变异概率，变异概率 ；(7)(7)初始化：随机产生初始种群；初始化：随机产生初始种群；(8)(8)终止条件：算法运行所指定的最大代数后终止。终止条件：算法运行所指定的最大代数后终止。第25页，本讲稿共74页3.4应用实例应用实例实验结果 项目参考解遗传算法的解GRG的解第26页，本讲稿共7
17、4页3.4应用实例应用实例l例例3.2 3.2 考虑下列优化问题考虑下列优化问题 该问题有该问题有5 5个自变量，个自变量，6 6个非线性约束和个非线性约束和1010个上下界约束。注个上下界约束。注意，意，x x2 2和和x x4 4未显式地包含在目标函数里。未显式地包含在目标函数里。第27页，本讲稿共74页3.4应用实例应用实例l用动态惩罚函数对约束进行处理。令用动态惩罚函数对约束进行处理。令 惩罚函数定义为惩罚函数定义为其中其中C=2C=2，t t为演化代数，为演化代数，的定义如下：的定义如下：第28页，本讲稿共74页3.4应用实例应用实例第29页，本讲稿共74页3.4应用实例应用实例l广
18、义目标函数定义为广义目标函数定义为 l极小化极小化 的遗传算法设计如下：的遗传算法设计如下：(1)(1)编码：实数向量编码编码：实数向量编码 (2)(2)适应函数：适应函数取为适应函数：适应函数取为 (3)(3)选择策略：锦标赛选择，竞争规模选择策略：锦标赛选择，竞争规模k=2k=2，每次选择适应值较，每次选择适应值较小的个体小的个体 第30页，本讲稿共74页3.4应用实例应用实例 (4)(4)杂交算子：整体算术杂交杂交算子：整体算术杂交 (5)(5)变异算子：非均匀变异变异算子：非均匀变异 (6)(6)控制参数的确定：种群规模控制参数的确定：种群规模 ，最大代数，最大代数 ，杂交概率，杂交概
19、率 ，变异概率，变异概率 (7)(7)初始化：随机产生满足变量上下界要求的初始种群初始化：随机产生满足变量上下界要求的初始种群.(8)(8)终止条件：算法运行所指定的最大代数后终止终止条件：算法运行所指定的最大代数后终止.第31页，本讲稿共74页3.4应用实例应用实例l实验结果实验结果 项目项目参考解参考解遗传算法的解遗传算法的解GRG的解的解第32页，本讲稿共74页3.5 组合优化组合优化l度约束最小生成树问题度约束最小生成树问题 设设 是赋权连通无向图，其中是赋权连通无向图，其中 是顶点的是顶点的集合，集合，是边的集合，是边的集合，W是一个从是一个从E E到实数到实数集合上的函数，边集合上
20、的函数，边 的权值记为的权值记为 。若。若T是是G的生成树，的生成树，T中边中边的权之和定义为的权之和定义为T的权，记为的权，记为 。所有生成树中具有。所有生成树中具有最小权的生成树称为最小权的生成树称为 最小生成树。最小生成树。第33页，本讲稿共74页3.3 组合优化组合优化l求解最小生成树问题的算法有求解最小生成树问题的算法有Prim算法和算法和Kruskal算法算法.l在一些实际问题中，对生成树中顶点的度有一定在一些实际问题中，对生成树中顶点的度有一定的限制。即在极小化生成树的权值时，往往要求的限制。即在极小化生成树的权值时，往往要求顶点的度顶点的度 不大于一个给定的值不大于一个给定的值
21、 。度约束最小生成树问题就是求满足给定度约束的度约束最小生成树问题就是求满足给定度约束的最小生成树。最小生成树。第34页，本讲稿共74页3.3 组合优化组合优化l下面讨论用遗传算法求解度约束最小生成树问题。为简单下面讨论用遗传算法求解度约束最小生成树问题。为简单起见，假定图是完全图且由权值矩阵起见，假定图是完全图且由权值矩阵 给出，并假给出，并假设设 ，其中，其中d d是一个常数。是一个常数。(1)(1)编码编码 图论中的一个经典定理是图论中的一个经典定理是Cayley定理，即定理，即n n个顶点的完全图中有个顶点的完全图中有 棵不同的生成树。该定理的一种证明方法是在生成树和长度为棵不同的生成
22、树。该定理的一种证明方法是在生成树和长度为 的序列的序列 之间建立一一对应关系，其中之间建立一一对应关系，其中 为整数且有为整数且有 。由此知一棵生成树可以用一个长度为。由此知一棵生成树可以用一个长度为 的序列的序列 编码。编码。第35页，本讲稿共74页3.3 组合优化组合优化l编码过程如下：设生成树编码过程如下：设生成树T T中具有最小标号的叶结点为中具有最小标号的叶结点为 ，其相，其相邻结点记为邻结点记为 ，移去顶点，移去顶点 和边和边 ；在剩下的个顶点中再；在剩下的个顶点中再寻找标号最小的叶结点，设其为寻找标号最小的叶结点，设其为 ，其相邻结点记为，其相邻结点记为 ，移去，移去顶点顶点
23、和边和边 ；这样继续下去，直到剩下最后一条边为止。；这样继续下去，直到剩下最后一条边为止。这样便可得到序列这样便可得到序列 。l反之，给定序列反之，给定序列 ，可以唯一地构造一棵生成树。，可以唯一地构造一棵生成树。第36页，本讲稿共74页3.3 组合优化组合优化l译码过程如下：从序列译码过程如下：从序列 中找出第一个不在序列中找出第一个不在序列 中的数，记为中的数，记为 ，构造边，构造边 ，从序列，从序列A A中删除中删除 ，从序，从序列列B B中删除中删除 ，然后重复上述过程，直到序列，然后重复上述过程，直到序列B B为空。这时再为空。这时再从序列从序列A A中剩余的两个顶点中剩余的两个顶点
24、 ,构造边构造边 ，由这，由这 条边便得到一棵数条边便得到一棵数T T。第37页，本讲稿共74页3.3 组合优化组合优化l例如例如 给定下列生成树给定下列生成树 可得序列可得序列 ，反之亦然。，反之亦然。3725461第38页，本讲稿共74页3.3 组合优化组合优化 (2)(2)适应函数适应函数 由于该问题是极小值问题，适应函数可取为由于该问题是极小值问题，适应函数可取为 其中其中c c是一个常数，是一个常数，为生成树为生成树T T的权值。的权值。(3)(3)选择策略选择策略 采用轮盘赌选择。采用轮盘赌选择。第39页，本讲稿共74页3.3 组合优化组合优化 (4)(4)遗传算子遗传算子 杂交算
25、子采用类似于二进制编码的单点杂交。变异算子如下对杂交算子采用类似于二进制编码的单点杂交。变异算子如下对个体个体 进行变异：首先选一随机整数进行变异：首先选一随机整数 ，然后，然后产生后代产生后代 ，其中，其中 是是 中的一个随机整数。中的一个随机整数。l显然杂交算子和变异算子作用后所得的个体仍代表生成树。显然杂交算子和变异算子作用后所得的个体仍代表生成树。第40页，本讲稿共74页3.3 组合优化组合优化 (5)(5)修复策略修复策略 由于存在度的约束，无论是初始种群中随机产生的个体，还是由于存在度的约束，无论是初始种群中随机产生的个体，还是经遗传算子作用后所得的个体都有可能不满足度的约束。为此
26、，经遗传算子作用后所得的个体都有可能不满足度的约束。为此，使用一个修复程序使得度约束条件能够得到满足。使用一个修复程序使得度约束条件能够得到满足。修复程序如下工作：若个体修复程序如下工作：若个体B B中的一个顶点中的一个顶点v v违反度的约束，违反度的约束，即即v v在在B B中出现的次数大于中出现的次数大于 ，则将多余的，则将多余的v v随机地替换为随机地替换为其它出现次数小于其它出现次数小于 的顶点就可以使该顶点满足度约束条的顶点就可以使该顶点满足度约束条件。件。第41页，本讲稿共74页3.3 组合优化组合优化 例如例如 在一个在一个9 9顶点完全图中，若顶点完全图中，若 ，即要求最小生成
27、树中每个顶，即要求最小生成树中每个顶点的度至多为点的度至多为3 3，则个体，则个体 中的顶点中的顶点6 6不满足度的约束，不满足度的约束，因为因为6 6出现了出现了3 3次。若将多余的一个次。若将多余的一个6 6随机地替换为顶点随机地替换为顶点3 3，则得到，则得到 ，该个体满足度约束条件。，该个体满足度约束条件。第42页，本讲稿共74页3.3 组合优化组合优化 (6)(6)控制参数控制参数 种群规模种群规模 ，最大代数，最大代数 ，杂交概率，杂交概率 ，变异概率，变异概率 。(7)(7)初始化：随机产生初始种群，并用修复程序对不满足度约初始化：随机产生初始种群，并用修复程序对不满足度约束的个
28、体进行修复。束的个体进行修复。(8)(8)终止条件：算法运行所指定的最大代数后终止。终止条件：算法运行所指定的最大代数后终止。第43页，本讲稿共74页求解度约束最小生成树问题的遗传算法求解度约束最小生成树问题的遗传算法 第44页，本讲稿共74页3.3 组合优化组合优化l旅行商问题旅行商问题 旅行商问题（旅行商问题（TSPTSP）是组合优化中研究最多的问题之一。该）是组合优化中研究最多的问题之一。该问题的叙述如下：一个商人欲从自己所在的城市出发，到问题的叙述如下：一个商人欲从自己所在的城市出发，到若干个城市推销商品，然后回到其所在的城市。如何选择若干个城市推销商品，然后回到其所在的城市。如何选择
29、一条周游路线使得商人经过每个城市一次且仅一次后回到一条周游路线使得商人经过每个城市一次且仅一次后回到起点且使他所走过的路径最短？起点且使他所走过的路径最短？第45页，本讲稿共74页3.3 组合优化组合优化l假定城市的集合为假定城市的集合为 ，城市之间的距离由一个，城市之间的距离由一个 的距离矩阵的距离矩阵 给出，其中给出，其中 表示城市表示城市i i与与j j之间的距之间的距离。离。l旅行商问题是要求一条周游路线旅行商问题是要求一条周游路线 使得使得 最小。其中最小。其中 为为1,2,n1,2,n的一个全排列。的一个全排列。第46页，本讲稿共74页3.3 组合优化组合优化l即即TSPTSP可以
30、描述为下列最优化问题：可以描述为下列最优化问题：l其中其中 为为1,2,n1,2,n的一个全排列。的一个全排列。第47页，本讲稿共74页3.3 组合优化组合优化l用遗传算法求解用遗传算法求解TSPTSP时，适应函数可以取为目标函数或目标函数时，适应函数可以取为目标函数或目标函数的一个简单变换，选择策略可用前面讨论过的某种选择策略，譬的一个简单变换，选择策略可用前面讨论过的某种选择策略，譬如轮盘赌选择，所以算法设计的重点主要集中在以下三个方面：如轮盘赌选择，所以算法设计的重点主要集中在以下三个方面：(1)(1)采用适当的方法对周游路线编码；采用适当的方法对周游路线编码；(2)(2)设计专门的遗传
31、算子，以避免不可行性；设计专门的遗传算子，以避免不可行性；(3)(3)防止过早收敛。防止过早收敛。l下面我们讨论周游路线常用的几种表示及其相应的遗传算子。下面我们讨论周游路线常用的几种表示及其相应的遗传算子。第48页，本讲稿共74页3.3 组合优化组合优化 1 1近邻表示近邻表示 近邻表示将一条周游路线表示成近邻表示将一条周游路线表示成n n个城市的一个排列个城市的一个排列 ，当且仅当周游路线中从城市当且仅当周游路线中从城市i i到达到达的下一个城市为城市的下一个城市为城市j j。例如，排列例如，排列 表示周游路线表示周游路线 。第49页，本讲稿共74页3.3 组合优化组合优化l显然，每一条周
32、游路线唯一地对应一个近邻表示，但任一显然，每一条周游路线唯一地对应一个近邻表示，但任一近邻排列却不一定都对应于合法周游路线。近邻排列却不一定都对应于合法周游路线。l例如，排列例如，排列 导致了不完全回路导致了不完全回路 ，因而无法对应一条周游路线。，因而无法对应一条周游路线。第50页，本讲稿共74页3.3 组合优化组合优化l几种为近邻表示而设计的杂交算子几种为近邻表示而设计的杂交算子 (1)(1)交替边杂交交替边杂交(alternating-edges crossover)：这种算子：这种算子产生后代时，首先从第一个父体中随机地选取一条边，再产生后代时，首先从第一个父体中随机地选取一条边，再从
33、第二个父体中选取一条适当的边，如此交替进行，使得从第二个父体中选取一条适当的边，如此交替进行，使得所选择的边扩展成一条合法的回路。若从某父体所选择的所选择的边扩展成一条合法的回路。若从某父体所选择的边导致当前路径构成一条子回路边导致当前路径构成一条子回路(即不包含所有顶点的回路即不包含所有顶点的回路)，则从不构成子回路的剩余边中随机地选择一条边。，则从不构成子回路的剩余边中随机地选择一条边。第51页，本讲稿共74页3.3 组合优化组合优化l例如，给定下列两个父体例如，给定下列两个父体 则一个可能的后代为则一个可能的后代为第52页，本讲稿共74页3.3 组合优化组合优化 (2)(2)子回路块杂交
34、：该杂交算子与交替边杂交类似，所不同的子回路块杂交：该杂交算子与交替边杂交类似，所不同的是，不是每次交替地从一个父体中选择一条边，而是选择一是，不是每次交替地从一个父体中选择一条边，而是选择一条随机长度的子路径。同样地，若来自某一父体的边导致当条随机长度的子路径。同样地，若来自某一父体的边导致当前路径构成子回路，则从不构成子回路的剩余边中随机地选前路径构成子回路，则从不构成子回路的剩余边中随机地选择一条边。择一条边。(3)(3)启发式杂交：该杂交算子首先随机地选择一个城市作启发式杂交：该杂交算子首先随机地选择一个城市作为起始点，再比较两父体中与该城市相连的几条边，选择为起始点，再比较两父体中与
35、该城市相连的几条边，选择其中最短的边，并将所选择边的另一端作为新的起始点。其中最短的边，并将所选择边的另一端作为新的起始点。如此反复进行，直到产生一条合法的回路。如果选择的边如此反复进行，直到产生一条合法的回路。如果选择的边导致一条子回路，则从不构成子回路的剩余边中随机地选导致一条子回路，则从不构成子回路的剩余边中随机地选择一条边。择一条边。第53页，本讲稿共74页3.3 组合优化组合优化l近邻表示的优点之一是比较适合模式分析。缺点是操作比较复杂，近邻表示的优点之一是比较适合模式分析。缺点是操作比较复杂，且遗传算子常常会破坏好的路径，所导致算法的性能较差。且遗传算子常常会破坏好的路径，所导致算
36、法的性能较差。第54页，本讲稿共74页3.3 组合优化组合优化 2 2次序表示次序表示 次序表示是取次序表示是取n n个城市的某个排列个城市的某个排列 作为参照排列，作为参照排列，通常取通常取 作为参照排列，然后将周游路线中的城市按作为参照排列，然后将周游路线中的城市按照其在参照排列中的次序记录下来，形成一个具有照其在参照排列中的次序记录下来，形成一个具有n n个元素的个元素的有序表。有序表。l例如，若取例如，若取 作为参照排列，那么路径作为参照排列，那么路径 的次序表示为的次序表示为 第55页，本讲稿共74页3.3 组合优化组合优化l一般一般,若路径若路径 的次序表示为的次序表示为 那么有那
37、么有l次序表示的主要优点是可以使用传统的杂交算子，即可以使次序表示的主要优点是可以使用传统的杂交算子，即可以使用类似于二进制表示的点式杂交。用类似于二进制表示的点式杂交。第56页，本讲稿共74页3.3 组合优化组合优化 3 3路径表示路径表示 路径表示也许是一条周游路线的最自然的表示。路径表示也许是一条周游路线的最自然的表示。例如一条周游路线例如一条周游路线 可表示为排列可表示为排列 这里将排列看成一个首尾相接的圆形排列。这里将排列看成一个首尾相接的圆形排列。第57页，本讲稿共74页3.3 组合优化组合优化l关于路径表示的杂交算子主要有：部分映射杂交关于路径表示的杂交算子主要有：部分映射杂交(
38、Partially Mapped Crossover,PMX)，次序杂交，次序杂交(Order Crossover，OX)，循环杂交，循环杂交(Cycle Crossover，CX)，基于位置杂交，基于位置杂交(Position-based Crossover，PX)等；变异算子主要包括倒位、插入、移等；变异算子主要包括倒位、插入、移位和互换等。位和互换等。第58页，本讲稿共74页3.3 组合优化组合优化l杂交算子杂交算子 (1)(1)部分映射杂交部分映射杂交 PMX杂交算子通过从一个父体中选择一个子序列，并尽可能杂交算子通过从一个父体中选择一个子序列，并尽可能多地保持另一个父体中城市的次序和
39、位置的方式产生后代。多地保持另一个父体中城市的次序和位置的方式产生后代。例例 给定下列两个父体给定下列两个父体,随机地选择两个杂交点随机地选择两个杂交点 将将 在这两点之间的中间段交换得在这两点之间的中间段交换得第59页，本讲稿共74页3.3 组合优化组合优化这里这里#表示待定城市。表示待定城市。这一交换所确定的部分映射为这一交换所确定的部分映射为再从各自父体中填入与中间段无冲突的城市得再从各自父体中填入与中间段无冲突的城市得第60页，本讲稿共74页3.3 组合优化组合优化l对对 中与中间段有冲突的中与中间段有冲突的#部分，执行部分映射，直到无冲突为部分，执行部分映射，直到无冲突为止。最后可得
40、：止。最后可得：第61页，本讲稿共74页3.3 组合优化组合优化 (2)(2)次序杂交次序杂交 OX杂交算子通过从一个父体中选择一个子序列，并保持另一个杂交算子通过从一个父体中选择一个子序列，并保持另一个父体中城市的相对次序的方式产生后代。父体中城市的相对次序的方式产生后代。给定下列两个父体，随机地选择两个杂交点给定下列两个父体，随机地选择两个杂交点 保留保留 上两个杂交点之间的中间段得上两个杂交点之间的中间段得第62页，本讲稿共74页3.3 组合优化组合优化 这里这里#表示待定城市。表示待定城市。从第二个杂交点开始，将从第二个杂交点开始，将 中的城市按原次序列出得中的城市按原次序列出得 从中
41、删除中间段中的城市的得从中删除中间段中的城市的得第63页，本讲稿共74页3.3 组合优化组合优化 将该子序列从第二个杂交点开始依次填入到将该子序列从第二个杂交点开始依次填入到 中得中得 类似地可得类似地可得第64页，本讲稿共74页3.3 组合优化组合优化 (3)(3)循环杂交循环杂交 CX杂交算子如下产生后代：后代中的每一个城市是某个父体相杂交算子如下产生后代：后代中的每一个城市是某个父体相应位置的城市。应位置的城市。给定下列两个父体给定下列两个父体 先从先从 中取第一个城市中取第一个城市2 2作为的作为的 第一个城市得第一个城市得第65页，本讲稿共74页3.3 组合优化组合优化l 中城市中城
42、市2 2对应对应 中的城市中的城市4 4，而，而4 4还没有填入到还没有填入到 中，将中，将4 4填入填入到到 中，位置与其在中，位置与其在 中的位置相同得中的位置相同得l 中城市中城市4 4所对应所对应 中城市中城市2 2，但，但2 2已经填入到已经填入到 中了，这完成了中了，这完成了一个循环。一个循环。l将将 中尚未在中尚未在 中出现的城市直接填入到中出现的城市直接填入到 中相应的位置中相应的位置后得后得第66页，本讲稿共74页3.3 组合优化组合优化l类似地可以得到类似地可以得到第67页，本讲稿共74页3.3 组合优化组合优化 (4)(4)基于位置杂交基于位置杂交 PX类似于次序杂交，唯
43、一的区别在于：在类似于次序杂交，唯一的区别在于：在PX中，不是选取父中，不是选取父体的一个连续的子序列，而是随机地选取一些位置，再按次序杂交的体的一个连续的子序列，而是随机地选取一些位置，再按次序杂交的方式产生后代。方式产生后代。l 给定下列两个父体给定下列两个父体 假定随机地选取的位置为假定随机地选取的位置为2 2，3 3，6 6，8 8。第68页，本讲稿共74页3.3 组合优化组合优化l保留保留 上在这些位置上的城市得上在这些位置上的城市得 l从最后一个选取位置的后面开始，将从最后一个选取位置的后面开始，将 中的城市按原次序列出得中的城市按原次序列出得l从中删除从中删除 中已选取的城市得中
44、已选取的城市得第69页，本讲稿共74页3.3 组合优化组合优化l将该子序列从最后一个选取位置的后面开始依次填入到将该子序列从最后一个选取位置的后面开始依次填入到 中得中得l类似地可得类似地可得第70页，本讲稿共74页3.3 组合优化组合优化l变异算子变异算子 (1)(1)倒位变异倒位变异 倒位变异的过程如下：首先在父体上随机地选择两个城市，然后倒位变异的过程如下：首先在父体上随机地选择两个城市，然后将这两个城市之间的子序列反转。将这两个城市之间的子序列反转。l设有父体设有父体 l假定随机地选择的两个城市为假定随机地选择的两个城市为3 3，7 7，则对该个体进行倒位变异，则对该个体进行倒位变异后
45、得后得 第71页，本讲稿共74页3.3 组合优化组合优化 (2)(2)插入变异插入变异 插入变异的过程如下：首先在父体中随机地选择一个城市，插入变异的过程如下：首先在父体中随机地选择一个城市，然后将该城市插入到某个随机的位置上。然后将该城市插入到某个随机的位置上。l设有父体设有父体 l假定随机地选择的城市为假定随机地选择的城市为2 2，随机地选择位置为，随机地选择位置为6 6，那么将，那么将城市城市2 2插入到第插入到第6 6个位置上得个位置上得第72页，本讲稿共74页3.3 组合优化组合优化 (3)(3)互换变异互换变异 互换变异随机地选择两个城市，并将这两个城市互换。互换变异随机地选择两个城市，并将这两个城市互换。l设有父体设有父体 l随机地选择的两个城市为随机地选择的两个城市为3 3，7 7，那么经互换变异后得，那么经互换变异后得 第73页，本讲稿共74页3.3 组合优化组合优化l产生随机排列的过程如下：产生随机排列的过程如下：从任一个排列从任一个排列 开始，开始，与从与从 中中随机地选择的一个元素交换，然后随机地选择的一个元素交换，然后 与从与从 中随机地选择的一个元素交换，这样继续下去，可得随机排列。中随机地选择的一个元素交换，这样继续下去，可得随机排列。第74页，本讲稿共74页