动态多目标TSP演化算法研究

阅读量：

213

作者：

杨鸣

展开

摘要：

在科学管理与经济决策的许多应用领域中,现实世界存在着大量的动态多目标优化问题。对于旅行商问题(Traveling Salesman Problem,TSP),实际中经常要同时考虑多个目标,如路程最短、时间最短、费用最省、风险最小等多方面的因素。目标之间往往存在冲突性。如何在多个目标中寻找一个公平、合理的解是比较复杂的问题。此外在实际生活中,大量的多目标优化问题具有实时性,问题的状态随着时间变化。这些优化问题除了具有多个目标的性质外,同时还具有动态性。 动态多目标TSP是从移动计算、移动通信等应用领域中提出的一类新的Np-难的数学理论模型,它属于演化计算的一个最新的研究领域。动态多目标TSP是动态TSP和多目标TSP的结合,是作为航天通信(地基、空基与天基相互之间进行通信)的数学理论模型于2004年首次提出来的。与经典的TSP、静态多目标TSP、动态单目标TSP相比,动态多目标TSP更复杂,具有更大的挑战性。它要求实时跟踪动态变化的最优Pareto前沿。动态多目标TSP的研究将推动一些实际问题,如:移动计算、移动通讯、航天通信等网络拓扑设计与路由算法的研究和发展。所以研究动态多目标TSP具有重大的理论意义和应用价值。 本文前两章介绍了TSP的基本知识、研究现状和遗传算法的基础理论知识。第三章到第五章,介绍了作者对动态多目标TSP取得的研究成果。 动态多目标TSP中有一些重大理论问题没有解决,例如:动态程度的度量问题,目标之间的冲突程度的度量问题,动态多目标优化算法的性能的评估问题以及Pareto最优解的数目与目标冲突程度的关系问题等。 在第三章中,对动态多目标TSP的动态程度和目标冲突程度的度量问题进行了研究。首次提出了动态程度和目标冲突程度的概念。问题的动态变化是通过代价矩阵的变化体现的,度量动态变化程度就是比较代价矩阵发生了多大的变化;而度量目标冲突程度则是比较各个目标的代价矩阵之间的冲突程度有多大。所以,度量问题的动态程度和目标之间的冲突程度就是度量某些代价矩阵的相异程度。根据上述思路,首次给出了问题的动态程度和目标冲突程度的度量方法。根据这些方法,可计算出动态多目标TSP问题的状态发生了多大的变化和目标之间的冲突程度。它们对动态多目标TSP的算法设计具有重要的指导意义。并且提出了动态多目标TSP优化算法的评估准则Paretos-Similarity。它可以从Pareto解集中解的数目、Pareto解集中每一个目标的最佳逼近度、Pareto解集的平均逼近度、Pareto解集分布的均匀性与多样性四个因素综合地评估某一Pareto解集与最优Pareto解集的逼近程度。根据Paretos-Similarity可对算法得出的解的质量和算法的性能进行有效地评价。 在第四章中,提出了DMOInver-Over算法求解动态多目标TSP,它是Inver-Over的动态多目标版本,其通过Inver-Over算子和动态弹性松弛算子相结合来求解动态多目标TSP。实验中以两个目标的三维标准测试问题CHNl44+5为例,对本文提出的DMOInver-Over的有效性进行了验证。从实验中可以看出,DMOInver-Over通过Inver-Over算子和动态弹性松弛算子相结合,配合下一代种群的生成规则生成新种群,可以在比较短的时间内得到一个近似最优Pareto解集。 对于动态多目标TSP,问题的状态和特征是随着时间变化的。根据优化问题的定理NFLTs,采用单个算法设计的方法已经不能有效地求解这类极其复杂、多变的优化问题。在第五章中,提出了一种新的求解动态多目标TSP的算法设计方法:多算法的协同演化策略(multi-algorithm coevolution strategy,MACS)。MACS采用在一次迭代过程中,运行多个算法生成新种群,通过多算法协同演化,可以充分发挥全局优化算法和局部优化算法的性能,达到多个算法的优势互补,避免单一算法的局限性;可以在加快算法收敛速度的同时,保持Pareto解集的多样性,保证Pareto前沿的均匀分布。实验中以两个目标的三维标准测试问题CHN144+5为例,对本文提出的MACS的有效性进行了验证。实验结果表明,MACS比单个算法的优化方法收敛速度更快,求得的Pareto解集的多样性更好,解的分布更加均匀,可以有效地求解动态多目标TSP。

展开

关键词：

旅行商问题 动态多目标优化 演化算法 多算法 TSP dynamic multi-objective optimization evolutionary algorithm multi-algorithm solver

DOI：

CNKI:CDMD:2.2008.095762

被引量：

9