Nothing Special   »   [go: up one dir, main page]

skip to main content
10.1145/3512290.3528730acmconferencesArticle/Chapter ViewAbstractPublication PagesgeccoConference Proceedingsconference-collections
research-article

Graph-based linear genetic programming: a case study of dynamic scheduling

Published: 08 July 2022 Publication History

Abstract

Linear genetic programming (LGP) has been successfully applied to various problems such as classification, symbolic regression and hyper-heuristics for automatic heuristic design. In contrast with the traditional tree-based genetic programming (TGP), LGP uses a sequence of instructions to represent an individual (program), and the data is carried by registers. A common issue of LGP is that LGP is susceptible to introns (i.e., instructions with no effect to the program output), which limits the effectiveness of traditional genetic operators. To address these issues, we propose a new graph-based LGP system. Specifically, graph-based LGP uses graph-based crossover and graph-based mutation to produce offspring. The graph-based crossover operator firstly converts each LGP parent to a directed acyclic graph (DAG), and then swaps the sub-graphs between the DAGs. The graph-based mutation selectively modify the connections in DAGs based on the height of sub graphs. To verify the effectiveness of the new graph-based genetic operators, we take the dynamic job shop scheduling as a case study, which has shown to be a challenging problem for LGP. The experimental results show that the LGP with the new graph-based genetic operators can obtain better scheduling heuristics than the LGP with the traditional operators and TGP.

References

