LISTA DE PROBLEMAS

PROBLEMA DEL VENDEDOR AMBULANTE , CONTINUACIÓN I

Calculando una solución [ editar ]

Las líneas de ataque tradicionales para los problemas NP-hard son las siguientes:

• Diseño de algoritmos exactos , que funcionan razonablemente rápido solo para pequeños problemas.
• Diseño de algoritmos "subóptimos" o heurísticos , es decir, algoritmos que brindan soluciones aproximadas en un tiempo razonable.
• Encontrar casos especiales para el problema ("subproblemas") para los cuales son posibles heurísticas mejores o exactas.

Algoritmos exactos [ editar ]

La solución más directa sería probar todas las permutaciones (combinaciones ordenadas) y ver cuál es la más barata (usando la búsqueda de fuerza bruta ). El tiempo de ejecución para este enfoque se encuentra dentro de un factor polinómico de$${\ displaystyle O (n!)}, el factorial del número de ciudades, por lo que esta solución se vuelve poco práctica incluso para solo 20 ciudades.

Una de las primeras aplicaciones de la programación dinámica es el algoritmo Held-Karp que resuelve el problema a tiempo.$${\ displaystyle O (n ^ {2} 2 ^ {n})}. ^[17] Este límite también ha sido alcanzado por Exclusión-Inclusión en un intento que precede al enfoque de programación dinámica.

Solución a un TSP simétrico con 7 ciudades utilizando la búsqueda de fuerza bruta. Nota: Número de permutaciones: (7-1)! / 2 = 360

Mejorar estos límites de tiempo parece ser difícil. Por ejemplo, no se ha determinado si un algoritmo exacto para TSP que se ejecuta a tiempo$${\ displaystyle O (1.9999 ^ {n})}existe ^[18]

Otros enfoques incluyen:

• Varios algoritmos de ramificación y unión , que se pueden usar para procesar TSP que contienen entre 40 y 60 ciudades.

Solución de un TSP con 7 ciudades utilizando un algoritmo simple Branch y enlazado. Nota: El número de permutaciones es mucho menor que la búsqueda de fuerza bruta.

• Algoritmos de mejora progresiva que utilizan técnicas que recuerdan a la programación lineal . Funciona bien para hasta 200 ciudades.
• Implementaciones de generación de cortes específicos de ramificación y problemas ( ramificación y corte ^[19] ); Este es el método de elección para resolver grandes instancias. Este enfoque tiene el récord actual, resolviendo una instancia con 85,900 ciudades, ver Applegate et al. (2006) .

En 2001 se encontró una solución exacta para 15.112 ciudades alemanas de TSPLIB utilizando el método de plano de corte propuesto por George Dantzig , Ray Fulkerson y Selmer M. Johnson en 1954, basado en programación lineal . Los cálculos se realizaron en una red de 110 procesadores ubicados en la Universidad de Rice y la Universidad de Princeton . El tiempo total de cálculo fue equivalente a 22.6 años en un solo procesador Alpha de 500 MHz . En mayo de 2004, se resolvió el problema del vendedor ambulante de visitar las 24.978 ciudades de Suecia: se encontró un recorrido de aproximadamente 72.500 kilómetros de longitud y se comprobó que no existe un recorrido más corto. ^[20]En marzo de 2005, el problema del vendedor ambulante de visitar los 33.810 puntos en una placa de circuito se resolvió utilizando Concorde TSP Solver : se encontró un recorrido de 66.048.945 unidades de longitud y se comprobó que no existe un recorrido más corto. El cálculo tomó aproximadamente 15.7 años CPU (Cook et al. 2006). En abril de 2006, se resolvió una instancia con 85.900 puntos utilizando Concorde TSP Solver , con más de 136 años de CPU, ver Applegate et al. (2006) .

Algoritmos heurísticos y de aproximación [ editar ]

Se han ideado varios algoritmos de heurística y aproximación , que rápidamente dan buenas soluciones. Estos incluyen el algoritmo de fragmentos múltiples . Los métodos modernos pueden encontrar soluciones para problemas extremadamente grandes (millones de ciudades) dentro de un tiempo razonable que tienen una alta probabilidad a solo 2–3% de la solución óptima. ^[9]

