Métodos Constructivos

Gladys Maquera

I COPIOS 03 al 05 de noviembre de 2009

Algoritmos Heurísticos

Métodos Constructivos

Métodos de Busca Local

Métodos Combinados

Métodos de Resolución

Métodos construtivos

Los métodos constructivos son procedimientos iterativos que, en cada paso aumentan un elemento hasta completar una solución. Usualmente son métodos determinísticos y están basados en seleccionar, en cada iteración el elemento con mejor evaluación.

Métodos Constructivos

Seleccionar secuencialmente el elemento que minimiza el incremento en el costo parcial;

Eventualmente descartando algunos ya seleccionados;

De tal forma que al final se obtenga una solución viable ( F);

El aumento en el costo de la solución es llamado de función gulosa;

algoritmo míope, pues “ve” solamente lo que está mas próximo.

Métodos Constructivos

Problema de la Mochila

Problema de la Mochila Imagine que los alumnos del curso sean premiados con un

viaje en um cruzero marítimo después de finalizar sus estudios, patrocinado por la universidad.

En alta mar el navío comienza a hundirse...

Solo existe um barco salvavidas, que, solamente puede llevar c kilos

Problema de la Mochila

Cada persona i tiene un peso pi ,

Cada persona i proporciona un beneficio bi caso sea rescatada por el barco salvavidas,

El problema consiste en escoger las personas que aportaran con el mayor beneficio posible sin ultrapasar la capacidad del barco.

Problema de la Mochilapersona Peso (Kg) Beneficio

persona X 140 0

recién graduado 60 1

Atlético 100 3

Profesor de Ingeniería 80 4

Morena “ojos verdes” 75 3

Rubia 60 2

Pelé 90 10

Capacidad del barco: 250 Kg. Solución 1: Pelé + L+ A (250 Kg) Beneficio = 15

Problema de la Mochilapersona Peso (Kg) Beneficio

Persona X 140 0

recién graduado 60 1

ATLETICO 100 3

Profesor de Ingeniería 80 4

Morena “ojos verdes” 75 3

Rubia 60 2

Pelé 90 10

Capacidad del barco: 250 Kg. Solución 1: Pelé + L + A (250 Kg) Beneficio = 15

Solución 2: Pelé + MOV + PE (245 Kg) Beneficio = 17

Complejidad del Problema de la mochila

Para n personas existen 2n combinaciones posibles,

Ejemplo: Para n = 50 existen 1015 soluciones a ser evaluadas,

Una computadora que realiza una evaluación en10-8 segundos utilizaría aproximadamente 130 dias para encontrar la melhor solución!,

Conclusión: El barco se hundiría antes que la decisión sea elegida y se elija las personas que serán las escogidas.

Un método heurístico (constructivo) para el Problema de la Mochila

persona Peso (Kg) BeneficioBeneficio/Peso

persona X 140 0 0

recién graduado 60 1 0,017

ATLETICO 100 3 0,030

profesor de ingeniería 80 4 0,050

morena “ojos verdes” 75 3 0,040

rubia 60 2 0,030

Pelé 90 10 0,111

1º Paso: Calcular la relación beneficio/peso

Un método heurístico (constructivo) para el Problema de la Mochila

persona Peso (Kg) BeneficioBeneficio/Peso

Pelé 90 10 0,111

profesor de ingeniería 80 4 0,050

morena “ojos verdes” 75 3 0,040

rubia 60 2 0,030

ATLETICO 100 3 0,030

recién graduado 60 1 0,017

persona X 140 0 0

2º Paso: Ordenar los elementos

Un método heurístico (constructivo) para el Problema de la Mochila

persona Peso (Kg) BeneficioBeneficio/Peso

Pelé 90 10 0,111

profesor de ingeniería 80 4 0,050

Morena “ojos verdes” 75 3 0,040

rubia 60 2 0,030

ATLETICO 100 3 0,030

recién graduado 60 1 0,017

persona X 140 0 0

3º Paso: Elegir el elemento que producirá la mayor relación beneficio/peso, y que respete la capacidad del barco

Un método heurístico (constructivo) para el Problema de la Mochila

persona Peso (Kg) BeneficioBeneficio/Peso

Pelé 90 10 0,111

