Optimizaci´ on en Ingenier´ıa

Dr. Carlos A. Coello Coello

Optimizaci´ on en Ingenier´ıa

Dr. Carlos A. Coello Coello Departamento de Computaci´ on CINVESTAV-IPN Av. IPN No. 2508 Col. San Pedro Zacatenco M´ exico, D.F. 07300 email: [email protected]

Clase No. 3

2009

Optimizaci´ on en Ingenier´ıa

Dr. Carlos A. Coello Coello

M´ etodo de B´ usqueda de Fibonacci Algoritmo Paso 1:

Paso 2: Paso 3:

Paso 4:

Clase No. 3

Elegir un l´ımite inferior a y un l´ımite superior b. L=b−a Elegir un n´ umero deseado de iteraciones N k=2 L∗k = (Fn−k+1 /Fn+1 ) ∗ L x1 = a + L∗k ; x2 = b − L∗k Calcular f (x1 ) ´ o f (x2 ) (el que no se haya evaluado antes) Usar la propiedad de eliminaci´ on de regiones. Establecer nuevos valores de a y b. ¿Es k > N ? Si no, k = k + 1, GOTO Paso 2 ELSE TERMINAR 2009

Optimizaci´ on en Ingenier´ıa

Dr. Carlos A. Coello Coello

M´ etodo de B´ usqueda de Fibonacci Observaciones: La funci´on a optimizarse debe ser unimodal en el intervalo inicial de b´ usqueda. Este m´etodo no puede localizar el ´ optimo exacto del problema. S´olo proporciona un intervalo, el cual posiblemente sea muy peque˜ no. Debe especificarse el n´ umero de iteraciones a efectuarse.

Clase No. 3

2009

Optimizaci´ on en Ingenier´ıa

Dr. Carlos A. Coello Coello

M´ etodo de B´ usqueda de Fibonacci Con la b´ usqueda de Fibonacci, el intervalo se reduce a (2/Fn+1 ) ∗ L despu´es de n evaluaciones de la funci´ on objetivo. Por tanto, para una precisi´ on deseada , se requiere un n´ umero de evaluaciones correspondientes a la ecuaci´ on 2 Fn+1

Clase No. 3

(b − a) = 

2009

Optimizaci´ on en Ingenier´ıa

Dr. Carlos A. Coello Coello

M´ etodo de B´ usqueda de Fibonacci N´ otese que debe calcularse la serie de Fibonacci hasta N + 1 al usar este m´etodo. A cada iteraci´ on, se elimina una proporci´ on del espacio de b´ usqueda de: (k = iteraci´ on actual) Fn−k /Fn−k+2 Para valores grandes de n, este valor es cercano a 38,2 %, lo cual es mejor que la reducci´ on del m´etodo de divisi´ on de intervalos por la mitad, que elimina el 25 %.

Clase No. 3

2009

Optimizaci´ on en Ingenier´ıa

Dr. Carlos A. Coello Coello

M´ etodo de la Secci´ on Dorada Uno de los problemas de la b´ usqueda de Fibonacci es que deben calcularse y almacenarse los n´ umeros de Fibonacci. Otro problema es que a cada iteraci´ on la proporci´ on de la regi´ on eliminada no es la misma. Para aliviar estas dos desventajas y mantener el c´ alculo de una sola evaluaci´on de la funci´ on objetivo por iteraci´ on, se usa el m´etodo de la secci´on dorada.

Clase No. 3

2009

Optimizaci´ on en Ingenier´ıa

Dr. Carlos A. Coello Coello

M´ etodo de la Secci´ on Dorada En este algoritmo, el espacio de b´ usqueda (a, b) se mapea linealmente a un intervalo unitario (0, 1). Posteriormente, dos puntos en τ desde cualquier extremo del espacio de b´ usqueda se eligen en forma que a cada iteraci´ on la regi´ on eliminada sea de (1 − τ ) con respecto a la iteraci´ on previa. Esto se puede lograr igualando 1 − τ con (τ × τ ). Esto produce el n´ umero dorado: τ =0.618.

Clase No. 3

2009

Optimizaci´ on en Ingenier´ıa

Dr. Carlos A. Coello Coello

M´ etodo de la Secci´ on Dorada

