Extrapolation-Directed Crossover for Job-shop Scheduling Problems: Complementary Combination with JOX
Extrapolation-Directed Crossover for Job-shop Scheduling Problems: Complementary Combination with JOX
复制标题
作业车间调度问题的外推定向交叉：与 JOX 的互补组合
DOI：
10.1109/icsmc.2012.6377727
复制
发表时间：
2000
期刊：
影响因子：
--
通讯作者：
S. Kobayashi
中科院分区：
文献类型：
--
作者：
J. Sakuma;S. Kobayashi
本文提出了一种新的遗传算法，该算法采用两个交叉算子来求解车间作业调度问题。杂交JOX获得了相对较好的结果，但JOX产生的后代存在于双亲周围或在双亲中间区域内。JOX的这一特征导致了整个种群的收敛。为了解决JOX的这一缺陷，我们提出了两个交叉的互补组合。一个是JOX，另一个是edX，这是我们的建议。EDX的设计是通过本地搜索来扩大人口，并探索人口发现的区域。虽然通常将突变应用于探索，但我们将交叉框架应用于edX以实现更有效的探索。具有不同搜索区域的两个交叉器的组合能够弥补彼此的缺陷。用这两个交叉算子设计的遗传算法被应用于大型JSP基准测试，并证明了它的有效性。
In this paper, we propose a new Genetic Algorithm for JSP using two crossovers. The crossover, JOX, obtained relatively good results, however offspring generated by JOX exist around parents or within an intermediate area of them. This feature of JOX induces a convergence of the whole population. To deal with this fault of JOX, we propose a complementary combination of two crossovers. One is JOX, and the other, EDX, is our proposal. EDX is designed to have the population enlarge using a local search and explores the area where the population uncovers. Although a mutation is applied for exploration in general, we apply a framework of crossover to EDX for a more efficient exploration. The combination of two crossovers, which has a different search area, is able to compensate for each other's fault. The GA designed with these two crossovers was applied to large-size JSP benchmarks, and we show its effectiveness.