求解置换流水线调度问题的混合离散果蝇算法

A hybrid discrete fruit fly optimization algorithm for solving permutation flow-shop scheduling problem

中文关键词  置换流水车间调度  离散果蝇算法  协作进化  混合算法

英文关键词  permutation flow-shop scheduling  discrete fruit fly optimization algorithm  co-evolution  hybrid algorithm

中文摘要

      针对置换流水线调度问题, 提出了一种新颖的混合离散果蝇算法. 算法每一代进化包括4个搜索阶段: 嗅觉 搜索、视觉搜索、协作进化和退火过程. 在嗅觉搜索阶段, 采用插入方式生成邻域解; 在视觉搜索阶段, 选择最优邻 域解更新个体; 在协作进化阶段, 基于果蝇个体间的差分信息产生引导个体; 在退火操作阶段, 以一定概率接受最 优引导个体从而更新种群. 同时, 通过试验设计方法对算法参数设置进行了分析, 并确定了合适的参数组合. 最后, 通过基于标准测试集的仿真结果和算法比较验证了所提算法的有效性和鲁棒性.

英文摘要

      To solve the permutation flow-shop scheduling problem (PFSP), we propose a novel hybrid discrete fruit fly optimization algorithm (HDFOA). Each generation of evolution in the algorithm contains four search stages: smell-based search, vision-based search, co-evolutionary search and annealing procedure. In the smell-based search stage, an insertion operator is adopted to produce neighbors. In the vision-based search stage, the individuals are replaced by their best neighbors. In the co-evolutionary search stage, the guiding individuals are produced based on the differential information among fruit flies. In the annealing procedure, the best guiding fruit flies are accepted according to certain acceptance probabilities for updating the population. Moreover, the effect from parameter setting is analyzed by using the experiment design method, and a combination of suitable parameter values is determined. Finally, simulation results and comparisons based on the benchmark testing sets demonstrate the effectiveness and robustness of the proposed algorithm.