图着色问题的启发式搜索蚂蚁算法

Vol .33 No.16 Computer Engineering · 人工智能及识别技术 ·

文章编号：1000—3428(2007)16—0191—02

文献标识码：A

2007年8月

August2007

中图分类号：TP18

图着色问题的启发式搜索蚂蚁算法

廖飞雄，马 良

（上海理工大学管理学院，上海 200093）

摘 要：针对经典的图着色问题，该文在随机序列启发式搜索求解的基础上，引进蚂蚁算法优化思想，设计了一种新型算法，有效地避免了启发式搜索易陷入局部极小的缺陷。通过给地图着色和仿真实验结果表明，该方法对图着色问题的求解是可行、有效的，且具有通用性。关键词：图着色；启发式搜索；蚂蚁算法

Heuristic Search-based Ant Algorithm

of Solving Graph Coloring Problem

LIAO Fei-xiong, MA Liang

(College of Management, University of Shanghai for Science and Technology, Shanghai 200093)

【Abstract】Based on the idea of sequential heuristic search, this paper proposes a new ant colony optimization algorithm for the classical graphcoloring problem to effectively avoid the weakness of easily running into local minimum of heuristic research. Series of numerical simulations andexperiments show the effectiveness and generality of the method. 【Key words】graph coloring; heuristic search; ant algorithm

图着色问题(graph coloring problem, GCP)是图论中的一个经典难题[1,2]，内容包括点着色、边着色、组合地图的面着色等。GCP在组合分析和实际生活中有着广泛的应用背景，如任务调度、资源分配、排课表、VLSI布线和测试等，目前大量的科技、管理及工业设计等领域问题都可归结为图着色问题来解决；一些典型的组合问题，如最大支配集、二次分配、最大覆盖问题等也都可以转化为图着色问题来加以研究。 对“四色猜想”和“五色定理”的证明曾相继引出许多理论结果，以及有关色多项式和一些着色数上界的结论。后来出于应用需要，更多的研究集中到了算法设计方面。早期的算法研究主要是诸如基于布尔代数运算的着色算法和基于深度优先检索的回溯算法等经典方法，后来在用传统方法解决复杂及较大规模的问题出现困难时，一些近似算法或启发式算法陆续问世，而近些年来随着智能算法的发展，遗传算法和模拟退火等自适应算法逐渐受到了人们的重视。但由于图着色问题是个典型的NP-难题，大部分早期算法的时间复杂性为指数级的，而智能算法在图着色方面的应用还处于试探阶段，成果较少。本文分析了一种随机序列启发式搜索的特点，给出了一种新的基于蚂蚁算法思想[3,4]的求解策略，在时间复杂度相当的情况下，明显地提高了解的质量。 令p = 1 + Δ(G)）并且极小化，使得对任意(vi,vj)∈E，C(vi)≠C(vj)。 定理 若图G的顶点最大度数为Δ(G)，则χ(G)≤1+Δ(G)。 图顶点着色问题可形式化地描述为：给定无自环图G (V, E)，V={v1,v2,K,vn}，建立映射C:V→{c1,c2,K,cp,}（参照定理2 算法设计 2.1 随机序列启发式算法 对于任一给定的无环无向图G(V, E)，随机生成顶点序列V={v1,v2,K,vn}，假定以C=c1,c2,K,cp,表示每个顶点p种不同可着色颜色的一个集合。 随机序列启发式算法可描述为： Step1 随机生成顶点序列V={v1,v2,K,vn}，每个顶点的可着色集为C={c1,c2,K,cp,}。 Step2 给v1着色：在可着色集中选择第1个颜色c1给v1着色，并将v1移到已着色点集中。 Step3 给v2着色：若v2与v1相关联，则v2可着色集去除c1，并选择可着色集中的第1个元素c2给v2着色；否则可着色集的第1个元素c1给v2着色，将v2移到已着色点集中。 Step4 给vi (i>=3)着色：若vi与已着色点集中点相关联，则在可着色集中去除该点着色颜色，并在可着色集中选择第一个颜色为vi着色。 Step5 若未着色点集不为空，则转到Step4；否则着色完成，输出结果。 该算法的特点是优先使用旧颜色，同时也保证每一次着基金项目：国家自然科学基金资助项目(70471065)；上海市重点学科建设基金资助项目(T0502)

作者简介：廖飞雄(1983－)，男，硕士研究生，主研方向：系统工程，智能优化；马 良，博士、教授、博士生导师 收稿日期：2006-08-30 E-mail：fly_honk@163.com

{}1 问题描述 图着色问题主要分为顶点着色、边着色、图的全着色。经一定的变换，图的边着色和全着色都可以等价地转化为图的顶点着色，因此本文仅局限于讨论图的点着色问题。点着色是对图G(V, E)的顶点进行着色，要求将每个顶点涂上一种颜色，使得任何相邻顶点都具有不同颜色。若用k种颜色能够对G的顶点进行一种着色，就称G是k−点可着色的。若G是k−点可着色的但不是(k−1)−点可着色的，就简称G是k−色的或称k为G的色数，记作χ(G)，即χ(G)是使G是k−称G是k−色图，点可着色的k的最小值。这里，引入一个点着色的重要定理[5]：

—191—

色都是可行着色。图1简要的说明了该算法的着色过程。 v1(c1)

v5 (c3)

v8 (c3)v2 (c2)vv7 (c2)6 (c1) v4 (c2)

