Um algoritmo genético para a solução de problemas específicos de programação inteira. / A genetic algorithm for solving specific problems integer programming.

AUTOR(ES)
FONTE

IBICT - Instituto Brasileiro de Informação em Ciência e Tecnologia

DATA DE PUBLICAÇÃO

26/03/2010

RESUMO

Vários são os algoritmos existentes para solucionar problemas de otimização combinatória. Para modelos que possuam um grande número de variáveis e restrições, e principalmente se essas variáveis são binárias, o tempo de resposta desses métodos se torna impraticável. Diante desta dificuldade e da grande importância prática de tais problemas, vem-se realizando um considerável esforço para se obter melhores soluções. Assim, parte dos trabalhos que enfocam problemas de otimização combinatória utiliza métodos aproximativos, heurísticas e/ou metaheurísticas. Este trabalho conduz a implementação de um Algoritmo Genético, que é uma meta-heurística populacional cuja eficácia é comprovada pelo grande número de trabalhos publicados na área. O propósito deste trabalho é desenvolver um algoritmo que obtenha boas soluções para algumas instâncias de problemas clássicos de otimização combinatória. Tais problemas modelados por programação inteira linear são resolvidos em um tempo computacional aceitável, usando a meta-heurística citada. O desempenho é medido através da qualidade das soluções, do esforço computacional e do tamanho da instância. Possui uma abordagem quantitativa, é, por natureza, uma pesquisa explicativa e faz uso de um método experimental. Utiliza a linguagem de programação Java, em um computador com processador Core 2 Duo e Windows XP como sistema operacional. O trabalho utiliza instâncias extraídas de uma biblioteca de testes largamente utilizada para validação de diversos trabalhos sobre otimização combinatória. O algoritmo proposto obteve boas soluções, próximas da ótima, em um tempo computacional aceitável, devido à qualidade da população inicial e à forma de implementação dos operadores genéticos. Esta última, através de um aumento na taxa de mutação e uma combinação harmoniosa entre técnicas de cruzamento, influenciou de forma significativa nos resultados obtidos.

ASSUNTO(S)

algoritmo genético programação inteira otimização combinatória ciencia da computacao genetic algorithm integer programming combinatorial optimization

ACESSO AO ARTIGO

Documentos Relacionados