Algoritmos genéticos y robotica

Angie Katherinne Beltran Lamus

Jhon Estiben Cárdenas Fajardo

Escuela Tecnológica Instituto Tecnico Central

Faculta de Ingeniería Mecatrónica
Inteligencia Artificial
Bogotá D.C
2020
 Introducción

Los Algoritmos Genéticos o AG nacen de la necesidad como seres humanos de

experimentar los límites de nuestras creaciones o transformaciones como la tecnología.
Por eso se busca que el computador comprenda nuestro lenguaje y deseo, todo esto se
logra por medio de algoritmos. Estos algoritmos se desean cada vez mejorar, con el fin
de optimizar el procedimiento que pueda realizar, es por esto por lo que se quieren
igualar a la maquina más interesante: el ser humano.

Con base en lo anterior, se busca hacer una analogía entre el sistema de un ser humano
y de una maquina en ingeniería de computación, por tanto, los Algoritmos Genéticos se
basan en estructuras genéticas del ser humano como los cromosomas, el gen, el
genotipo, entre otros. Existen muchos operadores genéticos que ayudan a optimizar
procesos y problemas que se ven cotidianamente, como la búsqueda de rutas optimas,
optimización de circuitos, de sistemas de tuberías, por mencionar algunos.

En este documento, encontrará el desarrollo teórico para conceptualizar términos,

algunos operadores genéticos, algunas ventajas y desventajas, aplicaciones y la
implementación de un AG a un problema de ingeniería mecatrónica, como es el campo
de la robótica móvil
 Objetivos
Objetivo General
Investigar y aplicar los conceptos de Algoritmos Genéticos en una problemática de la
ingeniería mecatrónica.

Objetivos específicos
1. Investigar los conceptos básicos sobre el Algoritmos Genéticos.

2. Identificar una problemática en el área de la ingeniería mecatrónica donde se

pueda se puede hacer uso de Algoritmos Genéticos

3. Implementar Algoritmos Genéticos a la problemática

 Marco Teórico
¿Qué es un algoritmo genético?
Los algoritmos genéticos (AG) son considerados métodos adaptativos, generalmente
suele ser usados para solucionar problemas de búsqueda y optimización de parámetros,
los cuales están basados en la reproducción y los principios de supervivencia del más
apto (Gestal, Rivero, Rabuñal, Dorado, & Pazos, 2010).

De manera más formal siguiendo la definición dada por Goldberg, los AG se pueden
considerar algoritmos de búsqueda, los cuales se basan en la mecánica de selección
natural y de la genética natural. Combinan la supervivencia del más apto entre
estructuras que van en secuencia con un intercambio de información estructurada,
aunque aleatorizado, mediante el cual se puede construir un algoritmo de búsqueda que
este basado en las genialidades humanas(Goldberg, 1989).

Figura 1. Algoritmos genéticos y genética natural (UNAM, s.f.)

Esquema básico de un algoritmo genético

Todos los procesos de evolución biológica en la naturaleza se realizan de forma natural,
pero para lograr la aplicación del algoritmo genético en la resolución de problemas hay
que seguir una serie de pasos. La primera premisa es considerar el tamaño de la
población, esta debe ser lo suficientemente grande lo cual garantizara la diversidad de
soluciones, la población debe ser generada de forma aleatoria, si esta no es genera de
forma aleatoria se debe considerar la diversidad en la población (Arranz de la Peña &
Parra Truyol, 2007), lo pasos para el algoritmo genético son los siguientes:

• Evaluar la puntuación de cada uno de los individuos generados.

• Permitir la reproducción de los individuos siendo los más aptos los que tengan
más probabilidad de reproducirse.
• Con cierta probabilidad de mutación, mutar un gen del nuevo individuo generado.
• Organizar la nueva población.

En la Figura 2 se puede apreciar la estructura más simple de un algoritmo genético.

Figura 2 Estructura de un AG simple

(Arranz de la Peña & Parra Truyol, 2007)

Operadores de los algoritmos genéticos

Los algoritmos genéticos constan de los siguientes operadores genéticos para que su
funcionamiento sea el correcto:

