Svoboda | Graniru | BBC Russia | Golosameriki | Facebook

research-article

Enhancing generalization in genetic programming hyper-heuristics through mini-batch sampling strategies for dynamic workflow scheduling

Authors:

Mengjie ZhangAuthors Info & Claims

Volume 678, Issue C

https://doi.org/10.1016/j.ins.2024.120975

Published: 08 August 2024 Publication History

Abstract

Genetic Programming Hyper-heuristics (GPHH) have been successfully used to evolve scheduling rules for Dynamic Workflow Scheduling (DWS) as well as other challenging combinatorial optimization problems. The method of sampling training instances has a significant impact on the generalization ability of GPHH, yet they are rarely addressed in existing research. This article aims to fill this gap by proposing a GPHH algorithm with a sampling strategy to thoroughly investigate the impact of six instance sampling strategies on algorithmic generalization, including one rotation strategy, three mini-batch strategies, and two hybrid strategies. Experiments across four scenarios with varying settings reveal that: (1) mini-batch with random sampling can outperform rotation in generalizing to unseen workflow scheduling problems under the same computational cost; (2) employing a hybrid strategy that combines rotation and mini-batch further enhances the generalization ability of GPHH; and (3) mini-batch and hybrid strategies can effectively enable heuristics trained on small-scale training instances generalizing well to large-scale unseen ones. These findings highlight the potential of mini-batch strategies in GPHH, offering improved generalization performance while maintaining diversity and suggesting promising avenues for further exploration in GPHH domains.

Highlights

•

GPHH algorithm with instance sampling strategy fills critical research gap.

•

Mini-batch strategies outperform rotation, enhancing generalization.

•

Hybrid strategies further boost generalization ability of GPHH.

•

GPHH with hybrid strategies excels at generalizing to large-scale problem instances.

•

Population diversity analysis enriches GPHH understanding.

References

[1]

S. Abrishami, M. Naghibzadeh, D.H. Epema, Deadline-constrained workflow scheduling algorithms for infrastructure as a service clouds, Future Gener. Comput. Syst. 29 (1) (2013) 158–169.

Digital Library

[2]

S.G. Ahmad, C.S. Liew, M.M. Rafique, E.U. Munir, S.U. Khan, Data-intensive workflow optimization based on application task graph partitioning in heterogeneous computing systems, in: IEEE Fourth International Conference on Big Data and Cloud Computing, IEEE, 2014, pp. 129–136.

[3]

V. Arabnejad, K. Bubendorfer, B. Ng, Dynamic multi-workflow scheduling: a deadline and cost-aware approach for commercial clouds, Future Gener. Comput. Syst. 100 (2019) 98–108.

[4]

S.A. Bello, L.O. Oyedele, O.O. Akinade, M. Bilal, J.M.D. Delgado, L.A. Akanbi, A.O. Ajayi, H.A. Owolabi, Cloud computing in construction industry: use cases, benefits and challenges, Autom. Constr. 122 (2021).

[5]

A. Benlian, W.J. Kettinger, A. Sunyaev, T.J. Winkler, G. Editors, The transformative value of cloud computing: a decoupling, platformization, and recombination theoretical framework, J. Manag. Inf. Syst. 35 (3) (2018) 719–739.

[6]

Y. Bi, B. Xue, M. Zhang, Instance selection-based surrogate-assisted genetic programming for feature learning in image classification, IEEE Trans. Cybern. (2021).

[7]

Y. Bi, B. Xue, M. Zhang, Using a small number of training instances in genetic programming for face image classification, Inf. Sci. 593 (2022) 488–504.

[8]

W. Chen, E. Deelman, Workflowsim: a toolkit for simulating scientific workflows in distributed environments, in: IEEE International Conference on E-Science, IEEE, 2012, pp. 1–8.

[9]

S.Y. Chong, P. Tino, X. Yao, Relationship between generalization and diversity in coevolutionary learning, IEEE Trans. Comput. Intell. AI Games 1 (3) (2009) 214–232.

[10]

W.S. Du, Subtraction and division operations on intuitionistic fuzzy sets derived from the Hamming distance, Inf. Sci. 571 (2021) 206–224.

[11]

K.-R. Escott, H. Ma, G. Chen, Transfer learning assisted gphh for dynamic multi-workflow scheduling in cloud computing, in: Australasian Joint Conference on Artificial Intelligence, Springer, 2022, pp. 440–451.

[12]

K.-R. Escott, H. Ma, G. Chen, Cooperative coevolutionary genetic programming hyper-heuristic for budget constrained dynamic multi-workflow scheduling in cloud computing, in: Evolutionary Computation in Combinatorial Optimization: European Conference, EvoCOP 2023, Springer, 2023, pp. 146–161.

[13]

