En optimización, 3-opt es un algoritmo de búsqueda local simple para resolver el problema del vendedor ambulante y los problemas relacionados con la optimización de la red . Comparado con el algoritmo de 2 opciones más simple , es más lento pero puede generar soluciones de mayor calidad.
El análisis de 3 opciones implica eliminar 3 conexiones (o bordes) en una red (o recorrido), para crear 3 sub recorridos. Luego se analizan las 7 formas diferentes de reconectar la red para encontrar la óptima. Este proceso se repite luego para un conjunto diferente de 3 conexiones, hasta que se hayan probado todas las combinaciones posibles en una red. Una sola ejecución de 3-opt tiene una complejidad de tiempo de. [1] El 3-opt iterado tiene una mayor complejidad de tiempo.
Este es el mecanismo por el cual el intercambio de 3 opciones manipula una ruta determinada:
def reverse_segment_if_better ( tour , i , j , k ): "" "Si el tour inverso [i: j] haría el tour más corto, entonces hazlo." "" # Tour dado [... AB ... CD .. .EF ...] A , B , C , D , E , F = recorrido [ i - 1 ], recorrido [ i ], recorrido [ j - 1 ], recorrido [ j ], recorrido [ k - 1 ], recorrido [ k % len ( recorrido )] d0 = distancia ( A , B ) + distancia ( C , D ) + distancia ( E , F ) d1 = distancia ( A , C ) + distancia ( B , D ) + distancia ( E , F ) d2 = distancia ( A , B ) + distancia ( C , E ) + distancia ( D , F ) d3 = distancia ( A , D ) + distancia ( E , B ) + distancia ( C , F ) d4 = distancia ( F , B ) + distancia ( C , D ) + distancia ( E , A ) if d0 > d1 : tour [ i : j ] = invertido ( tour [ i : j ]) return - d0 + d1 elif d0 > d2 : tour [ j : k ] = invertido ( tour [ j : k ]) return - d0 + d2 elif d0 > d4 : recorrido [ i : k ] = invertido ( recorrido [ i : k ]) retorno - d0 + d4 elif d0 > d3 : tmp = recorrido [ j : k ] + recorrido [ i : j ] recorrido [ i : k ] = tmp return - d0 + d3 return 0
El principio es bastante simple. Tu calculas la distancia originaly calcula el costo de cada modificación. Si encuentra un mejor costo, aplique la modificación y devuelva(coste relativo). Este es el intercambio completo de 3 opciones que hace uso del mecanismo anterior:
def three_opt ( tour ): "" "Mejora iterativa basada en el intercambio 3." "" while True : delta = 0 para ( a , b , c ) en all_segments ( len ( tour )): delta + = reverse_segment_if_better ( tour , a , b , c ) si delta > = 0 : tour de retorno de ruptura def all_segments ( n : int ): "" "Genera todas las combinaciones de segmentos" "" return (( i , j , k ) para i en rango ( n ) para j en rango ( i + 2 , n ) para k en rango ( j + 2 , n + ( i > 0 )))
Para el recorrido dado, genera todas las combinaciones de segmentos y para cada combinación, intenta mejorar el recorrido invirtiendo los segmentos. Mientras encuentre un mejor resultado, reinicie el proceso, de lo contrario finalice.
Ver también
Referencias
- F. BOCK (1965). Un algoritmo para resolver problemas de optimización de red relacionados con el vendedor ambulante . manuscrito inédito asociado a la charla presentada en el 14º Encuentro Nacional ORSA .
- S. LIN (1965). Soluciones informáticas del problema del viajante . Bell Syst. Tech. J. 44, 2245-2269.Disponible como PDF [ enlace muerto permanente ]
- S. LIN Y BW KERNIGHAN (1973). Un algoritmo heurístico eficaz para el problema del vendedor ambulante . Operaciones Res. 21, 498-516.Disponible como PDF [ enlace muerto permanente ]
- Heurística de búsqueda local. (nd) Obtenido el 16 de junio de 2008 de http://www.tmsk.uitm.edu.my/~naimah/csc751/slides/LS.pdf [ enlace muerto permanente ]