Selección
Los algoritmos de selección son los encargados de escoger aquellos individuos que
tienen más probabilidad de reproducirse e identificar aquellos que no tienen la posibilidad
de reproducirse. Se trata de imitar lo que ocurre en la naturaleza por lo tanto se otorga
un mayor número de oportunidades a los individuos más aptos, sin embargo no se deben
eliminar por completo aquellos individuos que no sean aptos, puesto que en pocas
generaciones la población se volvería algo homogénea (Gestal, Rivero, Rabuñal,
Dorado, & Pazos, 2010).

Los algoritmos de selección pueden ser divididos en dos grandes grupos: probabilísticos
y determinísticos. Los dos tipos de algoritmos basan su funcionamiento en el principio
expresado con anterioridad “escoger una mayor cantidad de veces a los más aptos”. El
primer tipo adjudica estas posibilidades basado en el azar, en este grupo se encuentran
los algoritmos de selección por ruleta o por torneo, dado su importancia por ser los más
utilizados.

El segundo grupo contiene una serie de algoritmos dado el ajuste conocido de cada
individuo, se puede asignar a cada uno el número de veces que será escogido para
reproducirse, esto evitara problemas de predominancia de ciertos individuos, cada
algoritmo presenta una variación respecto al número de veces que se tomarán los
mejores y peores, se impondrá una presión en la búsqueda en el espacio de estados en
la zona donde se encuentra el mejor individuo (Gestal, Rivero, Rabuñal, Dorado, &
Pazos, 2010).

Selección por ruleta

A cada individuo de la población se le asignara una parte proporcional a su ajuste en la
ruleta, por lo cual la suma de todos los porcentajes sea igual a 1, los individuos más
aptos van a recibir una porción mayor en la ruleta, por lo general la población esta
ordenada en base al ajuste, basta con generar un número aleatorio entre 0 y 1 para
seleccionar un individuo.

Este método suele ser sencillo, pero algo ineficiente a medida que aumenta la población,
su complejidad es de 𝑂(𝑛2 ), otro problema que surge de este método es que el peor
individuo puede ser seleccionado en más de una ocasión (Pose, 2000).
 Figura 3 Ruleta de selección.
(Arranz de la Peña & Parra Truyol, 2007)

Selección por torneo

Este método consiste en seleccionar los individuos genéticos en base a comparaciones
entre sus genotipos, existen dos versiones para la selección mediante torneo:

• Determinístico
• Probabilístico

Para la versión determinística se va a seleccionar al azar un número p de individuos por

lo general se elige p=2, para los individuos seleccionados se toma el más apto el cual
pasara a la siguiente generación.

La versión probabilística se diferencia en el paso de la selección del ganador del torneo,

el lugar de escoger siempre al mejor se va a generar un numero aleatorio en un intervalo
de 0 a 1, si es mayor que el parámetro p (fijado para el proceso evolutivo) se tomara el
individuo más apto en caso contrario al menos apto, por lo general los valores para p se
dan entre 0.5 < 𝑝 ≤ 1, se tienen que variar el número de participantes en cada torneo
para modificar la precisión de selección, si participan varios individuos en un torneo los
menos aptos será los más descartados (Pose, 2000).

Selección jerárquica
En este tipo de selección, los individuos van a atravesar diferentes rondas de selección
en cada generación, en los primeros niveles las evaluaciones son más rápidas y menos
discriminatorias, aquellos que sobrevivan hasta los niveles más altos serán evaluados
rigurosamente. Este método posee la ventaja de reducir el tiempo total de cálculos
utilizando una evaluación menos selectiva para eliminar la mayoría de los individuos que
puedan ser poco o nada prometedores y sometiendo a los más aptos a un mayor análisis
(Arranz de la Peña & Parra Truyol, 2007).

Cruce
Luego de tener los individuos seleccionados, estos van a hacer recombinados para
generar una nueva decendencia, el cruce es una estrategia de reproducción tiene una
gran importación para la transición entre las generaciones, la tasa de cruce con las que
más se suele trabajar ronda entre el 90%

Existe una gran variación de algoritmos de cruce, la más empleados se explicarán a

continuación:

