Análisis de datos y Estadística Avanzadawebs.ucm.es/info/Astrof/POPIA/asignaturas/ana_dat_est… · · 2011-05-18Diseño de aviones y estructuras aeroespaciales para minimizar

Análisis de datos y Estadística AvanzadaMáster Interuniversitario de Astrofísica UCM+UAM

Tema 10: Optimización

Javier Gorgas y Nicolás CardielDepartamento de Astrofísica y Ciencias de la Atmósfera

Facultad de Ciencias Físicas

Universidad Complutense de Madrid

Tema 10: Optimización (♣) Análisis de datos y Estadística Avanzada 1Curso 2010/2011 1 / 65

Esquema1 Introducción

Importancia de la optimización2 Métodos basados en técnicas de cálculo tradicionales

Características generalesCondiciones de optimizaciónOptimización sin restriccionesOptimización con restricciones

3 Otros métodosEnumerative schemesRamdom search algorithmsDownhillAlgoritmos GenéticosNeural NetworksSimulated annealing

4 Un ejemplo astrofísico propioBoundary Fitting


Introducción Importancia de la optimización

Optimización, optimización, optimización,. . .A la Naturaleza (y por tanto el ser humano) le encanta optimizar.

Por ejemplo, el principio de Fermat establece que la luz viaja entre dos puntos

siguiendo la trayectoria que le lleva el menor tiempo posible.

El principio de mínima acción es una idea básica en el desarrollo de la Física y laMatemática modernas.

El ser humano se pasa el tiempo tratando de maximizar elrendimiento (minimizando los costes) en la realización de cualquieractividad.



Optimización para todoLa optimización se aplica a un innumerable número de problemas (ver porejemplo Rao 1996):

Diseño de aviones y estructuras aeroespaciales para minimizar peso

Encontrar trayectoras óptimas de vehículos espaciales

Diseño de estructuras de obras civiles (puentes, torres, chimeneas, presas. . . ) al precio más bajo

Peso mínimo de estructuras resistentes a terremotos y viento

Diseño de reservas de agua para un uso eficiente

Diseño óptimo de estructuras de plástico

Diseño óptimo de engranajes, levas, y todo tipo de componentes mecánicos

Camino más corto pasando por una serie de puntos

Planificación de una producción óptima

Análisis de datos estadísticos y construcción de modelos a partir de datos experimentales para obtener larepresentación más realista de un fenómeno físico

Control de los tiempos de espera en una línea de producción para minimizar costes

Planificación de la mejor etrategia para obtener el máximo beneficio en presencia de competidores

Diseño óptimo de sistemas de control

. . .



¿Qué entendemos por optimización en ciencia?

Optimización ≡

Minimizar

oMaximizar

De forma práctica, en investigación nosvamos a encontrar con la necesidad deminimizar o maximizar una determi-nada función dependiente de una seriede parámetros, sobre los cuales puedenexistir restricciones.

La optimización, también llamada programación matemática, cae en el ámbito dela matemática aplicada. El término programación se debe a causas históricas y noestá relacionado con la programación computacional, aunque en la actualidad todaslas técnicas de optimización se llevan a cabo con ordenadores.


Métodos basados en técnicas de cálculo tradicionales Características generales

¿Minimizar o maximizar?En principio da lo mismo minimizar que maximizar dado que

máximo{f (x)} = −mínimo{−f (x)}

Por convenio suele hablarse de minimización y por ello la función a minimizar recibemuchas veces el nombre de función objetivo o de coste.



La importancia de las restriccionesEn general nos encontraremos con las siguientes opciones

1 Minimización sin restricciones (unconstrained minimization)

minimizar f (x)x∈Rn

donde f : Rn −→ R.2 Minimización con restricciones de igualdad (equality constrained minimization)


, con las restricciones c(x) = 0

donde c : Rn −→ Rm, con m ≤ n.3 Minimización con restricciones de desigualdad (inequality constrained

minimization)


, con las restricciones c(x) ≥ 0

donde c : Rn −→ Rm, y m puede ser mayor que n.4 Minimización con restricciones de igualdad y de desigualdad.



Un ejemplo sencilloEncontrar el mínimo de la función

f (x1, x2) = (x1 − 2)2 + (x2 − 1)2

con las restricciones�

x21 − x2 ≤ 0

x1 + x2 ≤ 2

Usando la notación anterior, podemos reescribir el problema como:Encontrar el mínimo de f (x) = (x1 − 2)2 + (x2 − 1)2, donde x ∈ R2, esdecir,

