Novo algoritimo genético para problemas de cobertura de conjuntos

Abstract

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.