Cruce de 1 punto
Esta es la técnica más sencilla, luego de tener seleccionados dos individuos que tendrán
el papel de padres son recombinados por medio de la selección de un punto de corte,
para posteriormente intercambiar las secciones que se encuentran a la derecha de dicho
punto, es decir los genes del padre 1 a la izquierda del punto de corte forman parte del
hijo 1 y los situados a la derecha formaran parte del hijo 2, con el padre 2 sucederá lo
contrario (Arranz de la Peña & Parra Truyol, 2007).

Figura 4 cruce en un punto.

(Gestal, Rivero, Rabuñal, Dorado, & Pazos, 2010)

Cruce de 2 puntos
Este cruce el similar al anterior, pero se realiza para cada gen de los padres, en este
cruce los genes del padre 1 formaran parte del hijo uno y os genes impares formaran
parte del hijo 2, para el padre dos sucede el caso contrario .
 Figura 5 cruce en dos puntos.
(Gestal, Rivero, Rabuñal, Dorado, & Pazos, 2010)

Cruce uniforme
Este cruce es muy diferente a los dos anteriores, cada gen de la descendencia va a tener
las mismas probabilidades de pertenecer a uno u otro padre.

La técnica contiene la generación de una máscara para realizar el cruce con valores
binarios, si en una de las posiciones de la máscara hay un 1, el gen situado en esa
posición en uno de los descendientes se copia del primer padre, si por el contrario hay
un 0 el gen se copia del segundo padre, el segundo descendiente se intercambian los
papeles de los padres, o bien se intercambia la interpretación de los unos y ceros de la
máscara de cruce (Gestal, Rivero, Rabuñal, Dorado, & Pazos, 2010).

Como se puede apreciar en la Figura 5, la descendencia contiene una mezcla de genes

de cada uno de los padres.

Figura 6 cruce uniforme

(Gestal, Rivero, Rabuñal, Dorado, & Pazos, 2010)
Mutación
La mutación es considera uno de los operadores básicos, proporciona el elemento de
aleatoriedad en los individuos de la población, si bien se admite que el operador de cruce
será el responsable de efectuar la búsqueda a lo largo del espacio de posibles
soluciones, el operador de mutación es el responsable del aumento o reducción del
espacio de búsqueda dentro del algoritmo genético y del fomento de la variabilidad
genética de los individuos de la población. Existen varios métodos para aplicar la
mutación a los individuos de una población, pero el más comúnmente utilizado es el de
mutar un porcentaje de los genes totales de la población.

El porcentaje de genes a mutar se puede elegir de dos maneras, de forma fija,

especificando el mismo porcentaje de mutación a todas las generaciones del algoritmo
genético y de forma variable, variando el porcentaje de mutación de una generación a
otra, de esta forma se puede hacer una búsqueda más amplia y global al inicio y
reduciendo está en las siguientes generaciones (Arranz de la Peña & Parra Truyol, 2007).

Figura 7 Mutación simple

(Arranz de la Peña & Parra Truyol, 2007)

Evaluación de los algoritmos genéticos

Para evaluar el correcto funcionamiento de un AG se debe implementar un método el
cual indique si los individuos de la población representan o no buenas soluciones ante el
problema planteado, para cada tipo de problema que se desee resolver se derivara un
método. De esto se encargará la función evaluación la cual establece la medida
numérica, mediante la cual define la bondad de la solución, esta medida recibe el nombre
de ajuste y en mundo de los AG es empleada para controlar la aplicación de los
operadores genéticos, esta permitirá controlar el número de selecciones, cruces, copias,
mutaciones que se desarrollen (Gestal, Rivero, Rabuñal, Dorado, & Pazos, 2010),

Se pueden diferenciar 4 tipos de ajustes o fitness :

Fitness puro: 𝒓(𝒊, 𝒕)

Esta es la medida de ajuste establecida en la terminología natural del propio problema,
suponga una población de hormigas las cuales deben llevar la comida para el invierno,
la bondad de cada hormiga será el número de piezas de comida que lleven hasta el
hormiguero, la Ecuación 1 que representa este ajuste es la siguiente:

𝑁𝑐

