基于混合差分进化的多目标工艺规划和调度研究

Process planning and scheduling (PPS) is an important and hot research topic in flexible manufacturing system (FMS) due to its complexity, fundamentality and importance. Owing to the complicated and practical characteristics as well as the ability of providing the many Pareto optimal solutions with incommensurable quality for decision makers, multiobjective optimization is great difficulty problem in PPS. Therefore, it will provide significant impacts on academic and application areas to do research on multiobjective evolutionary algorithm (MOEA) for such typical combinatorial optimization problem in real-world production scheduling. This project major concerns the multiobjective optimization of PPS and attempts to propose a new hybrid differential evolution (DE) framework, a special design of fitness evaluation function, a novel hybrid selection mechanism, a distinct elitism preservation strategy and a masterly combined local search technology basing on multiple objectives, to enhance the convergence and distribution performances, while reducing the time complexity of the algorithm as much as possible. The main achievements of this study lie in the series of guidance values at theory and application of algorithms for designing of hybrid MOEA framework, searching with multiple directions, balancing of convergence and distribution performances, improving of efficiency, etc. The investigation of hybrid DE on solving multiobjective PPS with multiple resources constraints in FMS will promote the research and development of complex intelligent manufacturing system.

工艺规划和调度以其基础性、重要性以及复杂性，成为柔性制造系统领域研究的重点和热点。而多目标优化因其复杂性、现实性以及给决策者提供更多更实际的备选方案集等特征，成为工艺规划和调度研究中的难点。研究此类实际生产调度中典型组合优化问题的多目标进化算法具有重要的学术意义和应用价值。本项目围绕工艺规划和调度的多目标优化，通过创新的混合差分进化框架构建、特殊的适应度评价函数设计、新颖的混合选择机制、独特的精英保存策略以及基于多个目标的混合局部搜索技术等，以增强算法在Pareto前沿面多个方向上的收敛性能并保证算法的均匀分布性能，同时尽可能的降低算法的时间复杂度。本研究旨在混合进化算法框架设计、方向性搜索、收敛和分布性能平衡以及效率提高等方面取得一系列有指导价值的理论与算法应用成果。本项目对于混合差分进化解决多资源约束条件下的多目标工艺规划和调度问题的研究，将有利于推动复杂智能加工制造系统的研究和发展。

多目标工艺规划和调度的多资源约束、先后顺序约束以及多目标特征，是生产调度优化研究中的关键问题和进化多目标优化算法领域的研究难点。项目围绕工艺规划和调度的多目标优化，主要研究了集成规划和调度编解码方式和进化操作、混合差分进化算法框架设计、方向性搜索增强策略以提高算法的收敛速度和均匀分布能力。本课题设计了集成工艺规划和调度并适应多约束多目标特征的多向量编解码方式，以及与之相适应的交叉和变异操作，并提出了与目标相适应的局部搜索增强方式。针对之前算法的分布性能和收敛速度不足问题，设计了混合多目标进化算法框架，该算法混合了基于向量的遗传算法和基于支配和被支配关系的适应度评价函数及其精英种群更新机制，使得算法快速收敛到帕累托前沿面的中心区域和边界区域，从而提高算法的收敛速度，同时自然的提高了算法的均匀分布能力，而且由于不计算个体间的拥挤程度，大大降低了算法的时间复杂度。为了进一步提高算法的性能，提出了混合差分进化算法，该算法在混合多目标进化算法的提高收敛和分布能力的基础上，针对每代得到的精英种群，进一步应用差分进化算法。该算法根据个体的适应度评价函数值的差异，决定个体的下一步的可能搜索方向，引导个体向着真实帕累托前沿面进一步收敛，或者沿着真实帕累托前沿面搜索以提高分布性能，或者兼而有之，从而使得混合差分进化算法进一步提高了解决多目标工艺规划和调度的能力。混合差分进化算法在问题表达、融合框架、方向搜索策略上进行了设计并通过标准测试问题集、工艺规划和调度问题集进行了验证，对比多个经典进化多目标优化算法取得了明显的收敛性能和分布性能提升。项目所取得的成果有助于推进多目标进化算法解决多资源多约束多目标生产调度问题，从而推动复杂智能加工制造系统的进一步发展。