SIQUEIRA, Paulo Henrique

Neste trabalho são apresentadas duas Redes Neurais Recorrentes para resolver o problema da Designação Linear. Na fase inicial do problema, onde os elementos da matriz de custos do problema da Designação devem ser determinados, utiliza-se Mapas de Kohonen, conhecidos também como Mapas Auto-Organizáveis, e na resolução do problema da Designação propriamente dito, a técnica utilizada é a Rede Neural Recorrente de Wang, com a aplicação de um princípio aqui proposto, denominado Winner Takes All. A fase de definição dos custos na resolução de um problema da Designação é de grande importância, pois se os custos não forem determinados de forma adequada, a solução final não será a ideal. O cálculo de custos para problemas da Designação com a utilização de Redes Neurais Artificiais é um assunto pouco explorado, que depende do tipo de aplicação pretendida. Quando a matriz de custos do problema da Designação é tal que admite múltiplas soluções ótimas, ou soluções ótimas locais muito próximas, a Rede Neural de Wang não converge, e a proposta apresentada neste trabalho mostra a utilização do princípio Winner Takes All para esta rede, obtendo-se soluções ótimas globais na maioria das matrizes testadas, utilizando-se aproximadamente 1% do número necessário de iterações da Rede de Wang original. Neste trabalho são apresentados os resultados da aplicação desta técnica (a Rede Neural Recorrente de Wang com o princípio Winner Takes All) para 73 matrizes com custos definidos aleatoriamente para o problema da Designação, além de alguns critérios para ajustes de parâmetros da Rede Neural de Wang, entre eles alguns tradicionais, e outros que utilizam medidas de dispersão entre os elementos da matriz de custos do problema. A metodologia proposta neste trabalho é aplicada em um estudo de caso: o Problema de Alocação de Salas de Aula para disciplinas de graduação e pós-graduação da UFPR, onde são testados mapas com diversas dimensões para a determinação dos custos deste problema. Os resultados encontrados com a aplicação desta metodologia no estudo de caso são considerados satisfatórios, com erro médio na solução final da Designação inferior a 3% para os melhores mapas encontrados. Uma outra aplicação da Rede Neural de Wang com o princípio Winner Takes All é a resolução do problema clássico do Caixeiro Viajante, com soluções ótimas globais em vários problemas do banco de dados TSPLIB, e com soluções ótimas locais com erros inferiores a 16%. Para aplicar a metodologia proposta neste trabalho para o problema do Caixeiro Viajante uma adaptação do princípio Winner Takes All é feita, obtendo-se sempre rotas factíveis para este problema. A mesma técnica é utilizada para problemas do Caixeiro Viajante simétricos e assimétricos, e a técnica 2-opt é utilizada para melhorar as soluções encontradas.

Palavras-chave: Resolução de problemas.