广义顶点覆盖问题和k覆盖集问题是覆盖问题的扩展,其中广义顶点覆盖问题扩展了经典顶点覆盖问题,k覆盖集问题扩展了经典集合覆盖问题。这两个问题都具有广泛的应用领域。例如,计算生物学领域、无线技术网络领域。另外,广义顶点覆盖问题和k覆盖集问题是覆盖问题都是NP难的问题。在现实世界中,大量的NP难问题具有的共同特点是,随着例子规模的不断增大,可行解的数量以及求解难度往往都呈指数级增长,这也导致了精确求解算法很难在令人满意的时间内得到一个不错的精确解。局部搜索算法则可以在合理的时间内得到一个可行解。目前,启发式算法是一种常用的局部搜索算法,是解决最优化问题的方法之一。局部搜索算法可以看作是一种简单的贪心搜索算法,每次从当前解的相邻解空间中选择一个最佳操作执行,进而生成新的当前解,直到达到一个局部最优解。本文设计了两个局部搜索算法分别求解广义顶点覆盖问题和k覆盖集问题。用于求解广义顶点覆盖问题的算法是一种基于进化搜索和迭代邻域搜索的混合启发式算法。该算法使用新的初始化方法以产生高质量的初始解,然后使用交叉操作生成后代解,最后利用最佳选择的邻域搜索来查找更好的解。实验结果证明,该算法在随机实例和DIMACS实例上具有优异的性能。用于求解k覆盖集问题的算法是一种基于格局检测和打分机制的局部搜索算法。首先,为了克服局部搜索中的循环问题,提出了k集合覆盖格局检测策略。其次,为了使算法可以找到更优的解,采用元素成本定义打分机制。本文提出的基于格局检测和打分机制的局部搜索算法与两个最先进的算法进行了比较。实验结果表明,在大多数经典情况下,格局检测和打分机制的算法给出的解的质量要优于其他算法。