PerezEscuderoAlexis

Vista previa del material en texto

UNIVERSIDAD VERACRUZANA
Maestŕıa en Inteligencia Artificial
Implementación de un esquema robótico para la optimización de
comportamientos en ambientes no estructurados utilizando algoritmos
bioinspirados
TESIS QUE PRESENTA:
Alexsi Adad Pérez Escudero
PARA OBTENER EL TÍTULO DE Maestro en Inteligencia Artificial
DIRECTOR DE TESIS: Dr. Fernando M. Montes González
CO-DIRECTOR: Dr. Efrén Mezura Montes
REVISOR: Dr. Carlos Alberto Ochoa Ort́ız Zezzatti
Xalapa, Veracruz, México NOVIEMBRE DE 2014
ii
iii
AGRADECIMIENTOS
Es imposible nombrar a todas las personas a las que le estoy agradecido, ya que he
tenido muy bueno compañeros amigos y personas muy queridas que dejan huella en tu
vida, aśı que a todas esas personas les estoy muy agradecido por haber formado parte
de mi vida.
A mi madre por apoyarme incondicionalmente en las buenas y en las malas, por
enseñarme a ser una mejor persona cada d́ıa, por enseñarme a nunca rendirme y sobre
todo por estar conmigo en cada momento de mi vida, y escucharme cuando lo necesito,
y acercarme a Dios para aprender a creer en él y sentir su apoyo cuando más lo necesito.
A mi hermano con acompañarme en los bueno y en los malos momentos, y distraerme
en los momentos necesarios.
A mis t́ıos que se enorgullecen de mı́ por ver todos los logros y metas que he alcan-
zado.
Y a todos mis familiares que han créıdo en mı́ y que saben que puedo lograr esto y
mucho más, gracias por su apoyo.
A mis directores de tesis los Drs. Fernando Montes y Efrén Mezura por ayudarme
y orientarme en los problema presentandos, por su paciencia y tiempo.
A todos los maestros de la MIA por compartir su conocimiento y tener la paciencia
de enseñarme nuevas cosas.
A todos mis amigos de la MIA especialmente a Paty y a Miguel por su apoyo
incondicional, también a Adán a Elva y a Javier que me ayudaron en estos años en que
cursamos la maestŕıa.
A todos mis amigos de la PANA por apoyarme en los momentos dificiles, Kuter,
Marcos, Ever, Pocho, Clark, Fercho.
♡
iv
ÍNDICE GENERAL
AGRADECIMIENTOS iii
ÍNDICE GENERAL v
ÍNDICE DE TABLAS ix
ÍNDICE DE FIGURAS xi
1 Motivo de la Investigación 1
1.1 Introducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Aproximación basada en el conocimiento . . . . . . . . . . . . . . . . . 3
1.2.1 Robótica basada en comportamientos . . . . . . . . . . . . . . . 4
1.3 Problemática . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.4 Justificación e Hipótesis . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.5 Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.5.1 Objetivo General . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.5.2 Objetivos Espećıficos . . . . . . . . . . . . . . . . . . . . . . . . 10
1.6 Alcances y limitaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2 Robótica Evolutiva 13
2.1 Introducción a la robótica evolutiva . . . . . . . . . . . . . . . . . . . . 13
2.1.1 Inicio de la robótica evolutiva . . . . . . . . . . . . . . . . . . . 13
2.1.2 Perspectiva Ingenieril de la RE . . . . . . . . . . . . . . . . . . 15
2.1.3 Diferentes enfoques de la RE . . . . . . . . . . . . . . . . . . . . 17
2.2 Neuro-controladores . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
v
vi ÍNDICE GENERAL
2.3 Proceso de evolución de la RNA . . . . . . . . . . . . . . . . . . . . . . 23
3 Algoritmos Bioinspirados 27
3.1 Introducción a los algoritmos bioinspirados . . . . . . . . . . . . . . . . 27
3.1.1 Inteligencia Colectiva . . . . . . . . . . . . . . . . . . . . . . . . 29
3.1.2 Espacio de búsqueda . . . . . . . . . . . . . . . . . . . . . . . . 31
3.2 Algoritmo Genético . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.3 Evolución Diferencial . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.3.1 Operadores de la ED . . . . . . . . . . . . . . . . . . . . . . . . 39
3.4 MBFOA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
3.4.1 Operadores del MBFOA . . . . . . . . . . . . . . . . . . . . . . 45
3.5 CDE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
4 Metodoloǵıa 51
4.1 Robots utilizados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
4.1.1 Robot E-puck . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
4.1.2 Robot Pioneer . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
4.1.3 Simulador Player-Stage . . . . . . . . . . . . . . . . . . . . . . . 56
4.1.4 Simulación de robot en Player-Stage . . . . . . . . . . . . . . . 58
4.1.5 Adaptación del comportamiento en las RNA’s . . . . . . . . . . 58
4.1.6 Evaluación/Evolución del comportamiento de seguir paredes . . 60
4.1.7 Pruebas estad́ısticas utilizadas . . . . . . . . . . . . . . . . . . . 63
5 Resultados 65
5.1 Introducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
5.1.1 Resultados obtenidos . . . . . . . . . . . . . . . . . . . . . . . . 65
5.2 Comportamiento de los Algoritmos . . . . . . . . . . . . . . . . . . . . 72
5.2.1 Algoritmo Genético . . . . . . . . . . . . . . . . . . . . . . . . . 72
5.2.2 M.B.F.O.A. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
5.2.3 Evolución Diferencial . . . . . . . . . . . . . . . . . . . . . . . . 75
5.2.4 CDE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
ÍNDICE GENERAL vii
6 Conclusiones y Trabajo Futuro 79
6.1 Conclusiones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
6.1.1 Trabajo Futuro . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
BIBLIOGRAFÍA 83
viii ÍNDICE GENERAL
ÍNDICE DE TABLAS
4.1 Elementos del Pioneer . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
4.2 Parámetros de los AB’s . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
5.1 Resultados Pioneer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
5.2 Resultados del robot E-puck . . . . . . . . . . . . . . . . . . . . . . . . 66
5.3 Estad́ısticas Obtenidas . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
5.4 Prueba de Wilcoxon para el robot pioneer . . . . . . . . . . . . . . . . 70
5.5 Prueba de Wilcoxon par el robot e-puck . . . . . . . . . . . . . . . . . 71
ix
x ÍNDICE DE TABLAS
ÍNDICE DE FIGURAS
1.1 Modelo de la estructura basada en conocimiento . . . . . . . . . . . . . 3
1.2 Modelo de la estructura basada en comportamiento . . . . . . . . . . . 5
1.3 Modelo de la robótica evolutiva . . . . . . . . . . . . . . . . . . . . . . 7
1.4 Proceso de evolución del neuro-controlador . . . . . . . . . . . . . . . . 11
2.1 Metodoloǵıa de la robótica evolutiva . . . . . . . . . . . . . . . . . . . 15
2.2 Esquema de neurona biológica . . . . . . . . . . . . . . . . . . . . . . . 19
2.3 Modelo de neurona artificial . . . . . . . . . . . . . . . . . . . . . . . . 21
2.4 Modelo de RNA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3.1 Representación artificial del algoritmo ACO . . . . . . . . . . . . . . . 31
3.2 Representación del espacio de búsqueda . . . . . . . . . . . . . . . . . . 32
3.3 representación genot́ıpica . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.4 Método selección por Ruleta . . . . . . . . . . . . . . . . . . . . . . . . 36
3.5 Método de cruza AG . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.6 Método de mutación AG . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.7 Elección de 3 vectores . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.8 Obtención vector mutante . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.9 Ejemplo de vectores generados . . . . . . . . . . . . . . . . . . . . . . . 43
3.10 Ejemplo de nado y tambaleo de bacteria . . . . . . . . . . . . . . . . . 45
3.11 Convergencia de MBFOA . . . . . . . . . . . . . . . . . . . . . . . . . 46
3.12 Proceso de swarming MBFOA . . . . . . .. . . . . . . . . . . . . . . . 47
4.1 E-Puck Básico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
xi
xii ÍNDICE DE FIGURAS
4.2 E-puck con torreta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
4.3 Robot Pioneer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
4.4 Entorno Player-Stage . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
4.5 Robots Simulados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
4.6 RNA del robot epuck . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
4.7 RNA del robot Pioneer . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
4.8 Arena de prueba . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
5.1 Gráfica de convergencia robot Pioneer . . . . . . . . . . . . . . . . . . . 69
5.2 Gráfica de convergencia robot E-puck . . . . . . . . . . . . . . . . . . . 70
5.3 Gráfica de convergencia AG robot Pioneer . . . . . . . . . . . . . . . . 72
5.4 Gráfica de convergencia AG robot E-puck . . . . . . . . . . . . . . . . 73
5.5 Gráfica de convergencia MBFOA robot Pioneer . . . . . . . . . . . . . 74
5.6 Gráfica de convergencia MBFOA robot E-puck . . . . . . . . . . . . . . 74
5.7 Gráfica de convergencia ED robot Pioneer . . . . . . . . . . . . . . . . 75
5.8 Gráfica de convergencia ED robot E-puck . . . . . . . . . . . . . . . . . 76
5.9 Gráfica de convergencia CDE robot pioneer . . . . . . . . . . . . . . . . 77
5.10 Gráfica de convergencia CDE robot E-puck . . . . . . . . . . . . . . . . 77
CAPITULO 1
Motivo de la Investigación
1.1 Introducción
El buscar la forma de que los robots sean cada vez más autónomos es una de las
principales tareas de los investigadores en la actualidad [Nolfi and Floreano, 2000] ,
debido a esto cada vez se buscan nuevas técnicas para que los robots puedan realizar
funciones más complejas que generalmente pueden resultar dif́ıciles o muy repetitivas
para los humanos. Es por esto que la Inteligencia Artificial (IA) nace como un campo
de estudio a partir de la robótica, ya que en esta última existen muchas vertientes como
pueden ser redes neuronales, teoŕıa de control, teoŕıa de la complejidad, visión artificial,
entre otras. Marvin Minsky [Marvin, 2006] argumentó que:
“La máquina inteligente podŕıa construir dentro de śı misma, un modelo
abstracto del entorno y entonces intentar experimentos externos”
a partir de esta postura se incrementan las investigaciones en la robótica. Durante
muchos años los robots que más desarrollo tuvieron fueron los robots industriales, ha-
ciendo ensamblajes y maximizando las lineas de producción, realizando estas labores
mucho más rápido y automatizando tareas que antes no se pod́ıan, no obstante este
tipo de robots casi siempre trabajan en ambientes estructurados, es decir ambientes
que no presentan algún tipo de cambio significativo con el paso del tiempo, son ambi-
entes predecibles en donde sus cambios, si es que se llegan a presentar, son cambios que
1
2 CAPITULO 1. MOTIVO DE LA INVESTIGACIÓN
pueden ser incluidos en la programación de dichos robots. Pero esto ha dado un giro
muy importante en los últimos años, dando cabida a nuevos tipos de robots autónomos,
los cuales tienen que desempeñar tareas más complejas que una linea de producción,
en otras palabras estos robots tienen que ser lo más autónomos posible porque las
funciones que tienen que realizar serán dentro de ambientes no estructurados, es decir
ambientes dinámicos que no pueden ser predichos, esto hace imposible que el robot este
programado para todas las situaciones que se puedan presentar al momento de llevar a
cabo sus instrucciones [Santos and Duro, 2005].
La robótica autónoma se considera un sub-campo de la inteligencia artificial debido
a que el realizar algunas labores o aprender diversos comportamientos requiere de cierto
grado de inteligencia, pero además de esto el trabajar con robots implica varios retos
más, como por ejemplo, no solamente hacer que el robot realice con éxito las tareas que
le son encomendadas y producir una respuesta sino que esta debe ser reflejada en el
mundo real. Para aclarar esto el término “robot autónomo” suele confundirse con “robot
móvil” pero realmente son términos diferentes. Un robot autónomo suele ser móvil, es
decir es aquel que no esta fijado en alguna posición sino más bien que puede desplazarse
por su entorno e interactuar con él con la menor intervención humana posible o en el
mejor de los casos con completa ausencia de ésta. Por el contrario un robot móvil no
es necesariamente autónomo ya que existen muchos robots que son tele-operados como
por ejemplo los robots que se usan para desarmar bombas [Nolfi and Floreano, 2000].
Para considerar que un robot es autónomo, es necesario que sea capaz de reaccionar
e interactuar con su entorno aśı como también lidiar con situaciones que no estén
consideradas en su programación y pueda resolver de una manera satisfactoria la tarea
que le fue encomendada o por lo menos encontrar a una solución factible de acuerdo
a las condiciones presentadas, todo esto sin que alguna supervisión venga del exterior
[Murphy, 2000].
Sin embargo para que todo esto sea posible es necesario que el robot cuente con
una estructura cognitiva de control que le permita vincular los est́ımulos que recibe del
mundo exterior gracias a su sensores, y las acciones que deberá ejecutar por medio de
sus actuadores, esta vinculación sensor-actuador es lo que hace posible que el robot
pueda sobrevivir en ambientes no estructurados y aśı pueda alcanzar sus metas, al
1.2. APROXIMACIÓN BASADA EN EL CONOCIMIENTO 3
Figura 1.1: Modelo de la estructura basada en conocimiento
mismo tiempo la retroalimentación hace que cada vez realice mejor sus tareas, como
por ejemplo que aprenda de sus errores [Santos and Duro, 2005].
Existen varias maneras de atacar los problemas de autonomı́a de los robots, la IA
propone varias opciones de entre las cuales se encuentran, la tradicional aproximación
basada en conocimiento que tiene sus oŕıgenes en la relación con la Inteligencia Artificial
simbólica y una más actual que es la robótica basada en comportamientos la cual esta
inspirada en la naturaleza y rompe con algunas de las bases de la IA tradicional.
1.2 Aproximación basada en el conocimiento
Las arquitecturas que siguen la aproximación basada en el conocimiento o tradicional
surgen de la descomposición de los procesos que el robot debe realizar en tareas inde-
pendientes para posteriormente unirlos, como lo ilustra la Figura 1.1, donde se puede
apreciar que primero el robot recibe est́ımulos a través de sus sensores para interpretar
los datos, con estos el robot hace un modelado del entorno en el que se desenvuelve,
modelo sobre el cual hace una planificación del conjunto de acciones que puede llegar a
realizar, finalmente pasa por un proceso de ejecución de las acciones determinadas que
indican a los actuadores que valores deben de tomar para cada situación.
Dentro de este enfoque la parte de la planificación se basa en un sistema de res-
olución de problemas llamado STRIPS (Stanford Research Institute Problem Solver,
4 CAPITULO 1. MOTIVO DE LA INVESTIGACIÓN
por sus siglas en ingles) sobre un modelo de entorno simbólico es decir mediante
lógica de predicados de primer orden para tareas como mover objetos o desplazarse
[Fikes and Nilsson, 1971].
Uno de los problemas que tiene esta aproximación es que algunos procesos como
lo son la obtención de datos y la planificación, se realizan mediante módulos desarrol-
lados, sin tener en cuenta el resto de los módulos que participan en la arquitectura.
Otro problema que también presenta es como representar el mundo real, ya que es ex-
tremadamente dif́ıcil debido a que el mundo se encuentra en constante cambio y este
cambio es muy dif́ıcil de representar por el diseñador. Porotro lado algunas de las
desventajas que menciona Harvey I. son [Harvey, 1997]:
• La descomposición del sistema de control de un robot en sub-partes no siempre
es evidente.
• Las interacciones entre los módulos son más complejas que unos simples enlaces
entre ellos, dado que muchas de ellas las determina el propio entorno.
• A medida que la complejidad del sistema crece, las interacciones entre los módulos
crecen de modo exponencial.
Debido a las debilidades que presentaba este enfoque los investigadores del área
comenzaron a buscar otras formas de arquitecturas cognitivas, en las cuales sus diversos
módulos se desarrollen e interactúen de una manera coordinada y simultanea, esto dio
origen a la aproximación basada en comportamientos.
1.2.1 Robótica basada en comportamientos
La falta de robustez que presenta la robótica basada en conocimiento es debido, en gran
parte, a la ausencia en la estrategia de las interacciones entre los diferentes módulos al
momento de diseñarlos. Es por esto que el enfoque de la Robótica Basada en Compor-
tamiento parte de la idea de proveer al robot con una colección de comportamientos
simples y básicos [Nolfi and Floreano, 2000].
1.2. APROXIMACIÓN BASADA EN EL CONOCIMIENTO 5
Figura 1.2: Modelo de la estructura basada en comportamiento
Los comportamientos son implementados en sub-partes separadas del sistema de
control y un mecanismo de coordinación es el encargado de determinar la fuerza rel-
ativa de cada comportamiento en un momento en particular. La coordinación puede
ser llevada a cabo por medio de métodos competitivos o cooperativos. En los métodos
competitivos sólo un comportamiento afecta la salida del motor del robot en un mo-
mento en particular. En los métodos cooperativos diferentes comportamientos pueden
contribuir a una acción sencilla del motor aunque con diferente intensidad.
El comportamiento global del robot debe emerger de la interacción entre estos com-
portamientos simples y el ambiente que lo rodea [Brooks, 1986]. La selección del com-
portamiento que debe emerger se basa en la jerarqúıa de subsunción donde los com-
portamiento están ordenados por capas, y los comportamientos de las capaz más bajas
tienen prioridad sobre los comportamientos de las capaz más altas, es decir las capas
más bajas inhiben a las capas superiores como se muestra en la Figura 1.2.
Partiendo de esta postura [Brooks, 1991] menciona que para poder tener un sistema
robótico robusto hay que tomar en cuenta los siguientes puntos al momento de diseñar
dicho sistema:
• El robot se encuentra en el mundo real y no requiere operar con representaciones
abstractas del mundo, al contrario debe operar con el mundo mismo.
• El robot presenta caracteŕısticas f́ısicas, las cuales se deben considerar en las
acciones que el robot realiza en el mundo.
6 CAPITULO 1. MOTIVO DE LA INVESTIGACIÓN
• La inteligencia del robot debe surgir a ráız de la interacción con el mundo.
• Toda la información que el robot recibe debe ser directamente del ambiente y no
a través de śımbolos.
• El sistema robótico debe ser escalable.
Investigadores como [Brooks, 1986], [Maes, 1990], [Sharkey, 1997] empezaron a es-
tablecer las bases de una nueva tendencia en robótica, la cual está situada entre la
planificación de alto nivel de la inteligencia deliberativa y la teoŕıa de control de bajo
nivel. Posteriormente debido a los buenos resultados arrojados por la robótica basada
en comportamiento Sharkey menciono que esta aproximación:
“Creció como una tendencia a la simplicidad, adaptabilidad y como actitud
de lo que la naturaleza conoce mejor: la estupidez natural es mejor que la
inteligencia artificial”
Por otro lado es importante mencionar que este enfoque no sólo se aplica en robótica
sino que también se puede aplicar en casos en los que se requiera un sistema que
realice varias tareas en un entorno dinámico, dado que estos sistemas deben aprender
a reaccionar dependiendo de la situación, esto es lo que afirma [Maes, 1990]
La mayoŕıa de los sistemas basados en el comportamiento también son reactivos, lo
que significa que no necesitan de una programación de representaciones internas de por
ejemplo como luce una silla, o en que tipo de superficie el robot se mueve. En cambio
toda esa información se obtiene de la entrada de los sensores del robot. El robot utiliza
esa información para corregir gradualmente sus acciones de acuerdo a los cambios en el
entorno inmediato.
El hecho de trabajar con la robótica basada en comportamiento indica que el
diseñador/programador, es el responsable de dividir los comportamientos, lo cual en
algunos casos puede llegar a ser demasiado complejo y siempre dependerá de la per-
spectiva que el diseñador le quiera dar al problema, esto implica que un mismo compor-
tamiento complejo puede llegar a emerger a partir de diferentes diseños/configuraciones
de sub-comportamientos [Nolfi and Floreano, 2000]. En estos casos es dif́ıcil descom-
poner modularmente cada uno de los elementos que conforman el comportamiento final,
1.2. APROXIMACIÓN BASADA EN EL CONOCIMIENTO 7
Figura 1.3: Modelo de la robótica evolutiva, donde el diseñador no tiene que decidir
como dividir el comportamiento deseado. La forma en que se divide un comportamiento
deseado en distintos módulos es el resultado un proceso de auto-organización
esto es una gran desventaja que presenta esta aproximación debido a que muchas veces
se depende de la prueba y error para dotar al robot con los comportamientos necesar-
ios para su tarea final. Estas desventajas presentadas fueron el catalizador para que
surgiera un nuevo tipo de robótica: la Robótica Evolutiva (RE).
La RE es un área de la robótica autónoma, la cual se basa en el uso de algorit-
mos bio-inspirados (AB), como lo son las redes neuronales artificiales (RNA), algo-
ritmos evolutivos (AE) y de inteligencia colectiva (IC), para el desarrollo de compor-
tamientos robóticos. La RE intenta relacionar la bioloǵıa con ciencias cognitivas y la
inteligencia artificial, y está basada en el principio Darwiniano de reproducción selec-
tiva del más apto, esto último es conocido mayormente como evolución artificial (EA)
[Nolfi and Floreano, 2000].
Cabe mencionar que la evolución artificial esta inspirada en la evolución natural,
pero presenta ciertas diferencias con ésta, como por ejemplo, la evolución natural no
tiene un objetivo en especifico es básicamente un proceso de adaptación constante,
mientras que la evolución artificial simplemente es un proceso de optimización de solu-
ciones para problemas determinados, otra diferencia es que en la evolución natural los
individuos más aptos son aquellos que logran adaptarse mejor a su ambiente, por el
contrario en la evolución artificial la calidad de los individuos o más aptos son deter-
minados por una función de aptitud (fitness) que mide su desempeño de acuerdo al
problema dado.
8 CAPITULO 1. MOTIVO DE LA INVESTIGACIÓN
Este principio hizo que varios investigadores empezaran a implementar la EA para
obtener controladores de robots con el objetivo de que pudieran ser lo más autónomos
posible, y propusieron a la EA como un medio para automatizar la obtención de éste
tipo de controladores [Beer and Gallagher, 1992], [Husbands et al., 1994].
A grandes rasgos en la robótica evolutiva definimos los componentes del sistema
de control (sensores y actuadores) y un criterio de selección, y dejamos a la evolución
artificial descubrir a los individuos más adecuados con el paso de generaciones, mientras
el robot interactúa con el entorno, es decir con cada nueva generación los individuos
serán más aptos para realizar la tarea que se les ha programado, sin tener intervención
humana o muy poca [Santos and Duro, 2005]. Después de la evolución, el resultado
es un agente cognitivo simulado pero situado en un ambiente real y cuyos mecanismos
de controlneuronal (redes neuronales, sensores y actuadores), son capaces de producir
conductas cognitivas (ver Figura 1.3 ). Generalmente el sistema de control de los robots
es una o varias RNAs, razón por lo que se le conoce como neuro-controlador, este neuro-
controlador es el que generalmente se somete al proceso de evolución. Éste tema será
tratado con mayor profundidad en los siguientes caṕıtulos.
En este trabajo se tiene por objetivo evolucionar una red neuronal (neuro-controlador),
es decir encontrar los pesos óptimos para las interconexiones de las neuronas, utilizando
el algoritmo de inteligencia colectiva M.B.F.O.A. (Modified Bacterial Foraging Opti-
mization Algorithm), el cúal a su vez esta basado en el algoritmo B.F.O.A (Bacterial
Foraging Optimization Algorithm) propuesto por Passino en 2002, y aśı obtener un buen
neuro-controlador para el robot para el comportamiento de seguir paredes y además ver
qué tan eficiente es el M.B.F.O.A. realizando esta tarea al compararlo con el algoritmo
genetico (AG) (el más usado tradicionalmente en esta área) y contra la Evolución Difer-
encial (ED), algoritmo que por su forma de trabajar ha demostrado tener muy buenos
resultados en problemas de busqueda y optimización, a su vez también se prueba contra
un algoritmo reciente que incorpora los puntos más fuertes del B.F.O.A. y de la E.D.
llamado Chemotaxis Diferential Evolution (C.D.E.) .
1.3. PROBLEMÁTICA 9
1.3 Problemática
En robótica evolutiva desde que se comprobó que los algoritmos genéticos resolv́ıan de
una manera eficiente la obtención de neuro-controladores para el robot, se ha dejado de
probar con nuevas técnicas, por consecuencia es un área poco explorada en la actualidad
pero con mucho potencial por delante, es por esto que en éste trabajo se implementarán
el M.B.F.O.A., la E.D. y la C.D.E para obtener dichos neuro-controladores para poder
comprarlos contra el A.G. y proponer otro algoritmo para estos usos.
1.4 Justificación e Hipótesis
El explorar nuevas técnicas para la obtención de neuro-controladores es muy impor-
tante dentro de la robótica evolutiva ya que aśı se podŕıan encontrar mejores maneras
de obtener estos neuro-controladores que las tradicionales (algoritmos genéticos) y el
M.B.F.O.A. puede ser una de estas técnicas que podŕıa llegar a suplantar a los algorit-
mos tradicionales, por esto para saber qué tan eficiente puede llegar a ser el M.B.F.O.A.
para obtener neuro-controladores se plantea la siguiente hipótesis, el M.B.F.O.A. no
debeŕıa presentar diferencia significativa con respecto a otros algoritmos (algoritmo
genético, evolución diferencial y C.D.E. ), al evolucionar comportamientos.
Para comprobar esta hipótesis se implementará el comportamiento de seguir pare-
des en un robot e-puck y un robot poineer mediante el simulador Player-Stage, y se
evolucionaran sus respectivas redes neuronales. El probarlo en ambos robots representa
un reto también para el algoritmo puesto que los espacios de búsqueda no son iguales
en ambos robots ya que en el pioneer serán individuos de 144 variables mientras que en
el e-puck son individuos de 40 variables, se hablará de esto más adelante.
1.5 Objetivos
En este trabajo se tiene por objetivo evolucionar una red neuronal (neu-rocontrolador),
es decir encontrar los pesos óptimos para las interconexiones de las neuronas, utilizando
los algoritmos de inteligencia colectiva M.B.F.O.A. (Modified Bacterial Foraging Op-
10 CAPITULO 1. MOTIVO DE LA INVESTIGACIÓN
timization Algorithm), E.D. (Evolución Diferencial) y C.D.E. (Chemotaxis Diferential
Evolution),y aśı obtener un buen neurocontrolador para el robot para los comportamien-
tos de seguir paredes y además ver qué tan eficiente es el M.B.F.O.A. realizando esta
tarea.
1.5.1 Objetivo General
• Comparar el rendimiento de M.B.F.O.A. con el de los algoritmos de Evolución
Diferencia, Algoritmo Genético y C.D.E..
1.5.2 Objetivos Espećıficos
• Implementar el comportamiento de seguir paredes, utilizando M.B.F.O.A., evolución
diferencial (ED), Chemotaxis Diferential Evolution (CDE) y el algoritmo genetico
(AG)
• Comprobar que no exista diferencia significativa entre dichos algoritmos, es-
pećıficamente con el M.B.F.O.A.
• Implementar dicho comportamiento en el robot e-puck y pionner.
1.6 Alcances y limitaciones
• Se usara el simulador player stage para evolucionar los neuro-controladores
• Se utilizaran los algoritmos geneticos:
– Algoritmo Genético (AG)
– Modified Bacterial Foraging Optimization Algorithm (MBFOA)
– Evolución Diferencial (ED)
– Chemotaxis Diferential Evolution (CDE)
• Esto algoritmos se usaran para evolucionar una red neuronal artificial, que cumple
la función de neuro-controlador del robot
1.6. ALCANCES Y LIMITACIONES 11
Figura 1.4: Ejemplo del modelo del proceso de evolución del neuro-controlador, donde
se puede observar que para medir la aptitud del robot es necesario probarlo primero en
el ambiente simulado
• El comportamiento de seguir paredes es una función mono-objetivo y sin restric-
ciones, por lo cual se usaran los algoritmos mencionados adecuados a estas carac-
teŕısticas.
El proceso de evolución del neuro-controlador será para buscar los pesos de las
conexiones que existen en las redes neuronales, estos pesos son los encargados de guardar
el conocimiento del robot y de acuerdo a estos será la respuesta que muestre el robot
para el comportamiento de seguir paredes, el proceso puede ser visto más gráficamente
en la Figura 1.4.
12 CAPITULO 1. MOTIVO DE LA INVESTIGACIÓN
CAPITULO 2
Robótica Evolutiva
2.1 Introducción a la robótica evolutiva
2.1.1 Inicio de la robótica evolutiva
Existen diferentes arquitecturas para crear controladores de un robot, generalmente
la más usada es la arquitectura de subsumción [Brooks, 1986], sin embargo como se
menciono en el capitulo anterior la RE nace a partir de las desventajas que presentaba
la robótica basada en comportamiento, el termino fue introducido por los investigadores
Cliff, Harvey y Husbands en la Universidad de Sussex a principios de los 90’s, pero sus
investigaciones comenzaron a finales de los 80’s cuando Husbands se dio cuenta que
era necesario crear una solución que fuera completamente automática para la creación
de sistemas autónomos robóticos, que les permitiera sobrevivir en el entorno con la
menor intervención humana posible. Es aqúı que junto con otros cient́ıficos como Beer
y Gallager, eligieron a la evolución artificial como herramienta para poder obtener una
solución automática, y agregaron que lo más importante dentro de la robótica evolutiva
era conocer cómo se deb́ıan generar los comportamientos adecuados para que un robot
pueda solucionar una tarea o actividad.
Es debido a esto que según [Husbands et al., 1994], la RE nace como una nueva
alternativa para generar automáticamente neuro-controladores robóticos, atacando dos
problemas primordiales que aparecen principalmente en la robótica basada en compor-
13
14 CAPITULO 2. ROBÓTICA EVOLUTIVA
tamientos:
• Disminuir la complejidad que representa el diseño de mecanismos de interacción
entre los comportamientos, aśı como la interacción de los comportamientos con
la información que proviene del medio donde el robot se encuentra inmerso.
• Evitar el desarrollo de los comportamientos por parte del programador; lo que se
busca es que el robot desarrolle de alguna manera, los comportamientos necesarios
para cumplir una actividad o tarea.
Posteriormente en 1992 [Cliff et al., 1992] optaron por cambiar la visión con la que
la RE hab́ıa nacido, decidiendo que lo mas importante no era conocer cómo se deb́ıan
generar los comportamientos adecuados para una tarea determinada, sino más bien qué
comportamientos necesita el robot para cumplir con su propósito, pero conservando la
premisa básica de la robótica evolutiva y reduciendo al mı́nimo las decisiones humanas
de laprogramación, dejándole toda la responsabilidad al proceso evolutivo.
Hasta ahora se ha hablado sobre como nació la RE, pero en la literatura hay difer-
entes definiciones para describir a la RE de las cuales se resaltan las siguientes 3:
• Floreano y Mondana definen a la robótica evolutiva como: la investigación en
robótica que ve la vida tal y como es; la vida tal como podŕıa ser, entendiéndose
como concepto de vida aplicado a todo ser vivo y no únicamente al ser humano
[Floreano and F., 1998].
• Una definición un poco mas especifica es la de Santos y Duro quienes dicen que
la robótica evolutiva es una rama de la robótica que intenta obtener de un modo
automático tanto los niveles de comportamiento como la relación entre ellos, en
donde el humano decide a un nivel mı́nimo que comportamientos son necesarios
para cumplir una tarea o función, y de una manera reducida la manera en cómo
se generan dichos comportamientos, todo ello tratando de llevar al mı́nimo la
intervención del programador [Santos and Duro, 2005].
• Por último Nolfi y Floreano dicen que el resultado de la robótica evolutiva es
un agente cognitivo simulado o corpóreo, situado en un entorno sensorio-motor
2.1. INTRODUCCIÓN A LA ROBÓTICA EVOLUTIVA 15
Figura 2.1: Metodoloǵıa de la robótica evolutiva
y cuyos mecanismos de control son capaces de producir conductas cognitivas
[Nolfi and Floreano, 2000].
La robótica evolutiva buscar generar elementos de control y/o morfoloǵıa del robot
que le permitan cumplir con sus tareas asignadas, pero utilizando un proceso evolu-
tivo que artificialmente replique todo lo que ese proceso implica y todo ello con la
menor intervención humana posible [Nolfi and Floreano, 2000] [Husbands et al., 1994].
La metodoloǵıa en la que se basa la robótica evolutiva puede tener varios esquemas
dependiendo de que tan detallado se quiera ser al momento de explicarla, pero una
buena explicación de esta metodoloǵıa se puede apreciar en la Figura 2.1:
2.1.2 Perspectiva Ingenieril de la RE
En la actualidad los investigadores están de acuerdo en que es muy dif́ıcil diseñar sis-
temas de comportamiento tal como robots autónomos. Podemos observar que existen
programas de computadora eficaces que pueden jugar ajedrez o resolver problemas for-
males pero todav́ıa no hay robots móviles inteligentes en nuestros hogares o ciudades.
La razón principal de porque los robots móviles son dif́ıciles de diseñar, es que su com-
portamiento debe ser una propiedad emergente de la interacción de sus actuadores con
16 CAPITULO 2. ROBÓTICA EVOLUTIVA
el entorno. El robot y el ambiente se pueden describir como un sistema dinámico de-
bido a que el estado del sensor del robot en cualquier momento dado es una función de
ambas: el ambiente y las acciones previas del robot. Como el comportamiento del robot
es una propiedad emergente de la interacción entre el robot y el ambiente, tiene como
consecuencia que robots simples puedan producir comportamientos complejos. Sin em-
bargo al ser un sistema dinámico, las propiedades del comportamiento no pueden ser
inferidas o predichas a partir de reglas de conocimiento que gobiernen las interacciones.
Lo inverso también es verdad: es dif́ıcil predecir cuales reglas producirán un compor-
tamiento dado, ya que éste es el resultado emergente de la interacción dinámica entre
el robot y el ambiente [Nolfi and Floreano, 2000].
La estrategia que se ha venido siguiendo para resolver estos problemas ha sido la de
“divide y vencerás”, donde la solución viene dada de dividir el problema principal en
una serie de problemas más simples. Los enfoques clásicos de la robótica han asumido
a menudo una ruptura primaria entre percepción, planeación y acción. Los resultados
que ha producido esta forma de dividir los problemas son limitados y ha sido criticado
por un buen número de investigadores.
[Brooks, 1986], propone un enfoque radicalmente diferente en el cual la división
se lleva a cabo al nivel del comportamiento. El comportamiento deseado se separa
en un conjunto de comportamientos básicos más simples, los cuales son modulados
a través de un mecanismo de coordinación. En este último enfoque, el sistema de
control es construido incrementalmente nivel por nivel, donde cada nivel es responsable
de un sólo comportamiento básico ligando directamente sensores a motores. Primero
se implementan los comportamientos básicos simples, a continuación nuevos niveles
que implementan otros comportamientos básicos, son adheridos una a la vez después
de intensas pruebas y depuraciones. Este enfoque ha demostrado que ambos niveles
(módulos) responsables de los comportamientos básicos simples y el mecanismo de
coordinación puede ser obtenido de un proceso de auto-organización más que de un
diseño explicito.
En enfoques de descomposición basados en el comportamiento, el diseñador es el en-
cargado de romper el comportamiento deseado en varios comportamientos básicos más
simples. Desafortunadamente, no dejan claro cómo es que el comportamiento deseado
2.1. INTRODUCCIÓN A LA ROBÓTICA EVOLUTIVA 17
debeŕıa ser descompuesto, y es muy dif́ıcil llevar tal descomposición a mano. Incluso
investigadores que adoptaron exitosamente la descomposición de comportamientos e in-
tegración sienten que este es un problema crucial. Rodney Brooks, por ejemplo, anota:
“En cambio, dados muchos comportamientos presentes en un sistema basado
en el comportamiento, y sus dinámicas individuales de interacción con el
mundo, es a menudo dif́ıcil decir que una serie particular de acciones fue pro-
ducida por un comportamiento particular. Algunas veces muchos compor-
tamientos están operando simultáneamente, o están alternando rápidamente”.
[Brooks, 1991]
2.1.3 Diferentes enfoques de la RE
Tradicionalmente y de acuerdo con los oŕıgenes en Inteligencia Artificial la robótica
empleaba planificación la cual inicialmente proporcionaba soluciones lentas al problema
de controlar un robot en un ambiente poco estructurado. A partir de esto surgió la
propuesta de la robótica reactiva y que cobró su mayor importancia a través de los
trabajos de Brooks [Brooks, 1986] que empleaban sistemas codificados por un diseñador
humano. Posteriores trabajos [Maes, 1994], [Minsky, 1988], entre otros, ofrecieron la
alternativa de descomponer las acciones en conductas haciendo de la selección de acción
un sistema reactivo.
Mucho de este enfoque se preserva hasta ahora resumiendo el problema de selección
de acción en cómo integrar los distintos módulos para producir comportamientos co-
herentes. Sin embargo muchos investigadores consideran que esta división es artificial y
depende del punto de vista del diseñador humano, aśı como la identificación de conduc-
tas en un animal dependen de un etólogo. Sin embargo, existe considerable evidencia
de que en los vertebrados existen mecanismos de selección de acción centralizados que
permiten la integración de módulos que pueden representar bloques de movimientos
previamente memorizados [Nolfi and Floreano, 2000].
Por otra parte, un sistema completamente autónomo debeŕıa ser capaz de desple-
gar diferentes tipos de conductas para poder sobrevivir y contender con las diferentes
vicisitudes ambientales. Algunas de estas conductas serán compatibles y algunas otras
18 CAPITULO 2. ROBÓTICA EVOLUTIVA
serán mutuamente exclusivas. Debido a que no todas las conductas son compatibles,
el sistema debe ser capaz de activar la conducta adecuada en el momento oportuno
(una selección adecuada entre las distintas conductas). Para llevar a cabo lo anterior
distintas metodoloǵıas han sido propuestas para diseñar sistemas que sean capaces de
exhibir distintos comportamientos con un correcto arbitraje.
Estas metodoloǵıas dependen en gran parte en una organización de comportamien-
tos implementados por un diseñador humano. Además estos modelosdependen de
una propuesta que no es completamente escalable debido a que el desarrollo de estos
sistemas se ha enfocado en un diseño espećıfico para desplegar una gran cantidad de
conductas. En lugar de lidiar con pequeñas variaciones en el medio ambiente de de-
sempeño y en la tarea de modelar. De este modo un reto actual en la robótica consiste
en desarrollar metodoloǵıas que sirvan de base a sistemas que sean capaces de desar-
rollar autónomamente sus propias habilidades conductuales. Aśı como de arbitraje a
través de un proceso interactivo con una genuina interacción con el medio ambiente.
2.2 Neuro-controladores
Una red neuronal artificial es una estructura de procesamiento distribuido inspirado
biológicamente en la redes neuronales del cerebro.
Es importante mencionar que biológicamente las neuronas se comunican a través de
conexiones llamadas sinapsis. Cada neurona esta compuesta por tres partes fundamen-
tales: el soma, dendritas y axón (ver Figura 2.2). El soma en su capa externa tiene la
capacidad única de generar impulsos nerviosos. Las dendritas que son como las ramas
que salen del soma, poseen algunas conexiones sinápticas en donde se reciben señales
que generalmente vienen de otros axones. El soma realiza la sumatoria de todas las
señales provenientes de las dendritas, cuando en el soma se llega a una suma suficiente,
se dispara la célula, o en su defecto, transmite mediante el axón, una señal hacia otras
neuronas [Russell and Norvig, 2004]. El funcionamiento de una neurona artificial esta
basado en éste diseño.
Para poder dotar al robot de una estructura de control que le permita aprender con
el paso del tiempo, las redes neuronales artificiales son generalmente las más utilizadas
2.2. NEURO-CONTROLADORES 19
Figura 2.2: Esquema de neurona biológica
para éste propósito, sin embargo su uso no sólo se limita a éste tipo de estructuras
sino que en general son muy utilizadas dentro del campo de la inteligencia artificial. El
primer modelo de una Red Neuronal Artificial fue desarrollado por McCulloch y Pitts
en 1943, consist́ıa en dos estados lógicos como salida: encendido y apagado.
Sin embargo ésta primera aproximación no fue muy popular debido en gran parte a
que sólo funcionaba con problemas que eran linealmente separables, debido a esto las
investigaciones sobre RNA’s fueron apartadas por mucho tiempo. No fue sino hasta
la década de los 80’s que el campo recobro fuerzas, gracias a la aparición de RNA’s
multicapas que permit́ıan resolver problema linealmente no separables mediante la re-
gionalización del problema y con ayuda del algoritmo de retroalimentación del error
(del inglés backpropagation) propuesto por Rumelhart, Hinton y Williams.
Estas RNA’s pueden llegar a ser tan robustas debido a las caracteŕısticas que pre-
sentan que según [Hilera González and Mart́ınez Hernando, 1995] seŕıan las siguientes:
• Aprendizaje adaptativo: Esta quizás sea la mejor caracteŕıstica que presentan
las RNA’s, se refiere a la capacidad que tienen para aprender a realizar tareas
basadas en un experimento o entrenamiento inicial. De esta forma, no es necesario
elaborar un modelo a priori, ni establecer funciones probabiĺısticas. Una red
neuronal artificial es adaptativa porque puede modificarse constantemente con el
20 CAPITULO 2. ROBÓTICA EVOLUTIVA
fin de adaptarse a nuevas condiciones de trabajo.
• Autoorganización: Mediante su aprendizaje adaptativo las RNA’s pueden
organizar toda la información que reciben durante el aprendizaje. Consiste en la
modificación de la red completa con el fin de llevar a cabo un objetivo especifico, es
aśı como la red puede responder a datos o situaciones no experimentadas antes,
pero puede hacer inferencias sobre su base de conocimiento. Esto es muy útil
sobre todo cuando la información de entrada no esta completa o es poco clara.
• Tolerancia a fallos: Mientras que en la computación tradicional la inconsisten-
cia o perdida de datos pueden causar un colapso total del sistema en las RNA’s
esto no sucede debido a que poseen una gran tolerancia a fallos, esto es debido a
que las RNA’s guardan su información de una manera distribuida y muy redun-
dante, de este modo las redes pueden seguir trabajando aunque se destruya una
parte de la red, si esto llega a suceder probablemente el comportamiento de la red
se vea afectado, pero de ningún modo colapsara, y se podrá adaptar a la nueva
situación.
• Operación en tiempo real: Si se quiere hacer un reconocimiento de patrones
en tiempo real las RNA’s son las más indicadas para hacer esta labor, debido a
que trabajan en paralelo actualizando sus instancias simultáneamente. Cabe re-
saltar que está caracteŕıstica sólo se aprecia cuando se trabaja con algún hardware
especializado en procesos paralelos.
• Fácil inserción dentro de la tecnoloǵıa existente: Debido a que una RNA
puede ser fácil y rápidamente entrenada y verificada ésta puede ser trasladada
a chips especializados para RNA’s y de esta manera integrarlos en sistemas es-
pećıficos ya existentes.
Una red neuronal consiste en un conjunto de elementos de procesamiento, llamados
neuronas, los cuales se conectan entre śı. La organización y disposición de las neuronas
dentro de una red neuronal se denomina topoloǵıa, y viene dada por el número de capas,
la cantidad de neuronas por capa, el grado de conectividad, y el tipo de conexión entre
neuronas. Una vez determinada la topoloǵıa de la red neuronal, es necesario entrenarla.
2.2. NEURO-CONTROLADORES 21
Figura 2.3: Modelo de neurona artificial, la Wi representa los pesos sinápticos entre las
conexiones
En la etapa de entrenamiento la red es capaz de aprender relaciones complejas entre
entradas y salidas mediante el ajuste de los pesos de las conexiones entre neuronas.
Por lo tanto, los elementos que constituyen la neurona son: conjunto de entradas,
pesos sinápticos, regla de propagación, función de activación, y función de salida, estos
elementos se muestran con gráficamente en la figura 2.3
Para [Russell and Norvig, 2004] una RNA está compuesta por nodos que se conectan
a través de unidades llamadas conexiones, asociadas con unos pesos numéricos, que rep-
resentan una memoria de largo plazo y que se ajusta en un proceso de aprendizaje. Otra
definición seŕıa la de [Santos and Duro, 2005] que dice que una RNA es una estructura
de procesamiento distribuida compuesta de nodos o neuronas que calculan una función
matemática generalmente no lineal y con conexiones o pesos que simulan la conexión
sináptica de las dendritas y los axones. Estas conexiones pueden ser excitadoras si
incrementan su nivel de activación o inhibidoras en el caso contrario, en general una
red neuronal según estos autores, trata de imitar a un nivel básico, el funcionamiento
de las neuronas biológicas.
Las conexiones que existen entre estas neuronas se llaman conexiones sinapticas y
son direccionales, es decir la información sólo puede propagarse en un único sentido,
desde la neurona presináptica a la postsináptica. Cuando varias neuronas se agrupan
22 CAPITULO 2. ROBÓTICA EVOLUTIVA
Figura 2.4: Modelo de una RNA, donde se pueden apreciar las capas que la constituyen
a un mismo nivel se les llama capas, dependiendo de la estructura de la propia red se
pueden encontrar varias capas, pero en general se distinguen 3 tipos de capas: de en-
trada, de salida y ocultas [Hilera González and Mart́ınez Hernando, 1995], al conjunto
de una o más capas se le denomina red neuronal.
La capa de entrada esta constituida por neuronas que reciben datos o señales del
exterior, en el caso de la robótica generalmente esta capa esta constituida por los
sensores del robot. La capa de salida es aquella donde las neuronas proporcionan la
respuesta de la red neuronal, de igual manera en robótica esta capa de salida suele ser
la capa que contiene los actuadores del robot. Porúltimo la capa oculta es la que no
tiene una conexión directa con el entorno, es decir las entradas de estas neuronas son
las salidas de las neuronas provenientes de la capa anterior y su salida no es directa al
exterior sino que mandan su respuesta hacia otra capa de la red, esto se muestra en la
figura 2.4.
Las conexiones entre las neuronas pueden ser excitatorias o inhibitorias: un peso
sináptico negativo define una conexión inhibitoria, mientras que uno positivo determina
una conexión excitatoria. Habitualmente, no se suele definir una conexión como de un
tipo o de otro, sino que por medio del aprendizaje se obtiene un valor para el peso, que
incluye signo y magnitud [Russell and Norvig, 2004].
En el contexto de las redes neuronales, puede definirse el aprendizaje como el proceso
por el que se produce el ajuste de los parámetros libres de la red a partir de un proceso de
2.3. PROCESO DE EVOLUCIÓN DE LA RNA 23
estimulación por el entorno que rodea la red. El proceso de aprendizaje de una RNA está
dividido en dos fases: entrenamiento y clasificación. Durante la etapa de entrenamiento
los pesos sinápticos entre las conexiones de la red son ajustados, utilizando t́ıpicamente
algún algoritmo de aprendizaje supervisado y no supervisado. Posteriormente la etapa
de clasificación ocurre una vez que los pesos de la red han sido ajustados y es cuando
la red comienza a realizar la tarea para la que fue diseñada [Russell and Norvig, 2004].
En el caso de la Robótica Evolutiva estos mismos procesos están presentes, con la
diferencia de que en la primera etapa no se utilizan algoritmos clásicos de las redes
neuronales para el aprendizaje, sino que se utilizan algoritmos diseñados para la com-
putación evolutiva, generalmente AG, que intentan optimizar los pesos de la red neu-
ronal mediante un proceso de evolución. El proceso de clasificación de la red neuronal
en robótica evolutiva se realiza de la manera t́ıpica, presentando entradas y obteniendo
salidas a partir de las funciones de entrada y activación utilizadas.
2.3 Proceso de evolución de la RNA
Una red neuronal aprende a través de un proceso de entrenamiento donde la RNA
asimila como ejecutar un conjunto de datos por toda su estructura, debido a esto el
sistema puede ajustar los pesos sinápticos (ver imagen 2.3) al comparar los resultados
parciales con el resultado final, después de ejecutar un gran numero de muestras, un
peso aleatoriamente seleccionado se puede ajustar para representar el peso exacto, al
aprender como se repiten estos patrones y secuencias, entonces la red podrá realizar
predicciones exactas cuando datos con resultados desconocidos sean procesados.
Cabe mencionar que existen dos tipos de entrenamientos, el supervisado y no su-
pervisado cuya distinción proviene en origen del campo de reconocimiento de patrones.
Dentro del entrenamiento supervisado se sabe de antemano la salida u objetivo deseado,
y se le presenta a la red un conjunto de patrones para que iterativamente vaya ajustando
sus pesos hasta que la salida tienda a ser la deseada, utilizando para ello información
detallada del error cometido a cada paso. Por otro lado el aprendizaje no supervisado
se le puede presentar a la red la misma serie de patrones, sin embargo esta vez sin
adjuntar la salida esperada, de esta manera por medio de la regla de aprendizaje la red
24 CAPITULO 2. ROBÓTICA EVOLUTIVA
estima la función de densidad de probabilidad a partir de lo cual se pueden reconocer
regularidades en el conjunto de entrada, extraer rasgos o agrupar patrones (clustering)
[Russell and Norvig, 2004]
Las caracteŕısticas más fuertes que presentan las RNA’s y que gracias a estas son
muy utilizadas en la robótica autónoma son la tolerancia a fallos, tolerancia a ruido (car-
acteŕıstica muy importante a considerar cuando se trabaja con robótica autónoma sobre
todo en entornos reales), y por último la posibilidad de usar algoritmos de aprendizaje
conexionistas tradicionales, esto hace posible hacer uso del aprendizaje conexionista
tradicional en conjunto con la evolución artificial [Nolfi, 1997].
El proceso de evolución es el medio artificial por el cual se trata de alcanzar un
objetivo en especifico o de optimizar aquello que se desea, que generalmente puede
ser: el elemento de control, la morfoloǵıa, o ambos. Dentro de la robótica evolutiva
existen diferentes herramientas o métodos que permiten alcanzar los óptimos buscados,
todos ellos forman parte de la computación evolutiva, tratando de imitar el proceso de
evolución natural en el cual se les da prioridad a los individuos más aptos para para
resolver la tarea encomendada, y aśı de esta manera los individuos más aptos puedan
pasar sus genes a las siguientes generaciones. [Nolfi and Floreano, 2000]
Para saber que individuos son los más aptos para resolver la tarea encomendada
se hace uso de una función de calidad, o función de aptitud (del ingles fitness), esta
función se encarga de evaluar que tan bien esta realizando la tarea cada individuo, es
decir es el medio a partir del cual se califica si un individuo es más o menos apto que
otro para realizar la tarea asignada, todo mediante una función matemática que califica
las aptitudes de los individuos. El resultado de esta función de calidad nos dirá que tan
bien se desenvolvió el robot en dicho ambiente.
Al evolucionar los neuro-controladores lo que se busca, en esté caso, es una con-
figuración adecuada de los pesos de las conexiones de la red para que el robot pueda
desenvolverse dentro de un ambiente, ya sea simulado o real, posteriormente la con-
figuración de estos pesos hará que el robot muestre ciertos comportamientos, compor-
tamientos que serán evaluados con la función de aptitud, la cual indicará que robots
desempeñaron mejor su función.
Si se evalúa el neuro-controlador obtenido durante un tiempo determinado (un
2.3. PROCESO DE EVOLUCIÓN DE LA RNA 25
parámetro para el proceso de evolución) y la función de calidad de cada neuro-controlador
durante un determinado tiempo T, se obtiene una curva de calidad que representa el
desempeño del proceso evolutivo, esto es crucial si se pretende analizar el proceso de
evolución porque permite detectar si ya se alcanzó el objetivo buscado o en su defecto si
ya se ha estancado en algún óptimo local, e incluso determinar si la función de aptitud
utilizada es la adecuada para el problema planteado.
El proceso de evolución del neuro-controlador del robot puede tomar un tiempo
considerable para obtener las aptitudes de cada individuo (robot), porque se tienen
que probar a los individuos dentro del entorno por un tiempo determinado para saber
que tan buena aptitud tienen, éste proceso se repetira por cada individuo dentro de
la población.[Nolfi and Floreano, 2000] Es por esto que cuando se tiene por objetivo
evolucionar los neuro-controladores de un robot de deben tomar las siguientes consid-
eraciones:
• Robustez mecánica: Generalmente las primeras generaciones de un pobla-
cion suelen producir comportamientos muy diferentes al deseado, y estos com-
portamientos pueden llegar a dañar al robot, como por ejemplo colisiones a alta
velocidad contra objetos o sobrepasar el limite de los servo-motores, etc.
• Suministro de enerǵıa: Los experimentos evolutivos generalmente son más
largos que la duración de las bateŕıas del robot, por ellos es necesario encon-
trar alguna fuente de alimentación alterna o usar simuladores para encontrar la
solución óptima que posteriormente se probará en el robot real.
• Análisis: El sistema de control de robots evolucionados puede ser muy complejo,
lo cual se traduce en la dificultad de análisis. Esto esta ı́ntimamente relacionado
con el ambiente por tal motivo a veces es dif́ıcil entender el comportamiento del
robot por simple análisis.
• Tiempo de eficiencia: Una ejecución evolutiva puede durar horas, d́ıas o
inclusohasta semanas. En algunos casos este numero puede ser reducido sin
reducir el número de pruebas de aptitud, a veces también depende de como este
planteado el problema.
26 CAPITULO 2. ROBÓTICA EVOLUTIVA
• Diseño de funciones de aptitud: El criterio de selección puede tener una
mayor influencia sobre los resultados de una ejecución evolutiva, pero puede ser
dif́ıcil el poder diseñar a priori una función efectiva para robots autónomos que
operen en ambientes parcialmente desconocidos.
En resumen en un inicio se cuenta con una población con determinado numero
de individuos y mediante el proceso de evolución el neuro-controlador dictará el com-
portamiento de cada individuo dentro del entorno, aśı mediante la función de aptitud
sabremos que tan bien realizo la tarea cada individuo de la población, posteriormente
se les dará prioridad a los individuos que hayan tenido un mejor desempeño para que
sus genes o caracteŕısticas sean heredados a las generaciones posteriores.
CAPITULO 3
Algoritmos Bioinspirados
3.1 Introducción a los algoritmos bioinspirados
Se sabe que la naturaleza es por excelencia una gran fuente de inspiración para re-
solver problemas dif́ıciles y complejos en ciencias de la computación, sin embargo la
naturaleza también ha servido como soporte para otras ciencias, como por ejemplo la
psicoloǵıa, la socioloǵıa, entre otras. Siempre encuentra la solución óptima para re-
solver su problema de mantener el equilibrio perfecto entre sus componentes, esto es
debido a que la naturaleza lleva miles de años trabajando en encontrar soluciones, es
aśı como la naturaleza toma ventaja sobre cualquier ciencia humana, y es debido a esto
que muchas veces los cient́ıficos al enfrentarse a algún problema “x” primero investigan
si la naturaleza ya ha resuelto problemas de tipo “x” para poder inspirarse de eso y
aśı llegar a una posible solución del problema presentado. Ésta es la idea detrás del
computo bioinspirado. Los algoritmos bioinspirados son una metaheuŕıstica que imitan
a la naturaleza para resolver problemas de optimización, esto es una apertura para una
nueva era en la computación [Binitha and S Siva, 2012].
Con base en esto nacen los algoritmo evolutivos los cuales están inspirados en los
principios de Darwin de la supervivencia del más apto y la teoŕıa de la evolución. Este
paradigma sostiene que los procesos que utiliza la naturaleza para mantener la vida
y equilibrio en el planeta es basicamente aplicar sobre las poblaciones cuatro procesos
estad́ısticos que son: reproducción, mutación, competencia y selección. Al resultado de
27
28 CAPITULO 3. ALGORITMOS BIOINSPIRADOS
aplicar estos procesos por varias generaciones se le conoce como evolución.
Como se menciono anteriormente la evolución artificial esta basada en la evolución
natural, para llevar a cabo esta emulación la evolución artificial simula poblaciones de
individuos los cuales son sometidos a diversas operaciones para poder calificar y obtener
a los individuos mejor adaptados, estas operaciones generalmente son: selección, cruza
y mutación, que de igual manera intentan emular estas mismas acciones en su análogo
natural. Este tipo de enfoque es utilizado para resolver principalmente problemas de
optimización, ya que no es necesario tener conocimiento alguno del problema para que
la evolución artificial alcance una solución satisfactoria.
En los años 30’s Wright hizo los primeros intentos para implementar la evolución
artificial tratando de resolver problemas de optimización, sugiriendo la utilidad de vi-
sualizar un sistema evolutivo que explora los picos de funciones multimodales mediante
clusters alrededor de los picos.
Desde entonces diferentes versiones de algoritmos bioinspirados han sido implemen-
tadas, por ejemplo en 1956 George J. Friedman propone una aplicación de técnicas
evolutivas en la robótica. Posteriormente en el año 1958 [Bremermann, 1958] fue el
primero en considerar a la evolución como un proceso de optimización y utilizó cade-
nas binarias que se combinaban por medio de operadores de reproducción, selección y
mutación.
Posteriormente gracias a la necesidad de solucionar problemas numéricos complejos
nacen las estrategias evolutivas. Un grupo de investigadores liderados por Rechemberg
en la Technische Universität de Berĺın son los responsables de proponer esta solución,
donde en su primera versión, se utiliza sólo el operador de mutación y sólo con un
individuo en la población, que posteriormente recibió algunos cambios para mejorar
esta primera aproximación [Rechenberg, 1973].
Los intentos por alcanzar diversas metas en IA hacen que un grupo de investi-
gadores ubicado en Los Ángeles en la Universidad de California, propongan la evolución
de agentes inteligentes representados como máquinas de estado finito, este enfoque lo
sugiere [Fogel et al., 1966] y es conocido como programación evolutiva.
Años más tarde en 1975 John Henry Holland en la University of Michigan decidió
que para poder hacer sistemas adaptativos más robustos, que se desenvuelvan en ambi-
3.1. INTRODUCCIÓN A LOS ALGORITMOS BIOINSPIRADOS 29
entes cambiantes e inciertos y que sobre todo pudieran autoadaptarse a estos cambios,
propuso el proceso evolutivo como solución para estas problemáticas, es aśı que se
expone el enfoque de los algoritmos genéticos (AG) [Holland, 1975].
La década de los 70’s fue muy importante para el avance de los algoritmos evolutivos
ya que se logró avanzar en los estudios emṕıricos y en la teoŕıa, mejorando el desempeño
y aplicabilidad de los paradigmas mencionados anteriormente. Posteriormente en los
años en los años 80’s se esforzaron por mejorar todo lo relacionado a estos paradigmas, se
amplio la diversidad de aplicaciones y se generaron nuevas variantes de estos enfoques.
A partir de los años 90’s, surgen los primeros congresos de esta área, lo que permitió
aportaciones en conjunto, colaboraciones y discusiones sobre los nuevos temas, también
se acuña el término de Computo Evolutivo para darle una imagen a todos estos nuevos
paradigmas y surge el primer journal Evolutionary Computation del MIT press.
Siguiendo con las investigaciones en esta nueva rama de la IA en 1997 Rainer Storn
y Kenneth Price presentan el algoritmo de Evolución Diferencial (ED), el cual es un
algoritmo sencillo de implementar pero muy potente para buscar soluciones, este al-
goritmo se basa en obtener las diferencias entre los vectores de solución para guiar la
búsqueda y generar nuevos individuos utilizando la población actual aplicando dicha
diferencia [Price et al., 2005].
Posteriormente en el año 2002 [Passino, 2002] propone una nuevo algoritmo evolu-
tivo llamado B.F.O.A (Bacterial Foraging Optimization Algorithm), el cual trata de im-
itar el comportamiento de la bacteria E. Coli en el proceso de búsqueda, éste mismo algo-
ritmo posteriormente fue modificado en 2009 por [Mezura M. and Hernández O., 2009]
llamándolo M.B.F.O.A (Modified Bacterial Foraging Optimization Algorithm), cabe
menciar que esta última modificación es la que se implemento en este trabajo.
3.1.1 Inteligencia Colectiva
La inteligencia colectiva se basa en la teoŕıa colectiva la cual dice que un comportamiento
o una tarea espećıfica puede ser alcanzada gracias a la interacción de varios individuos,
es por esto que si se examina a una hormiga individualmente puede parecer torpe,
sin embargo al ver como interactúa una colonia de hormigas se puede percibir cierta
inteligencia, ya que responden rápida y efectivamente a su entorno. También se cree
30 CAPITULO 3. ALGORITMOS BIOINSPIRADOS
que un punto clave para que las colonias tengan este existo es que nadie se encuentra
a cargo, sino que todos cooperan por el bien común, inclusive cuando existen reinas
dentro de las colonias su función está limitada a poner huevos y no a dar órdenes a los
demásmiembros de las colonias [Miller, 2007].
A partir de observar este tipo de comportamientos Gerardo Beni, Suzanne Hack-
wood and Jing Wang, introducen el término de inteligencia colectiva en 1989 en el
contexto de sistemas robóticos celulares. Esto llevado al campo de la informática y
más espećıficamente al de la IA, la inteligencia colectiva se usa más para problemas
de optimización dónde la solución es no lineal o dif́ıcil de encontrar, es ah́ı donde este
tipo de algoritmos encuentran un lugar perfecto para ser utilizados. Una definición más
formal de inteligencia colectiva seŕıa la siguiente:
Los algoritmos de inteligencia colectiva con técnicas metaheuŕısticas de inteligen-
cia artificial, basadas en el estudio de los comportamientos colectivos observados
en la naturaleza. [Beni, 2005]
Algunos algoritmos de inteligencia colectiva son:
• 1. Ant Colony Optimization (ACO). Propuesto por Marco Dorigo en 1992.
• 2. Particle Swarm Optimization (PSO). Propuesto por Kennedy Eberhart en
1995.
• 3. Artificial Bee Colony (ABC) Algorithm . Propuesto por D. Karaboga en 2005
• 4. Bacterial Foraging Optimization Algorithm (BFOA). Propuesto por Passino
en 2002
El Ant Colony Optimization (ACO) se baso en en el comportamiento de una colo-
nia de hormigas para buscar caminos entre el hormiguero y la fuente de comida más
cercana, [Dorigo, 1992] propuso esta técnica para resolver problemas computacionales
relacionados con la búsqueda de caminos en grafos (ver Figura 3.1).
Cabe señalar que el algoritmo que se usa en éste trabajo (MBFOA) pertenece a esta
categoŕıa
3.1. INTRODUCCIÓN A LOS ALGORITMOS BIOINSPIRADOS 31
Figura 3.1: Representación artificial del algoritmo ACO, dónde se intenta emular la
forma en que las hormigas trazan los caminos entre el hormiguero y la comida.
3.1.2 Espacio de búsqueda
El espacio de búsqueda en problemas de optimización se refiere al dominio de la función
a ser optimizada 3.2. En otras palabras el espacio de búsqueda es un lugar geométrico
en un plano donde se pueden apreciar las posibles soluciones para un problema uti-
lizando una codificación dada. Cada punto en el espacio de búsqueda representa una
posible solución. A cada posible solución se le puede asociar un fitness o aptitud que
indicará que tan buena es la solución encontrada para el problema. Por ejemplo un
algoritmo genético (AG) devolverá la mejor solución de entre todas las posibles que
tenga en un momento dado [Santos and Duro, 2005].
Si suponemos que en el espacio de búsqueda presentado en la figura 3.2 la variables
de los ejes ”‘x”’ y ”‘y”’ son discretos y que sólo pueden tomar valores entre 1 y 40
quiere decir que por cada variable puede haber 40 valores que combinándolos con la
segunda variable seŕıan 1,600 posibles soluciones, de las cuales algunas tendrán una
mejor aptitud que otras.
Los algoritmos evolutivos son algoritmos de búsqueda en paralelo donde toda la
población explora al mismo tiempo el paisaje de calidad buscando el óptimo, es decir
cada individuo de la población será responsable de explorar un pequeño punto dentro
32 CAPITULO 3. ALGORITMOS BIOINSPIRADOS
Figura 3.2: Representación de un espacio de búsqueda para un problema bidimensional,
donde los ejes ”‘x”’ y ”‘y”’ representan la combinación de los genes y el eje ”‘z”’
representa la aptitud alcanzada
del paisaje de búsqueda, de esta manera es posible explorar más zonas dentro del
espacio de soluciones, pero simultáneamente a esto también trabaja la explotación del
espacio de búsqueda que se encarga de realizar evaluaciones en las proximidades de una
buena solución para encontrar una mejor posición del óptimo. Es por eso que cuando
se utilizan este tipo de algoritmos es importante equilibrar la exploración y explotación
del espacio de búsqueda.
A continuación se describen con más detalle los algoritmo a utilizar en este trabajo
que son: algoritmo genético, evolución diferencial y MBFOA.
3.2. ALGORITMO GENÉTICO 33
3.2 Algoritmo Genético
Como se ha mencionado anteriormente los AG’s están inspirados en la evolución natural
y fueron implementados por primera vez por Holland en 1975, con la finalidad de
abstraer y explicar los procesos adaptativos de los sistemas naturales y de esta manera
diseñar sistemas que contengan los mecanismos más importantes de su contra-parte
natural.
Algunas definiciones más formales sobre los AG seŕıan las siguientes:
Es un algoritmo matemático altamente paralelo que transforma un conjunto de
objetos matemáticos individuales con respecto al tiempo usando operaciones mod-
eladas de acuerdo al principio Darwiniano de reproducción y supervivencia del
más apto, y tras haberse presentado de forma natural una serie de operaciones
genéticas de entre las que destaca la recombinación sexual. Cada uno de estos
objetos matemáticos suele ser una cadena de caracteres (letras o números) de lon-
gitud fija que se ajusta al modelo de las cadenas de cromosomas, y se les asocia
con una cierta función matemática que refleja su actitud [Koza R., 1992].
Los algoritmos genéticos son algoritmos de búsqueda basados mecanismos de
selección natural y la genética, que combinan la supervivencia del más apto entre
estructuras en forma de cadenas de información, que intercambian información de
manera estructurada, pero también azarosa para buscar enriquecer la búsqueda.
En cada generación, un conjunto nuevo de individuos o cadenas de información es
creado a partir de pequeños cambios en ellos respecto a los individuos anteriores
o mediante la combinación de individuos anteriores [Goldberg, 1989].
Un algoritmo genético es aquel que empieza con un conjunto de uno o varios
individuos, a quienes les son aplicados operadores de selección y reproducción para
que evolucionen satisfactoriamente, mediante una cuantificación de su aptitud
conocida como función de adaptación que depende totalmente del problema que
se intenta atacar[Russell and Norvig, 2004].
Dentro de este enfoque se cuenta con 4 elementos principales que son: selección
de padres, cruza, mutación y reemplazo. El factor dominante es la cruza, en la que se
seleccionan a 2 o más individuos de la población (según sea el caso) a los que se les llama
34 CAPITULO 3. ALGORITMOS BIOINSPIRADOS
Figura 3.3: Ejemplo de representación genot́ıpica con su decodificación equivalente en
fenotipo
padres, para que intercambien sus materiales genéticos y aśı crear nuevos individuos
que serán los hijos.
Como se menciono en la sección anterior debe existir un balance entre la explotación
y la exploración del espacio de búsqueda, en el caso de los AG la exploración se asocia
con el operador de mutación, que generalmente tiene una baja probabilidad de ocurren-
cia, mientras que la explotación esta relacionada con la cruza y ésta ocurre con mucha
más frecuencia. Por lo que a la cruza se le considera un operador primario y la mutación
un operador secundario de los AG’s.
Además de esto otra cosa que es importante considerar es la manera de representar
las soluciones ya que puede ser a nivel genot́ıpico o a nivel fenot́ıpico. En la primera
representación los genes sólo pueden tomar valores de 0 y 1, mientras que en la repre-
sentación fenot́ıpica es la representación decimal del genotipo (generalmente para casos
de espacios continuos), esto puede apreciarse mejor en la figura 3.3, donde la repre-
sentación genot́ıpica se somete a un proceso de decodificación para obtener su valor
equivalente dentro del dominio de los números enteros [Nolfi and Floreano, 2000].
El algoritmo 1 muestra en pseudocódigo el funcionamiento general de un AG, los
mecanismos de selección son importantes porque estos elegirán a los individuos que
se les aplicará el proceso de reproducción. En un AG, existen diversos métodos para
aplicar este proceso de selección, uno de los más populares es el método de ruletaen
donde la probabilidad de selección es proporcional a la aptitud de cada individuo, de
esta manera los individuos más aptos tienen una mayor probabilidad de ser elegidos,
la probabilidad de elegir individuos menos aptos es lo que mantiene la diversidad de la
población ver figura 3.4. Otra opción es el llamado método por torneo que consiste
3.2. ALGORITMO GENÉTICO 35
Algoritmo 1 Algoritmo Genético Simple
Iniciar la población aleatoriamente
para Cada individuo de la población hacer
Calcular aptitud
fin para
repetir
Selección de padres
Cruza
Mutación
para Cada individuo de la población hacer
Calcular aptitud
fin para
Remplazo
Elitismo
hasta que Alcanzar una condición de paro
en elegir aleatoriamente un conjunto de posibles padres, de los cuales se elegirá al más
apto para reproducirse [Goldberg, 1989].
[Santos and Duro, 2005] dicen que los mecanismos de selección pueden clasificarse
a partir de la presión selectiva del mecanismo, ya que por ejemplo, si un mecanismo
tiene una alta presión selectiva, los individuos con una mayor aptitud serán selecciona-
dos, entonces los individuos más aptos terminaran dominando el proceso de selección,
provocando que los individuos con baja aptitud desaparezcan en unas cuantas gen-
eración, que puede representar una disminución importante en la riqueza selectiva de
los individuos, llevando al procesos evolutivo a caer en mı́nimos locales.
Otros operadores básicos de un AG son la cruza y la mutación. El operador de cruza
busca combinar los genes de los individuos seleccionados como padres, para generar hijos
que sean mejores soluciones que los padres, y aśı con el paso de generaciones hacer que
la población converja hacia las mejores soluciones. La cruza consiste en seleccionar uno
o más puntos de los padres y copiar los segmentos seleccionados en los hijos combinando
segmentos de ambos padres como lo ilustra la figura 3.9
36 CAPITULO 3. ALGORITMOS BIOINSPIRADOS
Figura 3.4: Ejemplo del método de selección por ruleta. (b) Ruleta que representa los
valores de la tabla (a).
Para el caso de la mutación existe un parámetro de probabilidad mutación que
indica el porcentaje con el que se aplicará éste operador a los nuevos individuos creados.
Aplicar éste operador consiste en cambiar aleatoriamente un gen del nuevo individuo,
cuando la cadena de genes es en genotipo lo que hace es cambiar el valor del gen por
su contraparte es decir si el valor del gen al que se le aplicará la mutación es 1 se
cambia por 0 y viceversa, en el caso de aplicar éste operador de manera fenot́ıpica de
igual manera se elige un gen al azar y cambia por un valor igualmente aleatorio que se
encuentre dentro de los limites permitidos [Nolfi and Floreano, 2000], como lo muestra
la figura 3.6
Por último para en el remplazo es donde se sustituyen los individuos de la generación
pasada por los nuevos individuos creados gracias a los operadores anteriores, este rem-
plazo es generacional lo que quiere decir que lo hijos recién creados reemplazaran por
completo a los padres sin importar si tienen un mejor aptitud o no, sin embargo dentro
de este proceso se puede aplicar un operador más el cual es el elitismo, que consiste
en conservar intacto al mejor o mejores (según sea el caso) individuos de cada gen-
eración e incluirlos en la generación siguiente. Esto es para que la población pueda
3.2. ALGORITMO GENÉTICO 37
Figura 3.5: Ejemplo del método de cruza para generar nuevos individuos.
Figura 3.6: Ejemplo del método de mutación aplicado en un nuevo individuo
38 CAPITULO 3. ALGORITMOS BIOINSPIRADOS
converger hacia el óptimo, es decir ayuda al algoritmo para encontrar el óptimo de una
mejor manera. [Rudolph, 1994] sugiere que el porcentaje de elitismo sea 1 por cada 100
individuos dentro de la población.
En el campo de la Robótica Evolutiva, los algoritmos genéticos son la herramienta
de optimización más popular, posiblemente por la facilidad en su implementación y
flexibilidad debido a que pueden trabajar tanto en fenotipo como en genotipo con una
sencillez moderada, esto es útil al trabajar con neuro-controladores más espećıficamente
con RNA’s porque dependiendo el caso se puede usar una codificación u otra. Otra
razón por la cual estos algoritmos son tan populares puede ser porque presentan un
buen desempeño al trabajar con neuro-controladores encontrado siempre una solución
adecuada al problema.
3.3 Evolución Diferencial
El algoritmo de evolución diferencial fue creado para la optimización en espacios contin-
uos. Nace de la idea de [Storn and Price, 1997] en su intento por resolver el polinomio
de Chebyshev. En la ED las variables se representan mediante números reales debido
a que fue propuesto para optimización con parámetros reales.
Desde su creación, gracias a su fácil implementación y robustez de búsqueda, la
ED ha destacado en diferentes competencias como por ejemplo la IEEE’s International
Contest on Evolutionary Optimization (ICEO) en los años 1996 y 1997. Es un método
de búsqueda directa en paralelo que utiliza vectores de parámetros NP D-dimensionales
como población por cada generación G. Al ser un algoritmo evolutivo éste también
trabaja con una población inicial generada aleatoriamente (cuando no se conoce nada
acerca del problema) sin embargo su mayor diferencia es que enfatiza la mutación, utiliza
un operador de cruce/recombinación a posteriori de la mutación, y la distribución de
éste operador no depende de una distribución de probabilidad predefinida, sino más
bien depende de la distribución de las soluciones actuales, lo cual parece ser una de sus
principales ventajas [Price, 1999].
3.3. EVOLUCIÓN DIFERENCIAL 39
3.3.1 Operadores de la ED
En la ED a los individuos dentro de una población se les conoce mayormente como
vectores, los pasos con los que trabaja este algoritmo son inicialización, mutación,
recombinación o cruza y selección.
Para inicializar la población primero se deben establecer los limites superior e infe-
rior para cada parámetro. Una vez especificados estos limites el dominio de las variables
del problema estará restringido entre valores mı́nimos y máximos. Los valores son rep-
resentados con las variable “b”, el sub́ındice “U” representa el valor mı́nimo que puede
tomar el parámetro y el sub́ındice “L” el mayor valor que puede tomar. Por ejemplo,
el valor inicial (g=0) del j-esimo parámetro del i-esimo vector seŕıa:
Xj ,i,0= randj(0, 1) ∗ (bj ,U − bj,L ) + bL
Donde “randj(0, 1)” devuelve un número aleatorio distribuido de manera uniforme
dentro del rango [0, 1), es decir 0 ≤ randj(0, 1) < 1. El sub́ındice, j, indica que un nuevo
valor aleatorio se genera para cada parámetro, y el sub́ındice i representa el ı́ndice de
la población, esto generará una población de NP individuos [Storn and Price, 1997].
La ED genera nuevos vectores de parámetros mediante la adición de la diferencia
entre dos vectores de la población a un tercer vector. A este paso se le conoce como
mutación. El algoritmo general para la ED se puede observar en el algoritmo 3
Una vez inicializada la población, la ED aplica la mutación. Primero se debe hacer
un proceso de selección, el cual es determinista, es decir cada vector “target” (padre)
generará un vector “trial” (hijo), y la selección de sobrevivientes también será determin-
ista puesto que sobrevive el individuo con mejor aptitud entre el “target” y el “trial”’.
De esta manera por cada vector “target”’ ( xi,G ,i = 1, 2, 3...NP ) se elegirán aleato-
riamente otros 3 vectores (ver figura 3.7) para generar un vector mutuante, es decir
es una diferencia aritmética entre un par de vectores (xr2, xr3), a esta diferencia se le
conoce como vector de perturbación. Una vez obtenido el vector de perturbación, un
tercer vector es seleccionado (xr1) también aleatoriamente y se le suma el vector de
perturbación escalado,