Data Mining & Bigdata

Clase 5
Profesor Dr. Mauricio Sepúlveda

1
Temario
• Optimización combinatoria
• Heurísticas
• Búsqueda Local
• Metaheurísticas

2
Introducción
Que es un Data Scientist
Es un experto en Data Science (Ciencia de datos), su trabajo
consiste en extraer conocimiento a partir de los datos para
poder responder a las preguntas que se le formulan.

Habilidades de un Data Scientist

3
Optimización combinatoria

4
Ejemplo: enrutamiento de
vehículos

Usted dirige una empresa de transporte con

su propio automóvil.
Tiene un conjunto de trabajos de recolección
y mañana debe hacer entregas en la ciudad.
¿Qué secuencia de paradas debe elegir para
terminar los trabajos lo antes posible?

Decisión operativa
• Problema de optimización
• El problema del vendedor Viajero (TSP)
5
 Ejemplo de problema de optimización
El problema del vendedor Viajero
(TSP)
2 3

1 4
5
7

Solución Factible: 1 2 7 3 4 5 6 1 con valor: 184

6
Problemas de optimización
combinatoria (programación entera)

Nos encontraremos con varios problemas

abstractos diferentes
Problema del vendedor ambulante
Problema de asignación de tareas
(Multidimensional 0/1) Problemas de mochila
… y más
Todos son problemas de optimización
combinatoria (COP), del tipo programación
entera (IP), donde las variables solo pueden
tomar valores enteros
7
Programación entera

Un problema de programación entera tiene la

siguiente estructura:

Max c x
s. a.
Axb
x  Z+
Programación entera
Resolución de un problema de programación lineal entera
Enfoque ingenuo: Resolver con programación lineal y aproximar la
solución.

Ejemplo:

Max 1.00 x1 + 0.64 x2

Sujeto a

50 x1 + 31 x2 ≤ 250

3 x1 - 2x2 ≥ -4

x1 , x2 ≥ 0, x1 , x2 entera

En este cado no es muy útil, ya que la solución entera es (5,0), si no se

pide que las variables sean enteras, la solución del problema de
programación lineal es (376/193, 950/193).
Problema de optimización
combinatoria

Una instancia de COP es un par (S, f)

• S es el conjunto de soluciones utilizables
(factibles e implícitas)
• f: S → R es la función de costo

El objetivo es encontrar una solución globalmente

óptima:

i  S : f (i )  f (i), i  S
* *

10
Ejemplo 1: Una instancia del TSP
3 ciudades: 1, 2, 3
Dados (S,f)
min f(s)
sϵS

11
 Ejemplo 2: Instancia del problema de la
mochila binaria.
Mochila con capacidad 101, 10 "artículos" (por ejemplo,
proyectos, ...) 1, ..., 10
Dados (S,f)
max f(s)
sϵS

S = Aquellas soluciones de S+ que son factibles (implícitamente por la restricción

presupuestaria)

12
Comentarios acerca de COP

• S rara vez se da explícitamente

Puede, por ejemplo, darse por restricciones en una formulación
de IP
• S es a menudo un subconjunto de soluciones
factibles en un espacio más amplio de soluciones
posibles (factible + inviable)
• A menudo una representación compacta de la
instancia
• Una solución a menudo viene dada por los valores de
las variables de decisión (x1, ..., xn)
• Se tienen algoritmos de tiempo polinomiales para
verificar la membresía en S y el costo/valor de las
soluciones candidatas
13
¿Cómo podemos resolver
problemas?

A veces puede ser ventajoso distinguir tres

grupos de métodos para encontrar
soluciones a nuestros problemas abstractos

• Algoritmos exactos
• Algoritmos heurísticos

14
Algoritmos exactos

El algoritmo brinda la solución óptima para un

problema de optimización

Ejemplos:

Backtracking
Branch and Bound
Programación Dinámica
Otros…

15
Algoritmo Backtracking

16
Algoritmo Backtracking
4 reinas

17
Algoritmo Branch and Bound

La solución de Backtracking se puede

optimizar si conocemos el límite del mejor
subárbol de solución posible enraizado en
cada nodo. Si el mejor subárbol es peor que
el mejor actual, simplemente podemos
ignorar este nodo y sus subárboles.
Entonces, calculamos el límite (la mejor
solución) para cada nodo y comparamos el
límite con la mejor solución actual antes de
explorar el nodo.

18
Algoritmo Branch and Bound

19
Algoritmo Branch and Bound

20
Programación dinámica
Es un procedimiento recursivo que divide de manera iterativa el
problema, incorporando en cada etapa, soluciones óptimas cada vez
mayores para el problema original. El procedimiento puede hacerse
hacia delante o hacia atrás.

