Empecemos con la famosa cita de Charles Darwin: “No es la más fuerte de las especies la que sobrevive, ni la más inteligente, sino la que más se adapta al cambio”. Todo el concepto de los Algoritmos Genéticos se basa en esta cita.
Los Algoritmos Genéticos son una técnica de optimización inspirada en la búsqueda basada en el principio de la selección natural de Darwin. Se trata de una novedosa técnica de Inteligencia Artificial introducida en la década de 1970. Esto tiene la capacidad de resolver preguntas que no pueden ser resueltas de otras técnicas como las Redes Neuronales Artificiales.
Los Algoritmos Genéticos son algoritmos basados en búsquedas basadas en los conceptos biológicos de selección natural y genética. Los Algoritmos Genéticos son un subconjunto de una rama mucho más profunda de la computación conocida como Computación Evolutiva.
En los Algoritmos Genéticos, tenemos una reserva o una población de posibles soluciones a un problema dado. Estas soluciones se someten entonces a algunas operaciones genéticas, produciendo nuevos hijos y el proceso se repite a lo largo de varias generaciones. A cada individuo, o solución candidata, se le asigna un valor de aptitud basado en un valor de función de evaluación y a los individuos más aptos se les da una mayor oportunidad de aparearse y producir más individuos más aptos. Esto está en línea con la teoría Darwiniana de la “supervivencia de los más fuertes”. De esta manera, seguimos evolucionando mejores individuos o soluciones a lo largo de generaciones, hasta que llegamos a un criterio de terminación.
Algoritmos Evolutivos
La tarea principal que realizan los algoritmos evolutivos es la optimización. La diferencia entre los algoritmos tradicionales y los algoritmos evolutivos es que los algoritmos evolutivos son dinámicos y, por lo tanto, pueden evolucionar con el tiempo y pueden utilizarse eficazmente para representar información que cambia con frecuencia.
Los algoritmos evolutivos tienen tres características principales:
- Basado en la población: los algoritmos evolutivos tienen por objeto optimizar un proceso en el que el conjunto actual de soluciones es malo o no óptimo para generar nuevas, mejores u óptimas soluciones. El conjunto de soluciones actuales a las que aquí se hace referencia se denomina población.
- Orientado al fitness: existe un valor de fitness o aptitud asociado a cada solución individual que se calcula a partir de una función de fitness. Este valor de fitness refleja hasta qué punto la solución es buena.
- Función de la variación: si no hay una solución aceptable en la población actual de acuerdo con la función de fitness calculada a partir de cada individuo, deberíamos hacer una adaptación para generar nuevas y mejores soluciones. Como resultado, las soluciones individuales sufrirán una serie de variaciones, simplemente iteraciones para generar nuevas soluciones.
Terminología básica
Los Algoritmos Genéticos se encuentran dentro de los siguientes términos básicos, con los que debes estar familiarizado.
- Población: es un subconjunto de todas las soluciones posibles, codificadas, para un problema dado. Simplemente, este es el conjunto de individuos y cada individuo es una solución al problema que queremos resolver.
- Cromosomas: es una de esas soluciones al problema en cuestión.
- Gen: es la posición de un elemento de un cromosoma. Los individuos de una población se caracterizan por un conjunto de parámetros, variables y son particulares, denominados genes. Básicamente, los genes se unen en una cadena para formar un cromosoma, solución.
- Alelo: es el valor que toma un gen para un cromosoma en particular.
Noción de selección natural
El proceso de selección natural comienza con la selección de los individuos más aptos de una población. Producen descendencia que hereda las características de los padres y que será añadida a la siguiente generación. Si los padres tienen un mejor estado físico, sus hijos serán mejores que los padres y tendrán una mejor oportunidad de sobrevivir. Esto proceso continúa iterando y al final, una generación con los individuos más aptos será encontrada.
Esta noción puede aplicarse a un problema de búsqueda. Consideramos un conjunto de soluciones para un problema y seleccionamos el conjunto de las mejores de ellas.
El funcionamiento de un algoritmo genético también se deriva de la biología y se divide en los siguientes 5 pasos.
- Población inicial
- Función fitness
- Selección
- Cruce
- Mutación
Por lo tanto, tratemos de entender los pasos uno a uno.
Población Inicial
El proceso comienza con un conjunto de individuos que se llama población. Cada individuo es una solución al problema que desea resolver.
Un individuo se caracteriza por un conjunto de parámetros, variables, conocidos como genes. Los genes se unen en una cadena para formar un cromosoma, solución.
En un Algoritmo Genético, el conjunto de genes de un individuo se representa mediante una cadena, en términos de un alfabeto. Normalmente se utilizan valores binarios, cadena de 1 y 0. Decimos que codificamos los genes en un cromosoma.
Es importante que las soluciones en la población inicial sean creadas con genes asignados aleatoriamente, para tener un alto grado de variación genética.
Función fitness
En este paso, el algoritmo debe ser capaz de determinar qué es lo que hace que una solución sea más adecuada que otra solución. Esto se determina por la función fitness o de aptitud. El objetivo de la función es evaluar la viabilidad genética de las soluciones dentro de la población, colocando a aquellos con los rasgos genéticos más viables, favorables y superiores a la cabeza de la lista.
Para las diferentes tareas, la función fitness se somete a ligeras modificaciones. Sin embargo, en esencia, su función principal es desempeñar el papel de diferenciador en la población que separa a los estudiantes más fuertes de los más débiles.
Selección
Durante cada generación sucesiva, una proporción de la población existente es seleccionada para criar una nueva generación. Las soluciones individuales se seleccionan a través de un proceso basado en la función fitness, en el que las soluciones más adecuadas suelen ser las que más se seleccionan.
Ciertos métodos de selección califican la idoneidad de cada solución y seleccionan preferentemente las mejores soluciones. Otros métodos clasifican solo una muestra aleatoria de la población, ya que este proceso puede llevar mucho tiempo. La mayoría de las funciones son estocásticas y están diseñadas para que se seleccione una pequeña proporción de soluciones menos adecuadas. Esto ayuda a mantener la diversidad de la población a un nivel elevado, lo que impide la convergencia prematura hacia soluciones deficientes. Los métodos de selección más populares y bien estudiados incluyen la selección de la rueda de la ruleta y la selección de torneos.
Cruce
En el paso anterior, hemos seleccionado los cromosomas padres que producirán descendientes. Así que, en términos biológicos, el cruce no es más que reproducción.
El tipo más común es el cruce de punto único. En el cruce de un solo punto, se elige un lugar en el que se intercambian los alelos restantes de un progenitor al otro. Esto es complejo y se entiende mejor visualmente.
Como puedes observar, los niños toman una sección del cromosoma de cada padre. El punto en el que se rompe el cromosoma depende del punto de cruce seleccionado al azar. Este método en particular se llama cruce de punto único porque solo existe un punto de cruce. A veces solo se crea al niño 1 o al niño 2, pero a menudo ambas crías son creadas y puestas en la nueva población.
Sin embargo, el cruce no siempre ocurre. A veces, en base a un conjunto de probabilidades, no se produce ningún cruce y los padres se copian directamente a la nueva población. La probabilidad de que ocurra un cruce es generalmente del 60% al 70%.
Mutación
Después de la selección y el cruce, ahora se tiene una nueva población llena de individuos. Algunos se copian directamente y otros se producen por el cruce. Para asegurar que los individuos no son todos exactamente iguales, se permite una pequeña posibilidad de mutación.
Se hace un bucle a través de todos los alelos de todos los individuos, y si ese alelo es seleccionado para la mutación, puede cambiarlo por una pequeña cantidad o reemplazarlo con un nuevo valor. La probabilidad de mutación suele estar entre 1 y 2 décimas de porcentaje. La mutación es bastante simple. Solo tienes que cambiar los alelos seleccionados en función de lo que consideres necesario y seguir adelante. Sin embargo, la mutación es vital para asegurar la diversidad genética en la población.
Terminación
Este proceso generacional se repite hasta que se alcanza una condición de terminación. Las condiciones comunes de terminación son:
- Se encuentra una solución que satisface los criterios mínimos
- Número fijo de generaciones alcanzadas.
- Se ha alcanzado el presupuesto asignado.
- La solución de mayor rango del modulo fitness es alcanzar o ha alcanzado un nivel tal que las iteraciones sucesivas ya no producen mejores resultados.
- Inspección manual.
- Cualquier combinación de las anteriores.
Proceso básico de un Algoritmo Genético
La estructura básica de un Algoritmo Genético es la siguiente.
El proceso debe iniciarse con una población inicial, que puede ser generada al azar o sembrada por otras heurísticas. Luego, usando la función de evaluación, los padres son seleccionados de esta población para el apareamiento. Luego se aplican operadores de cruce y mutación a los padres para generar nuevas crías. Finalmente, estas crías reemplazan a los individuos existentes en la población y el proceso se repite. Así es como los Algoritmos Genéticos imitan realmente la evolución humana.
Limitaciones de los Algoritmos Genéticos
Como cualquier técnica científica, los Algoritmos Genéticos también sufren de algunas limitaciones. Estos incluyen:
- No apto para todos los problemas, especialmente los problemas que son simples y para los que se dispone de información derivada.
- El valor del modulo fitness se calcula repetidamente, lo que puede resultar costoso para algunos problemas.
- La necesidad de computadoras con alta potencia y capacidad de procesamiento. Ya que se necesita mucho espacio para almacenar el aumento de la población cuando se ejecuta un Algoritmo Genético.
- Toma más tiempo para producir un resultado si no hay suficiente potencia de procesamiento y capacidad informática.
- Al ser estocástico, no hay garantías sobre el óptimo o la calidad de la solución.
- Si no se implementan correctamente, los Algoritmos Genéticos pueden no converger hacia la solución óptima.
Aplicaciones de los Algoritmos Genéticos
Los Algoritmos Genéticos se utilizan principalmente en problemas de optimización, pero también se utilizan con frecuencia en otras áreas de aplicación. A continuación, se presentan algunas de las áreas en las que se utilizan frecuentemente los Algoritmos Genéticos.
- Optimización: los Algoritmos Genéticos se utilizan más comúnmente en problemas de optimización en los que tenemos que maximizar o minimizar un valor de función de evaluación dado bajo un conjunto dado de restricciones.
- Redes neuronales artificiales: para entrenar redes neuronales, principalmente redes neuronales recurrentes.
- Sector financiero: los Algoritmos Genéticos son los más utilizados para encontrar los mejores valores de combinación de parámetros en una regla de negociación y pueden ser incorporados en los modelos de redes neuronales artificiales diseñados para seleccionar acciones e identificar operaciones.
- Economía: caracterizar varios modelos económicos como el precio de activos, resolución de equilibrio de la teoría de juegos, etc.
- Paralelización: los Algoritmos Genéticos tienen muy buenas capacidades paralelas y demuestran ser un medio muy eficaz para resolver ciertos problemas y también proporcionan una buena área para la investigación.
- Procesamiento de imágenes: se utilizan para varias aplicaciones de procesamiento de imágenes digitales como la correspondencia de píxeles densos.
- Programación: se utilizan para resolver varios problemas de programación, por ejemplo, el problema de la programación de horarios.
- Análisis de ADN: para determinar la estructura del ADN usando datos espectrométricos sobre la muestra.
- Generación de trayectorias de robot: para planificar la trayectoria que toma un brazo de robot moviéndose de un punto a otro.
- Diseño paramétrico de aeronaves: diseñar aeronaves variando los parámetros y desarrollando mejores soluciones.
Con esto finalizamos la explicación. Ya tienes una base de lo que se tratan los Algoritmos Genéticos, por lo tanto te dejo la siguiente pregunta, ¿Cuáles de las siguientes afirmaciones crees tú que sea cierta?
Opción 1: Los Algoritmos Genéticos forman parte de la Computación Evolutiva.
Respuesta Correcta.
Opción 2: La estructura básica de los Algoritmos Genéticos son 5 pasos que se ejecutan una sola vez.
Respuesta Incorrecta. El proceso generacional se repite hasta que se alcanza una condición de terminación definida previamente.
Opción 3: Los Algoritmos Genéticos necesita computadoras con alta potencia y capacidad de procesamiento.
Respuesta Correcta.
