A Genetic Programming Approach for Evolving Variable Selectors in Constraint Programming
提出一种遗传规划方法，自动进化出高效的变量选择器，以提升约束规划求解器在作业车间调度等组合优化问题中的搜索效率，减少计算量并增加找到最优解的机会。
Operational researchers and decision modelers have aspired to optimization technologies with a self-adaptive mechanism to cope with new problem formulations. Self-adaptive mechanisms not only free users from low-level and complex development tasks to enhance optimization efficiency but also allow them to focus on addressing high-level real-world operational requirements. In recent years, there has been a growing interest in applying machine learning and artificial intelligence techniques to improve self-adaptive mechanisms. However, learning to optimize hard combinatorial optimization problems remains a challenging task. This article proposes a new genetic programming approach to evolve efficient variable selectors to enhance the search mechanism in constraint programming. Starting with a set of training instances for a specific combinatorial optimization problem, the proposed approach evaluates variable selectors and evolves them to be more efficient over a number of generations. The novelties of our proposed approach are threefold: 1) a new representation of variable selectors; 2) a new mechanism for fitness evaluations; and 3) a preselection technique. We examine performance of the proposed approach on different job-shop scheduling problems, and the results show that variable selectors can be evolved efficiently. In particular, there are substantial reductions in the computational effort required for the search component of the constraint solver as well as increased chances of finding the optimal solutions. Further analyses also confirm the efficacy of our approach in respect to scalability, generalization, and interpretability of the evolved variable selectors.