Se reconocen varias categorías de heurísticas.

Heurística constructiva [ editar ]

Algoritmo de vecino más cercano para un TSP con 7 ciudades. La solución cambia a medida que cambia el punto de partida

El algoritmo vecino más cercano (NN) (un algoritmo codicioso ) le permite al vendedor elegir la ciudad no visitada más cercana como su próximo movimiento. Este algoritmo produce rápidamente una ruta efectivamente corta. Para N ciudades distribuidas aleatoriamente en un avión, el algoritmo en promedio produce una ruta un 25% más larga que la ruta más corta posible. ^[21] Sin embargo, existen muchas distribuciones de ciudades especialmente organizadas que hacen que el algoritmo NN dé la peor ruta. ^[22] Esto es cierto tanto para TSP asimétricos como simétricos. ^[23] Rosenkrantz y col. ^[24] mostró que el algoritmo NN tiene el factor de aproximación$${\ displaystyle \ Theta (\ log | V |)}para instancias que satisfacen la desigualdad del triángulo. Una variación del algoritmo NN, llamado operador Fragmento más cercano (NF), que conecta un grupo (fragmento) de ciudades no visitadas más cercanas, puede encontrar una ruta más corta con iteraciones sucesivas. ^[25] El operador NF también se puede aplicar en una solución inicial obtenida por el algoritmo NN para mejorar aún más en un modelo elitista, donde solo se aceptan mejores soluciones.

El recorrido bitónico de un conjunto de puntos es el polígono monótono de perímetro mínimo que tiene los puntos como vértices; Se puede calcular eficientemente mediante programación dinámica .

Otra heurística constructiva , Match Twice and Stitch (MTS), realiza dos emparejamientos secuenciales , donde el segundo emparejamiento se ejecuta después de eliminar todos los bordes del primer emparejamiento, para producir un conjunto de ciclos. Los ciclos se cosen para producir el recorrido final. ^[26]

Algoritmo de Christofides [ editar ]

El algoritmo de Christofides sigue un esquema similar pero combina el árbol de expansión mínima con una solución de otro problema, la coincidencia perfecta de peso mínimo . Esto proporciona un recorrido TSP que es como máximo 1,5 veces el óptimo. El algoritmo de Christofides fue uno de los primeros algoritmos de aproximación , y fue en parte responsable de llamar la atención sobre los algoritmos de aproximación como un enfoque práctico para problemas intratables. De hecho, el término "algoritmo" no se extendió comúnmente a los algoritmos de aproximación hasta más tarde; El algoritmo de Christofides se denominó inicialmente la heurística de Christofides.

Este algoritmo analiza las cosas de manera diferente mediante el uso de un resultado de la teoría de gráficos que ayuda a mejorar el LB del TSP que se originó al duplicar el costo del árbol de expansión mínima. Dado un gráfico euleriano , podemos encontrar un recorrido euleriano en$${\ displaystyle O (n)}hora. ^[6] Entonces, si tuviéramos un gráfico euleriano con ciudades de un TSP como vértices, podemos ver fácilmente que podríamos usar un método para encontrar un recorrido euleriano para encontrar una solución TSP. Por desigualdad triangular sabemos que el recorrido TSP no puede ser más largo que el recorrido Euleriano y, como tal, tenemos un LB para el TSP. Tal método se describe a continuación.

Usando un método abreviado heurístico en el gráfico creado por la coincidencia a continuación

1. Encuentre un árbol de expansión mínimo para el problema
2. Crea duplicados para cada borde para crear un gráfico euleriano
3. Encuentre un recorrido euleriano para este gráfico
4. Convierte a TSP: si una ciudad se visita dos veces, crea un atajo desde la ciudad antes de esto en el recorrido hasta el siguiente.

