Um algoritmo genético paralelo autoadaptável misto para a otimização multimodal com e sem restrições.

Abstract

Os algoritmos genéticos são algoritmos de busca que utilizam uma série de parâmetros para encontrar a melhor solução de um dado problema. A escolha desses parâmetros é um desafio, pois diferentes problemas podem exigir diferentes configurações. Na maioria das vezes, essa escolha é feita pelo método da tentativa-e-erro que além de demandar tempo pode não levar à melhor configuração possível. Outra possibilidade é a utilização de design de experimentos (fator n k ) que além de ser limitada à quantidade de fatores k, exige que muitas simulações sejam feitas antes da determinação da melhor configuração que também é dependente do problema a ser resolvido. É nesse contexto que surgem os algoritmos autoadaptáveis, permitindo a melhor seleção tanto de taxas quanto de operadores genéticos em tempo de execução. Dessa forma, esta dissertação desenvolve um algoritmo autoajustável que além de escolher entre 4 tipos diferentes de operadores de cruzamento e 4 operadores de mutação, permite também adaptar em tempo de execução as taxas de cruzamento e mutação. Superado o desafio de encontrar a melhor configuração, resta aumentar a velocidade da execução, pois à medida que mais parâmetros são ajustados, maior poder computacional é exigido. Para solucionar esse problema, lança-se mão da utilização da computação paralela que se tornou acessível e popular após a criação e redução dos custos dos processadores multi-núcleos. Nesta dissertação, o paralelismo é obtido através da utilização do OpenMP, que é uma interface de programação de aplicativo (API) que fornece um modelo portável e escalável para programadores criarem aplicações paralelas. Para avaliar o desempenho do algoritmo genético autodaptativo foram utilizados benchmarks padrão, como as funções Schwefel, Griewank, Rastringin, Rosenbrock, variações das duas últimas utilizadas (Shifted Rastring e Shifted Rosenbrock) e uma aplicação real denominada despacho econômico dinâmico de energia elétrica. A avaliação foi feita em termos de qualidade da solução utilizando-se ANOVA e teste de Tukey. Em termos de paralelismo, a avaliação foi feita utilizando-se as métricas de speedup e eficiência.