MICRO-ALGORITMO GENÉTICO EN INGENIERÍA

M. en C. José Eduardo Cardoza Plata
Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.

Dr. Mauricio Olguín Carbajal
Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.

Dr. Juan Carlos Herrera Lozada
Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.

Instituto Politécnico Nacional
Centro de Innovación y Desarrollo Tecnológico en Cómputo

Resumen

Los Algoritmos Evolutivos son un conjunto de técnicas heurísticas, procedimientos de búsqueda, optimización y aprendizaje, cuyo modelo se obtiene del mecanismo de selección natural y las teorías de la evolución, basadas en el paradigma Neo-Darwiniano que aplica sobre esquemas poblacionales, particularmente el comportamiento de la herencia genética y la dominancia genética inspiraron el micro-algoritmo genético presente en este trabajo, buscando al mejor individuo (solución óptima) quien ha evolucionado sus aptitudes de supervivencia heredando los mejores genes a través de varias generaciones.

I. Introducción

Desde la antigüedad la humanidad ha construido máquinas y buscado soluciones para facilitar las tareas cotidianas, hasta nuestros días donde grandes computadoras resuelven complejos problemas. Es por ello que en el área de la inteligencia artificial se buscan técnicas o estrategias que encauzan la búsqueda de soluciones ante grandes espacios de problemas, a esto se le conoce como búsqueda heurística.

Ante enormes espacios de búsqueda, donde los caminos a las posibles soluciones se ramifican como un árbol, seguir una única ruta puede resultar poco útil al llegar a una solución no satisfactoria, por su parte, explorar cada uno de los caminos resulta en una gran inversión de tiempo y pérdida de recursos. Es por ello que los algoritmos, como el aquí presentado, resultan de gran utilidad para optimizar el proceso de búsqueda explorando diversas soluciones posibles.

II. Descripción del algoritmo

Un algoritmo es una serie de pasos o procedimientos a seguir para resolver un problema o realizar una determinada tarea. Particularmente los algoritmos genéticos se utilizan dentro del área de Inteligencia artificial en el ámbito de optimización, manipulando simultáneamente un conjunto de soluciones potenciales a un problema dado el cual se busca maximizar o minimizar.

Al hablar de genética nos adentramos en una amplia área de la biología que busca comprender y explicar el funcionamiento de la herencia biológica, de padres a hijos, a través de generaciones mediante el ADN y los genes que los conforman, de ahí el término genética (estudio de genes). Los genes, pueden ser de diferentes formas las cuales se denominan alelos, por ejemplo para el caso del gen de la semilla de la planta de chícharo este tiene dos alternativas ser liso o rugoso, por lo tanto un alelo representa la característica liso(A) y otro para la característica rugoso(a). En este punto entra el término de dominancia genética. La dominancia es una relación entre los alelos de un mismo gen en el que uno enmascara al otro (el dominante al recesivo) siendo este un concepto clave en las leyes de Mendel y la genética clásica. La segunda ley de Mendel: principios de segregación, mostrada en la figura 1, describe perfectamente este comportamiento.

Figura 1. Segunda ley de Mendel.

Dado un problema matemático el cual se busca optimizar (minimizar o maximizar) y un conjunto de soluciones candidatas, a las cuales llamaremos cromosomas (conjunto de genes estructurados), comúnmente generados de manera pseudoaleatoria, los cuales son evaluados a través de una métrica función objetivo o función de aptitud la cual nos posibilita evaluar cuantitativamente, permitiéndonos saber que tan apto son, es decir, en qué posición del espacio de búsqueda y a que distancia del optimo global se encuentran. La función de aptitud ejerce como el medio ambiente sobre los individuos (cromosomas) los cuales son incitados a la evolución, de acuerdo a las teorías darwinistas, para que su especie no perezca en la selección natural.

