Towards Interpretable Dispatching Rules: Application of Expression Simplification Methods
Lucija Planinić, Marko Ðurasević, Domagoj Jakobović · 2021 IEEE Symposium Series on Computational Intelligence (SSCI) · 2021
Genetic programming (GP) is a powerful hyper-heuristic method used for evolving dispatching rules (DRs). DRs are commonly used to solve scheduling problems in which scheduling decisions have to be performed in a small amount of time, and are often based on incomplete information. Although GP is the most commonly used method for evolving DRs, it suffers from a serious problem called bloat, which represents the uncontrolled growth of expression trees during evolution. Bloat usually has two important repercussions on the evolved DRs. First, DRs become hard to understand and it is unclear by which strategy they perform scheduling decisions. Secondly, some trees can also include parts that are a result of overfitting on the training set and which reduce their generalization ability. To deal with the problem of bloating DRs, we propose a simplification method consisted of two parts: algebraic reduction and pruning. The simplification method is applied after the normal evolution process with GP is done to reduce the complexity of the evolved DRs. The results demonstrate that it is possible to reduce the number of nodes in an expression tree without significantly deteriorating its performance. This shows that the DRs evolved by GP are bloated and that substantial parts of them are redundant.