profesor de ingeniería 80 4 0,050

morena “ojos verdes” 75 3 0,040

rubia 60 2 0,030

ATLETICO 100 3 0,030

recién graduado 60 1 0,017

persona X 140 0 0

4º Paso: Repetir el paso anterior hasta que ningún elemento pueda ser insertado en el barco sin ultrapasar la capacidad del mismo.

Un método heurístico (constructivo) para el Problema de la Mochila

persona Peso (Kg) BeneficioBeneficio/Peso

Pelé 90 10 0,111

profesor de ingeniería 80 4 0,050

Morena “ojos verdes” 75 3 0,040

rubia 60 2 0,030

ATLETICO 100 3 0,030

recién graduado 60 1 0,017

persona X 140 0 0

4º Paso: Repetir el paso anterior hasta que ningún elemento pueda ser insertado en el barco sin ultrapasar la capacidad del mismo.

Un método heurístico (constructivo) para el Problema de la Mochila

Pelé (90, 10) Prof. de ingeniería (80, 4) Morena (75, 3)

Capacidad del barco: 250 Capacidad utilizada : 245 Beneficio: 17

Otras heurísticas constructivas

Problema de la Mochila

n=?, C=?w=[ ?, ?]p=[ ?, ?]

Heurística #1 Mochila 0-1

Ser goloso en la utilización de la capacidad: Seleccionar los items en orden cresciente del peso !

n=2, C=7w=[ 3 , 6 ]p=[ 2 , 10 ]

Apenas el item 1 es selecionado;

Valor (profit) de la selección es 2.

No provee la mejor solución! (item 2, valor 10)

Heurística #2 Mochila 0-1

Ser goloso en la ganancia del valor (profit): Seleccionar los items en orden decresciente del valor !

n=3, C=7w=[ 7, 3,2 ]p=[ 10, 8,6 ]

Valor (profit) de la selección es 10;

Apenas el item 1 es selecionado.

No provee la mejor selección! (items 2 y 3, valor 14)

Heurística #3 Mochila 0-1

Ser goloso en la densidad del valor: razón pi/wi

Seleccionar los items en orden decresciente de densidad de valor !

n=2, C=7w=[ 1 , 7 ]

p=[ 10 , 21 ]

Apenas el item 1 es seleccionado, con valor (profit) 10.

No provee la mejor solución! (item 2, valor 21)

Heurística #3: golosa en la densidad de valor pi/wi

Funciona para el Problema de la Mochila Fraccionária

n=2 , C=7

w=[ 1 , 7 ] p=[ 10 , 21 ]

Fase 1: El ítem 1 es seleccionado, con valor (profit) 10;

Fase 2: se selecciona 6/7 del ítem 2, agregando valor 18.

Solución óptima de valor 28 !

(x2=6/7)

(x1=1)

Algoritmo Goloso

Precepto: hacer una elección localmente ótima (miope), con la esperanza de que esta elección lleve a una solución óptima global.

La elección hecha en cada paso debe ser:

Viable: satisfacer las restricciones del problema;

Localmente óptima: la mejor elección local entre todas las elecciones viables;

Irrevocable: una vez hecha, la elección no puede ser alterada en los pasos subsecuentes (invariancia).

Los algoritmos golosos siempre generan soluciones óptimas?

Algoritmo de construcción golosa

Programación Dinámica Metodología

1. Caracterizar la estructura de una solución óptima;

2. Definir recursivamente el valor de una solución óptima;

3. Computar el valor de una solución óptima de manera bottom-up:

Primero encontrar soluciones óptimas para los subproblemas;

Después escoger cual utilizar en la solución óptima para el problema.

Mochila 0-1: Programación Dinámica

Relaciones de RecurrenciaSean dados:

Capacidad de la mochila: C Valor y peso de cada item i: (pi,wi)

Defina:ƒ[i,c] = valor de la solución óptima para:

una mochila de capacidad disponible c; items disponibles (candidatos a entrar) {1,...,i }.

Entonces:

Idea: •discretizar la capacidad c de 1 hasta C •aumentar i y c gradualmente hasta... •alcanzar la solución ƒ[n,C]

Mochila 0-1: Programación DinámicaRelaciones de recursividad: principio de la

optimalidad

