集合覆盖问题的分散搜索算法

A Scatter Search Algorithm for Solving the Set Covering Problem

集合覆盖问题的搜索算法有着广泛的应用.本文提出了一个有效求解集合覆盖问题的分散搜索算法,该算法根据集合覆盖问题的特点,以及参考集的产生方法和更新方法,并采用45个标准测试例子测试此算法,通过数值实验结果与遗传算法、基因文化算法的比较,结果表明了此算法是有效的.

The set covering problem has wide applications .In this paper , an efficient scatter search algorithm is proposed to solve the set covering problem .According to the structure of the set covering problem , a reference set generation method , a solution improvement method , a solution combination method and a reference set update method are developed .The experiments were done on 45 benchmarks from the literature .Numerical results and comparisons with genetic algorithm and culture algorithm indicate that the proposed algorithm is efficient .