Algoritmos genético paralelo

Algoritmos Genéticos Paralelos

Algoritmos genéticos seqüencial tem a deficiente de tempo de execução requerido quando comparado com as demais heurísticas.Algumas limitações estão sendo resolvidas atrás da introdução dos algoritmos genéticos não convencionais ,onde são utilizados também algumas técnicas para melhorar o desempenho do tempo computacional.

O caminho mais promissor para resolver este problema é aproveitar o paralelismo intrínseco que existem nos algoritmos genéticos.

Os algoritmos genéticos são inspirados em processo evolutivo paralelo de uma produção de indivíduos .Os processos de AGs não são imediatos por necessitarem de um controle global no passo de seleção ,requerem uma comunicação entre processadores , podendo conduzir altos custo de comunicação.

Existem modelos propostos que procuram reduzir estes problemas utilizado os processos de paralelização.Esses modelos se dividem através de 3 categoria:

1. O ISLAND MODEL (MODELO ILHA OU MODELO DE GRANULARIDADE GROSSA):Neste modelo várias subpopulações isoladas se evoluem em paralelo e trocam informações periodicamente com as subpopulações vizinhas.Suas implementações seguem o modelo Island,são assíncronas e são mais adequados a máquinas MIMD.

2. O FINE-GRAINED MODEL(MODELO DE GRANULARIDADE FINA): Também conhecido como neighbourhood model,neste modelo uma única população evolui e cada individuo de uma célula e colocado em um planar.O processo de seleção e do crossover é aplicados somente entre indivíduos vizinhos na grade.Este modelo é mais adequado a arquitetura SIMD paralelas com o “array processors" e "connection machines”.

3. PANMITIC MODEL:São importantes versões paralelas de algoritmos genéticos seqüenciais ordinários .Eles trabalham sobre uma população global,são síncronos.

É adequado para arquiteturas paralelas com memórias