Clase No. 3

2009

Optimizaci´ on en Ingenier´ıa

Dr. Carlos A. Coello Coello

M´ etodo de la Secci´ on Dorada El valor de τ tiene su historia. Los arquitectos de la Grecia antigua cre´ıan que un edificio de dimensiones d y b, el cual cumpliera con la relaci´on d+b d τ= = d b tendr´ıa las propiedades m´ as placenteras a los sentidos (ver figura del siguiente acetato):

Clase No. 3

2009

Optimizaci´ on en Ingenier´ıa

Dr. Carlos A. Coello Coello

M´ etodo de la Secci´ on Dorada

Tambi´en se encuentra este concepto en la geometr´ıa de Euclides.

Clase No. 3

2009

Optimizaci´ on en Ingenier´ıa

Dr. Carlos A. Coello Coello

M´ etodo de la Secci´ on Dorada Algoritmo Paso 1:

Paso 2:

Paso 3:

Clase No. 3

Elegir un l´ımite inferior a y un l´ımite superior b. Elegir una tolerancia  Normalizar la variable x usando: w = (x − a)/(b − a) aw = 0, bw = 1, Lw = bw − aw k=1 w1 = aw + (0,618)Lw w2 = bw − (0,618)Lw IF f (w1 ) < f (w2 ) aw = w2 ELSE bw = w1 Lw = bw − aw IF |Lw | <  TERMINAR ELSE k = k + 1; GOTO Paso 2 2009

Optimizaci´ on en Ingenier´ıa

Dr. Carlos A. Coello Coello

M´ etodo de la Secci´ on Dorada En el m´etodo de la secci´ on dorada, el intervalo se reduce a (0.618)n−1 despu´es de n evaluaciones de la funci´ on objetivo. De tal forma, el n´ umero de evaluaciones de la funci´ on objetivo que se requieren para lograr una precisi´ on deseada  se calcula resolviendo (para n) la siguiente ecuaci´ on: (0,618)n−1 (b − a) = 

Clase No. 3

2009

Optimizaci´ on en Ingenier´ıa

Dr. Carlos A. Coello Coello

M´ etodo de la Secci´ on Dorada Al igual que en la b´ usqueda de Fibonacci, s´ olo se requiere una evaluaci´on de la funci´ on objetivo por iteraci´ on y la eliminaci´ on regional efectiva por evaluaci´ on de la funci´ on es exactamente 38.2 %, que es un valor m´ as alto que en el m´etodo de divisi´ on de intervalos por la mitad. Esta cantidad es la misma que en la b´ usqueda de Fibonacci para un valor grande de n. De hecho, para un valor grande de n, el m´etodo de Fibonacci es equivalente a la secci´on dorada.

Clase No. 3

2009

Optimizaci´ on en Ingenier´ıa

Dr. Carlos A. Coello Coello

Comparaci´ on de los M´ etodos de Eliminaci´ on de Regiones Comparemos ahora las eficiencias relativas de los m´etodos de eliminaci´on de regiones que hemos visto hasta ahora. Denotemos el intervalo de incertidumbre original como Lo y al intervalo de incertidumbre final, despu´es de N evaluaciones de la funci´ on objetivo le llamaremos LN . Supongamos ahora que consideramos a la reducci´on fraccional (RF ) del intervalo original como una medida de m´erito de los m´etodos de eliminaci´ on de regiones. Tenemos entonces:

Clase No. 3

2009

Optimizaci´ on en Ingenier´ıa

Dr. Carlos A. Coello Coello

Comparaci´ on de los M´ etodos de Eliminaci´ on de Regiones

RF (N ) =

LN Lo

La siguiente tabla muestra los intervalos finales de incertidumbre de cada uno de los m´etodos que vimos:

Clase No. 3

2009

Optimizaci´ on en Ingenier´ıa

Dr. Carlos A. Coello Coello

Comparaci´ on de los M´ etodos de Eliminaci´ on de Regiones

Clase No. 3

M´etodo

F´ ormula

B´ usqueda Exhaustiva

LN =

Div. intervalos por la mitad

LN =0.5

Fibonacci

LN =

Secci´on dorada

LN =(0.618)

2 N Lo N/2

Lo

