Los mapas de rasgos autoorganizativos y el problema del viajante de comercio

Resumen

Esta Tesis se centra en la aplicación de los Mapas de Rasgos Autoorganizativos (SOFM) de Kohonen a la resolución del Problema del Viajante de Comercio (TSP) bidimensional en el espacio Euclídeo, El problema se define como un conjunto de n pares de valores (x,y), que representan las coordenadas de las ciudades. Se toma una red cuya capa de salida estara formada por al menos n neuronas, organizadas en un vector. Para definir, un anillo, el ultimo elemento del vector se considera vecino inmediato del primero. Durante el entrenamiento, se presentan a la entrada de la red de forma iterativa los pares (x,y), para permitir que los pesos de las neuronas se aproximen a las coordenadas de las ciudades. Al concluir el entrenamiento, cada ciudad tendrá alguna neurona asociada y el camino a seguir vendrá determinado por las ciudades asociadas a las sucesivas neuronas del vector que define la capa de salida. Los SOFM dan una representación atrativa del espacio de entrada, ya que las neuronas no sólo están situadas de acuerdo con la distribución por probabilidad descrita por los vectores de entrada, sino que también hay una ordenación topológica de éstas que refleja la estructura del espacio de entrada. Por ello, su aplicación a problemas como el TSP, con una estructura espacial clara, resulta lógica. El trabajo parte del algoritmo basico de Kohonen. Se analizan los resultados obtenidos y se estudia la problemática planteada. Como resultado del estudio, se ha desarrollado una Red de tipo Autoorganizativo que soluciona los problemas observados en el modelo basico y genera mejores soluciones. El trabajo se completa con una descripcion de los sistemas de Redes Neuronales Artificiales y una revisión en las tecnicas mas utilizadas para resolver el TSP, tanto las clasicas como las basadas en Redes Neuronales.