基于改进精英策略的PCA-NSGAⅡ的高维目标调度优化研究

研究背景与作者信息

本文以题为《基于改进精英策略的PCA-NSGAⅡ的高维目标调度优化》（Many-objectives Scheduling Optimization based on PCA-NSGAII with Improved Elite Strategy），发表于《计算机集成制造系统》第26卷第9期（2020年9月），DOI号为10.13196/j.cims.2020.09.017。第一作者为刘琼，合作者包括熊书平与湛梦梦，作者单位为“华中科技大学数字制造装备与技术国家重点实验室”。研究得到了国家自然科学基金项目的资助（项目编号：51675206, 51875429）。

研究背景与意义

随着制造系统复杂度的增加，高维目标调度优化（Many-objectives Scheduling Optimization）问题在智能优化领域中受到广泛关注。尤其当优化目标的维度达到4或以上时，该问题被视为“高维目标优化问题”，其求解面临计算复杂度高、解最大化效率低等挑战。

在“中国制造2025”战略的驱动下，制造企业间资源协同与共享成为趋势，需要解决调度问题以优化资源分配和利用。具体来说，制造过程中需要在兼顾成本、工期、碳排放等多个目标的情况下，实现多项指标的最优平衡。但传统基于“权重函数”的方法在求解高维问题时往往会丧失搜索效率和解的质量。此外，考虑实际企业生产需求的背景下，难点不止于多目标规划，还在于目标间高度非线性与超大规模搜索空间。

为了解决上述问题，本文引入基于主成分分析（Principal Component Analysis, PCA）的非支配排序遗传算法（NSGA-II, Non-dominated Sorting Genetic Algorithm），设计出改进精英策略的PCA-NSGAⅡ算法模型，为高维目标调度问题提供了一种创新性和工程实用性并行的解决方案。

研究方法与技术实现

本研究的核心贡献在于设计一种改进精英策略的PCA-NSGAⅡ算法，通过以下过程实现：

1. 问题建模

本文构建了考虑四个高维目标的制造调度优化模型，包括： - 最小化生产总成本（ccost）：总成本由加工成本和运输成本组成。 - 最小化最大完工时间（ctime）：表示从首个工件开始加工至最后一个工件完成间的时间跨度。 - 最小化拖期/提前惩罚成本（ett）：衡量工件实际完成时间与既定交货期间的偏差。 - 最小化碳排放（cp）：覆盖加工机器能耗、空转功率以及搬运工件时的油耗等。

数学模型还纳入了约束条件（如任务不能中断、工件任务只能分配至单台机器上等），从而确保实际问题的合理性。参数如设备功能、运输距离、用能指标的具体数据通过实验设计给出。

2. PCA占优机制引入

为了破解高维优化问题中因目标数增加导致的权重选择压力弱化现象，本文创新性地采用PCA对非支配解种群个体进行目标权重计算。该方法基于PCA矩阵分析，能有效保留全体目标特征，同时通过权重向量对个体目标值差值的比较实现精确判定。

3. 改进精英策略

传统PCA-NSGAⅡ存在解个体多样性丧失与收敛性不足的缺陷。为了优化此算法： - 设计了独立的外部种群，用于保存每一代迭代产生的最优个体。 - 更新后的精英策略允许种群通过非支配排序和拥挤度算子进行筛选，将外部种群与原始主种群联合优化，增强寻优性能。

种群编码方面引入二段式交叉策略（分别用于任务顺序编码与机器资源分配），以更好反映调度优化的复杂性。

4. 算法验证

本文选取一个由三家制造工厂和多台加工机器组成的协同制造系统进行了案例分析验证，以Python语言编程实现算法并通过设定种群大小、交叉率、变异率等超参数，产生多组Pareto优化解集。

实验结果与分析

通过实验验证，研究结果表明：

• 本文提出的PCA-NSGAⅡ相比其他创新不足的标准算法，如传统NSGAⅡ和原始PCA-NSGAⅡ，在收敛性能、解的均匀性、解的多样性上均有显著优势。
• 在优化目标方面，各指标值均超越基准对比算法的性能。例如，最小碳排放解的总值为45.7237 kg CO2，显著低于传统基线模型。

算法对比分析

实验将本文算法结果与三种现有算法分别进行了对比： 1. 经典NSGA-II算法 2. 基于ε支配的NSGA-II 3. 未改进的PCA-NSGA-II

结果显示，改进版本的PCA-NSGAⅡ在解的搜索范围、解集丰富性与目标收敛效果上均优于对比项。

研究结论与意义

本文构建了一种改进精英策略的PCA-NSGAⅡ算法。其主要贡献在于： 1. 提出基于PCA占优机制的多目标分类算法框架，为高维调度优化问题提供了一种系统的“降维”方法； 2. 改善传统精英策略，外部种群的加入提升了全局优化寻优能力； 3. 在工业环境的实际案例中展示了理论模型的工程适用性，借助多目标权衡决策支持，为协同制造场景下的调度优化问题提供了解决思路。

工程及科学价值：

• 本研究为《中国制造2025》背景下推动制造资源优化配置，提升企业资源利用率提供了技术手段；
• PCA算法结合外部种群策略作为原创性的技术应用，拓展了现有算法在复杂优化问题中的应用范围。

新颖处总结：

• 理论突破：创新引入基于主成分的多目标权衡权重方法；
• 技术创新：采用外部种群提高遗传算法的全局搜索能力并强化结果收敛。

未来展望

尽管取得了显著成果，但在未来研究中仍需探索以下潜在优化方向： 1. 进一步提升降维策略对解决超大规模实际问题的适配性。 2. 针对不同企业生产目标的异构调度需求，扩展算法的灵活性。

总而言之，该研究在理论和实践上均具有重要意义，为工业智能调度优化领域提供了坚实的科学支撑以及创新学习方向。