𝑟(𝑖, 𝑗) = ∑|𝑠(𝑖, 𝑗) − 𝑐(𝑖, 𝑗)|

𝑗=1

(1)

Donde:

𝑟(𝑖, 𝑗) es la bondad del individuo i en la generación t

𝑠(𝑖, 𝑗) valor deseado para el individuo i en el caso j

𝑐(𝑖, 𝑗) valor obtenido por el individuo i en caso j

𝑁𝑐 número de casos

Fitness estandarizado 𝒔(𝒊, 𝒕)

Este es usado en problemas de maximización y minimización, para ello se modifica el
ajuste puro con la Ecuación 2.

𝑟(𝑖, 𝑡) 𝑚𝑖𝑛𝑖𝑚𝑖𝑧𝑎𝑐𝑖ó𝑛
𝑠(𝑖, 𝑡) = {
𝑟𝑚𝑎𝑥 − 𝑟(𝑖, 𝑡) 𝑚𝑎𝑥𝑖𝑚𝑖𝑧𝑎𝑐𝑖ó𝑛

(2)
Fitness ajustado 𝒂(𝒊, 𝒕)
El fitness ajustado toma valores siempre entre (0,1], entre más se aproxime el fitness
ajustado a 1 mayor será la bondad del individuo, se obtiene por la Ecuación 3.

1
𝑎(𝑖, 𝑡) =
1 + 𝑠(𝑖, 𝑡)

(3)

Fitness normalizado 𝒏(𝒊, 𝒕)

Los anteriores ajustes mencionados solo hacen referencia a la bondad que pueda
proporcionar el individuo, pero el fitness normalizado genera un nuevo aspecto, este va
a indicar la bondad de la solución con respecto a las demás soluciones presentadas en
la población se obtiene con la Ecuación 4 donde se considera una población de tamaño
M:

𝑎(𝑖, 𝑡)
𝑛(𝑖, 𝑡) =
∑𝑀
𝑘=1 𝑎(𝑘, 𝑡)

(4)

Ventajas y desventajas

Ventajas Desventajas
• Operan paralelamente y de • Desechan soluciones subóptimas
manera simultánea con • El lenguaje debe ser robusto capaces de
varias soluciones. tolerar cambios aleatorios
• Tienen la habilidad para • Si un individuo que es más apto que la
manipular muchos mayoría de sus competidores emerge
parámetros muy pronto en el curso de la ejecución,
simultáneamente se puede reproducir tan
• No se necesitan abundantemente que merme la
conocimientos específicos diversidad de la población demasiado
sobre el problema a resolver pronto.
Aplicaciones de AG

Las aplicaciones que pueden tener es un gran número. Sin embargo, a continuación, se
nombran algunas de las más destacables.

• Hidráulica: Muchas veces se presentan fugas debido a altas presiones y

presentan rupturas, como solución se instalan válvulas reductoras de presión,
donde se debe conocer cuantas son requeridas y su respectiva posición. El AG
es una codificación binaria con individuos de una longitud igual al número de
tubos, donde un cero significa la ausencia de válvula y 1 la presencia de esta. por
tanto, se requería tener la mínima cantidad de unos.
• Plegado de proteínas: Es muy estudiado por cristalización de proteínas, pero hay
algunas que no se pueden estudiar este modelo, por tanto, se busca predecir su
conformación de manera matemática y de optimización, clasificando hidrofóbico o
polar.
• Optimización de portafolios: involucra crecimiento económico de un inversionista,
consiste en la asignación eficiente de capital, donde se busca minimizar el riesgo
sin exceder el capital para alcanzar determinado rendimiento. Su codificación esta
dado por el número de activos (na) y un numero de bits que representa el capital
a invertir por cada activo.
• Problema del agente viajero: Encuentra la ruta que recorra todos los puntos de
una red pasando solo una vez por ellos, se suele aplicar en problemas de ruteo o
logística, es un problema NP que minimiza la distancia de recorrido.

Figura 8. Agente viajero (UNAM, s.f.)

Algoritmos Genéticos aplicado a ingeniería mecatrónica

Una de las áreas de aplicación de la ingeniería mecatrónica es en la robótica, para aplicar

un AG, particularmente se ha enfocado en la robótica móvil, donde se busca partir de un
inicio hasta llegar a una meta por el camino mas optimo, con el fin de ahorrar tiempo y
energía. En la Figura 9, se puede observar los obstáculos en negro, el cual debe evitar
el robot, y unas secciones dadas verticalmente por los vértices de los obstáculos. Existen
algunos métodos y operadores de solución mediante algoritmos como son los de fuerza
bruta, el método del vecino más cercano y el cruce.

Figura 9. Obstáculos entre inicio y llegada.

La cantidad de rutas posibles está determinada por

(𝑛 − 1)!

Este es un símil del problema del agente viajero o TSP, donde se requiere hacer un
trayecto donde no se debe pasar por un nodo más de una vez.

Cuando se aplica el método de fuerza bruta, se buscan todos los recorridos posibles, es
un método muy básico. Por su parte, el método del vecino mas cercano, que tiene un
calculo muy eficiente, donde se evalúa el nodo de partida y va seleccionando sus nodos
más cercanos
 Figura 10. Red de nodos para llegar de 7 a 15. Fuente propia

Teniendo 18 nodos, se tiene que las rutas posibles son:

(𝑛 − 1)! = 17! = 3.55 𝑥 1014

Método de Fuerza Bruta

En este método se exploran todas las rutas que pueda haber. A partir de la Figura 10 se
encuentran que hay las siguientes rutas:

• 7-8-9-10-14-17-18-15
• 7-8-9-10-14-13-15
• 7-8-9-10-14-15
• 7-8-9-6-4-11-12-13-15
• 7-8-9-6-4-11-12-13-15
• 7-8-9-6-4-11-12-14-15
• 7-8-9-6-4-11-12-13-14-15
• 7-8-9-6-4-11-12-13-14-15
• 7-1-2-3-4-11-12-13-15
• Entre otras

Método del vecino más cercano

Para esto se debe dar algunos pesos para cada arco y así evaluar cual es el camino mas
cercano, con el fin de ahorrar tiempo y energía, que suele ser vital en dispositivos
móviles.

Operador de cruce

Basado en la combinación de arcos se toma el nodo inicial: 7, como el de referencia de

la Figura 10. Se toma al azar uno de los dos padres, el 8 o el 1. Suponiendo que se toma
el primero, ahora llego al nodo 9 donde debo decidir que nodo tomar como referente,
dependiendo del que tenga menor numero de arcos, entonces continuaría en 10, luego
14. Alli encuentra que hay tres rutas que tienen la misma cantidad de arcos (dos) por
tanto se elegiría uno al azar, con suerte será el del noto final que es el 15, resultando la
ruta más optima la de la Figura 11, donde se tiene 7-8-9-10-14-15
Figura 11. Ruta más óptima encontrada
Conclusiones

• Los algoritmos genéticos, ayudan a optimizar muchos procesos y en la ingeniería

mecatrónica se puede dar en procesos como control y robótica.
• En algunas ocasiones hay suboptimizaciones que pueden no tenerse en cuenta,
lo que juega en contra de un AG, puesto que puede que se requiera otra u otras
soluciones.
• Los diversos métodos AG ofrecen una variedad de aplicaciones y formas de
implementación, lo que puede ayudar muchos problemas por diversos operadores
genéticos.
• Se pudo aplicar un AG para dar solución a un problema de robótica móvil
 Bibliografía
Arranz de la Peña, J., & Parra Truyol, A. (2007). Algoritmos genéticos. Universidad Carlos
III.

Gestal, M., Rivero, D., Rabuñal, J. R., Dorado, J., & Pazos, A. (2010). Introducción a los
Algoritmos Genéticos y la Programación Genética. Universidade da Coruña.

Pose, M. G. (2000). Introducción a los Algoritmos Genéticos. Departamento de

Tecnologías de la Información y las Comunicaciones Universidad de Coruña.

UNAM. (s.f.). Apliaciones de algoritmos genéticos. Obtenido de

https://www.coursera.org/lecture/computo-evolutivo/aplicaciones-de-algoritmos-
geneticos-oYUSU