Una hiperheurística para la solución del Problema del Viajante Asimétrico

Partes: 1, 2

Resumen
Revisión
bibliográfica
Solución del
problema
Conclusiones
Referencias

Resumen

El uso de métodos
aproximativos eficientes para obtener soluciones
cercanas a las óptimas en diversos problemas
combinatorios complejos es de gran interés
por la gran cantidad de aplicaciones que tienen. La literatura refleja diversos
algoritmos
heurísticos, metaheurísticos o híbridos para
la solución de problemas, pero muy pocos con enfoques
hiperheurísticos.

En general, los primeros métodos mencionados
requieren de un dominio de los
especialistas y un trabajo previo
de ajuste de parámetros para ser exitosos en una amplia
gama de instancias de un problema concreto.

En este trabajo se propone una hiperheurística
para el Problema del Viajante Asimétrico. La literatura
revisada no refleja la utilización de este método
para este tipo de problema. El objetivo
fundamental no es competir con métodos eficientes
existentes para mejorar la calidad de las
soluciones obtenidas por los mismos, sino obtener un
método robusto que se eficiente.

Para el diseño
de la hiperheurística propuesta se definen diversas
heurísticas simples y estructuras de
vecindad, que se utilizan en métodos de búsqueda
local. Se realiza un diseño de experimento con un conjunto
de instancias descritas en la literatura, y se muestran los
resultados obtenidos.

Palabras claves

Problemas combinatoriales, heurísticas,
metaheurísticas, hiperheurísticas, el Problema del
Viajante Asimétrico.

Introducción

Se pueden encontrar una gran cantidad de problemas
reales que son modelados y resueltos con técnicas
de optimización. Entre los que pueden mencionarse
están los clásicos problemas de diseño de
redes de
telecomunicación, los de planificación de horarios, los de
secuenciación de tareas, los distintos problemas de ruteo,
u organización de la producción hasta los más actuales en
ingeniería y re-ingeniería de
software. Algunas clases de estos problemas son relativamente
fáciles de resolver, este es el caso, por ejemplo, de los
problemas lineales, en los que tanto la función
objetivo como las restricciones son expresiones lineales, que
pueden ser resueltos con el conocido método
Simplex; sin embargo, muchos otros tipos de problemas de
optimización son muy difíciles de resolver, y gran
parte de ellos corresponden a problemas de Optimización
Combinatorial.

Estos problemas difíciles de interés
práctico resultan intratables si se trata de obtener una
solución óptima en un tiempo
razonable mediante técnicas de cálculo.
Ante esta dificultad, los algoritmos heurísticos se
revelan como un medio útil para su resolución, ya
que permiten obtener buenas soluciones, en algunos casos
óptimas, en un tiempo razonable. En los últimos
años ha cobrado auge el uso de las metaheurísticas
[29] que son algoritmos aproximativos, aplicándolos a una
gama de diferentes problemas. Entre ellos se encuentra el
Recocido Simulado [10], el Greedy Randomized Adaptive Search
Procedures (GRASP) [12], Búsquedas Tabú [22] o
los Algoritmos Genéticos [16]. Existen numerosos trabajos
con aplicaciones de estos métodos en diferentes revistas
especializadas de Investigación Operativa.

Sin embargo, esta clase de
algoritmos presentan esta clase de inconvenientes cuando se trata
de aplicarlos a un problema específico:

El número de parámetros a ser ajustados
para obtener un buen desempeño del algoritmo
puede requerir un tiempo considerable.
La comprensión de estos parámetros,
básicamente para un usuario no especializados en estos
métodos. Puede citarse, por ejemplo, que en los
Algoritmos Genéticos es bastante fácil de
entender que mientras el tamaño de la población es mas grande, los resultados
obtenidos deben ser mejores aunque con un costo de
tiempo mayor. Sin embargo no está muy claro cual
sería la incidencia en la ejecución del algoritmo
los ajustes de parámetros, como la probabilidad de
cruzamientos. Otro ejemplo es el Recocido Simulado, donde la
literatura describe que los mejores valores de
r (la velocidad en
que disminuye la temperatura), se obtiene solo de extensos
diseños de experimento.
Para un mismo tipo de problema, los parámetros
ajustados pueden no ser los mejores para cualquier tipo de
instancia, pueden depender, por ejemplo, del tamaño de
la instancia, las características de una matriz de
costos,
etc.

Mucho más reciente, cuya literatura aún es
escasa, es el uso de métodos hiperheurísticos [9]
para la solución de problemas combinatoriales. Estos
métodos eliminan las inconveniencias planteadas de las
metaheurísticas.

