funcionamiento de un algoritmo genético básico

2
Funcionamiento de un algoritmo genético básico Un algoritmo genético puede presentar diversas variaciones, dependiendo de cómo s operadores genéticos (cruzamiento, mutación), de cómo se realiza la selección y d el reemplazo de los individuos para formar la nueva población. En general, el pse consiste de los siguientes pasos: Algoritmo genético i: inicialización, f(X): evaluación, : condición de término, !e: cruzamiento, #u: mutación, $e: reemplazo, X%: me&or solución. Inicialización : !e genera aleatoriamente la población inicial, 'ue est constit con&unto de cromosomas los cuales representan las posibles soluciones del p caso de no acerlo aleatoriamente, es importante garantizar 'ue dentro de l inicial, se tenga la diversidad estructural de estas soluciones para tener la mayor parte de la población posible o al menos evitar la convergencia pr Evaluación : * cada uno de los cromosomas de esta población se aplicar la fun aptitud para saber cómo de +buena+ es la solución 'ue se est codificando. Condición de término El * se deber detener cuando se alcance la solución ópt ésta generalmente se desconoce, por lo 'ue se deben utilizar otros criterio -ormalmente se usan dos criterios: correr el * un n mero m /imo de iteraci (generaciones) o detenerlo cuando no aya cambios en la población. #ientras la condición de término se ace lo siguiente: o Selección 0espués de saber la aptitud de cada cromosoma se procede a ele cromosomas 'ue ser n cruzados en la siguiente generación. 1os cromosom me&or aptitud tienen mayor probabilidad de ser seleccionados. o Recombinación o Cruzamiento 1a recombinación es el principal operador genético, representa la reproducción se/ual, opera sobre dos cromosoma para generar dos descendientes donde se combinan las caracter2sticas cromosomas padres.

Upload: mauricio-rojas-valdivia

Post on 05-Oct-2015

4 views

Category:

Documents


0 download

DESCRIPTION

Algoritmo GeneticoFuncionamiento

TRANSCRIPT

Funcionamiento de un algoritmo gentico bsicoUn algoritmo gentico puede presentar diversas variaciones, dependiendo de cmo se aplican los operadores genticos (cruzamiento, mutacin), de cmo se realiza la seleccin y de cmo se decide el reemplazo de los individuos para formar la nueva poblacin. En general, el pseudocdigo consiste de los siguientes pasos:

Algoritmo gentico i: inicializacin, f(X): evaluacin,?: condicin de trmino, Se: seleccin, Cr: cruzamiento, Mu: mutacin, Re: reemplazo, X*: mejor solucin. Inicializacin: Se genera aleatoriamente la poblacin 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 poblacin inicial, se tenga la diversidad estructural de estas soluciones para tener una representacin de la mayor parte de la poblacin posible o al menos evitar la convergencia prematura. Evaluacin: A cada uno de los cromosomas de esta poblacin se aplicar la funcin de aptitud para saber cmo de "buena" es la solucin que se est codificando. Condicin de trmino El AG se deber detener cuando se alcance la solucin ptima, pero sta generalmente se desconoce, por lo que se deben utilizar otros criterios de detencin. Normalmente se usan dos criterios: correr el AG un nmero mximo de iteraciones (generaciones) o detenerlo cuando no haya cambios en la poblacin. Mientras no se cumpla la condicin de trmino se hace lo siguiente: Seleccin Despus de saber la aptitud de cada cromosoma se procede a elegir los cromosomas que sern cruzados en la siguiente generacin. Los cromosomas con mejor aptitud tienen mayor probabilidad de ser seleccionados. Recombinacin o Cruzamiento La recombinacin es el principal operador gentico, representa la reproduccin sexual, opera sobre dos cromosomas a la vez para generar dos descendientes donde se combinan las caractersticas de ambos cromosomas padres. Mutacin modifica al azar parte del cromosoma de los individuos, y permite alcanzar zonas del espacio de bsqueda que no estaban cubiertas por los individuos de la poblacin actual. Reemplazo una vez aplicados los operadores genticos, se seleccionan los mejores individuos para conformar la poblacin de la generacin siguiente