第２７卷第１０期２０１０年１０月
计算机应用与软件
ＣｏｍｐｕｔｅｒＡｐｐｌｉｃａｔｉｏｎｓａｎｄＳｏｆｔｗａｒｅ
Ｖ０１．２７Ｎｏ．１０
Ｏｃｔ．２０１０
基于蚁群算法求解最大团问题
王会颖耿家礼
（安徽财贸职业学院计算机系安微合肥２３０６０１）
摘要最大团问题是一种典型的ＮＰ完全问题，是图论中一个经典的组合优化问题。研究将蚁群算法应用于求解最大团问题，
提出一种求解最大团问题蚁群算法。通过定义最大团问题蚁群算法中的各元素，并改进了蚂蚁搜索解的方法，有效地改善蚁群算法易于过早地收敛于局部最优解的缺陷。仿真实验表明，图中的顶点数较多时，也取得了较好的结果。关键词
最大团问题蚁群算法
最大团问题蚁群算法
ＳＯＬＶＩＮＧ
ＭＡＸＩＭＵＭＣＬＩＱＵＥＰＲＯＢＬＥＭ
ＢＡＳＥＤｏＮＡＮＴＣＯＬＯＮＹＯＰＴＩＭＩＺＡＴＩＯＮ
ＷａｎｇＨｕｉｙｉｎｇ
ＧｅｎｇＪｉａｌｉ
（Ｄｅｐａｒｔｍｅｎｔ矿Ｃｏｍｐｕｔｅｒ＆切Ｍ，ＡｎｈｕｉＦｉｎａｎｃｅ＆ＴｒａｄｅＶｏｃａｔｉｏｎａｌＣｏｌｌｅｇｅ，Ｈｅｆｅｉ２３０６０１，Ａｎｈｕｉ，Ｃｈｉｎａ）
Ａｂｓｔｒａｃｔ
Ｍａｘｉｍｕｍｃｈｑｕｅｐｒｏｂｌｅｍｉｓ
ａｎｔ
ａ
ｔｙｐｉｃａｌＮＰｃｏｍｐｌｅｔｅｐｒｏｂｌｅｍ，ａｎｄｉｓ
ｔｏ
ａ
ｃｌａｓｓｉｃａｌｐｒｏｂｌｅｍｏｆｃｏｍｂｉｎａｔｏｒｉａｌｏｐｔｉｍｉｚａｔｉｏｎｉｎｇｒａｐｈ
ｔｈｅｏｒｙ．Ｉｎｔｈｉｓｐａｐｅｒ，ｔｏａｐｐｌｙ
ｃｏｌｏｎｙｏｐｔｉｍｉｚａｔｉｏｎｒｅｓｏｌｆｉｎｇ
ｍａｘｉｍｕｍｃｌｉｑｕｅｐｒｏｂｌｅｍｉｓｒｅｓｅａｒｃｈｅｄ，ａｎｄａｎａｌｇｏｒｉｔｈｍｏｆａｎｔｃｏｌｏｎｙｏｐｔｉ—
ｍｉｚａｔｉｏｎｆｏｒｓｏｌｖｉｎｇｍａｘｉｍｕｍｃｌｉｑｕｅｍｅｎｔ
ｏｎ
ｐｒｏｂｌｅｍ（ＡＣＯＭＣＰ）ｉｓｐｕｔｆｏｒｗａｒｄ．ＷｉｔｈｔｈｅｄｅｆｉｎｉｔｉｏｎｏｆｅａｃｈｅｌｅｍｅｎｔｉｎＡＣＯＭＣＰａｎｄｔｈｅｉｍｐｒｏｖｅ—
ｄｉｓａｄｖａｎｔａｇｅｏｆｅａｓｉｌｙｆａｌｌｉｎｇｉｎｔｏｌｏｃａｌｂｅｓｔｔｈｅ
ｍｏｒｅｎｕｍｂｅｒｓｏｆｔｈｅｖｅｒｔｅｘ，ｉｔ
ａｎｔ
ｔｈｅ
ｗａｙ
ｔｈｅ
ａｎｔ
ｓｅａｒｃｈｅｓｉｔｓｓｏｌｕｔｉｏｎｓ．ｔｈｅ
ｃｏｌｏｎｙｏｐｔｉｍｉｚａｔｉｏｎ
ｈａｓｉｓｅｆｆｅｃｔｉｖｅｌｙ
ａ．
ｍｅｌｉｏｒａｔｅｄ．Ｓｉｍｕｌａｔｉｏｎｒｅｓｕｌｔｓｓｈｏｗｅｄ，ｗｈｅｎｔｈｅｒｅ
Ｍａｘｉｍｕｍｃｌｉｑｕｅｐｒｏｂｌｅｍ
ａｒｅ
Ｃａｎ
ａｌｓｏａｃｈｉｅｖｅｆａｉｒｌｙｇｏｏｄｅｆｆｅｃｔ．
Ｋｅｙｗｏｒｄｓ
Ａｎｔｃｏｌｏｎｙｏｐｔｉｍｉｚａｔｉｏｎ
Ａｎｔｃｏｌｏｎｙｏｐｔｉｍｉｚａｔｉｏｎｆｏｒ
ｓｏｌｖｉｎｇｍａｘｉｍｕｍｃｌｉｑｕｅｐｒｏｂｌｅｍ（ＡＣＯＭ・
ＣＰ）
质的强度成正比。当一条路径上通过的蚂蚁越来越多时，其留
０引言
下的信息素也越来越多，后来蚂蚁选择该路径的概率也越高，从而更增加了该路径的信息素强度。而强度大的信息索会吸引更多的蚂蚁，从而形成一种正反馈机制。通过这种正反馈机制，蚂蚁最终可以发现最短路径“。
以ＴＳＰ为例说明基本蚁群算法ＡＣＯ（ａｎｔ
ｃｏｌｏｎｙ
ｏｐｔｉｍｉｚａ－
最大团问题是一类ＮＰ完全问题，也被称为最大独立集问题。它的应用领域包括市场分析、方案选择、信号传输、计算机视觉和故障诊断等。研究它有很大的理论价值和实践价值。传统的确定性算法不能有效地进行求解最大团问题，因此好多学者提出了各种各样的启发式算法求解该问题。目前国内使用启发式算法求解最大团问题的研究还处于起步阶段¨。。
蚁群算法是一种新型仿生类进化算法，是继模拟退火、遗传算法、禁忌搜索等之后的又一启发式智能优化算法，具有很强的通用性和鲁棒性。意大利学者ＤｏｒｉｇｏＭ等于１９９１年最早提出蚁群算法，１９９２年，ＤｏｒｉｇｏＭ又在其博士论文中进一步阐述其核心思想门１。蚁群算法成功地应用于求解ＴＳＰ、二次分配、着色、车辆调度、集成电路设计及通信网络负载等问题。蚁群算法从提出到现在，因其在求解组合优化问题中突出表现，吸引了人们的极大关注。
ｔｉｏｎ）。ＴＳＰ描述为，已知，１个城市及各城市间的距离，求一条经过各城市一次且仅一次的最短的Ｈａｍｉｌｔｏｎ回路。
设有ｎ个城市，ｍ只蚂蚁，任意两城市ｉ、，之间的距离为ｄ（ｉＪ），ｒ（ｉ√）表示两个城市ｉ√之间信息素的浓度。初始时刻，各信息素的浓度相同。蚂蚁ｋ从城市ｉ转移到另一个城市』的
概率为Ｐ：，其计算式如式（１）所示。其中，Ｊ（ｋ）为蚂蚁ｋ在城市
ｉ时，还没有访问过的城市集合。启发函数田（ｉ，Ｊ）＝１／ｄ（ｉ，Ｊ）。ａ≯ｐ为参数。
ｌ∑［ｒ（√）］４・［＇７（ｉＪ）］４
Ｐｉ３…１
５｛『∈．，（％）
。
。ｆ揣特揣㈦＾…，ｎ
’。－’
”’
Ｆ
１
【０
其它
ｒ（ｉＪ）＝ｇｒ（ｉ√）＋△ｆ（ｉ√）
（２）
１基本蚁群算法
蚂蚁有能力在没有任何提示下找到从其巢穴到食物源的最短路径，并且能随环境的变化，适应性地搜索新的路径，产生新的选择。根本原因是蚂蚁在寻找食物源时，能在其走过的路上释放一种特殊的分泌物一信息素，随着时间的推移该物质会逐渐挥发，后来的蚂蚁选择该路径的概率与当时这条路径上该物
信息素更新式为式（２）。其中，Ｔ（ｉ，ｊ）表示城市ｉ，，之间的信息素的浓度，１－ｐ（０＜ｐ＜１）表示信息素的挥发程度，Ａ＇ｒ（ｉ，Ｊ）＝ｌ／ｌｍｂ，ｌｍｂ为一代中蚂蚁找到的最短路经的长度。信息素
收稿日期：２００９—０２—１５。安微省自然科学基金项目（Ｋ．１２００８Ｂ０２１）。王会颖。讲师。主研领域：智能软件，群体智能。
１０８
计算机应用与软件
２０１０点
的处理方式为：一代中仅对周游路径长度最短的蚂蚁所经过的路径进行信息素的修改增加，其余衰减，Ａｔ（ｉ）＝１／ｌｍｂ，ｌｍｂ为一代中蚂蚁找到的最短路径的长度。
算法ＡＣＯ简单描述如下：
①初始化。设定各参数值，蚂蚁个数ｍ，最大进化代数腑，信息素．ｒ（ｉ√）＝ｌ。
②每只蚂蚁独立地构造一个解。蚂蚁ｋ随机选择一个城
市ｉ作为起点，开始周游。根据概率公式（１）计算概率Ｐ：，按概率Ｐ：大者选择下一个城市Ｊ，蚂蚁ｋ从ｉ转移到下～个城市Ｌ若
蚂蚁ｋ周游的当前路径长度大于本代求得最短路径长度，结束此只蚂蚁的周游，否则，继续寻找下一个城市，直到蚂蚁ｋ访问完所有的城市。
③若ｍ只蚂蚁都构造完成各自的解，则转④，否则转②。④根据周游路径长度最小的蚂蚁，按式（２）及信息素的处理方式进行全局信息素更新。
⑤若满足结束条件，则输出最优解，否则ＧＥＮ＝ＧＥＮ＋１，转②。结束条件为ＧＥＮ＞Ａｒｃ或当前解已稳定。
２最大团问题
给定一个无向图Ｇ＝（ｙ，Ｅ）。如果Ｕ∈Ｖ，且对任意ｕ，ｔＪ∈Ｕ有（Ⅱ，口）∈Ｅ，则称Ｕ是Ｇ的一个完全子图。Ｇ的完全子图Ｕ是Ｇ的一个团，当且仅当Ｕ不包含在Ｇ的更大的完全子图中。Ｃ的最大团是指Ｇ中所含顶点数最多的团‘“。
图１无向图Ｇ
在图１无向图Ｇ中，子集｛ｌ，２｝是Ｇ的一个大小为２的完全子图。这个完全子图不是一个团，因为它包含于Ｇ的更大的完全子图｛ｌ，２，５｝之中。ｔ１，２，５｝是Ｇ的一个最大团。｛ｌ，４，５｝和｛２，３，５｝也是图Ｇ的最大团‘”。
３求解最大团问题蚁群算法
３．１
求解最大团问题蚁群算法中各元素的定义
本文提出求解最大团问题蚁群算法ＡＣＯＭＣＰ（ａｎｔ
ｃｏｌｏｎｙ
ｏｐｔｉｍｉｚａｔｉｏｎｏｆｓｏｌｖｉｎｇｎｌ／ｌ】【ｉｍｕｍｃｌｉｑｕｅ
ｐｒｏｂｌｅｍ）。在ＡＣＯＭＣＰ
中，每个顶点作为一个信息素载体，信息素积累在顶点上；一代迭代后，每只蚂蚁构造出一个可行解（团），第☆只蚂蚁形成团ｕ，Ｕ＝｛菇¨’菇托，…，鬈ｋ｝，其中，％＝ｉ表示第ｋ只蚂蚁第Ｊ次选中顶点ｉ，ＩｕＩ表示第ｋ只蚂蚁构造的团所包含的顶点数，即团的阶数。
设无向图Ｇ＝（Ｖ，Ｅ），有ｎ个顶点，图的存储结构采用邻接
矩阵删，堋（ｉ√）＝ｌ表示顶点ｉ和顶点，相邻接，ａｒｃｓ（ｉ√）＝０
表示顶点ｉ和顶点，不相邻接。顶点ｉ的度数为ｄｅｇｒｅｅ（ｉ）。启发函数叩定义为和顶点相关联的边数，即顶点的度数，田（ｉ）＝ｄｅｇｒｅｅ（ｉ）。目标函数为各蚂蚁构造的团中，团的阶数ＩｕＩ的最大值。
蚂蚁ｋ求解时，从一个顶点ｉ转移到下一个顶点Ｊ的概率，按式（３）计算，其中，ｒＵ）为ｔ时刻积累在顶点＿『上的信息素的浓度，
Ｊ（ｋ）为蚂蚁ｋ可以转移的下一个顶点的集合。集合．，（ｋ）中的每个顶点ｊ要满足三个条件：①顶点Ｊ不包含在蚂蚁ｋ形成的当前解｛髫…毒垃，…，％｝中；②顶点Ｊ和蚂蚁ｋ已求得的当前解中的每个顶点相邻接；③顶点门砸ｉ邻接，即ａｒｃｓ（ｉｄ）＝ｌ。
扣ｆ蚩黼Ｉｎ（Ｊ）
硝＝ｊ∑［ｆｕ）］。×
］４
川㈩（３）
一“”。
（３）
ｒ’
ｏｌｈ盯
信息素的更新仅采用全局更新的方式，一代中仅对所含顶点数最多的团中所含的顶点进行信息素的修改增加，其余衰减。更新为式（４），其中，ｌｍｂ为一代中蚂蚁找到的顶点数最多的团的阶数。
ｒ‘（ｔ＋１）＝ｐ＿ｒ。（ｔ）＋△ｆ（ｉ）
（４）
其中：
甜¨卜１０．…
ｒＩｍｂ／ｎ顶点ｉ属于一代中蚂蚁找到顶点数最多的团
其他
３．２对基本蚁群算法的改进
根据式（１）计算出集合Ｊ（ｋ）中所有顶点的概率，基本蚁群算法一般是选取概率大者作为下一个顶点。这样虽然强化了启发函数和信息素的引导，但是，容易出现停滞现象，过早地收敛于局部最优解。在蚁群算法中，信息素的加强形成正反馈机制，从而使可行解一步一步地向好解进化。同时也要增加搜索的随机性，兼顾解空间的各种情况，才能搜索到较好解，冲出局部最优解，向全局最优解进化。
基于上述分析，最大团问题蚁群算法改进蚂蚁选择下一个顶点的方式，采用最大原则或轮盘赌两种选点方式：给定参数ｑｏ（Ｏ≤ｑ０＜１），生成随机数ｇ（Ｏ≤ｇ＜１）。
（１）当ｇ≤ｇｏ时，蚂蚁按最大原则选点，按式（５）计算，蚂蚁选取［ｒ（ｊ）］４×［叼（Ｊ）］９达到最大的集合Ｊ（奄）中的顶点。
ｌＩ娜（［ｆ（Ｊ）］４×［ｎ（Ｊ）］４），∈Ｊ（ｋ）（５）
（２）当ｑ＞ｑ。时，按概率算式（３）计算集合．，（七）中所有顶点的概率，然后采用轮盘赌的方式选点，这样既兼顾了概率大小，又增加了搜索的随机性。轮盘赌的伪代码描述如下：
①生成一随机数ｒ，Ｏ《ｒ＜ｌ，．『＝０，，＝ｐ，；②如果／≥ｒ，则转④；⑤ｊ＝ｊ＋ｌＪ＝ｆ＋ｐ；，辕②；④选取点Ｊ，输出，结束。
对上述给定的参数％采用动态改变的方式。在进化的前期，由于初始信息素匮乏，信息素还不能很好地起到弓ｌ导作用，
ｑ０取较大的值，这样蚂蚁较多按最大原则选点，减少蚂蚁的盲目搜索，蚂蚁容易找到较好的解，缩短搜索时间，加快收敛速度。在进化的后期，ｑ。取较小的值。蚂蚁较多依据概率按轮盘赌方法选取下一个顶点，增加搜索的随机性，能有效地突破局部最优解，改善停滞现象，向最优解转化。
３．３最大团问题蚁群算法分析
求解最大团问题蚁群算法描述如下：
①初始化。设定各参数的值，蚂蚁的个数ｍ，最大进化代数Ⅳｃ，当前进化代数ＧＥＮ＝０，各顶点初始信息素的浓度下（ｉ）＝
１，ｉ＝１，２，…，，Ｉ。
②蚂蚁Ｉ｜｝（ｋ＝ｌ，２，…，ｍ）随机选择一个顶点ｉ为初始起点，
放入解向量，ｓｏｌｕｔｉｏｎｓ（１）＝ｉ，舶Ⅱ（ｉ）＝ｌ，团的阶数ｓ＝ｌ。
③每只蚂蚁独立地构造一个团。生成蚂蚁ｋ从顶点ｉ可转移的下一个顶点的集合．，（．｜｝）；若＿，（ｋ）为不空，生成随机数ｑ，若
第１０期王会颖等：基于蚁群算法求解最大团问题
１０９
ｑ＜。ｑｏ，蚂蚁按最大原则选点，，否则，蚂蚁按轮盘赌的方式选点Ｊ；将顶点Ｊ放入蚂蚁ｋ求得的解ｓｏｌｕｔｉｏｎｓ中，ｔａｂｕ（，）＝Ｉ，团的阶数ｓ＝ｓ＋１。如此循环，直到蚂蚁后可转移的下一个顶点的集合Ｊ（ｋ）为空。ｑ０进化初期取值较大，后期较小，动态变化。
④若蚂蚁ｋ形成的团的阶数大于当代最优团的阶数，保存＆形成的团为当代最优团。
⑤若ｍ只蚂蚁都构造完成各自的团，则转⑥，否则转②。⑥根据本代的最优团，按（４）式进行全局信息素更新。⑦若本代最优团阶数大于进化以来的全局最优团阶数，保存本代最优团为全局最优团。
⑧若达到一定的代数或解已稳定，则输出最优解；否则ＧＥＮ＝ＧＥＮ＋１，转②。
在求解ＴＳＰ问题基本蚁群算法ＡＣＯ中，算法的时间复杂度Ｔ（，１）＝ｏ（Ｎｃ・ｎ２・ｍ）；空间复杂度Ｓ（ｎ）＝ｏ（１７，２）＋Ｏ（／／，・ｍ）¨０｜。ＡＣＯ和ＡＣＯＭＣＰ的时间复杂度比较如下：在初始化步骤上，ＡＣＯ为Ｏ（，１２），ＡＣＯＭＣＰ为Ｏ（，１）；在每只蚂蚁独立构造一个解步骤上，ＡＣＯ为Ｏ（ｎ２），ＡＣＯＭＣＰ为Ｏ（ｒ／．２）；在信息素更新步骤上，ＡＣＯ为Ｏ（，１２），ＡＣＯＭＣＰ为Ｏ（／７，）。在ＡＣＯＭＣＰ中，虽然总体时间复杂度没变，但在初始化，信息素更新步骤上，从ＡＣＯ的０（，１２）降低到ＡＣＯＭＣＰ的Ｏ（ｎ）。在ＡＣＯＭＣＰ中，启发函数、信息素、解向量、概率、禁忌表均为一维向量。空间复杂度Ｓ（ｒｔ）＝Ｏ（／１．）。因此，最大团问题蚁群算法时间复杂度Ｔ（／１，）＝０（Ｎｃ・／７，２・ｍ）；空间复杂度Ｊｓ（ｎ）＝Ｏ（珏）。
顶点数１１
８８
实例文献７，图１
文献６。图９
文献
ＡＣＯＭＣＰ求解结果最大团
１，２，６，７２，３，５，６，７１，２，３，４，５，６，７，８，９，１０
回溯算法
时间
Ｏ．０００３０．Ｏ００３
阶数
４５
阶数代数
４５
ｌ１
阶数时间
４５
Ｏ．０００ｌＯ．０００ｌ
１４
文献６，图２
１０１０ｌＯ．００２５１００．００３５
２０
文献５
３
０。６，７或０，６，１１或０，６，１４或Ｄ。１４，１５或３，８，１６或３，１６，１９或４。６，１１
３ｌ０．００１０３Ｏ．００１３
表２回溯算法、ＡＧＯＭＣＰ对ＤＩＭＡＣＳ中的实例的求解结果比较
ＤＪＭＡＣＳ
顶点数
ｎ
边数
９４３５２２５９９０
实例
Ｋｅｌｌｅｒ一４Ｋｅｌｌｅｒ一５
ＡＣＯＭＣＰ求解结果阶数个数代数
ｌｌ２７
９２１０
ｌ７１
列溯算法
阶数
ｌｌ２７
时间
Ｏ．４０８７８１２．４２１９
阶数
１ｌ
时间
１７８．２６２２
１７Ｉ７７６
表３ＡＣＯＭＣＰ算法求解实例ｋｅｌｌｅｒ－５得到的１０个不同的阶数为２７的最大团
３６４０４２５２６３Ｊ４６１９８２３９３０９３１２３２６３２８３４４４２２４２８４３０４６ｌ４７２５００５３７６６５７２９７４６７４９７５３７７ｌ７７５３６４０４２５２６３１４６１９８２３９３０９３１２３２６３２８３４４３７２４２２４２８４３０
４６ｌ４７２５３７６６５７２９７４６７４９７５３７７ｌ７７５
３４４３９０
４仿真实验
实验数据来源分为二部分：第一部分采用美国离散数学及理论计算科学中心ＤＩＭＡＣＳ提供的ＤＩＭＡＣＳ基准图中的ｋｅｌｌｅｒ４实例和ｋｅｌｌｅｒ５实例。ＤＩＭＡＣＳ基准图可通过登录ｔｉｐ：／／ｄｉｍａｅｓ．Ｒｕｇｅｒｓ．ｅｄｕ／ｐｕｂ／ｃｈａｌｌｅｎｇ／或者ｈｔｔｐ：／／ｄｉｍａｃｓ．Ｒｕｔｇｅｒｓ．ｅｄｕ／ｃｈａｌ—ｌｅｎｇｅｓ／获得。实例ｋｅｌｌｅｒ４和ｋｅｌｌｅｒ５数据在ｆｔｐ：／／ｄｉｍａｅｓ．Ｒｕｔ－ｇｅｍ．ｅｄｕ／ｐｕｂ／ｃｈａｌｌｅｎｇ／ｇｒａｐｈ／ｃｏｎｔｒｉｂｕｔｅｄ／ｓｈｏｔ／ｑａ。
第二部分实验数据采用文献［５—９］提供实例数据。实验运行环境为：Ｐｅｎｔｉｕｍ
０
４ｌ４４４８６６７０１６ｌ２３９２７２３０９３１２３２６３２８
４２２４２８４３０４６１４７２５３７６５０７２９７４ｌ７４５７４７７５７７６８４ｌ４４４８６６７０１６ｌ２３９２７２３０９３１２３２６３２８３４４３９０４２２４２８４３０
４６ｌ４７２５３７６３２６５０７４ｌ７４５７４７７５７７６８
３４４４２２
４ｌ４４４８６６７０１６ｌ２３９２７２３０９３１２３２６３２８４２８４３０４ｌ
４６ｌ４７２５１８５３７６５０７２９７４１７４５７４７７５７７６８
４４４８６６７０１６ｌ１８３２３９３０９３１２３２６３２８３４４３９０
４２２４２８４３０４６ｌ４７２５３７６３２６５０７４ｌ７４５７４７７５７７６８４ｌ
４４４８６６７０１６１１８３２３９３０９３１２３２６３２８３４４４２２
１～６
４，２．２６Ｇ
ＣＰＵ，５１２Ｍ内存，ｊｄｋ
４２８４３０４６１４７２５１８５３７６５０７２９７４ｌ７４５７４７７５７７６８４１
１１，Ｅｃｌｉｐｓｅ．ＳＤＫ－３．４．１，Ｊａｖａ编程。实验参数：蚂蚁数ｍ
４４４８６６７０１６１１８３２３９３０９３１２３２６３２８３４４４２２
＝ｎ，瑾＝１，Ｂ＝ｌ，Ｐ＝Ｏ．９，Ｔ＿ｌｌｌａＸ＝ｌ，ｘ＿ｍｉｎ＝０．０００００００１，最大进化代数为２００，ｑＯ在进化初期取０．８，中期取０．６，后期取０．４。
实验比较回溯算法’４。和最大团问题蚁群算法的求解质量和求解时间。在求解质量上，ＡＣＯＭＣＰ取得了回溯算法精确求解得到的最优值，全部最优解。但在求解时间上，当问题规模较大时，ＡＣＯＭＣＰ求解时间远远小于回溯算法，取得较好的效果。实验结果如表Ｉ一表３和图２所示，其中，时间单位均为秒，代数为蚂蚁求得最优解进化的平均代数。
用文献Ｅ５—９］提供的实例对ＡＣＯＭＣＰ、回溯算法进行测试，表１给出求解结果比较，其中，时间均为求得一个最优解的平均时间。结果表明，ＡＣＯＭＣＰ均容易求得其最优值和最优解。
表１
顶点
ＡＣＯＭＣＰ和回溯算法及文献［５—９］结果的比较
４２８４３０４６ｌ４７２５１８５３７６３２６５０７４ｌ７４５７４７７５７７６８４１４４４８６６７０１６１２３９２７２３０９３１２３２６３２８
３４４４２２
４２８４３０４６ｌ４７２５１８５３７６３２６５０７４１７４５７４７７５７７６８４ｌ４４４８６６７０１６１１８３２３９３０９３１２３２６３２８３４４３９０４２２４２８４３０
４６ｌ４７２５３７６５０７２９７４１７４５７４７７５７７６８
数ｎ
６
实例文献９，图２。
（ａ）
文献阶数
４
ＡＣＯＭＣＰ求解结果
最大团
回溯算法
时间
Ｏ．０００２
阶数代数
４
ｌ
阶数
４
时间
０
０，２，３，４或
０，１，２，３
图２ＡＣＯＭＣＰ求解ｋｅｌｌｅｒ－５每代的进化情况
用ＤＩＭＡＣＳ基准图中的ｋｅｌｌｅｒ４和ｋｅｌｌｅｒ５测试实例对
４
０．０００ｌ
８
文献８，
４
２，４，５，７
４１０．ｏ（）０３
（下转第１１３页】
第１０期李政：主动学习在基于内容的遥感影像检索中的应用
１１３
时间；ＡＣＯＭＣＰ个数为ＡＣＯＭＣＰ求得的不同最大团的个数，
５结论
本文提出的融合主动学习和ＳＶＭ的主动集成学习算法
经实验表明，可进一步减少所需标记样本的数量，同时能够最大程度地缩减变型空间，能有效地改善学习器性能，从而能快速准确地捕捉到用户查询概念。下一步将对该算法的适应性进行深入研究和验证。
ＡＣＯＭＣＰ时间为在连续ｌＯ次求解中，求得第一个最优解所用的平均时间，如Ｋｅｌｌｅｒ－５实例，求得第一个最优解的平均代数为７１代，每代进化的平均时间为１１．４９８９秒，ＡＣＯＭＣＰ时间为７１×１１．４９８９＝８１６．４２１９秒。可以看出，对Ｋｅｌｌｅｒ－４实例，ＡＣＯＭＣＰ求解质量同于回溯算法。但求解时间远远小于回溯算法，从回溯算法的１７０８．２６２２秒降低到０．４０８７秒。对Ｋｅｌｌｅｒ－５实例，ＡＣＯＭＣＰ顺利求解，而回溯算法求解困难。实例ｋｅｌｌｅｒ－４用ＡＣＯＭＣＰ得到了阶数为１１的９２个不同的最大团。对实例ｋｅｌ—ｌｅｒ－５用ＡＣＯＭＣＰ得到的阶数为２７的１０个不同的最大团在表３
ｉｍａｇｅ
参考文献
［１］Ｓｍｅｕｌｄｅｒｓ
ｔｈｅ
ｅａｒｌｙ
Ａ
ＷＭ，ｅｔａ１．Ｃｏｎｔｅｎｔ—ｂａｓｅｄ
Ｔｒａｎｓａｃｔｉｏｎｓ
ｏｎ
ｒｅｔｒｉｅｖａｌ
ａｔ
ｔｈｅｅｎｄｏｆ
中给出。
图２中，横坐标表示ＡＣＯＭＣＰ进化的代数，纵坐标表示团的阶数，图２反映了ＡＣＯＭＣＰ求解过程中团的阶数随代数的变化情况，算法在第７３代已达到了稳定，求解效率较高。
ｙｅａｒｓ．ＩＥＥＥ
ＰａｔｔｅｒｎＡｎａｌｙｓｉｓａｎｄＭａｃｈｉｎｅ
Ｉｎｔｅｌｌｉｇｅｎｃｅ。２０００。２２（１２）：１３４９—１３８０．
［２］ＳａｌｔｏｎＧ，Ｂｕｄｄｅｙｃ．Ｉｍｐｒｏｖｉｎｇｒｅｔｒｉｅｖａｌｐｅｒｆｏｒｍａｎｃｅｂｙｒｅｌｅｖａｎｃｅ
ｆｅｅｄｂａｃｋ．Ｊｏｕｒｎａｌ
ｏｆ
ｔｈｅＡｍｅｒｉｃａｎ
ｓｏｃｉｅｔｙ
ｆｏｒｉｎｆｏｒｍａｔｉｏｎ
ｓｃｉｅｎｃｅ，
１９９０，４１（４）：２８８—２９７．
［３］张健沛，徐华．支持向量机（ＳＶＭ）主动学习方法研究与应用．计
算机应用，２００４（１）：ｌ一３．
［４］徐杰．基于小样本学习的图像检索研究［Ｄ］．上海：上海交通大
学，２００４．
［５］张学工．关于统计学习理论与支持向量机．自动化学报。２０００，２６
（１）：３２—４２．
［６］ＦｒｅｕｎｄＹ，ＳｅｕｎｇＨ，ｅｔａ１．Ｓｅｌｅｃｔｉｖｅｓａｍｐｌｉｎｇ
ｍｉｔｔｅｅ
ｕｓｉｎｇ
５结论
本文研究利用蚁群算法求解最大团问题，提出了求解最大团问题蚁群算法。应用蚁群算法原理及算法模型对求解最大团问题进行建模，定义了最大团问题蚁群算法中的各元素。对基本蚁群算法进行改进，改进蚂蚁选择下一个顶点的方式，依据动态参数，采用最大原则或轮盘赌方式。这样，在进化前期蚂蚁较多按最大原则选点，蚂蚁容易找到较好的解，减少蚂蚁的盲目搜索，缩短搜索时间，加快收敛速度；在进化后期，蚂蚁较多依据概率按轮盘赌方法选取下一个顶点，既兼顾了概率大小，又增加了搜索的随机性，兼顾解空间的多种情况，有效改善蚁群算法易于过早地收敛于局部最优解的缺陷。对ＡＣＯＭＣＰ进行分析，其时间复杂度为Ｏ（Ⅳｃ・，１２・ｍ），空间复杂度为０（ｎ）。仿真实验比较ＡＣＯＭＣＰ和回溯算法及文献［５—９］的结果，并用ＤＩＭＡＣＳ基准图中的ｋｅｌｌｅｒ４和ｋｅｌｌｅｒ５测试实例对ＡＣＯＭＣＰ、回溯算法进行测试。实验结果表明，ＡＣＯＭ－ＣＰ算法取得较好的求解速度和求解质量。将最大团问题蚁群算法和其它算法融合，进一步改进算法的求解效率和求解质量，是需要进一步研究的问题。
ｔｈｅ
ｑｕｅｒｙｂｙ
ｏ｛Ｍｎ［ｉ－
ａｌｇｏｒｉｔｈｍ．ＭａｃｈｉｎｅＬｅａｒｎｉｎｇ，１９９７。２８：１３３—１６８．
ｆｏｒｔｒａｉｎｉｎｇ
［７］ＤａｇａｎＩ，ＥｎｇｅｌｓｏｎＳ．Ｃｏｍｍｉｔｔｅｅ・ｂａｓｅｄｓａｍｐｌｉｎｇ
ｔｉｃ
ｏｎ
ｐｒｏｂａｂｉｌｉｓ－Ｃｏｎｆｅｒｅｎｃｅ
ｃｌａｓｓｉｆｉｅｒｓ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓｏｆｔｈｅｔｗｅｌｆｔｈ
ＭａｃｈｉｎｅＬｅａｒｎｉｎｇ．１９９５：１５０—１５７．
Ｉｎｔｅｒｎａｔｉｏｎａｌ
［８］ＣｏｈｎＤ，ＡｔｌａｓＬ，ＬａｄｎｅｒＲ．Ｉｍｐｒｏｖｉｎｇｇｅｎｅｒａｌｉｚａｔｉｏｎｗｉｔｈ
ｉｎｇ．Ｍａｃｈｉｎｅ
ａｃｔｉｖｅｌｅａｒｎ－
Ｌｅａｒｎｉｎｇ，１９９４，１５（２）：２０１—２２１．
ｓｅｑｕｅｎｔｉａｌ
［９］ＬｅｗｉｓＤ，ＧａｌｅＷＡ．Ａ
ａｌｇｏｒｉｔｈｍ
ｆｏｒ
ｔｒａｉｎｉｎｇ
ｔｅｘｔ
ｃｌａｓｓｉｆｉｅｒｓ
ｆＣ］／／Ｐｎ）ｅ．ＯｆｔｈｅＳｅｖｅｎｔｅｅｎｔｈＡｎｎｕｍＩｎｔｌ．ＡＣＭ．ＳＩＧＩＲＣｏｎｆ．Ｒｅ．
ｓｅａｒｃｈ
ａｎｄ
Ｄｅｖｅｌｏｐｍｅｎｔ
ｉｎ
Ｉｎｆｏｒｍａｔｉｏｎ
Ｒｅｔｒｉｅｖａｌ，Ｓｐｒｉｎｇｅｒ－
Ｖｅｄ％，１９９４．
［１０］刘宏，屠轶清，黄上腾．一种新的支持向量机主动学习策略及其
在文本分类中的应用．计算机科学，２００３，３０（６）：１１０一１１２．［１１］Ｔｏｎｇｓ，ＫｏｌｌｅｒＤ．Ｓｕｐｐｏｒｔ
ｃａｔｉｏｎｓ
ｔｏ
Ｖｅｃｔｏｒ
Ｍａｃｈｉｎｅ
ｏｆ
Ａｃｔｉｖｅ
ＬｅａｒｎｉｎｇｗｉｔｈＡｐｐｌｉ・
ＴｅｘｔＣｌａ∞ｉｉｉｃａｔｉｏｎ．Ｊｏｕｒｎａｌ
ＭａｃｈｉｎｅＬｅａｒｎｉｎｇＲｅｓｅａｒｃｈ．
２００１，２：４５—６６．
参考文献
［１］周旭东，王丽爱，陈岐．启发式算法求解最大团问题研究［Ｊ］．计算
机工程与设计，２００７，２８（１８）：４３２９—４３３２．
（２］ＤｏｒｉｇｏＭ．Ｏｐｔｉｍｉｚａｔｉｏｎｌｅａｒｎｉｎｇａｎｄｎａｔｕｒｅａｌｇｏｒｉｔｈｍ［Ｄ］．ＰｈＤ．Ｔｈｅ－
ｓｉｓ，ＤｅｐａｒｔｍｅｎｔｏｆＥｌｅｃｔｒｏｎｉｃｓ，ＰｏｌｉｔｅｃｎｉｅｏｄｉＭｉｌａｎｏ，Ｉｔａｌｙ，１９９２．
ｓｕｐｐｏｒｔ
ｖｅｃｔｏｒ
［１２］Ｍｉｔｃｈｅｌｌ
Ｔ
Ｍ．Ｇｅｎｅｒａｌｉｚａｔｉｏｎ鹊Ｓｅａｒｃｈ．ＪｏｕｒｎａｌｏｆＡｒｔｉｔｌｃｉａｌＩｎｔｅＲｉ－
ｇｅｎｃｅ．１９８２．１８：２０３—２２６．
［１３］ＭｉｔｃｈｅｌｌＴ．ＭａｃｈｉｎｅＬｅａｒｎｉｎｇ．ＭｃＧｒａｗＨｉｌｌ。１９９７．［１４］Ｔｏｎｇｓ，ＣｈａｎｇＥ．Ｓｕｐｐｏｒｔ［１５］ＳｃｈｏｈｎＧ，ＣｏｈｎＤ．Ｌｅｓｓ
ｖｅｃｔｏｒ
ｍａｃｈｉｎｅａｃｔｉｖｅ
ｌｅａｒｎｉｎｇｆｏｒｉｍａｇｅ睁
ｔｒｉｅｖａｌ．ＡＣＭＭｕｌｔｉｍｅｄｉａ。Ｏｔｔａｗａ，Ｃａｎａｄａ，２００１．
ｉｓ
ｍｏｒｅ，Ａｃｔｉｖｅ
ｌｅａｒｎｉｎｇｗｉｔｈ
［３］丁建立，陈增强，袁著祉．遗传算法与蚂蚁算法的融合［Ｊ］．计算机
研究与发展，２００３。４０（９）：１３５１—１３５６．
［４］王晓东．计算机算法设计与分析［Ｍ］．２版．北京：电子工业出版
ｍａｃｈｉｎｅｓ［Ｃ］／／Ｐｒｅｃ．ｏｆｔｈｅＳｅｖｅｎｔｅｅｎｔｈｌｎｄ．Ｃｏｎｆ．ＯｉｌＭａｃｈｉｎｅ
ｉｎｇ．２０００．
Ｌｅａｒｎ－
［１６］ＣｈａｎｇＣｃ，ｕｎｃＪ．ＬＩＢＳＶＭ：Ａｌｉｂｒａｒｙｆｏｒｓｕｐｐｏｒｔ
２００１．ｈｔｔｐ：／／ｗｗｗ．ｅｓｉｅ．ｎｔｕ．ｅｄｕ．ｔｗ／一ｃｊｌｉｎ／ｌｉｂｅｖｍ．
ｖｅｃｔｏｒ
ｍａｃｈｉｎｅｓ，
社．２００５：１４１—１４３．
［５］刘怀义．杨小帆，孙丽萍，等．用带非线性自反馈的神经网络求解最
大团问题［Ｊ］．重庆大学学报：自然科学版，２００７，３０（９）：６０—６２．
ｆ上接第１０９页）
ＡＣＯＭＣＰ和回溯算法分别进行测试，表２、表３和图２给出这些实例的部分测试结果。实验结果可以看出，ＡＣＯＭＣＰ可以求得基准图的最优值和不同的最优解，取得较好的结果，实证了ＡＣＯＭＣＰ求解的有效性和高效性。
表２中，ＤＩＭＡＣＳ阶数为当前国际上对基准图测试得到的最大团阶数的最优值；回溯算法时间为求得一个最优解的平均
［６］韩爱丽，杨志敏．ＨＥＷＮ算法的复杂性分析～点商榷意见［Ｊ］．软件
学报，２００２，１３（１２）：２３３７—２３４２．
［７］贾晓峰，郭廷花，续晓欣．关于最大团问题的一种新算法［Ｊ］．中北
大学学报：自然科学版，２００６，２７（２）：１８０—１８２．
［８］钱晓锋，郁松年，徐炜民．一种借助邻接矩阵求任意图最大团的方
法［Ｊ］，计算机工程与应用，２００１，２３：１０３—１０５．
［９］李燕，王秀峰．ＤＮＡ计算方法［Ｊ］．计算机科学，加阱，３１（５）：１４２—１躬．［１０］段海滨．蚁群算法原理及应用［Ｍ］．北京：科学出版社，２００５：４０一４２．
基于蚁群算法求解最大团问题
作者：作者单位：刊名：英文刊名：年，卷(期)：
王会颖， 耿家礼， Wang Huiying， Geng Jiali安徽财贸职业学院计算机系,安徽,合肥,230601计算机应用与软件
COMPUTER APPLICATIONS AND SOFTWARE2010,27(10)
参考文献(10条)
1. 段海滨 蚁群算法原理及应用 2005
2. 李燕;王秀峰 DNA计算方法[期刊论文]-计算机科学 2004(05)
3. 钱晓锋;郁松年;徐炜民 一种借助邻接矩阵求任意图最大团的方法[期刊论文]-计算机工程与应用 2001(23)4. 贾晓峰;郭廷花;续晓欣 关于最大团问题的一种新算法[期刊论文]-中北大学学报(自然科学版) 2006(02)5. 韩爱丽;杨志敏 HEWN算法的复杂性分析-点商榷意见[期刊论文]-软件学报 2002(12)
6. 刘怀义;杨小帆;孙丽萍 用带非线性自反馈的神经网络求解最大团问题[期刊论文]-重庆大学学报(自然科学版)2007(09)
7. 王晓东 计算机算法设计与分析 2005
8. 丁建立;陈增强;袁著祉 遗传算法与蚂蚁算法的融合[期刊论文]-计算机研究与发展 2003(09)9. Dorigo M Optimization learning and nature algorithms 1992
10. 周旭东;王丽爱;陈岐 启发式算法求解最大团问题研究[期刊论文]-计算机工程与设计 2007(18)
本文链接：http://d.g.wanfangdata.com.cn/Periodical_jsjyyyrj201010033.aspx
第２７卷第１０期２０１０年１０月
计算机应用与软件
ＣｏｍｐｕｔｅｒＡｐｐｌｉｃａｔｉｏｎｓａｎｄＳｏｆｔｗａｒｅ
Ｖ０１．２７Ｎｏ．１０
Ｏｃｔ．２０１０
基于蚁群算法求解最大团问题
王会颖耿家礼
（安徽财贸职业学院计算机系安微合肥２３０６０１）
摘要最大团问题是一种典型的ＮＰ完全问题，是图论中一个经典的组合优化问题。研究将蚁群算法应用于求解最大团问题，
提出一种求解最大团问题蚁群算法。通过定义最大团问题蚁群算法中的各元素，并改进了蚂蚁搜索解的方法，有效地改善蚁群算法易于过早地收敛于局部最优解的缺陷。仿真实验表明，图中的顶点数较多时，也取得了较好的结果。关键词
最大团问题蚁群算法
最大团问题蚁群算法
ＳＯＬＶＩＮＧ
ＭＡＸＩＭＵＭＣＬＩＱＵＥＰＲＯＢＬＥＭ
ＢＡＳＥＤｏＮＡＮＴＣＯＬＯＮＹＯＰＴＩＭＩＺＡＴＩＯＮ
ＷａｎｇＨｕｉｙｉｎｇ
ＧｅｎｇＪｉａｌｉ
（Ｄｅｐａｒｔｍｅｎｔ矿Ｃｏｍｐｕｔｅｒ＆切Ｍ，ＡｎｈｕｉＦｉｎａｎｃｅ＆ＴｒａｄｅＶｏｃａｔｉｏｎａｌＣｏｌｌｅｇｅ，Ｈｅｆｅｉ２３０６０１，Ａｎｈｕｉ，Ｃｈｉｎａ）
Ａｂｓｔｒａｃｔ
Ｍａｘｉｍｕｍｃｈｑｕｅｐｒｏｂｌｅｍｉｓ
ａｎｔ
ａ
ｔｙｐｉｃａｌＮＰｃｏｍｐｌｅｔｅｐｒｏｂｌｅｍ，ａｎｄｉｓ
ｔｏ
ａ
ｃｌａｓｓｉｃａｌｐｒｏｂｌｅｍｏｆｃｏｍｂｉｎａｔｏｒｉａｌｏｐｔｉｍｉｚａｔｉｏｎｉｎｇｒａｐｈ
ｔｈｅｏｒｙ．Ｉｎｔｈｉｓｐａｐｅｒ，ｔｏａｐｐｌｙ
ｃｏｌｏｎｙｏｐｔｉｍｉｚａｔｉｏｎｒｅｓｏｌｆｉｎｇ
ｍａｘｉｍｕｍｃｌｉｑｕｅｐｒｏｂｌｅｍｉｓｒｅｓｅａｒｃｈｅｄ，ａｎｄａｎａｌｇｏｒｉｔｈｍｏｆａｎｔｃｏｌｏｎｙｏｐｔｉ—
ｍｉｚａｔｉｏｎｆｏｒｓｏｌｖｉｎｇｍａｘｉｍｕｍｃｌｉｑｕｅｍｅｎｔ
ｏｎ
ｐｒｏｂｌｅｍ（ＡＣＯＭＣＰ）ｉｓｐｕｔｆｏｒｗａｒｄ．ＷｉｔｈｔｈｅｄｅｆｉｎｉｔｉｏｎｏｆｅａｃｈｅｌｅｍｅｎｔｉｎＡＣＯＭＣＰａｎｄｔｈｅｉｍｐｒｏｖｅ—
ｄｉｓａｄｖａｎｔａｇｅｏｆｅａｓｉｌｙｆａｌｌｉｎｇｉｎｔｏｌｏｃａｌｂｅｓｔｔｈｅ
ｍｏｒｅｎｕｍｂｅｒｓｏｆｔｈｅｖｅｒｔｅｘ，ｉｔ
ａｎｔ
ｔｈｅ
ｗａｙ
ｔｈｅ
ａｎｔ
ｓｅａｒｃｈｅｓｉｔｓｓｏｌｕｔｉｏｎｓ．ｔｈｅ
ｃｏｌｏｎｙｏｐｔｉｍｉｚａｔｉｏｎ
ｈａｓｉｓｅｆｆｅｃｔｉｖｅｌｙ
ａ．
ｍｅｌｉｏｒａｔｅｄ．Ｓｉｍｕｌａｔｉｏｎｒｅｓｕｌｔｓｓｈｏｗｅｄ，ｗｈｅｎｔｈｅｒｅ
Ｍａｘｉｍｕｍｃｌｉｑｕｅｐｒｏｂｌｅｍ
ａｒｅ
Ｃａｎ
ａｌｓｏａｃｈｉｅｖｅｆａｉｒｌｙｇｏｏｄｅｆｆｅｃｔ．
Ｋｅｙｗｏｒｄｓ
Ａｎｔｃｏｌｏｎｙｏｐｔｉｍｉｚａｔｉｏｎ
Ａｎｔｃｏｌｏｎｙｏｐｔｉｍｉｚａｔｉｏｎｆｏｒ
ｓｏｌｖｉｎｇｍａｘｉｍｕｍｃｌｉｑｕｅｐｒｏｂｌｅｍ（ＡＣＯＭ・
ＣＰ）
质的强度成正比。当一条路径上通过的蚂蚁越来越多时，其留
０引言
下的信息素也越来越多，后来蚂蚁选择该路径的概率也越高，从而更增加了该路径的信息素强度。而强度大的信息索会吸引更多的蚂蚁，从而形成一种正反馈机制。通过这种正反馈机制，蚂蚁最终可以发现最短路径“。
以ＴＳＰ为例说明基本蚁群算法ＡＣＯ（ａｎｔ
ｃｏｌｏｎｙ
ｏｐｔｉｍｉｚａ－
最大团问题是一类ＮＰ完全问题，也被称为最大独立集问题。它的应用领域包括市场分析、方案选择、信号传输、计算机视觉和故障诊断等。研究它有很大的理论价值和实践价值。传统的确定性算法不能有效地进行求解最大团问题，因此好多学者提出了各种各样的启发式算法求解该问题。目前国内使用启发式算法求解最大团问题的研究还处于起步阶段¨。。
蚁群算法是一种新型仿生类进化算法，是继模拟退火、遗传算法、禁忌搜索等之后的又一启发式智能优化算法，具有很强的通用性和鲁棒性。意大利学者ＤｏｒｉｇｏＭ等于１９９１年最早提出蚁群算法，１９９２年，ＤｏｒｉｇｏＭ又在其博士论文中进一步阐述其核心思想门１。蚁群算法成功地应用于求解ＴＳＰ、二次分配、着色、车辆调度、集成电路设计及通信网络负载等问题。蚁群算法从提出到现在，因其在求解组合优化问题中突出表现，吸引了人们的极大关注。
ｔｉｏｎ）。ＴＳＰ描述为，已知，１个城市及各城市间的距离，求一条经过各城市一次且仅一次的最短的Ｈａｍｉｌｔｏｎ回路。
设有ｎ个城市，ｍ只蚂蚁，任意两城市ｉ、，之间的距离为ｄ（ｉＪ），ｒ（ｉ√）表示两个城市ｉ√之间信息素的浓度。初始时刻，各信息素的浓度相同。蚂蚁ｋ从城市ｉ转移到另一个城市』的
概率为Ｐ：，其计算式如式（１）所示。其中，Ｊ（ｋ）为蚂蚁ｋ在城市
ｉ时，还没有访问过的城市集合。启发函数田（ｉ，Ｊ）＝１／ｄ（ｉ，Ｊ）。ａ≯ｐ为参数。
ｌ∑［ｒ（√）］４・［＇７（ｉＪ）］４
Ｐｉ３…１
５｛『∈．，（％）
。
。ｆ揣特揣㈦＾…，ｎ
’。－’
”’
Ｆ
１
【０
其它
ｒ（ｉＪ）＝ｇｒ（ｉ√）＋△ｆ（ｉ√）
（２）
１基本蚁群算法
蚂蚁有能力在没有任何提示下找到从其巢穴到食物源的最短路径，并且能随环境的变化，适应性地搜索新的路径，产生新的选择。根本原因是蚂蚁在寻找食物源时，能在其走过的路上释放一种特殊的分泌物一信息素，随着时间的推移该物质会逐渐挥发，后来的蚂蚁选择该路径的概率与当时这条路径上该物
信息素更新式为式（２）。其中，Ｔ（ｉ，ｊ）表示城市ｉ，，之间的信息素的浓度，１－ｐ（０＜ｐ＜１）表示信息素的挥发程度，Ａ＇ｒ（ｉ，Ｊ）＝ｌ／ｌｍｂ，ｌｍｂ为一代中蚂蚁找到的最短路经的长度。信息素
收稿日期：２００９—０２—１５。安微省自然科学基金项目（Ｋ．１２００８Ｂ０２１）。王会颖。讲师。主研领域：智能软件，群体智能。
１０８
计算机应用与软件
２０１０点
的处理方式为：一代中仅对周游路径长度最短的蚂蚁所经过的路径进行信息素的修改增加，其余衰减，Ａｔ（ｉ）＝１／ｌｍｂ，ｌｍｂ为一代中蚂蚁找到的最短路径的长度。
算法ＡＣＯ简单描述如下：
①初始化。设定各参数值，蚂蚁个数ｍ，最大进化代数腑，信息素．ｒ（ｉ√）＝ｌ。
②每只蚂蚁独立地构造一个解。蚂蚁ｋ随机选择一个城
市ｉ作为起点，开始周游。根据概率公式（１）计算概率Ｐ：，按概率Ｐ：大者选择下一个城市Ｊ，蚂蚁ｋ从ｉ转移到下～个城市Ｌ若
蚂蚁ｋ周游的当前路径长度大于本代求得最短路径长度，结束此只蚂蚁的周游，否则，继续寻找下一个城市，直到蚂蚁ｋ访问完所有的城市。
③若ｍ只蚂蚁都构造完成各自的解，则转④，否则转②。④根据周游路径长度最小的蚂蚁，按式（２）及信息素的处理方式进行全局信息素更新。
⑤若满足结束条件，则输出最优解，否则ＧＥＮ＝ＧＥＮ＋１，转②。结束条件为ＧＥＮ＞Ａｒｃ或当前解已稳定。
２最大团问题
给定一个无向图Ｇ＝（ｙ，Ｅ）。如果Ｕ∈Ｖ，且对任意ｕ，ｔＪ∈Ｕ有（Ⅱ，口）∈Ｅ，则称Ｕ是Ｇ的一个完全子图。Ｇ的完全子图Ｕ是Ｇ的一个团，当且仅当Ｕ不包含在Ｇ的更大的完全子图中。Ｃ的最大团是指Ｇ中所含顶点数最多的团‘“。
图１无向图Ｇ
在图１无向图Ｇ中，子集｛ｌ，２｝是Ｇ的一个大小为２的完全子图。这个完全子图不是一个团，因为它包含于Ｇ的更大的完全子图｛ｌ，２，５｝之中。ｔ１，２，５｝是Ｇ的一个最大团。｛ｌ，４，５｝和｛２，３，５｝也是图Ｇ的最大团‘”。
３求解最大团问题蚁群算法
３．１
求解最大团问题蚁群算法中各元素的定义
本文提出求解最大团问题蚁群算法ＡＣＯＭＣＰ（ａｎｔ
ｃｏｌｏｎｙ
ｏｐｔｉｍｉｚａｔｉｏｎｏｆｓｏｌｖｉｎｇｎｌ／ｌ】【ｉｍｕｍｃｌｉｑｕｅ
ｐｒｏｂｌｅｍ）。在ＡＣＯＭＣＰ
中，每个顶点作为一个信息素载体，信息素积累在顶点上；一代迭代后，每只蚂蚁构造出一个可行解（团），第☆只蚂蚁形成团ｕ，Ｕ＝｛菇¨’菇托，…，鬈ｋ｝，其中，％＝ｉ表示第ｋ只蚂蚁第Ｊ次选中顶点ｉ，ＩｕＩ表示第ｋ只蚂蚁构造的团所包含的顶点数，即团的阶数。
设无向图Ｇ＝（Ｖ，Ｅ），有ｎ个顶点，图的存储结构采用邻接
矩阵删，堋（ｉ√）＝ｌ表示顶点ｉ和顶点，相邻接，ａｒｃｓ（ｉ√）＝０
表示顶点ｉ和顶点，不相邻接。顶点ｉ的度数为ｄｅｇｒｅｅ（ｉ）。启发函数叩定义为和顶点相关联的边数，即顶点的度数，田（ｉ）＝ｄｅｇｒｅｅ（ｉ）。目标函数为各蚂蚁构造的团中，团的阶数ＩｕＩ的最大值。
蚂蚁ｋ求解时，从一个顶点ｉ转移到下一个顶点Ｊ的概率，按式（３）计算，其中，ｒＵ）为ｔ时刻积累在顶点＿『上的信息素的浓度，
Ｊ（ｋ）为蚂蚁ｋ可以转移的下一个顶点的集合。集合．，（ｋ）中的每个顶点ｊ要满足三个条件：①顶点Ｊ不包含在蚂蚁ｋ形成的当前解｛髫…毒垃，…，％｝中；②顶点Ｊ和蚂蚁ｋ已求得的当前解中的每个顶点相邻接；③顶点门砸ｉ邻接，即ａｒｃｓ（ｉｄ）＝ｌ。
扣ｆ蚩黼Ｉｎ（Ｊ）
硝＝ｊ∑［ｆｕ）］。×
］４
川㈩（３）
一“”。
（３）
ｒ’
ｏｌｈ盯
信息素的更新仅采用全局更新的方式，一代中仅对所含顶点数最多的团中所含的顶点进行信息素的修改增加，其余衰减。更新为式（４），其中，ｌｍｂ为一代中蚂蚁找到的顶点数最多的团的阶数。
ｒ‘（ｔ＋１）＝ｐ＿ｒ。（ｔ）＋△ｆ（ｉ）
（４）
其中：
甜¨卜１０．…
ｒＩｍｂ／ｎ顶点ｉ属于一代中蚂蚁找到顶点数最多的团
其他
３．２对基本蚁群算法的改进
根据式（１）计算出集合Ｊ（ｋ）中所有顶点的概率，基本蚁群算法一般是选取概率大者作为下一个顶点。这样虽然强化了启发函数和信息素的引导，但是，容易出现停滞现象，过早地收敛于局部最优解。在蚁群算法中，信息素的加强形成正反馈机制，从而使可行解一步一步地向好解进化。同时也要增加搜索的随机性，兼顾解空间的各种情况，才能搜索到较好解，冲出局部最优解，向全局最优解进化。
基于上述分析，最大团问题蚁群算法改进蚂蚁选择下一个顶点的方式，采用最大原则或轮盘赌两种选点方式：给定参数ｑｏ（Ｏ≤ｑ０＜１），生成随机数ｇ（Ｏ≤ｇ＜１）。
（１）当ｇ≤ｇｏ时，蚂蚁按最大原则选点，按式（５）计算，蚂蚁选取［ｒ（ｊ）］４×［叼（Ｊ）］９达到最大的集合Ｊ（奄）中的顶点。
ｌＩ娜（［ｆ（Ｊ）］４×［ｎ（Ｊ）］４），∈Ｊ（ｋ）（５）
（２）当ｑ＞ｑ。时，按概率算式（３）计算集合．，（七）中所有顶点的概率，然后采用轮盘赌的方式选点，这样既兼顾了概率大小，又增加了搜索的随机性。轮盘赌的伪代码描述如下：
①生成一随机数ｒ，Ｏ《ｒ＜ｌ，．『＝０，，＝ｐ，；②如果／≥ｒ，则转④；⑤ｊ＝ｊ＋ｌＪ＝ｆ＋ｐ；，辕②；④选取点Ｊ，输出，结束。
对上述给定的参数％采用动态改变的方式。在进化的前期，由于初始信息素匮乏，信息素还不能很好地起到弓ｌ导作用，
ｑ０取较大的值，这样蚂蚁较多按最大原则选点，减少蚂蚁的盲目搜索，蚂蚁容易找到较好的解，缩短搜索时间，加快收敛速度。在进化的后期，ｑ。取较小的值。蚂蚁较多依据概率按轮盘赌方法选取下一个顶点，增加搜索的随机性，能有效地突破局部最优解，改善停滞现象，向最优解转化。
３．３最大团问题蚁群算法分析
求解最大团问题蚁群算法描述如下：
①初始化。设定各参数的值，蚂蚁的个数ｍ，最大进化代数Ⅳｃ，当前进化代数ＧＥＮ＝０，各顶点初始信息素的浓度下（ｉ）＝
１，ｉ＝１，２，…，，Ｉ。
②蚂蚁Ｉ｜｝（ｋ＝ｌ，２，…，ｍ）随机选择一个顶点ｉ为初始起点，
放入解向量，ｓｏｌｕｔｉｏｎｓ（１）＝ｉ，舶Ⅱ（ｉ）＝ｌ，团的阶数ｓ＝ｌ。
③每只蚂蚁独立地构造一个团。生成蚂蚁ｋ从顶点ｉ可转移的下一个顶点的集合．，（．｜｝）；若＿，（ｋ）为不空，生成随机数ｑ，若
第１０期王会颖等：基于蚁群算法求解最大团问题
１０９
ｑ＜。ｑｏ，蚂蚁按最大原则选点，，否则，蚂蚁按轮盘赌的方式选点Ｊ；将顶点Ｊ放入蚂蚁ｋ求得的解ｓｏｌｕｔｉｏｎｓ中，ｔａｂｕ（，）＝Ｉ，团的阶数ｓ＝ｓ＋１。如此循环，直到蚂蚁后可转移的下一个顶点的集合Ｊ（ｋ）为空。ｑ０进化初期取值较大，后期较小，动态变化。
④若蚂蚁ｋ形成的团的阶数大于当代最优团的阶数，保存＆形成的团为当代最优团。
⑤若ｍ只蚂蚁都构造完成各自的团，则转⑥，否则转②。⑥根据本代的最优团，按（４）式进行全局信息素更新。⑦若本代最优团阶数大于进化以来的全局最优团阶数，保存本代最优团为全局最优团。
⑧若达到一定的代数或解已稳定，则输出最优解；否则ＧＥＮ＝ＧＥＮ＋１，转②。
在求解ＴＳＰ问题基本蚁群算法ＡＣＯ中，算法的时间复杂度Ｔ（，１）＝ｏ（Ｎｃ・ｎ２・ｍ）；空间复杂度Ｓ（ｎ）＝ｏ（１７，２）＋Ｏ（／／，・ｍ）¨０｜。ＡＣＯ和ＡＣＯＭＣＰ的时间复杂度比较如下：在初始化步骤上，ＡＣＯ为Ｏ（，１２），ＡＣＯＭＣＰ为Ｏ（，１）；在每只蚂蚁独立构造一个解步骤上，ＡＣＯ为Ｏ（ｎ２），ＡＣＯＭＣＰ为Ｏ（ｒ／．２）；在信息素更新步骤上，ＡＣＯ为Ｏ（，１２），ＡＣＯＭＣＰ为Ｏ（／７，）。在ＡＣＯＭＣＰ中，虽然总体时间复杂度没变，但在初始化，信息素更新步骤上，从ＡＣＯ的０（，１２）降低到ＡＣＯＭＣＰ的Ｏ（ｎ）。在ＡＣＯＭＣＰ中，启发函数、信息素、解向量、概率、禁忌表均为一维向量。空间复杂度Ｓ（ｒｔ）＝Ｏ（／１．）。因此，最大团问题蚁群算法时间复杂度Ｔ（／１，）＝０（Ｎｃ・／７，２・ｍ）；空间复杂度Ｊｓ（ｎ）＝Ｏ（珏）。
顶点数１１
８８
实例文献７，图１
文献６。图９
文献
ＡＣＯＭＣＰ求解结果最大团
１，２，６，７２，３，５，６，７１，２，３，４，５，６，７，８，９，１０
回溯算法
时间
Ｏ．０００３０．Ｏ００３
阶数
４５
阶数代数
４５
ｌ１
阶数时间
４５
Ｏ．０００ｌＯ．０００ｌ
１４
文献６，图２
１０１０ｌＯ．００２５１００．００３５
２０
文献５
３
０。６，７或０，６，１１或０，６，１４或Ｄ。１４，１５或３，８，１６或３，１６，１９或４。６，１１
３ｌ０．００１０３Ｏ．００１３
表２回溯算法、ＡＧＯＭＣＰ对ＤＩＭＡＣＳ中的实例的求解结果比较
ＤＪＭＡＣＳ
顶点数
ｎ
边数
９４３５２２５９９０
实例
Ｋｅｌｌｅｒ一４Ｋｅｌｌｅｒ一５
ＡＣＯＭＣＰ求解结果阶数个数代数
ｌｌ２７
９２１０
ｌ７１
列溯算法
阶数
ｌｌ２７
时间
Ｏ．４０８７８１２．４２１９
阶数
１ｌ
时间
１７８．２６２２
１７Ｉ７７６
表３ＡＣＯＭＣＰ算法求解实例ｋｅｌｌｅｒ－５得到的１０个不同的阶数为２７的最大团
３６４０４２５２６３Ｊ４６１９８２３９３０９３１２３２６３２８３４４４２２４２８４３０４６ｌ４７２５００５３７６６５７２９７４６７４９７５３７７ｌ７７５３６４０４２５２６３１４６１９８２３９３０９３１２３２６３２８３４４３７２４２２４２８４３０
４６ｌ４７２５３７６６５７２９７４６７４９７５３７７ｌ７７５
３４４３９０
４仿真实验
实验数据来源分为二部分：第一部分采用美国离散数学及理论计算科学中心ＤＩＭＡＣＳ提供的ＤＩＭＡＣＳ基准图中的ｋｅｌｌｅｒ４实例和ｋｅｌｌｅｒ５实例。ＤＩＭＡＣＳ基准图可通过登录ｔｉｐ：／／ｄｉｍａｅｓ．Ｒｕｇｅｒｓ．ｅｄｕ／ｐｕｂ／ｃｈａｌｌｅｎｇ／或者ｈｔｔｐ：／／ｄｉｍａｃｓ．Ｒｕｔｇｅｒｓ．ｅｄｕ／ｃｈａｌ—ｌｅｎｇｅｓ／获得。实例ｋｅｌｌｅｒ４和ｋｅｌｌｅｒ５数据在ｆｔｐ：／／ｄｉｍａｅｓ．Ｒｕｔ－ｇｅｍ．ｅｄｕ／ｐｕｂ／ｃｈａｌｌｅｎｇ／ｇｒａｐｈ／ｃｏｎｔｒｉｂｕｔｅｄ／ｓｈｏｔ／ｑａ。
第二部分实验数据采用文献［５—９］提供实例数据。实验运行环境为：Ｐｅｎｔｉｕｍ
０
４ｌ４４４８６６７０１６ｌ２３９２７２３０９３１２３２６３２８
４２２４２８４３０４６１４７２５３７６５０７２９７４ｌ７４５７４７７５７７６８４ｌ４４４８６６７０１６ｌ２３９２７２３０９３１２３２６３２８３４４３９０４２２４２８４３０
４６ｌ４７２５３７６３２６５０７４ｌ７４５７４７７５７７６８
３４４４２２
４ｌ４４４８６６７０１６ｌ２３９２７２３０９３１２３２６３２８４２８４３０４ｌ
４６ｌ４７２５１８５３７６５０７２９７４１７４５７４７７５７７６８
４４４８６６７０１６ｌ１８３２３９３０９３１２３２６３２８３４４３９０
４２２４２８４３０４６ｌ４７２５３７６３２６５０７４ｌ７４５７４７７５７７６８４ｌ
４４４８６６７０１６１１８３２３９３０９３１２３２６３２８３４４４２２
１～６
４，２．２６Ｇ
ＣＰＵ，５１２Ｍ内存，ｊｄｋ
４２８４３０４６１４７２５１８５３７６５０７２９７４ｌ７４５７４７７５７７６８４１
１１，Ｅｃｌｉｐｓｅ．ＳＤＫ－３．４．１，Ｊａｖａ编程。实验参数：蚂蚁数ｍ
４４４８６６７０１６１１８３２３９３０９３１２３２６３２８３４４４２２
＝ｎ，瑾＝１，Ｂ＝ｌ，Ｐ＝Ｏ．９，Ｔ＿ｌｌｌａＸ＝ｌ，ｘ＿ｍｉｎ＝０．０００００００１，最大进化代数为２００，ｑＯ在进化初期取０．８，中期取０．６，后期取０．４。
实验比较回溯算法’４。和最大团问题蚁群算法的求解质量和求解时间。在求解质量上，ＡＣＯＭＣＰ取得了回溯算法精确求解得到的最优值，全部最优解。但在求解时间上，当问题规模较大时，ＡＣＯＭＣＰ求解时间远远小于回溯算法，取得较好的效果。实验结果如表Ｉ一表３和图２所示，其中，时间单位均为秒，代数为蚂蚁求得最优解进化的平均代数。
用文献Ｅ５—９］提供的实例对ＡＣＯＭＣＰ、回溯算法进行测试，表１给出求解结果比较，其中，时间均为求得一个最优解的平均时间。结果表明，ＡＣＯＭＣＰ均容易求得其最优值和最优解。
表１
顶点
ＡＣＯＭＣＰ和回溯算法及文献［５—９］结果的比较
４２８４３０４６ｌ４７２５１８５３７６３２６５０７４ｌ７４５７４７７５７７６８４１４４４８６６７０１６１２３９２７２３０９３１２３２６３２８
３４４４２２
４２８４３０４６ｌ４７２５１８５３７６３２６５０７４１７４５７４７７５７７６８４ｌ４４４８６６７０１６１１８３２３９３０９３１２３２６３２８３４４３９０４２２４２８４３０
４６ｌ４７２５３７６５０７２９７４１７４５７４７７５７７６８
数ｎ
６
实例文献９，图２。
（ａ）
文献阶数
４
ＡＣＯＭＣＰ求解结果
最大团
回溯算法
时间
Ｏ．０００２
阶数代数
４
ｌ
阶数
４
时间
０
０，２，３，４或
０，１，２，３
图２ＡＣＯＭＣＰ求解ｋｅｌｌｅｒ－５每代的进化情况
用ＤＩＭＡＣＳ基准图中的ｋｅｌｌｅｒ４和ｋｅｌｌｅｒ５测试实例对
４
０．０００ｌ
８
文献８，
４
２，４，５，７
４１０．ｏ（）０３
（下转第１１３页】
第１０期李政：主动学习在基于内容的遥感影像检索中的应用
１１３
时间；ＡＣＯＭＣＰ个数为ＡＣＯＭＣＰ求得的不同最大团的个数，
５结论
本文提出的融合主动学习和ＳＶＭ的主动集成学习算法
经实验表明，可进一步减少所需标记样本的数量，同时能够最大程度地缩减变型空间，能有效地改善学习器性能，从而能快速准确地捕捉到用户查询概念。下一步将对该算法的适应性进行深入研究和验证。
ＡＣＯＭＣＰ时间为在连续ｌＯ次求解中，求得第一个最优解所用的平均时间，如Ｋｅｌｌｅｒ－５实例，求得第一个最优解的平均代数为７１代，每代进化的平均时间为１１．４９８９秒，ＡＣＯＭＣＰ时间为７１×１１．４９８９＝８１６．４２１９秒。可以看出，对Ｋｅｌｌｅｒ－４实例，ＡＣＯＭＣＰ求解质量同于回溯算法。但求解时间远远小于回溯算法，从回溯算法的１７０８．２６２２秒降低到０．４０８７秒。对Ｋｅｌｌｅｒ－５实例，ＡＣＯＭＣＰ顺利求解，而回溯算法求解困难。实例ｋｅｌｌｅｒ－４用ＡＣＯＭＣＰ得到了阶数为１１的９２个不同的最大团。对实例ｋｅｌ—ｌｅｒ－５用ＡＣＯＭＣＰ得到的阶数为２７的１０个不同的最大团在表３
ｉｍａｇｅ
参考文献
［１］Ｓｍｅｕｌｄｅｒｓ
ｔｈｅ
ｅａｒｌｙ
Ａ
ＷＭ，ｅｔａ１．Ｃｏｎｔｅｎｔ—ｂａｓｅｄ
Ｔｒａｎｓａｃｔｉｏｎｓ
ｏｎ
ｒｅｔｒｉｅｖａｌ
ａｔ
ｔｈｅｅｎｄｏｆ
中给出。
图２中，横坐标表示ＡＣＯＭＣＰ进化的代数，纵坐标表示团的阶数，图２反映了ＡＣＯＭＣＰ求解过程中团的阶数随代数的变化情况，算法在第７３代已达到了稳定，求解效率较高。
ｙｅａｒｓ．ＩＥＥＥ
ＰａｔｔｅｒｎＡｎａｌｙｓｉｓａｎｄＭａｃｈｉｎｅ
Ｉｎｔｅｌｌｉｇｅｎｃｅ。２０００。２２（１２）：１３４９—１３８０．
［２］ＳａｌｔｏｎＧ，Ｂｕｄｄｅｙｃ．Ｉｍｐｒｏｖｉｎｇｒｅｔｒｉｅｖａｌｐｅｒｆｏｒｍａｎｃｅｂｙｒｅｌｅｖａｎｃｅ
ｆｅｅｄｂａｃｋ．Ｊｏｕｒｎａｌ
ｏｆ
ｔｈｅＡｍｅｒｉｃａｎ
ｓｏｃｉｅｔｙ
ｆｏｒｉｎｆｏｒｍａｔｉｏｎ
ｓｃｉｅｎｃｅ，
１９９０，４１（４）：２８８—２９７．
［３］张健沛，徐华．支持向量机（ＳＶＭ）主动学习方法研究与应用．计
算机应用，２００４（１）：ｌ一３．
［４］徐杰．基于小样本学习的图像检索研究［Ｄ］．上海：上海交通大
学，２００４．
［５］张学工．关于统计学习理论与支持向量机．自动化学报。２０００，２６
（１）：３２—４２．
［６］ＦｒｅｕｎｄＹ，ＳｅｕｎｇＨ，ｅｔａ１．Ｓｅｌｅｃｔｉｖｅｓａｍｐｌｉｎｇ
ｍｉｔｔｅｅ
ｕｓｉｎｇ
５结论
本文研究利用蚁群算法求解最大团问题，提出了求解最大团问题蚁群算法。应用蚁群算法原理及算法模型对求解最大团问题进行建模，定义了最大团问题蚁群算法中的各元素。对基本蚁群算法进行改进，改进蚂蚁选择下一个顶点的方式，依据动态参数，采用最大原则或轮盘赌方式。这样，在进化前期蚂蚁较多按最大原则选点，蚂蚁容易找到较好的解，减少蚂蚁的盲目搜索，缩短搜索时间，加快收敛速度；在进化后期，蚂蚁较多依据概率按轮盘赌方法选取下一个顶点，既兼顾了概率大小，又增加了搜索的随机性，兼顾解空间的多种情况，有效改善蚁群算法易于过早地收敛于局部最优解的缺陷。对ＡＣＯＭＣＰ进行分析，其时间复杂度为Ｏ（Ⅳｃ・，１２・ｍ），空间复杂度为０（ｎ）。仿真实验比较ＡＣＯＭＣＰ和回溯算法及文献［５—９］的结果，并用ＤＩＭＡＣＳ基准图中的ｋｅｌｌｅｒ４和ｋｅｌｌｅｒ５测试实例对ＡＣＯＭＣＰ、回溯算法进行测试。实验结果表明，ＡＣＯＭ－ＣＰ算法取得较好的求解速度和求解质量。将最大团问题蚁群算法和其它算法融合，进一步改进算法的求解效率和求解质量，是需要进一步研究的问题。
ｔｈｅ
ｑｕｅｒｙｂｙ
ｏ｛Ｍｎ［ｉ－
ａｌｇｏｒｉｔｈｍ．ＭａｃｈｉｎｅＬｅａｒｎｉｎｇ，１９９７。２８：１３３—１６８．
ｆｏｒｔｒａｉｎｉｎｇ
［７］ＤａｇａｎＩ，ＥｎｇｅｌｓｏｎＳ．Ｃｏｍｍｉｔｔｅｅ・ｂａｓｅｄｓａｍｐｌｉｎｇ
ｔｉｃ
ｏｎ
ｐｒｏｂａｂｉｌｉｓ－Ｃｏｎｆｅｒｅｎｃｅ
ｃｌａｓｓｉｆｉｅｒｓ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓｏｆｔｈｅｔｗｅｌｆｔｈ
ＭａｃｈｉｎｅＬｅａｒｎｉｎｇ．１９９５：１５０—１５７．
Ｉｎｔｅｒｎａｔｉｏｎａｌ
［８］ＣｏｈｎＤ，ＡｔｌａｓＬ，ＬａｄｎｅｒＲ．Ｉｍｐｒｏｖｉｎｇｇｅｎｅｒａｌｉｚａｔｉｏｎｗｉｔｈ
ｉｎｇ．Ｍａｃｈｉｎｅ
ａｃｔｉｖｅｌｅａｒｎ－
Ｌｅａｒｎｉｎｇ，１９９４，１５（２）：２０１—２２１．
ｓｅｑｕｅｎｔｉａｌ
［９］ＬｅｗｉｓＤ，ＧａｌｅＷＡ．Ａ
ａｌｇｏｒｉｔｈｍ
ｆｏｒ
ｔｒａｉｎｉｎｇ
ｔｅｘｔ
ｃｌａｓｓｉｆｉｅｒｓ
ｆＣ］／／Ｐｎ）ｅ．ＯｆｔｈｅＳｅｖｅｎｔｅｅｎｔｈＡｎｎｕｍＩｎｔｌ．ＡＣＭ．ＳＩＧＩＲＣｏｎｆ．Ｒｅ．
ｓｅａｒｃｈ
ａｎｄ
Ｄｅｖｅｌｏｐｍｅｎｔ
ｉｎ
Ｉｎｆｏｒｍａｔｉｏｎ
Ｒｅｔｒｉｅｖａｌ，Ｓｐｒｉｎｇｅｒ－
Ｖｅｄ％，１９９４．
［１０］刘宏，屠轶清，黄上腾．一种新的支持向量机主动学习策略及其
在文本分类中的应用．计算机科学，２００３，３０（６）：１１０一１１２．［１１］Ｔｏｎｇｓ，ＫｏｌｌｅｒＤ．Ｓｕｐｐｏｒｔ
ｃａｔｉｏｎｓ
ｔｏ
Ｖｅｃｔｏｒ
Ｍａｃｈｉｎｅ
ｏｆ
Ａｃｔｉｖｅ
ＬｅａｒｎｉｎｇｗｉｔｈＡｐｐｌｉ・
ＴｅｘｔＣｌａ∞ｉｉｉｃａｔｉｏｎ．Ｊｏｕｒｎａｌ
ＭａｃｈｉｎｅＬｅａｒｎｉｎｇＲｅｓｅａｒｃｈ．
２００１，２：４５—６６．
参考文献
［１］周旭东，王丽爱，陈岐．启发式算法求解最大团问题研究［Ｊ］．计算
机工程与设计，２００７，２８（１８）：４３２９—４３３２．
（２］ＤｏｒｉｇｏＭ．Ｏｐｔｉｍｉｚａｔｉｏｎｌｅａｒｎｉｎｇａｎｄｎａｔｕｒｅａｌｇｏｒｉｔｈｍ［Ｄ］．ＰｈＤ．Ｔｈｅ－
ｓｉｓ，ＤｅｐａｒｔｍｅｎｔｏｆＥｌｅｃｔｒｏｎｉｃｓ，ＰｏｌｉｔｅｃｎｉｅｏｄｉＭｉｌａｎｏ，Ｉｔａｌｙ，１９９２．
ｓｕｐｐｏｒｔ
ｖｅｃｔｏｒ
［１２］Ｍｉｔｃｈｅｌｌ
Ｔ
Ｍ．Ｇｅｎｅｒａｌｉｚａｔｉｏｎ鹊Ｓｅａｒｃｈ．ＪｏｕｒｎａｌｏｆＡｒｔｉｔｌｃｉａｌＩｎｔｅＲｉ－
ｇｅｎｃｅ．１９８２．１８：２０３—２２６．
［１３］ＭｉｔｃｈｅｌｌＴ．ＭａｃｈｉｎｅＬｅａｒｎｉｎｇ．ＭｃＧｒａｗＨｉｌｌ。１９９７．［１４］Ｔｏｎｇｓ，ＣｈａｎｇＥ．Ｓｕｐｐｏｒｔ［１５］ＳｃｈｏｈｎＧ，ＣｏｈｎＤ．Ｌｅｓｓ
ｖｅｃｔｏｒ
ｍａｃｈｉｎｅａｃｔｉｖｅ
ｌｅａｒｎｉｎｇｆｏｒｉｍａｇｅ睁
ｔｒｉｅｖａｌ．ＡＣＭＭｕｌｔｉｍｅｄｉａ。Ｏｔｔａｗａ，Ｃａｎａｄａ，２００１．
ｉｓ
ｍｏｒｅ，Ａｃｔｉｖｅ
ｌｅａｒｎｉｎｇｗｉｔｈ
［３］丁建立，陈增强，袁著祉．遗传算法与蚂蚁算法的融合［Ｊ］．计算机
研究与发展，２００３。４０（９）：１３５１—１３５６．
［４］王晓东．计算机算法设计与分析［Ｍ］．２版．北京：电子工业出版
ｍａｃｈｉｎｅｓ［Ｃ］／／Ｐｒｅｃ．ｏｆｔｈｅＳｅｖｅｎｔｅｅｎｔｈｌｎｄ．Ｃｏｎｆ．ＯｉｌＭａｃｈｉｎｅ
ｉｎｇ．２０００．
Ｌｅａｒｎ－
［１６］ＣｈａｎｇＣｃ，ｕｎｃＪ．ＬＩＢＳＶＭ：Ａｌｉｂｒａｒｙｆｏｒｓｕｐｐｏｒｔ
２００１．ｈｔｔｐ：／／ｗｗｗ．ｅｓｉｅ．ｎｔｕ．ｅｄｕ．ｔｗ／一ｃｊｌｉｎ／ｌｉｂｅｖｍ．
ｖｅｃｔｏｒ
ｍａｃｈｉｎｅｓ，
社．２００５：１４１—１４３．
［５］刘怀义．杨小帆，孙丽萍，等．用带非线性自反馈的神经网络求解最
大团问题［Ｊ］．重庆大学学报：自然科学版，２００７，３０（９）：６０—６２．
ｆ上接第１０９页）
ＡＣＯＭＣＰ和回溯算法分别进行测试，表２、表３和图２给出这些实例的部分测试结果。实验结果可以看出，ＡＣＯＭＣＰ可以求得基准图的最优值和不同的最优解，取得较好的结果，实证了ＡＣＯＭＣＰ求解的有效性和高效性。
表２中，ＤＩＭＡＣＳ阶数为当前国际上对基准图测试得到的最大团阶数的最优值；回溯算法时间为求得一个最优解的平均
［６］韩爱丽，杨志敏．ＨＥＷＮ算法的复杂性分析～点商榷意见［Ｊ］．软件
学报，２００２，１３（１２）：２３３７—２３４２．
［７］贾晓峰，郭廷花，续晓欣．关于最大团问题的一种新算法［Ｊ］．中北
大学学报：自然科学版，２００６，２７（２）：１８０—１８２．
［８］钱晓锋，郁松年，徐炜民．一种借助邻接矩阵求任意图最大团的方
法［Ｊ］，计算机工程与应用，２００１，２３：１０３—１０５．
［９］李燕，王秀峰．ＤＮＡ计算方法［Ｊ］．计算机科学，加阱，３１（５）：１４２—１躬．［１０］段海滨．蚁群算法原理及应用［Ｍ］．北京：科学出版社，２００５：４０一４２．
基于蚁群算法求解最大团问题
作者：作者单位：刊名：英文刊名：年，卷(期)：
王会颖， 耿家礼， Wang Huiying， Geng Jiali安徽财贸职业学院计算机系,安徽,合肥,230601计算机应用与软件
COMPUTER APPLICATIONS AND SOFTWARE2010,27(10)
参考文献(10条)
1. 段海滨 蚁群算法原理及应用 2005
2. 李燕;王秀峰 DNA计算方法[期刊论文]-计算机科学 2004(05)
3. 钱晓锋;郁松年;徐炜民 一种借助邻接矩阵求任意图最大团的方法[期刊论文]-计算机工程与应用 2001(23)4. 贾晓峰;郭廷花;续晓欣 关于最大团问题的一种新算法[期刊论文]-中北大学学报(自然科学版) 2006(02)5. 韩爱丽;杨志敏 HEWN算法的复杂性分析-点商榷意见[期刊论文]-软件学报 2002(12)
6. 刘怀义;杨小帆;孙丽萍 用带非线性自反馈的神经网络求解最大团问题[期刊论文]-重庆大学学报(自然科学版)2007(09)
7. 王晓东 计算机算法设计与分析 2005
8. 丁建立;陈增强;袁著祉 遗传算法与蚂蚁算法的融合[期刊论文]-计算机研究与发展 2003(09)9. Dorigo M Optimization learning and nature algorithms 1992
10. 周旭东;王丽爱;陈岐 启发式算法求解最大团问题研究[期刊论文]-计算机工程与设计 2007(18)
本文链接：http://d.g.wanfangdata.com.cn/Periodical_jsjyyyrj201010033.aspx