El propósito fundamental de este trabajo es
realizar el diseño de un algoritmo hiperheurístico
que solucione de forma eficiente, teniendo en cuenta la calidad
de la solución y tiempo de ejecución, una amplia
gama de instancias del Problema del Viajante Asimétrico
(PVA). Colateralmente, que también pueda ser extensible a
otros problemas como el Problema de la Mochila Binaria
(PMB).

El por qué se diseña una
hiperheurística para el PVA está dado
básicamente por las siguientes razones: resolver un
problema real surgido en la planificación del
teñido de telas en la industria
textil [25, 26 y 30], el cual es modelado por el PVA el cual es
NP – completo [14] al cual se le han aplicado diversos
algoritmos heurísticos e
metaheurísticos.

La literatura reporta bibliotecas de
instancias generadas con el fin de evaluar la calidad del
desempeño de nuevos métodos realizados para este
problema [33].

El documento tiene una estructura
formada por tres epígrafes, las conclusiones y
recomendaciones. En el primer epígrafe se realiza un
análisis bibliográfico a las
literaturas utilizadas, en el segundo propone la solución
al problema, el tercero ofrece un diseño de experimento a
los resultados obtenidos.

2.1 El Problema del Viajante
Asimétrico
El Problema del Viajante Asimétrico [4 y 7],
más conocido por su nombre en ingles The Asymmetric
Traveling Salesman Problem, es quizá el problema
de optimización combinatorial más popular de
todos. De la manera más simple, el PAV consiste, en
dadas un conjunto de n ciudades un vendedor debe
visitar cada una de ellas una sola vez y regresar a su ciudad
de origen, de tal forma que su recorrido sea mínimo.
Matemáticamente para cada par de ciudades , se denota como
la distancia
entre ellas, la meta es
encontrar una permutación de las ciudades que
minimice:
Existen diversas heurísticas constructivas y
de búsquedas para la solución de este problema.
Entre las heurísticas constructivas encontradas para
este problema se encuentra la popular estrategia
voraz, la del vecino más cercano, la técnica de
remiendo, etc.
2.1.1 Métodos constructivos
Las heurísticas constructivas aportan
soluciones del problema por medio de un procedimiento
que incorpora iterativamente elementos a una estructura,
inicialmente vacía, que representa a la
solución. Las heurísticas constructivas
establecen estrategias para seleccionar las componentes
con las que se construye una buena solución del
problema.
Una de las mejores metaheurística
constructivas sin duda alguna es GRASP [12], en su
diseño el parámetro alfa es un aspecto bien
discutido. Los diferentes autores que han utilizado este
método lo definen después de realizar un
análisis estadístico a su problema con
diferentes valores. Los
valores extremos de este parámetro brinda dos
tipos de soluciones: golosas y aleatorias . Existen diversas variantes
eficientes del método GRASP, una de ellas por ejemplo,
es la llamada GRASP-Reactivo [12] donde su parámetro
se va
actualizando según se desarrollan las iteraciones del
algoritmo.
Los métodos golosos y el vecino más
cercano son dos variantes del método GRASP, que
realizan una elección que le implique los mejores
resultados inmediatos, sin tener en cuenta una perspectiva
más amplia. La heurística del vecino más
cercano, conocido como Nearest Neighbor, comienza
escogiendo un nodo inicial aleatoriamente e iterativamente
busca su nodo más cerca, o si existen varios,
construye una lista y escoge uno de ellos aleatoriamente. El
método goloso ó Greedy, busca
iterativamente los dos nodos más próximos y
escoger uno aleatoriamente [7].
Estos métodos aceptan algunas mejoras como
aplicar una búsqueda local al final de cada
iteración o al finalizar todas las iteraciones,
así se obtiene una solución con mejor
calidad.
2.1.1.1 Remiendo por cubrimiento de
ciclos
El método de remiendo por cubrimiento de
ciclos construye las soluciones a partir de ciclos realizados
por las asignaciones obtenidas [7]. Por tanto el primer paso
para realizar este método es convertir el PVA en un
problema de asignación.
El Problema de Asignación (PA) [34] es un
problema clásico de optimización combinatorial,
en el cual se encuentra un vasto número de problemas
de diseño y de distribución de recursos
en diferentes campos, donde la decisión a tomar es una
asignación de elementos de un conjunto en otro. Para
aplicar el PA al PVA se utiliza un grafo bipartito, donde la
cantidad de nodos es 2n, siendo n el
número de ciudades y la distancia un valor
arbitrariamente grande.
Existen varios métodos para la
solución del PA. Uno de ellos, muy popular, es el
método Húngaro, con sus variantes. Los pasos de
este están descrito por [32], y por muchas otras
referencias, pero no solucionan (no convergen) algunas
instancias que presentan soluciones múltiples, y se
necesitan otros pasos adicionales, no aclarados. Existen
otros artículos que describen este método
basado en el problema dual [32], con una complejidad
, pero es
engorroso y presenta detalles incompletos para su
implementación.
Otro método es por subasta, conocido como
Auction [31], donde su función objetiva es
maximizar, y consiste en realizar una subasta donde hay
n carros a subastar a n personas, con la
condición de que cada persona se
lleven un carro. Este método utiliza técnica de
escalamiento siendo muy eficiente y fácil de
implementar.
2.1.2 Cotas inferiores
Para evaluar la calidad de una solución
obtenida, en ausencia de la solución óptima, es
importante contar con métodos que proporcionen cuotas
inferiores a la solución del problema siendo el AP uno
de los métodos más difundido. El método
desarrollado por Held – Karp (HK) [17 y 18] ofrece
mejores cotas inferiores más cercanas al óptimo
real .
2.1.3 Búsquedas locales
Los métodos de búsquedas locales
mejoran una solución obtenida comparándolas con
soluciones vecinas a ella. En un proceso
iterativo se van obteniendo nuevas soluciones vecinas, de
mejor calidad, mientras sea posible. Una búsqueda
local es la que basa su estrategia en el estudio de
soluciones del vecindario o entorno de la solución
actual, en general ofrecen óptimos locales.
Muchos métodos metaheurísticos
utilizan búsquedas locales como son GRASP, Recocido
Simulado, Búsqueda Tabú, y Búsqueda en
Vecindades Variables.
El término local se emplea con bastante frecuencia en
los estudios teóricos y prácticos del campo de
las metaheurísticas de búsqueda. Las
estructuras de entorno suelen reflejar algún concepto de
proximidad o vecindad entre las soluciones alternativas del
problema. Por tanto, una búsqueda local es un proceso
que, dada la solución actual en la que se encuentra el
recorrido, selecciona iterativamente una solución de
su entorno.
Las búsquedas locales requieren tener en
cuenta diversos aspectos como son: estructuras de vecindad
utilizada, criterio para recorrer el espacio de
solución (para encontrar su óptimo local con la
primera mejora o con la mejora profunda, etc.) y la forma en
que se recorre las soluciones vecinas.
Existen excelentes heurísticas de
búsquedas para el PVA, como las variantes realizadas
de Kanellakis-Papadimitriou [20], como 3-Opt [7, 11, 15, 19,
20 y 23], 4-Opt[15 y 17] cuya complejidad es
O(n4) y [15] propone un algoritmo de tipo
O(n2), etc.
1. Los métodos
  hiperheurísticos
