Use este identificador para citar ou linkar para este item: http://repositorio.utfpr.edu.br/jspui/handle/1/205
Título: Otimização por nuvem de partículas aplicada ao problema de atribuição de tarefas dinâmico
Autor(es): Pierobom, Jean Lima
Orientador(es): Kaestner, Celso Antonio Alves
Palavras-chave: Inteligência coletiva
Otimização combinatória
Otimização matemática
Inteligência artificial
Algorítmos computacionais
Simulação (Computadores)
Swarm intelligence
Combinatorial optimization
Mathematical optimization
Automatic theorem proving
Computer algorithms
Computer simulation
Artificial intelligence
Demonstração automática de teoremas
Data do documento: 13-Fev-2012
Editor: Universidade Tecnológica Federal do Paraná
Câmpus: Curitiba
Citação: PIEROBOM, Jean Lima. Otimização por nuvem de partículas aplicada ao problema de atribuição de tarefas dinâmico. 2011. 83 f. Dissertação (Mestrado em Computação Aplicada) – Universidade Tecnológica Federal do Paraná, Curitiba, 2011.
Resumo: A Inteligência de Enxame (Swarm Intelligence) é uma área de estudos que busca soluções para problemas de otimização utilizando-se de técnicas computacionais inspiradas no comportamento social emergente encontrado na biologia. A metaheurística Particle Swarm Optimization (PSO) é relativamente nova e foi inspirada no comportamento social de bandos de pássaros. PSO tem apresentado bons resultados em alguns trabalhos recentes de otimização discreta, apesar de ter sido concebido originalmente para a otimização de problemas contínuos. Este trabalho trata o Problema de Atribuição de Tarefas - Task Assignment Problem (TAP), e apresenta uma aplicação: o problema de alocação de táxis e clientes, cujo objetivo da otimização está em minimizar a distância percorrida pela frota. Primeiramente, o problema é resolvido em um cenário estático, com duas versões do PSO discreto: a primeira abordagem é baseada em codificação binária e a segunda utiliza permutações para codificar as soluções. Os resultados obtidos mostram que a segunda abordagem é superior à primeira em termos de qualidade das soluções e tempo computacional, e é capaz de encontrar as soluções ótimas para o problema nas instâncias para as quais os valores ótimos são conhecidos. A partir disto, o algoritmo é adaptado para a otimização do problema em um ambiente dinâmico, com a aplicação de diferentes estratégias de resposta às mudanças. Os novos resultados mostram que a combinação de algumas abordagens habilita o algoritmo PSO a obter boas soluções ao longo da ocorrência de mudanças nas variáveis de decisão problema, em todas as instâncias testadas, com diferentes tamanhos e escalas de mudança.
Abstract: Swarm Intelligence searches for solutions to optimization problems using computational techniques inspired in the emerging social behavior found in biology. The metaheuristic Particle Swarm Optimization (PSO) is relatively new and can be considered a metaphor of bird flocks. PSO has shown good results in some recent works of discrete optimization, despite it has been originally designed for continuous optimization problems. This paper deals with the Task Assignment Problem (TAP), and presents an application: the optimization problem of allocation of taxis and customers, whose goal is to minimize the distance traveled by the fleet. The problem is solved in a static scenario with two versions of the discrete PSO: the first approach that is based on a binary codification and the second one which uses permutations to encode the solution. The obtained results show that the second approach is superior than the first one in terms of quality of the solutions and computational time, and it is capable of achieving the known optimal values in the tested instances of the problem. From this, the algorithm is adapted for the optimization of the problem in a dynamic environment, with the application of different strategies to respond to changes. The new results show that some combination of approaches enables the PSO algorithm to achieve good solutions along the occurrence of changes in decision variables problem, in all instances tested, with different sizes and scales of change.
URI: http://repositorio.utfpr.edu.br/jspui/handle/1/205
Aparece nas coleções:CT - Programa de Pós-Graduação em Computação Aplicada

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
CT_PPGCA_Pierobom, Jean Lima_2011.pdf3,81 MBAdobe PDFThumbnail
Visualizar/Abrir


Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.