论文部分内容阅读
作为一类经典的组合优化问题,最大流问题有着40多年的研究历史和广泛的应用领域,成为研究各种实际网络系统的重要手段,也存在着丰富的研究成果。随着研究和应用的深入,人们发现不确定性是实际系统的固有特性,如:输变电网络中元件和数据通讯网络中节点可能非正常运行。这些不确定性表现于网络系统中,则形成不确定图。不确定图上的最大流问题是传统最大流问题在不确定图上的自然延伸,其中求取最可靠最大流分布具有较高的理论和应用研究价值,可用来有效解决诸如构建可靠性网络、可靠传输路径选择以及系统薄弱环节分析等一系列实际问题。 本文首先对不确定图上最大流和最可靠最大流问题进行了定义,然后借鉴最小费用最大流问题中的“消环思想”,提出一种基于负权群落的迭代消去算法NCBI(NegativeCommunity Based Iterative Algorithm)。该算法定义了一种在剩余图上计算边权重的规则,并提出了负权群落的概念,进而通过在一个原始最大流分布所对应的剩余图上,迭代地消去负权群落,不断对最大流的可靠性进行优化,直至达到最可靠最大流。为了提高算法性能,本文提出一种改进策略,在迭代过程中,优先查找、消去单个“负权环”,当不存在负权环时再寻找、消去负权群落。 针对迭代算法时间复杂度较高的问题,本文提出了最大负权群落的概念,并在此基础上提出一种最大负权群落消去算法MNCE(Maximum Negative Community EliminationAlgorithm),MNCE算法通过在剩余图上消去最大负权群落,直接获得最可靠最大流,而无需进行多次迭代,显著地提高了算法的效率。同时由于存在着负权群落仅出现在强连通分量上这一重要性质,算法可利用强连通分解思想将剩余图分割为若干个具有算法独立性的强连通子图,一方面减小最大负权群落的搜索空间,另一方面可借助并行计算获得良好的算法伸缩性。为进一步减小最大负权群落的搜索空间,本文提出一种基于关键边的容量化简算法CEBCS(Critical Edges Based Capacity Simplify Algorithm)。关键边是指剩余图中可对可靠性产生影响的边。CEBCS算法通过关键边流量取值的不同组合,对负权群落枚举空间进行划分,再利用流量守恒条件对剩余图的边容量划分进行化简,大幅缩小了最大负权群落的搜索空间,从而进一步提高了算法效率。 在实验中,本文对影响算法效率的可能因素进行了分析,并着重对最大负权群落消去算法和基于关键边的容量化简算法的性能进行了对比。实验表明:最大负权群落消去算法可在规模较小的不确定图上有效求取最可靠最大流,对于较大的不确定图,基于关键边的容量化简算法具有明显的性能优势。