Abraham Otero Quintana
1/75
Inspiraciones biológicas de la ingeniería: aprendiendo lecciones de la
madre naturalezaAbraham Otero Quintana
Abraham Otero Quintana
2/75
1. Introducción
2. Algoritmos genéticos
3. Redes neuronales artificiales
4. Algoritmos bioinspirados
5. Conclusiones
Índice
Abraham Otero Quintana
3/75
• La ciencia a menudo tiene como objetivo estudiar la naturaleza.
– Física, química, biología, astronomía, geología…
• El objetivo suele ser comprender la naturaleza para tomar ventaja de cómo funciona
– Procesos industriales, diseño de nuevos materiales, medios de transporte, predicción de fenómenos metereológicos…
Inspiraciones biológicas de la ingeniería
Abraham Otero Quintana
4/75
• La madre naturaleza ha tenido que “resolver problemas” complejos, y a lo largo de millones de años de evolución ha encontrado soluciones ingeniosas.
• En ocasiones estas soluciones pueden ser aplicables en ingeniería para resolver problemas complejos que, si no pudiésemos copiar a la madre naturaleza, quizás incluso no podríamos resolver.
Inspiraciones biológicas de la ingeniería
Abraham Otero Quintana
5/75
1. Introducción a la inteligencia artificial
2. Algoritmos genéticos
3. Redes neuronales artificiales
4. Algoritmos bioinspirados
5. Conclusiones
Índice
Abraham Otero Quintana
6/115
• Los algoritmos genéticos son programas que “evolucionan”, simulando en cierto grado la selección natural, y alcanzan a resolver problemas complejos que ni siguiera quienes los crearon comprenden.
John H. HollandJohn H. Holland
Algoritmos Genéticos
Abraham Otero Quintana
7/115
• Caracterización del problema:
– Problemas de búsqueda (optimización: clasificación, diseño, juegos, etc.)
– Disponemos de un espacio de soluciones previsiblemente complejo y amplio o de muchas restricciones difíciles de representar matemáticamente.
– Deseamos encontrar la solución, o la mejor de entre todas.
– La búsqueda está guiada por una función objetivo que tratamos de maximizar (juegos) o minimizar (reconocimiento de patrones).
Algoritmos Genéticos
Abraham Otero Quintana
8/115
• Charles Darwin (1859) introduce la teoría de la evolución en el libro “El origen de las especies por medio de la selección natural”.
• Gregor Mendel (1822) descubre que los caracteres se heredan de forma discreta, y les llama genes.
Algoritmos Genéticos
Abraham Otero Quintana
9/115
• Walther Flemming descubre en 1879 los cromosomas.
• Watson y Crick descubren en los años 1950 el ADN.
Algoritmos Genéticos
Abraham Otero Quintana
10/115
• Existen dos tipos de mecanismos que condicionan la evolución de una especie:
– Mecanismos de disminución de variabilidad:
1. Selección natural.
2. Deriva genética.
– Mecanismos de aumento de la variabilidad:
1. Mutación.
2. Poliploidía.
3. Recombinación.
4. Flujo genético.
Algoritmos Genéticos
Abraham Otero Quintana
11/115
• Los algoritmos genéticos fueron propuestos por Holland en 1970.
• Son métodos sistemáticos para la resolución de problemas de búsqueda y optimización.
• Es decir, hallar una solución S={x1,x2,...,xn} tal que F(x1,x2,...,xn) sea máximo o mínimo (según). {x1,x2,...,xn} se codifican en un cromosoma.
• Aplican métodos análogos a los de la evolución biológica: selección, reproducción sexual y mutación.
Algoritmos Genéticos
Abraham Otero Quintana
12/115
• Codificación: cada individuo (cadena) codifica un conjunto de genes (parámetros) en bloques de código.– Se puede demostrar que la codificación sobre la que actúan mejor los algoritmos genéticos es aquella que emplea un
alfabeto de tamaño dos.
1 0 1 1 0 0 1 0 1 0 0 0 1 1 1 0 1 1 0 0 0
Gen 1 Gen 2 Gen 2 Gen 3 Gen 4
Algoritmos Genéticos
Abraham Otero Quintana
13/115
100101001110011100011101
111001101001110110111110
100101001
111001101
00111
11001
100101001110011100011101
111001101001110110111110
Recombinación de 1 punto
Recombinación de 2 puntos
100101001110
111001101001
110110111110
011100011101
1100011101
0110111110
Algoritmos Genéticos
• Recombinación: se define como el intercambio de subcadenas entre individuos.
• Se habla de recombinación de n-puntos, siendo n el número de puntos de corte.
Abraham Otero Quintana
14/115
• Mutación: se define como la variación en uno o más elementos del código de un individuo.
• Es necesario establecer previamente una frecuencia de mutación. Por ejemplo, uno por mil.
111001101001110110111110
mutación
11100110101 1110110111110
Algoritmos Genéticos
Abraham Otero Quintana
15/115
1. Cada individuo se evalúa según la función objetivo.
2. Las que logran mayor puntuación se aparean entre sí, mediante recombinación.
3. Tiene lugar una mutación en una fracción pequeña de la población, con el fin de que no se dé una población
uniforme.
4. Es necesario un criterio de finalización.
Algoritmos Genéticos
Abraham Otero Quintana
16/115
POBLACIÓN INICIAL
0011101101111101001
1110110101101001000
0000111101101101110
0010010001101001100
01010101001011010110’10
0’60
0’60
0’50
0’45
0’30
0’25
0’20
0111111101101011010
1010101101101100011
APAREAMIENTO
X
X
X
X
0011101101111101001
0111111101101011010
1010101101101100011
1100001101101011111 1100001101101011111
POBLACIÓN RESULTANTE
1010101101101011010
0111111101101100011
1100001101101011111
0’60 1010101101101100011
01111111011010110100’60
0’70
0’60
0011101101111111111
1100001101101001001
0’50
0’50
0’50
0’30
0011101101110101001
mutación
Algoritmos Genéticos
Abraham Otero Quintana
17/115
• Los algoritmos genéticos echan la red sobre el espacio de soluciones.
• Los distintos individuos de la población exploran distintas zonas del espacio de soluciones. Paralelismo.
• Si el problema evoluciona, no es necesario reiniciar la búsqueda. La población constituye un contenedor de conocimiento que puede servir para adaptarse a los cambios.
Algoritmos Genéticos
Abraham Otero Quintana
18/115
• Aplicaciones:
– Control de redes de distribución de gas.
– Control de temperatura de grandes edificios.
– Diseño de turbinas.
– Diseño de redes neuronales.
– Diseño de nuevos fármacos.
– Simulación de ecosistemas. Vida artificial.
– Aprendizaje.
– Minería de datos.
Algoritmos Genéticos
Abraham Otero Quintana
19/115
• Veámoslos en acción: 1D
(http://cs.felk.cvut.cz/~xobitko/ga/)
Algoritmos Genéticos
Abraham Otero Quintana
20/115
• Veámoslos en acción: 3D
(http://cs.felk.cvut.cz/~xobitko/ga/)
Algoritmos Genéticos
Abraham Otero Quintana
21/115
• Veámoslos en acción: problema del viajante
(http://cs.felk.cvut.cz/~xobitko/ga/)
Algoritmos Genéticos
Abraham Otero Quintana
22/115
• Bibliografía:– J. Holland, “Algoritmos genéticos”. Investigación y Ciencia, 192, 38-45,
1992.– D. B. Fogel, “What is evolutionary computation?”. IEEE Spectrum, 26-32,
2000.– C. Z. Janikow y D. St. Clair. “Genetics algorithms. Simulating nature’s
methods of evolving the best design solution”. IEEE Potentials, 31-35, 1995.– D. B. Fogel. “What is evolutionary computation?”. IEEE Spectrum, 26-32,
2000.
Algoritmos Genéticos
Abraham Otero Quintana
23/75
1. Introducción
2. Algoritmos genéticos
3. Redes neuronales artificiales
4. Algoritmos bioinspirados
5. Conclusiones
Índice
Abraham Otero Quintana
24/115
• Cajal describe por primera vez en 1887 los distintos tipos de neuronas.
Estructura de la neurona.
soma
axón
dendritas
Redes Neuronales
Abraham Otero Quintana
• Los contactos entre neuronas se denominan sinapsis, y pueden ser de naturaleza química, eléctrica o mixta.
• En una sinapsis química, la llegada de impulso eléctrico provoca la liberación de neurotransmisores, para los que la dendrita postsináptica posee receptores específicos.
Ejemplo de funcionamiento de una sinapsis química
Redes Neuronales
Abraham Otero Quintana
Redes Neuronales
• La conexión entre dos neuronas puede ser excitadora o inhibidora de la neurona postsináptica.
Abraham Otero Quintana
• La plasticidad neuronal hace referencia a la capacidad del sistema nervioso de remodelar los contactos entre neuronas y la eficiencia de las sinapsis.
Un sistema aprende cuando es capaz de experimentar modificaciones estructurales y/o funcionales que se manifiestan en su comportamiento externo como una mejora en la realización de una tarea.
Redes Neuronales
Abraham Otero Quintana
actividad aferente(entrada)
actividad eferente(salida)
f(θ)
-2
0.2
0.5
PESO
SUMADOR
FUNCIÓNDE
ACTIVACIÓN
• Los pesos constituyen la memoria a largo plazo, y su ajuste corresponde a lo que se denominará aprendizaje.
x1
x2
xn
x1w1
x2w2
xnwn
wixiΣi=1
n
S=f(θ)=1 si
0 en caso contrario
wixi > θΣi=1
n
S
Redes Neuronales
Abraham Otero Quintana
• En el caso más sencillo, la neurona proporciona a la salida un valor de activación o de inhibición.
• Esto se logra mediante la función de activación.
1.0
0.0
t
1.0
0.0
t
función escalón función sigmoide
f f
Redes Neuronales
Abraham Otero Quintana
• Tipos de entrenamiento:
– Supervisado: se le presentan a la red ejemplos de clases diferentes.
– No supervisado: la red neuronal busca una partición adecuada del espacio de entrada.
– Mediante refuerzo: no se le proporciona a la red un conjunto ejemplos, pero sí un refuerzo positivo o negativo según clasifique bien o mal.
Redes Neuronales
Abraham Otero Quintana
• Aplicaciones:– Explotación de datos (data mining).– Evaluación en la concesión de préstamos hipotecarios.– Verificación de firmas en cheques.– Predicción en la evolución de mercados.– Reconocimiento de formas en percepción visual.– Diagnóstico médico.– Reconocimiento óptico de caracteres.– Filtrado en telecomunicaciones.– Predicción de demanda de consumo eléctrico.– Control adaptativo en procesos industriales.
Redes Neuronales
Abraham Otero Quintana
• Aplicación militar: reconocimiento de formas.
Una red de Hopfield memorizó aviones o trozos de aviones serbios y reconoció éste bajo la cola de un avión comercial
Redes Neuronales
Abraham Otero Quintana
34/115
• Veamos algunos ejemplos:– http://www.aispace.org/neural/sample2.html
Redes Neuronales
Abraham Otero Quintana
• J. Freeman y D. Skapura, “Redes neuronales: algoritmos, aplicaciones y técnicas de programación”. Addison Wesley, 1993.
• G. E. Hinton, “Redes neuronales que aprenden de la experiencia”. Investigación y Ciencia, noviembre 1992.
• D. R. Hush y B. Horne, “An overview of neural networks. Part I: static networks”. Informática y Automática, 25(1), 1992.
• S. Russell y P. Norvig, “Inteligencia Artificial. Un enfoque moderno”. Prentice Hall, 1996.
• P. Isasi e I. Galván, “Redes Neuronales Artificiales. Un enfoque práctico”. Prentice Hall, 2004.
Redes Neuronales
Abraham Otero Quintana
36/75
1. Introducción a la inteligencia artificial
2. Redes neuronales artificiales
3. Algoritmos genéticos
4. Algoritmos bioinspirados
5. Conclusiones
Índice
Abraham Otero Quintana
37/75
• Las colonias hormigas, termitas y abejas, entre otras colonias de insectos, constituyen algunos de los sistemas auto-organizados más interesantes.– Administran eficientemente los recursos de la colonia.
– Construyen viviendas complejas.
– Realizan cooperativamente tareas como la búsqueda de alimento, enfrentamiento con enemigos, traslado de objetos, etc.
• … y lo hacen sin un control central y con una comunicación limitada.
• Aparecen comportamientos complicados, coordinados, dirigidos por objetivos a partir de la interacción de múltiples individuos.
Computación Bioinspirada
Abraham Otero Quintana
38/75
• Los investigadores en computación se han inspirado en el comportamiento social de las colonias de insectos para resolver problemas parecidos.
• Se inspiran en los insectos como las RNA se inspiran en la organización del cerebro.
• No por imitar a lo natural se obtiene un buen resultado. Se trata de imitar a lo natural en aquello en lo que lo natural obtiene muy buenos resultados.
Computación Bioinspirada
Abraham Otero Quintana
39/75
• Los algoritmos basados en colonias de hormigas se inspiran en el comportamiento de las hormigas reales.
• Las hormigas resuelven sus problemas mediante la cooperación multiagente y una comunicación basada en la modificación del entorno.
• Cada hormiga libera una hormona llamada feromona.
• Las hormigas prefieren seguir el rastro de las feromonas.
• Eso les permite optimizar las rutas a seguir hasta el alimento.
Computación Bioinspirada
Abraham Otero Quintana
40/75
• Una avanzadilla de hormigas sale en busca de alimento siguiendo direcciones aleatorias.
Computación Bioinspirada
Abraham Otero Quintana
41/75
• Cuando encuentran un obstáculo lo rodean de un modo aleatorio (arriba, abajo, izquierda, derecha).
Computación Bioinspirada
Abraham Otero Quintana
42/75
• El rastro más corto es más intenso en contenido de feromona, y se convierte en preferido.
Computación Bioinspirada
Abraham Otero Quintana
43/75
• Supongamos un sistema basado en una red de comunicaciones (red vial, red telefónica, internet).
• Se desea comunicar los puntos A y B.
A
B
• Hacemos que una avanzadilla de hormigas artificiales recorran la red, dejando menos feromona en los nodos más congestionados.
• Las rutas más congestionadas tienen un rastro más débil y se abandonan progresivamente.
• Puesto que la feromona se evapora, el método se adapta a la situación actual de la red.
Computación Bioinspirada
Abraham Otero Quintana
44/115
• Las hormigas realizan tareas como las de clasificar cadáveres, ordenar la alimentación.
• Estos comportamientos todavía no se conocen bien, pero se pueden modelar mediante comportamientos locales probabilistas:
1. Es más probable recoger un artículo cuando difiere de lo que lo rodea.
2. Es más probable dejar un artículo entre los que se le parecen.
• Podemos resolver nuestros problemas siguiendo esta estrategia.
Computación Bioinspirada
Abraham Otero Quintana
45/115
• Imaginemos que queremos sentar a mucha gente en un banquete. Parece razonable sentar juntos a los conocidos.
• Podemos construir un grafo que representa la relación conocido: une nodos que corresponden a gente que se conoce.
• Ponemos encima del grafo y una colonia de hormigas.1. Cada hormiga recoge un nodo si está rodeado de nodos
desconocidos.
2. Cada hormiga deposita un nodo si está rodeado de nodos conocidos.
Computación Bioinspirada
Abraham Otero Quintana
46/115
• Poco a poco se van formando los grupos.
• Algunas utilidades reales de clasificación de este tipo de algoritmos pueden ser:
– Diseño de circuitos electrónicos (los componentes electrónicos conectados deben estar cerca)
– Gestión eficiente de computadoras paralelas (los procesos con dependencia de datos deben ejecutarse en el mismo procesador).
Computación Bioinspirada
Abraham Otero Quintana
47/115
• Demo: http://www.rennard.org/alife/english/antsgb.html
Computación Bioinspirada
Abraham Otero Quintana
48/75
• Bibliografía:– J. Schneider, Swarm intelligence, Communications of the
ACM, 45(8), 62-67.
Computación Bioinspirada
Abraham Otero Quintana
49/75
1. Introducción a la inteligencia artificial
2. Redes neuronales artificiales
3. Algoritmos genéticos
4. Algoritmos bioinspirados
5. Conclusiones
Índice
Abraham Otero Quintana
50/75
Conclusiones
• Las soluciones de la madre naturaleza no tienen que ser siempre las mejores…
Abraham Otero Quintana
51/75
Conclusiones
• Pero a veces pueden ser sorprendentemente buenas… y sencillas