第 30 卷第 5 期 2013 年 5 月 计算机应用与软件 Computer Applications and Software Vol. 30 No． 5 May 2013 求解图着色问题的进化稳定策略蚁群算法 赵焕平1 胡 可2 李敬文3 1 ( 南阳理工学院计算机与信息工程学院 河南 南阳 ) 473004 2 ( 南阳理工学院 河南 南阳 ) 473004 3 ( 兰州交通大学电子与信息工程学院 甘肃 兰州 ) 730070 针对图着色问题，在传统的启发式蚁群算法的基础上提出一种进化稳定策略蚁群算法。进化稳定策略蚁群算法针对蚁 摘 要 群算法的隐含并行性，利用变换因子自适应地更新信息素，动态自适应地调节启发式因子的作用参数，增强算法的搜索能力，加快算 法的收敛速度，同时避免了传统蚁群算法容易陷入局部最优的问题。通过给地图着色的仿真实验结果表示，该方法对图着色问题的 求解是可行、有效的，通过大量实验表明算法在求解质量上优于启发式蚁群算法。 关键词 图着色 蚁群算法 进化稳定策略 变换因子 中图分类号 TP301． 6 文献标识码 A : DOI 10． 3969 / j． issn． 1000-386x． 2013． 05． 007 EVOLUTIONAＲY STABLE STＲATEGY ANT COLONY ALGOＲITHM FOＲ SOLVING GＲAPH COLOUＲING 1 ( School of Computer and Information Engineering ， Nanyang Institute of Technology ， Henan ， China ) Zhao Huanping1 Hu Ke2 Li Jingwen3 ， 2 ( Nanyang Institute of Technology ， Nanyang 473004 3 ( School of Electronic and Information Engineering ， Lanzhou Jiaotong University Lanzhou 730070 ， Gansu ， China ) Nanyang 473004 ， China ) ， Henan ， ， ， Abstract In the paper we propose an evolutionary stable strategy ant colony algorithm for graph colouring problem based on the traditional heuristic ant colony algorithm． Aiming at the implicit parallelism of ant colony algorithm the new algorithm uses conversion factor to update the pheromone adaptively and dynamically and adaptively adjusts the parameters of heuristic factor therefore enhances the search capability ， of algorithm and accelerates the algorithm’s convergence speed as well while avoids running into local minimum which the conventional ant colony algorithm is prone to． It is demonstrated by the simulation experimental result of colouring the map that using this method to solve a great deal of experiments also proves that the new algorithm outperforms the heuristic ant colony graph colouring is feasible and effective algorithm in solution quality． ; Keywords Graph colouring Ant colony algorithm Evolutionary stable strategy Conversion factor 0 引 言 1 － 3 。 。 NP 如电网络 图着色问题［ 排课表 、 由于图着色问题是图论中典型的 ］是图论研究中一个很活跃的课题，无论是 资 在理论上还是工程应用上均有良好的应用背景 、 拉丁方构造等问题都可以归结为图着色问题来 源分配 、 完全难题，获得最 解决 优解的时间随着问题规模的增加呈指数级增长，因此，对问题的 近年来，蚁群算法在解决组合优 研究主要集中在智能算法上 化问题上取得了比较理想的结果，如旅行商问题( ) ，二次分 配问题( 本文提出了一种基于进化稳定策略的自适 应并行蚁群算法来解决图的着色问题，在传统的启发式蚁群算 法的基础上改进了信息素的更新机制，并自适应地调节了启发 式信息的作用，与传统蚁群算法相比，求得解的质量有了明显的 基于进化稳定策略的蚁群算法会根据解的密度和质量自 改善 适应地动态更新信息素，同时根据解的分布情况动态自适应地 ) 等 QAP TSP 。 。 。 调节启发式信息的作用，从而避免了收敛过快而陷入局部最优 解的情况 。 1 蚁群算法求解图着色模型 1． 1 问题描述 图着色的问题可描述为: 已知无向图 颜色，用这 G 邻的两个顶点都着不同的颜色，就称 种不同颜色分别对图 k ( 种不同 的顶点着色，使图中任意相 ) 和 ， E G V k 是 点可着色的 G k- 。 图着色问题主要包括图的顶点着色，图的边着色和图的全 着色等，经过一定的变换，图的边着色和全着色问题 经 过 全 图［ ］的转换加上一些限定条件都可以转化为图的顶点着色问 4 收稿日期: 2012 － 06 － 19。 国家自然科学基金项目( 焕平，讲师，主研领域: 图染色算法及应用，智能算法研究 李敬文，教授 ) 。赵 10771091 。胡可，讲师 。 。 

