10 agoritmo genetico

Guillermo Baquerizo 2012 I Trmino

! Fue creado por John Holland en 1975 ! Los AG son mtodos adaptativos que pueden usarse para resolver

problemas de bsqueda y optimizacin. ! Estn basados en el proceso gentico de los organismos

vivos. A lo largo de las generaciones, las poblaciones evolucionan en la

naturaleza de acorde con los principios de la seleccin natural y la supervivencia de los ms fuertes, postulados por Darwin (1859).

! Por imitacin de este proceso son capaces de ir creando soluciones para problemas del mundo real. La evolucin de dichas soluciones hacia valores ptimos del

problema depende en buena medida de una adecuada codicacin de las mismas.

! Se la considera como tcnica robusta, y pueden tratar con xito una gran variedad de problemas provenientes de diferentes reas, incluyendo aquellos en los que otros mtodos encuentran dicultades .

! No garantiza que el AG encuentre la solucin optima del problema, existe evidencia emprica de que se encuentran soluciones de un nivel a c e p t a b l e , e n u n t i e m p o competit ivo con el resto de a lgor i tmos de opt imizac in combinatoria.

! El gran campo de aplicacin de los AG se relaciona con aquellos problemas para los cuales no existen tcnicas especializadas. Incluso en el caso en que dichas tcnicas existan, y funcionen bien, pueden efectuarse mejoras de las mismas hibridndolas con los AG.

Elaborado por: Guillermo Baquerizo

Algoritmos gen9cos Seleccin y operadores genticos de sobrecruzamiento El propsito de la seleccin de padres es incrementar la probabilidad

de reproducir miembros de la poblacin que tengan buenos valores de la funcin objetivo.

Una vez que los padres han sido elegidos, se utiliza un operador gentico como el sobrecruzamiento.

La eleccin de otro mecanismo ms adecuado, permite un tratamiento matemtico ms riguroso.

El sobrecruzamiento es el procedimiento por el cual dos seres vivientes intercambian parte de su material gentico para crear un nuevo organismo, para lo cual se puede elegir en forma aleatoria un punto de ruptura de tal manera que el material gentico ms all de este punto es intercambiado entre dos padres para crear dos hijos.

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

Sobrecruzamiento: El cruzamiento es el principal operador gentico, representa la reproduccin sexual, opera sobre dos cromosomas a la vez para generar dos descendientes donde se combinan las caracter st icas de ambos cromosomas padres.

! Su espacio de bsqueda (i.e., sus posibles soluciones) debe de estar delimitado dentro de un cierto rango.

! Debe permitir denir una funcin de aptitud que nos indique que tan buena o mala es una cierta respuesta.

! Las soluciones deben codicarse de una forma que resulte relativamente fcil de implementar en el computador.

Durante los primeros aos el tipo de representacin utilizado era siempre binario, debido a que se adapta perfectamente al tipo de operaciones y el tipo de operadores que se utilizan en un AG. Sin embargo, las representaciones binarias no son siempre efectivas por lo que se empezaron a utilizar otro tipo de representaciones, como por ejemplo : Representacin binaria: Cada gen es un valor 1 0. 1 0 1 1 0 1

Representacin entera: Cada gen es un valor entero. 1 0 3 -1 0 4

Representacin real: Cada gen es un valor real. 1,78 2,6 7 0 -1,2 6,5


Algoritmos gen9cos Ejemplo de sobrecruzamiento one-point crossover Suponga que tiene dos padres: p1 = y p2 = Si suponemos que el punto de entrecruzamiento elegido

aleatoriamente es 3, dos conguraciones hijas generadas son: ch1 = y ch2 =

Cree usted dos nuevos hijos, pero considere que el punto de entrecruzamiento es 6.


Algoritmos gen9cos Seleccin y operadores genticos de sobrecruzamiento Al irse desarrollando el campo de los AGs, se fueron haciendo notorias

ciertas limitaciones del one-point crossover, principalmente al no poder combinar caractersticas presentes en los dos cromosomas.

Una solucin ha sido el uso del two-point crossover. En este caso, son elegidos dos puntos de ruptura al azar y es intercambiado el material gentico entre ambos.

Como este ltimo algoritmo tambin presenta sus restricciones, esto motiv el desarrollo del uniform crossover: comenzando por el primer bit, es elegido al azar un padre para que contribuya con su primer bit al primer hijo, mientras el segundo hijo recibe el bit del segundo padre. Este proceso contina hasta que todos los bits han sido reasignados.


Algoritmos gen9cos Seleccin y operadores genticos de sobrecruzamiento Otro proceso importante en los AGs es la mutacin, a pesar de que

