A memetic algorithm framework for multimodal continuous optimization

Abstract

Despite the advances in computational methods and the wide range of metaheuristics proposed for multimodal continuous optimization, there is still a strong demand for de veloping new strategies focused on issues related to the algorithms’ performance when applied to challenging problems with complicated objective functions. The general idea of this work is centered around the investigation of distinct metaheuristic characteristics to deal with multimodal problems in the continuous domain. In this sense, we defined the multimodal 3-D protein structure prediction problem as our real case study, one of the most important problems in Structural Bioinformatics. Thus, we proposed an adap tive memetic algorithm as a general framework-based method with multiple populations and niching strategies, which incorporates concepts of bio-inspired algorithms for global optimization with separate local improvement. To evaluate the proposed approach, we designed different versions of the framework for three scenarios of multimodal optimiza tion: (i) the general framework for single global continuous optimization with multimodal objective function; (ii) the framework with archive strategy for multimodal optimization with more than one global optimum; and (iii) the framework with specific-problem com ponents for the multimodal problem of predicting the 3-D protein structures. With the de velopment of this work, we aimed to create, via a constructive and incremental approach, an evolutionary method capable of dealing with the inherent multimodality and issues of a range of optimization functions while preserving accurate results. Our focus was also to evaluate the behavior of the presented methods and search components facing multiple multimodal problems. The memetic algorithm framework was able to perform well on all the optimization scenarios explored by reaching promising results compared with relevant methods related to the corresponding research fields. Nonetheless, despite the obtained results, we highlight that each implemented algorithmic version still needs improvements regarding each of the delineated case studies to further enhance the method’s performance and results.

Apesar dos avanços computacionais e da ampla gama de meta-heurísticas propostas na literatura para lidar com problemas de otimização multimodal, ainda existe a necessidade de desenvolver novas estratégias de busca voltadas ao desempenho dos algoritmos quando aplicados a problemas difíceis com complexas funções de avaliação. A ideia geral deste trabalho consiste na investigação de diferentes aspectos relativos as meta-heurísticas utilizadas para tratar problemas multimodais de domínio contínuo. Neste sentido, definiu-se, como estudo de caso principal para o trabalho, a predição de estruturas 3-D de proteínas, o qual representa um dos mais importantes problemas da Bioinformática Estrutural. Neste trabalho, foi proposto um algoritmo memético adaptativo na forma de um framework computacional de propósito geral, o qual incorpora múltiplas populações, conceitos de al goritmos evolutivos e inteligência de enxame, combinados a funções adicionais de busca local, controle de convergência e performance. Como forma de avaliação do método pro posto, foram idealizadas diferentes versões, as quais foram empregadas em três cenários distintos de otimização: (i) versão mais geral para tratar funções multimodais com um único ótimo global; (ii) versão com arquivamento externo de soluções focada em otimi zação multimodal com diversos ótimos globais; e (iii) versão baseada em conhecimento com componentes de busca específicos para lidar com o problema de predição de estru turas 3-D de proteínas. Com isso, objetivou-se prover, através do desenvolvimento de uma abordagem incremental, um método de busca para lidar com as complexidades rela tivas à multimodalidade inerente a diversos problemas de otimização. De maneira geral, concluiu-se que a abordagem proposta obteve êxito quanto à otimização dos problemas concernentes aos diferentes cenários de otimização idealizados. O método atingiu resul tados promissores em relação aos algoritmos mais relevantes das áreas relativas a cada estudo de caso. No entanto, ressalta-se que cada uma das versões implementadas ainda necessita de melhorias em relação a cada um dos estudos de caso delineados, objetivando aprimorar ainda mais o desempenho obtido, bem como os resultados do método como um todo.