第 5 期 赵焕平等: 求解图着色问题的进化稳定策略蚁群算法 23 因此，本文只需要讨论图的点着色问题 。 题来求解 1． 2 求解图着色的蚁群算法［5，6］ ， … 对任一图 V = { ， v2 v1 。 ) 表示颜色集，图的最大顶点度数为 ， vn } 表示随机生成的顶 ， 因子，并由此定义其变换因子［ 更新信息量 。 ］，然后根据变换因子自适应地 7 解空间的位置距离与蚂蚁间的着色差值有关，差值越大，解 空间的位置就相隔越远，由此蚂蚁 的密度定义为: ( ， V G E ， ， … c2 ) ，用 ， cp ( C = c1 点序列， 用 m 只蚂蚁对图遍历着色 ( ) 表示图 ( D n × n 。 ， E ( D ， ) j i = G { V 0 1 × p ( S ， ) j i = 并且 ( S i ) 满足: ， j { 0 1 p 作如下定义: ) 的邻接矩阵，则: 表示 表示 和 和 vi vj 不相关联 相关联 vi vj 表示不给 表示给 vi vi 着 着 cj 颜色 cj 颜色 将所有蚂蚁放在一个顶点上开始遍历着色，着色矩阵 ) 表示着色结果，用来记录蚂蚁每次迭代的着色过程，则: ∑ ( j = 1 S i S ， j ( ， ) j i = 1 ) ，表示给 ， j ( 着 色 vi cj ) 表示给 。 着 ) 表示信息素矩阵， τ 色的信息 ) 相对应; 每条路径都要遵循一致的信息素挥发 vi cj i 若着色蚂蚁 ( k 经过 n × p ( S n × p τ 素，与 规则: ( ， ) j ( ) ( ， ) j 其中 ρ 在路径( i = τij i 表示信息素的挥发度，通常取 + Δτ ; 0． 3 ) 上留下一定的信息素之和，则: 1 － ρ τij Δτ ， j i ( ( ) ) 为所有蚂蚁 4 ， ) j ， j i i ( ( ， ) j i Δk τ = Q / NumC 其中 后使用的总色数 Q 表示信息素强度，通常取 ; 1 NumC 表示给点 vi － 1 。 表示启发式信息: ηij pk ij ηij = 1 / NumC 表示蚂蚁在遍历着色时给 着色 vi 的转移概率: cj { 0 pk ij = τα ij ηβ ij /∑τα ij ηβ ij if cj ∈ allowedk i else allowedk 其中， 表示蚂蚁 k 集，若不为空集，则按概率 令 vi 给 ，然后给 NumC = NumC + 1 给 pk ij i 着色时在已着色集中可行着色 ，若为空，若为空集，则 着色 vi 着色 vi cj cNumC 。 2 进化稳定策略蚁群算法 2． 1 进化稳定策略蚁群算法的改进策略 针对启发式蚁群算法存在早熟收敛等缺点，即在大规模的 求解任务时，当某个解的适应度值在群体中占主导地位，其对应 的信息素浓度也比较高，种群的多样性遭到破坏，算法搜索空间 减小，蚂蚁的搜索过程趋于收敛，再继续迭代的结果还为同一种 解而再也不能发现新的解，也就陷入了局部最优解 提出了一 种基于进化稳定策略的蚁群算法，进化稳定策略是一种保持进 针对蚁群算法的隐含 化种群稳定而又不陷入局部最优的策略 并行性，利用变换因子自适应地更新信息量，自适应地调节启发 式因子的作用参数，增强算法的搜索能力 具体改进如下: 。 。 。 ( 1) 信息素的更新 在蚁群算法中，更新信息素时只考虑了解的适应度，而忽视 根据解的分布情况进行信息素的更新，能够 了解的分布状态 动态地调整各路径上信息量的分布，从而加速收敛的同时避免 首先为每个解定义密度因子和质量 超级个体带来的早熟现象 。 。 P ( ) 1 ( S n ( ) 2 ( ) 3 6 ) ( 着色 ( ) 7 ( ) 8 i m ( ) ( ε ， ) j i ( ) 9 i = ∑ density 的颜色差值小于 j = 1 蚂蚁 时 i 的值一般根据问题的规模来取值 colmax j 其中当蚂蚁 为 0。colmax 定义密度因子为: ( ε i ) 值为 ， j 1 ，否则 。 δi density = exp 定义质量因子为: ( － density ( ) i ) / m ( ) 10 ( f ) i － Fmin f ) ( ( ( δi － Fmin quality = exp 反映了当前迭代中蚂蚁 i 保持不变的情况下， ( f ) / Fmax 的适应值与整体最差 ) 与 11 ) ) ( i i Fmax 个体适应值的相对差值，在 越大，蚂蚁 Fmin 的质量因子也越大 i 。 在密度因子和质量因子的基础上定义变换因子: density δi 在此基础上信息素更新公式为: δi = δi quality ( τ ， ) j i ( = 1 － ρ ) ( ， ) j i ·τ δi / NumCbest if ( ， ) j i Δτ' = { 0 m ( ， ) j i Δτ' + ρ·∑ k = 1 当前迭代的结 果为最优解 else ( ( ( ) ) ) 12 13 14 通过变换因子的调节，适应度较高而且密度较小的蚂蚁所 经过的路径上的信息量更新的程度就很大，这样做既可以强化 适应度高的路径，又可以保证解的多样性 。 ( 2) 信息量的调节 为了避免在迭代过程中陷入局部最优解 ，先设置一阈值 ，当信息素达到这个值时，使用矩阵来构造一个与局部最优解  差异较大的解，然后根据这个解来调整信息量 。 信息量的调整公式: ， ) j ( i i i ( ( τ Δk τ ， ) j ， ) j + γΔτ ( = τ ， ( ) j ) ) ) ，通过对其路径上的信息进行增加，适当地均衡 其中 最优路径和最差路径上的信息量，这样可以有效地保持解的多 另一方面，要使算法的搜索速度和收敛性不受到影响， 样性 γ 的值应相对较小 = Q / NumC ， 1 γ∈ 。 15 16 ( ( 0 i 。 因为信息量的调整是在阈值 是一个很关键的参数 不利于快速跳出局部最优解 。 ］结果较好 0． 95m 。  的控制下进行的，所以阈值 如果太小，会导致收敛速度太低，而太大 ， 通过实验总结出 ［ ∈ 0． 75m 。 ( 3) 启发式信息作用的调节 启发式因子 和 分别表示路径上的信息量 α β 及启发式 τij 对蚂蚁选择路径所起作用的大小 在传统的蚁群算法 的值是固定不变的，而在本算法中，它们可以根据解 。 ηij 和 信息 中， α 的分布情况自适应地调节 β 。 n β = 2 － ∑ i = 1 ( x ) i / N α = 2 － β ( ) 17 其中 ( ) i = Numi / NumC 。 x 在搜索的初期阶段，为了让解向多样性方向发展，首先让 α 随着算法的 = β = 1 不断迭代，超级个体引起某些路径上的信息量急剧增多，易造成 和启发式信息 的作用相同 ，使信息量 。 ηij τij 

24 局部收敛 v2 ， ， … vn 步骤 2 ; 步骤 3 NumC = 1 此时增大 的值 减小 、 β α 。 值，使得 的作用大，蚂蚁的选路在更大程度上依赖 起的作用要比 ηij ，这样可以扩大 τij 蚂蚁的搜索范围，避免陷入局部最优 2． 2 进化稳定策略蚁群算法 。 ηij 基于以上描述，在求解图着色的蚁群算法的基础上，进化稳 定策略蚁群算法描述如下: 步骤 1 初始化迭代次数 ，蚂蚁总数 NC-num 图以关联矩阵 ) 形式存储，随机生成顶点序列 m ，将待着色 ， { V = v1 ( D } ，按式( 将 m n × n ) 初始化信息素轨迹矩阵; 只蚂蚁置于同一个顶点 4 上，初始着色数 v1 。 蚂蚁 进行遍历着色: 当第 k k 色时，判断是否为空，如果不为空，则按概率 为空集，则令 ，然后再重新给 NumC 直至一次着色完成 值加 1 只蚂蚁给顶点 着颜色 着 vi ，若 cj ，按此方法 给 pij 染 vi vi cNumC 。 步骤 4 明一次迭代完成 果是，根据解的密度和质量，按式( 果获得的信息量超过设定阈值 来调整信息量，并根据式( 进行调整; 继续进行步骤 判断蚂蚁是否都已经遍历完，如果遍历完毕，则表 然后判断此次着色是否为当前的最优解，如 ) 自适应地更新信息量，如 ) 和 13 ，根据进化稳定策略中式( ) 对定启发式因子的作用参数 ，否则， ，返回步骤  15 17 α ; 5 k = k + 1 3 β 判断是否达到预定的最大迭代次数，如果达到，则 步骤 5 输出目前最好解; 否则，令迭代次数加 ，返回步骤 1 2。 算法的伪代码如下: 输入: 图 输出: 着色后的顶点序列{ 的规模 G n Initialize NC-num 根据式( ， m ) 初始化 ， D ( ， ; v ) τ n × p 4 ( 达到预定的最大迭代次数) While { ， v2 ， … ， vn } v1 NumC = 1 ; For k = 1 to m { For i = 1 to n { ( If NumC ! ) = NULL vi = cj else { NumC = NumC + 1 vi = cNumC } } } 按概率 给 pij vi / / 着颜色 cj ( 此次着色为当前的最优解) if { 按式( ) 更新信息素 13 If ( 信息素 { ) ＞  根据式( 根据式( 15 17 ) 调整信息素 ) 调整启发式信息的参数 和 β α } } 迭代次数加 1 } 计算机应用与软件 2013 年 3 实验结果及分析 的编号可得地图的邻接矩阵 为了验证算法的有效性，对编号如图 所示的中国地图进 行着色，根据图 ) ，通过 大量的实验得到自适应并行蚁群算法在求解图着色问题时参数 设置: 蚂蚁总数 次， 在 ， ρ = 0． 3 下运行，可得着色序列为: ［ ，迭代次数控制为 ， Q = 5 34 × 34 m = 30 机下 200 D 1 1 ( PC Windows XP 1 2 4 1 3 1 2 ］， 表 1 ， 2 ， 3 ， 4 1 2 1 3 4 1 2 3 2 1 4 2 2 1 2 3 2 1 3 1 4 1 3 2 2 1 1 示四种颜色 。 图 1 中国地图城市编号 1 表 中用几组不同的数据对进化稳定策略蚁群算法和启发 式算法对解决图着色问题的性能进行了比较，在相同的条件下， 分别对两种算法的着色数和运行时间比较如表 所示 1 表 1 不同规模下的运行时间及正确率 。 顶点 数 边的稠 密度 最大 度数 启发式蚂蚁算法 进化稳定策略蚁群算法 色数 运行时间 色数 运行时间 50 50 50 50 70 70 70 70 100 100 100 100 150 150 150 150 200 200 0． 1 0． 3 0． 5 0． 8 0． 2 0． 4 0． 6 0． 8 0． 1 0． 3 0． 5 0． 7 0． 1 0． 3 0． 5 0． 7 0． 3 0． 5 9 21 34 42 23 35 48 62 31 43 60 83 45 62 93 137 115 170 4 8 10 12 9 13 17 23 11 13 19 28 14 19 28 32 22 35 39． 7861 41． 5670 42． 3218 43． 1973 43． 7352 45． 6327 46． 8591 48． 1634 97． 3570 106． 2951 121． 3048 133． 4771 138． 1457 143． 4759 158． 3128 172． 4756 196． 7854 229． 6324 4 7 8 10 8 11 14 20 10 11 17 25 12 17 25 31 21 33 36． 4328 37． 6871 37． 9807 38． 0015 38． 6983 39． 5326 40． 3874 43． 3219 91． 5640 98． 7628 108． 7124 120． 0045 125． 7129 131． 9124 140． 0139 158． 3472 177． 5423 201． 3658 300 表中的色数是指同一算法求解 个实例所得色数的平均 值，从实验结果可以得出: 在求解图着色的问题中，进化稳定策 略蚁群算法与启发式蚂蚁算法相比，不但在运行时间上比启发 式蚂蚁算法有优化，而且在求解质量上也优于启发式蚁群算法 。 从实验结果可以看到该算法能有效地改进启发式蚂蚁算法的不 足，有较强的寻优能力 。 ( 下转第 40 页) 

40 计算机应用与软件 2013 年 : 8 40 。 次谐波和 左右，这是因为物业工作人员开启了部分照明回路打扫卫生，这 时的电流谐波主要是由格栅荧光灯产生的 随着上班时间的到 来，工作人员逐步到位并开启计算机等办公用电设备， 相电流 A 总畸变率迅速升高并于上午 以 分左右达到并维持在 35% 上， 以上， 次谐波含有率也分别保持在 5 3 这是因为计算机 投影仪和复印机等办公设备工作时产生了大 、 量的谐波 下午下班后随着照明灯具和办公用电设备的陆续关 闭，夜间监测到的电流畸变率杂乱无序且随时间迅速变化，这是 因为当监测电流值较小时，监测终端的相对误差增大 相出线端仅存有小于 路间的干扰 已没有实际意义 A 的杂散电流，这主要是由于配电线 电磁感应等因素造成的，此时的电流畸变率 、 漏电 、 这时 0． 1A 25% 15% 和 。 。 。 图 7 总供电回路 37． 44% 、 超过设定的 A 下午 6 九楼总供电回路 图 为谐波畸变率越限报警信息画面 A 相电流谐波畸变率曲线 14 : 。 达到 从图 36． 59% 和下午 7 相电流三次谐波含有率分别于上午 9 达到 相电流总畸变率于上午 可以看出， 达到 ， : 25 报警限值， 达到 A 报警限值，因此系统进行报警事务处 这是因为上班后办公用电设备的增 相电流谐波总畸变 35． 77% : 14 17 30 25 9 : 35% ，超过设定的 45． 14% 45% 理并生成了四条报警记录 加和设备启停对配电网产生的冲击致使 率和三次谐波含有率逐渐增大 。 A 。 耗采集与监测系统和建筑设备节能控制系统的功能增加进来， 构建一个综合的建筑能源管理系统 。 参 考 文 献 ［ 1 ［ 2 ［ 3 ［ 4 ［ 5 ［ 6 ［ 7 ［ 8 ］ ［ 9 ］ ［ ］ 10 ］ 王葵，李建超，蒋丽，等 ］ 谐波电流对低压配电网的影响分析［ J ． ． 继电器， ， 36 ］ 任宝立，刘晓峰 2008 ) : 24 － 28． ( 7 ］ 医院配电系统的谐波治理［ J ． ． 建筑电气， 2009 ， ( ) : 28 7 27 － 29． ］ 陈众励，翁晓翔，陈杰甫，等 电力电子技术， ］ 初探［ J ． ． 2007 医院医技楼低压配电系统的谐波状况 ( ， 41 ) : 12 54 － 56． ］ 陈峥，郭芳瑞 ． ， ( 9 科技， 2010 智能建筑中谐波畸变的检测与防范［ ］ J ． ) : 4 29 － 31． 中国西部 ］ 王昕，丁玉凤，王舟，等 智能建筑中的电能质量问题及其监测 ， 1 ］ 刘金凤，赵松利，赖晓明，等 现代建筑电气， ］ ［ J ． 2010 ) : ( ． 60 － 63． 2 一种应用于建筑 ］，智能建筑与城市信息， ． 量在线监测装置［ J 进线的电能质 ( ) : 10KV ， 11 2007 40 － 42． 的电能质量综合监测系统的研究 ) : 9 ］ 张立辉，李君兴 基于 制造业自动化， ． ］ ［ J ． LabVIEW ( ， 33 2011 10 47 － 49． Ｒosa J J G ， et al． A web-based distributed measurement system for elec- ， ， ． Elsevier Ltd． Measurement 2010 ［ ］ J trical power quality assessment : 43 771 － 780． ， Shen Bin Zhang Guiqing et al． The development of ， Wang Shaolin ， management system for building equipment Internet of Things ［ ］ C / / Proc． of the 3th IEEE International Conference on Communication Software and Network Xi’an China May 27-29 2011 423-427． ， ， ， ， : ITU NGN2GSI Ｒapporteur Group． Ｒequirements for support of USN ［ ］ applications and services in NGN environment Ｒ ， ， ， communication Union Geneva Switzerland 2007． ． International Tele-  ( 上接第 24 页) 4 结 语 用于解决图着色问题的进化稳定策略蚁群算法利用变换因 子改进了基本启发式蚁群算法的信息素更新策略，并动态自适 应地调节启发式信息的作用，加速了算法的收敛并避免了陷入 局部最优解，在解决图着色问题上，充分发挥了算法的优越性， 希望在进一步的研究中，能够 取得了非常好的实例仿真效果 缩短进化稳定策略蚁群算法的运行时间，并将其应用于更多的 领域，发挥其优越性 。 。 图 7 谐波畸变率越限报警信息 参 考 文 献 4 结 语 本文设计了一种基于建筑设备物联网的分布式谐波在线监 测系统，详细介绍了系统的整体架构，给出了物联网节点和物联 网服务器的实现方法，并用具体应用实例验证了系统的功能 。 与其他离线监测或集中式在线监测系统不同，本系统可以对分 布于建筑内的多个配电回路或重要设备的谐波情况进行在线监 测，如果谐波畸变率超过规定的限定值可以实时报警，同时采用 技术将数据发布至互联网中，用户可以在浏览器上以图形 Web 虽然本方案主要用于监测建筑物 方式随时随地查看谐波数据 内的谐波状况，但也可增加对电压偏差 三相电压不 、 平衡度等其他电能质量指标的在线监测功能 我们下一步还计 划在现有的建筑设备物联网平台上进行扩展，将现有的建筑能 频率偏差 、 。 。 ［ 1 ］ ［ 2 ］ ［ 3 ］ ［ 4 ［ 5 ［ 6 ［ 7 Burris A C． Vertex-Distinguishing Edge-Colorings ， University 1993 ， Murty U S Ｒ． Graph Theory with Applications 118 － 129． Bondy A ， 12 ) : 7 ( ［ ］ M ． Macmil- ［ ］ D ． Memphis State lan Press Ltd． ， 1976． Bazgan C ， Harkat-Benhamdine A ， Li Hao ， et al． On the Vertex-Dis- ［ ］ J ． J． Combin． Theory tinguishing Proper Edge-Coloring of graphs ， 1999 Ser ］ 赵焕平 ( 2 ) : ， 75 ］ 若干图的点可区别强全染色的算法研究［ D ． 288 － 301． ． 2009． 图着色问题的启发式搜索蚂蚁算法［ ］ J ． ) : ． 交通大学， ］ 廖飞，马良 ( ， 33 2007 16 191 － 195． ］ 朱虎，宋恩民，路志宏 ］ ［ J ． 计算机仿真， ． 求解图着色问题的最大最小蚁群搜索算法 ， 27 190 － 192． ) : 3 ( 2010 ］ 章春芳 ］ 自适应的并行蚁群算法及其应用［ D ． ． 杨州大学， 2006． 兰州: 兰州 计算机工程，