带约束的多目标进化算法及其应用研究
|
摘要
车间调度问题对企业提高资源利用率、节约成本、提高运行效率起着关键作用。但车间调度问题是一个多目标优化问题,且这些目标之间往往是相互冲突的,传统的解决方法是将多目标优化问题通过一定的处理转化为单目标优化问题,这种处理方法每次实验只能得到单一的最优解。为了得到多个可行较优解,就需要进行多次重复实验,这大大降低了优化效率。因此,研究一种高效的、可解决多目标的、带约束的优化算法来解决诸如车间调度这类实际生产问题,具有重要的理论与实践意义。
差分进化(Differential Evolution,DE)算法是一种高效的、解决连续优化问题的进化算法,本文对如何利用DE算法解决当前工程实际中最常见的多目标约束优化问题作了深入研究。研究内容主要从以下两方面进行:一是研究如何提高DE算法在解决多目标约束优化问题的算法效率;二是研究DE算法在车间调度优化中的应用。
第一部分的研究内容为:
(1)研究了如何将解决单目标、无约束优化问题的标准DE算法用于解决多目标约束优化问题。在对标准DE算法分析研究的基础上,提出了一种基于双群体搜索机制的改进DE算法来解决多目标约束优化问题,采用了两个不同种群分别保存可行个体与不可行个体的双群体约束处理策略,利用基于Pareto的分类排序多目标优化技术来完成对进化个体解的评价。并通过混沌群体初始化、自适应交叉和变异操作来提高DE算法的性能。用三个标准benchmark函数对其进行测试,验证了其解决低维多目标约束优化问题的有效性;
(2)针对标准DE算法在解决多目标优化问题时其多样性与收敛性之间的平衡维持难题,提出了基于自适应动态变异和非支配解二次变异的改进DE算法。用六个标准测试函数对其进行测试,验证了其性能优于非支配排序遗传算法和标准DE算法;
(3)针对标准DE算法在求解多目标优化问题时非支配解数目过少、易陷入局部最优的不足,提出了一种结合分阶段二次变异和混沌理论的改进DE算法来解决多目标约束优化问题。用典型测试问题对其进行测试,验证了所提算法能在全局搜索性能和局部搜索性能之间维持较好平衡。
第二部分的研究内容为:
(1)研究了如何用DE算法来解决多目标流水车间调度问题。主要工作是对标准DE算法进行了改进,使DE算法的应用范围从解决连续优化问题扩展到离散优化问题,构建了适合求解多目标流水车间调度问题的离散DE算法,用经典调度模型的标准测试问题集对其进行测试,验证了算法的有效性;
(2)研究了如何用DE算法来解决更为复杂的多目标作业车间调度问题。主要工作是对标准DE算法进行改进,构建了适合求解多目标作业车间调度问题的离散DE算法,并采用10个作业车间调度的标准测试问题对其进行测试,验证了算法的有效性。
最后,对全文进行了总结,并对后续工作作了讨论。
Job shop scheduling problem plays a key role in enhancing resource utilization rate, reducing cost and advancing operating efficiency for enterprise. But job shop scheduling problem is a multi-objective optimization problem, and these objectives often conflict with each other. For the classical methods, multi-objective optimization problem is usually transformed into a single objective optimization problem, so each test can only obtains a optimal solution. In order to acquire more feasible suboptimal solutions, experiment needs to be repeated over and over again, it greatly reduces the optimizing efficiency. Therefore, research on an efficient constrained optimization algorithm that can solve multi-objective problem, such as the actual production problem-job shop scheduling, is of great significance both on theory and practice.
Differential evolution (DE) algorithm is a very efficient evolutionary algorithm that is used to solve continuous optimization problem. In this paper, how to use DE algorithm to solve multi-objective constrained optimization problem is discussed, which often appears in the current practice engineering. The content of the paper is made of the following two aspects, ons is how to enhance the efficiency of DE algorithm which is used to solve multi-objective constrained optimization problem, the other is research on the application of improved DE algorithm in job shop scheduling problem.
The contents of the first section are as follows:
(1) How to solve multi-objective constrained optimization problem by DE algorithm is studied in detail. Through analyzing and studying of the standard DE algorithm, which is used to solve the problem of unconstrained optimization and single objective. Based on double populations searching scheme, an improved differential evolution algorithm is proposed for multi-objective constrained optimization problem. two different populations are adopted for handling constraints in optimization process, one is for feasible solutions, and the other is for infeasible solutions. To evaluate evolutionary individual, Pareto-based sorted ranking multi-objective technology is adopted. In addition, in order to improve the algorithm performance, population chaotic initialization, adaptive crossover and mutation are adopted at the same time. Through experiments on three benchmark functions with constraints and multi-objectives, it shows that the proposed algorithm is effective for solving multi-objective constrained optimization problem of low dimension.
(2) In order to keep balance between diversity and convergence of differential evolution algorithm in solving multi-objective optimization problem, an improved DE based on adaptive dynamic mutation and second mutation of non-dominance solution was proposed. Through experiments on six benchmark functions with constraints and multi-objectives, it shows that the proposed algorithm is superior to Non-dominated Sorting Genetic Algorithm II and standard DE algorithm in performance.
(3) To avoid shortcomings when the standard DE algorithm is used to solve multi -objective optimization problem, such as the number of Non-dominated solution obtained is too small and the algorithm is easily trapped into local optimum, an advanced differential evolution algorithm combing grading second mutation and chaotic theory is presented to solve multi-objective constrained optimization problem. Benchmarks functions are tested, simulation results show this algorithm has better convergence and distribution property.
The contents of the second section are as follows:
(1) Multi-objective Flow Shop Scheduling Problem (FSSP) based on DE algorithm is studied. The main task is to modify operators of standard DE algorithm and extend its application from continuous optimization problem to discrete optimization problem. Discrete DE algorithm which is suitable for solving multi-objective FSSP is constructed. Experiments on standard testing problem set of classic scheduling model are made, simulation results indicate that the proposed algorithm is effective.
(2) How to use DE algorithm to solve more complicated multi-objective Job-shop Scheduling Problem (JSP) is studied. The main work is to modify standard DE algorithm and construct discrete DE algorithm in order to solve multi-objective JSP. Experiments on ten standard testing problem of JSP are made, simulation results demonstrates the effectiveness of the proposed algorithm.
Finally, summary of the whole paper is given and the future work is discussed.
差分进化(Differential Evolution,DE)算法是一种高效的、解决连续优化问题的进化算法,本文对如何利用DE算法解决当前工程实际中最常见的多目标约束优化问题作了深入研究。研究内容主要从以下两方面进行:一是研究如何提高DE算法在解决多目标约束优化问题的算法效率;二是研究DE算法在车间调度优化中的应用。
第一部分的研究内容为:
(1)研究了如何将解决单目标、无约束优化问题的标准DE算法用于解决多目标约束优化问题。在对标准DE算法分析研究的基础上,提出了一种基于双群体搜索机制的改进DE算法来解决多目标约束优化问题,采用了两个不同种群分别保存可行个体与不可行个体的双群体约束处理策略,利用基于Pareto的分类排序多目标优化技术来完成对进化个体解的评价。并通过混沌群体初始化、自适应交叉和变异操作来提高DE算法的性能。用三个标准benchmark函数对其进行测试,验证了其解决低维多目标约束优化问题的有效性;
(2)针对标准DE算法在解决多目标优化问题时其多样性与收敛性之间的平衡维持难题,提出了基于自适应动态变异和非支配解二次变异的改进DE算法。用六个标准测试函数对其进行测试,验证了其性能优于非支配排序遗传算法和标准DE算法;
(3)针对标准DE算法在求解多目标优化问题时非支配解数目过少、易陷入局部最优的不足,提出了一种结合分阶段二次变异和混沌理论的改进DE算法来解决多目标约束优化问题。用典型测试问题对其进行测试,验证了所提算法能在全局搜索性能和局部搜索性能之间维持较好平衡。
第二部分的研究内容为:
(1)研究了如何用DE算法来解决多目标流水车间调度问题。主要工作是对标准DE算法进行了改进,使DE算法的应用范围从解决连续优化问题扩展到离散优化问题,构建了适合求解多目标流水车间调度问题的离散DE算法,用经典调度模型的标准测试问题集对其进行测试,验证了算法的有效性;
(2)研究了如何用DE算法来解决更为复杂的多目标作业车间调度问题。主要工作是对标准DE算法进行改进,构建了适合求解多目标作业车间调度问题的离散DE算法,并采用10个作业车间调度的标准测试问题对其进行测试,验证了算法的有效性。
最后,对全文进行了总结,并对后续工作作了讨论。
Job shop scheduling problem plays a key role in enhancing resource utilization rate, reducing cost and advancing operating efficiency for enterprise. But job shop scheduling problem is a multi-objective optimization problem, and these objectives often conflict with each other. For the classical methods, multi-objective optimization problem is usually transformed into a single objective optimization problem, so each test can only obtains a optimal solution. In order to acquire more feasible suboptimal solutions, experiment needs to be repeated over and over again, it greatly reduces the optimizing efficiency. Therefore, research on an efficient constrained optimization algorithm that can solve multi-objective problem, such as the actual production problem-job shop scheduling, is of great significance both on theory and practice.
Differential evolution (DE) algorithm is a very efficient evolutionary algorithm that is used to solve continuous optimization problem. In this paper, how to use DE algorithm to solve multi-objective constrained optimization problem is discussed, which often appears in the current practice engineering. The content of the paper is made of the following two aspects, ons is how to enhance the efficiency of DE algorithm which is used to solve multi-objective constrained optimization problem, the other is research on the application of improved DE algorithm in job shop scheduling problem.
The contents of the first section are as follows:
(1) How to solve multi-objective constrained optimization problem by DE algorithm is studied in detail. Through analyzing and studying of the standard DE algorithm, which is used to solve the problem of unconstrained optimization and single objective. Based on double populations searching scheme, an improved differential evolution algorithm is proposed for multi-objective constrained optimization problem. two different populations are adopted for handling constraints in optimization process, one is for feasible solutions, and the other is for infeasible solutions. To evaluate evolutionary individual, Pareto-based sorted ranking multi-objective technology is adopted. In addition, in order to improve the algorithm performance, population chaotic initialization, adaptive crossover and mutation are adopted at the same time. Through experiments on three benchmark functions with constraints and multi-objectives, it shows that the proposed algorithm is effective for solving multi-objective constrained optimization problem of low dimension.
(2) In order to keep balance between diversity and convergence of differential evolution algorithm in solving multi-objective optimization problem, an improved DE based on adaptive dynamic mutation and second mutation of non-dominance solution was proposed. Through experiments on six benchmark functions with constraints and multi-objectives, it shows that the proposed algorithm is superior to Non-dominated Sorting Genetic Algorithm II and standard DE algorithm in performance.
(3) To avoid shortcomings when the standard DE algorithm is used to solve multi -objective optimization problem, such as the number of Non-dominated solution obtained is too small and the algorithm is easily trapped into local optimum, an advanced differential evolution algorithm combing grading second mutation and chaotic theory is presented to solve multi-objective constrained optimization problem. Benchmarks functions are tested, simulation results show this algorithm has better convergence and distribution property.
The contents of the second section are as follows:
(1) Multi-objective Flow Shop Scheduling Problem (FSSP) based on DE algorithm is studied. The main task is to modify operators of standard DE algorithm and extend its application from continuous optimization problem to discrete optimization problem. Discrete DE algorithm which is suitable for solving multi-objective FSSP is constructed. Experiments on standard testing problem set of classic scheduling model are made, simulation results indicate that the proposed algorithm is effective.
(2) How to use DE algorithm to solve more complicated multi-objective Job-shop Scheduling Problem (JSP) is studied. The main work is to modify standard DE algorithm and construct discrete DE algorithm in order to solve multi-objective JSP. Experiments on ten standard testing problem of JSP are made, simulation results demonstrates the effectiveness of the proposed algorithm.
Finally, summary of the whole paper is given and the future work is discussed.
引文
[1]王凌.车间调度及其遗传算法[M].北京:清华大学出版社, 2003: 1-4.
[2] Wang B, Wang F, Zhang Q, et al. Primary structural and quantitative analysis of infeasible solution to job shop scheduling problem[J]. Joural of System Science and System Engineering, 2000, 9(2): 164-170.
[3] Baker K R. A Comparative Study of Flow Shop Algorithms [J]. Ops. Res, 1975, 23: 62-73.
[4]郭冬芬,李铁克.基于约束满足的车间调度算法综述[J].计算机集成制造系统, 2007, 13(1): 117-125.
[5] B. William. The papers of Benjamin Franklin[M]. Yale University Press, New Haven, 1975, 19: 299 -300.
[6] C. Koopmans. Analysis of production as an efficient combination of activities[M]. Activity Analysis of Production and Allocation, John Wiley and Sons, 1951: 33-97.
[7] H. W. Kuhn and A. W. Tucker. Nonlinear programming[C]. Proceedings of the second Berkeley Symposium on Mathematical Statistical and Probability, U. California Press, 1951: 481-491.
[8]刘海林.单目标、多目标最优化进化算法[D].广州:华南理工大学博士学位论文,2002.
[9]孟红云.多目标进化算法及其应用研究[D].西安:西安电子科技大学博士学位论文,2005.
[10] Rosenberg R S. Simulation of genetic populations with biochemical properties[D]. Ph D. dissertation, University of Michigan, Ann Harbor, Michigan, 1967.
[11] Richardson J T, Palmer M R, Liepins F, et al. Some guidelines for genetic algorithms with penalty functions[C]. Proceedings of the Third International Conference on Genetic Algorithms, Morgan -Kauffman, 1989: 191-197.
[12] J D Schaffer. Multiple objective optimization with vector evaluated genetic algorithms[D]. Ph D dissertation, Vanderbilt University, Nashville, TN, 1984.
[13] Fonseca C M, Fleming P J. Genetic Algorithms for Multi-objective Optimization: Formulation, Discussion and Generalization[C]. Proceedings of the Fifth International Conference on Genetic Algorithms, San Mateo, California, 1993: 416-423.
[14] J. Horn, N. Nafpliotis and D. E. Goldberg. A Niched Pareto Genetic Algorithm for Multi-objec–tive Optimization[C]. Proceedings of the First IEEE Conference on Evolutionary Computation,Piscataway USA, 1994: 82-87.
[15] Carlos Artemio Coello. An Empirical Study of Evolutionary Techniques for Multi-objective Optimization in Engineering Design[D]. Ph.D. thesis, Department of Computer Science, Tulane University, New Orleans, LA, apr 1996.
[16] N. Srinivas and K. Deb. Multi-objective optimization using non-dominated sorting in genetic algorithms[J]. Evolutionary Computation, 1994, vol 2(3): 221–248.
[17] K. Deb, A. Pratap, S. Agarwal, et al. A fast and elitist multi-objective genetic algorithm NSGAII[J]. IEEE Transaction on Evolutionary Computation, 2002, vol 6(2): 182-197.
[18] E. Zitzler, L. Thiele. Multi-objective Evolutionary Algorithms: A Comparative Case Study and the Strength Pareto Approach[J]. IEEE Transactions on Evolutionary Computation, 1999, Vol 3(4): 257-271.
[19] E. Zitzler, M. Laumanns and L. Thiele. SPEA2: Improving the strength Pareto evolutionary algorithm, TIK-Report 103, 2001.
[20]马清亮,胡昌华.多目标进化算法及其在控制领域中的应用综述[J].控制与决策, 2006, 5, (21): 481-486.
[21]郭秀萍.多目标进化算法及其在制造系统中的应用研究[D].上海:上海交通大学博士学位论文, 2007.
[22] Storn R, Price K. Differential Evolution-a Simple and Efficient Adaptive Scheme for Global Optimization over Continuous Spaces[J]. Technical Report, International Computer Science Institute, 1995, 8: 22-25.
[23] Ondrej Hrstkaa, Anna Kucerova. Improvements of real coded genetic algorithms based on differential operators preventing premature convergence[J]. Advances in Engineering Software, 2004, 35: 237–246.
[24] Leandro dos S. C. Reliability–redundancy optimization by means of a chaotic differential evolution approach [J]. Chaos, Solitons and Fractals, 2009, 41: 594–602.
[25] Xiao hui Yuan, Yong chuan Zhang, Liang Wang, et al. An enhanced differential evolution algorithm for daily optimal hydro generation scheduling[J]. Computers and Mathematics with Applications, 2008, 55: 2458–2468.
[26] L. Lakshminarasimman, S. Subramanian. A modified hybrid differential evolution for short-term scheduling of hydrothermal power systems with cascaded reservoirs[J]. Energy Conversion and Manage-ment, 2008, 49: 2513–2521.
[27] Hui-Ming Wee, Chien-Chung Lo, Ping-Hui Hsu. A multi-objective joint replenishment inventory model of deteriorated items in a fuzzy environment[J]. European Journal of Operational Research, 2009, 197: 620–631.
[28]孟红云,张小华,刘三阳.用于约束多目标优化问题的双群体差分进化算法[J].计算机学报, 2008, 31(2): 228-235.
[29]王凌,黄付卓,李灵坡.基于混合双种群差分进化的电力系统经济负荷分配[J].控制与决策, 2009, 24(8): 1156-1160,1166.
[30] Sheng-Kuan Wang, Ji-Pyng Chiou, Chih-Wen Liu. Parameters tuning of power system stabilizers using improved ant direction hybrid differential evolution[J]. Electrical Power and Energy Systems, 2009, 31: 34–42.
[31] Leandro D. S. C, Rodrigo C. T. S, Viviana C. M. Improved Differential Evolution Approach Based on Cultural Algorithm and Diversity Measure Applied to Solve Economic Load Dispatch Problems [J]. Mathematics and Computers in Simulation, 2009, 79: 3136–3147.
[32] Johnson S. Optimal two-and-three stage production schedules with setup times included[J]. Naval Research Logistics Quarterly, 1954: 61-68.
[33]潘全科,朱剑英.作业车间动态调度研究[J].南京航空航天大学学报, 2005, 37(2): 262-268.
[34] S. Panwalker, Mafik Iskander. A Survey of Scheduling[J]. Ops. Res, 1977, 25(1): 45-61.
[35] Chen H X, Cheng B C, Proth J M. A more efficient Lagrangian relaxation Proach to job shop scheduling Problems[C]. Proceeds of IEEE International Conference on Robotics and Automation, JaPan, 1995: 469-501.
[36]孙华丽,谢剑英.基于暂态混沌神经网络的多车调度混合优化算法[J].控制与决策, 2007, 22(1): 105-112.
[37] Jeffcoat D, Bulfin R. Simulated annealing for resource-constrained scheduling[J]. European Journal of Operational Research, 1993, 70: 43-51.
[38]王磊,黄文奇.求解工件车间调度问题的一种新的邻域搜索算法[J].计算机学报, 2005, 28(5): 809-816.
[39]邓颖辉,初红艳,费仁元等.双资源多目标车间调度算法研究[J].机械设计与制造, 2009, 12: 15-17.
[40]贾兆红,陈华平,孙耀晖.多目标粒子群优化算法在柔性车间调度中的应用[J].小型微型计算机系统, 2008, 29(5): 885-889.
[41]王万良,赵澄,熊婧等.基于改进蚁群算法的柔性作业车间调度问题的求解方法[J].系统仿真学报, 2008, 20(16): 4326-4329.
[42] Rainer Storn, Kenneth Price. Differential Evolution-A Simple and Efficient Heuristic for Global Optimization over Continuous space[J]. Journal of Global Optimization, 1997, 11: 341-359.
[43]刘波,王凌,金以慧.差分进化算法研究进展[J].控制与决策, 2007, 22(7): 127-927.
[44]周艳平,顾幸生.差分进化算法研究进展[J].化工自动化及仪表, 2007, 34(3): 1-5.
[45]苏海军,杨煜普,王宇嘉.微分进化算法的研究综述[J].系统工程与电子技术, 2008, 30(9): 1793-1797.
[46] Lu Haiming, Yen G. G. Rank-density-based multi-objective genetic algorithm and benchmark test function study[J]. IEEE Transactions on Evolutionary Computation, 2003, 7(4): 325-342.
[47]刘淳安,王宇平.约束多目标优化问题的进化算法及其收敛性[J].系统工程与电子技术, 2007, 29(2): 277-280.
[48] Ponsich A, Azzaro-Pante C, Domenech S. L, et al. Constraint handling strategies in Genetic Algorithms application to optimal batch plant design[J]. Chemical Engineering and Processing, 2008, 47: 420-434.
[49]许小健,黄小平,钱德玲.自适应加速差分进化算法[J].复杂系统与复杂性科学, 2008, 5(1): 87-92.
[50]卢有麟,周建中,李英海等.基于混沌搜索的自适应差分进化算法[J].计算机工程与应用, 2008, 44(10): 31-33.
[51]王跃宣,刘连臣,牟盛静等.处理带约束的多目标优化进化算法[J].清华大学学报(自然科学版), 2005, 45(1): 27-37.
[52]吴亮红,王耀南,周少武等.采用非固定多段映射罚函数的非线性约束优化差分进化算法[J].系统工程理论与实践, 2007, 3: 128-133.
[53] Tan K. C, Goh C. K, Mamun A. A, et al. An evolutionary artificial immune system for multi- objective optimization [J]. European Journal of Operational Research, 2008, 187: 371-392.
[54] Knowles J. D, Corne D. W. On metrics for comparing non-dominated sets[C]. Proceedings of the international congress on evolutionary computation conference (CEC02), IEEE Press, New York, 2002: 711–716.
[55] Rudolph G. Convergence analysis of canonical genetic algorithms[J]. IEEE Transactions onNeural Networks, 1994, 5(1): 96-101.
[56] Luis V. S. Q and Carlos A. C. C. An Algorithm Based on Differential Evolution for Multi- Objective Problems[J]. International Journal of Computational Intelligence Research, 2005, 1(2): 151- 169.
[57] Wenyin Gong, Zhihua Cai. An Improved Multiobjective Differential Evolution Based on Pareto-Adaptiveε-Dominance and Orthogonal Design[J]. European Journal of Operational Re- search, 2009, 198: 576-601.
[58] Bin Qian, Ling Wang, De xian Huang, et al. An Effective Hybrid DE-Based Algorithm for Multi-Objective Flow Shop Scheduling With Limited Buffers[J]. Computers & Operations Res- earch, 2009, 36: 209-233.
[59]牛大鹏,王福利,何大阔等.多目标混沌差分进化算法[J].控制与决策, 2009, 24(3): 361-370.
[60] Weiyi Qian, Ajun Li. Adaptive Differential Evolution Algorithm for Multi-objective Optimi -zation Problems[J]. Applied Mathematics and Computation, 2008, 201: 431-440.
[61] Changsheng Zhang, Jiaxu Ning, Shuai Lu, et al. A Novel Hybrid Differential Evolution and Particle Swarm Optimization Algorithm for Unconstrained Optimization[J]. Operations Research Letters, 2009, 37: 117-122.
[62] Price K, Storn R. Differential Evolution-A Practical Approach to Global Optimization[M]. Berlin, Germany: Springer-Verlag, 2006: 133-152.
[63]俞国燕,李鹏,何真等.一种用于多目标约束优化的改进进化算法[J].计算机集成制造系统, 2009, 15(6): 1172-1179.
[64] Guo Tao, Kang Li Shan. A New Evolutionary Algorithm for Function Optimization [J]. Wuhan University Journal of Natural Sciences, 1999, 4(4): 409-414.
[65] Ursem R. K. Diversity-guided Evolutionary Algorithms[C]. The 7th International Conf: on Parallel Problem Solving from Nature, LNCS 2439. Berlin: Springer, 2002: 462-474.
[66]薛文涛,王强,吴晓蓓.基于特异性免疫策略的遗传算法及应用[J].系统仿真学报, 2008, 20(16): 4315-4322.
[67] Mahamed G. H. O, Ayed S. Constrained optimization using CODEQ[J]. Chaos, Solitons and Fractals, 2009, 42: 662-668.
[68] Leandro dos S. C, Viviana C. M. Chaotic artificial immune approach applied to economicdispatch of electric energy using thermal units[J]. Chaos, Solitons and Fractals, 2009, 40: 2376-2383.
[69] Yuan X. H, Cao .B, Yang B, et al. Hydrothermal scheduling using chaotic hybrid differential evolution[J]. Energy Conversion and Management,2009,49:3627-3633.
[70] Wang Y. J,Zhang J. S. Global optimization by an improved differential evolutionary algorithm [J]. Applied Mathematics and Computation, 2007, 188: 669-680.
[71]程志刚,张立庆,李小林等.基于Tent映射的混沌混合粒子群优化算法[J].系统工程与电子技术, 2007, 29(1): 103-106.
[72]张劲松,李歧强,王朝霞.基于混沌搜索的混和粒子群优化算法[J].山东大学学报(工学版), 2007, 37(1): 47-50.
[73]张浩,张铁男,沈继红等. Tent混沌粒子群算法及其在结构优化决策中的应用[J].控制与决策, 2008, 23(8): 857-862.
[74] Yang L, Chen T. Application of chaos in genetic algorithm[J]. Communications in Theoretical Physics, 2002, 38(2): 168-172.
[75]王凤蕊,王文宏.解决位置管理问题的混沌混合差分进化算法[J].系统仿真学报, 2009, 21(6): 1609-1614.
[76]郭振宇,程博,叶敏等.一种并行混沌差异演化算法[J].西安交通大学学报, 2007, 41(3): 299-302.
[77]周驰,高亮,高海兵.基于PSO的置换流水车间调度算法[J].电子学报, 2006, 34(11): 2008-2011.
[78]徐震浩,顾幸生.不确定条件下的flow shop问题的免疫调度算法[J].系统工程学报, 2005, 20(4): 374-380.
[79]师瑞峰,周泓,上官春霞.混合递进多目标进化算法及其在flow shop排序中的应用[J].系统工程理论与实践, 2006, 8: 101-108.
[80] Harjunkoski I, Grossmann I E. A decomposition approach for the scheduling of a steel plant pro -duction[J]. Computers and Chemical Engineering, 2001, 25(11): 1647-1660.
[81] Mario V A, Coello Coello C A, Onesimo H L. Asymptotic convergence of metaheuristics for multi -objective optimization problems[J]. Soft Computer, 2005.
[82]张超勇,饶运清,李培根.基于POX交叉的遗传算法求解Job-Shop调度问题[J].中国机械工程, 2004, 23(15): 2149-2153.
[83]师瑞峰,周泓,上官春霞.一种求解job shop问题的混合多目标遗传算法[J].计算机工程与应用, 2005, 30: 1-5,133.
[84] Baker K R. Sequencing rules and due-date assignments in job shop[J]. Management Science, 1984, 30(9): 1093-1104.
[85] Sabuncuoglu I, Bayiz M. Job shop scheduling with beam search[J]. European Journal of Operational Research, 1999, 118: 390-412.
[86] Zitzler E,Thiele L. Multi-objective evolutionary algorithms:A comparative case study and the strength Pareto approach[J]. IEEE transaction on Evolutionary Computation , 1999, 3(4): 257-271.
[87] Davis L. Job shop scheduling with genetic algorithms[C]. Proceedings of the First International Conference on Genetic Algorithms. Hillsdale: Lawrence Erlbaum Associates, 1985: 136-140.
[88] K. Itoh, D. Huang and T. Enkawa. Twofold look-ahead search for multi-criterion job shop scheduling[J]. International Journal of Production Research, 1993, 31(9): 2215-2234.
[89] Sakawa M, Kubota R. Fuzzy programming for multiobjective job shop scheduling with fuzzy processing time and fuzzy due date through genetic algorithm[J]. European Journal of Operational Research, 2000, 120: 393-407.
[90] Ponnambalam S. G, Ramkumar V, Jawahar N. A multiobjective genetic algorithm for job shop scheduling[J]. Production Planning and Control, 2001, 12(8): 764-774.
[91] Gorczyca Mateusz, Duenas Alejandra, Petrovic Dobrila. A new multi-bjective genetic algorithm for job shop scheduling with limited resources[C]. 15th International Conference on Systems Science, Wroclaw, Poland, 2004: 201-211.
[92] Lei Deming, Wu Zhiming. Efficient multi-objective evolutionary algorithm for job shop scheduling[J]. Chinese Journal of Mechanical Engineering, 2005, 18(4): 494-497.
[93] R. K. Suresh, K. M. Mohanasundaram. Pareto archived simulated annealing for job shop schedul -ing with multiple objectives[J]. Int J Adv Manuf Technol, 2006(29): 184-196.
[94]雷德明,吴智铭.基于粒子群优化的多目标作业车间调度[J].上海交通大学学报, 2007, 41(11): 1796-1800.
[95]赵韩,高先圣,姜康等.基于免疫遗传算法的多目标柔性作业车间调度研究[J].系统仿真学报, 2008, 20(22): 6163-6168.
[96] D. Y. Sha, Hsing Hung Lin. A multi-objective PSO for job-shop scheduling problems[J]. Expert Systems with Applications, 2010, 37: 1065-1070.
[97] Cheng R W, Gen M, Tsujimura Y. A tutorial survey of job shop scheduling problems usinggenetic algorithms, part II: hybrid genetic search strategies[J]. Computers & Industrial Engineering, 1999, 36: 343-364.
[98]孙志峻,朱剑英,潘全科.基于遗传算法的多资源作业车间智能动态优化调度[J].机械工程学报, 2002, 38(4): 120-125.
[99]玄光男,程润伟著,汪定伟等译.遗传算法与工程设计[M].北京:科学出版社, 2000: 1-2.
[2] Wang B, Wang F, Zhang Q, et al. Primary structural and quantitative analysis of infeasible solution to job shop scheduling problem[J]. Joural of System Science and System Engineering, 2000, 9(2): 164-170.
[3] Baker K R. A Comparative Study of Flow Shop Algorithms [J]. Ops. Res, 1975, 23: 62-73.
[4]郭冬芬,李铁克.基于约束满足的车间调度算法综述[J].计算机集成制造系统, 2007, 13(1): 117-125.
[5] B. William. The papers of Benjamin Franklin[M]. Yale University Press, New Haven, 1975, 19: 299 -300.
[6] C. Koopmans. Analysis of production as an efficient combination of activities[M]. Activity Analysis of Production and Allocation, John Wiley and Sons, 1951: 33-97.
[7] H. W. Kuhn and A. W. Tucker. Nonlinear programming[C]. Proceedings of the second Berkeley Symposium on Mathematical Statistical and Probability, U. California Press, 1951: 481-491.
[8]刘海林.单目标、多目标最优化进化算法[D].广州:华南理工大学博士学位论文,2002.
[9]孟红云.多目标进化算法及其应用研究[D].西安:西安电子科技大学博士学位论文,2005.
[10] Rosenberg R S. Simulation of genetic populations with biochemical properties[D]. Ph D. dissertation, University of Michigan, Ann Harbor, Michigan, 1967.
[11] Richardson J T, Palmer M R, Liepins F, et al. Some guidelines for genetic algorithms with penalty functions[C]. Proceedings of the Third International Conference on Genetic Algorithms, Morgan -Kauffman, 1989: 191-197.
[12] J D Schaffer. Multiple objective optimization with vector evaluated genetic algorithms[D]. Ph D dissertation, Vanderbilt University, Nashville, TN, 1984.
[13] Fonseca C M, Fleming P J. Genetic Algorithms for Multi-objective Optimization: Formulation, Discussion and Generalization[C]. Proceedings of the Fifth International Conference on Genetic Algorithms, San Mateo, California, 1993: 416-423.
[14] J. Horn, N. Nafpliotis and D. E. Goldberg. A Niched Pareto Genetic Algorithm for Multi-objec–tive Optimization[C]. Proceedings of the First IEEE Conference on Evolutionary Computation,Piscataway USA, 1994: 82-87.
[15] Carlos Artemio Coello. An Empirical Study of Evolutionary Techniques for Multi-objective Optimization in Engineering Design[D]. Ph.D. thesis, Department of Computer Science, Tulane University, New Orleans, LA, apr 1996.
[16] N. Srinivas and K. Deb. Multi-objective optimization using non-dominated sorting in genetic algorithms[J]. Evolutionary Computation, 1994, vol 2(3): 221–248.
[17] K. Deb, A. Pratap, S. Agarwal, et al. A fast and elitist multi-objective genetic algorithm NSGAII[J]. IEEE Transaction on Evolutionary Computation, 2002, vol 6(2): 182-197.
[18] E. Zitzler, L. Thiele. Multi-objective Evolutionary Algorithms: A Comparative Case Study and the Strength Pareto Approach[J]. IEEE Transactions on Evolutionary Computation, 1999, Vol 3(4): 257-271.
[19] E. Zitzler, M. Laumanns and L. Thiele. SPEA2: Improving the strength Pareto evolutionary algorithm, TIK-Report 103, 2001.
[20]马清亮,胡昌华.多目标进化算法及其在控制领域中的应用综述[J].控制与决策, 2006, 5, (21): 481-486.
[21]郭秀萍.多目标进化算法及其在制造系统中的应用研究[D].上海:上海交通大学博士学位论文, 2007.
[22] Storn R, Price K. Differential Evolution-a Simple and Efficient Adaptive Scheme for Global Optimization over Continuous Spaces[J]. Technical Report, International Computer Science Institute, 1995, 8: 22-25.
[23] Ondrej Hrstkaa, Anna Kucerova. Improvements of real coded genetic algorithms based on differential operators preventing premature convergence[J]. Advances in Engineering Software, 2004, 35: 237–246.
[24] Leandro dos S. C. Reliability–redundancy optimization by means of a chaotic differential evolution approach [J]. Chaos, Solitons and Fractals, 2009, 41: 594–602.
[25] Xiao hui Yuan, Yong chuan Zhang, Liang Wang, et al. An enhanced differential evolution algorithm for daily optimal hydro generation scheduling[J]. Computers and Mathematics with Applications, 2008, 55: 2458–2468.
[26] L. Lakshminarasimman, S. Subramanian. A modified hybrid differential evolution for short-term scheduling of hydrothermal power systems with cascaded reservoirs[J]. Energy Conversion and Manage-ment, 2008, 49: 2513–2521.
[27] Hui-Ming Wee, Chien-Chung Lo, Ping-Hui Hsu. A multi-objective joint replenishment inventory model of deteriorated items in a fuzzy environment[J]. European Journal of Operational Research, 2009, 197: 620–631.
[28]孟红云,张小华,刘三阳.用于约束多目标优化问题的双群体差分进化算法[J].计算机学报, 2008, 31(2): 228-235.
[29]王凌,黄付卓,李灵坡.基于混合双种群差分进化的电力系统经济负荷分配[J].控制与决策, 2009, 24(8): 1156-1160,1166.
[30] Sheng-Kuan Wang, Ji-Pyng Chiou, Chih-Wen Liu. Parameters tuning of power system stabilizers using improved ant direction hybrid differential evolution[J]. Electrical Power and Energy Systems, 2009, 31: 34–42.
[31] Leandro D. S. C, Rodrigo C. T. S, Viviana C. M. Improved Differential Evolution Approach Based on Cultural Algorithm and Diversity Measure Applied to Solve Economic Load Dispatch Problems [J]. Mathematics and Computers in Simulation, 2009, 79: 3136–3147.
[32] Johnson S. Optimal two-and-three stage production schedules with setup times included[J]. Naval Research Logistics Quarterly, 1954: 61-68.
[33]潘全科,朱剑英.作业车间动态调度研究[J].南京航空航天大学学报, 2005, 37(2): 262-268.
[34] S. Panwalker, Mafik Iskander. A Survey of Scheduling[J]. Ops. Res, 1977, 25(1): 45-61.
[35] Chen H X, Cheng B C, Proth J M. A more efficient Lagrangian relaxation Proach to job shop scheduling Problems[C]. Proceeds of IEEE International Conference on Robotics and Automation, JaPan, 1995: 469-501.
[36]孙华丽,谢剑英.基于暂态混沌神经网络的多车调度混合优化算法[J].控制与决策, 2007, 22(1): 105-112.
[37] Jeffcoat D, Bulfin R. Simulated annealing for resource-constrained scheduling[J]. European Journal of Operational Research, 1993, 70: 43-51.
[38]王磊,黄文奇.求解工件车间调度问题的一种新的邻域搜索算法[J].计算机学报, 2005, 28(5): 809-816.
[39]邓颖辉,初红艳,费仁元等.双资源多目标车间调度算法研究[J].机械设计与制造, 2009, 12: 15-17.
[40]贾兆红,陈华平,孙耀晖.多目标粒子群优化算法在柔性车间调度中的应用[J].小型微型计算机系统, 2008, 29(5): 885-889.
[41]王万良,赵澄,熊婧等.基于改进蚁群算法的柔性作业车间调度问题的求解方法[J].系统仿真学报, 2008, 20(16): 4326-4329.
[42] Rainer Storn, Kenneth Price. Differential Evolution-A Simple and Efficient Heuristic for Global Optimization over Continuous space[J]. Journal of Global Optimization, 1997, 11: 341-359.
[43]刘波,王凌,金以慧.差分进化算法研究进展[J].控制与决策, 2007, 22(7): 127-927.
[44]周艳平,顾幸生.差分进化算法研究进展[J].化工自动化及仪表, 2007, 34(3): 1-5.
[45]苏海军,杨煜普,王宇嘉.微分进化算法的研究综述[J].系统工程与电子技术, 2008, 30(9): 1793-1797.
[46] Lu Haiming, Yen G. G. Rank-density-based multi-objective genetic algorithm and benchmark test function study[J]. IEEE Transactions on Evolutionary Computation, 2003, 7(4): 325-342.
[47]刘淳安,王宇平.约束多目标优化问题的进化算法及其收敛性[J].系统工程与电子技术, 2007, 29(2): 277-280.
[48] Ponsich A, Azzaro-Pante C, Domenech S. L, et al. Constraint handling strategies in Genetic Algorithms application to optimal batch plant design[J]. Chemical Engineering and Processing, 2008, 47: 420-434.
[49]许小健,黄小平,钱德玲.自适应加速差分进化算法[J].复杂系统与复杂性科学, 2008, 5(1): 87-92.
[50]卢有麟,周建中,李英海等.基于混沌搜索的自适应差分进化算法[J].计算机工程与应用, 2008, 44(10): 31-33.
[51]王跃宣,刘连臣,牟盛静等.处理带约束的多目标优化进化算法[J].清华大学学报(自然科学版), 2005, 45(1): 27-37.
[52]吴亮红,王耀南,周少武等.采用非固定多段映射罚函数的非线性约束优化差分进化算法[J].系统工程理论与实践, 2007, 3: 128-133.
[53] Tan K. C, Goh C. K, Mamun A. A, et al. An evolutionary artificial immune system for multi- objective optimization [J]. European Journal of Operational Research, 2008, 187: 371-392.
[54] Knowles J. D, Corne D. W. On metrics for comparing non-dominated sets[C]. Proceedings of the international congress on evolutionary computation conference (CEC02), IEEE Press, New York, 2002: 711–716.
[55] Rudolph G. Convergence analysis of canonical genetic algorithms[J]. IEEE Transactions onNeural Networks, 1994, 5(1): 96-101.
[56] Luis V. S. Q and Carlos A. C. C. An Algorithm Based on Differential Evolution for Multi- Objective Problems[J]. International Journal of Computational Intelligence Research, 2005, 1(2): 151- 169.
[57] Wenyin Gong, Zhihua Cai. An Improved Multiobjective Differential Evolution Based on Pareto-Adaptiveε-Dominance and Orthogonal Design[J]. European Journal of Operational Re- search, 2009, 198: 576-601.
[58] Bin Qian, Ling Wang, De xian Huang, et al. An Effective Hybrid DE-Based Algorithm for Multi-Objective Flow Shop Scheduling With Limited Buffers[J]. Computers & Operations Res- earch, 2009, 36: 209-233.
[59]牛大鹏,王福利,何大阔等.多目标混沌差分进化算法[J].控制与决策, 2009, 24(3): 361-370.
[60] Weiyi Qian, Ajun Li. Adaptive Differential Evolution Algorithm for Multi-objective Optimi -zation Problems[J]. Applied Mathematics and Computation, 2008, 201: 431-440.
[61] Changsheng Zhang, Jiaxu Ning, Shuai Lu, et al. A Novel Hybrid Differential Evolution and Particle Swarm Optimization Algorithm for Unconstrained Optimization[J]. Operations Research Letters, 2009, 37: 117-122.
[62] Price K, Storn R. Differential Evolution-A Practical Approach to Global Optimization[M]. Berlin, Germany: Springer-Verlag, 2006: 133-152.
[63]俞国燕,李鹏,何真等.一种用于多目标约束优化的改进进化算法[J].计算机集成制造系统, 2009, 15(6): 1172-1179.
[64] Guo Tao, Kang Li Shan. A New Evolutionary Algorithm for Function Optimization [J]. Wuhan University Journal of Natural Sciences, 1999, 4(4): 409-414.
[65] Ursem R. K. Diversity-guided Evolutionary Algorithms[C]. The 7th International Conf: on Parallel Problem Solving from Nature, LNCS 2439. Berlin: Springer, 2002: 462-474.
[66]薛文涛,王强,吴晓蓓.基于特异性免疫策略的遗传算法及应用[J].系统仿真学报, 2008, 20(16): 4315-4322.
[67] Mahamed G. H. O, Ayed S. Constrained optimization using CODEQ[J]. Chaos, Solitons and Fractals, 2009, 42: 662-668.
[68] Leandro dos S. C, Viviana C. M. Chaotic artificial immune approach applied to economicdispatch of electric energy using thermal units[J]. Chaos, Solitons and Fractals, 2009, 40: 2376-2383.
[69] Yuan X. H, Cao .B, Yang B, et al. Hydrothermal scheduling using chaotic hybrid differential evolution[J]. Energy Conversion and Management,2009,49:3627-3633.
[70] Wang Y. J,Zhang J. S. Global optimization by an improved differential evolutionary algorithm [J]. Applied Mathematics and Computation, 2007, 188: 669-680.
[71]程志刚,张立庆,李小林等.基于Tent映射的混沌混合粒子群优化算法[J].系统工程与电子技术, 2007, 29(1): 103-106.
[72]张劲松,李歧强,王朝霞.基于混沌搜索的混和粒子群优化算法[J].山东大学学报(工学版), 2007, 37(1): 47-50.
[73]张浩,张铁男,沈继红等. Tent混沌粒子群算法及其在结构优化决策中的应用[J].控制与决策, 2008, 23(8): 857-862.
[74] Yang L, Chen T. Application of chaos in genetic algorithm[J]. Communications in Theoretical Physics, 2002, 38(2): 168-172.
[75]王凤蕊,王文宏.解决位置管理问题的混沌混合差分进化算法[J].系统仿真学报, 2009, 21(6): 1609-1614.
[76]郭振宇,程博,叶敏等.一种并行混沌差异演化算法[J].西安交通大学学报, 2007, 41(3): 299-302.
[77]周驰,高亮,高海兵.基于PSO的置换流水车间调度算法[J].电子学报, 2006, 34(11): 2008-2011.
[78]徐震浩,顾幸生.不确定条件下的flow shop问题的免疫调度算法[J].系统工程学报, 2005, 20(4): 374-380.
[79]师瑞峰,周泓,上官春霞.混合递进多目标进化算法及其在flow shop排序中的应用[J].系统工程理论与实践, 2006, 8: 101-108.
[80] Harjunkoski I, Grossmann I E. A decomposition approach for the scheduling of a steel plant pro -duction[J]. Computers and Chemical Engineering, 2001, 25(11): 1647-1660.
[81] Mario V A, Coello Coello C A, Onesimo H L. Asymptotic convergence of metaheuristics for multi -objective optimization problems[J]. Soft Computer, 2005.
[82]张超勇,饶运清,李培根.基于POX交叉的遗传算法求解Job-Shop调度问题[J].中国机械工程, 2004, 23(15): 2149-2153.
[83]师瑞峰,周泓,上官春霞.一种求解job shop问题的混合多目标遗传算法[J].计算机工程与应用, 2005, 30: 1-5,133.
[84] Baker K R. Sequencing rules and due-date assignments in job shop[J]. Management Science, 1984, 30(9): 1093-1104.
[85] Sabuncuoglu I, Bayiz M. Job shop scheduling with beam search[J]. European Journal of Operational Research, 1999, 118: 390-412.
[86] Zitzler E,Thiele L. Multi-objective evolutionary algorithms:A comparative case study and the strength Pareto approach[J]. IEEE transaction on Evolutionary Computation , 1999, 3(4): 257-271.
[87] Davis L. Job shop scheduling with genetic algorithms[C]. Proceedings of the First International Conference on Genetic Algorithms. Hillsdale: Lawrence Erlbaum Associates, 1985: 136-140.
[88] K. Itoh, D. Huang and T. Enkawa. Twofold look-ahead search for multi-criterion job shop scheduling[J]. International Journal of Production Research, 1993, 31(9): 2215-2234.
[89] Sakawa M, Kubota R. Fuzzy programming for multiobjective job shop scheduling with fuzzy processing time and fuzzy due date through genetic algorithm[J]. European Journal of Operational Research, 2000, 120: 393-407.
[90] Ponnambalam S. G, Ramkumar V, Jawahar N. A multiobjective genetic algorithm for job shop scheduling[J]. Production Planning and Control, 2001, 12(8): 764-774.
[91] Gorczyca Mateusz, Duenas Alejandra, Petrovic Dobrila. A new multi-bjective genetic algorithm for job shop scheduling with limited resources[C]. 15th International Conference on Systems Science, Wroclaw, Poland, 2004: 201-211.
[92] Lei Deming, Wu Zhiming. Efficient multi-objective evolutionary algorithm for job shop scheduling[J]. Chinese Journal of Mechanical Engineering, 2005, 18(4): 494-497.
[93] R. K. Suresh, K. M. Mohanasundaram. Pareto archived simulated annealing for job shop schedul -ing with multiple objectives[J]. Int J Adv Manuf Technol, 2006(29): 184-196.
[94]雷德明,吴智铭.基于粒子群优化的多目标作业车间调度[J].上海交通大学学报, 2007, 41(11): 1796-1800.
[95]赵韩,高先圣,姜康等.基于免疫遗传算法的多目标柔性作业车间调度研究[J].系统仿真学报, 2008, 20(22): 6163-6168.
[96] D. Y. Sha, Hsing Hung Lin. A multi-objective PSO for job-shop scheduling problems[J]. Expert Systems with Applications, 2010, 37: 1065-1070.
[97] Cheng R W, Gen M, Tsujimura Y. A tutorial survey of job shop scheduling problems usinggenetic algorithms, part II: hybrid genetic search strategies[J]. Computers & Industrial Engineering, 1999, 36: 343-364.
[98]孙志峻,朱剑英,潘全科.基于遗传算法的多资源作业车间智能动态优化调度[J].机械工程学报, 2002, 38(4): 120-125.
[99]玄光男,程润伟著,汪定伟等译.遗传算法与工程设计[M].北京:科学出版社, 2000: 1-2.