第三章遗传算法在优化中的应用精选文档.ppt

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