x =

�x1x2

�

y las restricciones pueden escribirse como

c(x) =

�−x

21 + x2

−x1 − x2 + 2

�≥

�00

�



Encontrar el mínimo de f (x) = (x1 − 2)2 + (x2 − 1)2, con las restricciones

c(x) =

„−x

21 + x2

−x1 − x2 + 2

«≥

„00

«

Las restricciones indican qué regiones son posibles (en blanco) e imposibles (som-breadas) en el cálculo de la solución del problema.



Evitando las restriccionesConsideremos una función objetivo f (x) con x ∈ Rn que pretendemosminimizar imponiendo una serie de restricciones. Podemos escribiresta función como

f (x1, x2, . . . , xi−1, xi, xi+1, . . . , xn).

En algunos casos es posible eliminar las restricciones y convertir elproblema en otro más sencillo sin restricciones. Hay dos opcionesbásicas:

Realizar un cambio de variable para restricciones de desigualdad,haciendo que una variable acotada xi pueda expresarse comouna variable no restringida.Para restricciones de igualdad, se puede tratar de despejaralguna de las variables xi (si es posible) en función del resto.



Eliminando restricciones de desigualdad1 Si alguna de las variables está restringida a un intervalo

xi,min ≤ xi ≤ xi,max,

puede realizarse un cambio de variable tal que

xi = xi,min + (xi,max − xi,min) sin2yi

De esta forma

f (x1, x2, . . . , xi−1, xi, xi+1, . . . , xn) ← con restricción en xi

se convierte en

f (x1, x2, . . . , xi−1, yi, xi+1, . . . , xn) ← sin restricción en xi

2 Si xi está restringida al intervalo (0,1), puede utilizarse:

xi = sin2yi, xi = cos2

yi

xi =e

yi

eyi + e−yi

, xi =y

2i

1 + y2i



Eliminando restricciones de desigualdad3 Si xi debe tomar sólamente valores positivos:

xi = |yi|, xi = y2i, xi = e

yi

4 Si xi toma valores únicamente entre −1 y +1:

xi = sin yi, xi = cos yi, xi =2yi

1 + y2i

Advertencias:

Para poder ser eliminadas, en general las restricciones deben ser sencillas.

Para algunas restricciones de desigualad puede no ser posible encontrar latransformación deseada

Si no es posible eliminar todas las restricciones mediante cambio de variable, esmejor no utilizar ninguna transformación. Una transformación parcial puedeproducir una función objetivo distorsionada que puede ser mucho más difícil deminimizar que la función original.



Eliminando restricciones de igualdadDada una restricción de igualdad del tipo

c(x) = 0, con x ∈ Rn

podemos reescribir esta restricción como

c(x1, x2, . . . , xi−1, xi, xi+1, . . . , xn) = 0

Imaginemos que de la expresión anterior es posible despejar lavariable xi de forma que

xi = v(x1, x2, . . . , xi−1, xi+1, . . . , xn).

Entonces es inmediato ver que introduciendo esta función v en larestricción, tenemos una función que no depende de xi

c(x1, x2, . . . , xi−1, v(x1, x2, . . . , xi−1, xi+1, . . . , xn), xi+1, . . . , xn) = 0



Encontrar el mínimo de f (x) = (x1 − 2)2 + (x2 − 1)2, con la restricción

c(x) = −x1 − x2 + 2 = 0

La restricción es la ecuación de la recta x2 = 2− x1. El mínimo se encontrará ahorasobre dicha recta. Para calcularlo, despejamos x2 de la restricción (ya lo hemos hechoal escribir la ecuación de la recta) y sustituimos en la función

f (x1, x2) = (x1 − 2)2 + (x2 − 1)2 = · · · = 2x21 − 6x1 + 5 ≡ f (x1),

cuyo mínimo se calcula de forma trivial igualando a cero la derivada de la funciónrespecto a la única variable que nos queda, es decir

∂f

∂x1= 4x1 − 6 = 0 ⇒ x1 = 3

2



Cálculo mediante iteracionesDejando de lado casos sencillos, en general los algoritmos de

optimización son iterativos: comienzan con un valor inicial de pruebax0 y van generando una secuencia de estimadores mejorados {xk}∞k=0hasta alcanzar (con suerte) la solución buscada.

La estrategia utilizada para mejorar la solución en cada iteracióndistingue un algoritmo de otro:

