用遗传算法实现四色图问题

火善栋

摘 要： 遗传算法是模拟生物进化过程的算法，任何问题只要能用一组合适的编码来表示其中的一个可行解，那么这个可行解就可以看做是一个生物个体，若干个可行解就可以看做是一个生物种群。将问题的若干个可行解利用生物进化的特点，最终就可以简单快速地得到问题的一个最优解。利用遗传算法和四色图问题的这一特点，通过遗传算法实现了四色图问题的求解。实验证明，用遗传算法实现类似的四色图问题，思想简单，收敛速度快。

关键词： 四色图问题； 遗传算法； 染色体编码； 邻接矩阵

中图分类号：TP391 文献标志码：A 文章编号：1006-8228（2015）03-56-02

Abstract： Genetic algorithms are algorithms to simulate biological evolution， as long as one of the feasible solution can be represented by a set of suitable code， then the feasible solution can be seen as a biological entity， serveral feasible solutions can be seen as a biological population. By using the characteristics of biological evolution with a number of feasible solutions， the optimal solution can be obtained easily and quickly. This article uses the characteristics of genetic algorithms and the four-color map problem， to solve the four-color map problem with genetic algorithm. Experiments show that， to solve a similar four-color map problem with genetic algorithms can be simply thinking and fast convergence.

Key words： four-color map problem； genetic algorithm； chromosome coding； adjacency matrix

0 引言

图的着色问题是由地图的着色问题引申而来的：用m种颜色为地图着色，使得地图上的每一个区域着一种颜色，且相邻区域颜色不同。图的着色问题在组合分析和实际生活中有着广泛的应用背景，如任务调度、资源分配、考试安排、交通管理和排课表等。

19世纪50年代，英国学者提出了任何地图都能以4种颜色来着色的4色猜想问题。过了100多年，这个问题才由美国学者在计算机上予以证明，这就是著名的四色定理。

至于图的着色问题有很多学者提出了一些相关的算法，如：穷举法、回溯法、贪心法、蚁群算法等，本文采用遗传算法实现了四色图问题。

遗传算法[3]的工作过程实质上就是模拟生物的进化过程。首先，确定一种编码方法，使得问题的任何一个潜在的可行解都能表示为一个“数字”染色体，然后，创建一个由随机染色体组成的初始群体（每条染色体代表一个不同的候选解），再经过优胜劣汰、交差变异、基因突变得到一个新的群体，每个新的群体不断如此反复，经过若干代以后，只要问题有解，遗传算法将会收敛到一个解。遗传算法的最大优点就是，不需要知道怎么去解决一个问题，仅需知道用怎样的方式对可行解进行编码，使得它能够被遗传机制所利用。通常情况下，代表可行解的染色体采用一系列二进制位编码，在运行开始时，创建一个染色体群体，每个染色体都是由一组随机的二进制位所组成，二进制位（即染色体）的长度在整个群体中都是一样的。实验证明，用遗传算法实现类似的四色图问题，思想简单，收敛速度快。

1 遗传算法在四色图问题中的具体实现

1.1 地图的简化表示及其邻接矩阵[4]

1.2 染色体的编码

由于四色图问题中每一个顶点仅限为4种颜色，故编码后的染色体应该就代表这4种颜色信息的一个字符串，传统的编码方法就是把颜色变换成二进制的代码。

1.3 染色体适应度的计算

设置一个一维数组，该数组中的每一个元素对应相应顶点的颜色信息，该颜色信息分别为0、1、2、3（这个颜色信息可以通过染色体中相应的两个相邻的比特位来得到），然后通过简化图的邻接矩阵来计算每条染色体（候选解）的适应度。其方法是：遍历简化图中的每一个顶点，通过其邻接矩阵找到与当前顶点相连接的所有的顶点，当这个相邻顶点与当前顶点的颜色值相等时，其适应性分数n就加1。当所有的顶点遍历完了之后，就可以得到这条染色体的适应度fitness=1/（1+n）。通过这个公式可以看出，当n=0时，这条染色体就是问题的一个解，并且其适应度越大，其个体的适应性就越强，该个体就越有可能产生新的后代个体。

1.4 用遗传算法求解四色图问题的详细求解过程

用遗传算法实现四色图问题时，其收敛次数和收敛时间并不与种群的大小成一定的比例关系，当种群为100和80时其收敛次数随着种群的减少而呈现增加趋势，收敛时间呈增多趋势，当种群大小为70、60、50和40时，收敛次数为1，收敛时间很短，近似为0，但当种群大小为20时，迭代次数突然增大，当然迭代时间也突然增大。从这种结果也可以看出，在用遗传求解相关问题时，种群的大小直接影响到求解问题的迭代次数和迭代时间。从表2的实验结果也可以看出，只要比较合理地设定初始种群的大小，用遗传算法就可以快速有效的解决类似的四色图问题。

参考文献：

[1] [美]Mat Buckland著，吴祖增，沙鹰译.游戏编程中的人工智能技术[M].

清华大学出版社，2006.

[2] [美]George E Luger著，郭茂祖等译.人工智能复杂问题求解的结果

和策略[M].机械工业出版社，2010.

[3] 王小平，曹立明著.遗传算法：理论、应用与软件实现[M].西安交通大

学出版社，2002.

[4] 高一凡，编著.《数据结构》算法实现及其解析[M].西安电子科技大学

出版社，2002.

[5] 程杰编著.大话数据结构[M].清华大学出版社，2011.

[6] 吕凤詟编著.C++语言程序设计[M].清华大学出版社，2003.