Las metaheurísticas son estrategias
inteligentes para diseñar o mejorar procedimientos heurísticos muy
generales con un alto rendimiento. Entre las más
populares y bien estudiadas técnicas se encuentran
GRASP [12], Recocido Simulado [10], Búsquedas
Tabú [22], y los Algoritmos Genéticos [16]. Las
cuales se han aplicado con éxito en la solución de un gran
número de problemas reales.
Sin embargo, muchos de estos enfoques carecen de la
robustez para resolver una amplia gama de problemas. Las
metaheurísticas pueden resolver eficientemente un
problema real luego de realizar un diseño de
experimento profundo para ajustar sus parámetros, pero
no pudiera resolver en lo absoluto, o da soluciones muy
pobres, a otros casos inclusos derivados de los mismos
problemas [9]. El ajuste de parámetro de una misma
metaheurística en la solución de varios
problemas puede llevar tiempo mucho tiempo.
En los últimos años los investigadores
de esta temática han propuesto una nueva
técnica llamada hiperheurística [9 y 10]. La
hiperheurística es un algoritmo de clase abstracta que
opera a un nivel mas alto que las metaheurísticas, y
dirige a un grupo de
heurísticas simples (de un nivel más bajo) las
cuales son aplicadas, dependiendo de la característica
del espacio de soluciones donde se encuentra explorando
[9].
Una hiperheurística selecciona a cada paso la
más prometedora heurística simple (o una
combinación de heurísticas) que puede mejorar
potencialmente la solución. Por otro lado, si no hay
mejora, es decir, fue encontrada una solución
óptima local, ella es capaz de diversificar la
búsqueda a otras áreas del espacio de
solución realizando una apropiada selección de un nuevo juego de
heurísticas. Las heurísticas de bajo nivel,
normalmente representan a los métodos de
búsquedas locales o a las técnicas
constructivas [9].
Todo el dominio de información se concentra en el conjunto
de heurísticas simple y en la función objetivo.
La selección de una nueva heurística
está basada por distintos criterios: los valores
retornados de la función objetivo, por el tiempo de
ejecución de la CPU, etc.,
siendo necesario para estos casos una perturbación de
la solución [10].
Los enfoques hiperheurísticos con respecto a
las metaheurísticas tienen las siguientes ventajas
principales. Primeramente, una hiperheurística es
sencilla y rápida de implementar; al mismo tiempo
puede producir soluciones comparables en calidad a otras ya
encontradas por eficientes metaheurísticas. Segunda,
ella no tiene el acceso al conocimiento del dominio específico del
problema, haciéndola aplicable en pequeños
estudios o a problemas reales pobremente
estudiados.
Finalmente, estas técnicas son robustas:
pueden ser eficazmente aplicadas a una amplia gama de
instancias de un problema.
Revisión
bibliográfica
Solución del
problema

