[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

A generic method to compose an algorithm portfolio with a problem set of unknown distribution

  • Regular research paper
  • Published:
Memetic Computing Aims and scope Submit manuscript

Abstract

As an individual algorithm rarely outperforms all kinds of optimization problems, algorithm portfolios are proposed to combine algorithms and take advantage of their strengths which fits well the prevalent theme of memetic computing. When there are many algorithms to choose from, the possibilities of algorithm combinations are numerous. Therefore, composing an algorithm portfolio which performs well for a given problem class is essential. In this paper, based on a problem set drawn from any unknown problem class according to an unknown probability distribution, we propose a general method to automatically accomplish portfolio construction. The problem set is used as training data for our method to learn an algorithm portfolio suitable for solving the underlying problem class. To construct the portfolio, algorithms are chosen and added one by one. We first find the best-performing algorithm based on its average rank of solving the training problem set. Its most complementary algorithm is then selected by applying the Pearson correlation coefficient of fitness values at the first hitting time. The method iterates to compose the portfolio with more and more algorithms until there is no more improvement. The experimental results indicate the effectiveness of this approach to select well-cooperated algorithms, and the composed portfolio is shown to have the best rank compared to individual algorithms, elite portfolios and comparison algorithms.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  1. Karaboga D, Akay B (2009) A comparative study of artificial bee colony algorithm. Appl Math Comput 214(1):108–132

    MathSciNet  MATH  Google Scholar 

  2. Kennedy J, Eberhart R (1995) Particle swarm optimization. In: Proceedings of ICNN’95-international conference on neural networks. vol 4, IEEE, pp 1942–1948

  3. Das S, Suganthan PN (2010) Differential evolution: a survey of the state-of-the-art. IEEE Trans Evolut Comput 15(1):4–31

    Article  Google Scholar 

  4. Hansen N (2006) The CMA evolution strategy: a comparing review. In: Towards a new evolutionary computation. Springer, pp 75–102

  5. Fletcher R (2013) Practical methods of optimization. Wiley

  6. Wolpert DH, Macready WG (1997) No free lunch theorems for optimization. IEEE Trans Evolut Comput 1(1):67–82

    Article  Google Scholar 

  7. Garcia-Martinez C, Rodriguez FJ, Manuel L (2012) Arbitrary function optimisation with metaheuristics. Soft Comput 16(12):2115–2133

    Article  Google Scholar 

  8. Kadlec P, Gabrys B (2009) Architecture for development of adaptive on-line prediction models. Memet Comput 1(4):241–269

    Article  Google Scholar 

  9. Burke EK, Gendreau M, Hyde M, Kendall G, Ochoa G, Özcan E, Qu R (2013) Hyper-heuristics: a survey of the state of the art. J Oper Res Soc 64(12):1695–1724

    Article  Google Scholar 

  10. Ertenlice O, Kalayci CB (2018) A survey of swarm intelligence for portfolio optimization: algorithms and applications. Swarm Evolut Comput 39:36–52

    Article  Google Scholar 

  11. Yuen SY, Chow CK, Zhang X, Lou Y (2016) Which algorithm should I choose: an evolutionary algorithm portfolio approach. Appl Soft Comput 40:654–673

    Article  Google Scholar 

  12. He Y, Yuen SY, Lou Y, Zhang X (2019) A sequential algorithm portfolio approach for black box optimization. Swarm Evolut Comput 44:559–570

    Article  Google Scholar 

  13. Vrugt JA, Robinson BA, Hyman JM (2008) Self-adaptive multimethod search for global optimization in real-parameter spaces. IEEE Trans Evolut Comput 13(2):243–259

    Article  Google Scholar 

  14. Peng F, Tang K, Chen G, Yao X (2010) Population-based algorithm portfolios for numerical optimization. IEEE Trans Evolut Comput 14(5):782–800

    Article  Google Scholar 

  15. Akay R, Basturk A, Kalinli A, Yao X (2017) Parallel population-based algorithm portfolios: an empirical study. Neurocomputing 247:115–125

    Article  Google Scholar 

  16. He M, Hu Y, Chen H, Sun L, Wang X, Su W, Liu F, Liang X, Ma L (2019) Lifecycle coevolution framework for many evolutionary and swarm intelligence algorithms fusion in solving complex optimization problems. Swarm Evolut Comput 47:3–20

    Article  Google Scholar 

  17. Muñoz MA, Sun Y, Kirley M, Halgamuge SK (2015) Algorithm selection for black-box continuous optimization problems: a survey on methods and challenges. Inf Sci 317:224–245

    Article  Google Scholar 

  18. Kerschke P, Hoos HH, Neumann F, Trautmann H (2019) Automated algorithm selection: survey and perspectives. Evolut Comput 27(1):3–45

    Article  Google Scholar 

  19. Wu G, Mallipeddi R, Suganthan PN (2019) Ensemble strategies for population-based optimization algorithms—a survey. Swarm Evolut Comput 44:695–711

    Article  Google Scholar 

  20. Tang K, Peng F, Chen G, Yao X (2014) Population-based algorithm portfolios with automated constituent algorithms selection. Inf Sci 279:94–104

    Article  Google Scholar 

  21. Yuen SY, Zhang X (2015) On composing an algorithm portfolio. Memet Comput 7(3):203–214

    Article  Google Scholar 

  22. Yuen SY, Lou Y, Zhang X (2019) Selecting evolutionary algorithms for black box design optimization problems. Soft Comput 23(15):6511–6531

    Article  Google Scholar 

  23. He J, Yao X (2003) Towards an analytic framework for analysing the computation time of evolutionary algorithms. Artif Intell 145(1–2):59–97

    Article  MathSciNet  Google Scholar 

  24. Liu W, Yuen SY, Sung CW (2020) Composing algorithm portfolio with problem set of unknown distribution. In: 2020 IEEE symposium series on computational intelligence (SSCI), pp 814–821

  25. Liang JJ, Qu BY, Suganthan PN, Hernández-Díaz AG (2013) Problem definitions and evaluation criteria for the CEC 2013 special session on real-parameter optimization. Computational Intelligence Laboratory, Zhengzhou University, Zhengzhou, China and Nanyang Technological University, Singapore, Technical Report, 201212(34):281–295

  26. Fan Q, Yan X, Zhang Y (2018) Auto-selection mechanism of differential evolution algorithm variants and its application. Eur J Oper Res 270(2):636–653

    Article  MathSciNet  Google Scholar 

  27. Hong L, Page SE (2004) Groups of diverse problem solvers can outperform groups of high-ability problem solvers. Proc Natl Acad Sci 101(46):16385–16389

    Article  Google Scholar 

  28. Hart E, Sim K (2018) On constructing ensembles for combinatorial optimisation. Evolut Comput 26(1):67–87

    Article  Google Scholar 

  29. Munoz MA, Kirley M (2016) Icarus: identification of complementary algorithms by uncovered sets. In: 2016 IEEE congress on evolutionary computation (CEC). IEEE, pp 2427–2432

  30. Liu S, Tang K, Yao X (2020) Generative adversarial construction of parallel portfolios. IEEE Trans Cybern 52:784–795

    Article  Google Scholar 

  31. Nof Y, Strichman O (2021) Real-time solving of computationally hard problems using optimal algorithm portfolios. Ann Math Artif Intell 89(7):693–710

    Article  MathSciNet  Google Scholar 

  32. Tang K, Liu S, Yang P, Yao X (2021) Few-shots parallel algorithm portfolio construction via co-evolution. IEEE Trans Evolut Comput 25(3):595–607

    Article  Google Scholar 

  33. Luo XJ, Fong KF (2019) Development of integrated demand and supply side management strategy of multi-energy system for residential building application. Appl Energy 242:570–587

    Article  Google Scholar 

  34. Souravlias D, Kotsireas IS, Pardalos PM, Parsopoulos KE (2019) Parallel algorithm portfolios with performance forecasting. Optim Methods Softw 34(6):1231–1250

    Article  MathSciNet  Google Scholar 

  35. Nikolaus H, Anne A, Raymond R, Olaf M, Tea T, Dimo B (2020) Coco: a platform for comparing continuous optimizers in a black-box setting. Optim Methods Softw 36:114–144

    MathSciNet  MATH  Google Scholar 

  36. Gallagher M, Yuan B (2006) A general-purpose tunable landscape generator. IEEE Trans Evolut Comput 10(5):590–603

    Article  Google Scholar 

  37. Rönkkönen J, Li X, Kyrki V, Lampinen J (2011) A framework for generating tunable test functions for multimodal optimization. Soft Comput 15(9):1689–1706

    Article  Google Scholar 

  38. Yang L, Shiu YY (2019) On constructing alternative benchmark suite for evolutionary algorithms. Swarm Evolut Comput 44:287–292

    Article  Google Scholar 

  39. Benesty J, Chen J, Huang Y, Cohen I (2009) Pearson correlation coefficient. In: Noise reduction in speech processing. Springer, pp 1–4

  40. García S, Molina D, Lozano M, Herrera F (2009) A study on the use of non-parametric tests for analyzing the evolutionary algorithms’ behaviour: a case study on the CEC’2005 special session on real parameter optimization. J Heuristics 15(6):617

    Article  Google Scholar 

  41. García-Martínez C, Lozano M, Herrera F, Molina D, Sánchez AM (2008) Global and local real-coded genetic algorithms based on parent-centric crossover operators. Eur J Oper Res 185(3):1088–1113

    Article  Google Scholar 

  42. Brest J, Greiner S, Boskovic B, Mernik M, Zumer V (2006) Self-adapting control parameters in differential evolution: a comparative study on numerical benchmark problems. IEEE Trans Evolut Comput 10(6):646–657

  43. Kai QA, Huang VL, Suganthan PN (2008) Differential evolution algorithm with strategy adaptation for global numerical optimization. IEEE Trans Evolut Comput 13(2):398–417

    Google Scholar 

  44. Zhang J, Sanderson AC (2009) JADE: adaptive differential evolution with optional external archive. IEEE Trans Evolut Comput 13(5):945–958

    Article  Google Scholar 

  45. Wang Y, Cai Z, Zhang Q (2011) Differential evolution with composite trial vector generation strategies and control parameters. IEEE Trans Evolut Comput 15(1):55–66

    Article  Google Scholar 

  46. Tanabe R, Fukunaga AS (2014) Improving the search performance of shade using linear population size reduction. In: 2014 IEEE congress on evolutionary computation (CEC). IEEE, pp 1658–1665

  47. Dekking FM, Kraaikamp C, Lopuhaä HP, Meester LE (2005) A modern introduction to probability and statistics: understanding why and how. Springer Science & Business Media

  48. Zar JH (1999) Biostatistical analysis. Pearson Education India

  49. Hansen N, Finck S, Ros R, Auger A (2009) Real-parameter black-box optimization benchmarking 2009: noiseless functions definitions

Download references

Author information

Authors and Affiliations

  1. Department of Electrical Engineering, City University of Hong Kong, Hong Kong, China

    Wenwen Liu, Shiu Yin Yuen & Chi Wan Sung

Authors
  1. Wenwen Liu
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Shiu Yin Yuen
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Chi Wan Sung
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Shiu Yin Yuen.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Appendix

Appendix

There are three experiments conducted to verify the abilities of the approach proposed in this paper. The problem sets for both composing and testing the portfolios are all randomly sampled by the given distributions. The detailed information of problem sets is recorded in Appendix.

Table 18 Problem set for composing the algorithm portfolio of Experiment 4.3, the first column of Table 7
Full size table
Table 19 Problem set for composing the algorithm portfolio of Experiment 4.3, the second column of Table 7
Full size table
Table 20 Problem set for composing the algorithm portfolio of Experiment 4.3, the third column of Table 7
Full size table
Table 21 Testing Problem set of Experiment 4.3 for 14 algorithms in Table 9
Full size table
Table 22 Testing Problem set of Experiment 4.3 for 6 algorithm portfolios in Fig. 5
Full size table

Tables 10, 11, 12 and 13 cover problem sets in experiment 4.1. In the first experiment, the problems in each problem set is uniformly sampled from BBOB.

Tables 15 and 16 cover problem sets in experiment 4.2. In the second experiment, the problem sets are non-uniformly sampled. The occurrence distribution of problems is that 90% of the problems are sampled from unimodal and linear problems, which are functions 1, 2, 5, 6, 10, 12 of BBOB [49], while the rest of the problems (10%) are randomly selected from other problems.

From Tables 10, 11, 12, 13, 14, 15, 16 and 17 “fxx” represents the function numbers of BBOB and the number following is the instance number. For example, “f15-80” is BBOB suite problem f15 instance 80 in 20D.

Tables 18, 19, 20, 21 and 22 record values of nGaussian, which is the number of Gaussians used in the landscape in experiment 4.3. In the third experiment, the problems in the problem sets are randomly generated from the MSG landscape generator.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Liu, W., Yuen, S.Y. & Sung, C.W. A generic method to compose an algorithm portfolio with a problem set of unknown distribution. Memetic Comp. 14, 287–304 (2022). https://doi.org/10.1007/s12293-022-00367-8

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s12293-022-00367-8

Keywords

Search

Navigation