Metodologia de seleção de algoritmos para problemas de otimização contínua e com formulação black-box

Abstract

Este trabalho apresenta uma metodologia para seleção de algoritmo para problemas de otimização contínua black-box, de forma autônoma. Esta baseia-se nos conceitos de ASP (Algorithm Selection Problem), acopladas com uma estratégia de classificação sensível ao custo dependente dos exemplos, chamada aqui de CSMLR (Regressão logística multinomial sensível ao custo). Como problemas black-box não fornecem informações que possam auxiliar na seleção, utilizou-se dos conceitos de ELA (Exploratory Landscape Analysis) para caracterizar um problema de otimização, a partir de amostragem. Além disso, construiu-se um conjunto de algoritmos, com pontos fortes distintos, para servirem de opções. A metodologia foi testada em um conjunto composto por centenas de funções distintas, tanto disponíveis na literatura quanto geradas neste estudo. Comparou-se o custo total obtido pelo processo de seleção nesse conjunto com o custo de se aplicar cada um dos algoritmos analisados, sem nenhuma distinção entre as funções. O método desenvolvido foi capaz de superar consideravelmente qualquer algoritmo em se tratando de custo total no conjunto, mesmo considerando-se o custo de amostragem. Apesar do processo de seleção apresentar um erro de classificação considerado alto, ele muito raramente indica um algoritmo que não seja capaz de atingir a precisão desejada para um dado problema. Assim, pode-se dizer que o método cumpre seu objetivo de auxiliar o usuário nessa etapa de seleção: mesmo que a indicação não seja a ótima, ela muito provavelmente será adequada.

Abstract : This study presents a methodology of algorithm selection for black-box continuous optimization problems. This is based in the ASP (Algorithm Selection Problem) concepts, coupled with a example dependent cost sensitive strategy, called here by CSMLR. Since black-box problem do not provides any information that helps in the selection process, was used ELA (Exploratory Landscape Analysis) concepts for characterize a optimization problem, by sampling it. Furthermore, was built a set of algorithms, with different strengths, to be options of choice. The methodology was tested in a set composed by hundreds of distinct functions, both available in literature and generated in this study. Was compared the total cost obtained by the selection process in this set with the cost of applying each of the analyzed algorithms, without any distinction between functions. The method was able to overcome considerably any algorithm in terms of total cost in the set, even when sampling cost was added. Although the selection process has a considerably high misclassification error, it rarely select a algorithm that do not be able to solve a given problem. So, it can be said that the method reach it objective of help the user in this selection step: even the selection do not be the best, it likely to be suitable.