给定一个无向图,寻找一个顶点子集,使得子集中的任意两个顶点都相邻,这样的顶点子集称作团。最大团问题是指寻找一个基数最大的团,该问题是一个著名的组合优化问题,也是一类NP完全问题。最大团问题在信息检索、生物信息学和故障诊断等领域有着广泛的应用。最大边加权团问题和团划分问题是团问题的扩展,它们有着更强的表达能力和更广泛的应用,已被证明是NP-难组合优化问题。求解这两个问题的算法主要分为两类即精确算法和启发式算法。精确算法可以给出问题的最优解,但随着问题规模的增长,精确算法将很难求解,由此启发式算法应运而生,如局部搜索算法、禁忌算法等,该类算法可以在合理的时间内给出问题的最优解或者次优解。启发式算法具有思路简单、容易实现、高效和通用的特点。本文针对求解最大边加权团问题和团划分问题的局部搜索算法展开研究。最大边加权团问题应用在实验设计、信号传输和计算机视觉等领域。我们提出了基于多规则的局部搜索算法求解该问题。该算法首先提出了一个打分策略用于评估添加和交换操作的收益,然后使用顶点加权策略来增加解的多样性,并且使用格局检测策略来避免循环问题。通过结合这三种策略,算法提出了多个规则来选择添加的顶点和交换的顶点对。基于这些规则,提出了一种高效的局部搜索算法,即基于多规则的局部搜索算法(LSMR)。实验结果表明,LSMR在求解质量和计算效率方面均优于对比算法。团划分问题在机场物流和社会科学等领域有着广泛的应用。我们提出了基于两模式的局部搜索算法求解该问题。首先,算法采用了一个两模式局部搜索过程来提高当前解的质量。然后,为了增加解的多样性而提出了一个扰动过程,并且扰动强度会根据当前解的情况自适应地更新。基于这两个过程,提出了一种新颖的带自适应参数的两模式局部搜索算法(TMLS＿SA)。实验结果表明在求解质量方面TMLS＿SA优于对比算法。