Surrogate model for memetic genetic programming with application to the one machine scheduling problem with time-varying capacity

• Published in: Expert systems with applications 2023-12, Vol.233, p.120916, Article 120916
• Main Authors: Gil-Gala, Francisco J., Sierra, María R., Mencía, Carlos, Varela, Ramiro
• Format: Article
• Language: English
• Subjects: Evolutionary computation; Hyper-heuristics; Scheduling; Surrogate model
• ISSN: 0957-4174; 1873-6793
• DOI: 10.1016/j.eswa.2023.120916

Surrogate evaluation is a useful, if not the unique, technique in population-based evolutionary algorithms where exact fitness calculation is too expensive. This situation arises, for example, in Genetic Programming (GP) applied to evolve scheduling priority rules, since the evaluation of a candidate rule amounts to solve a large number of problem instances acting as training set. In this paper, a simplified model is proposed that relies on finding and then exploiting a small set of small problem instances, termed filter, such that the evaluation of a rule on the filter may help to estimate the performance of the same rule in solving the training set. The problem of finding the best filter is formulated as a variant of the optimal subset problem, which is solved by means of a Genetic Algorithm (GA). The surrogate evaluation of a new candidate rule consist in solving the instances of the filter. This model is exploited in combination with a Memetic Genetic Program (MGP); the resulting algorithm is termed Surrogate Model MGP (SM-MGP). An experimental study was performed on the problem of scheduling a set of jobs on a machine with varying capacity over time, denoted (1,Cap(t)||∑Ti). The results of this study provided interesting insights into the problems of filter and rules calculation, and showcase that the priority rules evolved by SM-MGP outperform those evolved by MGP. •Formalization of the Optimal Filtering Set Problem (OFSP).•Development of a Genetic Algorithm (GA) for solving the OFSP.•Combination of surrogate evaluation and local search in Genetic Programming.•Analysis and comparison of eleven variants of Genetic Programming on performance.