随机局部搜索算法是一种解决计算机科学和运筹学领域中组合最优化问题的元启发式方法。近年来,由于其简单、高效的特点而得到越来越多的应用。本论文中,我们对随机局部搜索算法进行研究,展示了根据具体问题的特点来设计算法的过程。更具体地讲,我们选择集合覆盖问题作为我们的主要研究目标,主要的工作和贡献有：1.设计一个新的适用于集合覆盖问题的随机局部搜索算法叫做行加权局部搜索算法(RWLS:Row Weighting Local Search),它具有以下特点1)一个扰动搜索的框架,该框架由两个操作函数(ADD和REMOVE)实现；2)多种禁忌策略来避免搜索的重复和循环,包括时间戳的方法,禁忌表和布尔状态检查的策略；3)一个权值调整的策略来帮助算法跳出局部最优。我们对RWLS和文献中最好的方法进行了比较,在OR-Library上的80个实例上的比较结果显示RWLS一共更新了14个已知最好的解,并且在剩下的66实例上都能够达到已知的最好结果。在7个超大规模的铁路调度实例上,结合一种降低问题规模的方法,在4个实例上,RWLS的表现要好于CPLEX。2.在RWLS算法思想的基础上,我们进一步抽象出了一个平衡多样性和探索性的扰动局部搜索算法框架(BIDPLS:Balancing Intensification and Diversification Perturbative Local Search),这个算法框架的有效性在多维度多选择背包问题得到了验证。