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 la selecció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:
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 qué tan "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
No hay comentarios:
Publicar un comentario