Algunos algoritmos utilizan los valores de la función a minimizar,las restricciones y, en algunas ocasiones, los valores de lasderivadas primeras e incluso segundas de dichas funciones.Algunos algoritmos acumulan la información obtenida en lasiteraciones anteriores; otros únicamente se sirven de informaciónlocal obtenida en la iteración actual (en curso).La información se utiliza para conseguir encontrar un nuevo valorxk+1 para el cual la función tenga un valor inferior al que tiene en xk.Existen algunos algoritmos (no monótonos) que no exigen que elvalor de la función disminuya en cada paso, sino al menos al cabode un determinado número de iteraciones: f (xk) < f (xk−m).



¡Advertencia!En general no podremos garantizar que las iteraciones converjanhacia un mínimo global salvo que la función a minimizarobedezca a restricciones importantes.Lo que normalmente sí se trata de garantizar es que el procesoiterativo conduzca a un una sucesión {f (xk)} que converja a cero.



Cualidades de un buen algoritmoUn buen algoritmo debe poseer las siguientes cualidades:

Robusted: los algoritmos deben comportarse bien al serutilizados para resolver una amplia variedad de problemas (dentrode una cierta especialidad) y para todos los valores razonablesiniciales utilizados como arranque de las iteraciones.Eficacia: no deben exigir excesivo tiempo de cómputo nialmacenamiento (memoria).Precisión: deben ser capaces de identificar una solución conprecisión, sin ser especialmente sensibles a errores en los datoso a los errores de redondeo que tienen lugar al serimplementados en un ordenador.

Típicamente este cualidades entran en conflicto: un método rápidamente convergentepuede requerir demasido espacio de almacenamiento; por otro lado los métodos ro-bustos suelen ser los más lentos. Un equilibrio adecuado entre las diferentes cuali-dades es fundamental.


Métodos basados en técnicas de cálculo tradicionales Condiciones de optimización

Recordemos nociones de cálculo básicas. . .Sea la función unidimensional f (x) (con x ∈ R1), continua y derivable almenos dos veces (f ∈ C2), y que contiene un mínimo al menos localen x = x∗ (x∗ no en un borde del intervalo en el que está definida f (x)).

Sabemos desde hace mucho que las condiciones necesarias

para encontrar el mínimo de dicha función unidimensional (sinintroducir restricciones) son:1) f

�(x∗) = 0 ← condición de primer orden2) f

��(x∗) ≥ 0 ← condición de segundo ordenNota: la condición 2) no garantiza que sea un mínimo (ver porejemplo f (x) = x

3 en x = 0).Las condiciones suficientes son:1) f

�(x∗) = 02) f

��(x∗) > 0 ← extrictamente positiva

Las condiciones necesarias sirven para poder rechazar puntos que no son mínimos válidos; lascondiciones suficientes sirven para garantizar que el valor encontrado sí es un mínimo válido.



Recordemos nociones de cálculo básicas. . .Bajo la presencia de restricciones (de igualdad), también aprendimosen su día a tener en cuenta dichas restricciones mediante la utilizaciónde la técnica de los multiplicadores de Lagrange.

Dicha técnica establece que dada, por ejemplo, la necesidad deencontrar los valores extremos de una función f (x1, x2, x3) sujeta a unarestricción de la forma φ(x1, x2, x3) = 0, dichos valores extremospueden calcularse a partir de la anulación de las derivadas parciales(con respecto a x1, x2 y x3) de la función

f (x1, x2, x3) + λφ(x1, x2, x3),

lo que proporciona 3 ecuaciones con cuatro incógnitas (x1, x2, x3,λ). Lacuarta ecuación la suministra la propia restricción

φ(x1, x2, x3) = 0.

El parámetro λ anterior se conoce con el nombre de multiplicador deLagrange.



NotaciónVeamos algunas definiciones útiles a la hora de estudiar condicionesde optimización de una función f (x) con x ∈ Rn.

Vector gradiente de la función objetivo:

g(x) ≡ �x f (x) =

∂f

∂x1...∂f

∂xn

Matriz Hessiana de la misma función:

H(x) ≡ �xx f (x) =

∂2f

∂x21

∂2f

∂x1∂x2. . . ∂2

f

∂x1∂xn

∂2f

∂x2∂x1

∂2f

∂x22

. . . ∂2f

∂x2∂xn

......

...∂2

f

∂xn∂x1

∂2f

∂x2∂x1. . . ∂2

f

∂x2n



Condiciones de optimización sin restricciones(Ver Gould & Leyffer 2003)

