An Improved Genetic Algorithm for Set Cover using Rosenthal Potential

• Autorzy: Tayebi Dena , Ray Saurabh , Ajwani Deepak

Identyfikatory

DOI

10.15439/2024F7060

• Konferencja: Federated Conference on Computer Science and Information Systems (19 ; 08-11.09.2024 ; Belgrade, Serbia)
• Języki publikacji: EN

Abstrakty

EN

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. Our results are better than existing state of the art genetic algorithms and also comparable in performance with the recent local search algorithm NuSC (carefully engineered for set cover) on benchmark instances. Our algorithm, however, performs better than NuSC on simple synthetic instances where starting from an initial solution, large local moves are necessary to find a solution that is close to optimal. For such instances, our algorithm is able to find near optimal solutions whereas NuSC either takes a very long time or returns a much worse solution.

Słowa kluczowe

EN

computer science; smoothing methods; cost; heuristic algorithms; benchmark testing; linear programming; search problems; optimization; genetic algorithms

PL

informatyka; koszt; algorytmy heurystyczne; testy porównawcze; programowanie liniowe; optymalizacja; algorytmy genetyczne

• Wydawca: Polskie Towarzystwo Informatyczne
• Czasopismo: Annals of Computer Science and Information Systems
• Rocznik: 2024
• Tom: Vol. 39
• Strony: 689--694
• Opis fizyczny: Bibliogr. 24 poz., tab., wz.

Twórcy

autor

Tayebi Dena

• University College Dublin Ireland

• https://orcid.org/0000-0001-6447-7930

autor

Ray Saurabh

• New York University Abu Dhabi

• https://orcid.org/0009-0005-6708-125X

autor

Ajwani Deepak

• University College Dublin Ireland

• https://orcid.org/0000-0001-7269-4150

Bibliografia

• 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.

Uwagi

Thematic Sessions: Short Papers