Algoritmos geneticos paralelos
Páginas: 18 (4288 palabras)
Publicado: 17 de mayo de 2010
Introducci´n a la Computaci´n Evolutiva o o
Dr. Carlos A. Coello Coello
Introducci´n a la Computaci´n Evolutiva o o
Dr. Carlos A. Coello Coello Departamento de Computaci´n o CINVESTAV-IPN Av. IPN No. 2508 Col. San Pedro Zacatenco M´xico, D.F. 07300 e email: ccoello@cs.cinvestav.mx http: //delta.cs.cinvestav.mx/~ccoello
Clase No. 15
2009
Introducci´n a la Computaci´n Evolutiva oo
Dr. Carlos A. Coello Coello
AGs Paralelos
El m´todo m´s simple de paralelizar un AG es la llamada e a paralelizaci´n global. o En este caso, s´lo hay una poblaci´n, como en el AG convencional, o o pero la evaluaci´n de los individuos y los operadores gen´ticos se o e paralelizan de forma expl´ ıcita.
Clase No. 15
2009
Introducci´n a la Computaci´n Evolutiva o o
Dr. Carlos A.Coello Coello
AGs Paralelos
Puesto que s´lo hay una poblaci´n, la selecci´n considera a todos o o o los individuos y cada individuo tiene oportunidad de aparearse con cualquier otro (o sea, hay apareamiento aleatorio). Por lo tanto, el comportamiento del AG simple permanece sin cambios.
Clase No. 15
2009
Introducci´n a la Computaci´n Evolutiva o o
Dr. Carlos A. Coello CoelloAGs Paralelos
Clase No. 15
2009
Introducci´n a la Computaci´n Evolutiva o o
Dr. Carlos A. Coello Coello
AGs Paralelos
La paralelizaci´n global es un m´todo relativamente f´cil de o e a implementar y puede obtenerse un incremento significativo de velocidad si los costos de comunicaci´n no dominan los costos de o procesamiento. Una observaci´n importante es que no debe confundirse elconcepto o de paralelismo impl´ ıcito de un AG (visto antes en clase) con el de paralelismo expl´ ıcito.
Clase No. 15
2009
Introducci´n a la Computaci´n Evolutiva o o
Dr. Carlos A. Coello Coello
AGs Paralelos
A la paralelizaci´n global tambi´n se le conoce como AG o e panm´ ıtico, pues se cuenta con un solo dep´sito de material o gen´tico (gene pool ), o sea con una solapoblaci´n. e o
Clase No. 15
2009
Introducci´n a la Computaci´n Evolutiva o o
Dr. Carlos A. Coello Coello
AGs Paralelos
Los AGs panm´ ıticos son utiles cuando el costo de evaluar la funci´n ´ o de aptitud es elevado (p.ej., una simulaci´n). o En el AG panm´ ıtico no se requieren nuevos operadores ni nuevos par´metros y la soluci´n encontrada ser´ la misma que la a o a producida con un AGconvencional (o sea, serial).
Clase No. 15
2009
Introducci´n a la Computaci´n Evolutiva o o
Dr. Carlos A. Coello Coello
AGs Paralelos
Es importante hacer notar que aunque el paralelismo global normalmente es s´ ıncrono (o sea, que el programa se detiene y espera a recibir los valores de aptitud de toda la poblaci´n antes de o proceder a producir la siguiente generaci´n), puedeimplementarse o tambi´n de forma as´ e ıncrona, aunque en ese caso, su funcionamiento ya no resultar´ equivalente al de un AG a convencional.
Clase No. 15
2009
Introducci´n a la Computaci´n Evolutiva o o
Dr. Carlos A. Coello Coello
AGs Paralelos
Adem´s de paralelizarse la evaluaci´n de la funci´n de aptitud, en a o o el paralelismo global es posible incluir tambi´n los operadores egen´ticos, pero dada la simplicidad de ´stos, no suelen e e paralelizarse, pues los costos de comunicaci´n disipar´ cualquier o ıan mejora en el desempe˜o del programa. n
Clase No. 15
2009
Introducci´n a la Computaci´n Evolutiva o o
Dr. Carlos A. Coello Coello
AGs Paralelos
Una idea m´s sofisticada es usar los llamados AGs de grano a grueso. En este caso, la poblaci´n del AG se divideen m´ltiples o u subpoblaciones o demes que evolucionan de manera aislada la mayor parte del tiempo, aunque intercambian individuos ocasionalmente.
Clase No. 15
2009
Introducci´n a la Computaci´n Evolutiva o o
Dr. Carlos A. Coello Coello
AGs Paralelos
A este intercambio de individuos se le llama migraci´n, y se o considera como un nuevo operador gen´tico. Adem´s de requerirse e...
Dr. Carlos A. Coello Coello
Introducci´n a la Computaci´n Evolutiva o o
Dr. Carlos A. Coello Coello Departamento de Computaci´n o CINVESTAV-IPN Av. IPN No. 2508 Col. San Pedro Zacatenco M´xico, D.F. 07300 e email: ccoello@cs.cinvestav.mx http: //delta.cs.cinvestav.mx/~ccoello
Clase No. 15
2009
Introducci´n a la Computaci´n Evolutiva oo
Dr. Carlos A. Coello Coello
AGs Paralelos
El m´todo m´s simple de paralelizar un AG es la llamada e a paralelizaci´n global. o En este caso, s´lo hay una poblaci´n, como en el AG convencional, o o pero la evaluaci´n de los individuos y los operadores gen´ticos se o e paralelizan de forma expl´ ıcita.
Clase No. 15
2009
Introducci´n a la Computaci´n Evolutiva o o
Dr. Carlos A.Coello Coello
AGs Paralelos
Puesto que s´lo hay una poblaci´n, la selecci´n considera a todos o o o los individuos y cada individuo tiene oportunidad de aparearse con cualquier otro (o sea, hay apareamiento aleatorio). Por lo tanto, el comportamiento del AG simple permanece sin cambios.
Clase No. 15
2009
Introducci´n a la Computaci´n Evolutiva o o
Dr. Carlos A. Coello CoelloAGs Paralelos
Clase No. 15
2009
Introducci´n a la Computaci´n Evolutiva o o
Dr. Carlos A. Coello Coello
AGs Paralelos
La paralelizaci´n global es un m´todo relativamente f´cil de o e a implementar y puede obtenerse un incremento significativo de velocidad si los costos de comunicaci´n no dominan los costos de o procesamiento. Una observaci´n importante es que no debe confundirse elconcepto o de paralelismo impl´ ıcito de un AG (visto antes en clase) con el de paralelismo expl´ ıcito.
Clase No. 15
2009
Introducci´n a la Computaci´n Evolutiva o o
Dr. Carlos A. Coello Coello
AGs Paralelos
A la paralelizaci´n global tambi´n se le conoce como AG o e panm´ ıtico, pues se cuenta con un solo dep´sito de material o gen´tico (gene pool ), o sea con una solapoblaci´n. e o
Clase No. 15
2009
Introducci´n a la Computaci´n Evolutiva o o
Dr. Carlos A. Coello Coello
AGs Paralelos
Los AGs panm´ ıticos son utiles cuando el costo de evaluar la funci´n ´ o de aptitud es elevado (p.ej., una simulaci´n). o En el AG panm´ ıtico no se requieren nuevos operadores ni nuevos par´metros y la soluci´n encontrada ser´ la misma que la a o a producida con un AGconvencional (o sea, serial).
Clase No. 15
2009
Introducci´n a la Computaci´n Evolutiva o o
Dr. Carlos A. Coello Coello
AGs Paralelos
Es importante hacer notar que aunque el paralelismo global normalmente es s´ ıncrono (o sea, que el programa se detiene y espera a recibir los valores de aptitud de toda la poblaci´n antes de o proceder a producir la siguiente generaci´n), puedeimplementarse o tambi´n de forma as´ e ıncrona, aunque en ese caso, su funcionamiento ya no resultar´ equivalente al de un AG a convencional.
Clase No. 15
2009
Introducci´n a la Computaci´n Evolutiva o o
Dr. Carlos A. Coello Coello
AGs Paralelos
Adem´s de paralelizarse la evaluaci´n de la funci´n de aptitud, en a o o el paralelismo global es posible incluir tambi´n los operadores egen´ticos, pero dada la simplicidad de ´stos, no suelen e e paralelizarse, pues los costos de comunicaci´n disipar´ cualquier o ıan mejora en el desempe˜o del programa. n
Clase No. 15
2009
Introducci´n a la Computaci´n Evolutiva o o
Dr. Carlos A. Coello Coello
AGs Paralelos
Una idea m´s sofisticada es usar los llamados AGs de grano a grueso. En este caso, la poblaci´n del AG se divideen m´ltiples o u subpoblaciones o demes que evolucionan de manera aislada la mayor parte del tiempo, aunque intercambian individuos ocasionalmente.
Clase No. 15
2009
Introducci´n a la Computaci´n Evolutiva o o
Dr. Carlos A. Coello Coello
AGs Paralelos
A este intercambio de individuos se le llama migraci´n, y se o considera como un nuevo operador gen´tico. Adem´s de requerirse e...
Leer documento completo
Regístrate para leer el documento completo.