Hispanopedia Wiki
Articulo de referencia

Búsqueda de vecindario variable

La búsqueda de vecindario variable (VNS), [ 1 ] propuesta por Mladenović y Hansen en 1997, [ 2 ] es un método metaheurístico para resolver un conjunto de problemas de optimizaci...

Hispanopedia WikiContenido en espanolLectura gratuita

La búsqueda de vecindario variable (VNS), [ 1 ] propuesta por Mladenović y Hansen en 1997, [ 2 ] es un método metaheurístico para resolver un conjunto de problemas de optimización combinatoria y global . Explora vecindarios distantes de la solución actual y se mueve desde allí a una nueva si y solo si se ha realizado una mejora. El método de búsqueda local se aplica repetidamente para pasar de soluciones en el vecindario a óptimos locales. VNS fue diseñado para aproximar soluciones de problemas de optimización discretos y continuos y, por lo tanto, está dirigido a resolver problemas de programación lineal , problemas de programación entera , problemas de programación entera mixta, problemas de programación no lineal , etc.

Introducción

VNS modifica sistemáticamente el entorno en dos fases: primero, un descenso para encontrar un óptimo local y, finalmente, una fase de perturbación para salir del valle correspondiente.

Las aplicaciones están aumentando rápidamente en número y abarcan muchos campos: teoría de la localización , análisis de clústeres , planificación , enrutamiento de vehículos , diseño de redes , dimensionamiento de lotes, inteligencia artificial , ingeniería, problemas de agrupación, biología, filogenia , fiabilidad , geometría, diseño de telecomunicaciones, etc.

Existen varios libros importantes para comprender VNS, como: Handbook of Metaheuristics , 2010, [ 3 ] Handbook of Metaheuristics, 2003 [ 4 ] y Search methodologies, 2005. [ 5 ] Trabajos anteriores que motivaron este enfoque se pueden encontrar en

  1. Davidon, WC [ 6 ]
  2. Fletcher, R., Powell, MJD [ 7 ]
  3. Mladenović, N. [ 8 ] y
  4. Brimberg, J., Mladenović, N. [ 9 ]

Estudios recientes sobre la metodología VNS, así como numerosas aplicaciones, se pueden encontrar en 4OR, 2008 [ 10 ] y Annals of OR, 2010.

Definición del problema

Defina un problema de optimización determinista con

donde S , X , x y f son el espacio de soluciones, el conjunto factible, una solución factible y una función objetivo de valor real , respectivamente. Si S es un conjunto finito pero grande, se define un problema de optimización combinatoria.S=Rnorte{\displaystyle {S=R^{n}}}Existe un modelo de optimización continua.

Una soluciónincógnita∗∈incógnita{\displaystyle {x^{*}\in X}}es óptimo si

El algoritmo exacto para el problema ( 1 ) consiste en encontrar una solución óptima x* , con la validación de su estructura óptima, o si es irrealizable, en el procedimiento se debe demostrar que no existe una solución alcanzable, es decir,incógnita=∅{\displaystyle X=\varnothing }o la solución no está acotada. El tiempo de CPU debe ser finito y corto. Para la optimización continua, es razonable permitir cierto grado de tolerancia, es decir, detenerse cuando una solución factibleincógnita∗{\displaystyle x^{*}}se ha encontrado tal que

Algunas heurísticas aceptan rápidamente una solución aproximada o una solución óptima, pero sin ninguna validación de su optimalidad. Algunas de ellas tienen un certificado incorrecto, es decir, la soluciónincógnitah{\displaystyle x_{h}}obtenido satisface

para algún ε , aunque rara vez es pequeño.

Las heurísticas se enfrentan al problema de los óptimos locales como resultado de evitar un tiempo de cálculo ilimitado. Un óptimo localincógnitaL{\displaystyle x_{L}}del problema es tal que

dóndenorte(incógnitaL){\displaystyle N(x_{L})} denota un vecindario deincógnitaL{\displaystyle x_{L}}

Descripción

Según (Mladenović, 1995), VNS es una metaheurística que realiza sistemáticamente el procedimiento de cambio de vecindario, tanto en el descenso a mínimos locales como en el escape de los valles que los contienen.

