Detalhes bibliográficos
Ano de defesa: |
2010 |
Autor(a) principal: |
Almeida, Francisco Wescley Cunha de |
Orientador(a): |
Não Informado pela instituição |
Banca de defesa: |
Não Informado pela instituição |
Tipo de documento: |
Dissertação
|
Tipo de acesso: |
Acesso aberto |
Idioma: |
por |
Instituição de defesa: |
Universidade Estadual do Ceará
|
Programa de Pós-Graduação: |
Não Informado pela instituição
|
Departamento: |
Não Informado pela instituição
|
País: |
Não Informado pela instituição
|
Palavras-chave em Português: |
|
Link de acesso: |
https://siduece.uece.br/siduece/trabalhoAcademicoPublico.jsf?id=59987
|
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 meta-heurí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. Palavras-chave: Algoritmo Genético. Programação Inteira. Otimização Combinatória. |