Novo algoritimo genético para problemas de cobertura de conjuntos
Contribuinte(s) |
Universidade Estadual Paulista (UNESP) |
---|---|
Data(s) |
27/04/2015
27/04/2015
2011
|
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. |
Formato |
147-162 |
Identificador |
http://e-revista.unioeste.br/index.php/variascientia/article/view/3832 Varia Scientia, v. 10, n. 17, p. 147-162, 2011. 1519-9886 http://hdl.handle.net/11449/122412 ISSN1519-9886-2011-10-17-147-162.pdf 9919773182316062 2294602229519458 |
Idioma(s) |
por |
Relação |
Varia Scientia |
Direitos |
openAccess |
Palavras-Chave | #Cobertura de conjunto #algoritmos genéticos #set covering problem #genetic algorithms |
Tipo |
info:eu-repo/semantics/article |