VNS se basa en las siguientes percepciones:

  1. Un mínimo local con respecto a la estructura de un vecindario no es necesariamente un mínimo local para la estructura de otro vecindario.
  2. Un mínimo global es un mínimo local con respecto a todas las posibles estructuras vecinas.
  3. En muchos problemas, los mínimos locales con respecto a uno o varios vecindarios están relativamente cerca unos de otros.

A diferencia de muchas otras metaheurísticas, los esquemas básicos de VNS y sus extensiones son sencillos y requieren pocos parámetros, o incluso ninguno. Por lo tanto, además de proporcionar soluciones muy buenas, a menudo de forma más simple que otros métodos, VNS permite comprender las razones de dicho rendimiento, lo que, a su vez, puede conducir a implementaciones más eficientes y sofisticadas.

Hay varios artículos donde se podría estudiar entre los mencionados recientemente, como (Hansen y Mladenović 1999, 2001a, 2003, 2005; Moreno-Pérez et al.; [ 11 ] )

Se realiza una heurística de búsqueda local eligiendo una solución inicial x y descubriendo una dirección de descenso desde x dentro de un vecindario .norte(incógnita){\displaystyle N(x)}⁠ , y procediendo al mínimo de ⁠F(incógnita){\displaystyle f(x)}dentro​​norte(incógnita){\displaystyle N(x)}en la misma dirección. Si no hay dirección de descenso, la heurística se detiene; de ​​lo contrario, se itera. Por lo general, se utiliza la dirección de descenso más alta, también relacionada con la mejor mejora. Este conjunto de reglas se resume en el §  Algoritmo 1 , donde asumimos que se da una solución inicial x . La salida consiste en un mínimo local, denotado por x ′ , y su valor. Observe que una estructura de vecindarionorte(incógnita){\displaystyle N(x)}⁠ se define para todo x ∈ x . En cada paso, el vecindario ⁠norte(incógnita){\displaystyle N(x)}Se explora completamente el vector x . Como esto puede llevar mucho tiempo, una alternativa es utilizar la heurística del primer descenso. Vectoresincógnitai∈norte(incógnita){\displaystyle x^{i}\in N(x)}Luego se enumeran sistemáticamente y se realiza un movimiento tan pronto como se encuentra una dirección para el descenso. Esto se resume en el §  Algoritmo 2 .

Algoritmo 1: Heurística de mejor mejora (descenso más alto)

Función MejorMejora ( x ) repetirx ′ ← xx ← argmin_ { f ( y ) }, y ∈ N ( x ) hasta que ( f ( x ) ≥ f ( x ′) ) devolver x ′

Algoritmo 2: Heurística de primera mejora (primer descenso)

Función FirstImprovement ( x ) repetirx ′ ← x ; i ← 0repetiri ← i + 1x ← argmin { f ( x ), f ( x ^ i )}, x ^ i ∈ N ( x ) hasta que ( f ( x ) < f ( x ^ i ) o i = | N ( x )| ) hasta que ( f ( x ) ≥ f ( x ′) ) devolver x ′

Sea uno denotemosnortek(k=1,...,kmáximo){\displaystyle {\mathcal {N}}_{k}(k=1,...,k_{\max })}, un conjunto finito de estructuras vecinales preseleccionadas, y connortek(incógnita){\displaystyle {\mathcal {N}}_{k}(x)}el conjunto de soluciones en el k-ésimo entorno de x .

