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

《随机型流量网络中若干问题模型及其算法的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、山东师范大学博士学位论文摘要网络流理论是图论的一个重要分支，是研究网络上相关优化问题的理论和方法。1956年，L．R．福特和D．R．富尔克森等人给出了解决在给定的网络上寻求两点间最大运输量这类问题的算法，从而奠定了网络流理论的基础。网络流理论发展至今，已普遍应用于通讯、运输、电力、工程规划、任务分派等众多领域。为了更好的解决现实中的问题，网络流理论也在不断发展中，先后出现了具有增益的流、分派与匹配、网络优化的拉格朗日松弛法、多商品流、网络流的分解与合并等新的理论和方法。但以上研究都是在网络参数和拓扑

2、结构固定的网络上进行的优化，而实际环境中的网络系统受多种因素影响往往会表现出随机性，所以传统网络流理论在具体应用时与实际情况会有一定的偏差，如果能在随机环境下对网络流进行优化，对提高网络流理论的实用性和针对性均有重要意义，这个问题已越来越引起关注。目前主要从3个方面将随机因素引入网络流理论：1．令网络的权值为随机变量；2．假设网络的拓扑结构为随机的；3．假设网络中各边的容量为随机变量，提出了随机型流量网络(stochasticFIowNetwork)的概念。随机型流量网络上的网络流理论的研究目前处于

3、起步阶段，研究主要集中在：设计算法寻找网络流在网络容量状态X下的最大流V(x)能满足接收端需求d的网络容量状态的临界点d—Mcs或d—MPs，并根据这些点计算随机型流量网络的可靠性。但当随机型流量网络的容量处于非临界状态时，对网络流进行分配优化的研究还较少见，论文中将针对不同问题选取特定优化目标，研究网络流不处于最大流状态V(X)时的优化问题。论文主要研究了以下几方面的内容：1．以目前使用较多的两种随机型流量网络模型(网络节点可靠，单商品流，多发送端，多接收端的网络模型和网络节点不可靠，多商品流，多

4、发送端，多接收端的网络模型)为基础，研究当网络流不处于最大流状态V(X)时如何对网络流流量进行分配优化。选定满足接收端需求的网络流可靠性为目标，建立整数随机规划模型。针对模型的特点，设计相应的山东师范大学博士学位论文算子，采用遗传算法对优化模型进行求解，并与使用Lin90软件方法求解得到的结果进行比较，分析两种求解方法的优缺点及其适用的问题。2．文中将网络流传输时间和成本从约束条件转化为整体优化目标，并结合网络流可靠性这一主要目标，研究随机型流量网络上网络流的多目标优化问题。为求解建立的多目标优化模

5、型，对NSG心Ⅱ方法做出如下改进：改进2．联赛选择算子的比较规则，将模拟2进制交叉算子改进为单点复合交叉算子，改进精英保留策略，使用改进后的算法对模型进行求解，经过测试，得到的结果从多方面优于原NSGA-Ⅱ算法。3．已有的随机型流量网络可靠性的算法，由于涉及到最大流最小割原理和Ford．FuU【erson算法等传统网络流理论，故不得不假设随机型流量网络中的所有变量为离散型变量。本文中由于采用了单目标／多目标遗传算法对网络流进行优化，故不受上面的限制。因此文中扩展随机型流量网络的容量为连续型随机变量，

6、各条边上分配的网络流量为连续实数，建立连续型的多目标网络流优化模型，为了处理包含连续型变量的等式约束，对等式约束增加逼近参数，将等式约束分解为两条不等式约束以逼近方式处理。采用改进后的NSGA．II对处理后的优化模型进行求解。通过测试，可快速求出连续型多目标优化模型的Pareto前沿。4．论文对网络中各节点包含随机需求的网络流多目标优化问题进行了研究。针对这种复杂随机情况下的网络流优化问题建立了机会约束多目标随机规划模型。对建立的随机规划模型进行预处理，将部分以置信度表示的约束条件转化为对应的确定性

7、等价约束。采用随机模拟方法对优化模型的其余部分进行处理。结合前面提到的改进后的多目标遗传算法，提出一个基于随机模拟的多目标遗传算法对机会约束随机规划模型进行求解。通过算例测试，可以求得优化问题的Paret0解集。关键字：随机型流量网络；多目标优化：最小路；网络流优化；山东师范大学博士学位论文AbstractNe俯orknowmeo巧is锄irnport锄tb瑚chof渤phTheoⅨanditisttlctheowofstudying叩ti血zationprobleIIlsuponne斜ork．hI

8、1956，L．R．Ford觚dD．R．Fuu【e娼onprcIpoulldtllealgorithmt0∞lvetheprcIblemofseel【ingmaximal缸．觚sportationquanti哆bet、ⅣeeIlt、Ⅳonodes0n廿lene帆ork．FtomthelloIl'neMorknowme0巧w雒f10衄deda11ddeveloped．N曲lⅣorkflowtlleorynowtlasbe％widely印pliedtocommlulicat