2

FN +1 Lo N −1

Lo

2009

Optimizaci´ on en Ingenier´ıa

Dr. Carlos A. Coello Coello

Comparaci´ on de los M´ etodos de Eliminaci´ on de Regiones Las reducciones fraccionales pueden obtenerse f´ acilmente: B´ usqueda exhaustiva: RF (N ) =

LN 2Lo 2 = = Lo N Lo N

Divisi´on de intervalos por la mitad: LN 0,5N/2 Lo RF (N ) = = = 0,5N/2 Lo Lo

Clase No. 3

2009

Optimizaci´ on en Ingenier´ıa

Dr. Carlos A. Coello Coello

Comparaci´ on de los M´ etodos de Eliminaci´ on de Regiones Fibonacci: LN 2Lo 2 RF (N ) = = = Lo FN +1 Lo FN +1 Secci´on Dorada: LN (0,618)N −1 Lo = = (0,618)N −1 RF (N ) = Lo Lo

Clase No. 3

2009

Optimizaci´ on en Ingenier´ıa

Dr. Carlos A. Coello Coello

Comparaci´ on de los M´ etodos de Eliminaci´ on de Regiones La siguiente tabla muestra los valores de RF (N ) para distintos valores de N . Estos valores son indicativos de la eficiencia de cada m´etodo. M´etodo

N =5

N = 10

N = 15

N = 20

0.4

0.2

0.133

0.1

0.177

0.03125

0.0055

0.0009765

F6 =13

F11 =144

F16 =1597

F21 =17711

Fibonacci

0.1538

0.01389

0.00125

0.000113

Secci´ on dorada

0.1459

0.01315

0.001185

0.00010685

B´ usqueda Exhaustiva Div. intervalos por la mitad

Clase No. 3

2009

Optimizaci´ on en Ingenier´ıa

Dr. Carlos A. Coello Coello

Comparaci´ on de los M´ etodos de Eliminaci´ on de Regiones De esta tabla se desprende que el m´etodo m´ as eficiente es el de Fibonacci, seguido por la secci´ on dorada. En la pr´actica, suele calcularse el n´ umero de iteraciones que se requieren para obtener una precisi´ on dada. Esto se puede obtener usando: LN =   = precisi´on requerida. Si usamos Lo = 1, podemos obtener el n´ umero de iteraciones que requiere cada m´etodo para lograr una precis´on dada. Ver la tabla siguiente:

Clase No. 3

2009

Optimizaci´ on en Ingenier´ıa

Dr. Carlos A. Coello Coello

Comparaci´ on de los M´ etodos de Eliminaci´ on de Regiones M´etodo

 =0.1

 =0.05

 =0.01

 =0.001

B´ usqueda Exhaustiva

19

39

199

1999

Div. intervalos

7

9

14

20

6

8

11

16

por la mitad Secci´on dorada

Clase No. 3

2009

Optimizaci´ on en Ingenier´ıa

Dr. Carlos A. Coello Coello

M´ etodos de Aproximaci´ on Polinomial o Estimaci´ on de Puntos Los m´etodos de eliminaci´ on de regiones que vimos anteriormente, s´olo requieren que la funci´ on sea unimodal. Por tanto, son aplicables tanto a funciones continuas como discontinuas, as´ı como a problemas con variables discretas. La l´ ogica de estos m´etodos se basa en una simple comparaci´ on de valores de la funci´ on en 2 puntos diferentes. Adem´ as, esta comparaci´ on s´ olo toma en cuenta el ordenamiento de los valores de la funci´ on y no involucra de manera alguna a las magnitudes de la diferencia entre valores funcionales.

Clase No. 3

2009

Optimizaci´ on en Ingenier´ıa

Dr. Carlos A. Coello Coello

M´ etodos de Aproximaci´ on Polinomial o Estimaci´ on de Puntos Los m´etodos de estimaci´ on de puntos s´ı toman en cuenta las magnitudes relativas de los valores de la funci´on y, en consecuencia, suelen tener mejor desempe˜ no que los m´etodos de eliminaci´ on de regiones. Sin embargo, esta mejora en eficiencia se obtiene a partir de requerir que las funciones a optimizarse sean sufientemente “suaves”.

