Download Computacion Bio-Inspirada

Computación Bio-Inspirada
Ing. Fabio A. González PhD
Depto. de Ing. de Sistemas e Industrial
Universidad Nacional de Colombia
Departamento de Ing. de Sistemas e Industrial
Algunas restricciones de la
computación actual:
•
•
•
•
•
Frágil
Garbage In --> Garbage Out
No adaptable
No aprende
El software no explota la distribución y
paralelismo del hardware
• Comunicación hombre-máquina no es natural
• La naturaleza ha resuelto estos y otros problemas
de manera satisfactoria durante millones de años!
Departamento de Ing. de Sistemas e Industrial
Computación Bioinspirada
• Desarrollo de sistemas artificiales
inspirados por conceptos, principios y
mecanismos propios de sistemas naturales.
• Otros nombres:
– Computación natural
– Computación flexible
– Inteligencia computacional
Departamento de Ing. de Sistemas e Industrial
El proceso de la computación
bioinspirada
Sistema
Natural
QuickTi me™ and a
TIFF ( Uncompressed) decompressor
are needed to see thi s pi ctur e.
Los aviones no aletean las alas!
Otras
ideas, teorías, etc.
Modelo
Abstracto
QuickTime™ and a
TIFF (Uncompressed) decompressor
are needed to see this picture.
Sistema
Artificial
QuickTime™
QuickTime™
and aand a
(Uncompressed)
decompressor
TIFFTIFF
(Uncompressed)
decompressor
are needed
to see
are needed
tothis
seepicture.
this picture.
QuickTime™ and a
TIFF (Uncompressed) decompressor
are needed to see this picture.
Departamento de Ing. de Sistemas e Industrial
Inteligencia Artificial Clásica
• Inteligencia == manipulación de símbolos
• Lógica, algoritmos de búsqueda, sistemas
basados en reglas
• Apogeo durante 70’s y 80’s
– Sistemas expertos
– Proyecto 5 generación
• Desencanto, promesas no cumplidas
• Cuál es el problema?
Departamento de Ing. de Sistemas e Industrial
Computación en la naturaleza
• Pasos lentos, pero extremadamente
paralelos
• Alto porcentaje de errores, pero gran
tolerancia a fallos
• Memoria imperfecta, pero fuerte habilidad
para aprender y adaptarse
Departamento de Ing. de Sistemas e Industrial
Principales áreas de investigación
•
•
•
•
•
•
Neuro-computación
Computación evolutiva
Inteligencia colectiva (de enjambre)
Sistemas inmunológicos artificiales
Vida artificial
Computación molecular
Departamento de Ing. de Sistemas e Industrial
Neuro-computación
• Las Redes Neuronales Artificiales son un
modelo abstracto del sistema nervioso que
exhibe características propias de su
contraparte natural.
Departamento de Ing. de Sistemas e Industrial
Características de los sistemas
neurales
• Altamente distribuidos y paralelos
• Computación rápida y fiable a partir de
elementos lentos y no fiables
• Tolerante al ruido
• Tolerante a fallos
• Aprenden
• Apropiados para reconocimiento de
patrones y síntesis funcional
Departamento de Ing. de Sistemas e Industrial
Bases Biológicas
• Se estima que el cerebro humano contiene
más de 1011 neuronas y 1014 sinapsis
• La mayor parte de las neuronas poseen una
estructura de árbol llamadas dendritas que
reciben las señales de entrada que vienen de
otras neuronas a través de la uniones
llamadas sinapsis
Departamento de Ing. de Sistemas e Industrial
Neurona Biológica
• Tres partes principales de
una neurona:
– el cuerpo de la neurona,
– ramas de extensión
llamadas dendritas para
recibir las entradas, y
– un axón que lleva la salida
de la neurona a las dendritas
de otras neuronas
Departamento de Ing. de Sistemas e Industrial
Neurona Artificial (1)
• Wi,j: peso (fortaleza)
de la conexión
(sinapsis)
• i: umbral
• u(.) : Función de
adición
• f(.) : función de
activación
Departamento de Ing. de Sistemas e Industrial
Neurona Artificial (2)
n
ui (W , X )   wij x j
j 1
1 si ui   i
f (ui )  
0 si ui   i
Departamento de Ing. de Sistemas e Industrial
Red Neuronal Artificial
• Es un sistema compuesto
de múltiple unidades
procesadoras (neuronas)
operando en paralelo, cuya
función está determinada
por la estructura de la red,
el peso de las conexiones
y el proceso desempeñado
por cada neurona.
Departamento de Ing. de Sistemas e Industrial
Entrenamiento
• Las redes neuronales no se programan, aprenden a
partir de ejemplos
• El algoritmo de entrenamiento modifica los
diversos parámetros de la red (estructura, pesos,
etc.) basado en un conjunto de patrones.
• Tipos de aprendizaje:
– Supervisado
– No supervisado
Departamento de Ing. de Sistemas e Industrial
Historia breve
•
•
•
•
•
McCulloch-Pitts, 1943: primer modelo de neurona
Hebb, 1949: regla de aprendizaje de Hebb
Rosenblatt, 1958: perceptron
Minsky-Papert, 1969: críticas a los perceptrones
Kohonen, Hopfield, Feldman, 1982: nuevos
modelos de redes neuronales
• McClelland-Rumelhart, 1986: algoritmo de
retropropagación
Departamento de Ing. de Sistemas e Industrial
Aplicaciones
•
•
•
•
Predicción
Control
Robótica
Reconocimiento de patrones:
– Visión artificial
– Reconocimiento del habla
– OCR
•
•
•
•
•
Síntesis del habla
Detección de fraudes
Minería de datos
Procesamiento de señales
Optimización
Departamento de Ing. de Sistemas e Industrial
Computación Evolutiva
• El complejo repertorio de características
exhibidas por los sistemas naturales es fruto
de un proceso evolutivo que se ha
desarrollado durante años.
• La computación evolutiva usa dicho
proceso como inspiración para resolver
problemas de optimización y búsqueda.
Departamento de Ing. de Sistemas e Industrial
Historia Breve (1)
Teoría de la evolución: Charles Darwin. Sobre el orígen de las
especies por medio de la selección natural.
 Pequeños cambios heredables en los seres vivos y la selección
