Skip to main content
SpringerLink
Log in

Stochastic online decisioning hyper-heuristic for high dimensional optimization

  • Published:
Applied Intelligence Aims and scope Submit manuscript

Abstract

Most existing heuristic optimizers are found to be restricted to problems of moderate dimensionality, and their performance suffers when solving high-dimensional or large-scale optimization tasks. In this paper, we transform the high-dimensional optimization into online decision making problems and propose a stochastic online decisioning hyper-heuristic framework, by considering multi-armed bandits with temporal reward estimation as our essential backbone. The multi-armed bandit problem simulates an agent which tries to balance exploration and exploitation simultaneously. Specifically, we introduce 1) a sliding time window to assign temporal credit for differing heuristics, and 2) boltzmann exploration for balancing the exploration-exploitation tradeoff. The proposed method is well suited for real-world applications, with flexible compatibility for versatile cost definitions, easy interfaces for heuristics as well as fewer hyper-parameters for consistent generalization performance. Experimental studies on the benchmarks results verify the efficacy and significance of the proposed framework, i.e., when considering three differing heuristics, our method reported consistently competitive performance on benchmark problems with a dimensionality up to 10,000.

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
¥17,985 /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 (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Algorithm 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7

Similar content being viewed by others

Explore related subjects

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

Data Availibility Statement

The datasets generated during and/or analysed during the current study are available from the corresponding author on reasonable request.

Notes

  1. https://github.com/PwnerHarry/SOOPLAT, with the source code of all reproduced algorithms except MOS. We cannot satisfactorily reproduce the algorithm with consistent performance as in the literature. For these algorithms, we used the results directly copied from the literature.

  2. The differences in performance may seem quite significant before comparing with other algorithms.

References

  1. Ma X, Li X, Zhang Q, Tang K, Liang Z, Xie W, Zhu Z (2019) A survey on cooperative co-evolutionary algorithms. IEEE Trans Evol Comput 23(3):421–441

    Article  Google Scholar 

  2. Ge Y, Yu W, Lin Y, Gong Zhan Z, Chen W, Zhang J (2018) Distributed differential evolution based on adaptive mergence and split for large-scale optimization. IEEE Transactions on Cybernetics 48(7):2166–2180

    Article  Google Scholar 

  3. Cheng R, Omidvar MN, Gandomi AH, Sendhoff B, Menzel S, Yao X (2019) Solving incremental optimization problems via cooperative coevolution. IEEE Trans Evol Comput 23(5):762–775

    Article  Google Scholar 

  4. Cao Y, Zhang H, Li W, Zhou M, Zhang Y, Chaovalitwongse WA (2019) Comprehensive learning particle swarm optimization algorithm with local search for multimodal functions. IEEE Trans Evol Comput 23(4):718–731

    Article  Google Scholar 

  5. Eremeev AV, Kovalenko YV (2020) A memetic algorithm with optimal recombination for the asymmetric travelling salesman problem. Memetic Computing 12:23–36

    Article  Google Scholar 

  6. Hiba H, Rahnamayan S, Asilian Bidgoli A, Ibrahim A, khosroshahli R, (2022) A comprehensive investigation on novel center-based sampling for large-scale global optimization. Swarm Evol Comput 73:101105

    Article  Google Scholar 

  7. Ge H, Sun L, Tan G, Chen Z, Chen CLP (2017) Cooperative hierarchical pso with two stage variable interaction reconstruction for large scale optimization. IEEE Transactions on Cybernetics 47(9):2809–2823

    Article  Google Scholar 

  8. Loshchilov I, Glasmachers T, Beyer HG (2019) Large scale black-box optimization by limited-memory matrix adaptation. IEEE Trans Evol Comput 23(2):353–358

    Article  Google Scholar 

  9. Tian Y, Zhang X, Wang C, Jin Y (2020) An evolutionary algorithm for large-scale sparse multiobjective optimization problems. IEEE Trans Evol Comput 24(2):380–393

    Article  Google Scholar 

  10. Feng L, Gupta A, Ong YS (2019) Compressed representation for higher level meme space evolution: a case study on big knapsack problems. Memetic Computing 11:3–17

    Article  Google Scholar 

  11. Xu G, Cui Q, Shi X, Ge H, Zhan ZH, Lee HP, Liang Y, Tai R, Wu C (2019) Particle swarm optimization based on dimensional learning strategy. Swarm Evol Comput 45:33–51

    Article  Google Scholar 

  12. Li Z, Zhang Q, Lin X, Zhen HL (2020) Fast covariance matrix adaptation for large-scale black-box optimization. IEEE Transactions on Cybernetics 50(5):2073–2083

    Article  Google Scholar 

  13. Tseng LY, Chen C (2008) Multiple trajectory search for large scale global optimization. In: 2008 IEEE Congress on Evolutionary Computation (IEEE World Congress on Computational Intelligence), pp. 3052–3059

  14. LaTorre A, Muelas S, Pena JM (2012) Multiple offspring sampling in large scale global optimization. In: 2012 IEEE Congress on Evolutionary Computation (CEC), pp. 1–8

  15. Molina D, Herrera F (2015) MIterative hybridization of DE with local search for the CEC’2015 special session on large scale global optimization. In: 2015 IEEE Congress on Evolutionary Computation (CEC), pp. 1974–1978

  16. Hadi AA, Mohamed AW, Jambi KM (2019) LSHADE-SPA: memetic framework for solving large-scale optimization problems. Complex & Intelligent Systems 5:25–40

    Article  Google Scholar 

  17. Wu G, Mallipeddi R, Suganthan PN (2019) Ensemble strategies for population-based optimization algorithms– A survey. Swarm Evol Comput 44:695–711

  18. Attiya I, Elaziz MA, Abualigah L, Nguyen TN, El-Latif AAA (2022) An improved hybrid swarm intelligence for scheduling iot application tasks in the cloud. IEEE Trans Industr Inf 18(9):6264–6272

    Article  Google Scholar 

  19. Luo J, Liu Z, Zhou M, Xing K (2020) Deadlock-free scheduling of flexible assembly systems based on petri nets and local search. IEEE Transactions on Systems, Man, and Cybernetics: Systems 50(10):3658–3669

    Article  Google Scholar 

  20. Oteiza PP, Ardenghi JI, Brignole NB (2021) Parallel hyper-heuristics for process engineering optimization. Computers & Chemical Engineering 153:107440

    Article  Google Scholar 

  21. Drake JH, Kheiri A, Ozcan E, Burke EK (2020) Recent advances in selection hyper-heuristics. Eur J Oper Res 285(2):405–428

    Article  MathSciNet  Google Scholar 

  22. Lin J, Wang ZJ, Li X (2017) A backtracking search hyper-heuristic for the distributed assembly flow-shop scheduling problem. Swarm and Evolutionary Computation 36, 124–135 (2017)

  23. Kheiri A, Keedwell E (2015) A sequence-based selection hyper-heuristic utilising a hidden markov model. In: Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation, pp. 417–424

  24. Burke EK, Hyde MR, Kendall G, Ochoa G, Özcan E, Woodward JR (2019) A classification of hyper-heuristic approaches: revisited. Handbook of Metaheuristics. Springer, New York, pp 453–477

    Chapter  Google Scholar 

  25. Sallam KM, Chakrabortty RK, Ryan MJ (2021) A reinforcement learning based multi-method approach for stochastic resource constrained project scheduling problems. Expert Syst Appl 169:114479

    Article  Google Scholar 

  26. Shan W, Hu H, Cai Z, Chen H, Liu H, Wang M, Teng Y (2022) Multi strategies boosted mutative crow search algorithm for global tasks: Cases of continuous and discrete optimization. J Bionic Eng 19:1830–1849

    Article  Google Scholar 

  27. Yang J, Yu J, Huang C (2022) Adaptive multistrategy ensemble particle swarm optimization with Signal-to-Noise ratio distance metric. Inf Sci 612:1066–1094

    Article  Google Scholar 

  28. Shao W, Shao Z, Pi D (2022) Multi-local search-based general variable neighborhood search for distributed flow shop scheduling in heterogeneous multi-factories. Appl Soft Comput 125:109–138

    Article  Google Scholar 

  29. Li L, Fang W, Mei Y, Wang Q (2021) Cooperative coevolution for large scale global optimization based on fuzzy decomposition. Soft Comput 25:3593–3608

    Article  Google Scholar 

  30. Parsopoulos KE, Tatsis VA, Kotsireas IS, Pardalos PM (2022) Parallel algorithm portfolios with adaptive resource allocation strategy. Journal of Global Optimization

  31. Yang M, Omidvar MN, Li C, Li X, Cai Z, Kazimipour B, Yao X (2017) Efficient resource allocation in cooperative co-evolution for large-scale global optimization. IEEE Trans Evol Comput 21(4):493–505

    Article  Google Scholar 

  32. Ye S, Dai G, Peng L, Wang M (2014) A hybrid adaptive coevolutionary differential evolution algorithm for large-scale optimization. In: 2014 IEEE Congress on Evolutionary Computation (CEC), pp. 1277–1284

  33. He X, Zhou Y, Chen Z, Zhang J, Chen WN (2021) Large-scale evolution strategy based on search direction adaptation. IEEE Transactions on Cybernetics 51(3):1651–1665

    Article  Google Scholar 

  34. Shahriari B, Swersky K, Wang Z, Adams RP, de Freitas N (2016) Taking the human out of the loop: A review of bayesian optimization. Proc IEEE 104(1):148–175

    Article  Google Scholar 

  35. Martinez-Cantin R (2019) Funneled bayesian optimization for design, tuning and control of autonomous systems. IEEE Transactions on Cybernetics 49(4):1489–1500

    Article  Google Scholar 

  36. DaCosta L, Fialho A, Schoenauer M, Sebag M (2008) Adaptive operator selection with dynamic multi-armed bandits. In: Conference on Genetic and Evolutionary Computation, pp. 913–920

  37. Lordeiro IQ, Haddad DB, Cardoso DO (2022) Multi-armed bandits for minesweeper: Profiting from exploration-exploitation synergy. IEEE Transactions on Games 14(3):403–412

    Article  Google Scholar 

  38. Ai M, Huang Y, Yu J (2021) A non-parametric solution to the multi armed bandit problem with covariates. Journal of Statistical Planning and Inference 211:402–413

    Article  MathSciNet  Google Scholar 

  39. Zameni M, Sadri A, Ghafoori Z, Moshtaghi M, Salim FD, Leckie C, Ramamohanarao K (2020) Unsupervised online change point detection in high-dimensional time series. Knowl Inf Syst 62:719–750

    Article  Google Scholar 

  40. Denton AM, Goetze J, Dusek NS (2022) Iterative sliding window aggregation for generating length-scale-specific fractal features. Knowl Inf Syst 64(12):3463–3489

  41. Chen MR, Huang YY, Zeng GQ, Lu KD, Yang LQ (2021) An improved bat algorithm hybridized with extremal optimization and boltz mann selection. Expert Syst Appl 175:114812

    Article  Google Scholar 

  42. Zhang XY, Gong YJ, Lin Y, Zhang J, Kwong S, Zhang J (2019) Dynamic cooperative coevolution for large scale optimization. IEEE Trans Evol Comput 23(6):935–948

    Article  Google Scholar 

  43. Yang Z, Tang K, Yao X (2008) Large scale evolutionary optimization using cooperative coevolution. Inf Sci 178(15):2985–2999

    Article  MathSciNet  Google Scholar 

  44. Tanabe R, Fukunaga AS (2014) Improving the search performance of SHADE using linear population size reduction. In: 2014 IEEE Congress on Evolutionary Computation (CEC), pp. 1658–1665

  45. Cheng R, Jin Y (2015) A competitive swarm optimizer for large scale optimization. IEEE Transactions on Cybernetics 45(2):191–204

    Article  Google Scholar 

  46. Molina D, LaTorre A, Herrera F (2018) SHADE with iterative local search for large-scale global optimization. In: 2018 IEEE Congress on Evolutionary Computation (CEC), pp. 1–8

  47. Omidvar MN, Yang M, Mei Y, Li X, Yao X (2017) DG2: A faster and more accurate differential grouping for large-scale black-box optimization. IEEE Trans Evol Comput 21(6):929–942

    Article  Google Scholar 

  48. Omidvar MN, Li X, Yao X (2010) Cooperative co-evolution with delta grouping for large scale non-separable function optimization. In: 2010 IEEE Congress on Evolutionary Computation (CEC), pp. 1–8

  49. Liu J, Tang K (2013) Scaling up covariance matrix adaptation evolution strategy using cooperative coevolution. International Conference on Intelligent Data Engineering and Automated Learning. Springer, Berlin, Heidelberg, pp 350–357

    Google Scholar 

  50. Li X, Tang K, Omidvar MN, Yang Z, Qin K (2013) Benchmark functions for the CEC’2013 special session and competition on large-scale global optimization. Technical report, Evolutionary Computing and Machine Learning group, RMIT, Australia

  51. Jian JR, Chen ZG, Zhan ZH, Zhang J (2021) Region encoding helps evolutionary computation evolve faster: A new solution encoding scheme in particle swarm for large-scale optimization. IEEE Trans Evol Comput 25(4):779–793

    Article  Google Scholar 

  52. Yang Q, Zhu Y, Gao X, Xu D, Lu Z (2022) Elite directed particle swarm optimization with historical information for high-dimensional problems. Mathematics 10(9):1384

    Article  Google Scholar 

  53. Sheng M, Wang Z, Liu W, Wang X, Chen S, Liu X (2022) A particle swarm optimizer with multi-level population sampling and dynamic p-learning mechanisms for large-scale optimization. Knowl-Based Syst 242:108382

    Article  Google Scholar 

  54. Li D, Guo W, Lerch A, Li Y, Wang L, Wu Q (2021) An adaptive particle swarm optimizer with decoupled exploration and exploitation for large scale optimization. Swarm Evol Comput 60:100789

    Article  Google Scholar 

Download references

Acknowledgements

This work is supported by the National Natural Science Foundation of China (61976034), the Dalian Science and Technology Innovation Fund (2022JJ12GX013), the Liaoning Natural Science Foundation (2022-YGJC20), and the Fundamental Research Funds for the Central Universities (DUT23YG103).

Author information

Authors and Affiliations

  1. College of Computer Science and Technology, Dalian University of Technology, Dalian, 116023, Liaoning, China

    Wang Xia, Ge Hongwei, Zhao Mingde, Hou Yaqing & Sun Mingyang

Authors
  1. Wang Xia
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Ge Hongwei
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Zhao Mingde
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Hou Yaqing
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Sun Mingyang
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Ge Hongwei.

Ethics declarations

Statements and Declarations

The authors have no conflict of interest. All authors have contributed to the information or material submitted for publication.

Additional information

Publisher's Note

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

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Xia, W., Hongwei, G., Mingde, Z. et al. Stochastic online decisioning hyper-heuristic for high dimensional optimization. Appl Intell 54, 544–564 (2024). https://doi.org/10.1007/s10489-023-05185-0

Download citation

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10489-023-05185-0

Keywords

Search

Navigation