Novo algoritimo genético para problemas de cobertura de conjuntos


Autoria(s): Constantino, Ademir Aparecido; Santos, Andréia Alves dos; Araujo, Silvio Alexandre de
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