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.
alt=|miniaturadeimagen|La antena 2006 de la nave espacial de la NASA ST5. Esta forma complicada fue encontrada por un programa evolutivo del diseño de computadora para crear el mejor patrón de la radiación. Se conoce como una antena evolucionada.
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, se decide cuáles son los individuos más adaptados, que sobreviven, y cuáles son 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.
Introducción
Función 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.
Cuándo usar estos algoritmos 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: Si la función a optimizar tiene muchos máximos/mínimos locales se requerirán más iteraciones del algoritmo para "asegurar" el máximo/mínimo global. Si la función a optimizar contiene varios puntos muy cercanos en valor al óptimo, solamente podemos "asegurar" que encontraremos uno de ellos (no necesariamente el óptimo).
Funcionamiento de un algoritmo genético básico 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:
right|thumb|300px|Algoritmo genético i: inicialización, f(X): evaluación, ?: condición de término, Se: selección, Cr: cruzamiento, Mu: mutación, Re: reemplazo, X*: mejor solución.
Inicialización: Se genera aleatoriamente la población inicial, que está constituida por un conjunto de cromosomas los cuales representan las posibles soluciones del problema. En caso de no hacerlo aleatoriamente, es importante garantizar que dentro de la población inicial, se tenga la diversidad estructural de estas soluciones para tener una representación de la mayor parte de la población posible o al menos evitar la convergencia prematura. Evaluación: A cada uno de los cromosomas de esta población se aplicará la función de aptitud para saber cómo de "buena" es la solución que se está codificando. Condición de término: El AG se deberá detener cuando se alcance la solución óptima, pero esta generalmente se desconoce, por lo que se deben utilizar otros criterios de detención. Normalmente se usan dos criterios: correr el AG un número máximo de iteraciones (generaciones) o detenerlo cuando no haya cambios en la población. Mientras no se cumpla la condición de término se hace lo siguiente: Selección: Después de saber la aptitud de cada cromosoma se procede a elegir los cromosomas que serán cruzados en la siguiente generación. Los cromosomas con mejor aptitud tienen mayor probabilidad de ser seleccionados. Recombinación o cruzamiento: La recombinación es el principal operador genético, representa la reproducción sexual, opera sobre dos cromosomas a la vez para generar dos descendientes donde se combinan las características de ambos cromosomas padres. Mutación: Modifica al azar parte del cromosoma de los individuos, y permite alcanzar zonas del espacio de búsqueda que no estaban cubiertas por los individuos de la población actual. Reemplazo: Una vez aplicados los operadores genéticos, se seleccionan los mejores individuos para conformar la población de la generación siguiente.
Desventajas y limitaciones Entre otras podemos mencionar:
Para problemas de alta complejidad la función de evaluación puede tornarse demasiado costosa en términos de tiempo y recursos. Por ejemplo existen casos en la vida real para los cuales recrear una simulación de la solución propuesta por una iteración puede tardar muchos días y consumir gran cantidad de procesamiento y recursos asociados.
Puede haber casos en los cuales dependiendo los parámetros que se utilicen para la evaluación el algoritmo podría no llegar a converger en una solución óptima o bien terminar en una convergencia prematura con resultados no satisfactorios (la convergencia prematura podría significar una convergencia en un óptimo local o punto arbitrario afectando los resultados a largo plazo).
Se dice que no poseen una buena escalabilidad con la complejidad, por ejemplo para sistemas que están compuestos por muchas variables, componentes o elementos su respectivo espacio de búsqueda crece de manera exponencial debido entre otras cosas a las relaciones que puedan surgir, por lo tanto el problema del diseño de una aeronave debe desglosarse en representaciones simples, como perfiles aerodinámicos, tomando en cuenta que la recombinación de los elementos puede perjudicar el rendimiento individual.
La "mejor" solución lo es solo en comparación a otras soluciones por lo que no se tiene demasiado claro un criterio de cuándo detenerse ya que no se cuenta con una solución específica.
No es recomendable utilizarlos para problemas que buscan respuesta a problemas que convergen en soluciones simples como Correcto/Incorrecto ya que el algoritmo difícilmente convergerá y el resultado será tan válido como escogerlo al azar.
El diseño, la creación de la función de aptitud (fitness) y la selección de los criterios de mutación entre otros, necesitan de cierta pericia y conocimiento del problema para obtener buenos resultados.
Aplicaciones Diseño automatizado, incluyendo investigación en diseño de materiales y diseño multiobjetivo de componentes automovilísticos: mejor comportamiento ante choques, ahorros de peso, mejora de aerodinámica, etc. Diseño automatizado de equipamiento industrial. Diseño automatizado de sistemas de comercio en el sector financiero. Construcción de árboles filogenéticos. Optimización de carga de contenedores. Diseño de sistemas de distribución de aguas. Diseño de topologías de circuitos impresos. Diseño de topologías de redes computacionales. En teoría de juegos, resolución de equilibrios. Análisis de expresión de genes. Aprendizaje de comportamiento de robots. Aprendizaje de reglas de lógica difusa. Análisis lingüístico, incluyendo inducción gramática, y otros aspectos de procesamiento de lenguajes naturales, tales como eliminación de ambigüedad de sentido. Infraestructura de redes de comunicaciones móviles. Optimización de estructuras moleculares. Planificación de producción multicriteria. Predicción. Aplicación de algoritmos genéticos al dilema del prisionero iterado. Optimización de sistemas de compresión de datos, por ejemplo, usando wavelets. Predicción de plegamiento de proteínas. Optimización de Layout. Optimización de Redes. Predicción de estructura de ARN. En bioinformática, alineamiento múltiple de secuencias. Aplicaciones en planificación de procesos industriales, incluyendo planificación job-shop. Selección óptima de modelos matemáticos para la descripción de sistemas biológicos. Manejo de residuos sólidos. Ingeniería de software. Construcción de horarios en grandes universidades, evitando conflictos de clases. Problema del viajante. Hallazgo de errores en programas. Optimización de producción y distribución de energía eléctrica. Diseño de redes geodésicas (problemas de diseño). Calibración y detección de daños en estructuras civiles. Cálculo de poblaciones estelares en sistemas estelares complejos.
Metodología
Problemas de optimización 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 genética del dominio de la solución. Una función de aptitud para evaluar el dominio de la solución. 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.
Inicializació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.
Selección