python - tsp - Vendedor ambulante con una restricción direccional.
python genetic algorithm travelling salesman problem (1)
A juzgar por la documentación en pytsp, la matriz de distancia no tiene que ser simétrica. Esto significa que podría modificar la norma L2 para incorporar información sobre una dirección preferida en esa matriz. Digamos que tienes una dirección preferida para algunos pares de puntos (i, j), luego para cada uno de estos puntos podrías dividir dists[i,j] por (1+a) y multiplicar dists[j,i] por (1+a) Hacer más favorable esa dirección. Esto significa que si su algoritmo está seguro de encontrar el óptimo global, puede forzarlo para que satisfaga su dirección preferida tomando a es lo suficientemente grande.
Además, no estoy seguro de que sea imposible tener bucles cerrados en una solución donde la matriz de distancia se toma de datos 3D. Me parece que el ''no bucle cerrado'' es un resultado (de la desigualdad del triángulo) específico de 2D.
Estoy tratando de ordenar una serie de coordenadas 3D por su orden a lo largo de una ruta. Una muestra:
points = np.array([[ 0.81127451, 0.22794118, 0.52009804],
[ 0.62986425, 0.4546003 , 0.12971342],
[ 0.50666667, 0.41137255, 0.65215686],
[ 0.79526144, 0.58186275, 0.04738562],
[ 0.55163399, 0.49803922, 0.24117647],
[ 0.47385621, 0.64084967, 0.10653595]])
Los puntos están en orden aleatorio, pero siempre hay un solo camino a través de ellos. Estoy encontrando el camino con un problema adaptado de vendedor ambulante (TSP), utilizando el solucionador LKH (Helsgaun 2009). Implica dos modificaciones:
- Agregue un punto en o cerca del origen. Esto encuentra el mejor punto de partida en cada instancia que he abordado hasta ahora. Esta fue mi idea, no tengo otra base para ello.
- Agregue un punto a una distancia de cero desde cada punto. Esto hace que el solucionador encuentre una ruta hacia el otro extremo de la ruta. Esta idea fue de esta pregunta SO .
Tenga en cuenta que el TSP no implica la posición , solo las distancias entre los nodos. Así que el solucionador "sabe" (o importa) que estoy trabajando en 3D. Acabo de hacer una matriz de distancia así:
import numpy as np
from scipy.spatial.distance import pdist, squareform
# Add a point near the origin.
points = np.vstack([[[0.25, 0, 0.5]], points])
dists = squareform(pdist(points, ''euclidean''))
# Normalize to int16s because the solver likes it.
d = 32767 * dists / np.sqrt(3)
d = d.astype(np.int16)
# Add a point that is zero units from every other point.
row, col = d.shape
d = np.insert(d, row, 0, axis=0)
d = np.insert(d, col, 0, axis=1)
Paso esto a mi fork de pytsp , que se lo pasa al solucionador LKH. Y todo está bien ... excepto cuando el camino se cruza. Las soluciones de TSP no pueden tener bucles cerrados, así que siempre se muestra el bucle abierto a la derecha aquí:
Tenga en cuenta que esta es una versión 2D análoga de mi situación. Tenga en cuenta también que los puntos están alineados de manera imperfecta, incluso a lo largo de los bits "rectos".
Así que mi pregunta es: ¿cómo puedo ayudar al solucionador a preservar la dirección del camino siempre que sea posible? Tengo dos ideas mal formadas, pero hasta ahora no he podido implementar nada:
- Usa otra métrica en lugar de L2. Pero no creo que esto pueda funcionar, porque en un cruce dado, no hay nada intrínsecamente diferente sobre el punto "incorrecto". Su error depende del punto anterior. Y aún no sabemos cuál es el punto anterior (eso es lo que estamos tratando de resolver). Así que creo que esto no es bueno.
- Evalúe la colinealidad local de cada conjunto de tres puntos (por ejemplo, usando el determinante de cada triple). Module la ''pendiente 3D'' local (no estoy seguro de lo que quiero decir) con este coeficiente de colinealidad. Dar a cada punto otra dimensión que exprese esta alineación local. Ahora la norma reflejará la alineación local y (con suerte) las cosas colineales se unirán.
He puesto estos archivos en Dropbox:
Gracias por leer; Cualquier idea apreciada.
Referencia
K. Helsgaun, General k-opt submoves para la heurística TSP Lin-Kernighan. Computación de programación matemática, 2009, doi: 10.1007 / s12532-009-0004-6 .