optimización heurística: búsqueda de vecindad variable

Optimización heurística: Búsqueda de Vecindad Variable

ABRAHAM DUARTE

1

www.grafo.etsii.urjc.es

Optimización

o En lenguaje coloquial, optimizar significa mejorar

o En el contexto científico, es el proceso de tratar de encontrar la mejor solución posible para un problema determinado

Problema de optimización

o El objetivo de un problema de optimización es encontrar la solución óptima dado un criterio para discriminarentre dos soluciones

o Encontrar el valor de unas variables de decisión (sujetas a restricciones) para los que una determinada función objetivo alcanza su valor máximo o mínimo

Optimización

o Representación: codifica las soluciones factibles para su representación. Determina el tamaño del espacio de búsqueda del problema

o Objetivo: modelo matemático que expresa la tarea a realizar

o Función de evaluación: asocia a cada solución factible un valor que determina su calidad.

Optimización

o Dado un dominio 𝑋 y una función

el objetivo es encontrar un 𝑥 que verifique

o Optimización combinatoria: consiste en encontrar un objeto en un conjunto finito de soluciones

𝑓 𝑋 : 𝑥 ∈ 𝑋 → 𝑅

𝑥⋆ ∈ 𝑋: 𝑓 𝑥⋆ ≥ 𝑓 𝑥 , ∀𝑥 ∈ 𝑋

Tipos de problemas combinatorios

o Según la representación de la solución• Permutaciones: problemas de ordenación• Binarios: problemas de pertenencia• Enteros: problemas de cardinalidad• Otros (mixtos, subgrafos, árboles, etc.)

1221334443311222144321112234

Tipos de problemas

o Fáciles de resolver• Lineales: función objetivo y restricciones

lineales (método Simplex)

o Difíciles de resolver (𝑁𝑃-difícil)• No podemos garantizar encontrar la mejor

solución en un tiempo razonable• La mayoría de problemas de aplicación práctica• Desarrollamos procedimientos eficientes para

encontrar soluciones de calidad

Tipos de problemas

Tipos de problemas

𝑁𝑃-completo

𝑁𝑃-difícil

𝑃

𝑁𝑃 𝑃 = 𝑁𝑃 =𝑁𝑃-completo

𝑁𝑃-difícil

𝑃 ≠ 𝑁𝑃 𝑃 = 𝑁𝑃

Tipos de problemas

Ejemplos de problemas

o Viajanteo Mochilao Coloreado de grafoso Partición de conjuntoso Ordenación linealo Diversidado Enrutado de vehículoso …

Problema del viajante

o Travelling Salesman Problem, TSP. Un comerciante tiene que visitar n ciudades, comenzando y finalizando en su propia ciudad. Conociendo el coste de ir de una ciudad a otra, encontrar el recorrido de coste mínimo.

10

1

8

1 16 13

Problema del viajante

o Número de soluciones en el TSP• 10 ciudades. 105 (aprox.)• 20 ciudades. 1012 (aprox.)• 50 ciudades. 1062 (aprox.)o Enumeración exhaustiva§ Edad del universo 15000 millones de años (1018 sec)§ Súper-computador: 100 petaflops (1017Inst/sec)

0.000000000000000000000000001% de soluciones evaluadas

Problema del viajante

Tipos de óptimos

o Óptimo global: se trata de la mejor solución que se puede encontrar a un problema

o Óptimo local: es la mejor solución de un problema dentro de una vecindad determinada

o Un óptimo global es óptimo local de cualquier vecindad

Tipos de óptimos

Vecindado Dada una solución 𝑥, la vecindad 𝑁(𝑥) de esa

solución es un subconjunto del espacio de soluciones que contiene soluciones próximas a la original

o Cada solución de su vecindad 𝑥2 ∈ 𝑁(𝑥) puede obtenerse directamente desde 𝑥 mediante una operación llamada movimiento

Movimiento

Heurísticas y metaheurísticas

o Para la mayoría de los problemas con interés práctico, los algoritmos exactos no son una alternativa realista

• El tamaño del problema hace que éste sea ineficiente computacionalmente

• Ejemplo del viajante

Heurísticas y metaheurísticas

o Hay condiciones difíciles de modelar que exigen flexibilidad

o Se necesitan soluciones aproximadascomo parte de un procedimiento global que garantice el óptimo

