Métricas de Avaliação de Algoritmos de Otimização

Resumo

A área de Otimização trata do estudo de problemas de maximização ou minimização de uma função através de um conjunto de valores viáveis, em um determinado domínio. Os problemas de otimização buscam alcançar a solução ideal para um determinado problema, de forma que possa alcançar com o menor custo e/ou máxima eficiência os objetivos que foram estabelecidos[1]. Para isso, existem diversos algoritmos na literatura que podem ser utilizados para a solução de problemas de otimização [2]. Não ha´, entretanto, técnica de otimização que seja aplicável a toda sorte de problemas que ocorrem na prática. Ou seja, um algoritmo pode ser capaz de solucionar um determinado problema e não ter a mesma capacidade para solucionar outro, não havendo nenhuma forma que garanta encontrar o ponto ótimo global. Desta forma, as últimas décadas tem presenciado um crescimento sem precedentes na criac¸a˜o e aplicação de novos algoritmos e heurísticas para solução de problemas de otimização. Atualmente, a comparação de eficiência entre essas diferentes heurísticas e´ feita mediante a aplicação de benchmarks [1, 3, 7]. Entretanto, tal comparação tem sido feita de forma relativamente livre não havendo um padrão ainda estabelecido de comparação [4]. Analisar a eficiência de algoritmos de otimização e´ de grande importância tanto na área acadêmica quanto na área aplicada. Geralmente, a comparação e´ realizada com um conjunto de algoritmos de forma a se selecionar o que obteve melhor desempenho na solução de uma categoria previamente escolhida de problemas [5]. O desempenho do algoritmo depende de vários fatores, não somente de sua complexidade teórica. Para cada conjunto problema-algoritmo e´ possível medir o tempo computacional, o número de falhas, o erro da solução obtida, entre muitos outros, e analisar esses resultados não e´ uma tarefa fácil. A quantidade de dados obtidos pode ser enorme o que pode dificultar a apresentação e interpretação dos resultados. Com isto, e´ proposto a utilização de performance profiles, uma técnica de comparação de diferentes algoritmos, que combina as melhores características para avaliação de desempenho [6, 2]. A proposta deste trabalho, desenvolvido como dissertação de mestrado, e´ estabelecer uma metodologia baseada no conceito de performance profiles e aplicar tal metodologia na comparação de diferentes estratégias heurísticas de otimização baseada em inteligência computacional em diversos benchmarks [3, 7]. [...]