再上一篇:6. 2  一个示例
上一篇:6. 3  为什么遗传算法会奏效?
主页
下一篇:6. 5  习题
再下一篇: 第 7 章  旅行商问题
文章列表

6. 4  其它遗传操作

《用于最优化的计算智能》 Nirwan Ansari Edwin Hou 著 李军 边肇祺 译 清华大学出版社

对于许多问题,二值符号串不能被用来表示解空间。例如,TSP 的一个旅程可以很自然地表示为一个n城市的排列,但二值符号串的交叉和突变操作不能用于其上。

一组称为重排操作的新的操作可用来处理这类表示问题[50][65]。它包括三种操作: 部分匹配交叉(PMX)、有序交叉(OX)、循环交叉(CX)。

一种排列的表示要求每个等位基因都要在符号串中出现但只出现一次。PMX 操作[65]要求选取两个截点以便确定一个匹配段。例如,假定旅程1和旅程2是两个10城市TSP 中的旅程,其中截点以‖表示:

旅程1= (J H D ‖ E F I‖GC B A)

旅程2= (H GE ‖ B CJ ‖I A D F)

根据旅程1和旅程2中两个截点之间的中间段给出的映射关系可得

旅程1′= (I H D ‖ B C J‖ GF E A)

旅程2′= (H GB ‖ E F I ‖ J A D C)

这是两个新的合法旅程。它们都包含有旧旅程的成分。

操作[122]通过找到两个符号串构成的循环而生成新的符号串。利用上例中

CX PMX操作用到的两个旅程,我们可以构成如下排列:

J H D E F I G CB A

H GE B C J I A D F

第一个新旅程通过首先选取旅程1中的第一个城市而构成

旅程1′= (J ? ? ? ? ? ? ? ? ?)

由于J 在排列中对应于H,我们可以将其加入旅程

旅程1′= (J H ? ? ? ? ? ? ? ?)

继续这一映射过程,H 对应于G,G对应于I,I 对应于第一个选中的城市J,从而完成了一个循环。这时,已经得到的部分旅程变为排列的一个循环

旅程1′= (J H ? ? ? I G ? ? ?)

其余的空位可由旅程2中相应位置上的城市填充。这样,新的旅程变为

旅程1′= (J H E B C I GA D F)

第二个新旅程可选用旅程2中的第一个城市为起始,用类似方式通过找出循环而构造出来。第二个被生成的新旅程为

旅程2′= (H C D E F J I CB A)

操作[50]将在7.4节中描述。对这三种重排操作的理论和实验结果的对比可参见

OX

文献[122]。

遗传算法在TSP、模式匹配问题、多处理机任务调度问题和作业调度问题上的应用

#第56页-

将分别在第7,9,10和11章中讨论。