蚁群优化图着色算法在智能小区中的运用*

魏 娟

(江西服装学院商学院，江西 南昌 330201)

智能小区[1]是智慧城市里的基本单元，是通过物联网、移动互联网、云计算和信息智能终端等信息技术建立的住宅小区服务和管理集成系统，使小区管理者、用户与各类智慧系统完成各种形式的信息交互，让居民在吃、住、行、游等方面体验舒适快捷的现代化数字生活，同时使管理更高效.智能小区通常是采用地理信息系统(Geographic Information System，简称GIS) 的网格化管理，将小区里的各种动态数据和信息在地图网格中显现出来，并实时更新数据[2].为了在地图网格中清晰且直观地展现这些信息，可以利用蚁群算法在网格里进行着色，但是在颜色数太多时，该算法无法对着色色数进行控制，从而出现处理的信息杂乱无章的现象[3].笔者将对蚁群算法进行优化，以解决智能小区网格着色问题.

1 图着色问题描述

图着色问题(Graph Coloring Problem，简称GCP)又称着色问题.GCP多应用于组合分析和实际生活中，如最大支配集、二次分配和最大覆盖等典型的组合问题，又如工艺设计、科学技术和企业管理等领域的问题.在数学上，GCP的定义是从无向图公式G=(V,E)而来的，V表示顶点集合，E表示边集合.GCP就是将V分成K个颜色组，每组之间无相邻的顶点，都是单独集，对其进行优化就是将K值最小化.GCP主要包括点着色、边着色和组合地图的面着色等，而边着色和组合地图的面着色经一定的变换后，都可以转化成等价的点着色.点着色即对图G的顶点处着色，使得任何相邻顶点都涂上不同的颜色.若用K种颜色可以实现对图G的顶点进行着色，则称图G是K点可着色的；若K是图G的最小着色数，则称图G是K色图.

2 蚁群算法

M Dorigo根据蚂蚁觅食原理提出了模拟自然环境中蚂蚁真实觅食行为的算法，称为蚁群算法.其根本思想是蚂蚁在觅得食物之后，总能找到最优路径将食物运回巢穴，这是因为每只蚂蚁会在它所经过的路径上释放一种叫做信息素(pheromone)的挥发性物质，蚂蚁在行动过程中可以感知该物质的强度，从中获取有关信息并开展相应行动[4].因此，蚁群算法其实是一种在图G中寻找优化路径的机率型算法，是一类关于种群的启发式搜索仿生进化系统[5].

采用蚁群算法对一个给定的图形着色，设C是颜色集，C={c1,c2,c3,…,cp}，V是顶点集，V={v1,v2,v3,…,vn}，蚂蚁总数为m.为了着色准备，构建图G的邻接矩阵D=(Dij)，其中

用着色表S=(Siq)记录蚂蚁的着色行动.令Siq=1表示蚂蚁经过顶点vi，这时用cq对顶点vi着色，即

(1)

其中：ηij是启发式信息，

(2)

NumC是顶点vi-1着色后用的总颜色数；α和β(α,β∈{1,2,3,4})分别是信息素量Tij和启发式信息ηij对蚂蚁着色的影响参数.

3 蚁群优化图着色算法

图1 着色和褪色过程Fig. 1 Coloring and Fading Process

着色和褪色过程中存在着色不成功的问题.这个问题可通过如下5个步骤解决：

(ⅰ)设置各参数信息，包括循环次数NC、初始化蚁群数antCount、蚁群最大色数Max(4≤Max≤P)，以及影响参数α和β等.为了记录蚂蚁的爬行线路，增设一个路径信息tour，初始是点的次序；同时将antCount置于点1，设NumC=1，最开始着色蚂蚁t=1.

(ⅱ)蚂蚁t对图全面着色，主要是指对点tour[a]着色和褪色，直到全部点都着色.其中a是已着色点数，开始时a=1.假设进行了褪色的过程，那么a就是a-1.

(ⅲ)所有蚂蚁都全部着色，则记录最好的着色；不然，t++，返回步骤(ⅱ).

(ⅳ)由(1)，(2)式改变信息素量Tij和启发式信息ηij.

(ⅴ)假设循环次数NC已经达到，那么输出的就是当前最优的解；否则，是NC++.这时需要进入下一次循环，将antCount置于点1，设NumC=1，最开始着色蚂蚁t=1.

4 蚁群优化图着色算法与蚁群算法的对比

在Windows7环境下，采用Java软件，设置迭代次数1 000，蚁群数20，对比分析蚁群优化图着色算法与蚁群算法的着色色数和运转时间，如图2所示.

a 色数性能对比 b 运转时间对比图2 蚁群优化图着色算法与蚁群算法的性能对比Fig. 2 Performance Comparison Between Ant Colony Optimization Graph Coloring Algorithmand Ant Colony Algorithm

从图2a可以看出，在GCP的解决中，蚁群优化图着色算法能够有效地将色数控制在Max范围里，优于蚁群算法.从图2b可以看出，随着图的复杂性不断增加，蚁群优化图着色算法的运转时间比蚁群算法的少.由此可知，无论是求解色数方面，还是运转时间方面，蚁群优化图着色算法的性能都优于蚁群算法，尤其是在图复杂性极高的环境下，蚁群优化图着色算法还能减小并控制着色色数，实现四色着色.

5 蚁群优化图着色算法的运用

将蚁群优化图着色算法运用在智能小区中，对智能小区的网格进行着色.其主要过程如下：

(1)在GIS中获取地理数据信息，并根据主要街道绘制小区网格；然后从GIS空间数据的拓扑关联中获取每个网格间的邻接关联，并将邻接关联导入到relation.dat文档中.

(2)将relation.dat文档中读取的数据应用到蚁群优化图着色算法中，对读取的数据进行着色，然后回着色表S.

(3)依照着色表S对网格着色.

将蚁群优化图着色算法运用于南昌市某智能小区中，其最大色数Max设为4.根据该小区街道的特点，将小区分成8个网格，采用蚁群优化图着色算法获得着色色数是3.在对网格进行着色时，采用深灰色色调，透明度为20%，50%，80%.小区网格化着色结果如图3所示.

图3 小区网格化着色结果Fig. 3 Cell Grid Coloring Results

6 结语

蚁群优化图着色算法弥补了蚁群算法的不足.尤其是在图复杂性较高的环境下，蚁群优化图着色算法能减小并控制着色色数，实现四色着色，使得智能小区里的各种动态数据和信息在地图网格中更加清晰且直观地展现，从而在智能小区社会服务过程中表现出服务“零距离”、居民诉求 “全响应” 和社会管理 “全覆盖”等优点，值得在智能小区服务中推广应用.