- author = "Zhixing Huang and Yi Mei and Fangfang Zhang and Mengjie Zhang",
- title = "Graph-based Linear Genetic Programming: A Case Study of Dynamic Scheduling",
- booktitle = "Proceedings of the 2022 Genetic and Evolutionary Computation Conference",
- year = "2022",
- editor = "Alma Rahat and Jonathan Fieldsend and Markus Wagner and Sara Tari and Nelishia Pillay and Irene Moser and Aldeida Aleti and Ales Zamuda and Ahmed Kheiri and Erik Hemberg and Christopher Cleghorn and Chao-li Sun and Georgios Yannakakis and Nicolas Bredeche and Gabriela Ochoa and Bilel Derbel and Gisele L. Pappa and Sebastian Risi and Laetitia Jourdan and Hiroyuki Sato and Petr Posik and Ofer Shir and Renato Tinos and John Woodward and Malcolm Heywood and Elizabeth Wanner and Leonardo Trujillo and Domagoj Jakobovic and Risto Miikkulainen and Bing Xue and Aneta Neumann and Richard Allmendinger and Inmaculada Medina-Bulo and Slim Bechikh and Andrew M. Sutton and Pietro Simone Oliveto",
- pages = "955--963",
- address = "Boston, USA",
- series = "GECCO '22",
- month = "9-13 " # jul,
- organisation = "SIGEVO",
- publisher = "Association for Computing Machinery",
- publisher_address = "New York, NY, USA",
- keywords = "genetic algorithms, genetic programming, hyper-heuristic, directed acyclic graph, linear genetic programming, building block, intron, dynamic job shop scheduling, DJSS",
- isbn13 = "978-1-4503-9237-2",
-
DOI = "
doi:10.1145/3512290.3528730",
-
video_url = "
https://vimeo.com/723510274",
- size = "9 pages",
- 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.",
-
notes = "p955 'introns are in the sub-graphs that are isolated
from the main DAG.' 'often destruct useful building
blocks (i.e., topological structures of effective
instructions).'
genetic operators 'select only the instructions contributing to the final program output for modification. Specifically, the graph-based crossover operator selects a sub-graph from the DAGs corresponding to both parents and swaps them. The graph-based mutation mutates registers (i.e.,connection in DAGs) based on the height of sub-graphs.'
p957 crossover 'swaps the two sub-graphs to generate two offspring'. Graph-based Mutation 'tend to obtain a wider DAG with more parallel branches', 'increase ... large sub-graphs and reuse larger building blocks'.
GECCO-2022 A Recombination of the 31st International Conference on Genetic Algorithms (ICGA) and the 27th Annual Genetic Programming Conference (GP)",