son los dos hechos que provocan el cambio en la naturaleza y la
generación de nuevas especies.
 Darwin pensaba que los rasgos de un ser vivo eran como fluidos
y los “fluidos” de los padres se mezclaban en la descendencia.
Departamento de Ing. de Sistemas e Industrial
Historia Breve (2)
Gregor Mendel
Los caracteres se heredan de forma discreta, y se toman
del padre o de la madre, dependiendo de su carácter
dominante o recesivo.
Los caracteres (genes) pueden tomar diferentes valores
(alelos)
Departamento de Ing. de Sistemas e Industrial
Historia Breve (3)
Walther Flemming (1930)
Descubrió los cromosomas, como ciertos filamentos en los
que se agregaba la cromatina del núcleo celular durante la
división; poco más adelante se descubrió que cada célula
tiene un número fijo y característico de cromosomas.
Watson y Crick (1950)
Descubrieron que la base molecular de los genes está en el
ADN, los cromosomas están compuestos de ADN, por lo
tanto los genes están en los cromosomas.
Departamento de Ing. de Sistemas e Industrial
Lenguaje de la Vida
• Los organismos vivos consisten de células. En cada célula
existe el mismo conjunto de cromosomas
• Cromosomas: cadenas de ADN, modelo del organismo
completo
• Un cromosoma consiste de genes (bloques de ADN)
• Cada gen codifica una proteína particular (rasgo, p.e.,
color de ojos)
• Alelos: Los posibles valores para un rasgo (p.e., azul, café)
• Genoma: conjunto completo de material genético (todos
los cromosomas).
• Genotipo: conjunto particular de genes en un genoma.
• Fenotipo: el genotipo es la base para el fenotipo del
organismo, posterior desarrollo después del nacimiento.
Departamento de Ing. de Sistemas e Industrial
Genotipo y Fenotipo
Departamento de Ing. de Sistemas e Industrial
Evolución Natural
• Resultado de la acción de dos tendencias opuestas
actuando sobre una población de una especie:
– Selección Natural: propensión a adaptarse a un
ambiente dado a través de la preservación del más apto
(“supervivencia del más fuerte”); y
– Variación Genética: propensión a producir variación
para cumplir con los requerimientos del ambiente
(“recombinación sexual + mutación”).
Departamento de Ing. de Sistemas e Industrial
Adaptabilidad en la naturaleza y
en la Computación Evolutiva
decodificación
Genotipo
ambiente
Fenotipo
decodificación
cadenas
(cromosomas)
Adaptabilidad
solución
función
del
objetivo
problema
valor
de la
solución
codificación
Departamento de Ing. de Sistemas e Industrial
Departamento de Ing. de Sistemas e Industrial
Algoritmo Genético
Inicializar
población
Crear descendientes a
través de variación aleatoria
Evaluar la adaptabilidad de
cada solución candidata
Aplicar selección
NO
Terminar
SI
Departamento de Ing. de Sistemas e Industrial
Departamento de Ing. de Sistemas e Industrial
Operadores de Cruce
cruce de un solo punto
cruce de dos puntos
padre 1
padre 2
hijo 1
+
hijo 2
Departamento de Ing. de Sistemas e Industrial
Operadores de Mutación
mutación de un punto
mutación de varios puntos
mutación global
Departamento de Ing. de Sistemas e Industrial
Tipos de Algoritmos Evolutivos
• Algoritmos Genéticos
– optimización de problemas combinatorios
• Estrategias Evolutivas
– optimización de funciones continuas
• Programación Evolutiva
– Máquinas de estado finito
• Programación Genética
– problemas que requieren encontrar la solución a un
problema dado en la forma de una función o programa
Departamento de Ing. de Sistemas e Industrial
Ventajas
• Simplicidad Conceptual.
• Amplia aplicabilidad.
• Superiores a las técnicas tradicionales en muchos
problemas del mundo real.
• Tienen el potencial para incorporar conocimiento sobre el
dominio y para hibridizarse con otras técnicas de
búsqueda/optimización.
• Pueden explotar fácilmente las arquitecturas en paralelo.
• Son robustas a los cambios dinámicos.
• Generalmente pueden auto-adaptar sus parámetros.
• Capaces de resolver problemas para los cuales no se
conoce solución alguna.
Departamento de Ing. de Sistemas e Industrial
Aplicaciones de AEs ...
•
•
•
•
•
•
•
•
•
•
•
•
•
Programación (Scheduling) y Planeación
Diseño VLSI
Diseño en Ingeniería
Predicción Financiera
Minería de Datos
Comportamiento de Robots
Aprendizaje de Máquina
Toma de Decisiones
Aplicaciones Financieras
Diseño de Sistemas de Control
Identificación de Sistemas
Compresión de Imágenes
Sistemas de Vida Artificial
Departamento de Ing. de Sistemas e Industrial
Inyector de 2 fases
QuickTime™ and a
YUV420 codec decompressor
are needed to see this picture.
Departamento de Ing. de Sistemas e Industrial
Función Objetivo Dinámica
QuickTime™ and a
YUV420 codec decompressor
are needed to see this picture.
Departamento de Ing. de Sistemas e Industrial
Evolución de Criaturas Virtuales
QuickTime™ and a
YUV420 codec decompressor
are needed to see this picture.
Departamento de Ing. de Sistemas e Industrial
Inteligencia Colectiva
• La inteligencia colectiva o de enjambre (Swarm
Intelligence) es la propiedad de un sistema que
permite que el comportamiento colectivo agentes
(simples) que interactúan localmente con su
ambiente permita la emergencia global de patrones
funcionales coherentes.
• La inteligencia colectiva provee una base con la
cual es posible explorar la solución de problemas
colectivamente sin un control centralizado y sin la
provisión de un modelo global.
Departamento de Ing. de Sistemas e Industrial
Comportamiento Colectivo en
Colonias de Hormigas (1)
• Lasius Niger (hormigas):
– Regulación de temperatura en el rango de
1 grado
– Formación de puentes
– Incursión organizada de áreas específicas
para buscar comida
– Construcción y protección del nido
– Organización de crías y comida
– Cooperación para cargar objetos grandes
– Emigración de la colonia
– Encuentran la ruta más corta del nido a la
fuente de alimento
– Explotan de manera preferencial la fuente
de alimento más rica
QuickTime™ and a
TIFF (Uncompressed) decompressor
are needed to see this picture.
Departamento de Ing. de Sistemas e Industrial
Comportamiento Colectivo en
Colonias de Hormigas (2)
• El comportamiento de las hormigas
(individualmente) es poco sofisticado, pero
colectivamente desempeñan tareas muy complejas.
• Estigmergia: comunicación indirecta a través de la
interacción con el ambiente.
• Las hormigas han desarrollado una sofisticada
estigmergia:
– se comunican usando feromonas,
– las feromonas trazan caminos que pueden ser seguidos
por otras hormigas.
Departamento de Ing. de Sistemas e Industrial
Caminos de feromonas
• Las hormigas depositan feromonas al desplazarse
• Las feromonas se acumulan cuando múltiples hormigas usan el mismo
camino
• Las feromonas se evaporan
Departamento de Ing. de Sistemas e Industrial
•
Ant Colony Optimization
Simulación de una colonia
 (t) . 

