Un algoritmo es una serie de pasos organizados que describe el proceso que se debe seguir, para dar solución a un problema específico.
En los años 1970, de la mano de John Henry Holland, surgió una de las líneas más prometedoras de la inteligencia artificial, la de los algoritmos genéticos, (AG). Son llamados así porque se inspiran en la evolución biológica y su base genético-molecular.
Estos algoritmos hacen evolucionar una población de individuos sometiéndola a acciones aleatorias semejantes a las que actúan en la evolución biológica (mutaciones y recombinaciones genéticas), así como también a una selección de acuerdo con algún criterio, en función del cual se decide cuáles son los individuos más adaptados, que sobreviven, y cuáles los menos aptos, que son descartados.
Los algoritmos genéticos se enmarcan dentro de los algoritmos evolutivos, que incluyen también las estrategias evolutivas, la programación evolutiva y la programación genética.
Los algoritmos genéticos (AG) funcionan entre el conjunto de soluciones de un problema llamado fenotipo, y el conjunto de individuos de una población natural, codificando la información de cada solución en una cadena, generalmente binaria, llamada cromosoma. Los símbolos que forman la cadena son llamados genes. Cuando la representación de los cromosomas se hace con cadenas de dígitos binarios se le conoce como genotipo. Los cromosomas evolucionan a través de iteraciones, llamadas generaciones. En cada generación, los cromosomas son evaluados usando alguna medida de aptitud. Las siguientes generaciones (nuevos cromosomas), son generadas aplicando los operadores genéticos repetidamente, siendo estos los operadores de selección, cruzamiento, mutación y reemplazo.
Los algoritmos genéticos son de probada eficacia en caso de querer calcular funciones no derivables (o de derivación muy compleja) aunque su uso es posible con cualquier función.
Deben tenerse en cuenta también las siguientes consideraciones:
Un algoritmo genético puede presentar diversas variaciones, dependiendo de cómo se decide el reemplazo de los individuos para formar la nueva población. En general, el pseudocódigo consiste de los siguientes pasos:
Entre otras podemos mencionar:
En un algoritmo genético, una población de soluciones candidatas (llamadas individuos, criaturas o fenotipos) a un problema de optimización se desarrolla hacia mejores soluciones. Cada solución candidata tiene un conjunto de propiedades (sus cromosomas o genotipos) que pueden ser mutados y alterados. Tradicionalmente, las soluciones se representan en binario como cadenas de ceros y unos, pero también son posibles otras codificaciones.
La evolución suele partir de una población de individuos generados al azar, y es un proceso iterativo, con la población en cada iteración llamada generación. En cada generación, se evalúa la aptitud de cada individuo en la población. La aptitud suele ser el valor de la función objetivo en el problema de optimización que se está resolviendo. Los individuos más aptos son seleccionados estocásticamente de la población actual, y el genoma de cada individuo es modificado (recombinado y posiblemente mutado al azar) para formar una nueva generación. La nueva generación de soluciones candidatas se utiliza entonces en la siguiente iteración del algoritmo. Comúnmente, el algoritmo termina cuando se ha producido un número máximo de generaciones, o se ha alcanzado un nivel de aptitud satisfactorio para la población.
Un algoritmo genético típico requiere:
Una representación estándar de cada solución candidata es como una matriz de bits. Las matrices de otros tipos y estructuras se pueden utilizar esencialmente de la misma manera. La propiedad principal que hace convenientes estas representaciones genéticas es que sus partes son fácilmente alineadas debido a su tamaño fijo, lo que facilita las operaciones de cruce simple. También se pueden usar representaciones de longitud variable, pero la implementación del entrecruzamiento cromosómico es más compleja en este caso. Las representaciones arborescentes se exploran en la programación genética y las representaciones en forma de gráfico se exploran en la programación evolutiva. Una mezcla de ambos cromosomas lineales y árboles se explora en la programación de expresión genética.
Una vez que se define la representación genética y la función de aptitud, un AG procede a inicializar una población de soluciones y luego a mejorarla mediante la aplicación repetitiva de los operadores de mutación, entrecruzamiento cromosómico, inversión y selección.
El tamaño de la población depende de la naturaleza del problema, pero normalmente contiene varios cientos o miles de posibles soluciones. A menudo, la población inicial se genera aleatoriamente, permitiendo toda la gama de posibles soluciones (el espacio de búsqueda). Ocasionalmente, las soluciones pueden ser "sembradas" en áreas donde es probable encontrar soluciones óptimas.
Durante cada generación sucesiva, una parte de la población existente se selecciona para criar una nueva generación. Las soluciones individuales se seleccionan a través de un proceso basado en la aptitud, donde las soluciones de acondicionamiento (como medido por una función de acondicionamiento físico) son típicamente más probables de ser seleccionadas. Ciertos métodos de selección evalúan la aptitud de cada solución y preferentemente seleccionan las mejores soluciones. Otros métodos califican solo a una muestra aleatoria de la población, ya que el proceso anterior puede llevar mucho tiempo.
La función de fitness se define sobre la representación genética y mide la calidad de la solución representada. La función de acondicionamiento físico depende siempre del problema. Por ejemplo, en el problema de la mochila se quiere maximizar el valor total de los objetos que se pueden poner en una mochila de alguna capacidad fija. Una representación de una solución puede ser una matriz de bits, donde cada bit representa un objeto diferente, y el valor del bit (0 o 1) representa si el objeto está o no en la mochila. No todas las representaciones son válidas, ya que el tamaño de los objetos puede exceder la capacidad de la mochila. La aptitud de la solución es la suma de valores de todos los objetos en la mochila si la representación es válida, o 0 de lo contrario.
En algunos problemas, es difícil o incluso imposible definir la expresión de la condición física. En estos casos, se puede utilizar una simulación para determinar el valor de la función de aptitud de un fenotipo (por ejemplo, la dinámica de fluidos computacional se usa para determinar la resistencia al aire de un vehículo cuya forma se codifica como fenotipo) o incluso algoritmos genéticos interactivos.
El siguiente paso es generar una población de segunda generación, de soluciones de las seleccionadas a través de una combinación de operadores genéticos: entrecruzamiento cromosómico (también llamado crossover o recombinación) y mutación.
Para cada nueva solución que se ha producido, se ha seleccionado un par de soluciones "padre" para la cría de la agrupación seleccionada previamente. Al producir una solución de "cría" usando los métodos de entrecruzamiento cromosómico y mutación arriba mencionados, se crea una nueva solución que típicamente comparte muchas de las características de sus "padres". Se seleccionan nuevos padres para cada nueva cría, y el proceso continúa hasta que se genere una nueva población de soluciones de tamaño apropiado. Aunque los métodos de reproducción que se basan en el uso de dos padres son más "biología inspirada", algunos temas de investigación sugieren que más de dos "padres" puedan generar cromosomas de mayor calidad.
Estos procesos finalmente resultan en la siguiente generación de población de cromosomas, que es diferente a la generación inicial. En general, la aptitud física promedio se ha incrementado por este procedimiento para la población, ya que solo los mejores organismos de la primera generación son seleccionados para la cría, junto con una pequeña proporción de soluciones menos aptas. Estas soluciones menos aptas aseguran la diversidad genética dentro del grupo genético de los padres y, por lo tanto, aseguran la diversidad genética de la siguiente generación de hijos.
La opinión se divide en la importancia del cruce versus la mutación. Hay muchas referencias en Fogel (2006) que apoyan la importancia de la búsqueda basada en mutaciones.
Aunque el cruce y la mutación se conocen como los principales operadores genéticos, es posible utilizar otros operadores como el reagrupamiento, la colonización-extinción o la migración en algoritmos genéticos.
Vale la pena ajustar parámetros como la probabilidad de mutación, la probabilidad de entrecruzamiento cromosómico y el tamaño de la población para encontrar ajustes razonables para la clase de problema que se está trabajando. Una tasa de mutación muy pequeña puede conducir a la deriva genética (que es de naturaleza no ergódica). Una tasa de recombinación que es demasiado alta puede conducir a la convergencia prematura del algoritmo genético. Una tasa de mutación demasiado alta puede conducir a la pérdida de buenas soluciones, a menos que se utilice una selección elitista.
Este proceso generacional se repite hasta que se alcanza una condición de terminación. Las condiciones de terminación comunes son:
Los algoritmos genéticos son sencillos de implementar, pero su comportamiento es difícil de entender. En particular, es difícil entender por qué estos algoritmos con frecuencia tienen éxito en la generación de soluciones de alta aptitud cuando se aplica a problemas prácticos. La hipótesis del bloque de construcción (BBH) consiste en:
Goldberg describe la heurística de la siguiente manera:
Los esquemas cortos, de bajo orden y de alto ajuste son muestreados, recombinados (cruzados) y remuestreados para formar cadenas de aptitud potencialmente más alta. En cierto modo, al trabajar con estos esquemas particulares (los bloques de construcción), hemos reducido la complejidad de nuestro problema. En lugar de construir cadenas de alto rendimiento mediante el intento de todas las combinaciones concebibles, construimos mejores y mejores cadenas de las mejores soluciones parciales de los últimos muestreos.
"Debido a que los esquemas altamente ajustados de baja definición de longitud y bajo orden desempeñan un papel tan importante en la acción de los algoritmos genéticos, ya les hemos dado un nombre especial: bloques de construcción. Como un niño crea magníficas fortalezas a través de la disposición de bloques simples de madera, también lo hace un algoritmo genético buscando acercarse a un rendimiento óptimo a través de la yuxtaposición de corto, de bajo orden, de alto rendimiento esquemas, o bloques de construcción."
A pesar de la falta de consenso en cuanto a la validez de la hipótesis de bloques de construcción, se ha evaluado y utilizado como referencia a lo largo de los años. Muchas estimaciones de los algoritmos de distribución, por ejemplo, se han propuesto en un intento de proporcionar un entorno en el que la hipótesis se cumpliría. Aunque se han reportado buenos resultados para algunas clases de problemas, todavía queda escepticismo con respecto a la generalidad y / o practicidad de la hipótesis del bloque de construcción como explicación de la eficiencia de los AG. De hecho, hay una cantidad razonable de trabajo que intenta entender sus limitaciones desde la perspectiva de la estimación de los algoritmos de distribución.
Existen limitaciones en el uso de un algoritmo genético en comparación con algoritmos de optimización alternativos:
El algoritmo más simple representa cada cromosoma como una cadena de bits. Normalmente, los parámetros numéricos pueden ser representados por números enteros, aunque es posible usar representaciones de coma flotante. La representación en coma flotante es natural para las estrategias de evolución y la programación evolutiva. La noción de algoritmos genéticos de valor real se ha ofrecido pero es realmente un nombre incorrecto porque no representa realmente la teoría del bloque de construcción que fue propuesta por John Henry Holland en los años 70. Esta teoría no está sin apoyo, sin embargo, sobre la base de los resultados teóricos y experimentales (véase más adelante). El algoritmo básico realiza el cruce y la mutación en el nivel de bits. Otras variantes tratan el cromosoma como una lista de números que son índices en una tabla de instrucciones, nodos en una lista enlazada, hashes, objetos o cualquier otra estructura de datos imaginable. El cruce y la mutación se realizan para respetar los límites de los elementos de datos. Para la mayoría de los tipos de datos, se pueden diseñar operadores de variación específicos. Los diferentes tipos de datos cromosómicos parecen funcionar mejor o peor para diferentes dominios de problemas específicos.
Cuando se utilizan representaciones de números de bits de números enteros, a menudo se emplea la codificación Gray. De esta manera, pequeños cambios en el número entero pueden ser fácilmente afectados por mutaciones o crossovers. Esto se ha encontrado para ayudar a prevenir la convergencia prematura en las paredes llamadas Hamming, en el que demasiadas mutaciones simultáneas (o eventos de cruce) debe ocurrir con el fin de cambiar el cromosoma a una mejor solución.
Otros enfoques implican el uso de matrices de números de valor real en lugar de cadenas de bits para representar los cromosomas. Los resultados de la teoría de los esquemas sugieren que en general, cuanto menor es el alfabeto, mejor es el rendimiento, pero inicialmente fue sorprendente para los investigadores que se obtuvieron buenos resultados usando cromosomas de valor real. Esto se explicó como el conjunto de valores reales en una población finita de cromosomas como la formación de un alfabeto virtual (cuando la selección y la recombinación son dominantes) con una cardinalidad mucho menor de lo que se esperaría de una representación en coma flotante [14] [15]
Una expansión del algoritmo genético accesible problema del dominio se puede obtener a través de la codificación más compleja de la solución de agrupaciones por concatenación de varios tipos de genes heterogéneamente codificados en un cromosoma. [16] Este enfoque particular permite resolver problemas de optimización que requieren dominios de definición sumamente dispares para los parámetros del problema. Por ejemplo, en los problemas de ajuste en cascada del controlador, la estructura del controlador de bucle interno puede pertenecer a un regulador convencional de tres parámetros, mientras que el bucle externo podría implementar un controlador lingüístico (tal como un sistema difuso) que tiene una descripción inherentemente diferente. Esta forma particular de codificación requiere un mecanismo especializado de cruce que recombina el cromosoma por sección, y es una herramienta útil para el modelado y simulación de sistemas adaptativos complejos, especialmente procesos de evolución.
Una variante práctica del proceso general de construcción de una nueva población es permitir que los mejores organismos de la generación actual se trasladen a la siguiente, sin alterarse. Esta estrategia se conoce como selección elitista y garantiza que la calidad de la solución obtenida por la GA no disminuirá de una generación a la siguiente
Implementaciones paralelas de algoritmos genéticos vienen en dos sabores. Los algoritmos genéticos paralelos de grano grueso asumen una población en cada uno de los nodos informáticos y la migración de individuos entre los nodos. Los algoritmos genéticos paralelos suponen un individuo en cada nodo procesador que actúa con individuos vecinos para la selección y reproducción. Otras variantes, como algoritmos genéticos para problemas de optimización en línea, introducen dependencia del tiempo o ruido en la función de fitness.
Los algoritmos genéticos con parámetros adaptativos (algoritmos genéticos adaptativos, AGAs) es otra variante significativa y prometedora de los algoritmos genéticos. Las probabilidades de crossover (pc) y mutación (p. m.) determinan en gran medida el grado de exactitud de la solución y la velocidad de convergencia que los algoritmos genéticos pueden obtener. En lugar de utilizar valores fijos de pc y p. m., los AGs utilizan la información de población en cada generación y ajustan adaptativamente el pc y p. m. con el fin de mantener la diversidad de población así como para sostener la capacidad de convergencia. En AGA (algoritmo genético adaptativo), el ajuste de pc y p. m. depende de los valores de aptitud de las soluciones. En CAGA (algoritmo adaptativo basado en el clustering), a través del uso de análisis de agrupación para juzgar los estados de optimización de la población, el ajuste de pc y p. m. depende de estos estados de optimización. Puede ser muy eficaz combinar GA con otros métodos de optimización. GA tiende a ser bastante bueno para encontrar en general buenas soluciones globales, pero bastante ineficiente para encontrar las últimas mutaciones para encontrar el óptimo absoluto. Otras técnicas (como la simple subida de colinas) son bastante eficientes para encontrar el óptimo absoluto en una región limitada. La alternancia de GA y escalada de colinas puede mejorar la eficiencia de GA [citación necesaria], mientras que superar la falta de solidez de la subida de la colina.
Esto significa que las reglas de variación genética pueden tener un significado diferente en el caso natural. Por ejemplo - siempre que los pasos se almacenan en orden consecutivo - cruce puede sumar una serie de pasos de ADN materno añadiendo una serie de pasos de ADN paterno y así sucesivamente. Esto es como añadir vectores que más probablemente pueden seguir una cresta en el paisaje fenotípico. Por lo tanto, la eficiencia del proceso puede aumentarse en muchos órdenes de magnitud. Además, el operador de inversión tiene la oportunidad de situar los pasos en orden consecutivo o cualquier otra orden adecuada a favor de la supervivencia o la eficiencia.
Una variación, en la que la población en su conjunto se desarrolla en lugar de sus miembros individuales, se conoce como recombinación de grupos genéticos.
Se han desarrollado una serie de variaciones para intentar mejorar el rendimiento de los AGs en problemas con un alto grado de epistasis de aptitud, es decir, cuando la aptitud de una solución consiste en interaccionar subconjuntos de sus variables. Tales algoritmos tienen como objetivo aprender (antes de explotar) estas interacciones fenotípicas beneficiosas. Como tales, están alineados con la hipótesis del bloque de construcción en la reducción adaptativa de la recombinación disruptiva.
Los problemas que parecen ser particularmente apropiados para la solución mediante algoritmos genéticos incluyen problemas de programación y muchos paquetes de software de programación se basan en AGs. Los AG también se han aplicado a la ingeniería. Los algoritmos genéticos a menudo se aplican como un enfoque para resolver problemas de optimización global.
Como regla general, los algoritmos genéticos pueden ser útiles en dominios problemáticos que tienen un paisaje de aptitud complejo, ya que la mezcla, es decir, la mutación en combinación con crossover, está diseñada para alejar a la población de la óptima local de que un algoritmo tradicional. Observe que los operadores de crossover de uso común no pueden cambiar ninguna población uniforme. La mutación por sí sola puede proporcionar ergodicidad del proceso general del algoritmo genético (visto como una cadena de Markov).
En 1950, Alan Turing propuso una "máquina de aprendizaje" que sería paralela a los principios de la evolución. La simulación por computadora de la evolución comenzó tan pronto como en 1954 con el trabajo de Nils Aall Barricelli, que utilizaba la computadora en el instituto para el estudio avanzado en Princeton (Nueva Jersey). Su publicación de 1954 no fue ampliamente notada. A partir de 1957, el australiano cuantitativo genetista Alex Fraser publicó una serie de artículos sobre la simulación de la selección artificial de organismos con múltiples loci controlando un rasgo mensurable. A partir de estos comienzos, la simulación por ordenador de la evolución por los biólogos se hizo más común a principios de 1960, y los métodos fueron descritos en los libros de Fraser y Burnell (1970) y Crosby (1973) Las simulaciones de Fraser incluían todos los elementos esenciales de los algoritmos genéticos modernos. Además, Hans-Joachim Bremermann publicó una serie de artículos en los años sesenta que también adoptaron una población de solución a problemas de optimización, sometidos a recombinación, mutación y selección. La investigación de Bremermann también incluyó los elementos de los algoritmos genéticos modernos. Otros destacados primeros pioneros son Richard Friedberg, George Friedman y Michael Conrad. Muchos de los primeros artículos han sido reimpresos por Fogel (1998).
Aunque Barricelli, en el trabajo que relató en 1963, había simulado la evolución de la capacidad de jugar un juego simple, la evolución artificial se convirtió en un método de optimización ampliamente reconocido como resultado del trabajo de Ingo Rechenberg y Hans-Paul Schwefel en los años 1960 y principios de 1970 - el grupo de Rechenberg fue capaz de resolver problemas complejos de ingeniería a través de estrategias de evolución.Otro enfoque fue la técnica de programación evolutiva de Lawrence J. Fogel, que se propuso para generar inteligencia artificial. La programación evolutiva utilizó originalmente máquinas de estado finito para predecir los entornos y utilizó la variación y la selección para optimizar las lógicas predictivas. Los algoritmos genéticos, en particular, se hicieron populares a través del trabajo de John Henry Holland a principios de los años setenta, y particularmente de su libro Adaptation in Natural and Artificial Systems (1975). Su trabajo se originó con estudios de autómatas celulares, conducidos por Países Bajos y sus estudiantes en la Universidad de Míchigan. Países Bajos introdujo un marco formalizado para predecir la calidad de la próxima generación, conocido como el teorema del esquema de Países Bajos. La investigación en GAs permaneció en gran parte teórica hasta mediados de los años 80, cuando la primera conferencia internacional en algoritmos genéticos fue llevada a cabo en Pittsburgh, Pensilvania.
A finales de 1980, General Electric comenzó a vender el primer producto de algoritmo genético del mundo, una caja de herramientas basada en mainframe diseñada para procesos industriales. En 1989, Axcelis, Inc. lanzó Evolver, el primer producto AG comercial para computadoras de escritorio. El escritor de la tecnología del New York Times John Markoff escribió sobre Evolver en 1990, y siguió siendo el único algoritmo comercial interactivo hasta 1995. Evolver fue vendido a Palisade en 1997, traducido a varios idiomas, y actualmente está en su sexta versión.
Considérese el problema de insertar signos de suma o resta entre los dígitos 9 8 7 6 5 4 3 2 1 para construir una expresión cuyo valor sea 100; no vale añadir, retirar o desordenar a los dígitos. Una solución puede ser 98+7-6+5-4+3-2-1 porque, al evaluar su valor, da exactamente 100.
Hay 9 sitios (uno antes de cada dígito) donde colocar un signo de más (+), un signo de menos (-) o nada (lo cual implicará que dos o más dígitos se unan para formar cantidades mayores; como 98 en el ejemplo anterior, donde se puso "nada" antes del 9 y antes del 8). Existen, por lo tanto, 3 a la 9 = 19683 expresiones distintas (por combinatoria) entre las cuales buscar aquellas con la suma deseada. Es posible desarrollar un algoritmo exhaustivo que las genere todas y, dada la relativa pequeñez de este ejemplo, determinar completamente todas las posibles configuraciones. Sin embargo, este reto se presta para ilustrar los pasos de un proceso genético.
Existe una biyección entre las cadenas de "trits" (dígitos ternarios: 0, 1, 2) de longitud 9 y las posibles configuraciones de signos para cada suma. Por ejemplo, si se adopta la convención de que "0" representa "nada", "1" representa "menos" y "2" representa "más", entonces la cadena de "trits" 002121211 corresponde a la solución 98+7-6+5-4+3-2-1.
Los algoritmos genéticos son un subcampo de:
Los algoritmos evolutivos son un sub-campo de la computación evolutiva.
Escribe un comentario o lo que quieras sobre Algoritmo genético (directo, no tienes que registrarte)
Comentarios
(de más nuevos a más antiguos)