[1]
W Banzhaf, M Brameier, M Stautner, and Klaus Weinert. 2003. Genetic Programming and Its Application in Machining Technology. Advances in Computational Intelligence - Theory and Practice (2003), 194--242.
[2]
M. Brameier and W. Banzhaf. 2001. A comparison of linear genetic programming and neural networks in medical data mining. IEEE Transactions on Evolutionary Computation 5, 1 (2001), 17--26.
[3]
Markus Brameier and Wolfgang Banzhaf. 2001. Effective Linear Program Induction. Technical Report. Technical Report CI-108/01, Collaborative Research Center 531, University of Dortmund.
[4]
Markus Brameier and Wolfgang Banzhaf. 2007. Linear genetic programming. Vol. 53.
[5]
Jurgen Branke, Su Nguyen, Christoph W. Pickardt, and Mengjie Zhang. 2016. Automated Design of Production Scheduling Heuristics: A Review. IEEE Transactions on Evolutionary Computation 20, 1 (2016), 110--124.
[6]
Léo Françoso Dal Piccol Sotto and Vinícius Veloso de Melo. 2016. Studying bloat control and maintenance of effective code in linear genetic programming for symbolic regression. Neurocomputing 180 (2016), 79--93.
[7]
Leo Frangoso Dal Piccol Sotto and Vinicius Veloso de Melo. 2017. A probabilistic linear genetic programming with stochastic context-free grammar for solving symbolic regression problems. Proceedings of the Genetic and Evolutionary Computation Conference (2017), 1017--1024.
[8]
Léo Françoso Dal Piccol Sotto, Vinícius Veloso de Melo, and Márcio Porto Basgalupp. 2017. λ-LGP: an improved version of linear genetic programming evaluated in the Ant Trail problem. Knowledge and Information Systems 52, 2 (2017), 445--465.
[9]
Carlton Downey. 2011. Explorations in Parallel Linear Genetic Programming. Ph. D. Dissertation.
[10]
Carlton Downey and Mengjie Zhang. 2011. Caching for Parallel Linear Genetic Programming Categories and Subject Descriptors. In Proceedings of the Annual Conference Companion on Genetic and Evolutionary Computation. 201--202.
[11]
Carlton Downey and Mengjie Zhang. 2011. Execution trace caching for Linear Genetic Programming. In IEEE Congress of Evolutionary Computation. IEEE, 1186--1193.
[12]
Carlton Downey, Mengjie Zhang, and Will N. Browne. 2010. New crossover operators in linear genetic programming for multiclass object classification. Proceedings of the Annual Genetic and Evolutionary Computation Conference (2010), 885--892.
[13]
Carlton Downey, Mengjie Zhang, and Jing Liu. 2012. Parallel Linear Genetic Programming for multi-class classification. Genetic Programming and Evolvable Machines 13, 3 (2012), 275--304.
[14]
Candida Ferreira. 2001. Gene Expression Programming: a New Adaptive Algorithm for Solving Problems. Complex Systems 13, 2 (2001), 87--129. arXiv:0102027 [cs]
[15]
Christopher Fogelberg. 2005. Linear Genetic Programming for Multi-class Classification Problems. Ph. D. Dissertation. Victoria University of Wellington.
[16]
Stefan Forstenlechner, David Fagan, Miguel Nicolau, and Michael O'Neill. 2017. A Grammar Design Pattern for Arbitrary Program Synthesis Problems in Genetic Programming. In European Conference on Genetic Programming, Vol. 10196. 262-- 277.
[17]
M. I. Heywood and A. N. Zincir-Heywood. 2002. Dynamic page based crossover in linear genetic programming. IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics 32, 3 (2002), 380--388.
[18]
Zhixing Huang, Yi Mei, and Mengjie Zhang. 2021. Investigation of Linear Genetic Programming for Dynamic Job Shop Scheduling. In Proceedings of the IEEE Symposium Series on Computational Intelligence. IEEE.
[19]
Wolfgang Kantschik and Wolfgang Banzhaf. 2001. Linear-tree GP and its comparison with other GP structures. In European Conference on Genetic Programming, Vol. 2038. 302--312.
[20]
John R. Koza. 1992. Genetic Programming : On the Programming of Computers By Means of Natural Selection. Cambridge, MA, USA: MIT Press. 1--836 pages.
[21]
Yi Mei, Su Nguyen, and Mengjie Zhang. 2017. Evolving time-invariant dispatching rules in job shop scheduling with genetic programming. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 10196 LNCS (2017), 147--163.
[22]
Julian Miller, Dominic Job, and Vesselin Vassilev. 2000. Principles in the evolutionary design of digital circuits---Part I. Genetic Programming and Evolvable Machines, 1, 1-2 (2000), 7--35.
[23]
Julian Miller, Dominic Job, and Vesselin Vassilev. 2000. Principles in the Evolutionary Design of Digital Circuits---Part II. Genetic Programming and Evolvable Machines 1, 3 (2000), 259--288.
[24]
Jilian F. Miller. 1999. An empirical study of the efficiency of learning boolean functions using a Cartesian Genetic Programming approach. Proceedings of the Genetic and Evolutionary Computation Conference 2, December (1999), 1135--1142.
[25]
Julian F. Miller, Dennis G. Wilson, and Sylvain Cussat-Blanc. 2019. Evolving Developmental Programs That Build Neural Networks for Solving Multiple Problems. In Genetic Programming Theory and Practice XVI. Genetic and Evolutionary Computation. Springer, Cham, 137--178.
[26]
Su Nguyen, Yi Mei, and Mengjie Zhang. 2017. Genetic programming for production scheduling: a survey with a unified framework. Complex & Intelligent Systems 3, 1 (2017), 41--66.
[27]
Su Nguyen, Mengjie Zhang, Mark Johnston, and Kay Chen Tan. 2013. A computational study of representations in genetic programming to evolve dispatching rules for the job shop scheduling problem. IEEE Transactions on Evolutionary Computation 17, 5 (2013), 621--639.
[28]
Peter Nordin. 1994. A compiling genetic programming system that directly manipulates the machine code. Advances in genetic programming 1 (1994), 311-- 331.
[29]
Peter Nordin. 1997. Evolutionary program induction of binary machine code and its applications. Ph. D. Dissertation. University of Dortmund.
[30]
Vinicius Paulo L. Oliveira, Eduardo Faria de Souza, Claire Le Goues, and Celso G. Camilo-Junior. 2018. Improved representation and genetic operators for linear genetic programming for automated program repair. Empirical Software Engineering 23, 5 (2018), 2980--3006.
[31]
Michael O'Neill and Conor Ryan. 2001. Grammatical evolution. IEEE Transactions on Evolutionary Computation 5, 4 (2001), 349--358.
[32]
Michael O'Neill and Conor Ryan. 2003. Grammatical Evolution: Evolutionary Automatic Programming in an Arbitrary Language. Vol. 4.
[33]
P. C.D. Paris, E. C. Pedrino, and M. C. Nicoletti. 2015. Automatic learning of image filters using Cartesian genetic programming. Integrated Computer-Aided Engineering 22, 2 (2015), 135--151.
[34]
Sergejs Provorovs and Arkady Borisov. 2012. Use of Linear Genetic Programming and Artificial Neural Network Methods to Solve Classification Task. Scientific Journal of Riga Technical University. Computer Sciences 45, 1 (2012), 133--139.
[35]
Lee Spector. 2001. Autoconstructive Evolution: Push, PushGP, and Pushpop. In Proceedings of the Genetic and Evolutionary Computation Conference.
[36]
Garnett Wilson and Wolfgang Banzhaf. 2008. A comparison of cartesian genetic programming and linear genetic programming. In Proceedings of European Conference on Genetic Programming. 182--193.
[37]
Fangfang Zhang, Yi Mei, Su Nguyen, Kay Chen Tan, and Mengjie Zhang. 2021. Multitask Genetic Programming-Based Generative Hyperheuristics: A Case Study in Dynamic Scheduling. IEEE Transactions on Cybernetics (2021), 1--14.
[38]
Fangfang Zhang, Yi Mei, Su Nguyen, and Mengjie Zhang. 2021. Collaborative Multifidelity-Based Surrogate Models for Genetic Programming in Dynamic Flexible Job Shop Scheduling. IEEE Transactions on Cybernetics (2021), 1--15.
[39]
Fangfang Zhang, Yi Mei, Su Nguyen, and Mengjie Zhang. 2021. Correlation Coefficient-Based Recombinative Guidance for Genetic Programming Hyperheuristics in Dynamic Flexible Job Shop Scheduling. IEEE Transactions on Evolutionary Computation 25, 3 (2021), 552--566.
[40]
Fangfang Zhang, Yi Mei, Su Nguyen, and Mengjie Zhang. 2021. Evolving Scheduling Heuristics via Genetic Programming With Feature Selection in Dynamic Flexible Job-Shop Scheduling. IEEE Transactions on Cybernetics 51, 4 (2021), 1797--1811.
[41]
Fangfang Zhang, Yi Mei, Su Nguyen, Mengjie Zhang, and Kay Chen Tan. 2021. Surrogate-Assisted Evolutionary Multitasking Genetic Programming for Dynamic Flexible Job Shop Scheduling. IEEE Transactions on Evolutionary Computation 25, 4 (2021), 651--665.
[42]
Fangfang Zhang, Su Nguyen, Yi Mei, and Mengjie Zhang. 2021. Genetic Programming for Production Scheduling: An Evolutionary Learning Approach. In Machine Learning: Foundations, Methodologies, and Applications. Springer, Singapore, XXXIII+338.
[43]
Jinghui Zhong, Liang Feng, and Yew-Soon Soon Ong. 2017. Gene Expression Programming: A Survey [Review Article]. IEEE Computational Intelligence Magazine 12, 3 (2017), 54--72.
[44]
Jinghui Zhong, Yew-Soon Ong, and Wentong Cai. 2016. Self-Learning Gene Expression Programming. IEEE Transactions on Evolutionary Computation 20, 1 (2016), 65--80.

