Abordagem Paralela de Evolução Diferencial Aplicado ao Problema de Predição de Estrutura de Protéına

Resumo

Este trabalho explora a utilização do algoritmo de Evolução Diferencial paralelizado com MPI. O speedup obtido permite a utilização de operadores de busca de maior custo computacional. Os resultados preliminares indicam que há um speedup significativo da aplicação. Protéınas são macromoléculas essenciais para as formas de vida conhecidas, desempenhando papéis regulatórios, metabólicos e estruturais [Walsh 2002]. Sua estrutura tridimensional, que está diretamente associada a sua funcionalidade, é determinada experimentalmente em laboratório através de um processo lento e caro. Atualmente, o problema de predição de estrutura de protéına (PSPP) é considerado um problema em aberto tanto na Ciência da Computação quanto na Bio-informática estrutural e é considerado N P-difícil [Guyeux et al. 2014]. Portanto, a utilização de métodos exatos se torna inviável até mesmo para instâncias de pequeno porte. Sendo assim, abre-se oportunidade para utilização de heurísticas e meta-heurísticas para solução do problema. Considerando a complexidade do problema envolvido, algoritmos meta-heurísticos básicos demonstram limitações e são incapazes de obter soluções significantes em instâncias mais complexas. Logo, o emprego de métodos avançados e a agregação de informações sobre o problema torna-se necessário para uma melhor solução do problema. Além da dificuldade do problema, tem-se ainda a necessidade de avaliar um grande número de funções para determinar a qualidade das soluções durante o processo de otimização, ocupando a maior parte do tempo de execução. Deste modo, a aplicação de uma arquitetura computacional paralela eficiente torna-se necessária para poder escalar a complexidade do PSPP. Com isto em mente, este trabalho tem como objetivo explorar paralelismo no algoritmo de Evolução Diferencial (Differential Evolution - DE). O algoritmo DE é um otimizador para problemas de domínio contínuo [Storn and Price 1997] e foi utilizado com sucesso no PSPP em [Narloch and Parpinelli 2017] e [Oliveira et al. 2017]. O modelo de ângulos e torsões é o empregado neste trabalho.