【作者】 李鹏；

【导师】 俞国燕；

【作者基本信息】 广东海洋大学 ， 机械制造及其自动化， 2010， 硕士

【摘要】 车间调度问题对企业提高资源利用率、节约成本、提高运行效率起着关键作用。但车间调度问题是一个多目标优化问题,且这些目标之间往往是相互冲突的,传统的解决方法是将多目标优化问题通过一定的处理转化为单目标优化问题,这种处理方法每次实验只能得到单一的最优解。为了得到多个可行较优解,就需要进行多次重复实验,这大大降低了优化效率。因此,研究一种高效的、可解决多目标的、带约束的优化算法来解决诸如车间调度这类实际生产问题,具有重要的理论与实践意义。差分进化(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个作业车间调度的标准测试问题对其进行测试,验证了算法的有效性。最后,对全文进行了总结,并对后续工作作了讨论。更多还原

【Abstract】 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.更多还原