Clase No. 3

2009

Optimizaci´ on en Ingenier´ıa

Dr. Carlos A. Coello Coello

M´ etodos de Aproximaci´ on Polinomial o Estimaci´ on de Puntos La idea b´asica de los m´etodos de estimaci´ on de puntos es que si la funci´on es suficientemente “suave”, entonces puede ser aproximada mediante un polinomio, y dicho polinomio puede entonces usarse para predecir la ubicaci´ on del ´ optimo. Para que esta estrategia sea efectiva, es necesario que la funci´ on a optimizarse sea tanto unimodal como continua.

Clase No. 3

2009

Optimizaci´ on en Ingenier´ıa

Dr. Carlos A. Coello Coello

M´ etodos de Aproximaci´ on Polinomial o Estimaci´ on de Puntos El teorema de la aproximaci´ on de Weierstrass garantiza que, si la funci´on es continua en el intervalo considerado, entonces ´esta puede ser aproximada con la precisi´ on deseada usando polinomios de un orden suficientemente alto. Consecuentemente, si la funci´ on es unimodal y se cuenta con un polinomio que la aproxime razonablemente bien, entonces la ubicaci´ on del ´ optimo puede predecirse razonablemente bien usando el polinomio en cuesti´ on.

Clase No. 3

2009

Optimizaci´ on en Ingenier´ıa

Dr. Carlos A. Coello Coello

M´ etodos de Aproximaci´ on Polinomial o Estimaci´ on de Puntos El teorema de Weierstrass tambi´en sugiere que se puede mejorar nuestra aproximaci´ on del ´ optimo usando polinomios de aproximaci´on mediante alguno de los 2 mecanismos siguientes: 1.

Usando un polinomio de mayor orden, o

2.

Reduciendo el intervalo sobre el cual se aproximar´ a el ´ optimo de la funci´on.

Clase No. 3

2009

Optimizaci´ on en Ingenier´ıa

Dr. Carlos A. Coello Coello

M´ etodos de Aproximaci´ on Polinomial o Estimaci´ on de Puntos De entre estas 2 opciones, suele preferirse la segunda, porque el ´algebra de los polinomios de un orden superior a tres se complica bastante y, debido a la premisa de unimodalidad, la reducci´ on de intervalos es mucho m´ as f´ acil de realizarse.

Clase No. 3

2009

Optimizaci´ on en Ingenier´ıa

Dr. Carlos A. Coello Coello

M´ etodos de Estimaci´ on Cuadr´ atica El m´etodo de interpolaci´ on lineal m´ as simple es la aproximaci´ on cuadr´atica. Se basa en la observaci´ on de que si una funci´ on alcanza su m´ınimo en el interior de un intervalo, entonces debe ser al menos cuadr´atica. Si es lineal, se supondr´ a que su ´ optimo se encuentra en alguno de los extremos del intervalo. Por tanto, un esquema de estimaci´ on cuadr´atica presupone que, dentro del intervalo dado, la funci´on puede ser aproximada mediante una cuadr´ atica y dicha aproximaci´on mejorar´ a conforme los puntos utilizados para construir la aproximaci´ on se acercan al m´ınimo real.

Clase No. 3

2009

Optimizaci´ on en Ingenier´ıa

Dr. Carlos A. Coello Coello

M´ etodo de las Estimaciones Cuadr´ aticas Sucesivas Este algoritmo fue propuesto por Powell (1964) y usa la b´ usqueda cuadr´atica de manera iterativa para estimar el ´ optimo de una funci´on. El algoritmo comienza con tres puntos x1 , x2 y x3 , como la b´ usqueda cuadr´atica vista previamente. Esto es porque cualquier funci´on cuadr´atica puede ser definida usando tres puntos.

Clase No. 3

2009

Optimizaci´ on en Ingenier´ıa

Dr. Carlos A. Coello Coello

M´ etodo de las Estimaciones Cuadr´ aticas Sucesivas

Clase No. 3

2009

Optimizaci´ on en Ingenier´ıa

Dr. Carlos A. Coello Coello