0 , si i=0 o c=0ƒ [ i-1,c ] , si wi>cMax { pi + ƒ [ i-1,c-wi ] , ƒ [ i-1,c] } , si i>0 y

c≥wi

Principio de optimalidad para las relaciones de recursividad de la Mochila 0-1:

El mejor subconjunto de {1,..,i} que posee peso c es:

el mejor subconjunto de {1,..,i-1} que posee peso c ,

el mejor subconjunto de {1,..,i-1} que posee peso (c-wi ) mas el item i .

ƒ[i,c] =

Mochila 0-1: Programación DinámicaRelaciones de Recurrencia: interpretación

ƒ[i,c] =

0 , se i=0 ou c=0ƒ [ i-1,c ] , se wi>cMax { pi + ƒ [ i-1,c-wi ] , ƒ [ i-1,c] } , se i>0 e

c≥wi

2. wi ≤ c. En este caso el item i puede hacer parte de la solución, y escogemos el que proporciona mayor valor:

2.2 La solución óptima local incluye el item i: nuevo valor: pi + ƒ[ i-1,c-wi ]

2.1 La solución óptima local noo incluye el item i: mismo valor anterior de ƒ

1. wi>c. En este caso el item i no puede hacer parte de la solución, porque se estuviese el peso sería>c, contrariando el principio de la optimalidad;

Mochila 0-1: Programación DinámicaAlgoritmo y complejidad

for c 0 to Cƒ[ 0,c] = 0

for i 1 to nƒ[ i,0] = 0for c 1 to C

if (wi <= c) // item i puede hacer parte de la solución

