关于不确定条件下的最短路径问题的研究

关于不确定条件下的最短路径问题的研究摘要：在利用最短路模型解决问题时，由于天气、运输条件以及时间段等原因，网络中弧的权值经常很难给出确切的值。对传统的最短路径优化模型提出了挑战，也为最短路径优化模型的进一步发展提供了新的机遇。本文主要就不确定条件下最短路径问题进行研究，介绍了一种不确定条件下最短路径问题随机优化模型――有约束的期望最短路径模型，利用结合随机模拟方法和遗传算法的混合智能算法进行求解。通过系统的学习不确定条件下的最短路径问题的解决方法，开拓了思路，对自己运用系统思维解决自己研究方向的问题有很大的启发。关键字：网络优化；不确定最短路径问题；系统思维一、引言最短路径问题是指在网络中寻找节点间具有最小长度(或最小费用)的路径，具有重要的理论和实际应用意义。一方面，它可以直接应用于许多实际问题，如各种管道的铺设，线路安排等;另一方面，它也常被利用为解决其他一些优化问题的工具，是网络优化中的一个基本而又重要的问题。因此运筹界、工业界的学者对最短路径及其变形问题就算法和应用等方面进行了广泛的研究。然而在很多具体的应用中，我们遇到的信息，存在着客观的或者人为的不确定性，这种不确定性的表现形式是多种多样的，例如随机性、模糊性等。在利用最短路径模型解决问题时，由于天气、运输条件以及时间段等原因，网络中弧的权值经常很难给出确切的估计，这样只能根据历史数据获得其概率分布情况，即这些数据是随机的。但是随机性只是不确定性的一个方面，对于一些情况，譬如缺少历史数据、或者历史数据不可靠时，这些数据只能由专家根据自己的经验给出主观的估计，譬如通过该条路径的时间大概是3小时，流经该线路需时40分钟左右，这样表征弧上权值的量也因此而模糊起来，此时利用最短路径模型解决实际问题必须考虑这种不确定性。虽然对于不确定条件下的最短路径问题，学者们可通过研究动态随机网络中路径的分布函数以及期望值来研究网络问题，给出了分布函数为某一类型的求解方法，并没有考虑不同的决策要求，或者是分布函数为一般情况时的求解方法。至于模糊最短路径问题，最早由Dubois和Prade[1，2]在1980年首次提出，他们根据模糊集理论中的最大、最小值算子和Zadeh扩展原理，来求模糊最短路的长度，但由于模糊运算的特点，经过多次运算得到的模糊长度有时候并不能和某条路径对应上。有的学者根据多准则决策理论求非被支配解路径集合，但当网络较大时，该集合就会很大，对于决策者从中选择满意的方案就会很困难。因此，在不确定条件下建立模型给出算法，为决策者提供有价值的方案，具有重要的意义。二、问题描述为了对最短路问题进行建模，本文考虑无圈有向网络图，将网络的拓扑结构用图论术语可以描述如下:在有向图G=(V,A,W)中,V={l,2,...,n}代表节点集(设节点总数共计n个),A代表弧集,每个弧使用节点的有序对,ij来表示，其中,ijA，并假设从节点i到节点j之间只有一条有向弧。{|,}ijiWAjW代表弧的权集。这里我们考虑和每条弧关联着两个权值（也可以关联着多个)，对图G中的每一条边e,ij，相应的权向量12(W,W)ijijijW。在实际问题中分量有相应的物理量对应，如Qos路由问题中每条链路可以给出带宽、时延、代价，丢包率等，交通问题中每条弧对应着运行的时间和费用等。在实际应用中，由于各种原因，权向量ijW的每个分量并不是确定的，可能部分不确定或都不确定。我们令权向量(,c)ijijijW,分量ij为随机变量,cij勺为确定的量。实际上这样的网络是存在的，如交通网络中两地的运输费用是确定的但运行时间可能不确定;网络路由中的丢包率是随机的但是其他的量可能是确定的。在有些情况下，随机变量ij可能服从某种分布函数，可以为正态分布、均匀分布等等。如当服从正态分布时，可以记为2~(,)ijijijN;在另外一些情况下，随机变量ij可能无法获得它的准确分布函数，只能根据先前经验获得或估计其概率。由于在无圈网络G＝（V，A）中，对于所有的,ijA，所有的节点能够重新编号使得ij,这样我令1和n分别表示路径的起点和终点，则从节点1到n的一条路P的权向量定义为P中所有边的权向量之和，记为(i,j)P(i,j)P(i,j)PW(P)(,c)ijijijW有约束的最短路问题就是对于给定的约束C，要在所有从1到n的所有路径中，求一条路径使得(i,j)Pij最小且(i,j)PcijC，设决策变量为ijx，用下面的方法来表示一条路径{|,}ijixEjx其中1ijx表示弧,ij包含在该路径中，0ijx表示弧,ij不包含在该路径中，容易证明在有向无圈图中{|,}ijixAjx是一条从节点1到节点n的路，当且仅当(i,j)(,)110211ijjiEjiEixxinin记{|,}ijiAj，那么路x长度（目标函数）就可以写成为(i,j)(,)ijijEfxx优化的目标是使(,)fx最小。如果ij为确定的数，则求(,)fx的最小值是有定义的，但ij是随机变量时，导致目标函数(,)fx也为随机变量，这样求(,)fx的最小值也就失去了意义。因此，我们有必要根据随机理论知识，对随机条件下的最短路径进行定义，建立相关的数学模型。三、有约束的期望最短路径模型的建立定义1：设,xx为图G中从源节点1到目标节点n的不同路径，若有((,))((,))EfxEfx,则称期望条件下路x比路x短，其中((,))Efx称为x的期望路长。在实际应用中境下的期望值模型决策者根据路径长度的期望值来做决策，则考虑不确定环期望值模型是指在期望约束下，使目标函数的期望值达到最优。为了寻找期望的最短路径，建立了最短路径的期望值模型。(i,j)min[(,)]E()ijijEEfxx（3.1）(i,j)PStcijijxC（3.2）(i,j)(,)110211ijjiEjiEixxinin（3.3）{0,1}ijx其中,式(3.1)为优化目标，即路的期望权值最小，亦即期望最短路;式(3.2)为约束条件，表示路权的第二分量不超过C;式(3.3)保证{|,}ijixEjx为有向图中节点1到节点n的一条路。四、有约束的期望最短路径模型的求解通常情况下，不确定规划模型由于包含有不确定函数而变得很难用传统的方法来求解。我们这里介绍一种结合随机模拟方法和遗传算法的混合智能算法来求解以上建立的模型。4.1计算不确定函数的随机模拟方法对于随机不确定优化模型，将其转化为等价的确定性优化模型是非常困难的.只有在一些特殊情况下才能做到，对一些较复杂的问题通常很难做到这一点。为了在起点1与终点n之间的众多路径中搜索出满足约束条件的最优路径，我们采用随机模拟方法来计算最短路问题中的不确定函数.随机模拟(也称MonteCarlo模拟)是随机系统建模中刻画抽样试验的一门技术,它主要依据概率分布对随机变量进行抽样。虽然模拟技术只给出统计估计而非精确结果,且应用其研究问题需花费大量的计算时间,但对那些无法得到解析结果的复杂问题来说,这种手段可能是惟一的有效的工具。随机模拟的基本思想是根据问题建立一个概率模型，通过某种用数字进行的假象试验得到抽样值，然后进行统计处理，将结果作为问题的解。随机模拟处理问题的基本步骤是:①构造概率统计模型;②定义随机变量;③通过模拟获得子样;④统计计算。随机模拟主要依据分布函数或经验分布对随机变量进行抽样，它的理论基础是大数定理。下面介绍计算最短路径中不确定函数的随机模拟步骤：模拟不确定函数:1:[(,)]UxEfx首先根据随机向量各分量的分布函数从样本空间产生样本,1,2,...,kkN，由强大数定律可知，当n时1(x,)[(,)]NkkfEfxN因此只要N充分大，1((x,))NkkfN就可以用来作为[(,)]Efx的估计值。这样设计求[(,)]Efx的随机模拟方法如下：步骤1.设L＝0步骤2.根据各条弧上的随机变量的分布函数产生样本12(,,...,)m步骤3.LLf(,)x步骤4.重复步骤2和3共N次步骤5.[(,)]L/NEfx4.2遗传算法遗传算法是一种通过模拟自然进化过程搜索最优解的方法。在解决复杂的全局优化问题方面，过去30年中,遗传算法在解决复杂的全局优化问题方面得到了成功的应用,并受到了人们的广泛关注。在优化问题中，如果目标函数是多峰的，或者搜索空间不规则，很容易在局部最优解附近徘徊。这就要求所使用的算法必须具有高度的鲁棒性，以避免在局部最优解附近徘徊,而遗传算法的优点恰好在于全局搜索。其主要特点是群体搜索策略和群体中个体之间的信息交换,搜索过程对系统模型的依赖较少尤其适用于处理传统搜索方法难以解决的复杂的和非线性问题。另外,遗传算法本身并不要求对优化问题的性质作一些深入的数学分析,从而对那些不太熟悉数学理论和算法的使用者来说,无疑是方便的。自Holland[3]用遗传算法来解决组合问题以来，由于该算法的随机搜索方法，己经被应用到通讯、工业工程等很多领域，得到了各界学者的广泛研究[4，5]。为了求解不确定环境下的最短路问题模型，我们利用遗传算法来求各种准则下的最优路径，采用如下的路径的表示方法、初始化过程和遗传算子。4.2.1遗传表示选择所求解问题解的一种合适的表示形式是用遗传算法解决问题的基础。因此对于特定的问题实例,需要对问题进行仔细分析,才能准确表示问题的实质和设计该问题的遗传算子。根据网络图中最短路的特点和遗传算法的编码原则,本文介绍的遗传表示方法是利用向量12P(,,...,)k作为染色体表示图G从节点1到节点n的一条路径。因为不同的路径包括不同的节点和弧，所以染色体的长度是不固定的。如果12(,,...,)k表示从节点1到节点n的路径，则有1121(1,)A,(,),...,(,)(,)kkkAAnA。我们给出下面的定义，111,i1,1,i,1,i,0,llijkjjxjn如果如果存在l使得=如果其它对于所有的,ijA。很容易验证按照这种方式获得的,{|}ijijxA从节点1到节点n的一条路径，我们可以按照下面的过程获得一条染色体。4.2.2染色体的初始化初始群体的创建有两种方式:随机初始化和启发式初始化。为了获得一条可行的染色体，本文介绍采用启发式染色体初始化的步骤:步骤1.设l=0，01＝步骤2.随机产生m使得ml（，）A。步骤3.lmll+1,。步骤4.重复步骤2和步骤3直到:ln。步骤5.获得一条染色体121(,,...,)l。4.2.3遗传算子在遗传算法中，遗传算子模拟生物的遗传过程产生新的后代，在遗传算法中起着重要的作用[5]。在我们的算法中，交叉算子、变异操作以及选择过程设计如下。4.2.4染色体的交叉交叉操作是由一对父代染色体通过交换其部分基因,从而形成两个新的个体,交叉算子扮演着在当前搜索区域内寻找性能更佳的个体这样一个角色。交叉方法一般有单点交叉、多点交叉、均匀交叉和算术交叉等方法.针对节点序列编码及网络路径的特点,本文介绍单点交叉。交叉方法如下：设112212P(,,...,),P(,,...,)kk为两条染色体。.在这两条染色体中选择一个相同的节点，如果在两条染色体中有共同的节点，则随机地选择一个，譬如ii。则我们可以得到下面的两条新的染色体:121121(,,...,,,...,),(,,...,,,...,)iikiik显然这两条新的染色体也是从节点1到节点二的一条可行路径。如果两条染色体没有共同的节点，则不进行交叉。4.2.5染色体变异变异按照某个特定概率Pm随机改变群体中个体的局部基因位,将算法引入新的解空间进行搜索。它本