随机型流量网络中若干问题的模型及其算法的研究

论文摘要

网络流理论是图论的一个重要分支,是研究网络上相关优化问题的理论和方法。1956年,L.R.福特和D.R.富尔克森等人给出了解决在给定的网络上寻求两点间最大运输量这类问题的算法,从而奠定了网络流理论的基础。网络流理论发展至今,已普遍应用于通讯、运输、电力、工程规划、任务分派等众多领域。为了更好的解决现实中的问题,网络流理论也在不断发展中,先后出现了具有增益的流、分派与匹配、网络优化的拉格朗日松弛法、多商品流、网络流的分解与合并等新的理论和方法。但以上研究都是在网络参数和拓扑结构固定的网络上进行的优化,而实际环境中的网络系统受多种因素影响往往会表现出随机性,所以传统网络流理论在具体应用时与实际情况会有一定的偏差,如果能在随机环境下对网络流进行优化,对提高网络流理论的实用性和针对性均有重要意义,这个问题已越来越引起关注。目前主要从3个方面将随机因素引入网络流理论:1.令网络的权值为随机变量;2.假设网络的拓扑结构为随机的;3.假设网络中各边的容量为随机变量,提出了随机型流量网络（Stochastic Flow Network）的概念。随机型流量网络上的网络流理论的研究目前处于起步阶段,研究主要集中在:设计算法寻找网络流在网络容量状态X下的最大流V（X）能满足接收端需求d的网络容量状态的临界点d-MCs或d-MPs,并根据这些点计算随机型流量网络的可靠性。但当随机型流量网络的容量处于非临界状态时,对网络流进行分配优化的研究还较少见,论文中将针对不同问题选取特定优化目标,研究网络流不处于最大流状态V（X）时的优化问题。论文主要研究了以下几方面的内容:1.以目前使用较多的两种随机型流量网络模型（网络节点可靠,单商品流,多发送端,多接收端的网络模型和网络节点不可靠,多商品流,多发送端,多接收端的网络模型）为基础,研究当网络流不处于最大流状态V（X）时如何对网络流流量进行分配优化。选定满足接收端需求的网络流可靠性为目标,建立整数随机规划模型。针对模型的特点,设计相应的算子,采用遗传算法对优化模型进行求解,并与使用Lingo软件方法求解得到的结果进行比较,分析两种求解方法的优缺点及其适用的问题。2.文中将网络流传输时间和成本从约束条件转化为整体优化目标,并结合网络流可靠性这一主要目标,研究随机型流量网络上网络流的多目标优化问题。为求解建立的多目标优化模型,对NSGA-II方法做出如下改进:改进2-联赛选择算子的比较规则,将模拟2进制交叉算子改进为单点复合交叉算子,改进精英保留策略,使用改进后的算法对模型进行求解,经过测试,得到的结果从多方面优于原NSGA-II算法。3.已有的随机型流量网络可靠性的算法,由于涉及到最大流最小割原理和Ford-Fulkerson算法等传统网络流理论,故不得不假设随机型流量网络中的所有变量为离散型变量。本文中由于采用了单目标/多目标遗传算法对网络流进行优化,故不受上面的限制。因此文中扩展随机型流量网络的容量为连续型随机变量,各条边上分配的网络流量为连续实数,建立连续型的多目标网络流优化模型,为了处理包含连续型变量的等式约束,对等式约束增加逼近参数,将等式约束分解为两条不等式约束以逼近方式处理。采用改进后的NSGA-II对处理后的优化模型进行求解。通过测试,可快速求出连续型多目标优化模型的Pareto前沿。4.论文对网络中各节点包含随机需求的网络流多目标优化问题进行了研究。针对这种复杂随机情况下的网络流优化问题建立了机会约束多目标随机规划模型。对建立的随机规划模型进行预处理,将部分以置信度表示的约束条件转化为对应的确定性等价约束。采用随机模拟方法对优化模型的其余部分进行处理。结合前面提到的改进后的多目标遗传算法,提出一个基于随机模拟的多目标遗传算法对机会约束随机规划模型进行求解。通过算例测试,可以求得优化问题的Pareto解集。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 研究背景
• 1.2 随机型流量网络的定义及其与其它概念的比较
• 1.2.1 随机网络（Stochastic Network）
• 1.2.2 随机图（Random Graph）
• 1.2.3 复杂网络（Complex Networks）
• 1.3 研究现状综述
• 1.3.1 随机型流量网络研究文献综述
• 1.3.2 多目标优化方法研究现状综述
• 1.4 本文主要研究内容
• 1.5 本文主要创新点
• 第2章 随机型流量网络中网络流单目标优化研究
• 2.1 节点可靠的随机型流量网络中网络流优化研究
• 2.1.1 研究背景
• 2.1.2 模型符号描述
• 2.1.3 建立优化模型
• 2.1.4 计算复杂度分析
• 2.1.5 优化模型的求解
• 2.1.6 算法性能测试
• 2.1.7 小结
• 2.2 带不可靠节点的随机型流量网络中网络流优化研究
• 2.2.1 相关符号描述
• 2.2.2 优化模型的建立
• 2.2.3 计算复杂度分析
• 2.2.4 模型的求解
• 2.2.5 实例验证
• 2.2.6 小结
• 2.3 随机型流量网络中网络流单目标优化方法比较
• 2.3.1 Lingo 的计算结果
• 2.3.2 本文提出的遗传算法的计算结果
• 2.3.3 结论
• 第3章 随机型流量网络中流量分配的多目标优化研究
• 3.1 节点可靠的随机型流量网络中流量分配多目标优化研究
• 3.1.1 网络模型定义
• 3.1.2 优化模型的建立
• 3.1.3 计算复杂性分析
• 3.1.4 提出的多目标遗传算法
• 3.1.5 实验及数据分析
• 3.1.6 小结
• 3.2 带不可靠节点的随机型流量网络中流量分配多目标优化研究
• 3.2.1 网络模型定义
• 3.2.2 本节优化问题建模
• 3.2.3 计算复杂性分析
• 3.2.4 模型的求解
• 3.2.5 实例验证
• 3.2.6 小结
• 3.3 随机型流量网络上网络流分配多目标优化方法比较
• 3.3.1 改进后算法的计算结果
• 3.3.2 NSGA-II 算法的计算结果
• 3.3.3 两种算法计算结果比较
• 3.3.4 结论
• 第4章 连续随机型流量网络中网络流多目标优化研究
• 4.1 符号介绍和假定
• 4.2 建立模型
• 4.3 模型的求解
• 4.4 实例及结果分析
• 4.5 小结
• 第5章 基于机会约束模型的随机型流量网络中网络流分配优化研究
• 5.1 问题的提出
• 5.2 符号介绍和假定
• 5.3 建立模型
• 5.4 模型的求解
• 5.5 实例及结果分析
• 5.6 小结
• 第6章 随机型流量网络中流量分配三目标优化问题研究
• 6.1 问题的提出
• 6.2 模型的描述
• 6.3 目标函数值的计算
• 6.4 建立模型
• 6.5 模型的求解及实例计算
• 6.6 小结
• 第7章 总结与展望
• 参考文献
• 攻读博士学位期间发表论文情况
• 致谢