Condiciones necesarias de optimización (de primer y segundoorden):

– Si f ∈ C1 y x∗ es un mínimo local de f (x), entonces:g(x∗) = 0

– Si f ∈ C2 y x∗ es un mínimo local de f (x), entonces:g(x∗) = 0H(x∗) es positiva semi-definida; esto significa�s, H(x∗)s� ≥ 0 ∀s ∈ Rn.

Condiciones suficientes de optimización:– Si f ∈ C2 y x∗ satisface g(x∗) = 0, x∗ es un mínimo local aislado si

H(x∗) es definida positiva; es decir �s, H(x∗)s� > 0 ∀s �= 0 ∈ Rn.

Para el caso de restricciones (de igualdad y de desigualdad) existen condiciones análogas en lasque aparecen condiciones adicionales que involucran el gradiente de las restricciones, �x c(x),así como un vector de multiplicadores de Lagrange. Ver detalles, por ejemplo en Gould & Leyffer(2003), o en Gill et al. (2007).


Métodos basados en técnicas de cálculo tradicionales Optimización sin restricciones

Dos estrategias básicasEn el caso de la optimización sin restricciones, hay dos estrategiasfundamentales para el cálculo de mínimos de funciones:

1 Line search strategy: dado un valor xk, primero se calcula a partir de dicho puntouna dirección particular pk, exigiéndose que en dicha dirección se produzca unadisminución de la función,

�pk, g(xk)� < 0 si g(xk) �= 0

En segundo lugar, se elige un paso de longitud αk > 0 tal que

f (xk + αkpk) < f (xk) ← ¡es un problema unidimensional!

Finalmente se acepta xk+1 = xk + αkpk.2 Trust region: en este caso se construye un modelo mk de la función alrededor

del punto xk. Como el modelo puede no ser bueno lejos de xk, se restringe suextensión a una cierta distancia. Posteriormente se determina, dentro de dicharegión, el valor del paso sk que proporciona el mínimo del modelo. Finalmentese acepta xk+1 = xk + sk.



1) Line search strategy (I)De forma intuitiva, parecería que la mejor dirección para aplicar la estrategia line

search es utilizar pk = −g(xk) (steepest-descent direction). Sin embargo no es in-variante de escala y la convergencia puede llegar a ser muy lenta.

(Gould & Leyffer 2002)



1) Line search strategy (II)Como alternativa al método de la steepest-descent direction resulta útil probar conotras direcciones descendentes. En este sentido, si consideramos una matriz Bk

simétrica, definida positiva, se tiene que una dirección pk que verifique

Bkpk = −g(xk)

es siempre una dirección descendente.

Una posibilidad es seleccionar Bk = H(xk), en cuyo caso la dirección resultante seconoce como la dirección de Newton (y cualquier método que la use se conoce comométodo de Newton). Para poder emplear esta opción es necesario asegurarse queH(xk) es positiva definida.

Por otro lado, cualquier Bk no igual a H(xk), pero que sea suficientemente positivadefinida puede proporcionar una dirección descendente adecuada. En estos casos sehabla de métodos de tipo Newton.






2) Trust-region strategyComo ya se ha indicado, estos modelos se basan en aproximar la función a minimizarpor un modelo. Concentrándonos por ejemplo en un modelo de segundo orden

mk(s) = f (xk) + �s, g(xk)�+12�s, Bks�

La expresión anterior no deja de ser una aproximación a la función mediante un desar-rollo en serie de Taylor.

En este caso el gradiente de mk(s) en s = 0 coincide con el gradiente de f (xk) y, alcontrario de lo que ocurre en los métodos linesearch, Bk = H(xk) siempre se permite.

Finalmente se acepta xk+1 = xk + sx siempre que una fracción razonable de la disminu-ción observada en el modelo f (xk)−mk(sk) se traslade a una disminución de la funciónobjetivo f (xk)− f (xk + sk).




(dotted lines: contours of the original function; solid lines: contours of the trust-region model)


Métodos basados en técnicas de cálculo tradicionales Optimización con restricciones

Una gran variedad de métodos. . .Para el caso de la optimización con restricciones consultar porejemplo Gould & Leyffer (2002), Nocedal & Wright (2006), o Gill et al.(2007).

¡Necesitaríamos un curso dedicado sólo a este tema para poderexaminar las técnicas más habituales!

Casos especialesConviene resaltar algunos tipos de problemas en los que se verificanalgunas propiedades especiales que simplifican el trabajo:

Linear programming: se concentra en problemas en los que lafunción objetivo y todas las restricciones son funciones lineales.Quadratic programming: en este caso, aunque las restriccionessiguen siendo lineales, se permite que la función objetivo tengaforma cuadrática.



Un ejemplo clásico de programación cuadráticaSandra M. Faber publicó en 1972 un artículo titulado Quadratic

Programming Applied to the Problem of Galaxy Population Synthesis.

Q =JX

j=1

Wj(1−X

k

xklkj/Lj)2 ← función objetivo cuadrática

Lj luminosidad de la galaxia en el filtro j

xk número de estrellas de tipo k

lkj luminosidad de las estrellas tipo k en el filtro j

J número total de filtros

A esta función se le incorporan restricciones del tipo1 C1 ≤ xn/xn� ≤ C2 ← relación entre número de estrellas de diferentes tipos2 C3 ≤ xnlnj/

Pk

xklkj ≤ C4 ← contribución a la luz en el filtro j

3 R1 ≤ (P

kxkmk/m⊙)/(

Pk

xklkj/l⊙j) ≤ R2 ← relación M/L en el filtro j

donde C1, C2, C3, C4, R1 y R2 son constantes positivas.



Derecha: Galaxias ordenadas porcolor: el grupo 1 contiene los objetosmás azules y menos luminosos, mien-tras que el grupo 5 contiene galaxias Egigantes muy rojas.

Abajo: Número de estrellas de cadatipo obtenidas tras minimizar la funciónobjetivo Q con las restricciones corres-pondientes.


Otros métodos Enumerative schemes

Enumerative Schemes o el uso de la fuerza brutaSin lugar a dudas, los esquemas enumerativos constituyen la formamás simple de buscar el mínimo de una función.

El método consiste en tratar de definir un conjunto finito de posiblessoluciones (discretizando por ejemplo el espacio de parámetros hastauna cierta resolución) y recorrer todos los valores posibles.

Obviamente este tipo de métodos no son operativos cuando ladimensión del espacio de parámetros a explorar es muy grande.


Otros métodos Ramdom search algorithms

Random search algorithmsEn cierta forma pueden contemplarse como una variante de losenumerative schemes, dado que también se explora un conjunto desoluciones discretizadas.

En este caso, en lugar de seguir un procedimiento secuencial en labúsqueda de la solución, se permite saltar aleatoriamente de un puntoa otro del espacio de parámetros. En el caso de funcionesrelativamente sencillas, esto puede conducir a una reducciónimportante del tiempo de cálculo (en comparación con un algoritmoenumerativo). Sin embargo, para funciones complicadas el número deiteraciones puede resultar comparable.


Otros métodos Downhill

The downhill simplex methodMétodo presentado por Nelder & Mead (1965). Ver descripción (y código) en NumericalRecipes (Press et al. 2007).

Características básicas:

Este es un método basado en la utilización exclusiva de los valores de la funciónobjetivo y no de sus derivadas.

No es muy eficiente en términos de número de evaluaciones de la funciónobjetivo. Pero con los modernos ordenadores esto no suele ser un problema.

Posiblemente uno de los mejores métodos cuando la función objetivo norequiere para su evaluación un esfuerzo excesivo.

El método necesita como valor inicial no un único punto, sino un simplex (figurageométrica que en N dimensiones posee N + 1 vértices) no degenerado (queencierre un volumen interno N-dimensional no nulo).

El método procede por pasos, modificando siempre el vértice cuyo valor de lafunción objetivo sea el peor (más alto).

Una vez encontrado un mínimo conviene reiniciar el proceso alrededor de dichopunto para garantizar el resultado.


Otros métodos Downhill


Otros métodos Algoritmos Genéticos

La Naturaleza nos ha demostrado que saber optimizar. . .

¡Aprendamos de ella!



¿En qué son diferentes los Algoritmos Genéticos1 Los Algoritmos Genéticos trabajan con una codificación (e.g.

binaria) de los parámetros buscados y no con los parámetroscomo tales.

2 Los Algoritmos Genéticos realizan la búsqueda partiendo de unapoblación de puntos y no de un punto individual.

3 Los Algoritmos Genéticos utilizan los valores de la función aminimizar pero no el valor de sus derivadas (en este aspecto sonsólo diferentes de algunos algoritmos clásicos).

4 Los Algoritmos Genéticos utilizan reglas de transiciónprobabilísticas.

