混合共生生物搜索算法求解置换流水车间调度问题

Hybrid symbiotic organisms search algorithm for permutation flow shop scheduling problem

为了求解置换流水车间调度问题,提出基于共生生物搜索(SOS)算法与局部搜索策略结合的混合共生生物搜索算法.采用最大排序值的优先规则,处理离散的搜索空间.在初始化阶段结合NEH启发式算法以提高初始种群的质量.在优化过程中引入交换变异来改善种群内的多样性,插入-倒转区增加算法跳出局部最优的能力;采用局部搜索策略提升算法的全局探索能力,有效避免了共生生物搜索算法易早熟、后期搜索效率低、易陷入局部最优等缺陷.通过3个最常用、最专业的标准测试集Carlier、Rec和Taillard对算法性能进行测试.与其他多种算法进行比较,验证了提出的混合SOS算法的优越性和稳定性.

A hybrid algorithm based on the combination of symbiotic organism search algorithm(SOS)and local search strategy was proposed in order to solve the permutation flow shop scheduling problem.The largest rank value was adopted to deal with the discrete search space of the problem.The Nawaz Enscore Ham(NEH)heuristic algorithm was combined during initialization stage to improve the quality of the initial population.The diversity within the population was improved using a swap mutation operation during the optimization stage,and the insertreversed block operation was adopted to escape from the local optima.The local search strategy was used to enhance the ability of global search which effectively avoids the drawbacks of the symbiotic organism search algorithm such as ease of premature convergence,low convergence rate and falling into local optimum easily in the later stage.The performance of the proposed algorithm was tested by three most commonly used and professional standard test sets,Carlier,Rec and Taillard.The effectiveness and superiority of the proposed hybrid SOS algorithm was verified by comparing with other algorithms.