Está basada en el principio de optimalidad de Bellman:

“Cualquier subsecuencia de decisiones de una secuencia óptima de
decisiones que resuelve un problema también debe ser óptima
respecto al subproblema que resuelve.”

Algoritmo
1.Dividir el problema en subproblemas más pequeños.
2.Resolver estos problemas de manera óptima.
3.Usar estas soluciones óptimas para construir una solución óptima al
problema original.

21
Programación dinámica
Ejemplo Sucesión de Fibonacci

Esta sucesión puede expresarse mediante la siguiente recurrencia:

22
Heurísticas

23
Algoritmos heurísticos

• No garantizan encontrar la solución óptima.

• No necesariamente tienen un límite en lo malo
que puedan realizar
• Es decir, pueden devolver una solución que es
arbitrariamente mala en comparación con la
solución óptima
• Sin embargo, en la práctica, los algoritmos
heurísticos (heurísticos para abreviar) han
demostrado ser exitosos.

24
La explosión combinatoria

La explosión combinatoria se refiere al

hecho de que algunas funciones aumentan
muy rápidamente.

¿Cómo resolverías un problema de

vendedor ambulante con 100 clientes?

25
Métodos heurísticos

Algoritmos constructivos
• Algoritmo Trivial
• Algoritmo Golozo
Algoritmos de mejora (Veremos Búsqueda local)
• Ascensión de colinas
• Metaheurísticas
• GRASP
• Simulated Annealing
• Búsqueda tabú
• Algoritmos genéticos
26
Ejemplo TSP

Algoritmo Trivial:
1 2 3 4 5 6 7 1 (288)

Construcción mediante un Algoritmo Golozo:

1 3 5 7 6 4 2 1 (160)

27
Búsqueda Local

28
Dada una solución: Cómo encontrar
una mejor?

La modificación de una solución dada da una

"solución vecina"
Un cierto conjunto de operaciones sobre una
solución da un conjunto de soluciones vecinas,
una vecindad.

Evaluaciones de vecinos
 Valor de la función objetivo
 Factibilidad ?
29
Ejemplo TSP

Operador: 2-opt
Cuantos vecinos?

30
Valor del objetivo

Óptimos locales

Óptimo global

31
Definición de vecindad

Sea (S, f) una instancia de COP

Una función de vecindad es un mapeo desde una
solución hasta el conjunto de posibles soluciones,
alcanzado por un movimiento.
N : S  2S

Para una solución dada s  S , N define una

vecindad de soluciones, t  N ( s) que en cierto
sentido está "cerca" de s.
N ( s)  S es entonces un "vecino" de s.
32
Búsqueda local
 También llamado mejora iterativa
 Los movimientos se realizan sólo si se mejora
la solución

Algoritmo 1
s  Generar SolucionInicial()
Repeat
s  Mejorar(s,N(s))
Until no hay mejora posible

33
Búsqueda local

N (σ1 ) N (σ 2 ) N (σ 4 )
N (σ 0 )
σ1 σ2 σ4
σ0 σ3

Solución inicial N (σ 3 ) Óptimo local

Desafío principal en la búsqueda local

¿Cómo podemos evitar que la búsqueda se pare en un óptimo local?
34
 Búsqueda local

sk 1  N  ( sk ), k  0, …
N  ( s1 )
N  ( s0 )

s1

s1
s0 s1
s0 s2

Un movimiento es el proceso de seleccionar una solución dada en el

"vecindario" de la solución actual para que sea la solución actual, en la
próxima iteración
35
Hill Climbing (Ascensión de colinas)

1. Elige un punto al azar en el espacio de

búsqueda
2. Considerar a todos los vecinos del estado
actual.
3. Elegir al vecino con la mejor calidad y pasar a
ese estado.
4. Repetir hasta que todos los estados vecinos
sean de menor calidad.
5. Devuelve el estado actual como estado de
solución.

36
Hill Climbing (Ascensión de colinas)
Hill Climbing Algorithm
s = startNode;
loop do
L = N(s);
nextEval = EVAL(s);
nextNode = NULL;
for all x in L
if (EVAL(x) < nextEval)
nextNode = x;
nextEval = EVAL(x);
if nextEval >= EVAL(s)
return s;
s = nextNode;
End loop
37
Hill Climbing (Ascensión de colinas)
Ejemplo:
Ordenamiento de casillas

38
Trabajo de Laboratorio
CLASE5:Lab01
• Realice el trabajo en grupos de 2 estudiantes.

• Utilice el archivo “Problema de 50 clentes