est usualmente concebida como un operador cuyo papel es secundario.

En el caso binario, la mutacin consiste en reemplazar cierta probabilidad (denominada mutation rate, por lo general de pequeo valor) el valor de un bit.

Existen bsicamente dos maneras de implantarlo: La primera variante cambia el bit que el test de probabilidad permite (es

decir, si el i-simo bit vale 1 y pasa el test de probabilidad, el nuevo string contendr 0 en la i-sima posicin).

En la segunda variante, se genera al azar un nuevo bit para sustituir el bit que pas el test de probabilidad. Por lo tanto, el 50% de las veces el nuevo bit no cambiar, y la mutation rate ser la mitad de la primera variante.


Algoritmos gen9cos Seleccin y operadores genticos de sobrecruzamiento Los operadores genticos para strings de bits han acaparado la mayor

atencin por parte de los investigadores, en comparacin con otros tipos de representacin.

Cuando uno se mueve de la teora a la prctica, se tiende a usar operadores genticos diferentes y ms adaptados a los campos de aplicacin.

Un operador de sobrecruzamiento que puede manipular strings no binarios es el PMX (partially-matched crossover): Dados dos cromosomas padres, el operador copia un substring de uno de

los padres directamente a las mismas posiciones en el hijo. Las posiciones restantes se llenan con los valores que an no han sido utilizados en el mismo orden en que se encuentran uno de los padres.


Algoritmos gen9cos Ejemplo de sobrecruzamiento PMX Suponga que tiene dos padres: p1 = y p2 = En forma aleatoria se estableci que el string de p1 ser

insertado en p2: La conclusin inicial es que ste tiene relacin con el substring

, pues ocupan las mismas posiciones. La secuencia de operaciones la transformara en: p2 = Al eliminar las repeticiones, se obtendra: p2 = p2 =


Algoritmos gen9cos Strategic Edge Crossover Otro ejemplo de sobrecruzamiento, propuesto inicialmente para el

TSP, es el Strategic Edge Crossover, el cual: Comienza identicando aquellos strings (es decir, conjuntos de aristas

conectados) que estn presentes en ambos padres. Las ciudades al nal de estos strings son conectadas entre s formando subrutas, que luego son conectadas mediante una heurstica similar a la utilizada por Karp.

Para construir las subrutas, es muy til crear una estructura de datos llamada EdgeMap que puede ser denida como una lista de EdgeLists. El EdgeList de una ciudad dada es la lista de ciudades a las cuales est conectada en las dos rutas padres. Una ciudad marcada con el signo - indica que esta unin est presente en los dos padres. Desde una ciudad inicial elegida mediante algn procedimiento (al azar, la ms alejada a las ya visitadas, la ms cercana, etc.).


Algoritmos gen9cos Strategic Edge Crossover La creacin de un string involucra los siguientes pasos:

1. Elegir la StartCity del conjunto de ciudades an no visitadas. Se dene la variable BothDirections = False. Se dene CurrentCity = StartCity.

2. Se retiran todas las ocurrencias de CurrentCity en el EdgeMap. 3. Si CurrentCity tiene an elementos en su EdgeList entonces se contina

con el paso 4, y si no los tiene se va al paso 5. 4. Determinar cul es la ciudad en el EdgeList de la CurrentCity que tiene el

menor nmero de elementos en su propia EdgeList. sa ser la prxima CurrentCity y es insertada en el string. Los empates se resuelven aleatoriamente. Sin embargo, los empates no se rompen aleatoriamente cuando una de las ciudades tienen la misma arista en ambos padres. Tras esta secuencia se vuelve al paso 2.

sigue


Algoritmos gen9cos viene 5. Si BothDirections = False, entonces es declarada un EndPoint, esto es,

BothDirections = True, CurrentCity = StartCity y volvemos al paso 2, para comenzar a construir otra subruta desde la StartCity. En caso contrario, es decir, si BothDirections = True, entonces CurrentCity es el segundo EndPoint encontrado, y ambos EndPoints son unidos formando una subruta. Si ya no quedan ms ciudades por visitar, STOP; en caso contrario, se vuelve al paso 1 para generar una nueva subruta.


Algoritmos gen9cos Referencias bibliogrcas: Prgel-Bennett-Shapiro 1994 Ackley 1987 Moscato y Norman 1992 Holland 1975 Karp Heuristic Lawler et al, 1985 Radclie, Surry 1994 Goldberg 1989 Costa, Hertz, Dubuis 1995

10 agoritmo genetico

Documents

Transcript of 10 agoritmo genetico