SLIDES - Tecnología Digital V Diseño de Algoritmos (15)

Vista previa del material en texto

BúSQUEDA LOCAL
Tecnología Digital V: Diseño de Algoritmos
Universidad Torcuato Di Tella
Introducción
Consideremos el problema de optimización
min
B∈(
5 (B)
donde
# ( es el conjunto (discreto) de soluciones factibles.
# 5 (B) : (→ ℝ es la función objetivo.
Motivación
# Para los algoritmos exactos, exploramos el espacio de soluciones de forma
exhaustiva.
# Si esto se vuelve prohitivo, otra alternativa es considerar una solución
inicial y aplicar una secuencia de mejoras, apuntando a encontrar al final
una solución de buena calidad (eventualmente, la óptima).
# Algunas preguntas: Cómo definimos esta secuencia? Convergencia?
Complejidad?
1
Búsqueda Local: definiciones básicas
Sea B ∈ ( para nuestro problema.
Vecindario
Todas las soluciones que se pueden obtener mediante modificaciones
simples de una solución B ∈ (. Notamos #(B) ⊆ ( a un vecindario de la
solución B ∈ (.
Movida
Actualización de la solución por otra (con mejor función objetivo).
Criterio de aceptación
Condición mediante la cual se acepta una movida. Ejemplos:
# Best improvement: B′ ∈ #(B) tal que
B′ = arg min
B∈#(B)
5 (B)
y 5 (B′) < 5 (B).
# First improvement: primer B′ ∈ #(B), 5 (B′) < 5 (B), que identifiquemos
durante la exploración de #(B).
2
Búsqueda Local
BusquedaLocal()
1. Construir una solución B∗ ∈ (
2. repetir
3. elegir B ∈ #(B∗) tal que 5 (B) < 5 (B∗) y actualizar B∗ = B
4. mientras exista B ∈ #(B∗) tal que 5 (B) < 5 (B∗)
Convergencia
Un algoritmo de búsqueda local
converge a un mínimo local B∗ respecto a
#(B), es decir, 5 (B∗) ≤ 5 (B) para todo
B ∈ #(B∗).
Observación
La convergencia a un óptimo global no
está garantizada.
3
Búsqueda Local
BusquedaLocal()
1. Construir una solución B∗ ∈ (
2. repetir
3. elegir B ∈ #(B∗) tal que 5 (B) < 5 (B∗) y actualizar B∗ = B
4. mientras exista B ∈ #(B∗) tal que 5 (B) < 5 (B∗)
Convergencia
Un algoritmo de búsqueda local
converge a un mínimo local B∗ respecto a
#(B), es decir, 5 (B∗) ≤ 5 (B) para todo
B ∈ #(B∗).
Observación
La convergencia a un óptimo global no
está garantizada.
3
Búsqueda Local
BusquedaLocal()
1. Construir una solución B∗ ∈ (
2. repetir
3. elegir B ∈ #(B∗) tal que 5 (B) < 5 (B∗) y actualizar B∗ = B
4. mientras exista B ∈ #(B∗) tal que 5 (B) < 5 (B∗)
Convergencia
Un algoritmo de búsqueda local
converge a un mínimo local B∗ respecto a
#(B), es decir, 5 (B∗) ≤ 5 (B) para todo
B ∈ #(B∗).
Observación
La convergencia a un óptimo global no
está garantizada.
3
Búsqueda Local
BusquedaLocal()
1. Construir una solución B∗ ∈ (
2. repetir
3. elegir B ∈ #(B∗) tal que 5 (B) < 5 (B∗) y actualizar B∗ = B
4. mientras exista B ∈ #(B∗) tal que 5 (B) < 5 (B∗)
Convergencia
Un algoritmo de búsqueda local
converge a un mínimo local B∗ respecto a
#(B), es decir, 5 (B∗) ≤ 5 (B) para todo
B ∈ #(B∗).
Observación
La convergencia a un óptimo global no
está garantizada.
3
Búsqueda Local
BusquedaLocal()
1. Construir una solución B∗ ∈ (
2. repetir
3. elegir B ∈ #(B∗) tal que 5 (B) < 5 (B∗) y actualizar B∗ = B
4. mientras exista B ∈ #(B∗) tal que 5 (B) < 5 (B∗)
Convergencia
Un algoritmo de búsqueda local
converge a un mínimo local B∗ respecto a
#(B), es decir, 5 (B∗) ≤ 5 (B) para todo
B ∈ #(B∗).
Observación
La convergencia a un óptimo global no
está garantizada.
3
Búsqueda Local
BusquedaLocal()
1. Construir una solución B∗ ∈ (
2. repetir
3. elegir B ∈ #(B∗) tal que 5 (B) < 5 (B∗) y actualizar B∗ = B
4. mientras exista B ∈ #(B∗) tal que 5 (B) < 5 (B∗)
Convergencia
Un algoritmo de búsqueda local
converge a un mínimo local B∗ respecto a
#(B), es decir, 5 (B∗) ≤ 5 (B) para todo
B ∈ #(B∗).
Observación
La convergencia a un óptimo global no
está garantizada.
3
Búsqueda Local
BusquedaLocal()
1. Construir una solución B∗ ∈ (
2. repetir
3. elegir B ∈ #(B∗) tal que 5 (B) < 5 (B∗) y actualizar B∗ = B
4. mientras exista B ∈ #(B∗) tal que 5 (B) < 5 (B∗)
En la práctica
Un algoritmo de búsqueda local requiere definir (al menos) los siguientes
elementos:
# Cómo se representa una solución factible?
# Cómo se construye la primera solución factible?
# Qué vecindario(s) considera el algoritmo?
# Qué criterio de aceptación se implementa en cada caso?
4
Ejemplo: relocate para TSP
Definición
Dado un tour factible B para el TSP, el operador relocate (o
también llamado node insertion), #
rel
, se define como:
# considerar un vértice 8 ∈ B, adyacente a los vértices ? y
@.
# Dado un arco (9 , :) ∈ B, 9 ≠ ? y : ≠ @, un vecino de B
está dado por:
◦ remover a 8 de su posición;
◦ agregar el arco (?, @);
◦ insertar 8 entre 9 y : definiendo los ejes (9 , 8) e (8 , :).
# Aplicar estos pasos para todo 8 y (9 , :) ∈ B.
Propiedades
# Mejora. Una solución B′ ∈ ( es una mejora de B si
2?@ + 2 98 + 28: < 2 9: + 2?8 + 28@ ,
que puede ser verificado en $(1).
# Complejidad. La complejidad computacional de explorar el vecindario completo
#
rel
(B) es $(=2).
5
Ejemplo: relocate para TSP
Definición
Dado un tour factible B para el TSP, el operador relocate (o
también llamado node insertion), #
rel
, se define como:
# considerar un vértice 8 ∈ B, adyacente a los vértices ? y
@.
# Dado un arco (9 , :) ∈ B, 9 ≠ ? y : ≠ @, un vecino de B
está dado por:
◦ remover a 8 de su posición;
◦ agregar el arco (?, @);
◦ insertar 8 entre 9 y : definiendo los ejes (9 , 8) e (8 , :).
# Aplicar estos pasos para todo 8 y (9 , :) ∈ B.
Propiedades
# Mejora. Una solución B′ ∈ ( es una mejora de B si
2?@ + 2 98 + 28: < 2 9: + 2?8 + 28@ ,
que puede ser verificado en $(1).
# Complejidad. La complejidad computacional de explorar el vecindario completo
#
rel
(B) es $(=2). 5
Ejemplo: swap para TSP
Definición
Dado un tour factible B para el TSP, el operador swap,
#swap, se define como:
# considerar dos vértices distintos 8, 9;
# intecambiar las posiciones de 8 y 9 en B;
# aplicar estos cambios para todo par de vértices 8 , 9.
Propiedades
# Mejora. B′ ∈ #swap es una mejora de B si
2? 9 + 2 9@ + 2;8 + 28: < 2?8 + 28@ + 2; 9 + 2 9: ,
que puede ser verificado en $(1).
# Complejidad. La complejidad computacional de explorar el vecindario #swap es
$(=2).
6
Ejemplo: swap para TSP
Definición
Dado un tour factible B para el TSP, el operador swap,
#swap, se define como:
# considerar dos vértices distintos 8, 9;
# intecambiar las posiciones de 8 y 9 en B;
# aplicar estos cambios para todo par de vértices 8 , 9.
Propiedades
# Mejora. B′ ∈ #swap es una mejora de B si
2? 9 + 2 9@ + 2;8 + 28: < 2?8 + 28@ + 2; 9 + 2 9: ,
que puede ser verificado en $(1).
# Complejidad. La complejidad computacional de explorar el vecindario #swap es
$(=2).
6
Ejemplo: 2-opt para TSP
Definición
Dado un tour factible B para el TSP, el operador 2opt, #2opt,
se define como:
# considerar dos ejes distintos (8 , 9), (:, ;) ∈ B;
# conectar 8 → :, 9 → ; y ajustar el tour;
# aplicar estos cambios para todo par de ejes (8 , 9),
(:, ;) ∈ B.
Propiedades
# Mejora. B′ ∈ #2opt es una mejora de B si
28: + 2:→9 + 2 9; < 28 9 + 2 9→: + 2:; ,
que puede ser verificado en $(1).
# Complejidad. La complejidad computacional de explorar el vecindario #2opt es
$(=2).
7
Ejemplo: 2-opt para TSP
Definición
Dado un tour factible B para el TSP, el operador 2opt, #2opt,
se define como:
# considerar dos ejes distintos (8 , 9), (:, ;) ∈ B;
# conectar 8 → :, 9 → ; y ajustar el tour;
# aplicar estos cambios para todo par de ejes (8 , 9),
(:, ;) ∈ B.
Propiedades
# Mejora. B′ ∈ #2opt es una mejora de B si
28: + 2:→9 + 2 9; < 28 9 + 2 9→: + 2:; ,
que puede ser verificado en $(1).
# Complejidad. La complejidad computacional de explorar el vecindario #2opt es
$(=2).
7
Ejemplo: 2-opt para ATSP
Definición
Dado un tour factible B para el ATSP, el operador 2opt,
#2opt, se define como:
# considerar dos ejes distintos (8 , 9), (:, ;) ∈ B;
# conectar 8 → :, 9 → ; y ajustar el tour;
# aplicar estos cambios para todo par de ejes (8 , 9),
(:, ;) ∈ B.
Propiedades
# Mejora. B′ ∈ #2opt es una mejora de B si
28: + 2:→9 + 2 9; < 28 9 + 2 9→: + 2:; ,
que puede ser verificado en ¿?.
# Complejidad.La complejidad computacional de explorar el vecindario #2opt es
¿?.
8
Ejemplo: 2-opt para ATSP
Definición
Dado un tour factible B para el ATSP, el operador 2opt,
#2opt, se define como:
# considerar dos ejes distintos (8 , 9), (:, ;) ∈ B;
# conectar 8 → :, 9 → ; y ajustar el tour;
# aplicar estos cambios para todo par de ejes (8 , 9),
(:, ;) ∈ B.
Propiedades
# Mejora. B′ ∈ #2opt es una mejora de B si
28: + 2:→9 + 2 9; < 28 9 + 2 9→: + 2:; ,
que puede ser verificado en ¿?.
# Complejidad. La complejidad computacional de explorar el vecindario #2opt es
¿?.
8
Ejemplo: 2-opt para ATSP
Definición
Dado un tour factible B para el ATSP, el operador 2opt,
#2opt, se define como:
# considerar dos ejes distintos (8 , 9), (:, ;) ∈ B;
# conectar 8 → :, 9 → ; y ajustar el tour;
# aplicar estos cambios para todo par de ejes (8 , 9),
(:, ;) ∈ B.
Propiedades
# Mejora. B′ ∈ #2opt es una mejora de B si
28: + 2:→9 + 2 9; < 28 9 + 2 9→: + 2:; ,
que puede ser verificado en $(=).
# Complejidad. La complejidad computacional de explorar el vecindario #2opt es
$(=3). ¿Podemos mejorarla?
9
Ejemplo: 2-opt para ATSP
Para reducir la complejidad de validar si un movimiento 2opt mejora la solución en el
ATSP, se pueden seguir dos caminos:
# asumir que el cálculo se hace en un determinado orden, e ir actualizando ciertos
valores convenientemente;
# incorporar estructuras de datos que mantienen información sobre
B = (0, E1 , . . . , E= , 0);
◦ B[8] = 20,E
1
,...E8 el costo parcial de la ruta 0→ E8 .
◦ A4E_B[8] = 20,E= ,E=−1 ,...,E8 el costo parcial del reverso de la ruta E8 ← 0.
◦ Si 9 aparece despupés de 8,
28→9 = B[9] − B[8]
2 9→8 = A4E_B[8] − A4E_B[9]
Propiedades
# Mejora. B′ ∈ #2opt es una mejora de B si
28: + 2:→9 + 2 9; < 28 9 + 2 9→: + 2:; ,
que puede ser verificado en $(1).
# Complejidad. La complejidad computacional de explorar el vecindario #2opt es
$(=2).
Qué debemos hacer luego de actualizar la solución en caso de mejora?
10
Ejemplo: relocate para GAP
Definición
Dada una solución factible para el GAP, el operador
relocate, #
rel
, se define como:
# considerar un cliente 9 ∈ B asignado al depósito 8;
# considerar un depósito : ≠ 8;
◦ remover 9 de su ubicación actual;
◦ insertar 9 en el depósito :;
# Aplicar estos pasos para todos los clientes 9 ∈ B y los
depósitos distintos al actual.
Propiedades
# Mejora. Una solución B′ ∈ #
rel
(B) es una mejora de B si
2: 9 < 28 9 y 3: 9 ≤ 2̄: ,
con 2̄: la capacidad remanente del depósito :, que puede ser verificado en $(1).
# Complejidad. La complejidad computacional de explorar el vecindario completo
#
rel
(B) es $(= × <).
11
Ejemplo: relocate para GAP
Definición
Dada una solución factible para el GAP, el operador
relocate, #
rel
, se define como:
# considerar un cliente 9 ∈ B asignado al depósito 8;
# considerar un depósito : ≠ 8;
◦ remover 9 de su ubicación actual;
◦ insertar 9 en el depósito :;
# Aplicar estos pasos para todos los clientes 9 ∈ B y los
depósitos distintos al actual.
Propiedades
# Mejora. Una solución B′ ∈ #
rel
(B) es una mejora de B si
2: 9 < 28 9 y 3: 9 ≤ 2̄: ,
con 2̄: la capacidad remanente del depósito :, que puede ser verificado en $(1).
# Complejidad. La complejidad computacional de explorar el vecindario completo
#
rel
(B) es $(= × <).
11
Ejemplo: swap para GAP
Definición
Dada una solución factible para el GAP, el operador swap,
#swap, se define como:
# considerar dos clientes distintos 91 , 92 ∈ B asignado a los
depósitos 81 ≠ 82, respectivamente;
◦ remover 91 de 81 e insertarlo en 82;
◦ remover 92 de 82 e insertarlo en 81;
# Aplicar estos pasos para todos los clientes 91 , 92 ∈ B
asignados a depósitos distintos.
Propiedades
# Mejora. Una solución B′ ∈ #swap(B) es una mejora de B si
28
2
9
1
+ 28
1
9
2
< 28
1
9
1
+ 28
2
9
2
38
2
9
1
≤ 2̄8
2
+ 38
2
9
2
38
1
9
2
≤ 2̄8
1
+ 38
1
9
1
con 2̄: la capacidad remanente del depósito :, que puede ser verificado en $(1).
# Complejidad. La complejidad de explorar el vecindario #
rel
(B) es $(=2).
12
Ejemplo: swap para GAP
Definición
Dada una solución factible para el GAP, el operador swap,
#swap, se define como:
# considerar dos clientes distintos 91 , 92 ∈ B asignado a los
depósitos 81 ≠ 82, respectivamente;
◦ remover 91 de 81 e insertarlo en 82;
◦ remover 92 de 82 e insertarlo en 81;
# Aplicar estos pasos para todos los clientes 91 , 92 ∈ B
asignados a depósitos distintos.
Propiedades
# Mejora. Una solución B′ ∈ #swap(B) es una mejora de B si
28
2
9
1
+ 28
1
9
2
< 28
1
9
1
+ 28
2
9
2
38
2
9
1
≤ 2̄8
2
+ 38
2
9
2
38
1
9
2
≤ 2̄8
1
+ 38
1
9
1
con 2̄: la capacidad remanente del depósito :, que puede ser verificado en $(1).
# Complejidad. La complejidad de explorar el vecindario #
rel
(B) es $(=2).
12