empresa.txt”, que contiene un listado de
clientes de un banco con 2 campos: Ingreso
potencial (M$) para el banco y tiempo
estimado de atención (m). El banco tiene 1
ejecutivo y 2 días para rentabilizar esa base,
por ello dispone de 5177 minutos de atención.
Debe separar los clientes en 2 grupos y
optimizar los ingresos.
39
 Trabajo de Laboratorio
Segmentación de clientes
n
max  ci x i
El problema de la Mochila
Binaria. s.t.
i 1
• n artículos {1, ..., n}
n

a x
disponibles, con peso ai y
ganancia ci i i b
i 1
• Una selección de los artículos
se empacarán en una
mochila con capacidad b. 1
xi 
• Encuentra los artículos que
0
maximizan el beneficio.
40
Metaheurísticas

41
Metaheurísticas

• Concepto introducido por Glover (1986)

• Enfoques genéricos de solución heurística
diseñados para controlar y guiar heurísticas
específicas orientadas a problemas
• A menudo inspirado por analogías con
procesos naturales
• Desarrollo en los últimos 30 años
• La Metaheurística se puede usar para guiar
una búsqueda local y para ayudarla a escapar
de un óptimo local.
42
GRASP
 GRASP (Greedy Randomized Adaptive
Search procedure) es una heurística que
combina procedimientos constructivos y de
búsqueda local

Algoritmo
While no condicion fin do
s  ConstruirSolucionGRASP ()
AplicarLocalSearch(s)
MemorizarMejorSolución()
End While
43
Simulated annealing

 Es una de las metaheurísticas más antiguas

(80s) que incorpora una estrategia explícita
para impedir óptimos locales

 Basado en la física del calentamiento de

metales. Se propone una similitud entre una
buena estructura cristalina de metales y una
buena estructura de soluciones para problemas
de optimización combinatoria.

 Se trata de minimizar una función objetivo que

representa la energía del sistema.
44
Simulated annealing

 Idea: Permitir movimientos a soluciones con una

peor evaluación (según la función objetivo) de
forma de poder escapar de óptimos locales.
 La probabilidad de realizar los movimientos
anteriores decrece durante la búsqueda, junto con
la Temperatura del proceso y la diferencia con la
solución óptima (o error).
 Al comienzo, la temperatura es alta y cualquier
transición entre estados es permitida y soluciones
que empeoren la función objetivo pueden ser
aceptadas con mayor probabilidad que más tarde
cuando la temperatura disminuye.

45
Algoritmo Simulated annealing (simplificado)

s  GenerarSolucionInicial
T  T0
While no condicion fin do
Seleccionar s´ N(s) randómicamente
if EVAL(s´) < EVAL(s) then
s  s´
else
Aceptar s´como nueva solución con
probabilidad P(T, s´,s)
end if
Disminuir (T)
End While
46
Algoritmo Simulated annealing
Ejemplo Placement-Routage

http://fooo.fr/~vjeux/epita/recuit/recuit.html#
47
Búsqueda Tabú
 Utiliza una búsqueda local con memoria a
corto plazo que le permite “escapar” de
mínimos locales y evita ciclos.
 La memoria de corto plazo esta
representada por la lista Tabú la cual registra
las últimas soluciones “visitadas” e impide
volver a ellas en los próximos movimientos
 La lista Tabu se actualiza normalmente en
forma FIFO

48
Algoritmo Búsqueda Tabú

s  GenerarSolucionInicial
ListaTabu  
While no condicion fin do
s  MejorSolucion(s, N(s) ϵ ListaTabu)
Actualizar(ListaTabu)
End While

49
Algoritmos Genéticos (GA)

50
GA - Analogías con biología

• Representación de objetos complejos

por un vector de componentes simples
• Cromosomas
• Selección de más apto
• Evolución darwiniana

• El AG Clásico: Usa codificación binaria

51
Componentes de un GA

• Un problema para resolver, y ...

• Técnica de codificación (gen, cromosoma)
• Procedimiento de inicialización (creación)
• Función de evaluación (entorno)
• Selección de padres (reproducción)
• Operadores genéticos (mutación,
cruzamiento/recombinación)
• Configuración de parámetros (práctica y arte)

52
 Algoritmos Genéticos

AG clásicos: Cromosomas binarios

Cromosoma, vector componente, vector,
cadena, solución, Individuo x = (x1, ..., x7)

1 2 3 4 5 6 7
1 0 1 0 0 1 0

Posición
Gene, componente, variable, x3
Valor

Dominio de genes: x3{0,1}

53
Algoritmos Genéticos

54
 Algoritmos Genéticos

