Novo algoritimo genético para problemas de cobertura de conjuntos
Carregando...
Data
2011
Autores
Constantino, Ademir Aparecido
Santos, Andréia Alves dos
Araujo, Silvio Alexandre de [UNESP]
Título da Revista
ISSN da Revista
Título de Volume
Editor
Resumo
The Set Covering Problem (SCP) plays an important role in Operational Research since it can be found as part of several real-world problems. In this work we report the use of a genetic algorithm to solve SCP. The algorithm starts with a population chosen by a randomized greedy algorithm. A new crossover operator and a new adaptive mutation operator were incorporated into the algorithm to intensify the search. Our algorithm was tested for a class of non-unicost SCP obtained from OR-Library without applying reduction techniques. The algorithms found good solutions in terms of quality and computational time. The results reveal that the proposed algorithm is able to find a high quality solution and is faster than recently published approaches algorithm is able to find a high quality solution and is faster than recently published approaches using the OR-Library.
O Problema de Cobertura de Conjuntos (PCC) é bastante importante em Pesquisa Operacional, pois, pode ser encontrado como parte de vários problemas reais. Neste trabalho é reportado o uso de um algoritmo genético para resolver o PCC. O Algoritmo inicia com uma população gerada por uma heurística gulosa randômica. Um novo operador de cruzamento e um novo operador adaptativo de mutação foram incorporados para intensificar a busca. Nosso algoritmo foi testado para uma classe de exemplos “non-unicost”, obtido da “OR-Library”, sem aplicar técnicas de redução. O Algoritmo encontrou boas soluções em termos de qualidade e tempo computacional. Os resultados revelam que o algoritmo proposto é capaz de encontrar soluções de boa qualidade de maneira mais rápida do que algumas abordagens recentemente publicadas na literatura usando as instâncias da OR-Library.
O Problema de Cobertura de Conjuntos (PCC) é bastante importante em Pesquisa Operacional, pois, pode ser encontrado como parte de vários problemas reais. Neste trabalho é reportado o uso de um algoritmo genético para resolver o PCC. O Algoritmo inicia com uma população gerada por uma heurística gulosa randômica. Um novo operador de cruzamento e um novo operador adaptativo de mutação foram incorporados para intensificar a busca. Nosso algoritmo foi testado para uma classe de exemplos “non-unicost”, obtido da “OR-Library”, sem aplicar técnicas de redução. O Algoritmo encontrou boas soluções em termos de qualidade e tempo computacional. Os resultados revelam que o algoritmo proposto é capaz de encontrar soluções de boa qualidade de maneira mais rápida do que algumas abordagens recentemente publicadas na literatura usando as instâncias da OR-Library.
Descrição
Palavras-chave
Cobertura de conjunto, algoritmos genéticos, set covering problem, genetic algorithms
Como citar
Varia Scientia, v. 10, n. 17, p. 147-162, 2011.