Para mejorar el límite inferior, se necesita una mejor manera de crear un gráfico euleriano. Por desigualdad triangular, el mejor gráfico de Eulerian debe tener el mismo costo que el mejor recorrido de vendedor ambulante, por lo tanto, encontrar gráficos de Eulerian óptimos es al menos tan difícil como TSP. Una forma de hacerlo es mediante la coincidencia de peso mínimo utilizando algoritmos de$${\ displaystyle O (n ^ {3})}. ^[6]

Crear una coincidencia

Hacer un gráfico en un gráfico euleriano comienza con el árbol de expansión mínimo. Entonces todos los vértices de orden impar deben hacerse pares. Por lo tanto, se debe agregar una coincidencia para los vértices de grados impares, lo que aumenta el orden de cada vértice de grados impares en uno. ^[6] Esto nos deja con un gráfico donde cada vértice es de orden par, por lo que es euleriano. La adaptación del método anterior da el algoritmo de Christofides,

1. Encuentre un árbol de expansión mínimo para el problema
2. Cree una coincidencia para el problema con el conjunto de ciudades de orden impar.
3. Encuentre un recorrido euleriano para este gráfico
4. Convierte a TSP usando atajos.

Mejora iterativa [ editar ]

Un ejemplo de una iteración de 2 opciones

Intercambio en parejas [ editar ]

El intercambio por pares o la técnica 2-opt implica la eliminación iterativa de dos bordes y su reemplazo por dos bordes diferentes que vuelven a conectar los fragmentos creados por la eliminación de bordes en un recorrido nuevo y más corto. Del mismo modo, el 3-opt técnica elimina 3 bordes y vuelve a conectar para formar un recorrido más corto. Estos son casos especiales del método k -opt. La etiqueta Lin-Kernighan es un nombre inapropiado para 2-opt. Lin – Kernighan es en realidad el método k-opt más general.

Para las instancias euclidianas, las heurísticas de 2 opciones dan en promedio soluciones que son aproximadamente un 5% mejores que el algoritmo de Christofides. Si comenzamos con una solución inicial hecha con un algoritmo codicioso , el número promedio de movimientos disminuye considerablemente nuevamente y es$${\ displaystyle O (n)}. Sin embargo, para comienzos aleatorios, el número promedio de movimientos es$${\ displaystyle O (n \ log (n))}. Sin embargo, si bien se trata de un pequeño aumento de tamaño, el número inicial de movimientos para problemas pequeños es 10 veces mayor para un inicio aleatorio en comparación con uno hecho de una heurística codiciosa. Esto se debe a que tales heurísticas de 2 opciones aprovechan las partes "malas" de una solución, como los cruces. Estos tipos de heurística se utilizan a menudo dentro de la heurística de problemas de enrutamiento de vehículos para reoptimizar las soluciones de ruta. ^[21]

k -opt heurística, o heurística Lin-Kernighan [ editar ]

La heurística de Lin-Kernighan es un caso especial de la técnica V -opt o variable-opt. Involucra los siguientes pasos:

1. Dado un recorrido, elimine k bordes mutuamente disjuntos.
2. Vuelva a ensamblar los fragmentos restantes en un recorrido, sin dejar subtours disjuntos (es decir, no conecte los puntos finales de un fragmento). Esto, en efecto, simplifica el TSP bajo consideración en un problema mucho más simple.
3. Cada punto final del fragmento se puede conectar a 2 k  - 2 otras posibilidades: de 2 k puntos finales totales del fragmento disponibles, los dos puntos finales del fragmento en consideración no están permitidos. Tal TSP de 2 k- ciudades con restricciones se puede resolver con métodos de fuerza bruta para encontrar la recombinación de menor costo de los fragmentos originales.

El más popular de los métodos k -opt es 3-opt, como lo introdujo Shen Lin de Bell Labs en 1965. Un caso especial de 3-opt es donde los bordes no son disjuntos (dos de los bordes son adyacentes entre sí) . En la práctica, a menudo es posible lograr una mejora sustancial con respecto a la opción 2 sin el costo combinatorio de la opción 3 general al restringir los 3 cambios a este subconjunto especial donde dos de los bordes eliminados son adyacentes. Esta llamada opción de dos opciones y media generalmente cae aproximadamente a medio camino entre 2 opciones y 3 opciones, tanto en términos de la calidad de los recorridos logrados como del tiempo requerido para lograr esos recorridos.

