关于最大团问题的一种新算法

摘要：最大团问题是图论中重要的NP完全问题，目前求解最大团问题的方法只适合某些特殊的图，活则消耗时间长，求解效率低。该文提出了一种新的算法，蚁群算法来解决最大团问题。蚁群优化算法是一种基于自然启发的算法，是一种解决组合优化问题的有效方法。实验结果显示，算法的有效性。

关键词：最大团；组合优化；蚁群算法

中图分类号：TP18文献标识码：A文章编号：1009-3044(2008)22-708-03

A New Algorithm for the Maximum Clique Problem

ZHOU Xiao-xiao, BAI Yang

(City College,Wenzhou University, Wenzhou 325035, China)

Abstract:The maximum clique problem is an important NP complete problem in graph theory.Prebious algorithms are either applicable only to some particular graphs or in need of exponential time cost. In this paper, an new algorithm-Ant Conlony Optimization(ACO) is presented,which is applied for MCP .ACO algorithm is a nature-inspired algorithm.It is an efficient tool for solving combinatorial optimization problem. Experimental results prove the effectiveness of the improvements.

Key words: Maximum clique; combinatorial optimization; Ant Conlony Optimization

1 引言

最大团问题(Maximum Clique Problem，MCP)是经典的组合优化问题之一，这不仅仅因为它最早被证明是 NP-完全问题之一，而且因为它在理论和实践上有着重要的意义。可以将很多不同的领域的问题转化为最大团问题来解决。它在编码理论、差错诊断、计算机图像、模式匹配、信号传输、人工智能、聚类分析、移动计算、故障诊断、信息恢复、生物信息学等许多领域都有着广泛的应用。最大团问题在国外有着广泛的研究，在国内还刚刚起步。对最大团问题的研究实际就是一个NP问题的研究，目前解决最大团问题的方法主要集中在多项式时间的近似算法上。有很多解决最大团问题的metaheuristic近似算法，比如模拟退火、禁忌搜索、人工智能等。此文主要介绍一种遗传算法DD蚁群算法，蚁群算法（ant colony algorithm， ACA）是受到自然界中真实的蚁群集体行为的启发而提出的一种基于种群的模拟进化算法，属于随机搜索算法。意大利学者Dorigo等人在20世纪90年代初首先提出该算法时，充分利用了蚁群搜索食物的过程与著名的旅行商问题之间的相似性，通过人工模拟蚂蚁搜索食物的过程来求解TSP，取得了较为理想的效果。它是一种应用与组合优化问题的启发式智能搜索算法。蚁群算法不仅能够智能搜索、全局优化、而且具有鲁棒性、正反馈、分布式计算、易与其它算法相结合等特点。由于蚁群算法基本原理与最大团的求解过程有相似之处，所以本文所研究的内容在理论上是具有可行性的。并根据蚁群算法的自身缺陷进行了改进，提出了一种新的解决最大团问题的算法，测试表明算法是可行性。

2 最大团问题的基本定义

2.1最大团问题基本定义

给定一个无向图G = (V,E)，其中V ={1,2,...,n}是顶点的集合，E?哿V×V 是它的边的集合。一个团（Clique）是顶点集V 的一个子集，记为C，C?哿V ，要求C 中任意两个顶点之间有边相连。也就是说由团C 中顶点及其边组成的子图是完全图。最大团问题就是要找到具有最多元素数的子集C 。而最大团问题的目标就是要找到给定图的最大团。

2.2 最大团问题的数学描述

设t:(0,1)n2v,t(x)={i∈v:xi=1}，?坌x∈(0,1)n，?坌S∈2V，

则x=t-1(S)={xi:i=1,2,…,n}，其中，n为图的顶点数。

（1）

St xi+xj≤1，?坌(i,j)∈E，x∈(0,1)n

如果x*是式（1）的最优解，那么集合C=t(x*)是图G的一个最大团，且|C|=-f(x*)。

由于xi，xj∈(0,1)，xi+xj≤1，?坌(i,j)∈E当且仅当xi xj=0。有。其中，A为图G的补图G的邻接矩阵。

MCP等价于下面的全局二次0－1问题

Min f(x)=xTAx（2）

St x∈(0,1)n

其中，A=A-I,如果x*是式（2）的最优解，那么集合C=t(x*)是图G的一个最大团，且|C|=-f(x*)。

3 基本蚁群算法

