直觉模糊集相似度遗传算法求解多目标车间调度问题
|
摘要
为了提高高维多目标置换流水车间调度问题的求解质量,提出基于直觉模糊集相似度的遗传算法(similarity of intuitionistic fuzzy sets GA,SIFS_GA).算法中分别将参考解和Pareto解映射为参考解直觉模糊集和Pareto解直觉模糊集.计算两个集合之间的直觉模糊相似度,用以判断Pareto解的优劣.以直觉模糊集相似度值引导多目标遗传算法进化.对6个CEC标准测试集与10个流水车间调度测试实例进行仿真实验,结果表明SIFS_GA算法性能优于常用的多目标优化算法,且可以有效解决多目标置换流水车间调度问题,尤其在解决规模较大的问题上是一种有效方法.
To obtain better solution of many-objective permutation flow-shop scheduling problems(PFSP),a genetic algorithm based on similarity of intuitionistic fuzzy sets(SIFS_GA)is proposed.In this algorithm,reference solution and Pareto solution are mapped into reference solution intuitionistic fuzzy sets and Pareto solution intuitionistic fuzzy sets respectively.The similarity of intuitionistic fuzzy sets between two sets is calculated and adopted to determine the quality of the Pareto solution.The similarity value of intuitionistic fuzzy sets is used as the fitness value of GA to guide the algorithm evolution.Finally,simulation experiments are carried out with 6 CEC benchmark examples and 10 flow shop scheduling test examples to analyze the proposed algorithm.Experimental results show that SIFS_GA can obtain better results than other commonly used many-objective optimization algorithms,and can effectively solve many-objective flow shop scheduling problems,especially in solving the problem of large scale.
To obtain better solution of many-objective permutation flow-shop scheduling problems(PFSP),a genetic algorithm based on similarity of intuitionistic fuzzy sets(SIFS_GA)is proposed.In this algorithm,reference solution and Pareto solution are mapped into reference solution intuitionistic fuzzy sets and Pareto solution intuitionistic fuzzy sets respectively.The similarity of intuitionistic fuzzy sets between two sets is calculated and adopted to determine the quality of the Pareto solution.The similarity value of intuitionistic fuzzy sets is used as the fitness value of GA to guide the algorithm evolution.Finally,simulation experiments are carried out with 6 CEC benchmark examples and 10 flow shop scheduling test examples to analyze the proposed algorithm.Experimental results show that SIFS_GA can obtain better results than other commonly used many-objective optimization algorithms,and can effectively solve many-objective flow shop scheduling problems,especially in solving the problem of large scale.
引文
[1]PAN Quanke,GAO Liang,LI Xinyu.Flow Shop Scheduling and Its Optimization Algorithm.Wuhan:Huazhong University of Science and Technology Press,2013:20-21.(潘全科,高亮,李新宇.流水车间调度及其优化算法.武汉:华中科技大学出版社,2013:20-21.)
[2]WANG Dazhi,LIU Shixin,GUO Xiwang.A multi-agent evolutionary algorithm for solving total tardiness permutation flow-shop scheduling problem.Acta Automatica Sinica,20 14,40(3):548-555.(王大志,刘士新,郭希旺.求解总拖期时间最小化流水车间调度问题的多智能体进化算法.自动化学报,2014,40(3):548-555.)
[3]ZHANG Xianchao,ZHOU Hong.Variable parameters quantuminspired evolutionary algorithm and its application in permutation flow-shop scheduling problem.Computer Integrated Manufacturing System,2016,22(3):774-781.(张先超,周泓.变参数量子进化算法及其在求解置换流水车间调度问题中的应用.计算机集成制造系统,2016,22(3):774-781.)
[4]LIN J.A hybrid discrete biogeography-based optimization for the permutation flow shop scheduling problem.International Journal of Production Research,2017,54(16):1-10.
[5]LIU Gang,HUANG Chongzheng.Permutation flow shop scheduling based on hybrid discrete artificial bee colony algorithm.Control Engineering of China,2017,24(9):1925-1929.(刘刚,黄崇争.基于HDABC算法的置换流水车间调度策略.控制工程,2017,24(9):1925-1929.)
[6]LU C,GAO L,LI X,et al.Energy-efficient permutation flow shop scheduling problem using a hybrid multi-objective backtracking search algorithm.Journal of Cleaner Production,20 17,144:228-238.
[7]FU Yaping,HUANG Min,WANG Hongfeng,et al.Multipopulation multiobj ective genetic algorithm for multiobj ective permutation flow shop scheduling problem.Control Theory&Applications,20 16,33(10):1281-1288.(付亚平,黄敏,王洪峰,等.面向多目标流水车间调度的多种群多目标遗传算法.控制理论与应用,2016,33(10):1281-1288.)
[8]NGUYEN H.A novel similarity/dissimilarity measure for intuitionistic fuzzy sets and its application in pattern recognition.Expert Systems with Applications,2016,45(C):97-107.
[9]ANANTHI V P,BALASUBRAMANIAM P,RAVEENDRAN P.A thresholding method based on interval-valued intuitionistic fuzzy sets:an application to image segmentation.Pattern Analysis&Applications,2018,21(4):1039-105 1.
[10]YANG J,LI J,WANG Y,et al.Optimization of weapon-target assignment problem by intuitionistic fuzzy genetic algorithm.Application Research of Computers,2018,DOI:10.1051/matecconf/201712802004.
[11]WANG Kaijun,LIN Pinle.Operational safety and reliability assessment of high speed train with intuitionistic fuzzy set and VIKOR method.Computer Systems&Applications,20 17,26(4):29-34.(王开军,林品乐.基于直觉模糊集的灰色模型故障预测.计算机系统应用,2017,26(4):29-34.)
[12]LEI Deming,YAN Xinping.Multi-objective Intelligent Optimization Algorithm and Its Application.Beijing:Science Press,2009:271-272.(雷德明,严新平.多目标智能优化算法及其应用.北京:科学出版社,2009:271-272.)
[13]ATANASSOV K.Intuitionistic fuzzy sets.Fuzzy Sets and System,1986,20(1):87-96.
[14]HE Zhenghong.Research on intuitionistic fuzzy clustering and its application in information fusion.XI'an:Air Force Engineering University,2010.(贺正洪.直觉模糊聚类及其在信息融合中的应用研究.西安:空军工程大学,2010.)
[15]TAO Q,CHANG H,YI Y,et al.A rotary chaotic PSO algorithm for trustworthy scheduling of a grid workflow.Computers&operations research,2011,38(5):824-836.
[16]WANG Ling.Shop Scheduling with Genetic Algorithms[M].Beij ing:Qinghua University Press,2003:51-53.(王凌.车间调度遗传算法.北京:清华大学出版社,2003:51-53.)
[17]CHENG R,LI M,TIAN Y,et al.A benchmark test suite for evolutionary many-obj ective optimization.Complex&Intelligent Systems,2017,3(1):67-81.
[18]ISHIBUCHI H,YOSHIDA T,MURATA T.Balance between genetic search and local search in memetic algorithms for multi-objective permutation flows shop scheduling.IEEE Transactions on Evolutionary Computation,2003,7(2):204-223.
[19]DEB K,JAIN H.An evolutionary many-objective optimization algorithm using reference-point-b ased nondominated sorting approach,part i:solving problems with box constraints.IEEE Transactions on Evolutionary Computation,20 14,18(4):577-601.
[20]DEB K,PRATAP A,AGARWAL S,et al.A fast and elitist multiobjective genetic algorithm:NSGA-II.IEEE Transactions on Evolutionary Computation,2002,6(2):182-197.
[21]MOLINAC J,HERNANDEZ-DíAZ A G,COELLO C A C,et al.g-dominance:reference point based dominance for multiobjective metaheuristics.European Journal of Operational Research,2009,197(2):685-692.
[22]LAUMANNS M.SPEA2:Improving the Strength Pareto Evolutionary Algorithm.Switzerland:Technical Report Gloriastrasse,2001,103.
[23]PAN Q K,TASGETIREN M F,SUGANTHAN P N,et al.A discrete artificial bee colony algorithm for the lot-streaming flow shop scheduling problem.Computer Engineering&Applications,201 1,181(12):2455-2468.
[24]GONG M,JIAO L,DU H,et al.Multiobjective immune algorithm with nondominated neighbor-based selection.Evolutionary Computation,2009,17(1):131.
[25]ABRAHAM A,JAIN L.Evolutionary multi-objective optimization.Theoretical Advances and Applications.Beilin,Germany:SpringVerlag,2006:18-20.
[26]ZITZLER E,THIELE L.Multiobjective evolutionary algorithms:a comparative case study and the strength Pareto approach.Evolutionary Computation,1999,3(4):257-271.
[27]CAO Yangming,ZHOU Yaqin,YANG Jianguo,et al.The research on job-shop scheduling by considering tool constraints.Modern Manufacturing Engineering,2017,(12):1 14-1 18.(曹阳明,周亚勤,杨建国,等.考虑刀具约束的作业车间调度研究.现代制造工程,2017,(12):114-118.)
[28]AI Ziyi,LEI Deming.A novel shuffled frog leaping algorithm for low carbon flexible job shop scheduling.Control Theory&Applications,2017,34(10):1361-1368.(艾子义,雷德明.基于新型蛙跳算法的低碳柔性作业车间调度.控制理论与应用,2017,34(10):1361-1368.)
[2]WANG Dazhi,LIU Shixin,GUO Xiwang.A multi-agent evolutionary algorithm for solving total tardiness permutation flow-shop scheduling problem.Acta Automatica Sinica,20 14,40(3):548-555.(王大志,刘士新,郭希旺.求解总拖期时间最小化流水车间调度问题的多智能体进化算法.自动化学报,2014,40(3):548-555.)
[3]ZHANG Xianchao,ZHOU Hong.Variable parameters quantuminspired evolutionary algorithm and its application in permutation flow-shop scheduling problem.Computer Integrated Manufacturing System,2016,22(3):774-781.(张先超,周泓.变参数量子进化算法及其在求解置换流水车间调度问题中的应用.计算机集成制造系统,2016,22(3):774-781.)
[4]LIN J.A hybrid discrete biogeography-based optimization for the permutation flow shop scheduling problem.International Journal of Production Research,2017,54(16):1-10.
[5]LIU Gang,HUANG Chongzheng.Permutation flow shop scheduling based on hybrid discrete artificial bee colony algorithm.Control Engineering of China,2017,24(9):1925-1929.(刘刚,黄崇争.基于HDABC算法的置换流水车间调度策略.控制工程,2017,24(9):1925-1929.)
[6]LU C,GAO L,LI X,et al.Energy-efficient permutation flow shop scheduling problem using a hybrid multi-objective backtracking search algorithm.Journal of Cleaner Production,20 17,144:228-238.
[7]FU Yaping,HUANG Min,WANG Hongfeng,et al.Multipopulation multiobj ective genetic algorithm for multiobj ective permutation flow shop scheduling problem.Control Theory&Applications,20 16,33(10):1281-1288.(付亚平,黄敏,王洪峰,等.面向多目标流水车间调度的多种群多目标遗传算法.控制理论与应用,2016,33(10):1281-1288.)
[8]NGUYEN H.A novel similarity/dissimilarity measure for intuitionistic fuzzy sets and its application in pattern recognition.Expert Systems with Applications,2016,45(C):97-107.
[9]ANANTHI V P,BALASUBRAMANIAM P,RAVEENDRAN P.A thresholding method based on interval-valued intuitionistic fuzzy sets:an application to image segmentation.Pattern Analysis&Applications,2018,21(4):1039-105 1.
[10]YANG J,LI J,WANG Y,et al.Optimization of weapon-target assignment problem by intuitionistic fuzzy genetic algorithm.Application Research of Computers,2018,DOI:10.1051/matecconf/201712802004.
[11]WANG Kaijun,LIN Pinle.Operational safety and reliability assessment of high speed train with intuitionistic fuzzy set and VIKOR method.Computer Systems&Applications,20 17,26(4):29-34.(王开军,林品乐.基于直觉模糊集的灰色模型故障预测.计算机系统应用,2017,26(4):29-34.)
[12]LEI Deming,YAN Xinping.Multi-objective Intelligent Optimization Algorithm and Its Application.Beijing:Science Press,2009:271-272.(雷德明,严新平.多目标智能优化算法及其应用.北京:科学出版社,2009:271-272.)
[13]ATANASSOV K.Intuitionistic fuzzy sets.Fuzzy Sets and System,1986,20(1):87-96.
[14]HE Zhenghong.Research on intuitionistic fuzzy clustering and its application in information fusion.XI'an:Air Force Engineering University,2010.(贺正洪.直觉模糊聚类及其在信息融合中的应用研究.西安:空军工程大学,2010.)
[15]TAO Q,CHANG H,YI Y,et al.A rotary chaotic PSO algorithm for trustworthy scheduling of a grid workflow.Computers&operations research,2011,38(5):824-836.
[16]WANG Ling.Shop Scheduling with Genetic Algorithms[M].Beij ing:Qinghua University Press,2003:51-53.(王凌.车间调度遗传算法.北京:清华大学出版社,2003:51-53.)
[17]CHENG R,LI M,TIAN Y,et al.A benchmark test suite for evolutionary many-obj ective optimization.Complex&Intelligent Systems,2017,3(1):67-81.
[18]ISHIBUCHI H,YOSHIDA T,MURATA T.Balance between genetic search and local search in memetic algorithms for multi-objective permutation flows shop scheduling.IEEE Transactions on Evolutionary Computation,2003,7(2):204-223.
[19]DEB K,JAIN H.An evolutionary many-objective optimization algorithm using reference-point-b ased nondominated sorting approach,part i:solving problems with box constraints.IEEE Transactions on Evolutionary Computation,20 14,18(4):577-601.
[20]DEB K,PRATAP A,AGARWAL S,et al.A fast and elitist multiobjective genetic algorithm:NSGA-II.IEEE Transactions on Evolutionary Computation,2002,6(2):182-197.
[21]MOLINAC J,HERNANDEZ-DíAZ A G,COELLO C A C,et al.g-dominance:reference point based dominance for multiobjective metaheuristics.European Journal of Operational Research,2009,197(2):685-692.
[22]LAUMANNS M.SPEA2:Improving the Strength Pareto Evolutionary Algorithm.Switzerland:Technical Report Gloriastrasse,2001,103.
[23]PAN Q K,TASGETIREN M F,SUGANTHAN P N,et al.A discrete artificial bee colony algorithm for the lot-streaming flow shop scheduling problem.Computer Engineering&Applications,201 1,181(12):2455-2468.
[24]GONG M,JIAO L,DU H,et al.Multiobjective immune algorithm with nondominated neighbor-based selection.Evolutionary Computation,2009,17(1):131.
[25]ABRAHAM A,JAIN L.Evolutionary multi-objective optimization.Theoretical Advances and Applications.Beilin,Germany:SpringVerlag,2006:18-20.
[26]ZITZLER E,THIELE L.Multiobjective evolutionary algorithms:a comparative case study and the strength Pareto approach.Evolutionary Computation,1999,3(4):257-271.
[27]CAO Yangming,ZHOU Yaqin,YANG Jianguo,et al.The research on job-shop scheduling by considering tool constraints.Modern Manufacturing Engineering,2017,(12):1 14-1 18.(曹阳明,周亚勤,杨建国,等.考虑刀具约束的作业车间调度研究.现代制造工程,2017,(12):114-118.)
[28]AI Ziyi,LEI Deming.A novel shuffled frog leaping algorithm for low carbon flexible job shop scheduling.Control Theory&Applications,2017,34(10):1361-1368.(艾子义,雷德明.基于新型蛙跳算法的低碳柔性作业车间调度.控制理论与应用,2017,34(10):1361-1368.)