v3 (c1)

图1 着色过程 但是该算法在顶点关联比较复杂时容易陷入局部最优解，如图2所示，在给v5着色时可着集的第1个元素为c1，则v6要着色c4，以至于用了4个颜色给该图着色；如果在Step3中不选择可着色集的第1个元素却可以得到最优解，如图3所示，使用c3给v5着色，c1给v6着色，以至于只用3个颜色就可以给该图着色。所以，在处理这个环节上，引入了蚂蚁算法的局部搜索能力。 v1 (c1)

v4 (c2)v1 (c1)v4 (c2)v3 (c3)

v3 (c3)v2 (c2)v6 (c4)

v2 (c2)v6 (c1)

v5 (c1)

v5 (c3)

图2 用4个颜色着色 图3 用3个颜色着色 2.2 基于随机序列启发式搜索的蚂蚁算法 蚂蚁算法是一种源于大自然生物世界的新的仿生类算法，它吸收了昆虫王国中蚂蚁的行为特性。通过观察发现蚂蚁群体可以在没有任何可见提示下寻找其巢穴到食物源的最短路径，并且可以随着环境的变化，适应性地搜索新的最短路径，产生新的选择，这是通过蚂蚁个体之间的协作来完成的。在这些协作的蚂蚁个体之间采用的通信方式是：使用一种特有的称为信息素的挥发性分泌物，这种物质使得一定范围内的其他蚂蚁能够察觉到并由此影响它们以后的行动。觅食蚂蚁在寻找食物的过程中，在其走过的路径上留下信息素，同时又能检测到其他同伴释放的信息素，选择较强的一条路径从而决定行走的方向，行走的同时又释放自身的信息素，增强了该路线上的信息素数量(当然，随时间的推移会同时逐渐减弱)。后来蚂蚁选择该路径的概率也越高，从而更增加了该路径的轨迹强度。随着越来越多的蚂蚁通过该路线，一条最佳路径就会形成。基于此思想的蚂蚁算法在求解经典TSP问题、车辆调度问题等组合优化难题上表现出了良好的性能。 本文将给出一种基于启发式搜索的蚂蚁算法，用于求解图着色问题。 对于任一给定的无环图G(V, E)，随机生成顶点序列V={v1,v2,K,vn}，图的最大顶点度数为p，颜色集C={c1,c2,K,cp,}，作如下定义： D(n×n)表示图G(V, E)的邻接矩阵，满足 D(i,j)=⎨

⎧⎪0

表示vi与vj不关联 ⎪⎩1

表示vi与vj相关联

S(n×p)为一张着色表，也称为着色矩阵，满足 S(i,j)=⎧⎪0

表示不给v⎨i着cj色 ⎪⎩1

表示给vi着cj色

p

且∑S(i,j)=1j=1

。 若着色蚂蚁k经过S (i, j)，则表示给vi着cj色，（如图4中S (1,1) =1，图5中为一只蚂蚁的完全着色过程）。 —192

—c1c2c3c4c5…cpc1c2c3c4c5…cp112…2…334…4………………………n-1n-1…n… n 图4 着色矩阵 图5 一只蚂蚁的着色过程 τ(n×p)表示信息素矩阵，τ(i, j)表示给vi着cj色的信息素，与着色矩阵相对应； ∆kτ(i,j)表示蚂蚁k在遍历过程中释放的信息素： ∆τ(i,j)=

Q

kcoloredn

信息素更新方程：τij(i,j)=ρτij(i,j)+∆τ(i,j) 其中，m

∆τ(i,j)=∑∆k(i,j)。 k=1

ηij表示启发式信息： η1 ij=

Numc

其中，Numc表示vi-1着色后使用的总颜色数。 蚂蚁在着色遍历时，给顶点vk

i着cj色由转移概率pij定： 决⎧ταβijηij

pk=⎪⎨αcj∈allowedki ⎪∑τβijisηis

⎩

0else

其中，allowedki为蚂蚁k给vi着色时在已着色集中可行着色集，若不为空集则按概率pk

ij给vi着色cj，若为空集则Numc = Numc+1，给vi着cNumc。 α,β体现了信息素和启发信息对蚂蚁决策的影响(α,β=1,2,3,4)；Q值通常取1；1-ρ表示信息素的挥发度，通常取0.3。 整个算法可叙述为： Step1 gen←1；初始化循环次数、蚂蚁总数；将待着色图以关联矩阵形式存储，随机生成顶点序列V={v1,v2,K,vn}；初始化轨迹信息素矩阵。 Step2 将m只蚂蚁同时置于v1点，此时Numc = 1，初始着色k←1。 Step3 蚂蚁k进行遍历着色：当给vi着色时，判断allowedk

i是否为空，若不为空，则按概率pkij给vi着色cj；若为空集，则Numc=Numc+1，给vi着cNumc；按此方式直至一次着色 完成。 Step4 若m只蚂蚁全部着色完成，则记录当前最佳着色序列和所用颜色数；否则，k = k + 1，返回Step3。 Step5 更新轨迹信息素。 Step6 若达到预定迭代步数，则输出目前最好解；否则，gen = gen + 1，返回 Step2。 算法用Matlab编程实现，在PC机WindowsXP环境下运行通过。 3 计算实例 以中国地图着色问题进行测试：中国地图共包括34个省、直辖市、自治区、以及中国台湾、中国香港特别行政区 (下转第195页)