仿生学家经过大量地观察、研究发现，蚂蚁在寻找食物时，由大量蚂蚁组成的蚁群的集体行为表现出了一种信息正反馈现象：某条路径上经过的蚂蚁数越多，其上留下的外激素的迹也就越多（当然，随时间的推移会逐渐蒸发掉一部分），后来蚂蚁选择该路径的概率也越高，从而更增加了该路径上外激素的强度。蚂蚁个体之间就是通过这种信息的交流搜索食物，并最终沿着最短路径行进。蚁群优化算法就是模拟蚁群这一觅食行为的优化算法。蚁群算法主要包括两个基本阶段：适应阶段和协作阶段。在适应阶段，各候选解根据积累的信息不断调整自身结构，路径上经过的蚂蚁越多，信息素数量越大，则该路径越容易被选择，时间越长，信息素数量越少；在协作阶段，候选解之间通过信息交流，以期望产生性能更好的解。其协作方式的本质是：1)信息素踪迹越浓的路径，被选中的概率越大，即路径概率选择机制；2)路径越短，它上面的信息素踪迹增长得越快，即信息素更新机制；3)蚂蚁之间通过信息素进行通信，即协同工作机制。

3.1 蚁群算法在优化过程中的规则

1)蚂蚁在众多的路径中转移路线的选择规则：蚂蚁总是倾向于选择含有较多信息素的路径。这里信息素（Pheromone）类似于一种分布式的长期记忆，这种记忆不是局部地存在于单个的人工蚁，而是全局地分布在整个问题空间，这就导致了一种间接联络方式。

2)全局化信息素更新规则：在路径上的信息素，有一部分会被蒸发散失，这样没有被选择过的路径信息素越来越少，变得越来越不受欢迎。每只蚂蚁按路径的长短（或找到食物的质量）成比例地在属于其经过的路径上留下一定数量的信息素。信息素更新的实质就是人工蚂蚁根据真实蚂蚁在访问过的边上留下的信息素和蒸发的信息素来模拟真实信息素数量的变化，它使得越好的解答得到越多的增强。这就是为了更形象地模拟蚁群这种选择路径的过程时形成的自催化行为而成立的一种自催化强化学习机制。

3.2 蚁群算法的数学描述

假设X={Xi|Xi=(xi1,xi2,…,xim),i=1,2,…,N}是进行分析问题的数据集合。r为解的半径，phij(t)为t时刻数据Xi到数据Xj的路径上的信息素浓度，dij为样本与最佳解的加权欧氏距离，p为加权因子，可根据各分量在最佳解的求解中的影响程度而定。

则

（3）

设phij(0)=0为初始信息量，则

（4）

根据样本与最佳解之间的路径上的信息素浓度，

Xi归并到Xj的概率phij为：

（5）

其中，ηij(t)是启发式引导函数，表征蚂蚁Xi转移至Xj的期望程度，利用启发函数可反映像素之间的相似度，启发函数越大，像素归于相同解的概率就越大。α、β分别为像素求解过程中所积累的信息以及启发式引导函数对路径选择的影响因子。S={Xs|dsj≤r,s=1,2,…，j，j+1,…,N}；为可行路径集合。

若pij(t)≥p0，则Xi归并到Xj领域。设

Cj={Xk|dkj≤r,k=1,2,…,J},Cj表示所有归并到Xj领域的数据集合。求出理想的最佳解：

（6）

其中：Xk∈Cj

随着蚂蚁的移动，各路径上信息素的量发生变化，经过一次循环，按全局调整规则调整各路径上的信息素如下[5]：

Phij(t)=ρphij(t)+Δphij （7）

其中，ρ为信息素随时间的衰减系数，一般取0.5～0.99左右，Δphij为本次循环中路径信息素的增量。

（8）

Δph表示第k只蚂蚁在本次循环中留在路径中的信息素的量。

4 基于蚁群算法的最大团问题研究

4.1 最大团问题重新定义

为了将最大团问题的模型与蚁群算法的求解过程相一致，将最大团问题重新定义如下：

最大团的模型P=(G,S,Ψ,f,s*)由以下部分组成：

输入G：输入的问题为一个图G=(V,E),其中V是顶点结合，E∈V×V是边的集合。

解空间S:S定义于一组变量和变量的域之上。设X={X1,X2,…,Xn}是一组n个离散变量的集合，其中n=|V|，对于?坌Xi∈X，Di={0,1}(i=1,2,…,n)是变量Xi的域。对变量Xi的赋值用Xi=xi来表示。若xi=1，表示顶点i在当前所考虑的顶点集合中，反之，若xi=0，表示顶点i不在当前顶点集合中。一个可行解S是满足约束条件的X的一个完全赋值：X中的任意一个变量都被赋值。解空间则是所有可行解构成的集合，S={s={(X1,x1), (X2,x2),…, (Xn,xn)}|xi∈Di}，当s满足所有约束条件时。

