期刊
IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION
卷 25, 期 3, 页码 492-507出版社
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TEVC.2021.3050465
关键词
Optimization; Job shop scheduling; Search problems; Schedules; Programming; Constraint handling; Training; Genetic programming (GP); heuristics; job-shop scheduling (JSS); makespan; tardiness
资金
- David Myers Research Fellowship from La Trobe University
- Marsden Fund of New Zealand Government [VUW1509]
The article introduces a new genetic programming approach to optimize the search mechanism in constraint programming by evolving efficient variable selectors. The results demonstrate that evolved variable selectors can significantly reduce the computational effort of the search solver and increase the likelihood of finding optimal solutions.
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据