Um Algoritmo Genético Paralelo Aplicado ao Problema de Cobertura de Conjuntos
Resumo
O problema de cobertura de conjuntos (PCC) é um dos problemas mais importantes de otimização combinatória. O objetivo desse artigo é mostrar a aplicação de um Algoritmo Genético Paralelo ao PCC. A paralelização do Algoritmo Genético foi baseada no modelo de ilhas com migração unilateral. Os resultados computacionais preliminares mostram que o algoritmo proposto produz soluções de boa qualidade em um reduzido tempo computacional.
Referências
Alba, E. e Troya, M. J. M. (1999). A survey of parallel distributed genetic algorithms. Complexity, 4(4), p.31-52.
Alba, E. e Luque, G. (2005). Measuring the Performance of Parallel Metaheuristics. In Parallel Metaheuristics: A new Class of Algorithms, John Wiley & Sns, Inc., Hoboken, New Jersey, p.43-62.
Balas, E. (1980a). Cutting Planes from Conditional Bounds: A New Approach to Set Covering. Mathematical Programming, v. 12, p. 19-36.
Balas, E. e Ho, A. (1980b). Set covering algorithm using cutting planes, heuristics, and subgradient optimization: a computational study. Mathematical Programming, 12, p. 37-60.
Bartholdi, J. (1981). A Guaranteed-Accuracy Round-off Algorithm for Cyclic Scheduling and Set Covering, Operations Research, 29, p.501-510.
Beasley, J. E. (1990a). A lagrangian heuristic for set-covering problem. Naval Research Logistic, 37, p.151-164.
Beasley, J. E. (1990b). OR-Library: distributing test problems by electronic mail. Journal of the Operational Research Society, 41, p.1990-1072.
Beasley, J. E. e Chu, P. C. (1996). A genetic algorithm for the ser covering problem. European Journal of Operational Research, 94, p.392-404.
Benveniste, R. (1982). A Note on the Set Covering Problem. JORS 33, p. 261-265.
Chvàtal, V. (1979). A greed heuristic for the set covering problem. Management Science, 21, p.591-599.
Constantino, A. A., Reis, P. A., et al. (2003). Aplicação de Algoritmos Genéticos ao Problema de Cobertura de Conjunto. Simpósio Brasileiro de Pesquisa Operacional. Garey, M.R.; Johnson. D.S. (1979). Computers and intractability: a guide to the theory of NP-completeness. San Francisco, Freeman.
Holland, J. H. (1975). Adaptation in Natural and Artificial Systems. MIT Press, Cambridge, MA.
Pacheco, S. P. (1999) A User’s Guide to MPI. Disponível em: ftp://math.usfca.edu/pub/MPI/mpi.guide.ps. Acesso em 23 de janeiro de 2013.
Solar, M., Parada, V., Urrutia, R. (2002). A parallel genetic algorithm to solve the set covering problem. Computers and Operations Research, v.29, p.1221-1235.
Tanese, R. (1989). Distributed Genetic Algorithms. Proceedings of the third International Conference on Genetic Algorithms. Schaffer J. D. Editors, Morgan Kaufmann Publishers, p.434-439.
Taylor, P. e Huxley, S. (1989). A Break from Tradition for the San Francisco Police: Patrol Officer Scheduling Using an Optimization-Based Decision Support Tool. Interfaces, v. 45, p.4-24.
Vasko, F. J. e Wilson, G. R. (1984). An Efficient Heuristic for Large Set Covering Problems. Naval Research Logistic Quarterly, 31, p.163-171.
Alba, E. e Luque, G. (2005). Measuring the Performance of Parallel Metaheuristics. In Parallel Metaheuristics: A new Class of Algorithms, John Wiley & Sns, Inc., Hoboken, New Jersey, p.43-62.
Balas, E. (1980a). Cutting Planes from Conditional Bounds: A New Approach to Set Covering. Mathematical Programming, v. 12, p. 19-36.
Balas, E. e Ho, A. (1980b). Set covering algorithm using cutting planes, heuristics, and subgradient optimization: a computational study. Mathematical Programming, 12, p. 37-60.
Bartholdi, J. (1981). A Guaranteed-Accuracy Round-off Algorithm for Cyclic Scheduling and Set Covering, Operations Research, 29, p.501-510.
Beasley, J. E. (1990a). A lagrangian heuristic for set-covering problem. Naval Research Logistic, 37, p.151-164.
Beasley, J. E. (1990b). OR-Library: distributing test problems by electronic mail. Journal of the Operational Research Society, 41, p.1990-1072.
Beasley, J. E. e Chu, P. C. (1996). A genetic algorithm for the ser covering problem. European Journal of Operational Research, 94, p.392-404.
Benveniste, R. (1982). A Note on the Set Covering Problem. JORS 33, p. 261-265.
Chvàtal, V. (1979). A greed heuristic for the set covering problem. Management Science, 21, p.591-599.
Constantino, A. A., Reis, P. A., et al. (2003). Aplicação de Algoritmos Genéticos ao Problema de Cobertura de Conjunto. Simpósio Brasileiro de Pesquisa Operacional. Garey, M.R.; Johnson. D.S. (1979). Computers and intractability: a guide to the theory of NP-completeness. San Francisco, Freeman.
Holland, J. H. (1975). Adaptation in Natural and Artificial Systems. MIT Press, Cambridge, MA.
Pacheco, S. P. (1999) A User’s Guide to MPI. Disponível em: ftp://math.usfca.edu/pub/MPI/mpi.guide.ps. Acesso em 23 de janeiro de 2013.
Solar, M., Parada, V., Urrutia, R. (2002). A parallel genetic algorithm to solve the set covering problem. Computers and Operations Research, v.29, p.1221-1235.
Tanese, R. (1989). Distributed Genetic Algorithms. Proceedings of the third International Conference on Genetic Algorithms. Schaffer J. D. Editors, Morgan Kaufmann Publishers, p.434-439.
Taylor, P. e Huxley, S. (1989). A Break from Tradition for the San Francisco Police: Patrol Officer Scheduling Using an Optimization-Based Decision Support Tool. Interfaces, v. 45, p.4-24.
Vasko, F. J. e Wilson, G. R. (1984). An Efficient Heuristic for Large Set Covering Problems. Naval Research Logistic Quarterly, 31, p.163-171.
Publicado
22/05/2013
Como Citar
SILVA, Francisco Jhonatas da; OLIVEIRA, Antonio de; VERAS, Rodrigo.
Um Algoritmo Genético Paralelo Aplicado ao Problema de Cobertura de Conjuntos. In: SIMPÓSIO BRASILEIRO DE SISTEMAS DE INFORMAÇÃO (SBSI), 9. , 2013, João Pessoa.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2013
.
p. 224-229.
DOI: https://doi.org/10.5753/sbsi.2013.5690.
