最大团算法研究

2009最大团算法研究主要介绍：CompanyLogo最大团定义以其研究进展1最大团的算法介绍2回溯法和分支限界法详细介绍3最大团的应用4MCP描述CompanyLogo最大团问题

(MaximumCliqueProblem,MCP)描述：对于给定图G(V，E)，其中，V=(1，⋯，n)是图G的顶点集，E

VxV是图G的边集。图G的团就是一两两之间有边的顶点集合。如果一个团不被其它任一团所包含，即它不是其它任一团的真子集，则称该团为图G的极大团。顶点最多的极大团，称之为图G的最大团。

最大团问题的目标就是要找到给定图的最大团。MCP数学描述CompanyLogoMCP作为一个整数规划问题有许多等价的描述。整数规划问题的描述(二次0-1问题)：则设其中，，n为图的顶点数。MCP数学描述CompanyLogo由于（1）如果是（1）的最优解，那么集合C=是图G的最大团，且MCP数学描述CompanyLogo因此有其中：——图G的补图的邻接矩阵。MCP等价于下面的全局二次0-1问题其中：如果是（2）的最优解，那么集合是图G的一个最大团，且（2）算法研究进展CompanyLogo神经网络模拟退火禁忌搜索基于连续的启发式算法遗传算法19901989198719571993now反作用禁忌搜索算法、简单启发式算法、DLS—MC1957年，Hararv和Ross首次提出求解最大团问题的确定性算法。但随着研究的深入，遇到的问题复杂度越来越高(顶点增多和边密度变大)，确定性算法显得无能为力，不能有效解决这些NP完全问题，典型地体现是运行时间过长。在20世纪80年代末开始采用启发式算法求解最大团问题，并且取得了令人满意的效果。在时间上，由于采用了启发式信息，启发式算法的运算时间与确定性算法的运算时间之间的比值会随着图的顶点、密度的增加而变得越来越小。唯一的缺点就是不一定能找到最优值，有时只能找到近优值。研究表明，单独使用一种启发式算法求解最大团问题，算法性能并不是很好，因此，需要算法之间互相取长补短，形成新的混合算法来求解最大团问题。当前求解该问题最好的启发式算法有反作用禁忌搜索算法(ReactiveTabuSearch)、简单启发式算法(SimpleHeuristicBasedGeneticAlgorithm，HGA)和DLS—MC等。关于MCP算法介绍CompanyLogo

回溯法

分支限界法算法列举基础算法分类

顺序贪婪算法

局部搜索启发式算法

智能搜索算法遗传算法禁忌算法模拟退火算法神经网络