变量的约束条件Ψ：根据最大团问题本身的特性，Ψ定义为：如果Xi=1，Xj=1，?坌i,j=1,2,…,n，且i≠i，则无向图G的边集E中必然有一条连接顶点i和顶点j之间的边。目标函数f的定义：f是一个可行解集合到正整数集合的映射f:SZ，对于一个给定的可行解s∈S，。全局最优解s*: s*∈S是有着最大目标函数值的可行解，即对于s*∈S，f(s*)≥f(s)，?坌s∈S。

重新定义的MCP模型的最佳解是一个满足一定约束条件的顶点集合，所以本文为了将最大团问题与蚁群解决的办法相关联，采取的是基于顶点的信息素模型。定义如下：Ф=(τ1,τ2,…,τn)，其中n=|V|，τi表示顶点i上积累的信息素的数量，其值越大意味着在构造极大团过程中该顶点被选择的概率越大。

4.2 应用蚁群算法解决最大团问题的步骤

应用蚁群算法解决最大团问题的流程如下所示：

procedure 组合优化问题的 ACO 算法

设置参数，初始化信息素分布；

while 不满足结束条件 do

for 蚁群中的每个蚂蚁

for 每个解构造步（直到构造出完整解）

蚂蚁按信息素及启发式信息的指引构造一步问题的解；

进行信息素局部更新（可选）；

end of for

end of for

以某些已获得的解为起点进行领域（局部）搜索（可选）；

根据某些已获得解的质量进行全局更新信息素；

end of while

end of procedure

说明：1)这里 while 循环中的“结束条件”一般由“达到最大循环次数”和“找到最优解了”两个条件确定，两个条件中任意一个满足均可结束 while 循环。所谓“找到最优解了”是指连续若干次找不到更好的解的，我们认为“找到最优解了”。2)“局部更新信息素”过程也称在线逐步（online step by step）的更新方式，它在每只蚂蚁构造一个完整的可行解之后进行，下一只蚂蚁构造解的过程就受更新后的信息素指引，与全局更新方式不同,全局更新是一种在线延迟（online delayed）的更新方式。

5 实验结果

在实验中，设置蚁群的种群大小为10，即相当于蚁群的大小m。种群的代数设置为5000，相当于蚁群优化算法中的最大迭代次数。其它参数设置为，α=0.001，Δ=3，λ=0.7，β=0.9。应用5个典型的MCP基准实例来测试本算法，实验在Window XP操作系统下，MATLAB7.0仿真结果显示，尽管本算法只设定为10个蚂蚁进行搜索比起更多的蚂蚁来搜索所得到的解的质量并没有降低，相比更多的蚂蚁进行搜索，算法减少了相当多的运行时间。实验结果见图1。

6 结论

蚁群算法作为一种新的启发式算法，它具有正反馈、分布式计算等特点，使其能够成功地解决许多组合优化问题。本文在详细介绍蚁群算法原理的基础上，对蚁群算法在组合优化问题中的应用进行了研究，主要应用蚁群算法求解最大团这个个经典的组合优化问题。通过改进方法,即将信息素留在顶点上，而非边上，这样仅节省了存储空间，更重要的是提高了运行速度；增加了局部启发信息，消除了迭代初期的盲目性；在同等运算规模下，提高了算法的求解速度和能力,也为以后更加深入研究蚁群算法奠定一定的基础。

参考文献：

[1] 彭沛夫.遗传融合的自适应蚁群算法研究[D]. 长沙:湖南大学,2005

[2] 李默.解决最大团问题的蚁群优化算法的研究与应用[D]. 哈尔滨:哈尔滨工业大学,2006.

[3] 贾晓峰,郭廷花,续晓欣.关于最大团问题的一种新算法[J].中北大学学报,2006,27(2):180-182.

[4] 仲盛,谢立.求解图的最大团的一种算法[J].软件学报,1999,10(3):288-292.

[5] 高尚.蚁群算法理论、应用及其与其他算法的混合[J].电子学报,2005(10).

[6] 温玉娟.蚁群算法在图象分割中的应用[J].电子学报,2005(10).

[7] 林亚平.基于遗传因子的自适应蚁群算法的研究[J].电子学报,2006(16).

[8] 付宇.蚁群优化算法的改进及应用[J].电子学报,2006(7).

[9] 高尚,蒋新姿,汤可宗,杨静宇.蚁群算法与粒子群优化的混合算法[J]. 电子学报, 2006,8

[10] 李利香.基于混沌蚁群算法的研究[J].仪器仪表学报,2006(9)

[11] 刘彦鹏.蚁群优化算法的理论研究及其应用[J].电子学报,2007(4).