de hormigas enfatizando la p (t) 

comunicación a través de
feromonas.
• Aplicado a problemas de
optimización en redes.
• Conceptos claves:

– Concentración de feromonas
– Reglas para escoger un
camino
– Reglas para cambiar la
concentración de feromonas
k
ij

ij
 
ij

il

(t) .il 
J ik
pijk(t): probabilidad de escoger el
camino (i,j)
ij(t): concentración de feromonas
ij: visibilidad (inverso de la
distancia)
,: parametros que controlan el
balance entre visibilidad y
estimulación feromonal
Departamento de Ing. de Sistemas e Industrial
Aplicaciones
•
•
•
•
•
•
•
Programación de trabajos
Problema del agente viajero
Coloración de grafos
Enrutamiento de vehículos
Alineamiento de secuencias
Enrutamiento en redes
Balanceo de cargas
Departamento de Ing. de Sistemas e Industrial
Particle Swarm Optimization
• Inspirado en el comportamiento social de grupos
de organismos tales como enjambres de abejas,
bancos de peces,
• Es un procedimiento de búsqueda basado en
poblaciones en las cuales los individuos llamados
partículas cambian su posición (estado) con el
tiempo.
• Las partículas se desplazan en un espació
multidimensional ajustando su posición de
acuerdo a su propia experiencia y la de sus
vecinos.
Departamento de Ing. de Sistemas e Industrial
Ejemplos
• Ant Colony Optimization
• Floys
Departamento de Ing. de Sistemas e Industrial
Sistemas Inmunológicos
Artificiales
• Artificial Immune Systems
Departamento de Ing. de Sistemas e Industrial
Investigación en Colombia
• El área es cada vez más conocida.
• Múltiples grupos en diferentes universidades.
• Algunos investigadores colombianos trabajando
en el exterior:
– L'Ecole Polytechnique Fédérale de Lausanne
– The University of Memphis
• Congreso internacional de inteligencia
computacional: CIIC 2001 y 2003
Departamento de Ing. de Sistemas e Industrial
Investigación en la UN
•
•
•
•
•
Grupo de investigación con más de 13 años de trayectoria.
Cerca de 100 trabajos de pregrado y tesis de maestría.
Múltiples publicaciones.
2 Congresos Internacionales en Neuro-Computación (94 y 97).
Investigadores:
– Ing. Alberto Delgado, PhD (redes neuronales, robótica, computación con
ADN)
– Ing. Oscar Duarte, PhD (sistemas flexibles (difusos), computación
evolutiva)
– Ing. Germán Hernández, PhD (computación evolutiva, modelos
probabilísticos)
– Ing. Luis Fdo. Niño, PhD (redes neuronales, sistemas inmunológicos
artificiales)
– Ing. Fabio González, PhD (computación evolutiva, sistemas
inmunológicos artificiales)
Departamento de Ing. de Sistemas e Industrial
Conclusiones
• La computación bio-inspirada surgió en los comienzos mismos de la
computación.
• Ha tenido un renacimiento en los últimos años gracias a:
– Limitaciones en las técnicas convencionales para resolver problemas
complejos.
– Aumento en la capacidad del hardware que hace posible la aplicación
práctica de los algoritmos.
• Interesantes intersecciones entre diversas áreas del conocimiento.
• Las técnicas con más tradición (neurocomputación y computación
evolutiva) se han consolidado.
• Nuevas técnicas se siguen desarrollando y aún quedan muchos
caminos por explorar.
• La masa crítica en el país se está consolidando. Buen momento para
empezar a investigar.
Departamento de Ing. de Sistemas e Industrial
Contacto
• [email protected]
• http://dis.unal.edu.co/~fgonza/
• Laboratorio de Investigación en Sistemas
Inteligentes:
http://dis.unal.edu.co/~sisbio/
Departamento de Ing. de Sistemas e Industrial
Muchas Gracias!!
Departamento de Ing. de Sistemas e Industrial