D. Farinati, I. Bakurov, L. Vanneschi, A study of dynamic populations in geometric semantic genetic programming, Inf. Sci. 648 (2023).

[14]

N. Gazagnadou, R. Gower, J. Salmon, Optimal mini-batch and step sizes for saga, in: International Conference on Machine Learning, in: PMLR, 2019, pp. 2142–2150.

[15]

T. Hildebrandt, J. Branke, On using surrogates with genetic programming, Evol. Comput. 23 (3) (2015) 343–367.

[16]

T. Hildebrandt, J. Heger, B. Scholz-Reiter, Towards improved dispatching rules for complex shop floor scenarios: a genetic programming approach, in: Proceedings of the Genetic and Evolutionary Computation Conference, 2010, pp. 257–264.

[17]

V. Huang, C. Wang, H. Ma, G. Chen, K. Christopher, Cost-aware dynamic multi-workflow scheduling in cloud data center using evolutionary reinforcement learning, in: International Conference on Service-Oriented Computing, Springer, 2022, pp. 449–464.

[18]

M. Hussain, L.-F. Wei, A. Rehman, F. Abbas, A. Hussain, M. Ali, Deadline-constrained energy-aware workflow scheduling in geographically distributed cloud data centers, Future Gener. Comput. Syst. 132 (2022) 211–222.

[19]

G. Ismayilov, H.R. Topcuoglu, Neural network based multi-objective evolutionary algorithm for dynamic workflow scheduling in cloud computing, Future Gener. Comput. Syst. 102 (2020) 307–322.

Digital Library

[20]

A. Jajoo, Y.C. Hu, X. Lin, N. Deng, A case for task sampling based learning for cluster job scheduling, IEEE Trans. Cloud Comput. (2022).

[21]

Keskar, N.S.; Mudigere, D.; Nocedal, J.; Smelyanskiy, M.; Tang, P.T.P. (2016): On large-batch training for deep learning: generalization gap and sharp minima. arXiv preprint arXiv:1609.04836.

[22]

W.B. Langdon, R. Poli, Foundations of Genetic Programming, Springer Science & Business Media, 2013.

[23]

Z. Li, V. Chang, H. Hu, H. Hu, C. Li, J. Ge, Real-time and dynamic fault-tolerant scheduling for scientific workflows in clouds, Inf. Sci. 568 (2021) 13–39.

[24]

B.M. Lima, N. Sachetti, A. Berndt, C. Meinhardt, J.T. Carvalho, Adaptive batch size cgp: improving accuracy and runtime for cgp logic optimization flow, in: Genetic Programming: European Conference, EuroGP 2023, Springer, 2023, pp. 149–164.

[25]

J. Liu, J. Ren, W. Dai, D. Zhang, P. Zhou, Y. Zhang, G. Min, N. Najjari, Online multi-workflow scheduling under uncertain task execution time in iaas clouds, IEEE Trans. Cloud Comput. 9 (3) (2019) 1180–1194.

[26]

Y. Liu, Y. Mei, M. Zhang, Z. Zhang, Automated heuristic design using genetic programming hyper-heuristic for uncertain capacitated arc routing problem, in: Proceedings of the Genetic and Evolutionary Computation Conference, 2017, pp. 290–297.

[27]

Masters, D.; Luschi, C. (2018): Revisiting small batch training for deep neural networks. arXiv preprint arXiv:1804.07612.

[28]

Y. Mei, S. Nguyen, B. Xue, M. Zhang, An efficient feature selection algorithm for evolving job shop scheduling rules with genetic programming, IEEE Trans. Emerg. Top. Comput. Intell. 1 (5) (2017) 339–353.

[29]

S. Nguyen, D. Thiruvady, M. Zhang, D. Alahakoon, Automated design of multipass heuristics for resource-constrained job scheduling with self-competitive genetic programming, IEEE Trans. Cybern. 52 (9) (2021) 8603–8616.

[30]

S. Nguyen, M. Zhang, K.C. Tan, Surrogate-assisted genetic programming with simplified models for automated design of dispatching rules, IEEE Trans. Cybern. 47 (9) (2016) 2951–2965.

[31]

Schaul, T.; Quan, J.; Antonoglou, I.; Silver, D. (2015): Prioritized experience replay. arXiv preprint arXiv:1511.05952.

[32]

S. Wang, Y. Mei, M. Zhang, A multi-objective genetic programming algorithm with α dominance and archive for uncertain capacitated arc routing problem, IEEE Trans. Evol. Comput. (2022).

[33]

X. Xia, H. Qiu, X. Xu, Y. Zhang, Multi-objective workflow scheduling based on genetic algorithm in cloud environment, Inf. Sci. 606 (2022) 38–59.

[34]

