Phenotype and Genotype Based Sample Aware Surrogate-Assisted Genetic Programming in Dynamic Flexible Job Shop Scheduling

Genetic programming (GP) has been widely applied to evolve scheduling heuristics for dynamic flexible job shop scheduling (DFJSS). However, the evaluation of GP individuals is computationally expensive, especially in large scale DFJSS scenarios. A k-nearest neighbor (KNN) based surrogate has been successfully used to reduce individual evaluation time for GP by predicting the fitness of an individual with the most similar sample in KNN. Particularly, the phenotypes of GP individuals have been utilised to generate samples for KNN-based surrogates with a precondition that the fitness of individuals with the same phenotype is the same or similar. However, their real fitness may differ greatly due to different input decision situations for fitness calculations in DFJSS. Thus, only considering phenotypes of GP individuals to extract samples could decrease the accuracy of KNN surrogates. This paper proposes a KNN-based surrogate assisted GP algorithm by considering both the phenotype and genotype of GP individuals to generate samples. Specifically, a genotypic characterisation based on terminal frequency is designed to measure the similarity of individual genotypes. The results show that with the same training time, the proposed algorithm can converge fast and achieve better scheduling heuristics than the state-of-the-art algorithms in most examined scenarios. With the same number of generations, the proposed algorithm can obtain comparable performance but only needs about one third training time of baseline GP. The effectiveness of the proposed algorithm is also verified from different aspects, e.g., relation between genotype correlation and fitness difference of individuals, and population diversity.