Cited By

View all
  • (2024)Dynamical Sphere Regrouping Particle Swarm Optimization Programming: An Automatic Programming Algorithm Avoiding Premature ConvergenceMathematics10.3390/math1219302112:19(3021)Online publication date: 27-Sep-2024
  • (2024)Neural Architecture Search for Text Classification With Limited Computing Resources Using Efficient Cartesian Genetic ProgrammingIEEE Transactions on Evolutionary Computation10.1109/TEVC.2023.334696928:3(638-652)Online publication date: Jun-2024
  • (2024)Bridging directed acyclic graphs to linear representations in linear genetic programming: a case study of dynamic schedulingGenetic Programming and Evolvable Machines10.1007/s10710-023-09478-825:1Online publication date: 25-Jan-2024

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences
GECCO '22: Proceedings of the Genetic and Evolutionary Computation Conference
July 2022
1472 pages
ISBN:9781450392372
DOI:10.1145/3512290
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 08 July 2022

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. directed acyclic graph
  2. dynamic job shop scheduling
  3. hyper-heuristic
  4. linear genetic programming

Qualifiers

  • Research-article

Conference

GECCO '22
Sponsor:

Acceptance Rates

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)34
  • Downloads (Last 6 weeks)5
Reflects downloads up to 14 Dec 2024

Other Metrics

Citations

Cited By

View all
  • (2024)Dynamical Sphere Regrouping Particle Swarm Optimization Programming: An Automatic Programming Algorithm Avoiding Premature ConvergenceMathematics10.3390/math1219302112:19(3021)Online publication date: 27-Sep-2024
  • (2024)Neural Architecture Search for Text Classification With Limited Computing Resources Using Efficient Cartesian Genetic ProgrammingIEEE Transactions on Evolutionary Computation10.1109/TEVC.2023.334696928:3(638-652)Online publication date: Jun-2024
  • (2024)Bridging directed acyclic graphs to linear representations in linear genetic programming: a case study of dynamic schedulingGenetic Programming and Evolvable Machines10.1007/s10710-023-09478-825:1Online publication date: 25-Jan-2024
  • (2023)Grammar-guided Linear Genetic Programming for Dynamic Job Shop SchedulingProceedings of the Genetic and Evolutionary Computation Conference10.1145/3583131.3590394(1137-1145)Online publication date: 15-Jul-2023

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media