论文部分内容阅读
最短路径问题是传统的组合优化问题之一,并且在实际应用中较为常见,例如车辆导航问题和网络路由问题。最短路径问题的有很多种类,例如静态的最短路径问题、动态最短路径问题、单目标最短路径问题和多目标最短路径问题等。本文研究了动态最短路径问题、多目标最短路径问题和动态环境下的多目标最短路径问题,并将传统优化方法和演化求解算法结合,提出了两者结合的演化求解算法。本文主要工作如下所示。(1)对于静态网络中的最短路径问题,有很多确定性的求解算法。在静态的网络拓扑中,这些确定性的算法表现良好。但是当环境动态变化时,这些算法需要重新执行,而环境通常是局部变化的,因此这些确定性的算法不是很高效。本文提出了一个带有四个局部路径替换策略的解决动态最短路径问题的遗传算法。这些局部路径替换策略是由Dijkstra的最短路径算法所启发,并且在环境发生改变的时候进行调用来产生一些局部最短路径树。并且在种群进化时,这些保存的局部最短路径树用来增强个体的性能。实验表明,所提出的算法可以快速得到适应新环境的解,并产生高质量的个体。(2)实际生活中,有些问题是多目标的,并且不同的目标之间具有一定的冲突性。对于多目标的最短路径问题,每条边带有多个目标,该问题旨在求解从源点到终点的非支配路径集。在本文中,采用了将传统方法和演化算法结合的思想,算法的主体采用NSGA-Ⅱ,结合第k短路径算法,提出了KSPNSGA。该方法使用加权求和法将每条边上不同的目标值加权求和得到一个新的目标值,并且求解该目标值构成的新图中的第k短路径。在NSGA-Ⅱ的种群进化时,将上述求得的路径替换种群中的最差路径,用来加速对非支配解集的搜索。(3)问题所处的环境有时是动态变化的。同样,多目标最短路径问题所处环境也会变化。针对动态环境中的多目标最短路径问题,本文将提出的解决多目标最短路径问题的KSPNSGA进行了一些修改,提出了适应动态环境的DKSPNSGA,即每代进化时使用迁移个体替换一部分个体,以此来适应动态变化的环境。