APLICAÇÃO DE CAOS EM REDES NEURAIS AUTO-ORGANIZÁVEIS PARA RESOLVER PROBLEMAS DE OTIMIZAÇÃO
Josué Ervin Musial1; Paulo Henrique Siqueira1
1 Universidade Federal do Paraná
doi:10.20906/CPS/CILAMCE2015-0681
Resumo
O presente trabalho tem como objetivo apresentar uma modificação no algoritmo das redes de Mapas Auto-Organizáveis (Self- Organizing Maps - SOM) utilizando o conceito de caos determinístico para uma comparação com resultados encontrados na literatura. A solução eficiente de problemas como o de Roteamento de Veículos é fundamental na redução de custos, eficiência logística e distribuição de produtos. Desde a sua formulação em 1959, quando Dantzig e Ramser o descrevem como uma generalização do Problema do Caixeiro Viajante (Travelling Salesman Problem - TSP), sendo o segundo um problema clássico de otimização. Dada uma lista de cidades e o par de distâncias entre elas o TSP consiste em encontrar a menor rota possível que passe por todas as cidades exatamente uma vez. A solução para o TSP é classificada computacionalmente como um problema de otimização combinatória que demanda um grande esforço computacional e assim, surge um grande interesse em desenvolver heurísticas eficientes para resolvê-lo. Na literatura existem muitas heurísticas que são utilizadas na solução do TSP, como Algoritmos Genético, Busca Tabu, Simulated Annealing, Redes de Kohonen (SOM), entre outras. Como este estudo tem seu foco no algoritmo SOM, vale ressaltar que para resolver o TSP utilizando esta rede é necessário fazer uma adaptação criando uma malha de pesos conectados que envolvam, ou não, a posição geométrica das cidades. Este algoritmo produz uma aproximação dessa malha que se adapta a uma possível solução para o TSP. Na busca por melhores soluções acrescentam-se algumas alterações no algoritmo das redes SOM. Para tanto este trabalho utiliza o conceito de caos determinístico com o intuito de modificar determinadas associações de padrões (neurônio vencedor), bem como o ajuste de pesos dos neurônios vizinhos visando melhorias nas soluções encontradas tanto para o TSP como para as suas aplicações, como por exemplo no problema de roteamento de veículos.
Palavras-chave: Mapas Auto-organizáveis; Caos; Redes Neurais