• El heurístico proporciona una buena solución inicial y participa en el paso intermedio del procedimiento

Heurísticas y metaheurísticas

o Heurísticas: procedimientos simplesbasados en el sentido común que obtienen una buena solución a problemas difíciles de un modo sencillo y rápido

o Metaheurísticas: procedimiento iterativo maestro que guía y modifica las operaciones de una heurística subordinada para producir eficientementesoluciones de alta calidad

Exacto vs heurístico

Exactos Heurísticos/Metaheurísticos

Solución óptima Solución de calidad (óptimo no garantizado)

El tiempo invertido para obtener el óptimo de un problema difícil puede ser desproporcionado

El tiempo suele ser reducido

Útiles para problemas pequeños Útiles cuando el problema es grande y necesitamos generar soluciones en un corto espacio de tiempo

Heurísticos constructivos

o Estrategia voraz: Partiendo de una semilla, construyen iterativamente una solución

o En cada paso, se añade a la solución el elemento que produzca la mayor mejoraen la solución parcial

o Visión miope: eligen la mejor opción para la siguiente iteración sin importar lo que suceda en el futuro

Heurísticos constructivos

o Estrategia de descomposición: Se divide el problema en subproblemas más pequeños hasta que el tamaño del subproblema es trivial

o El algoritmo combina las soluciones en cada paso hasta obtener la solución al problema original

o Ejemplo: divide y vencerás

Heurísticos constructivos

o Estrategia de reducción: identifican características que contienen las soluciones buenas conocidas y se asume que la solución óptima también las tendrá

• Reducción drástica del espacio de búsqueda

o Manipulación del modelo: simplifican el modelo del problema original, se soluciona el modelo simplificado y se extrapola al problema original

Heurísticos constructivos

o Estrategia aleatorizada: dada una solución factible y una vecindad asociada, se seleccionan aleatoriamente soluciones dentro de la vecindad

o Su éxito depende de la selección de vecindades prometedoras

Heurísticos de búsqueda

o First improvement: examina la vecindad de una solución y selecciona el primer movimiento que produce una mejora

o Best improvement: examina todos los posibles movimientos en una vecindad, seleccionando el que produce la mayor mejora

Limitaciones de los heurísticos

o Dependen en gran medida del problema concreto para el que se han diseñado

o Las técnicas e ideas aplicadas a la resolución de un problema son específicasde éste

o Es difícil trasladar el aprendizaje a otros problemas

• Han de particularizarse para cada caso

Limitaciones de los heurísticos

Metaheurísticas

o Propósito: obtener mejores resultados que los obtenidos por los heurísticostradicionales

o El término fue introducido por Fred Gloveren 1986

o Los procedimientos se sitúan “por encima” de los heurísticos, guiando su comportamiento

Metaheurísticas

Técnicas de diseño de algoritmos* Divide y vencerás* Algoritmos voraces* Programación dinámica* Etc

Algoritmos específicos* Relajación del modelo* Algoritmos ad hoc* Etc

Inspiración* Psicología => Aprendizaje* Biología >* Termología Recocido* Etc

= Evolución=>

Estadística* Aleatorizac* Funciones de distribución* Estimimadores* Etc

ión

Metaheurística

Taxonomía

Ejemplos trayectoriales

o Búsqueda Tabu (Tabu Search – TS)o Búsqueda de Vecindad Variable (Variable

Neighborhood Search – VNS)o GRASP - Greedy Randomized Adaptive Serach

Procedureso Búsqueda local iterada (Iterated Local Search –

ILS)o Recocido Simulado (Simulated Annealing – SA)

Ejemplos poblacionales

o Búsqueda dispersa (Scatter Search – SS)o Reencadenamiento de trayectorias (Path

Relinking – PR)o Algoritmos evolutivos (genéticos – GA y

meméticos – MA)o Optimización por colonias de hormigas (Ant

Colony Optimization – ACO)o Inteligencia de enjambre (Swarm Intelligence –

SI)

Búsqueda de Vecindad Variable

o La búsqueda de vecindad variable (VNS –Variable Neighborhood Search) fue propuesta por P. Hansen y N. Mladenovic en 1997.

o Se basa en el principio del cambio sistemático de vecindad en la búsqueda.