3.1 Las estructuras de datos

En los problemas de optimización combinatorial,
además de la calidad en las soluciones dadas por los
métodos implementados, el aspecto más importante a
tener en cuenta es su tiempo de ejecución. Esto se puede
lograr realizando un eficiente diseño en las Estructuras
de Datos (ED) que
serán implementadas para los algoritmos [1, 2, 8, 13, 24 y
32].

Para realizar un diseño eficiente de algoritmos,
el principal aspecto que un programador debe conocer y tener en
cuenta son las ED que va a utilizar, así logrará
que su aplicación sea mucho más eficiente, en otras
palabras, que brinde sus soluciones en el menor tiempo posible.
Es importante tener en cuenta que en los tiempos de
ejecución de un algoritmo deben incluirse los tiempos de
procesamiento de
datos, de acceso a datos, etc., y las ED juegan en ello un
papel fundamental.

Para la solución del PVA existen varias ED
diseñadas, la principal es una lista enlazada de punteros,
en esta podemos guardar la solución obtenida,
además de utilizar una de tipo grafo, donde son guardados
los datos del problema.

3.2 Heurísticas constructivas

Como se describió en el epígrafe anterior
para construir las soluciones para el PVA se seleccionaron cinco
algoritmos: GRASP, aleatorio, el vecino más cercano, un
goloso y la técnica de remiendos.

En esta sección se analizará el
método de remiendos de ciclos. Este método se puede
desarrollar de varias formas: realizando cubrimiento de ciclos de
mayor a menor, de menor a mayor o de forma aleatoria, el
cubrimiento de estos ciclos se explica a
continuación.

3.2.1 Remiendo de ciclos

Para realizar esta técnica es necesario hallar
los ciclos que son formados de las asignaciones hechas por el
método Auction para el PA. Después de tener
las asignaciones el siguiente paso es construir una secuencia
LC:

LC =
C1, C2, … ,
Cm-1, Cm

siendo m la cantidad total de ciclos en la
aplicación PA, Ck representa un ciclo
ó una subruta del PVA:

Ck = ck,0, ck,1,
… , ck,r-1, ck,r, ck,0

Como resultado del empate o remiendo de un par de ciclo
Ck, Ck+1 se forma un nuevo
ciclo C’k buscando la mínima
distancia {d(ck+1,j ,
ck,i+1)+d(ck,i , ck+1,j+1)}, para
realizar un punto de ruptura (Figura 2.1), siendo (1 ≤
i < r) y (1 ≤ j < p), donde
| Ck | = r y | Ck+1| = p, quedando
C’k de la siguiente forma (Figura 2.2):

C’k = ck+1,0,
ck+1,1, … , ck+1,j, ck,i+1, …
, ck,r, ck,1, ck,2, … , ck,i,
ck+1,j+1, …, ck+1,p,
ck+1,0

Figura 2.1 Puntos de rupturas de los
ciclos Ck, Ck+1

Figura 2.2 Remiendo de
ciclos

Los métodos de tipo Patche utilizados
tienen en cuenta una única forma de unir ciclos, la
explicada anteriormente. El orden en el que se toman los ciclos
no es predefinido, lo define la propia
hiperheurística.

En este trabajo se propone una modificación a
estas técnicas realizando búsquedas locales a las
soluciones obtenidas que permitan mejorar la calidad de las
mismas. Para esto es necesario realizar un análisis de
posibles métodos de búsqueda local para el PVA y
seleccionar los mejores.