M´ etodo de las Estimaciones Cuadr´ aticas Sucesivas El m´ınimo de la curva (¯ x) se usa como uno de los puntos candidatos para la siguiente iteraci´ on. Para funciones no cuadr´ aticas, el algoritmo requiere varias iteraciones, mientras que para funciones cuadr´aticas el m´ınimo exacto puede obtenerse con s´ olo una iteraci´ on.

Clase No. 3

2009

Optimizaci´ on en Ingenier´ıa

Dr. Carlos A. Coello Coello

M´ etodo de las Estimaciones Cuadr´ aticas Sucesivas El m´etodo de Powell consiste en aplicar la b´ usqueda cuadr´ atica usando tres puntos x1 ,x2 y x3 y calcular x ¯. El punto x ¯ es un estimado del m´ınimo de la funci´ on, el cual depende u ´nicamente de los 3 puntos elegidos. De entre los cuatro puntos utilizados por el m´etodo (x1 ,x2 ,x3 y x ¯), se retienen los 3 mejores y se obtiene una nueva funci´ on interpolada q(x). El procedimiento contin´ ua hasta que dos estimaciones consecutivas se encuentran muy cerca entre s´ı.

Clase No. 3

2009

Optimizaci´ on en Ingenier´ıa

Dr. Carlos A. Coello Coello

M´ etodo de las Estimaciones Cuadr´ aticas Sucesivas Algoritmo Paso 1:

Paso 2: Paso 3:

Paso 4:

Clase No. 3

Hacer que x1 sea un punto inicial y ∆ sea el tama˜ no del paso (o incremento). Pedir T OL1 y T OL2. Calcular x2 = x1 + ∆ Evaluar f (x1 ) y f (x2 ) If f (x1 ) > f (x2 ) THEN x3 = x1 + 2∆ ELSE x3 = x1 − ∆. Evaluar f (x3 ). Determinar Fmin =min(f1 , f2 , f3 ) y Xmin es el punto xi que corresponde a Fmin .

2009

Optimizaci´ on en Ingenier´ıa

Dr. Carlos A. Coello Coello

M´ etodo de las Estimaciones Cuadr´ aticas Sucesivas Paso 5: Paso 6:

Paso 7

Clase No. 3

Calcular x ¯ usando x1 , x2 y x3 . ¿Es |Fmin − f (¯ x)| ≤ T OL1 AND |Xmin − x ¯| ≤ T OL2? Si no se cumple, GOTO Paso 7 ELSE el ´ optimo es el mejor de los 4 puntos. TERMINAR Almacenar el mejor punto (Xmin o x ¯) y dos puntos que lo rodeen, si esto es posible. Si no, almacena los 3 mejores puntos Re-etiquetarlos de acuerdo a: x1 < x2 < x3 . GOTO Paso 4.

2009

Optimizaci´ on en Ingenier´ıa

Dr. Carlos A. Coello Coello

M´ etodo de las Estimaciones Cuadr´ aticas Sucesivas Algoritmo Paso 1:

Paso 2: Paso 3:

Paso 4:

Clase No. 3

Hacer que x1 sea un punto inicial y ∆ sea el tama˜ no del paso (o incremento). Pedir T OL1 y T OL2. Calcular x2 = x1 + ∆ Evaluar f (x1 ) y f (x2 ) If f (x1 ) > f (x2 ) THEN x3 = x1 + 2∆ ELSE x3 = x1 − ∆. Evaluar f (x3 ). Determinar Fmin =min(f1 , f2 , f3 ) y Xmin es el punto xi que corresponde a Fmin .

2009

Optimizaci´ on en Ingenier´ıa

Dr. Carlos A. Coello Coello

M´ etodo de las Estimaciones Cuadr´ aticas Sucesivas Paso 5: Paso 6:

Paso 7

Clase No. 3

Calcular x ¯ usando x1 , x2 y x3 . ¿Es |Fmin − f (¯ x)| ≤ T OL1 AND |Xmin − x ¯| ≤ T OL2? Si no se cumple, GOTO Paso 7 ELSE el ´ optimo es el mejor de los 4 puntos. TERMINAR Almacenar el mejor punto (Xmin o x ¯) y dos puntos que lo rodeen, si esto es posible. Si no, almacena los 3 mejores puntos Re-etiquetarlos de acuerdo a: x1 < x2 < x3 . GOTO Paso 4.

2009