• Al quedarse atrapada en un óptimo local, la búsqueda salta a otra zona del espacio de soluciones.

Búsqueda de Vecindad Variable

1. Un mínimo local en una estructura de vecindad no lo es necesariamente de otra.

2. Un mínimo global es mínimo local respecto a todas las estructuras de vecindad.

3. En general, los mínimos locales con la misma o diferente estructura de vecindad están cerca.

o La cercanía entre óptimos locales es una observación empírica.

• Implica que los óptimos locales aportan información sobre el global.

o Por ejemplo, puede que compartan características.

• Pero no se suele saber qué características comparten.

o Es necesario estudiar las proximidades del óptimo local para encontrar uno mejor.

Búsqueda de Vecindad Variable

o Basic VNS – BVNSo Reduced VNS – RVNSo Variable Neighborhood Descent – VNDo General VNS – GVNSo Variable Neighb. Decomposition Search – VNDSo Skewed VNS – SVNSo Parallel VNS – PVNS

Búsqueda de Vecindad Variable

o Combina pasos aleatorios y deterministas en la exploración de las estructuras de vecindad.

o En cada iteración, se selecciona una solución aleatoria dentro de la vecindad actual y se encuentra su óptimo local.

o Se aplican cambios mientras la solución no mejore.

• Cuando mejora se vuelve a la vecindad inicial.

Búsqueda de Vecindad Variable

𝜑

𝑓 𝜑

Búsqueda de Vecindad Variable

BVNS(𝑆, 𝑘678, 𝑡678)do

𝑘 ← 1do𝑆2 ← 𝑠ℎ𝑎𝑘𝑒 𝑆, 𝑘𝑆22 ← 𝑙𝑜𝑐𝑎𝑙𝑆𝑒𝑎𝑟𝑐ℎ 𝑆2k ← 𝑁𝑒𝑖𝑔ℎ𝑏𝑜𝑟ℎ𝑜𝑜𝑑𝐶ℎ𝑎𝑛𝑔𝑒 𝑆, 𝑆22, 𝑘

while 𝑘 ≤ 𝑘678𝑡 ← 𝐶𝑃𝑈𝑇𝑖𝑚𝑒

while 𝑡 ≤ 𝑡678

Basic VNSBúsqueda de Vecindad Variable

Shake(𝑆, 𝑘) Improve(𝑆’) Neighborhood Change(𝑆, 𝑆’’)

𝑆, 𝑘 ← 1 𝑆′ 𝑆′′

𝑘 ≤ 𝑘678

yes

no

𝑆, 𝑘

𝑆, 𝑘𝑆

Búsqueda de Vecindad Variable

Shakeo Aplica una perturbación aleatoria a la solución

para moverse a una solución dentro de la vecindad k-ésima.

Basic VNS

Búsqueda de Vecindad Variable

Neighborhood Changeo Decide la siguiente vecindad a utilizar.o Si se ha producido una mejora, se actualiza la

mejor solución hasta el momento y se vuelve a la primera vecindad.

o Si no, se pasa a la siguiente vecindad.

Basic VNS

Búsqueda de Vecindad Variable

o En algunas ocasiones la búsqueda local es un procedimiento pesado.

o Para reducir el tiempo de cómputo, RVNS elimina la búsqueda local del proceso.

o Realiza cambios aleatorios de pequeño tamaño en la vecindad actual.

ReducedVNS

Búsqueda de Vecindad VariableRVNS(𝑆, 𝑘678, 𝑡678)do

𝑘 ← 1do𝑆2 ← 𝑠ℎ𝑎𝑘𝑒 𝑆, 𝑘k ← 𝑁𝑒𝑖𝑔ℎ𝑏𝑜𝑟ℎ𝑜𝑜𝑑𝐶ℎ𝑎𝑛𝑔𝑒 𝑆, 𝑆2, 𝑘

while 𝑘 ≤ 𝑘678𝑡 ← 𝐶𝑃𝑈𝑇𝑖𝑚𝑒

while 𝑡 ≤ 𝑡678

ReducedVNS

Shake(𝑆, 𝑘) Improve(𝑆’) Neighborhood Change(𝑆, 𝑆’’)

𝑆, 𝑘 ← 1

𝑆′

𝑘 ≤ 𝑘678

yes

no

𝑆, 𝑘

𝑆′, 𝑘𝑆