V -opt heurístico [ editar ]

El método de opción variable está relacionado con una generalización del método k -opt. Mientras que los métodos k -opt eliminan un número fijo ( k ) de bordes del recorrido original, los métodos de opción variable no fijan el tamaño del conjunto de bordes para eliminar. En cambio, hacen crecer el conjunto a medida que continúa el proceso de búsqueda. El método más conocido en esta familia es el método Lin-Kernighan (mencionado anteriormente como un nombre inapropiado para 2-opt). Shen Lin y Brian Kernighanpublicó su método por primera vez en 1972, y fue la heurística más confiable para resolver problemas de vendedores ambulantes durante casi dos décadas. David Johnson y su equipo de investigación desarrollaron métodos de opción variable más avanzados en Bell Labs a fines de la década de 1980. Estos métodos (a veces llamados Lin – Kernighan – Johnson ) se basan en el método Lin – Kernighan, agregando ideas de la búsqueda tabú y la computación evolutiva . La técnica básica de Lin-Kernighan da resultados que se garantiza que son al menos 3-opt. Los métodos Lin – Kernighan – Johnson calculan un recorrido Lin – Kernighan, y luego perturban el recorrido por lo que se ha descrito como una mutación que elimina al menos cuatro bordes y vuelve a conectar el recorrido de una manera diferente, luego V-opción de la nueva gira. La mutación a menudo es suficiente para mover el recorrido desde el mínimo local identificado por Lin-Kernighan. Los métodos V -opt son ampliamente considerados como la heurística más poderosa para el problema y pueden abordar casos especiales, como el problema del ciclo de Hamilton y otros TSP no métricos en los que otras heurísticas fallan. Durante muchos años, Lin – Kernighan – Johnson había identificado soluciones óptimas para todos los TSP en los que se conocía una solución óptima y había identificado las mejores soluciones conocidas para todos los otros TSP en los que se había probado el método.

Mejora aleatorizada [ editar ]

Los algoritmos de cadena de Markov optimizados que utilizan sub-algoritmos heurísticos de búsqueda local pueden encontrar una ruta extremadamente cercana a la ruta óptima para 700 a 800 ciudades.

TSP es una piedra de toque para muchas heurísticas generales diseñadas para la optimización combinatoria, como algoritmos genéticos , recocido simulado , búsqueda tabú , optimización de colonias de hormigas , dinámica de formación de ríos (ver inteligencia de enjambre ) y el método de entropía cruzada .

Optimización de colonias de hormigas [ editar ]

Artículo principal: algoritmos de optimización de colonias de hormigas

El investigador de inteligencia artificial Marco Dorigo describió en 1993 un método de generar heurísticamente "buenas soluciones" para el TSP utilizando una simulación de una colonia de hormigas llamada ACS ( sistema de colonias de hormigas ). ^[27] Modela el comportamiento observado en hormigas reales para encontrar caminos cortos entre las fuentes de alimentos y su nido, un comportamiento emergente que resulta de la preferencia de cada hormiga de seguir las feromonas de rastro depositadas por otras hormigas.

ACS envía una gran cantidad de agentes de hormigas virtuales para explorar muchas rutas posibles en el mapa. Cada hormiga elige probabilísticamente la siguiente ciudad para visitar en función de una heurística que combina la distancia a la ciudad y la cantidad de feromona virtual depositada en el borde de la ciudad. Las hormigas exploran, depositando feromonas en cada borde que cruzan, hasta que hayan completado un recorrido. En este punto, la hormiga que completó el recorrido más corto deposita feromona virtual a lo largo de su ruta completa ( actualización global de senderos ). La cantidad de feromona depositada es inversamente proporcional a la duración del recorrido: cuanto más corto es el recorrido, más se deposita.

Algoritmo de optimización de colonias de hormigas para un TSP con 7 ciudades: las líneas rojas y gruesas en el mapa de feromonas indican la presencia de más feromonas