Abstract: In this paper, an improved binary estimation distribution algorithm (I-EDA) is proposed to solve the combinatorial optimization problem such as permutation flow-shop scheduling. The algorithm takes binary distribution estimation algorithm as architecture, using NEH heuristic method to generate higher quality initial solution. The position matrix model and the link matrix model are constructed by statistics and sampling of the dominant solution, and the two matrix models are used to generate the offspring by combining the two probabilities. The two new local search mechanisms are proposed: NEH plug-in recombination strategy and location probabilistic exchange method instead of original adjacent exchange algorithm of the binary distribution estimation algorithm to further filter the optimal solution. The simulation results on Reeves suites and comparisons with other algorithms validate its excellent searching ability and efficiency of the proposed algorithm.

Key words: permutation flow-shop scheduling, binary estimation of distribution algorithms, link blocks, NEH heuristic

摘要： 针对置换流水车间调度这类组合最优化问题的求解,提出了一种改进二元分布估计算法(Improved binary estimation distribution algorithm, I-EDA)。算法以二元分布估计算法为架构,使用NEH(Nawaz-Enscore-Ham)启发式算法生成初始解,提高了初始解的质量;通过对优势解的统计采样构建位置矩阵模型和链接矩阵模型,依照两个矩阵模型的合并概率组合链接区块产生子代。提出了NEH插入式重组策略和基于位置概率的交换策略和两种全新局部搜索机制替代原二元分布估计算法的相邻交换法,以进一步筛选优势解。最后通过对Reeves标准测试集的仿真实验和算法比较验证了所提出算法的有效性。

关键词: 置换流水车间调度, 二元分布估计算法, 链接区块, NEH算法