J.-P. Xiao, X.-M. Hu, W.-N. Chen, Dynamic cloud workflow scheduling with a heuristic-based encoding genetic algorithm, in: International Conference on Neural Information Processing, Springer, 2020, pp. 38–49.

[35]

Q.-z. Xiao, J. Zhong, L. Feng, L. Luo, J. Lv, A cooperative coevolution hyper-heuristic framework for workflow scheduling problem, IEEE Trans. Serv. Comput. 15 (1) (2019) 150–163.

[36]

Q.-z. Xiao, J. Zhong, L. Feng, L. Luo, J. Lv, A cooperative coevolution hyper-heuristic framework for workflow scheduling problem, IEEE Trans. Serv. Comput. 15 (1) (2022) 150–163.

[37]

M. Xu, Y. Mei, F. Zhang, M. Zhang, A semantic genetic programming approach to evolving heuristics for multi-objective dynamic scheduling, in: Australasian Joint Conference on Artificial Intelligence, Springer, 2023, pp. 403–415.

[38]

M. Xu, Y. Mei, S. Zhu, B. Zhang, T. Xiang, F. Zhang, M. Zhang, Genetic programming for dynamic workflow scheduling in fog computing, IEEE Trans. Serv. Comput. (2023).

[39]

Y. Yang, G. Chen, H. Ma, S. Hartmann, M. Zhang, Dual-tree genetic programming with adaptive mutation for dynamic workflow scheduling in cloud computing, IEEE Trans. Evol. Comput. (2024) 1–15,.

[40]

Y. Yang, G. Chen, H. Ma, M. Zhang, Dual-tree genetic programming for deadline-constrained dynamic workflow scheduling in cloud, in: International Conference on Service-Oriented Computing, Springer, 2022, pp. 433–448.

[41]

Y. Yang, H. Ma, G. Chen, S. Hartmann, A model-driven machine learning approach to dynamic multi-workflow scheduling, in: Proceedings of the International Conference on Conceptual Modeling, 2023.

[42]

Z. Yang, C. Wang, Z. Zhang, J. Li, Mini-batch algorithms with online step size, Knowl.-Based Syst. 165 (2019) 228–240.

[43]

C.-H. Youn, M. Chen, P. Dazzi, Cloud Broker and Cloudlet for Workflow Scheduling, Springer, Singapore, 2017.

[44]

C. Zhang, W. Song, Z. Cao, J. Zhang, P.S. Tan, X. Chi, Learning to dispatch for job shop scheduling via deep reinforcement learning, Adv. Neural Inf. Process. Syst. 33 (2020) 1621–1632.

[45]

F. Zhang, Y. Mei, S. Nguyen, M. Zhang, Phenotype based surrogate-assisted multi-objective genetic programming with brood recombination for dynamic flexible job shop scheduling, in: IEEE Symposium Series on Computational Intelligence, IEEE, 2022, pp. 1218–1225.

[46]

F. Zhang, Y. Mei, S. Nguyen, M. Zhang, K.C. Tan, Surrogate-assisted evolutionary multitask genetic programming for dynamic flexible job shop scheduling, IEEE Trans. Evol. Comput. 25 (4) (2021) 651–665.

Digital Library

[47]

L. Zhang, L. Zhou, A. Salah, Efficient scientific workflow scheduling for deadline-constrained parallel tasks in cloud computing environments, Inf. Sci. 531 (2020) 31–46.

Recommendations

A genetic programming approach to the generation of hyper-heuristics for the uncapacitated examination timetabling problem
EPIA'07: Proceedings of the aritficial intelligence 13th Portuguese conference on Progress in artificial intelligence

Research in the field of examination timetabling has developed in two directions. The first looks at applying various methodologies to induce examination timetables. The second takes an indirect approach to the problem and examines the generation of ...
Enhancing Heuristics for Order Acceptance and Scheduling Using Genetic Programming
Simulated Evolution and Learning
Abstract
Order acceptance and scheduling (OAS) in make-to-order manufacturing systems is a NP-hard problem for which finding optimal solutions for problem instances can be challenging. Because of this, several heuristic approaches have been proposed in the ...
A comparative study of hyper-heuristics for solving the school timetabling problem
SAICSIT '13: Proceedings of the South African Institute for Computer Scientists and Information Technologists Conference

Hyper-heuristics have proven to be an effective means of obtaining generalized solutions to optimization problems. One such domain in which they have been a success is educational timetabling. However, all the research in this area has focused on ...

Comments

Information & Contributors

Information

Published In

Information Sciences: an International Journal Volume 678, Issue C

Sep 2024

1580 pages

ISSN:0020-0255

Issue’s Table of Contents

The Author(s).

Publisher

Elsevier Science Inc.

United States

Publication History

Published: 08 August 2024

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

0
Total Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 18 Aug 2024

Other Metrics

View Author Metrics

Citations

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents