Proceedings of the 19th Conference on Computer Science and Intelligence Systems (FedCSIS)

DOI: http://dx.doi.org/10.15439/2024F7060

Citation: Proceedings of the 19th Conference on Computer Science and Intelligence Systems (FedCSIS), M. Bolanowski, M. Ganzha, L. Maciaszek, M. Paprzycki, D. Ślęzak (eds). ACSIS, Vol. 39, pages 689–694 (2024)

Full text

Abstract. A major issue with heuristics for set-cover problem is that they tend to get stuck in a local optimum typically because a large local move is necessary to find a better solution. A recent theoretical result shows that replacing the objective function by a proxy (which happens to be Rosenthal potential function) allows escaping such local optima even with small local moves albeit at the cost of an approximation factor. The Rosenthal potential function thus has the effect of smoothing the optimization landscape appropriately so that local search works. In this paper, we use this theoretical insight to design a simple but robust genetic algorithm for weighted set cover. We modify the fitness function as well as the crossover operator of the genetic algorithm to leverage the Rosenthal potential function. We show empirically this greatly improves the quality of the solutions obtained especially in examples where large local moves are required.

References

1. V. Chvatal, “A greedy heuristic for the set-covering problem.” Math. Oper. Res., vol. 4, no. 3, pp. 233–235, 1979. https://doi.org/10.1287/MOOR.4.3.233
2. I. Dinur and D. Steurer, “Analytical approach to parallel repetition,” in STOC. ACM, 2014. https://doi.org/10.1145/2591796.2591884 p. 624–633.
3. K. Clarkson and K. Varadarajan, “Improved approximation algorithms for geometric set cover,” Discrete Computational Geometry, vol. 37, pp. 43–58, 2007. https://doi.org/10.1007/S00454-006-1273-8
4. A. Gupta, E. Lee, and J. Li, “A local search-based approach for set covering,” in SOSA. SIAM, 2023. https://doi.org/10.1137/1.9781611977585.CH1 pp. 1–11.
5. R. W. Rosenthal, “A class of games possessing pure-strategy nash equilibria,” Int. Jour. of Game Theory, vol. 2, pp. 65–67, 1973.
6. J. E. Beasley, “An algorithm for set covering problem,” European Journal of Operational Research, vol. 31, no. 1, pp. 85–93, 1987. https://doi.org/10.1016/0377-2217(87)90141-X
7. N. Bansal, A. Caprara, and M. Sviridenko, “A new approximation method for set covering problems, with applications to multidimensional bin packing,” SIAM J. Comput., vol. 39, pp. 1256–1278, 2009. https://doi.org/10.1137/080736831
8. J. Bautista and J. Pereira, “A grasp algorithm to solve the unicost set covering problem,” Computers & Operations Research, vol. 34, no. 10, pp. 3162–3173, 2007. https://doi.org/10.1016/j.cor.2005.11.026
9. Y. Wang, S. Pan, S. Al-Shihabi, J. Zhou, N. Yang, and M. Yin, “An improved configuration checking-based algorithm for the unicost set covering problem,” EJOR, vol. 294, no. 2, pp. 476–491, 2021. https://doi.org/10.1016/j.ejor.2021.02.015
10. Z. Naji-Azimi, P. Toth, and L. Galli, “An electromagnetism metaheuristic for the unicost set covering problem,” EJOR, vol. 205, no. 2, pp. 290–300, 2010. https://doi.org/10.1016/j.ejor.2010.01.035
11. C. Gao, X. Yao, T. Weise, and J. Li, “An efficient local search heuristic with row weighting for the unicost set covering problem,” EJOR, vol. 246, no. 3, pp. 750–761, 2015. https://doi.org/10.1016/j.ejor.2015.05.038
12. Z. Lei and S. Cai, “Solving set cover and dominating set via maximum satisfiability,” in EAAI. AAAI Press, 2020. https://doi.org/10.1609/AAAI.V34I02.5517 pp. 1569–1576.
13. M. J. Brusco, L. W. Jacobs, and G. M. Thompson, “A morphing procedure to supplement a simulated annealing heuristic for cost- andcoverage-correlated set-covering problems,” Ann. Oper. Res., vol. 86, pp. 611–627, 1999. https://doi.org/10.1023/A%3A1018900128545
14. J. Beasley and P. Chu, “A genetic algorithm for the set covering problem,” EJOR, vol. 94, no. 2, pp. 392–404, 1996. https://doi.org/10.1016/0377-2217(95)00159-X
15. B. Crawford, R. Soto, R. Cuesta, and F. Paredes, “Application of the artificial bee colony algorithm for solving the set covering problem,” Scientific World Journal, 2014. https://doi.org/10.1155/2014/189164
16. C. Luo, W. Xing, S. Cai, and C. Hu, “Nusc: An effective local search algorithm for solving the set covering problem,” IEEE Trans. Cybern., vol. 54, no. 3, pp. 1403–1416, 2024. https://doi.org/10.1109/TCYB.2022.3199147
17. T. Grossman and A. Wool, “Computational experience with approximation algorithms for the set covering problem,” EJOR, vol. 101, no. 1, pp. 81–92, 1997. https://doi.org/10.1016/S0377-2217(96)00161-0
18. S. Katoch, S. Chauhan, and V. Kumar, “A review on genetic algorithm: past, present, and future,” Multimed Tools Appl, vol. 80, p. 8091–8126, 2021. https://doi.org/10.1007/s11042-020-10139-6
19. S. Khanna, R. Motwani, M. Sudan, and U. Vazirani, “On syntactic versus computational views of approximability,” SIAM Journal on Computing, vol. 28, no. 1, pp. 164–191, 1998.
20. Y. Filmus and J. Ward, “Monotone submodular maximization over a matroid via non-oblivious local search,” SIAM Journal on Computing, vol. 43, no. 2, pp. 514–542, 2014.
21. V. Cohen-Addad, A. Gupta, L. Hu, H. Oh, and D. Saulpic, “An improved local search algorithm for k-median,” in SODA. SIAM, 2022. 10.1137/1.9781611977073.65 pp. 1556–1612.
22. D. E. Goldberg and K. Deb, “A comparative analysis of selection schemes used in genetic algorithms,” in First Workshop on Foundations of Genetic Algorithms, vol. 1. Elsevier, 1991. https://doi.org/10.1016/B978-0-08-050684-5.50008-2 pp. 69–93.
23. J. E. Beasley, “A lagrangian heuristic for set-covering problems,” Naval Research Logistics, vol. 37, pp. 151–164, 1990. https://doi.org/10.1002/1520-6750
24. D. Fulkerson, G. L. Nemhauser, and L. Trotter, “Two computationally difficult set covering problems that arise in computing the 1-width of incidence matrices of steiner triple systems,” in Approaches to integer programming, 1974. https://doi.org/10.1007/BFb0120689 pp. 72–81.