不可行染色体转换方法

Journal of Systems Engineering and Electronics ›› 2009, Vol. 31 ›› Issue (8): 1892-1896.

不可行染色体转换方法

王林平^1,2, 贾振元¹, 王福吉¹, 赵国凯¹

1. 大连理工大学精密与特种加工教育部重点实验室, 辽宁, 大连, 116024;
2. 烟台大学机电汽车工程学院, 山东, 烟台, 264005

收稿日期:2008-07-30 修回日期:2009-04-20 出版日期:2009-08-20 发布日期:2010-01-03
作者简介:王林平(1963- ),男,副教授,博士,主要研究方向为计算机集成制造系统、复杂产品设计、制造企业信息化、生产调度等.E-mail:qutinwlp@yahoo.com.cn
基金资助:
国家高技术研究发展计划(863计划)(2003AA414022)资助课题

Methods of infeasible chromosome conversion

WANG Lin-ping^1,2, JIA Zhen-yuan¹, WANG Fu-ji¹, ZHAO Guo-kai¹

1. Key Lab. for Precision and Non-traditional Machining Technology of Ministry of Education, Dalian Univ. of Technology, Dalian 116024, China;
2. School of Electromechanical Automobile Engineering, Yantai Univ., Yantai 264005, China

Received:2008-07-30 Revised:2009-04-20 Online:2009-08-20 Published:2010-01-03

摘要/Abstract

摘要： 染色体转换方法是遗传算法求解约束严组合优化问题的重要途径.探讨了转换方法设计及其性能问题,提出了对染色体转换方法的4项性能要求.在介绍综合作业调度问题(complete job shop scheduling problem,CJSSP)概念的基础上,设计了4种转换方法.实验结果表明,4种方法都是可行的,但具有明显不同的效率和质量,与观察结果和算法性能分析一致,为改进求解综合作业调度的遗传算法奠定了基础.

Abstract: Chromosome conversion is vital to genetic algorithm for solving tight-constraint combinatorial optimization problems.The conversion methods and their performances are explored.Four criteria are proposed to weigh conversion methods.Four conversion methods are designed after introducing the complete job shop scheduling problem(CJSSP).Computational results indicate that all methods are viable in application,different in conversion speed and quality,and consistent with observation and analytical conclusions.The methods also underlie modifying genetic algorithm for CJSSP.

中图分类号:

TP301
F406.2

王林平, 贾振元, 王福吉, 赵国凯. 不可行染色体转换方法[J]. Journal of Systems Engineering and Electronics, 2009, 31(8): 1892-1896.

WANG Lin-ping, JIA Zhen-yuan, WANG Fu-ji, ZHAO Guo-kai. Methods of infeasible chromosome conversion[J]. Journal of Systems Engineering and Electronics, 2009, 31(8): 1892-1896.

参考文献

[1] Michalewicz Z.A survey of constraint handling techniques in evolutionary computation methods[C]//Proc.of the Fourth Annual Conference on Evolutionary Programming,MIT Press,Cambridge,MA,1995:135-155.
[2] Coello C A C.Theoretical and numerical constraint-handling techniques used with evolutionary algorithms:a survey of the state of the art[J].Comput.Methods Appl.Mech.Engrg.,2002,191:1245-1287.
[3] 高玉根,程峰,王灿,等.基于违约解转化法的遗传算法及其性能分析[J].电子学报,2006,34(4):638-641.
[4] 郭冬芬,李铁克.基于约束满足的车间调度算法综述[J].计算机集成制造系统,2007,13(1):117-125.
[5] 杨晓梅,曾建潮.采用多个体交叉的遗传算法求解作业车间问题[J].计算机集成制造系统,2004,10(9):1114-1119.
[6] 王超.基于遗传算法的产品装配生产调度优化研究[D].武汉:武汉大学,2005.
[7] 高永超.智能优化算法的性能及搜索空间研究[D].济南:山东大学,2007.
[8] Shi Guoyong,Iima Hitoshi,Sannomiya Nobuo.A new encoding scheme for solving Job shop problems by genetic algorithm[C]//Proc.of the 35th Conference on Decision and Control,Kobe,Japan,1996:4395-4400.
[9] Wang Linping,Jia Zhenyuan,Wang Fuji.Solving complete job shop scheduling problem using genetic algorithm[C]//Proc.of The 7th World Congress on Intelligent Control and Automation,Chongqing,China,2008:8307-8310.
[10] 王凌.车间调度及其遗传算法[M].北京:清华大学出版社,2003.
[11] Jang Y,Jung H,Kim J.Large step optimization approach to flexible job shop scheduling[J].WSEAS Trans.on Circuits and Systems,2003,2(4):752-758.
[12] Staudacher A P.ISTS:a new procedure for the integrated scheduling of multi-stage systems[J].Int.J.Prod.Res.,2000,38(11):2489-2514.
[13] Goldberg D E,Deb K,Korb B.Messy genetic algorithms revisited:studies in mixed size and scale[J].Complex Systems,1990,4:415-444.
[14] Sharman D M,Yassine A A.Characterizing complex product architectures[J].Systems Engineering,2004,7(1):35-69.

