Composing Algorithm Portfolio with Problem Set of Unknown Distribution
Wenwen Liu, Shiu Yin Yuen, Chi Wan Sung · 2020
Portfolio approaches aim to combine different algorithms and take advantages of their strengths since it is challenging for a single algorithm to solve a problem set with all optimization problems. When there are many algorithms to choose from, there are various algorithm combinations of possibilities. Selecting a well-composed algorithm portfolio becomes essential to solve a problem set efficiently. In this paper, we propose a problem set dependent method to automatically and generically accomplish portfolio construction. The problem set can be composed of any problem, and come from any distribution or any benchmark. To decide which algorithm should be added in the portfolio, we utilize the average rank of results from solving problems to find the best-performing algorithm. Then we select complementary algorithms for the portfolio by applying Pearson correlation coefficient of fitness values. The method then iterates to compose more and more complex portfolios until there is no more improvement. This method is tested under three different problem sets. The experimental result shows the good ability of this approach to detect well-cooperated algorithms; and the composed portfolio is proved to have good adaptability to the problem set.