Filipe Saraiva's blog

Tecnologia, sociedade e política.

Quantas metaheurísticas cabem em um fusca?

without comments

Certos problemas de otimização são de solução impossível em tempo computacional hábil – enquanto não for possível provar que P = NP, não haverá algoritmo exato que os resolva. Por outro lado, esses problemas são de grande importância pois modelam situações do mundo real enfrentadas por organizações em geral.

Então, o que fazer? Uma das estratégias é utilizar metaheurísticas, que são métodos de resolução que podem encontram soluções razoáveis para os problemas em tempo aceitável.

Boa parte das metaheurísticas são inspiradas em dinâmicas evolutivas encontradas na natureza, sendo portanto chamadas “bioinspiradas”. Essas dinâmicas partem de uma solução ou conjunto de soluções melhorando-as de forma gradativa. Nesse sentido, os mais diferentes tipos de dinâmicas encontradas na natureza serviram de base para criação de metaheurísticas: do mais conhecido algoritmo genético, baseado na teoria evolucionária do Darwin e na genética, até a maneira como formigas e abelhas buscam por alimento, o processo de memorização do ser humano, o comportamento de enxame de peixes/insetos, e muito mais.

O que no início mostrou-se como a busca por formas mais efetivas de abordar os problemas, acabou por tornar-se uma máquina de criação de novos métodos que pouco contribuem para o domínio de aplicações das metaheurísticas. Hoje em dia é muito comum que na divulgação dos temas das conferências exista uma lista exaustiva com os nomes dessas técnicas.

Parcela significativa dos pesquisadores da área não escondem sua insatisfação com esse cenário, e o pesquisador Sörensen desenvolveu uma crítica contundente no artigo Metaheuristics – the metaphor exposed.

Utilizando uma fina ironia (o artigo inicia descrevendo como a comunidade de físicos reagiria a um trabalho onde a teoria das partículas seria reapresentada a partir de uma metáfora sobre comida!), Sörensen comenta sobre a importância que os métodos bioinspirados tem mas destaca que a atual situação da proliferação de técnicas acaba por não contribuir com o estado da arte da área e também impede que estudos mais relevantes sejam desenvolvidos e discutidos.

O artigo não tem apenas críticas, entretanto: o autor comenta sobre linhas interessantes de pesquisa que podem ser desenvolvidas e que seriam mais relevantes, como estudos comparativos entre operadores, análises teóricas sobre comportamento dos métodos, e mesmo hibridização de métodos já existentes.

Pessoalmente, gosto muito da ideia de pensar as metaheurísticas a partir de seus componentes (por exemplo, metaheurísticas que trabalham a partir de uma solução ou conjunto de soluções; operadores de cruzamento; tabela tabu; feromônios; etc) e tentar recombiná-los de forma a melhorar o desempenho nas aplicações em certos problemas. De fato, já existem até frameworks baseados nessa abordagem, como o Evolving Objects e o ParadisEO.

O artigo de Sörensen merece ser lido e refletido por todos aqueles que pesquisam sobre metaheurísticas. Além de um belo texto com muitas passagens de destaque (por exemplo, há uma dura crítica ao Harmony Search), os pontos negativos e positivos podem servir de insights tanto para pesquisadores veteranos quanto para aqueles que começaram a se aventurar nessa área.

Written by Filipe Saraiva

Março 3rd, 2018 at 4:46 pm

Leave a Reply