Hart E, Ross P, Nelson J
Department of Artificial Intelligence, University of Edinburgh.
Evol Comput. 1998 Spring;6(1):61-80. doi: 10.1162/evco.1998.6.1.61.
This work addresses the real-life scheduling problem of a Scottish company that must produce daily schedules for the catching and transportation of large numbers of live chickens. The problem is complex and highly constrained. We show that it can be successfully solved by division into two subproblems and solving each using a separate genetic algorithm (GA). We address the problem of whether this produces locally optimal solutions and how to overcome this. We extend the traditional approach of evolving a "permutation + schedule builder" by concentrating on evolving the schedule builder itself. This results in a unique schedule builder being built for each daily scheduling problem, each individually tailored to deal with the particular features of that problem. This results in a robust, fast, and flexible system that can cope with most of the circumstances imaginable at the factory. We also compare the performance of a GA approach to several other evolutionary methods and show that population-based methods are superior to both hill-climbing and simulated annealing in the quality of solutions produced. Population-based methods also have the distinct advantage of producing multiple, equally fit solutions, which is of particular importance when considering the practical aspects of the problem.
这项工作解决了一家苏格兰公司的实际调度问题，该公司必须为大量活鸡的抓捕和运输制定每日调度计划。这个问题复杂且受到高度限制。我们表明，通过将其分为两个子问题并分别使用单独的遗传算法（GA）来解决每个子问题，可以成功解决该问题。我们探讨了这样做是否会产生局部最优解以及如何克服这一问题。我们通过专注于进化调度生成器本身，扩展了传统的“排列 + 调度生成器”进化方法。这导致为每个每日调度问题构建一个独特的调度生成器，每个生成器都针对该问题的特定特征进行了单独定制。这产生了一个强大、快速且灵活的系统，能够应对工厂中大多数可想象的情况。我们还将遗传算法方法的性能与其他几种进化方法进行了比较，并表明基于种群的方法在产生的解的质量方面优于爬山法和模拟退火法。基于种群的方法还具有产生多个同等优度解的明显优势，这在考虑问题的实际方面时尤为重要。
