Semantic-Guided Memetic Genetic Programming for Evolving Scheduling Rules for Online Yard Crane Scheduling

Memetic Genetic Programming (MGP) has shown to be more effective than standard GP in addressing large search spaces by adding local search. However, existing local search procedures in MGP algorithms have three distinct limitations: imbalanced exploration and exploitation, inefficient neighbour generation, and insufficient redundancy handling. This article proposes a two-stage Semantic-Guided MGP (SMGP) to address these limitations and evolve effective scheduling rules. Specifically, three key novel elements are introduced to the existing local search processes of MGP. The first is a Semantic-Guided Neighbourhood Operator maintains behavioural diversity to balance exploration with exploitation. The second is a Knowledge-Guided Subtree Mutation that uses learned semantic structures from the initial stage to construct new neighbours, replacing inefficient random neighbour generation and focusing the search on promising regions. The third is an Iterative Semantic Equivalent Pruning procedure that simplifies the best-found solution into a smaller, equivalent rule to improve its interpretability and generality. Extensive experiments on a real-world online Yard Crane scheduling problem show that SMGP outperforms advanced MGP methods in both effectiveness and efficiency while maintaining rule simplicity. Moreover, the best SMGP-evolved rule significantly outperforms all manually crafted rules.