图着色的混合遗传算法研究 - 武汉大学学报·信息科学版.pdf

第 卷 第 期 武 汉 大 学 学 报 ·信 息 科 学 版 Ｖｏｌ．３４Ｎｏ．１２ ３４ １２ 年 月 Ｄｅｃ．２００９ ２００９ １２ ＧｅｏｍａｔｉｃｓａｎｄＩｎｆｏｒｍａｔｉｏｎＳｃｉｅｎｃｅｏｆＷｕｈａｎＵｎｉｖｅｒｓｉｔ ｙ 文章编号： （ ） 文献标志码： １６７１８８６０２００９１２１４９９０３ Ａ 图着色的混合遗传算法研究 ， ，， ， 彭珊１２ 何宗宜１２ 宋 鹰１２ 谢 锋３ 　 　 　 　 　 （ 武汉大学资源与环境科学学院，武汉市珞喻路 号， ） １ １２９ ４３００７９ 　 （ 武汉大学地理信息系统教育部重点实验室，武汉市珞喻路 号， ） ２ １２９ ４３００７９ 　 （ 赣州市第三中学，赣州市青年路 号， ） ３ ３０ ３４１０００ 　 摘 要：研究了一种结合贪心算法的混合遗传算法及其各种交叉算子，应用于平面图的四色着色问题。通过实 　 验分析对比了该混合遗传算法的 种可行的交叉算子对该算法的影响，结果显示，边重组交叉算子效果最好。 ４ 关键词：四色问题；贪心算法；混合遗传算法；边重组交叉 中图法分类号： Ｐ２８３．１ 图着色问题起源于地图设计中的着色问题， 父代序列中所没有的部分新序列，所以这种操作 　　 是从地图问题中引申出来的一个著名的图论问 方法的性状遗传特征不太好。对于具有这种约束 题。由于图着色问题是 难问题，传统的递归 编码的情况，可行的交叉算子还有顺序交叉（ ＮＰ ｏｒ 方法、回溯方法、贪心方法都不能取得很好的结 ， ）、循环交叉（ ， ｄｅｒｃｒｏｓｓｏｖｅｒ ＯＸ ｃｃｌｅｃｒｏｓｓｏｖｅｒ ｙ ［］ １ 果 ，因此，对图着色问题的研究主要集中在启发 ＣＸ）和边重组交叉 （ｅｄｅｒｅｃｏｍｂｉｎａｔｉｏｎｃｒｏｓｓ ｇ ［］ ［］ ２