Búsqueda de Vecindad Variable

o Utiliza diferentes estructuras de vecindad en el proceso de mejora.

o Los cambios de vecindad son deterministas.

Variable Neighborhood Descent

Búsqueda de Vecindad VariableVND(𝑆, 𝑘678)

𝑘 ← 1do𝑆2 ← 𝐵𝑒𝑠𝑡𝐼𝑛𝑁𝑒𝑖𝑔ℎ𝑏𝑜𝑟ℎ𝑜𝑜𝑑 𝑆, 𝑘𝑘 ← 𝑁𝑒𝑖𝑔ℎ𝑏𝑜𝑟ℎ𝑜𝑜𝑑𝐶ℎ𝑎𝑛𝑔𝑒 𝑆, 𝑆2, 𝑘

while 𝑘 ≤ 𝑘678

Variable Neighborhood Descent

Shake(𝑆, 𝑘) Improve(𝑆’) Neighborhood Change(𝑆, 𝑆’’)

𝑆, 𝑘 ← 1 𝑆′′

𝑘 ≤ 𝑘678

yes

no

𝑆, 𝑘

𝑆, 𝑘𝑆

Búsqueda de Vecindad Variable

o Se combinan las ideas anteriores:• Se mantiene el esquema de cambio aleatorio de BVNS• Se añade una búsqueda local más exhaustiva como en

VND.

General VNS

Búsqueda de Vecindad VariableGVNS(𝑆, 𝑘678, 𝑡678)do

𝑘 ← 1do𝑆2 ← 𝑠ℎ𝑎𝑘𝑒 𝑆, 𝑘𝑆22 ← 𝑉𝑁𝐷 𝑆2k ← 𝑁𝑒𝑖𝑔ℎ𝑏𝑜𝑟ℎ𝑜𝑜𝑑𝐶ℎ𝑎𝑛𝑔𝑒 𝑆, 𝑆22, 𝑘

while 𝑘 ≤ 𝑘678𝑡 ← 𝐶𝑃𝑈𝑇𝑖𝑚𝑒

while 𝑡 ≤ 𝑡678

General VNS

Shake(𝑆, 𝑘) Improve(𝑆’) Neighborhood Change(𝑆, 𝑆’’)

𝑆, 𝑘 ← 1

𝑆′

𝑘 ≤ 𝑘678

yes

no

𝑆, 𝑘

𝑆, 𝑘𝑆

VND(𝑆’)𝑆′′

Búsqueda de Vecindad Variable

Variable Neighborhood Decomposition Searcho Descompone el problema en subproblemas más

sencillosSkewed VNSo Permite la exploración de zonas con soluciones

infactibles.Hibridacioneso GRASP, Tabú Search, Scatter Search, etc.

Extensiones

Caso de uso. Vertex Separation

o Grafo genérico que se representa en una disposición lineal.

• Cada vértice 𝑣 de coloca en la posición 𝜑 𝑣

A

B

E F

G

C

D

Caso de uso. Vertex Separation

o Grafo genérico que se representa en una disposición lineal.

• Cada vértice 𝑣 de coloca en la posición 𝜑 𝑣

AB EFGCD

1 2 3 4 5 6 7

Caso de uso. Vertex Separation

𝑝 = 3

AB EFGCD

𝐿 𝜑, 𝑝 = 𝐵, 𝐶, 𝐷 𝑅 𝜑, 𝑝 = 𝐴, 𝐸, 𝐹, 𝐺

Caso de uso. Vertex Separationo 𝑆𝑒𝑝(𝜑, 𝑝) represents the separation value

at position 𝑝 of layout 𝜑.o Number of vertices in 𝐿(𝜑, 𝑝) with, at least,

one adjacent in 𝑅(𝜑, 𝑝).

𝑆𝑒𝑝 𝜑, 𝑝= 𝑢 ∈ 𝐿 𝜑, 𝑝 : ∃𝑣 ∈ 𝑅 𝜑, 𝑝 ∧ 𝑢, 𝑣 ∈ 𝐸

Caso de uso. Vertex Separation

AB EFGCD

1

𝑆𝑒𝑝 𝜑, 1 = 𝐷 = 1

Caso de uso. Vertex Separation

AB EFGCD

1 2

𝑆𝑒𝑝 𝜑, 2 = 𝐷, 𝐶 = 2

