一种基于混合惩罚策略的两阶段进化算法及其在多无人机路径规划中的应用

《Expert Systems with Applications》：A two-stage evolutionary algorithm based on hybrid penalty strategy and its application to multi-UAV path planning

提出两阶段混合惩罚策略的TSC-PSODE算法，通过早期外部惩罚维持种群多样性增强全局探索，后期内部惩罚加速收敛至高质量可行解，结合差分进化算子提升鲁棒性，实验验证其在约束优化及多无人机路径规划中的有效性优于现有算法。

　　在现代科学和技术发展的背景下，优化问题已经成为众多领域中不可或缺的一部分。这些问题广泛存在于路径规划、生物医学工程、金融投资、水电站运行系统以及智能交通等多个应用中。其中，受限优化问题（Constrained Optimization Problems, COPs）因其复杂性和动态性，对传统优化算法提出了更高的要求。受限优化问题的特点在于，它们的可行域往往具有狭窄、非凸和不连续的特性，这使得在求解过程中需要同时兼顾可行解的维持与全局探索的平衡。随着问题复杂性的增加，仅依靠单一的优化目标往往无法满足实际需求，因此，研究者们不断探索更有效的约束处理策略，以提高算法的性能和适应性。

针对这类复杂问题，进化算法（Evolutionary Algorithms, EAs）因其灵活性和全局搜索能力，成为解决受限优化问题的重要工具之一。然而，进化算法本质上是用于无约束优化的方法，因此必须结合特定的约束处理技术才能有效解决受限优化问题。常见的约束处理方法包括惩罚函数法、可行性规则、随机排名法、ε-约束法以及多目标优化法等。这些方法各有优劣，但在实际应用中，如何在保持种群多样性的同时提高收敛效率，仍然是一个值得深入研究的挑战。

为了应对这一问题，本文提出了一种名为TSC-PSODE的双阶段进化算法，其核心思想是通过结合外部惩罚和内部惩罚策略，实现对约束优化问题的高效求解。外部惩罚主要用于早期阶段，以保持种群的多样性并增强全局探索能力；而内部惩罚则在后期阶段被引入，以加快收敛速度并提高解的质量。此外，该算法还引入了差分进化算子的协同策略，以提升算法的鲁棒性，并帮助种群逃离局部最优解，从而在复杂环境中找到更加有效的可行解。

在算法设计中，TSC-PSODE的关键创新点在于其对惩罚函数的动态调整机制。传统惩罚函数法通常采用固定的惩罚系数，这可能导致在搜索过程中无法灵活适应不同的约束条件。相比之下，TSC-PSODE采用了一种混合惩罚策略，使得惩罚系数能够根据搜索阶段的变化进行动态调整。这种策略不仅提高了算法对不同约束条件的适应能力，还有效平衡了多样性保持与收敛效率之间的关系。具体来说，在早期阶段，外部惩罚通过引入较大的权重来引导算法探索整个搜索空间，避免过早陷入局部最优解；而在后期阶段，内部惩罚则通过调整惩罚系数，使得算法能够更加聚焦于可行解区域，从而快速逼近最优解。

除了惩罚函数的动态调整，TSC-PSODE还采用了差分进化（Differential Evolution, DE）的协同策略，以增强算法的全局探索能力。差分进化是一种高效的群体智能优化算法，其通过种群个体之间的差异向量进行变异和交叉操作，从而在搜索空间中产生多样化的候选解。在TSC-PSODE中，这种协同策略被设计为一种混合机制，能够结合差分进化算子的优势，进一步提升算法的鲁棒性和收敛速度。通过引入这种协同策略，TSC-PSODE能够在复杂的搜索空间中更好地维持种群的多样性，同时避免在搜索后期因多样性丧失而导致的收敛失败。

为了验证TSC-PSODE的有效性，本文在多个实验场景中对其进行了测试。首先，算法在CEC2017基准测试集上进行了评估。CEC2017是用于测试受限优化算法性能的常用基准，它包含了多种具有不同约束条件和复杂性的测试函数。通过对比实验，TSC-PSODE在多个测试函数上表现出优于当前最先进的算法的性能，这表明其在处理受限优化问题时具有良好的适应性和鲁棒性。其次，算法还被应用于多无人机路径规划（Multi-UAV Path Planning）任务，这一应用展示了TSC-PSODE在实际工程问题中的潜力。在多无人机路径规划中，算法不仅需要满足路径的可行性（如避开障碍物、满足飞行高度限制等），还需要在多个无人机之间进行协同规划，以提高整体任务执行效率。实验结果表明，TSC-PSODE能够在复杂环境中生成安全且可行的飞行路径，从而在实际应用中展现出较高的适应性和竞争力。

TSC-PSODE的成功不仅体现在其算法设计的创新性上，还在于其对实际问题的适应能力。在多无人机路径规划任务中，算法需要处理多个约束条件，例如无人机之间的路径冲突、飞行环境中的障碍物分布以及任务执行的时间限制等。这些问题的复杂性使得传统的优化算法难以在合理的时间内找到高质量的可行解。而TSC-PSODE通过其双阶段机制和协同策略，能够在早期阶段充分探索可能的路径选项，而在后期阶段快速收敛到最优解。这种分阶段的策略使得算法能够在复杂环境中保持较高的搜索效率，同时避免因过早收敛而导致的解质量下降。

此外，TSC-PSODE的实验结果也表明，其在处理动态约束优化问题时具有显著的优势。在实际应用中，许多优化问题的约束条件可能会随着时间的变化而发生变化，例如环境中的障碍物可能被移动，或者任务需求可能发生变化。这种动态性对算法提出了更高的要求，因为传统的静态惩罚函数方法往往无法适应这种变化。相比之下，TSC-PSODE的混合惩罚策略能够根据搜索阶段和约束条件的变化动态调整惩罚系数，从而在不同阶段维持适当的搜索方向和多样性。这种灵活性使得算法在处理动态约束问题时表现出更强的适应能力。

在算法的实现过程中，还考虑了参数设置对性能的影响。为了确保算法的稳定性与有效性，本文对种群规模、子种群数量以及最大函数评估次数等关键参数进行了系统性的分析和调整。通过合理的参数设置，TSC-PSODE能够在保持种群多样性的同时，提高收敛速度和解的质量。此外，本文还对算法的实验环境进行了说明，所有实验均在MATLAB R2022a平台上进行，以确保实验的可重复性和结果的可靠性。

总的来说，TSC-PSODE作为一种基于混合惩罚策略的双阶段进化算法，不仅在理论设计上具有创新性，还在实际应用中表现出良好的性能。通过结合外部惩罚和内部惩罚策略，以及差分进化算子的协同机制，该算法能够在复杂的受限优化问题中保持种群多样性，同时提高收敛效率，从而找到高质量的可行解。在CEC2017基准测试集和多无人机路径规划任务中的实验结果进一步验证了其在实际应用中的潜力。未来的研究可以进一步探索该算法在更多复杂约束条件下的适用性，以及如何将其扩展到多目标优化和动态优化问题中，以提升其在不同应用场景下的适应能力。