AG- Evolución

• N generaciones de poblaciones
• Por cada paso en la evolución
• Selección de individuos para operaciones
genéticas
• Creación de nuevos individuos
(reproducción)
• Mutación
• Selección de individuos para sobrevivir
• Tamaño de población fijo M

55
 Algoritmos Genéticos

El ciclo de reproducción del AG

children
reproduction modification
modified
parents children
population evaluation
evaluated children
deleted
members

discard

56
 Algoritmos Genéticos

AG- Mutación: Modificación local

Antes: (1 0 1 1 0 1 1 0)
Después: (1 0 1 0 0 1 1 0)

Antes: (1.38 -69.4 326.44 0.1)

Después: (1.38 -67.5 326.44 0.1)

• ¿Causa movimiento en el espacio de

búsqueda? (Local o global)
• Restaura la información perdida a la
población
57
 Algoritmos Genéticos

AG- Crossover: Cruzamiento

Crossover es una característica crítica de los

AG:
• Se acelera en gran medida la búsqueda
temprana en la evolución de una población
• Conduce a una combinación efectiva de
esquemas (subsoluciones en diferentes
cromosomas) 58
 Ejemplo 1
Encontrar el máximo de la función f(x) = x2
sobre los enteros {0,1, 2, . . . , 31}.
Utilizando un alfabeto para los cromosomas constituido por {0, 1},
necesitaremos cadenas de longitud 5 para representar los 32 puntos del
espacio de búsqueda.

Población inicial

59
 Algoritmos Genéticos

Ejemplo 1
Encontrar el máximo de la función f(x) = x2
sobre los enteros {0,1, 2, . . . , 31}.

Use tira la ruleta dando los siguientes valores 0.58, 0.84, 0.11 y 0.43, en
base a ello se seleccionan los individuos a cruzarse en la primera
generación.
Si la probabilidad de cruzamiento la establecemos en 0.8, entonces
debemos tirar los dados para determinar si se realiza cada uno de los 2
cruzamientos que nos van a generar 4 nuevos individuos.

Luego se debe determinar el punto de cruzamiento, en cada cruzamiento,

que también es aleatorio. En el ejemplo van a ser 2 y 3 respectivamente.
Luego se debe determinar si casa cromosoma generado será mutado. A
este parámetro se le da un número muy bajo. Supongamos que la
probabilidad fue favorable para el primer gen del 3er cromosoma.
60
 Algoritmos Genéticos

Ejemplo 1
Encontrar el máximo de la función f(x) = x2
sobre los enteros {0,1, 2, . . . , 31}.

Generación 1

61
Ejemplo 2

El problema del vendedor Viajero:

Busque un recorrido de un conjunto dado de ciudades.

tal que:
• Cada ciudad es visitada solo una vez
• Se minimiza la distancia total recorrida

62
 Algoritmos Genéticos

Ejemplo 2- Representación
Una posible representación, es en una lista ordenada de
ciudades
A esta representación se le llama order-based GA.

1) London 3) Dunedin 5) Beijing 7) Tokyo

2) Venice 4) Singapore 6) Phoenix 8) Victoria

Listado de ciudades 1 (3 5 7 2 1 6 4 8)
Listado de ciudades 2 (2 5 7 6 8 1 3 4)

63
 Algoritmos Genéticos

Ejemplo 2 - Cruzamiento
Crossover combina inversión y recombinación

Padre1 (3 5 7 2 1 6 4 8)
Padre2 (2 5 7 6 8 1 3 4)
Hijo (5 8 7 2 1 6 3 4)

Este operador es llamado order-based crossover

64
 Algoritmos Genéticos

Ejemplo 2- Mutación
La mutación implica el reordenamiento de la
lista:

Antes: (5 8 7 2 1 6 3 4)

Después: (5 8 6 2 1 7 3 4)

65
 Algoritmos Genéticos

Ejemplo 2- Evolución con 30 Ciudades

66
 Algoritmos Genéticos

Ejemplo 2- Evolución con 30 Ciudades

Generación 6, mejor solución= 941 Generación 8, mejor solución= 800

Generación 12, mejor solución= 652 Generación 25, solución óptima= 42067
 Algoritmos Genéticos

Ejemplo 2- Evolución con 30 Ciudades

68
Trabajo de Laboratorio
• Realice el trabajo en grupos de 2 estudiantes.

• Para los datos del laboratorio CLASE5:Lab01,

encuentre una solución óptimo local usando Solver
de Excel para el método evolutionary.

• Encuentre una solución óptima local utilizando

Jupiter Notebook con Python.
https://jupyter.org/try

69