Caso de uso. Vertex Separation

AB EFGCD

1 2 3

𝑆𝑒𝑝 𝜑, 3 = 𝐷, 𝐶, 𝐵 = 3

Caso de uso. Vertex Separation

𝑆𝑒𝑝 𝜑, 4 = 𝐷, 𝐶, 𝐵, 𝐺 = 4

AB EFGCD

1 2 3 4

Caso de uso. Vertex Separation

𝑆𝑒𝑝 𝜑, 5 = 𝐷, 𝐶, 𝐵 = 3

AB EFGCD

1 2 3 4 3

Caso de uso. Vertex Separation

𝑆𝑒𝑝 𝜑, 6 = 𝐷, 𝐶, 𝐹 = 3

AB EFGCD

1 2 3 4 3 3

Caso de uso. Vertex Separation

o The 𝑽𝑺-value for layout 𝜑 is defined as the maximum of all the 𝑺𝒆𝒑-values among all positions.

𝑉𝑆 𝜑 = maxlmnop

𝑆𝑒𝑝 𝜑, 𝑝

o VSP is a minimization problem.𝜑⋆ = arg min

u∈v𝑉𝑆 𝜑

Caso de uso. Vertex Separation

4

AB EFGCD

1 2 3 3 3

Caso de uso. Vertex Separation

AB EFGCD

1 2 3 3 3

𝑉𝑆 𝜑 = 4

4

Caso de uso. Vertex Separation

o Finding separators for graphs.o Very Large Scale Integration.o Graph theory – maximum independent set.o Computer language compiler design.o Graph drawing.o Natural Language Processing.

Caso de uso. Vertex Separationo Exact algorithms for special graphs: trees,

unicyclic graphs, 𝒏-dimensional grids, co-graphs and permutational graphs.

o A polynomial-time algorithm for general graphs was proposed but its complexity makes it impractical.

o Approximation algorithms: 𝑶 𝐥𝐨𝐠𝟐 𝒏 for general graphs and 𝑶 𝐥𝐨𝐠𝒏 for planar graphs.

Caso de uso. Vertex Separationo Proposal: exact and heuristic perspectives.o Mathematical model: impractical for large

instances.o Metaheuristic algorithm: Variable

Neighborhood Search framework.

Shake(𝑆, 𝑘) Improve(𝑆’) Neighborhood Change(𝑆, 𝑆’’)

𝑆, 𝑘 ← 1 𝑆′ 𝑆′′

𝑘 ≤ 𝑘678

yes

no

𝑆, 𝑘

𝑆, 𝑘𝑆

Caso de uso. Vertex Separation

o Procedimiento constructivo

A

B

E F

G

C

D

F

B C E

G A D

𝐿l

𝐿}

𝐿~

Caso de uso. Vertex Separation

o Procedimiento constructivo

F

B C E

G A D

𝐿l

𝐿}

𝐿~

F B C E G A D

Caso de uso. Vertex Separation

Neighborhood structures –𝑵𝟏• Best improvement with insertion moves. Neighborhood structures –𝑵𝟐• Heuristic rule for identifying promising positions for a

given vertex.• Usually located between the first and second adjacent

vertices.

Caso de uso. Vertex Separation

Variantes del Shake

Selection Insertion Objective

Shake1 Random Random Diversification

Shake2 Greedy Greedy Intensification

Shake3 Random Greedy Compromise

Shake4 Greedy Random Compromise

Caso de uso. Vertex Separation

• A. Duarte, L. F. Escudero, R. Martí, N. Mladenovic, J. J. Pantrigo, and J. Sánchez-Oro, Variable neighborhood search for the Vertex Separation Problem, Computers & Operations Research, 39(12):3247-3255, 2012.• DOI: https://doi.org/10.1016/j.cor.2012.04.017 • IF (2012): 1.909• Ranking: 10/79 (Q1)

Caso de uso. Vertex Separationo J. Sáchez Oro, J.J. Pantrigo, and A. Duarte. Combining

intensification and diversification strategies in VNS. An application to the Vertex Separation problem.Computers & Operations Research, 52(B):209-219, 2014.

• DOI: https://doi.org/10.1016/j.cor.2013.11.008• IF (2015): 1.988• Ranking: 19/82 (Q1)