Dynamically reconfigurable heterogeneous parallel island model

Abstract

Problemas de otimização N P-difíceis são encontrados em diversos campos de atividade, e à medida que a compreensão e a prática nesses campos avançam, suas complexidades se acentuam. Nas últimas décadas, diversos algoritmos bioinspirados para resolver problemas de otimização foram propostos. Cada um desses algoritmos possui características únicas que impactam de maneiras distintas tanto o processo evolutivo quanto a qualidade das soluções alcançadas. O Modelo de Ilhas Paralelas (MIP) é uma estratégia de paralelização de algoritmos bioinspirados que proporciona ganhos significativos na acurácia das soluções. Nesse modelo, o conjunto de soluções candidatas é dividido em subpopulações denominadas ilhas. Cada ilha evolui seu conjunto de soluções por meio de seu próprio algoritmo bioinspirado, operando de forma paralela às outras ilhas. Periodicamente, as ilhas trocam soluções entre si através do processo de migração. Esse movimento de soluções entre as ilhas é condicionado à topologia do modelo e a um conjunto de regras que compõem a política de migração. Este trabalho propõe uma nova abordagem de implementação para MIPs, inspirada em heterogeneidade e reconfiguração algorítmica: o MIP heterogêneo com reconfiguração baseada em estagnação. A heterogeneidade permite a execução de diferentes algoritmos bioinspirados nas ilhas, aumentando a diversidade. Ao mesmo tempo, a reconfiguração algorítmica permite a substituição dos algoritmos bioinspirados caso a estagnação das ilhas é detectada. Durante o processo evolutivo, cada ilha mantém um registro do seu progresso, mensurado pelo desempenho do melhor indivíduo em cada ilha, na geração atual e nas duas gerações anteriores. Sempre que exista estagnação, ou seja, não se detecte progresso, a ilha é reconfigurada para continuar o processo evolutivo executando o melhor algoritmo bioinspirado até o momento. Essa abordagem é particularmente útil para lidar com problemas de otimização nos quais encontrar soluções ótimas em tempo polinomial é impraticável. O novo modelo com reconfiguração baseada em estagnação computa soluções melhores que as obtidas por uma variedade de MIPs homogêneos e MIPs heterogêneos com reconfiguração aplicada numa frequência fixa.