Optimización inspirada en la...

Optimización inspirada en la naturaleza

Efrén Mezura-Montes Laboratorio Nacional de Informática Avanzada (LANIA AC)

Xalapa, Veracruz, MEXICOemezura@lania.mx

http://www.lania.mx/~emezura

10ª feria de Posgrados CONACyTJunio, 2009

Agenda

1. La demanda del mundo real2. Heurísticas inspiradas en la naturaleza3. Aplicaciones

1. La demanda del mundo real1. La demanda del mundo real

Un ejemplo

� Diseño de una pieza tubular� Variables

� Largo (l)� Diámetro (d)� Diámetro (d)� Grosor (g)

� Condiciones

� Objetivo� Minimizar el peso

cm5cm1

cm50cm10

cm1000cm100

≤≤≤≤≤≤

g

d

l

32

35.02

),,( gld

gdlf +

= π

¿Cómo solucionarlo?

� Probar combinaciones� l=100, d=10, g=1� l=100, d=10, g=2� l=100, d=10, g=3

32

35.02

),,( gld

gdlf +

= π

� l=100, d=10, g=3� l=100, d=10, g=4� l=100, d=10, g=5� .� .� .

35.02

),,( glgdlf +

= π

¿Cuántas soluciones hay?

� Sol. de “l” X Sol. de “d” X Sol. de “g” � 901 X 41 X 4 = 147 764 soluciones� Si agregamos 2 decimales de exactitud a cada

solución …

cm5cm1

cm50cm10

cm1000cm100

≤≤≤≤≤≤

g

d

l

solución …� (901 X 102) X (41 X 102) X (4 X 102) = 1.44X 1011

� ≈ 147,764,000,000 soluciones

Los problemas con los problemas del mundo real [Michalewicz. 2004]

� El número de soluciones posibles puede llegar a ser prohibitivo para una búsqueda exhaustiva

� El problema es muy complicado y sólo se pueden utilizar modelos simplificados del mismopueden utilizar modelos simplificados del mismo

� La función objetivo puede variar con respecto al tiempo

� Las soluciones están altamente restringidas

Clasificación de problemas

� Optimización� Optimización paramétrica� Optimización con restricciones� Optimización de estructuras de datos� Optimización de estructuras de datos

� Satisfacción de restricciones� Aprendizaje de Máquina� Programación automática� Optimización dinámica

Técnicas clásicas

� La Investigación de operaciones es la parte de las matemáticas que ofrece y aplica técnicas para resolver problemas de este tipo� Programación lineal� Programación lineal� Programación entera� Programación no lineal� Programación dinámica� Toma de decisiones multicriterio

2. Heurísticas inspiradas en la naturalezanaturaleza

¿Naturalmente inspirados?

� El cómputo inspirado en la naturaleza agrupa un conjunto de algoritmos heurísticos que basan su comportamiento en fenómenos encontrados en la naturaleza. Modelo matemáticola naturaleza.

Imagén tomada de http://www.hormiga.com

Modelo Biológico

Modelo matemático

Imagén tomada de www.ams.jhu.edu/~tucker/ta/

Implementación

¿Qué hay en la naturaleza?

� Mecanismos adaptativos que permiten o facilitan el comportamiento inteligente en ambientes cambiantes y complejos que además son capaces de:

Aprender� Aprender� Adaptarse� Generalizar� Abstraer� Descubrir� Asociar

Algoritmos evolutivos

� Conjunto de heurísticas que basan su funcionamiento en modelar procesos evolutivos fundamentados en la supervivencia de los individuos más aptos en una población.individuos más aptos en una población.

� http://africascience.blogspot.com/2007/07/study-detects-recent-instance-of-human.html

Paradigmas

� Algoritmo Genético [Holland, 1962]� Estrategias Evolutivas [Rechenberg et al., 1963]� Programación Evolutiva [Fogel,1966]

� Programación Genética [Koza, 1989]� Evolución Diferencial [Price, 1995]

Inteligencia en Cúmulos (Swarm Intelligence)

� Conjunto de técnicas basadas en el comportamiento social y cooperativo emergente de organismos agrupados en colonias, parvadas, etc.parvadas, etc.� Optimización mediante cúmulos de partículas� Colonia de hormigas

PSO

� Cada partícula representa una solución al problema

� Las partículas vuelan en el espacio de las solucionessoluciones

� Su vuelo depende de su propia experiencia y de la de sus vecinos

www.webcodeff.cl

Colonia de Hormigas

� Ant Colony [Dorigo et al.,1996]� Modelado del comportamiento de las hormigas

para encontrar el camino más corto hacia fuentes de alimentofuentes de alimento

� Basado en el depósito de feromona� Esta sustancia sirve para comunicar información

de manera indirecta entre las hormigas

Nuevas propuestas

� Glowworm Swarm Optimization (GSO) [Krishnanand and Ghose, 2006]

� Artificial Bee Colony (ABC) [Karaboga and Basturk, 2003]Basturk, 2003]

� Bacterial Foraging Optimization (BFO) [Passino, 2002]

http://www.zin.ru/Animalia/coleoptera/eng/korzhav1.htmhttp://photos-from-my-life.blogspot.com/2006/10/bee-swarm.htmlwww.universityofcalifornia.edu/.../ecoli.html

3. Aplicaciones a problemas del mundo realdel mundo real

Optimización inspirada en la naturaleza en LANIA

• Nuevos modelos• Mecanismos avanzados

Investigación en heurísticas bio-inspiradasbio-inspiradas

• Adaptación/diseño de algoritmos

• CalibraciónAplicaciones

Geometría Computacional

� Problema de triangulación. � Triangulación de peso mínimo� Trangulación de dilación mínima

Problema de estimación de la posición

� Integración GNSS/INS (involucra la combinación de salidas de diferentes sistemas de sensores para obtener una mejor aproximación de la posición)posición)

Aplicaciones en criptografía

� Optimización en cadenas de adición

fi.unizar.es/.../ssue/criptografia.jpg

Mecanismo CVT

� Se optimizó el diseño de este mecanismo de tracción, así como su control automático, planteado como un planteado como un problema de optimización multi-objetivo.

Diseño Estructurado de amplificadores

� Tres fases:� Ruido� Distorsión� Ancho de banda

* Solución ideal

� En las fases de ruido y ancho de banda aparecen problemas de programación no lineal

ruido

Ancho de bandadistorsión

Job-Shop SchedulingPlan de trabajo.

J1

Máquinas

M0

M1

M2 J1

J2

J0

J0

J2

J2 J0

J1

MAKESPAN12

O01 O02 O03

O11 O13 O12

O22 O21 O23

3 3 3

4 3 2

3 2 1

I T

O01 O02 O03

O11 O13 O12

O22 O21 O23

3 3 3

4 3 2

3 2 1

I

Tiempo

M2

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

J1 J2 J0

Registro de imágenes

� t

� t+1

� t+n

El objetivo es saber, a pesar del movimiento en el video, la posición de un píxel en cada frame.

Video sin optimizar Video optimizado

Gracias por su atención

Efrén Mezura MontesEfrén Mezura MontesGrupo de Investigación

en cómputo inspirado en la naturaleza

emezura@lania.mxhttp://www.lania.mx/~emezura