Hay que resaltar que, aunque los Algoritmos Genéticos hacen uso de reglas proba-bilísticas, no son una búsqueda a ciegas y constituyen una técnica muy diferente delas búsquedas puramente aleatorias. Los Algoritmos Genéticos emplean el azar comouna forma de guiar una búsqueda exhaustiva a través de una codificación del espaciode parámetros.



Pasos fundamentales de un Algoritmo Genético: codificación

Consideremos un caso muy sencillo: queremos encontrar el máximode la función y = x

2 en el intervalo x ∈ [0, 31].

Codificación: x −→ b4b3b2b1b0

El valor decimal de x =

Nbits−1X

i=0

bi × 2i

Lo primero que se realiza es una codificación de los parámetros de lafunción. En este caso sólo hay un parámetro, x, cuyos posibles valoresvamos a considerarlos enteros entre 0 y 31. Estos 32 valores puedencodificarse de forma trivial con 5 bits de 0’s y 1’s:0=00000, 1=00001, 2=00010,. . . , 13=01101,. . . , 31=11111.



Pasos fundamentales de un Algoritmo Genético: generación

población inicial

El siguiente paso es generar una población inicial. En el ejemploconsiderado vamos a utilizar una población de 4 individuos. Lapoblación inicial se determina de forma aleatoria:4 individuos × 5 bits/individuo = 20 elecciones aleatorias de 0’s y 1’s

Población inicial01101110000100010011



Pasos fundamentales de un Algoritmo Genético: evolución de

la población

Una vez establecida una población de un tamaño determinado,estamos en condiciones de proceder con las operaciones quecaracterizan su evolución:

1 Reproducción: las cadenas son copiadas, siendo más probablesaquellas con un valor mayor de la función a maximizar.

2 Cruce: las cadenas se emparejan, generando dos nuevascadenas con el código intercambiado de forma parcial.

3 Mutación: cambio ocasional (baja probabilidad) de algún valor enla cadena, con el objetivo de recuperar posibles solucionesperdidas en la población existente.



Para cada individuo de la población puede calcularse la función a maximizar(Fitness). Una vez determinados estos números para toda la población secalcula su suma (1170 en el ejemplo). Finalmente puede escribirse la fracciónde Fitness (% of Total) asociada a cada individuo.

No. String Fitness % of Total

1 01101 169 14.42 11000 576 49.23 01000 64 5.54 10011 361 30.9Total 1170 100.0

1 Reproducción: utilizando los valores de % of Total, se seleccionan alazar miembros de la población inicial para generar una población dehijos con el mismo número de individuos. Los individuos con mayorvalor de % of Total tienen mayor probabilidad de ser seleccionados.



2 Cruce: De la población hija se seleccionan al azar dos individuos paraser cruzados. Se selecciona, también al azar una posición de la lista debits (número entero k entre 1 y l− 1, donde l es la longitud en númerode bits de las cadenas; en el ejemplo l = 5). Finalmente se intercambianlas cadenas ubicadas entre la posición k + 1 y l.

Por ejemplo, para k = 4, considerando los dos primeros individuos denuestra población, antes del cruce tenemos0 1 1 0 | 1

1 1 0 0 | 0

y después del cruce0 1 1 0 0

1 1 0 0 1

3 Mutación: al tener una probabilidad típicamente muy baja (por ejemplo0.001) de forma práctica sucede pocas veces.



Example extracted from Goldberg (1989), chapter 1

No. initial xi Fitness % of Total Expected # times

string fi ≡ f (xi) 100× fi/P

ifi fi/f selected

1 01101 13 169 14.4 0.58 12 11000 24 576 49.2 1.97 23 01000 8 64 5.5 0.22 04 10011 19 361 30.9 1.23 1Sum 1170 100.0 4.00 4.0Average 293 025.0 1.00 1.0Maximum 576 049.2 1.97 2.0

Mating Pool Mate Crossover New xi Fitness

after Reprod. (random) (random) Population fi ≡ f (xi)0110|1 2 4 01100 12 1441100|0 1 4 11001 25 62511|000 4 2 11011 27 72910|011 3 2 10000 16 256

Sum 1754Average 439

Maximum 729

961←− Goal



Can a GA find an English phrase through evolution? (Flake 1998, Chapter 20)

Usemos la frase “sin sentido”: furious green ideas sweat profusely.Longitud: 35 caracteres. Usemos un alfabeto de 26 letras (minúsculas) y 1 espacio en blanco.¿Cuántas cadenas de 35 caracteres podemos formar con un alfabeto de 27 símbolos?

