Formulas de los algoritmos de decaimiento

Genetica

La aplicación más común de los algoritmos genéticos ha sido la solución de problemas de optimización, en donde han mostrado ser muy eficientes y confiables. Sin embargo, no todos los problemas pudieran ser apropiados para la técnica, y se recomienda en general tomar en cuenta las siguientes características del mismo antes de intentar usarla:

• Su espacio de búsqueda (i.e., sus posibles soluciones) debe estar delimitado dentro de un cierto rango.
• Debe poderse definir una función de aptitud que nos indique qué tan buena o mala es una cierta respuesta.
• Las soluciones deben codificarse de una forma que resulte relativamente fácil de implementar en la computadora.

El primer punto es muy importante, y lo más recomendable es intentar resolver problemas que tengan espacios de búsqueda discretos aunque éstos sean muy grandes. Sin embargo, también podrá intentarse usar la técnica con espacios de búsqueda continuos, pero preferentemente cuando exista un rango de soluciones relativamente pequeño.

La función de aptitud no es más que la función objetivo de nuestro problema de optimización. El algoritmo genético únicamente maximiza, pero la minimización puede realizarse fácilmente utilizando el recíproco de la función maximizante (debe cuidarse, por supuesto, que el recíproco de la función no genere una división por cero). Una característica que debe tener esta función es que tiene ser capaz de "castigar" a las malas soluciones, y de "premiar" a las buenas, de forma que sean estas últimas las que se propaguen con mayor rapidez.

La codificación más común de las soluciones es a través de cadenas binarias, aunque se han utilizado también números reales y letras. El primero de estos esquemas ha gozado de mucha popularidad debido a que es el que propuso originalmente Holland, y además porque resulta muy sencillo de implementar.

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.
• 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.

Funcionamiento de un algoritmo genético básico

Un algoritmo genético puede presentar diversas variaciones, dependiendo de cómo se aplican los operadores genéticos (cruzamiento, mutación), de cómo se realiza laselección y 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:

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 ésta 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

algoritmos

Funcionamiento

Los algoritmos genéticos 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 los 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 losoperadores 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).
• 
  
•