启发式算法其他算法详见MCP研究报告DLS—MC算法基于遗传算法的简单算法（HGA)反作用局部搜索算法MCP启发式算法介绍CompanyLogoBestin基本思路：由一个团出发，和这个团中顶点相连的顶点组成候选集。然后以一定的启发式信息，从中选择顶点加入团中，以后反复进行。直到最后得到一个极大团。顺序贪婪算法Worstout基本思路：从整个顶点集开始，然后按一定的启发式信息，从中反复进行删除顶点操作，直到最后得到一个团。顺序贪婪启发式算法有很大不足，该算法一旦找见一个极大团，搜索就停止：因此找到最大团的概率相对较低。MCP启发式算法介绍CompanyLogo局部搜索启发式算法存在一个问题是：仅能够找见一个局部最优值。所以为了提高求解的质量，该算法和其它算法相混合得到新性能好的算法。假设为图的所有极大团的集合，扩大在的搜索区域，比如，可以在极大团S的邻居中继续进行搜索，以扩大搜索区域，进而提高解的质量。依赖不同的邻居定义，局部搜索启发式算法可以得到不同的解。局部搜索启发式算法DLS—MC算法plateausearch局部搜索启发式和算法迭代改善法相混合得到的，该方法中引入了顶点惩罚函数，函数在算法的求解过程中能够动态改变；在算法执行过程中迭代改善法和plateausearch算法轮流执行来提高解的质量。MCP启发式算法介绍CompanyLogo智能搜索算法遗传算法其他算法禁忌算法模拟退火算法神经网络MCP启发式算法介绍CompanyLogo一种基于自然选择和群体遗传机理的搜索算法，它模拟了自然选择和自然遗传过程中发生的复制、交叉和变异现象，适应度函数起着非常关键的作用。遗传算法简单启发式算法HGA算法由两部分组成：简单遗传算法(SGA)和简单的贪婪启发式局部搜索算法。在基准图上对算法HGA的性能进行测试，证明了该算法在解的质量和计算速度方面都优于基于遗传算法的其它算法。MCP启发式算法介绍CompanyLogo一种改进的局部搜索算法。为了避免在搜索过程中出现死循环和开发新的搜索区域，采用了一种基于禁止的策略。其目标是最小化当前子集(解)顶点之间的边数。使用3个禁忌表：其中，一个禁忌表用来存放上一代的解，另外两个分别存放刚进入解顶点和刚被删去的顶点。禁忌算法反作用局部搜索算法通过引入局部搜索算法，扩展了禁忌搜索的框架。与一般禁忌搜索算法相比，该算法的特点是：在执行过程中，根据所得到的解的情况形成一种内部反馈机制以控制调整算法的控制参数，所以该算法的控制参数是动态变化的；比如，禁止表长度参数是动态变化的，因此禁忌表长度是动态变化的。MCP启发式算法介绍CompanyLogo模拟退火算法一种基于物质退火过程的随机搜索算法，是一种迭代求解的算法。首先在高温下较快地进行搜索，使系统进入“热平衡”状态，大致地找到系统的低能区域。随着温度的逐渐降低，搜索精度不断提高，可逐渐准确地找到最低能量的基态。作为局部搜索算法的扩展，当邻域的一次操作使当前解的质量提高时，接受这个改进解作为新的当前解；反之，以一定的概率接受相对质量比较差的解作为新的当前解。神经网络人工神经网络指为了模拟生物大脑的结构和功能而构成的一种大型的、分布式系统，它有很强的自组织性、自适应性和学习能力。对最大团和相关问题按人工神经网络进行编码，进而求解该问题。MCP启发式算法介绍CompanyLogo综合评价：前3种智能搜索算法适合求解MCP，而通过神经网络算法求解MCP时的性能比较差；单独使用智能搜索算法来求解MCP，算法性能并不好，因此，常和局部搜索算法相结合形成新的混合算法，比如：禁忌算法与局部搜索算法相混合形成的反作用禁忌搜索算法，遗传算法与局部搜索算法相混合形成的简单启发式算法等。MCP详细算法介绍CompanyLogo回溯法分支限界法MCP回溯法详细介绍CompanyLogo问题描述

给定无向图G=(V，E)。如果U

V，且对任意u，v

U有(u，v)

E，则称U是G的完全子图。G的完全子图U是G的团当且仅当U不包含在G的更大的完全子图中。G的最大团是指G中所含顶点数最多的团。下图G中，子集{1，2}是G的大小为2的完全子图。这个完全子图不是团，因为它被G的更大的完全子图{1，2，5}包含。{1，2，5}是G的最大团。{1，4，5}和{2，3，5}也是G的最大团。12453MCP回溯法详细介绍CompanyLogo回溯法基本思想回溯法按照深度优先策略，从根节点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。回溯法搜索解空间树时，根节点首先成为一个活结点，同时也成为当前的扩展节点。在当前扩展节点处，搜索向纵深方向移至一个新节点。这个新节点就成为一个新的活结点，并成为当前扩展节点。如果当前扩展节点不能再向纵深方向移动，则当前的扩展节点就成为死结点。此时，往回回溯至最近的一个活节点处，并使这个活结点成为当前的扩展节点。回溯法以这种方式递归地在解空间中搜索，直至找到所有要求的解或解空间已无活结点为止。MCP回溯法详细介绍CompanyLogo算法设计无向图G的最大团问题可以看作是图G的顶点集V的子集选取问题。因此可以用子集树表示问题的解空间。设当前扩展节点Z位于解空间树的第i层。在进入左子