Al principio del algoritmo se genera una población aleatoria de 5 individuos, la cual es evaluada con base en su aptitud, para posteriormente entrar a un proceso de cruza, donde los individuos más aptos se reproducirán más veces, también aportaran los alelos dominantes en la recombinación genética a sus progenitores, conformando tanto padres como hijos una nueva población, la cual es reevaluada, seleccionando a los dos mejores individuos (selección natural). Estos individuos junto con otros 3 seleccionados aleatoriamente (deriva genética), serán los sobrevivientes a la autorregulación donde la población regresa a su tamaño original. El proceso se repite cíclicamente hasta alcanzar la convergencia nominal, en donde, mediante un proceso de elitismo se seleccionan a los dos mejores individuos de la última población, los cuales junto con 3 nuevos individuos generados aleatoriamente integraran la nueva población que entrara al principio del algoritmo conformando así un segundo bucle con una condición de parada establecida en la convergencia general, al término de la cual tendremos al mejor individuo posible, resultado de la herencia genética a través de varias generaciones, y por lo tanto, la mejor solución posible. En la última etapa donde se introducen nuevos individuos totalmente aleatorios, se le conoce como ruido estocástico, el cual ayuda a mantener la diversidad en la población, escapando así de una convergencia prematura y evitando quedar atrapados en óptimos locales, mientras que el elitismo nos permite escalar sobre las mejores soluciones en búsqueda un óptimo global. Se debe mantener un balance entre la diversidad proporcionada, es decir, la exploración y la explotación del micro-algoritmo. La explotación es el proceso de usar la información obtenida de las soluciones exploradas previamente para determinar hacia cuales es más conveniente continuar avanzando, mientras que, la exploración es el proceso de visitar nuevas regiones del espacio de búsqueda (nuevas soluciones) para ver si se puede encontrar algo prometedor.

Figura 2. Micro-algoritmo Genético.

III. Pruebas y resultados

Para la fase de experimentación, se utilizó el micro-AG en representación binaria, para resolver el problema del MAX-ONE cuya función está dada por:

En donde dichos algoritmos estocásticos buscan una solución tal que en donde que maximice . N representa el número de bits de una cadena (vector), por lo que el máximo se obtendrá cuando los N bits de la cadena sean unos.

Las pruebas realizadas en esta fase utilizan cadenas de 8, 16 y 32 bits respectivamente y trabajan con una población fija de 5 individuos. Dichas pruebas se realizaron en un portátil con un procesador core i5-6300HQ a 2.3GHz, con 8GB de RAM. También se utilizó la ya mencionada plataforma de hardware RaspberryPi en su versión 3 modelos B, la cual cuenta con un procesador quad-core a 1.2GHz ARMv8 con 1 GB de RAM.

Figura 4. Grafica del comportamiento del algoritmo.

Como podemos apreciar en la figura 4, en la población inicial existe un cromosoma con aptitud de 16 bits en uno, siendo 32 bits en uno la aptitud ideal para el problema de MAX-ONE. Los cromosomas presentan una evolución constante, a tal grado que, al cabo de 10 generaciones el mejor de ellos presenta una aptitud de 26 bits en uno. A partir de este punto notamos que la gráfica se convierte en una pendiente cada vez más inclinada reduciendo los avances en la aptitud de los cromosomas a través de las generaciones, lo cual se puede apreciar en la generación 40 cuyo mejor cromosoma tiene una aptitud de 31 bits en uno y al paso de 35 generaciones más, sumando en total 75 generaciones, cuando se alcanzó una afinidad ideal de 32 bits en uno.

IV. Conclusiones

La búsqueda de la mejor solución o una suficientemente buena de una amplia gama de soluciones potenciales, resulta interesante para los algoritmos bioinspirados, siendo el micro-algoritmo genético presentado una técnica heurística eficiente ante este tipo de problemas. Mostrando una gran convergencia inicial y dando grandes saltos hacia lo desconocido, en una amplia fase de exploración evitando quedar atrapados en un óptimo local. Es por ello que la última etapa de la búsqueda es más exhaustiva y amplia involucrando un gran número de generaciones para conseguirlo.

V.Referencias

1. J.C. Herrera (2011). Sistema Inmune Artificial con Población Reducida para Optimización Numérica Centro de Investigación en Computación Instituto Politécnico Nacional, Distrito Federal, México.


2. A. Leon (2009). Diseño e implementación en hardware de un algoritmo bio-inspirado Centro de Investigación en ComputaciónInstituto Politécnico Nacional, Distrito Federal, México.


3. N. Cruz (2004). Sistema inmune artificial para solucionar problemas de optimizaciónTesis DoctoralCINVESTAV‐ IPN. México.