Algoritmos geneticos

goLOS ALGORITMOS GENÉTICOS
Una visión General Durante los últimos treinta años se ha experimentado un creciente interés por la construcción de sistemas de resolución de problemas basados en el proceso de evolución natural. En este sentido los algoritmos genéticos son algoritmos de búsqueda y optimización cuyo mecanismo de funcionamiento está basado en dicho proceso. Es bien conocido por losbiólogos que el proceso de evolución natural tiene lugar en los cromosomas, que poseen la información genética de los individuos. Aunque no se sabe aún de manera completa la información específica codificada en los cromosomas de un individuo, las siguientes propiedades generales son aceptadas por todos los especialistas en el tema: a) La evolución es un proceso que opera fundamentalmente sobre loscromosomas. b) El proceso de selección natural es el responsable de que aquellos individuos que tienen mejor adaptación al entorno se reproduzcan más que los poco adaptados. c) En la reproducción es donde tiene lugar la evolución. Los procesos de mutación producen cambios en los cromosomas de los hijos con respecto a los padres y mediante las combinaciones del material genético de los padres se puedecrear en los hijos material genético diferente. d) La evolución biológica carece de memoria. Lo único que pretende es producir individuos que se adapten de manera óptima al entorno en el que viven. Fue John Holland en los años 70 el primero que pretendió llevar esta estrategia de actuación al campo de la computación y tratar de diseñar sistemas artificiales con un comportamiento análogo al delsistema evolutivo natural. Este intento trajo consigo el nacimiento de lo que hoy conocemos como algoritmos evolutivos. Un algoritmo evolutivo es un algoritmo probabilístico que mantiene una población de individuos, P(t) para cada iteración t. Cada uno de los individuos constituye una potencial solución del problema, representada mediante alguna estructura de datos. Cada una de estas potencialessoluciones es evaluada para obtener una medida de su calidad como solución. Posteriormente, se construye una nueva población (iteración t+1) mediante un proceso de selección en P(t) de manera que los mejores individuos tienen mayor probabilidad de ser seleccionados. A continuación se altera esta nueva población mediante la aplicación sobre algunos miembros de de la misma de ciertos operadoresgenéticos. Estos operadores genéticos pueden ser unarios (mutaciones), produciendo nuevos individuos mediante pequeños cambios en el individuo sobre el que se aplican, o de aridad superior (cruces) de manera que dos o más individuos se combinan para producir nuevos individuos. Así se obtiene finalmente una nueva población P(t+1). Tras un número de iteraciones o generaciones es de esperar que el mejorindividuo de la población final obtenida represente una solución del problema óptima o al menos razonablemente buena.

11

Una primera aproximación a la estructura de un algoritmo evolutivo es la siguiente:

begin t←0 inicializar P(t) evaluar P(t) while (not condicion _de_parada) do begin t ← t+1 seleccionar P(t) desde P(t-1) alterar P(t) evaluar P(t) end end

Un caso concreto de algoritmosevolutivos son los denominados algoritmos genéticos. Estos algoritmos se caracterizan por utilizar operadores de cruce en el proceso de alteración de la población. Teniendo en cuenta lo anterior, los conceptos básicos que se manejan en la teoría de los algoritmos genéticos son los siguientes: Individuo o cromosoma: Un individuo determina una potencial solución del problema que se pretende resolvermediante el algoritmo genético. Población: Conjunto de individuos con los que se trabaja en el algoritmo genético. En un algoritmo genético los individuos que constituyen la población van cambiando pero generalmente el tamaño de la misma permanece constante. Función fitness: Se trata de una función evaluadora de la calidad de un individuo como solución a nuestro problema. Permite la ordenación...