También se utilizará la notaciónnorte′k(incógnita),k=1,...,kmáximo′{\displaystyle {\mathcal {N'}}_{k}(x),k=1,...,k'_{\max }}al describir la ascendencia local. Barriosnortek(incógnita){\displaystyle {\mathcal {N}}_{k}(x)}onorte′k(incógnita){\displaystyle {\mathcal {N'}}_{k}(x)}puede inducirse a partir de una o más funciones métricas (o cuasimétricas) introducidas en un espacio de soluciones S. Una solución óptimaincógnitaoptar{\displaystyle x_{\text{opt}}}(o mínimo global ) es una solución factible donde se alcanza un mínimo del problema. La llamamos ⁠incógnita′∈incógnita{\displaystyle x'\in X}un mínimo local del problema con respecto anortek(incógnita){\displaystyle {\mathcal {N}}_{k}(x)}si no hay soluciónincógnita∈norte′k(incógnita)⊆incógnita{\displaystyle x\in {\mathcal {N'}}_{k}(x)\subseteq X}de tal manera queF(incógnita)<F(incógnita′){\displaystyle f(x)<f(x')}.

Para resolver el problema utilizando varios vecindarios, los hechos 1 a 3 se pueden utilizar de tres maneras diferentes:

  1. determinista
  2. estocástico
  3. tanto deterministas como estocásticos.

Primero, en el §  Algoritmo 3, presentamos los pasos de la función de cambio de vecindario que se utilizará más adelante. La función NeighborhoodChange() compara el nuevo valor .F(incógnita′){\displaystyle f(x')}con el valor vigenteF(incógnita){\displaystyle f(x)}⁠ obtenido en el vecindario k ( línea 1 ). Si se obtiene una mejora, k vuelve a su valor inicial y se actualiza el nuevo titular ( línea 2 ). De lo contrario, se considera el siguiente vecindario ( línea 3 ).

Algoritmo 3: Cambio de vecindario

Función CambioDeVecindario ( x , x ′ , k )si f ( x ′ ) < f ( x ) entoncesx ← x ′ // Realizar un movimientok ← 1 // Vecindario inicialdemásk ← k + 1 // Siguiente vecindario

Cuando VNS no ofrece una buena solución, existen varios pasos que podrían ayudar en el proceso, como comparar las primeras y mejores estrategias de mejora en la búsqueda local, reducir el vecindario, intensificar la agitación, adoptar VND, adoptar FSS y experimentar con la configuración de parámetros.

El método VNS básico (BVNS) ( Manual de metaheurísticas , 2010) [ 3 ] combina cambios deterministas y estocásticos de vecindario. Sus pasos se dan en el §  Algoritmo 4. Vecindarios a menudo sucesivosnortek{\displaystyle {\mathcal {N}}_{k}}estará anidado. Observe que el punto x′ se genera aleatoriamente en el Paso 4 para evitar ciclos, que podrían ocurrir si se aplicara una regla determinista. En el Paso 5, se suele adoptar la búsqueda local de mejor mejora ( §  Algoritmo 1 ). Sin embargo, puede sustituirse por la primera mejora ( §  Algoritmo 2 ).

Algoritmo 4: VNS básico

Función VNS ( x , kmax , tmax )repetirk ← 1repetirx ′ ← Agitar ( x , k ) // Agitarx ″ ← MejorMejora ( x ′ ) // Búsqueda localx ← CambioDeVecindario ( x , x ″ , k ) // Cambiar vecindariohasta que k = kmaxt ← TiempoCpu ()hasta que t > tmax

Variantes del VNS

El método VNS básico es un método de descenso de mejor mejora con aleatorización. [ 3 ] Sin mucho esfuerzo adicional, se puede transformar en un método de descenso-ascenso: en la función NeighbourhoodChange(), también se reemplaza x por x″ con cierta probabilidad, incluso si la solución es peor que la actual. También se puede convertir en un método de primera mejora.

Otra variante del VNS básico puede consistir en encontrar una solución x′ en el paso de "Agitación" como la mejor entre b (un parámetro) soluciones generadas aleatoriamente del k -ésimo vecindario. Hay dos variantes posibles de esta extensión:

  1. realizar una única búsqueda local a partir del mejor de entre b puntos;
  2. realizar todas las búsquedas locales y luego elegir la mejor.

En el artículo (Fleszar y Hindi [ 12 ] ) se puede encontrar el algoritmo.

Extensiones

  • VND [ 13 ]
    El método de descenso de vecindario variable (VND) se obtiene cuando se realiza un cambio de vecindarios de forma determinista. En las descripciones de sus algoritmos, asumimos que se da una solución inicial x . La mayoría de las heurísticas de búsqueda local en su fase de descenso utilizan muy pocos vecindarios. La solución final debe ser un mínimo local con respecto a todoskmáximo{\displaystyle k_{\max }}vecindarios; por lo tanto, las posibilidades de alcanzar un alcance global son mayores al usar VND que con una estructura de vecindario único.
  • RVNS [ 14 ]
    El método VNS reducido (RVNS) se obtiene si se seleccionan puntos aleatorios denortek(incógnita){\displaystyle {\mathcal {N}}_{k}(x)}y no se realiza ningún descenso. En cambio, los valores de estos nuevos puntos se comparan con los del punto actual y se produce una actualización en caso de mejora. Se supone que se ha elegido una condición de parada, como el tiempo máximo de CPU permitido.tmáximo{\displaystyle t_{\max }}o el número máximo de iteraciones entre dos mejoras.
    Para simplificar la descripción de los algoritmos se utilizatmáximo{\displaystyle t_{\max }}abajo. Por lo tanto, RVNS utiliza dos parámetros:tmáximo{\displaystyle t_{\max }}ykmáximo{\displaystyle k_{\max }}RVNS es útil en instancias muy grandes, para las cuales la búsqueda local es costosa. Se ha observado que el mejor valor para el parámetrokmáximo{\displaystyle k_{\max }}Suele ser 2. Además, el número máximo de iteraciones entre dos mejoras se suele utilizar como condición de parada. RVNS es similar a un método de Montecarlo , pero es más sistemático.
  • VNS sesgado
    El método VNS sesgado (SVNS) (Hansen et al.) [ 15 ] aborda el problema de explorar valles alejados de la solución actual. De hecho, una vez encontrada la mejor solución en una región extensa, es necesario avanzar para obtener una mejor. Las soluciones extraídas al azar en vecindarios distantes pueden diferir sustancialmente de la solución actual, y VNS puede entonces degenerar, hasta cierto punto, en la heurística Multistart (en la que los descensos se realizan iterativamente a partir de soluciones generadas al azar, una heurística que se sabe que no es muy eficiente). En consecuencia, debe compensarse la distancia a la solución actual.
  • Búsqueda de descomposición de vecindario variable
    El método de búsqueda por descomposición de vecindario variable (VNDS) (Hansen et al.) [ 16 ] extiende el VNS básico a un esquema VNS de dos niveles basado en la descomposición del problema. Para facilitar la presentación, pero sin pérdida de generalidad, se supone que la solución x representa el conjunto de algunos elementos.
  • VNS paralelo
    Recientemente se han propuesto varias formas de paralelizar VNS para resolver el problema de la p-mediana. En García-López et al. [ 17 ] se prueban tres de ellas:
    1. paralelizar la búsqueda local
    2. aumentar el número de soluciones extraídas del vecindario actual y realizar una búsqueda local en paralelo desde cada una de ellas
    3. Haz lo mismo que en (ii), pero actualiza la información sobre la mejor solución encontrada.
    También se sugieren tres estrategias VNS paralelas para resolver el problema del comprador viajero en Ochi et al. [ 18 ].
  • VNS dual primario
    Para la mayoría de las heurísticas modernas, la diferencia de valor entre la solución óptima y la obtenida es completamente desconocida. El rendimiento garantizado de la heurística primal puede determinarse si se conoce una cota inferior para el valor de la función objetivo. Para ello, el enfoque estándar consiste en relajar la condición de integralidad de las variables primales, basándose en una formulación del problema mediante programación matemática.
Sin embargo, cuando la dimensión del problema es grande, incluso el problema relajado puede ser imposible de resolver con exactitud mediante solucionadores comerciales estándar. Por lo tanto, parece una buena idea resolver también heurísticamente problemas relajados duales. Se obtuvieron cotas garantizadas para el rendimiento de la heurística primal. En Primal-dual VNS (PD-VNS) (Hansen et al.) [ 19 ] se propone una posible forma general de alcanzar tanto las cotas garantizadas como la solución exacta.
  • Ramificación de vecindario variable [ 20 ]
    El problema de programación lineal entera mixta (MILP, por sus siglas en inglés) consiste en maximizar o minimizar una función lineal, sujeta a restricciones de igualdad o desigualdad y a restricciones de integralidad en algunas de las variables.
  • Búsqueda en el espacio de formulación de vecindario variable [ 21 ]
    FSS es un método muy útil porque un problema puede definirse en formulaciones adicionales y moverse a través de ellas es legítimo. Se ha demostrado que la búsqueda local funciona dentro de las formulaciones, lo que implica una solución final cuando se parte de una solución inicial en la primera formulación. La búsqueda local alterna sistemáticamente entre diferentes formulaciones, lo cual se investigó para el problema de empaquetamiento de círculos (CPP), donde el punto estacionario para una formulación de programación no lineal de CPP en coordenadas cartesianas no es estrictamente un punto estacionario en coordenadas polares .

Aplicaciones

Las aplicaciones de VNS, o de sus variantes, son muy abundantes y numerosas. Algunos campos donde se pueden encontrar colecciones de artículos científicos son:

Conclusión

VNS implica varias características que son presentadas por Hansen y Mladenović [ 22 ] y algunas se presentan aquí:

  1. Sencillez: VNS es simple, claro y de aplicación universal.
  2. Precisión: VNS se formula en definiciones matemáticas precisas.
  3. Coherencia: todas las acciones de las heurísticas para resolver problemas se derivan de los principios VNS.
  4. Eficacia: VNS proporciona soluciones óptimas o casi óptimas para todos o al menos la mayoría de los casos realistas.
  5. Eficiencia: VNS requiere un tiempo de cálculo moderado para generar soluciones óptimas o casi óptimas.
  6. Robustez: el funcionamiento del VNS es coherente en una variedad de situaciones.
  7. Facilidad de uso: VNS no tiene parámetros, por lo que es fácil de entender, expresar y usar.
  8. Innovación: VNS está generando nuevos tipos de aplicaciones.
  9. Generalidad: VNS está induciendo buenos resultados para una amplia variedad de problemas.
  10. Interactividad: VNS permite al usuario incorporar sus conocimientos para mejorar el proceso de resolución.
  11. Multiplicidad: VNS es capaz de producir ciertas soluciones casi óptimas entre las que el usuario puede elegir;

El interés en VNS está creciendo rápidamente, como lo demuestra el creciente número de artículos publicados cada año sobre este tema (hace 10 años, solo unos pocos; hace 5 años, alrededor de una docena; y cerca de 50 en 2007). Además, la 18.ª miniconferencia EURO celebrada en Tenerife en noviembre de 2005 estuvo dedicada íntegramente a VNS. Esto dio lugar a números especiales de IMA Journal of Management Mathematics en 2007, European Journal of Operational Research ( http://www.journals.elsevier.com/european-journal-of-operational-research/ ) y Journal of Heuristics ( https://www.springer.com/mathematics/applications/journal/10732/ ) en 2008.

Referencias

  1. ↑ Hansen, P.; Mladenović, N.; Perez, JAM (2010). "Búsqueda de vecindario variable: métodos y aplicaciones". Annals of Operations Research . 175 : 367–407 . doi : 10.1007/s10479-009-0657-6 . S2CID 26469746 . 
  2. ↑ Nenad Mladenović; Pierre Hansen (1997). "Búsqueda de vecindario variable". Computers and Operations Research . 24 (11): 1097– 1100. CiteSeerX 10.1.1.800.1797 . doi : 10.1016/s0305-0548(97)00031-2 . 
  3. 1 2 3 Gendreau, M.; Potvin, JY. (2010). "Manual de metaheurísticas". Springer.
  4. ↑ Glover, F.; Kochenberger, GA (2003). "Manual de metaheurísticas". Kluwer Academic Publishers.
  5. ↑ Burke, EK.; Kendall, G. (2005). Burke, Edmund K; Kendall, Graham (eds.). Metodologías de búsqueda. Tutoriales introductorios en técnicas de optimización y apoyo a la decisión . Springer. doi : 10.1007/978-1-4614-6940-7 . ISBN 978-1-4614-6939-1.
  6. ↑ Davidon, WC (1959). "Algoritmo de métrica variable para minimización". Informe del Laboratorio Nacional Argonne ANL-5990 .
  7. ↑ Fletcher, R.; Powell, MJD (1963). "Método de descenso de rápida convergencia para minimización" . Comput. J. 6 ( 2): 163– 168. doi : 10.1093/comjnl/6.2.163 .
  8. ↑ Mladenović, N. (1995). "Un algoritmo de vecindario variable: una nueva metaheurística para la optimización combinatoria". Resúmenes de ponencias presentadas en las Jornadas de Optimización, Montreal : 112.
  9. ↑ Brimberg, J.; Mladenović, N. (1996). "Un algoritmo de vecindario variable para resolver el problema continuo de localización-asignación". Stud. Locat. Anal . 10 : 1–12 .
  10. ↑ Hansen, P.; Mladenović, N.; Perez, JAM (2008). "Búsqueda de vecindario variable: métodos y aplicaciones". 4OR . 6 (4): 319– 360. doi : 10.1007/s10288-008-0089-1 . S2CID 538959 . 
  11. ↑ Moreno-Pérez, JA.; Hansen, P.; Mladenović, N. (2005). "Búsqueda de vecindad de variables paralelas". En Alba, E (ed.). Metaheurísticas paralelas: una nueva clase de algoritmos . págs. 247–266 . CiteSeerX 10.1.1.615.2796 . doi : 10.1002/0471739383.ch11 . ISBN   9780471739388.
  12. ↑ Fleszar, K; Hindi, KS (2004). "Resolución del problema de programación de proyectos con restricciones de recursos mediante una búsqueda de vecindario variable". Eur J Oper Res . 155 (2): 402– 413. doi : 10.1016/s0377-2217(02)00884-6 .
  13. ↑ Brimberg, J.; Hansen, P.; Mladenović, N.; Taillard, E. (2000). "Mejoras y comparación de heurísticas para resolver el problema de Weber de múltiples fuentes" . Oper. Res . 48 (3): 444– 460. doi : 10.1287/opre.48.3.444.12431 .
  14. ↑ Mladenović, N.; Petrovic, J.; Kovacevic-Vujcic, V.; Cangalovic, M. (2003b). "Resolución del problema de diseño de código polifásico de radar de espectro ensanchado mediante búsqueda tabú y búsqueda de vecindario variable". Eur. J. Oper. Res . 151 (2): 389– 399. doi : 10.1016/s0377-2217(02)00833-0 .
  15. ^ Hansen, P.; Jaumard, B ; Mladenović, N; Parreira, A (2000). "Búsqueda de barrio variable para el problema de máxima satisfacibilidad ponderada". Les Cahiers du GERAD G–2000–62, HEC Montréal, Canadá .
  16. ↑ Hansen, P; Mladenović, N; Pérez-Brito, D (2001). "Búsqueda de descomposición de vecindario variable". J Heuristics . 7 (4): 335– 350. doi : 10.1023/A:1011336210885 . S2CID 31111583 . 
  17. ↑ García-López, F; Melián Batista, B; Moreno-Pérez, JA (2002). "La búsqueda de vecindad de variables paralelas para el problema de la mediana p". J Heurística . 8 (3): 375– 388. doi : 10.1023/A:1015013919497 . S2CID 16096161 . 
  18. ↑ Ochi, LS; Silva, MB; Drummond, L (2001). "Metaheurísticas basadas en GRASP y VNS para resolver el problema del comprador viajero" . MIC'2001, Porto : 489–494 .
  19. ↑ Hansen, P; Brimberg, J; Uroševi´c, D; Mladenović, N (2007a). "Búsqueda de vecindario variable primal-dual para el problema simple de localización de plantas" . INFORMS J Comput . 19 (4): 552– 564. doi : 10.1287/ijoc.1060.0196 .
  20. ↑ Hansen, P.; Mladenović, N.; Urosevic, D. (2006). "Búsqueda de vecindario variable y ramificación local". Computers and Operations Research . 33 (10): 3034– 3045. CiteSeerX 10.1.1.108.987 . doi : 10.1016/j.cor.2005.02.033 . 
  21. ↑ Mladenović, N.; Plastria, F. ; Urosevic, D. (2006). "Reformulación de descenso aplicada a problemas de empaquetamiento de círculos". Computers and Operations Research . 32 (9): 2419– 2434. doi : 10.1016/j.cor.2004.03.010 .
  22. ↑ Hansen, P; Mladenović, N (2003). "Búsqueda de vecindario variable". En Glover F; Kochenberger G (eds.). Manual de metaheurísticas . Serie internacional en investigación operativa y ciencias de la gestión. Vol. 57. Dordrecht: Kluwer. pp. 145–184 . CiteSeerX 10.1.1.635.7056 . doi : 10.1007/0-306-48056-5_6 . ISBN    978-1-4020-7263-5.
  • EURO Mini Conferencia XXVIII sobre Búsqueda de Vecindario Variable
  • La 5ª Conferencia Internacional sobre Búsqueda de Vecindarios Variables
  • La 8ª Conferencia Internacional sobre Búsqueda de Vecindarios Variables