Algoritmos Genéticos Paralelos

Algoritmos Genéticos Paralelos
Amadeu A. Barbosa Júnior, André Lage Freitas1
Departamento de Ciência da Computação – Universidade Federal da Bahia

1

{amadeu,andre}@dcc.ufba.br

Resumo. A necessidade de se resolver problemas complexos e não triviais na computação motivou a exploração de técinicas da Inteligência Artificial. Utilizando técnicas bioinspiradas, os algoritmos genéticos propõem soluções eficientes baseadas no não-determinismo e na probabilidade para as soluções de problemas de otimização. Este artigo explora as técnicas de paralelização dos algoritmos genéticos e expõe um breve estudo sobre o estado atual da arte.
Abstract. Artificial Intelligence techniques are used for resolving non trivials and complex problems. The use of genectics algorithms (evolutionary computing) help us to solve in a non deterministic and probabilistc way optimizations problems. This paper shows the most important techniques of genectics algorithms paralelization in the actual state of art.
Palavras-chave: Algoritmos genéticos paralelos, computação evolutiva, computação paralela, inteligência artificial.
1. Introdução
Um dos maiores problemas da computação é a intratabilidade de algumas classes de problemas.
Geralmente, estes problemas possuem alta complexidade pois envolvem possibilidades combinatoriais e exponenciais na sua resolução. A necessidade de se resolver problemas complexos em tempo hábil, motivou a paralelização dos algoritmos que os resolvem. Assim, conseguia-se maior rapidez na resolução desses problemas - muito embora a intratabilidade destes não estivesse sido resolvida.
Através de observações da natureza, percebeu-se que ela resolvia seus problemas de forma elegante e eficiente. Um estudo mais detalhado constatou que boa parte desses problemas apresentava alta complexidade, o que intrigou os pesquisadores pois a natureza teria encontrado maneiras eficientes de se resolver problemas da mesma classe que eles queriam resolver.