125.236.737.537.878.753.441.860.054.533.045.969.266.612.127.846.243Si hay 280 electrones en el Universo, y éste tiene 10000 millones de años, cada electrón debería realizar 300 millones de inten-tos/segundo de adivinar la solución durante toda la existencia del Universo antes de poder obtener un valor correcto con unaprobabilidad razonable.

Time Average Fitness Best Fitness Best String

0 0.035314 0.200000 pjrmrubynrsksxiidwctxfodkodjjzfunpk1 0.070000 0.257143 pjrmrubynrsksxiidybvswcqo piisyexdt

.

.

....

.

.

....

25 0.708686 0.771429 qurmous gresn idnasvsweqt prifuseky26 0.724286 0.800000 qurmous green idnasvsweqt prifuseky

.

.

....

.

.

....

36 0.806514 0.914286 uurious green idnas sweqt profusely37 0.820857 0.914286 qurmous green ideas sweqt profusely

.

.

....

.

.

....

41 0.895943 0.942857 uurious green idnas sweat profusely42 0.908457 0.971429 qurious green ideas sweat profusely

.

.

....

.

.

....

45 0.927714 0.971429 qurious green ideas sweat profusely46 0.936800 1.000000 furious green ideas sweat profusely



¿Por qué los algoritmos genéticos funcionan?La idea básica es que cada cadena es la plantilla de muchas posiblessoluciones. Por ejemplo, la cadena *111* es la plantilla de las cuatrocadenas 01110, 01111, 11110, 11111. Aunque los cruces decadenas pueden romper estas plantillas (schemata en el argot de losalgoritmos genéticos) cuando son largas, las schemata de tamañomás corto pero altamente adaptadas (elevados valores de la función amaximizar), tienen una elevada probabilidad de sobrevivir.

Un análisis matemático más detallado revela que el número deschemata que se procesan positivamente en cada generacióndepende de n

3, mientras que el número de evaluaciones de la funcióna maximizar es del orden de n. Por tanto, los algoritmos genéticosconstituyen un excelente método para el procesado masivo de

posibilidades en el espacio de soluciones. Esta capacidad seconoce como implicit parallelism.


Otros métodos Neural Networks

¿Dónde reside la inteligencia?

Left: Comparative anatomy of brains from various vertebrate species. University of Wisconsin andMichigan State Comparative Mammalian Brain Collections and the National Museum of Healthand Medicine.Right: Drawing of Purkinje cells (A) and granule cells (B) from pigeon cerebellum by SantiagoRamón y Cajal, 1899; Instituto Santiago Ramón y Cajal, Madrid, Spain.



Las neuronas reciben múltiples señales através de unas uniones llamadas sinapsis,que a su vez se encuentran en los extremosde unas terminaciones de las propias neu-ronas llamadas dendritas.

Cada neurona reune la información querecibe de otras neuronas, procesa dicha in-formación, y genera una salida que viaja através de una extremidad más importante, lla-mada axón, lo que conduce al reenvío de lainformación procesada a otras neuronas.

De manera simplificada, cada neurona com-bina adecuadamente (∼ una suma pesada)la señal recibida, y si la señal combinada su-pera un cierto valor umbral, la neurona dis-para una respuesta.

Con la descripción anterior en mente,podemos representar el funcionamiento es-quemático de una una neurona artificial

como:



Ejemplo de feedforward network. Los valores de entrada llegan a las neuronas ubicadas en la input layer, las cuales se conectancon las neuronas que conforman la(s) hidden layer(s) (puede haber tantas neuronas y hidden layers como se quiera). Finalmentela señal viaja a las neuronas finales, que se encuentran en la output layer.



Cada neurona utiliza una función de activación para decidir si dispara o no una señal a las siguientes neuronas. Dichasfunciones pueden ser muy sencillas, como la función escalera (abajo a la izquierda), o más sofisticada como la función sigmoidal(abajo a la derecha).

La función sigmoidal permite realizar cálculoscon variables continuas. Esta función puedeescribirse como

output = 11+e−S/p

donde S es el valor de activación y p es unparámetro que controla la forma de la curva(típicamente p = 1). Si el valor umbral paradisparar la neurona lo llamamos bias, pode-mos escribir S =

Pxiwi + bias.



Una red neuronal debe ser entrenadaPara que una red neuronal funcione adecuadamente hay que enseñarla. Esto implicadeterminar los valores de los pesos wi que conducen, bajo una señal de entrada de-terminada, a la señal de salida requerida.