if (pi + ƒ[ i-1,c-wi ] > ƒ[ i-1,c ]ƒ[ i,c ] = pi + ƒ[ i-1,c- wi ] // item i participa de

la solución

else ƒ[ i,c ] = ƒ[ i-1,c ] // item i no participa de la

soluciónelse ƒ[ i,c] = ƒ[ i-1,c ] // wi > c : item I no puede hacer parte de

la solución

Complejidad: O(nC) pseudo-polinomial (depende de C)

Métodos Constructivos

Problema del Agente Viajero

Problema del Agente Viajero

17! (3.5568734e14)soluciones posibles

Solución óptima:Coste=226.64

Problema del Agente Viajero

Iteración: 0 Costo: 403.7 Solución óptima: 226.64

Problema del Agente Viajero

532! soluciones posibles

Coste solución óptima =27.686 millas

Métodos constructivos para o PAV

Los mas destacados para el PAV son: Heurísticas del vecino mas Próximo Heurísticas de Inserción Heurísticas basadas en Árboles Generadoras Heurísticas basadas en Economías

Heurística del “Vecino más Próximo”

Añade en cada paso el vértice más cercano al actual. Debido a Rosenkrantz, Stearns y Lewis (1977)

InicializaciónSeleccionar un vértice j al azar.Hacer t = j y W = V \ {j}.

M ientras (W )Tomar j de W / c tj = min {c ti / i en W}Conectar t a jHacer W = W \ {j} y t =j.

Complejidad: O(n2) Influencia del nodo

inicial Aplicar a partir de cada

nodo: O(n3)

Agente viajeroHeurística Constructiva #1: Vecino mas Próximo

5

4 3

2

1

1

3

2

5

7 ℓ =18

Agente viajeroHeurística Constructiva #1: Vecino mas Próximo

Posibilidad de no encontrar una solución viable:

4

3

2

1

2 2

3 3

1

Agente viajeroHeurística Constructiva #1: Vecino

mas Próximo

Posibilidad de obtener soluciones arbitrariamente “ruins”:

5

4 3

2

1

2

1

1

1

1

22

22

M

AV- Heurística Constructiva #2: Heurística de inserción

Idea: Iniciar con una sub ruta que considere

tres ciudades (las cuales pueden ser obtenidas por la heurística del vecino mas próximo)

Adicionar la ciudad k (entre las ciudades i y j) que producirá la inserción mas barata sij = cik + ckj - cij

Terminar cuando todas las ciudades fueren visitadas

AV- Heurística Constructiva #2: Heurística de inserción

Ciudad 1 2 3 4 5

1 0 12 7 9 8

2 12 0 11 7 6

3 7 11 0 12 13

4 9 7 12 0 8

5 8 6 13 8 0

Sub-Ruta inicial: 1->3->2->1 Costo: 30

AV- Heurística Constructiva #2: Heurística de inserción

2

4

3

5

1

12

7

11

AV- Heurística Constructiva #2: Heurística de inserción

2

4

3

5

1

12

7

11

7

9

Costo de la inserción = 9 + 7 – 12 = 4

AV- Heurística Constructiva #2: Heurística de inserción

2

4

3

5

1

12

7

11

Costo de la inserción = 12 + 7 – 11 = 8

12

7

AV- Heurística Constructiva #2: Heurística de inserción

2

4

3

5

1

12

7

11

Costo de la inserción = 9 + 12 - 7 = 14

129

AV- Heurística Constructiva #2: Heurística de inserción

Sub ruta: 1->3->2->5->1 Costo parcial = 32

i j k sij

1 2 4 9 + 7 - 12 = 4

1 3 4 9 + 12 – 7 = 14

2 3 4 12 + 7 – 11 = 8

1 2 5 8 + 6 – 12 = 2

1 3 5 8 + 10 – 7 = 11

2 3 5 10 + 6 – 11= 5

AV- Heurística Constructiva #2: Heurística de inserción

Ruta final: 1->3->4->2->5->1 Costo: 37

i j k sij

1 3 4 9 + 9 – 7 = 11

5 1 4 9 + 8 – 8 = 9

3 2 4 9 + 7 – 11 = 5

2 5 4 8 + 7 – 6 = 9

AV- Heurística Constructiva #2: Heurística de inserción

Extender ciclos que pasan por unos cuantos vértices (subtours), insertando un vértice nuevo en cada paso.

Mas Barato

Mas Distante

Mas Próximo

Aleatorio

Heurísticas basadas en Árboles Generadores: árboles y

Acoplamientos Un grafo es conexo si todo par de vértices esta unido por un

camino. Un árbol es un grafo conexo que no contiene ciclos. Un árbol generador es un árbol sobre todos los vértices. Un acoplamiento es un subconjunto M del conjunto de aristas tal

que cada vértice del grafo es incidente con una arista de M. Un acoplamiento es perfecto si es de cardinalidad máxima e igual

a |V|/ 2.

1

23

4

5

6

7

8

1

23

4

5

6

7

8

ÁrbolGenerador

AcoplamientoPerfecto

48. R. Martí. Universidad de Valencia.

Heurísticos basados enÁrboles Generadores

Paso 1Árbol generador demínimo peso

2

3 4

5

1

86

7

9

10

25

16

25 19

19

1415

179

2

3 4

5

1

86

7

910

2

3 4

5

1

86

7

9

10

25

16

19

14

179

68

45

Paso 2Duplicación de Aristas

Paso 3Obtención del Tour

Algoritmo de Christofides

Paso 2: En lugar de duplicar las aristas del árbol se añaden las aristas de un acoplamiento perfecto de mínimo peso sobre los vértices de grado impar del árbol generador.

2

3 4

5

1

86

7

9

10

25

16

25 19

19

1415

179

21

19

2

3 4

5

1

86

7

9

10

25

16

19

1415

179

21

1948

Heurísticos basados en Ahorros

Combinar sucesivamente subtours hasta obtener un tour. (Clarke y Wright, 1964)

Los subtours tienen un vértice común llamado base (z)

z

i

j z

i

j

Comparación dos Métodos

La librería de dominio público TSPLIB contiene un conjunto de ejemplos con la solución óptima del TSP. (Reinelt , 1991)

c c

ch opt

opt

100Porcentaje de desviación del óptimo :

Heurístico Desviacióndel Óptimo

T. Ejecución(pr2392)

Vecino más Próximo 18.6% 0.3Inserción más Alejada 9.9% 35.4Christofides 19.5% 0.7Ahorros 9.6% 5.07

Conclusiones

Los Métodos Constructivos son heurísticas que proporcionan rápidamente una solución relativamente buena.

Al diseñar un Método Heurístico tenemos que estudiar Calidad: Estudio Teórico o Empírico.

Eficiencia: Detalles de implementación, Agilizar los cálculos.