组合优化问题是计算机科学与运筹学的一个重要分支,主要是通过对数学方法的研究去寻找离散事件的最优分组、编排、筛选或次序等。组合优化问题在信息技术、交通运输、通信网络、经济管理等领域有着重要的应用。求解组合优化问题的算法包括精确算法和启发式算法,精确算法能够求出问题的最优解,但是随着问题规模逐渐增大,求解这些问题最优解所需的计算量与存储空间呈指数增长,会带来所谓的“组合爆炸”现象,使得在现有的计算能力下,使用精确算法求得最优解几乎变得不可能。在这种情况下,一些启发式算法应运而生,如局部搜索算法、松弛算法等。对于难解问题实例,局部搜索算法可以在合理的时间内找到近似最优解或最优解。同时局部搜索算法具有简单、高效、容易并行等优点。局部搜索算法很容易实现,对于优化问题,只要定义好解空间的邻居结构,就可以用局部搜索算法来求解。目前已有很多研究表明了局部搜索算法的高效性,尤其在求解NP难问题的较大实例,局部搜索算法有很大的潜力。由于很多局部搜索算法都加入了随机策略,不同随机种子的运行就可实现并行。本论文中,我们对局部搜索算法进行研究,并根据具体问题的特点设计高效的算法。具体来说,我们选择最小加权顶点覆盖问题、最小有容量支配集问题和最小连通支配集问题作为研究对象,设计高效的局部搜索算法。本文的主要研究工作和贡献如下:(1)提出基于动态打分策略和加权格局检测策略的局部搜索算法(DLSWCC)求解最小加权顶点覆盖问题。在DLSWCC算法中,动态打分策略在搜索陷入局部最优时更新边的权值,进而改变顶点的分数,从而使搜索跳出局部最优并向更优的方向进行;加权格局检测策略考虑了每个顶点的环境信息,用来减少局部搜索中的循环问题;结合以上两个策略我们提出了顶点选择方法,确定在局部搜索过程中加入或移出候选解的顶点。我们在大量的标准实例上对DLSWCC算法进行了测试,实验结果表明DLSWCC算法要优于现有最优算法。(2)提出基于顶点惩罚策略和两种模式的被支配顶点选择策略的局部搜索算法(LS_PD)求解最小有容量支配集问题。在LS_PD算法中,顶点惩罚策略在搜索陷入局部最优时增加当前未被支配顶点的罚值,罚值的改变会影响顶点的分数,使得算法跳出局部最优;两种模式的被支配顶点选择策略以的概率随机选择加入候选解的顶点支配哪些顶点,以1-的概率贪心选择;同时用强化策略来提高每个顶点容量的利用率,从而提高算法的性能。我们在固定容量和变化容量的一般图及UDG图上对LS_PD算法进行了对比实验。实验结果表明,无论是一般图还是UDG图,LS_PD算法都具有较高性能。(3)提出基于候选顶点集合和解的连接元素集合的GRASP算法求解最小连通支配集问题。在GRASP算法中,在构造初始候选解时,加入候选顶点集合中的顶点不会破坏候选解的连通性;在搜索过程中,加入解的连接元素集合中的顶点会使不连通的候选解变为连通;此外,我们还使用评估函数定义了每个顶点的分数,禁忌策略来避免局部搜索重复访问以前搜索过的解。我们将GRASP算法与现有最优启发式算法和精确算法进行对比。实验结果表明GRASP算法在LPRNMR实例和随机实例上效果很好,在MLSTP实例上只有少数稀疏图效果不是很好。