[1]	路复宇, 童宁宁, 冯为可, 万鹏程. 自适应杂交退火粒子群优化算法[J]. 系统工程与电子技术, 2022, 44(11): 3470-3476.
[2]	孙田野, 孙伟, 吴建军. 改进Quatre算法的无人机编队快速集结方法[J]. 系统工程与电子技术, 2022, 44(9): 2840-2848.
[3]	闫世瑛, 颜克斐, 方伟, 陆恒杨. 基于差分进化邻域自适应的大规模多目标算法[J]. 系统工程与电子技术, 2022, 44(7): 2112-2124.
[4]	汤安迪, 韩统, 徐登武, 周欢, 谢磊. 使用高斯分布估计策略的改进樽海鞘群算法[J]. 系统工程与电子技术, 2022, 44(7): 2229-2240.
[5]	庞维建, 李辉, 黄谦, 李朋, 马贤明. 基于本体的无人系统任务规划研究综述[J]. 系统工程与电子技术, 2022, 44(3): 908-920.
[6]	曾斌, 王睿, 李厚朴, 樊旭. 基于强化学习的战时保障力量调度策略研究[J]. 系统工程与电子技术, 2022, 44(1): 199-208.
[7]	马威强, 高永琪, 赵苗. 基于全局最优和差分变异的头脑风暴优化算法[J]. 系统工程与电子技术, 2022, 44(1): 270-278.
[8]	魏锋涛, 张洋洋, 黎俊宇, 史云鹏. 基于动态分级策略的改进正余弦算法[J]. 系统工程与电子技术, 2021, 43(6): 1596-1605.
[9]	丁嘉辉, 汤建龙, 于正洋. 轻量化的增量式集成学习算法设计[J]. 系统工程与电子技术, 2021, 43(4): 861-867.
[10]	刘家义, 岳韶华, 王刚, 姚小强, 张杰. 复杂任务下的多智能体协同进化算法[J]. 系统工程与电子技术, 2021, 43(4): 991-1002.
[11]	刘越, 仲小清, 付金宇, 李想. 基于混合优化方法的立体匹配算法[J]. 系统工程与电子技术, 2020, 42(12): 2692-2699.
[12]	徐涛, 吴志帅, 卢敏, 吕宗磊, 李忠虎. 面向拥堵问题的枢纽航线网络优化模型[J]. 系统工程与电子技术, 2020, 42(11): 2553-2559.
[13]	王前东. 经典轨迹的相似度量快速算法[J]. 系统工程与电子技术, 2020, 42(10): 2189-2196.
[14]	姚智海, 刘建平, 王建平, 李伟, 任勃. 地面测控资源调度效能评估指标体系[J]. 系统工程与电子技术, 2020, 42(8): 1751-1758.
[15]	刘家义, 岳韶华, 王刚, 张杰, 姚小强. 多平台分布式协同作战下基于MPC-MAS的指挥控制模型设计[J]. 系统工程与电子技术, 2020, 42(7): 1582-1589.