Algunas redes neuronales pueden ser programadas explícitamente para querealicen el trabajo para la cual se van a destinar. Sin embargo una red neuronales capaz de aprender.

Durante mucho tiempo, y usando redes neuronales pequeñas, los pesos seajustaban mediante ensayo y error, hasta conseguir la respuesta esperada.

En los años 80 se introdujo la utilización de algoritmos de propagación haciaatrás (back-propagation algorithms) los cuales comparan de forma sistemáticalos resultados obtenidos con los valores utilizados como entrada de la redneuronal. Estos algoritmos consiguen automatizar el proceso de aprendizaje deuna manera sencilla y rápida. Dado un conjunto de datos, puede dividirse lamuestra en dos grupos: uno puede utilizarse para entrenar la red neuronal y otropuede emplearse para comprobar que se generan los resultados esperados.

Algunas veces las redes neuronales consiguen configurarse para resolverproblemas para los que no fueron intencionadamente entrenadas.


Otros métodos Simulated annealing

Simulated annealing: Analogía con la termodinámicaLa idea básica detrás de este método está basada en la manera en la que los líquidos,al irse enfriando lentamente, se congelan permitiendo una distribución cristalina desus átomos que puede llegar a alcanzar dimensiones de miles de millones de veces eltamaño de los propios átomos. Estas configuraciones cristalinas constituyen el estadode mínima energía para el sistema.

En la Naturaleza un sistema en equilibrio térmico a una temperatura T tiene susniveles energéticos distribuidos en diferentes estados E, siguiendo la llamadadistribución de probabilidad de Boltzmann, Prob(E) ∼ exp(−E/kT), donde k esla constante de Boltzmann.

Esta idea puede trasladarse a la búsqueda de mínimos de problemascombinatorios (como el problema del viajante), en los que la función objetivo sedefine en un espacio discreto, aunque muy grande. También puede extendersesu uso para funciones objetivo definidas sobre variables continuas.

De forma práctica es necesario definir un análogo de la temperatura y unesquema temporal de enfriamiento que defina cómo la temperatura pasa de unvalor alto a un valor bajo.


Otros métodos Simulated annealing

El problema del viajante

Figura extraída de Numerical Recipes (Press etal. 2007). Ejemplo de aplicación del métodosimulated annealing introduciendo un factor depenalización por atravesar un río (línea vertical).Panel (a) sin penalización. Panel (b) con pena-lización. Panel (c) con penalización negativa.


Un ejemplo astrofísico propio Boundary Fitting

En el artículo Cardiel (2009) se presentó el ajuste de “fronteras”superiores e inferiores de datos, usando una generalización delmétodo de mínimos cuadrados.


Un ejemplo astrofísico propio Boundary Fitting

Referencias

Cardiel N., 2009, Monthly Notices of the Royal Astronomical Society, 396, 680

Faber S.M., 1972, Astronomy & Astrophysics, 20, 361

Flake G.W., 1998, The Computational Beauty of Nature, the MIT Press

Gill P.E., Murray W., Wright M.H., 2007, Practical Optimization, Emerald, Elsevier Academic Press

Goldberg D.E., 1989, Genetic Algorithms in Search, Optimization, and Machine Learning, Addison-Wesley PublishingCompany, Inc.

Gould N.I.M., Leyffer S., 2002, An introduction to algorithms for nonlinear optimization,http://www.numerical.rl.ac.uk/nimg/msc/lectures/paper.pdf

Nelder J.A., Mead R., 1965, Computer Journal, 7, 308

Nocedal J., Wright S.J., 2006, Numerical Optimization, 2nd Edition. Springer.

Press W.H., Teukolsky S.A., Vetterling W.T., Flannery B.P., 2007, Numerical Recipes, 3rd edition, Cambridge UniversityPress

Rao S.S., 1996, Engineering Optimization. Theory and Practice, 3rd Edition, Wiley-Intersience Publication

Whitley D., 1994, A Genetic Algorithm Tutorial, Statistics & Computing (4), 65-85; consultar esta y otras publicacionesrelacionadas en: http://www.cs.colostate.edu/~genitor/Pubs.html

Información sobre redes neuronales, algoritmos genéticos y más cosas en:http://www.ai-junkie.com/


Documents

Análisis de datos y Estadística Avanzadawebs.ucm.es/info/Astrof/POPIA/asignaturas/ana_dat_est… · · 2011-05-18Diseño de aviones y estructuras aeroespaciales para minimizar