3.3 Heurísticas de
búsquedas

En este trabajo se proponen cinco métodos de
búsquedas locales para el PVA, dos de ellos (Mover
Nodo y Intercambiar Nodo) no se encuentra
reflejado por ningún autor en la literatura, aunque son
variantes realizadas a 3-Opt y 4-Opt
respectivamente los otras son (2-Opt, 3-Opt y
4-Opt), las cuales son utilizado con frecuencia en los
trabajos del PVA [4 y 7].

Las búsquedas locales se pueden realizar de
diversas maneras, las más utilizadas son la primera mejora
(tomar como punto de partida la primera solución que
mejore la solución actual) y la mejora profunda (recorrer
toda la vecindad de la solución actual y tomar la mejor
solución vecina), aunque esta última es muy
rechazada por el costo computacional que genera [32]. En este
trabajo se utilizará la búsqueda de la primera
mejora para cada método de búsqueda. La
razón para ello es que, según un pequeño
diseño de experimento realizado, las estructuras de
vecindad propuestas son fuertes, en el sentido de que partiendo
de diversas soluciones iniciales se obtienen soluciones de
calidad semejante con la primera mejora o con la mejora profunda,
consumiendo este último mucho más tiempo de
ejecución.

3.3.1 Operador Mover nodo

En las literaturas estudiadas este movimiento de
búsqueda no fue descrito por ningún autor aunque es
una variante que se dijo del operador 3-Opt, la
búsqueda de Mover Nodo es la siguiente:

Sea la ruta S0 formada por la siguiente
estructura:

S0 = a0, a1,
… , ai-1, ai, ai+1, ai+2,
… , aj-1, aj, aj+1, … ,
an-2, an-1, an, a0

donde i y j son las dos posiciones a
utilizar para realizar el movimiento, este método se basa
en desplazar el nodo situado en la posición i a la
posición j, como se muestra en la
Figura 2.3a. Existen dos posibles variantes para el movimiento
del nodo ai, para obtener la nueva solución vecina
S1:

Si (i < j), el nodo ai se
coloca entre el nodo aj y aj+1, lo que
resulta:
S1 = a0, a1,
… , ai-1, ai+1, ai+2, … ,
aj-1, aj, ai, aj+1, … ,
an-1, an, a0
Si (i > j), el nodo ai se
coloca entre el nodo aj-1 y aj, por
tanto:

S1 = a0, a1,
… , aj-1, ai, aj, aj+1,
… , ai-1, ai+1, ai+2, … ,
an-1, an, a0

como se muestra en la Figura 2.3b y 2.3c
respectivamente.

2.3a 2.3b 2.3c

Fig. 2.3 Operador Mover
Nodo

Una búsqueda mejorada de éste para
disminuir tiempo de ejecución del algoritmo consiste en
que para cada iteración de búsqueda con una nueva
solución de mejor calidad que la anterior, en
función de los nodos i,j, existen soluciones
vecinas comunes a las vecindades de la solución actual y
anterior que no se tienen en cuenta porque ya fueron exploradas.
Este método es O(n2). La evaluación
del costo de cada nueva solución posible es parcial y muy
rápida, pues para un recorrido de n aristas, solo
es necesario evaluar los costos de 3 de ellas.

3.3.2 Operador intercambiar nodo

Este operador es una modificación del operador
4-Opt y consiste solo en intercambiar dos nodos, a
diferencias del operador inicial que intercambia dos subrutas.
Este operador tiene la siguiente estructura:

Sea la ruta S0 formada como
sigue:

S0 = a0, a1,
… , ai-1, ai, ai+1, ai+2,
… , aj-1, aj, aj+1, … ,
an-1, an, a0

donde i y j son las posiciones
seleccionadas para realizar el movimiento (Figura 2.4a). Se
realiza un intercambio entre el nodo ai y
aj, por tanto la nueva solución vecina
S1 resulta:

S1 = a0, a1,
… , ai-1, aj, ai+1, ai+2,
… , aj-1, ai, aj+1, … ,
an-1, an, a0

como se muestra en la Figura 2.4b.

2.4a 2.4b

Fig. 2.4 Operador Intercambiar
Nodo.

La mejora de este método es similar al de
Mover Nodo con O(n2) operaciones,
aunque utiliza menos tiempo computacional. Su movimiento es muy
simple, realiza un intercambio de dos variables. De la misma
manera la evaluación del costo de cada nueva
solución es parcial, pues para un recorrido de n
aristas, solo es necesario evaluar los costos de 4 de
ellas.

Partes: 1, 2

Página siguiente