随机算法（共9篇）
随机算法 篇1
1、引言
随机生产模拟于20世纪60年代末出现, 是电力系统规划工作中的重要工具, 用于模拟发电调度, 预测各发电机组在一段时期内的发电量期望值及燃料消耗量, 同时还可计算出该系统的可靠性指标。
随机生产模拟考虑了发电机组停运、负荷波动等不确定性因素, 很好地描述了电力生产中的随机性。在实际计算中, 有多种算法, 各算法有各自的优点与缺点, 本文将就两类常见的方法介绍对比。
2、随机生产模拟的基本原理
2.1 持续负荷曲线
随机生产模拟是以等效持续负荷曲线为核心的, 各类随机生产模拟的方法都以此为基础发展起来的, 该曲线综合考虑了发电机组的随机停运和负荷随机波动, 将两者结合起来从而形成等效持续负荷曲线。
在引入等效持续负荷曲线之前, 先对持续负荷曲线进行介绍。在得到负荷曲线时, 首先形成持续负荷曲线, 如图1所示的持续负荷曲线, 图中横坐标为系统负荷, 纵坐标为负荷的持续时间, T为模拟周期, 模拟周期根据具体的需要而定, 曲线上任意一点 (x, t) 表示系统负荷大于或等于负荷x的持续时间t, 即t=F (x) 。
用周期T除以上式, 得到
式中P可以看作系统负荷大于或等于x的概率。从而系统总负荷为
相类似的, 式 (2) 除以T, 可以得到负荷的平均值 (又称为期望值)
设系统在模拟周期T内投入运行的发电机总容量为Cs, 由图1得, 系统负荷大于发电机总容量的持续时间为
从而得到电力不足概率LOLP为
而相应的, 系统负荷大于发电机总容量时, 图1中的阴影部分的负荷需求, 从而得到电量不足期望值
2.2 递归卷积法
在实际运行中, 发电机组不完全可靠, 存在着随机停运, 因此, 需要考虑发电机组的随机停运状态, 并对原始持续负荷曲线进行修正, 得到考虑随机停运的等效持续负荷曲线。在修正等效持续负荷曲线时, 引入卷积的概念。式 (1) 为原始的持续负荷曲线f (0) , 设第一台发电机首先带负荷, 其容量为C1, 可用率为p1, 强迫停运率为q1=1-p1。
当该机组处于正常运行状态时, 它和其他发电机组所带的负荷由f (0) (x) 来表示。当机组1故障停运时, 系统负荷将由除去机组1剩下的发电机承担, 相当于机组1和其它发电机组共同承担了的xmax+C1负荷, 即曲线f (0) (x) 向右平移了C1, 即图2[1]中f (0) (x-C1) 曲线。
由于机组1可用率为p1, 强迫停运率为q1, 因此考虑其停运时, 等效持续负荷曲线变为:
同理, 可得到第i台发电机的卷积公式:
式中, Ci为第i台机组的额定容量, pi为第i机组的可用率, qi=1-pi, 为故障停运率。假设系统中有n台发电机, 当所有发电机组全部卷积后, 即可得到最终的等效持续负荷曲线f (n) (x) , 此时最大等效负荷为xmax+Cs, 而如图3[1]所示, 相对应的电量不足期望值和电力不足概率分别为:
3、等效电量函数法
上文阐述了随机生产模拟的基本原理。通过运用卷积法得到等效持续负荷曲线, 但为了保证计算精度, 计算过程需要大量的离散点描述持续负荷曲线, 计算量较大。而下文介绍的等效电量函数法在保证精度的基础上, 能够很好地解决计算量的问题。
3.1 等效电量函数法的基本原理
取机组容量的最大公因子Δx, 将横坐标x轴按Δx分段, 故根据2.2所述电量计算的公式, 可得离散化的电量函数:
式中J=
电力系统负荷的总电量为:
等效电量函数同样是把发电机组停运影响考虑在内的函数, 因此同样需要根据每个机组的可用率来安排其运行。
由2.1已知, 原始持续负荷曲线的概率分布为f (0) (x) , 其对应的电量函数则为E (0) (J) ;故安排完第i-1台发电机组带负荷后得到的等效持续负荷曲线f (i-1) (x) , 所对应的电量函数为E (i-1) (J) 。因此根据 (8) 及 (27) 式, 可得
式中Ki=Ci/Δx。
式 (30) 即为等效电量函数法的卷积计算公式。
同理, 根据 (10) 及 (27) 可得第i台发电机组的发电量为:
式中Ji-1=xi-1/Δx, Ji= (xi-1+Ci) /Δx。
在安排了第i台机组以后, 前i台机组带了区间 (1, Ji) 的负荷, 此时系统尚未满足的负荷电量应为:
式中EDi为前i台机组带负荷后, 系统中尚缺的电量。将式 (30) 代入上式得到:
由 (32) , 可得安排前i-1台机组后尚未满足的系统负荷为
因此 (33) 式中第二项为第i台机组的发电量, 与之前的式 (31) 一致。从而
而系统的电量不足期望值为:
系统的电力不足概率LOLP的计算需要用于2.2中提到的等效持续负荷曲线f (n) (x) 来说明。因为该曲线为单调减小的曲线, 所以LOLP大于其右侧Δx领域内任一点的函数值, 从而也大于该区间内函数f (n) (x) 的平均值, 平均值为:
根据等效电量函数的定义, 上式可以改写为
同理, LOLP小于其左侧Δx领域内任一点的函数值, 从而也小于该区间内, 函数f (n) (x) 的平均值, 故平均值为:
由式 (21) 及 (22) 得到LOLP的上下限:
在很小的区间内, 等效持续负荷曲线可以近似看成线性, 故在用等效电量函数法进行随机生产模拟时, LOLP计算可由下式得到:
4、算例
最后采用IEEEReliabilityTestSystem算例中的数据进行模拟, 机组数为7, 模拟周期为一天 (如表1, 2) 。
等效电量函数法的根据递归卷积法推出的, 将其结果与递归卷积法的对比, 可知, 采用等效电量函数法计算精度上相差不大, 计算得到的各机组发电量都一样, 程序运行时间也较小。因此在进行随机生产模拟时, 采用等效电量函数法比较合适。
5、结语
本文介绍了随机生产模拟的基本原理, 并介绍了两类计算方法, 通过算例比较了它们的优劣。等效电量函数法在计算量和计算精度上都有明显的优势, 因此进行随机生产模拟时, 采用该算法比较合适。
参考文献
[1]王锡凡.电力系统优化规划[M].北京:水利水电出版社, 1990:125-182.
[2]王锡凡, 王秀丽.随机生产模拟及其应用[J].电力系统自动化, 2003, 27 (8) .P10-15.
随机算法 篇2
随机结构动力可靠度估计算法的对比分析
对比分析了随机结构动力可靠度计算的三种估计算法.渐进展开法是基于Laplace算法对概率积分进行渐进估计的,此法通过计算最大被积分式值对应点,并将其代入概率积分的渐进估计表达式求解失效概率.由于概率积分的主要贡献来自于最大被积分式值对应点的周围,因此本文的重要抽样法假定重要抽样函数的最大似然值等于最大被积分式值对应点值.极值分布-泰勒展开法首先通过结构随机参数的.极值分布函数给出失效概率的表达式,随后利用泰勒展开法对失效概率进行估计,其中采用中心差分法对极值分布函数的梯度进行估算.最后应用三种算法和Monte Carlo法对受高斯白噪声激励作用的单自由度随机结构进行了计算,结果表明三种方法不但运算简便,而且对比Monte Carlo法计算效率有显著提高.
作 者：刘佩 姚谦峰 LIU Pei YAO Qianfeng 作者单位：北京交通大学,土木建筑工程学院,100044,北京 刊 名：地震工程与工程振动 ISTIC PKU英文刊名：JOURNAL OF EARTHQUAKE ENGINEERING AND ENGINEERING VIBRATION 年，卷(期)：2009 29(6) 分类号：P315.964 TU311 关键词：随机结构 动力可靠度 渐进展开 重要抽样 极值分布 泰勒展开 中心差分 stochastic structures dynamic reliability asymptotic expansions important sampling extreme value distribution Taylor series expansion central difference scheme在线考试系统中随机抽题算法研究 篇3
关键词：在线考试 随机函数 随机抽题
0 引言
随机抽题是在线考试系统中的核心部分，目前大部分的在线考试系统或无纸化考试系统大都采用了随机函数实现随机抽题，但大部分在线考试系统在随机抽题时存在抽题速度慢、试题覆盖面不稳定、重点不突出、灵活性差等问题。本文讨论了优化随机抽题的方法，给出了具体的抽题公式和查询语句。
1 优化使用随机函数方法研究
原始在线考试系统中，使用随机函数从题库中抽取试题，抽题公式为Int(Rnd*M)公式11。在抽取第一题时，直接将题号存放在指定的空数组中，表示抽取成功，以后每抽取一题，将题号和数组中已存在元素进行比较，若存在则抽取失败，若不存在则抽取成功，并将题号依次存储在该数组中，直到抽取结束。这种抽题方法的缺陷是时间浪费。这种时间浪费在单机的时候并不明显，但在B/S模式或C/S模式下，机器越多速度越慢。为了解决重复抽题，避免试题抽取过慢，可采用分段法、分类法和分类分段结合法。
1.1 分段法 分段法是解决重复抽题最简单的方法，其原理是将题库中的试题M分成N段，然后从每段中抽取一题，抽取公式为Int(Rnd*(MN))+i*(MN)(0≤i≤N-1)公式2。分段法的优点显而易见，可以完全杜绝试题重复抽取，但对题库中试题的数量有要求，即M>2N，且题库越大、试题数量越多，抽取效果就越好。在公式2中将M等分成N段，M并不一定能被N整除，也就是说采用公式2试题库最后M MOD N条试题永远不会被抽取，为了解决这个问题，可将公式2进行改进，设L=M MOD N，则抽取公式为Int(Rnd*(MN+1))+i*(MN+1)(0≤i≤L-1)公式3和Int(Rnd*(MN))+i*(MN)+L(L≤i≤N-1)公式4。分段法避免了重复抽取，但无法控制试题的覆盖面及难易程度。
1.2 分类法 分类法是在试题库的结构上添加相应分类字段，字段可以是章节、内容等，将所有试题按章节或内容分类，从每一类中抽取一题，不仅可以解决试题的重复抽取还可以控制试题的覆盖面。通常将分类字段的类型设置为整形，采用一组连续的整数作为分类字段的取值范围，这样方便在试题库中对分类进行循环查询，查询语句为select*from试题库where分类字段名=i查询1，设查询记录数为Mi，则抽题公式为Int(Rnd*Mi)公式5。分类法可以保证试卷的覆盖面，但没有侧重点。
1.3 分类分段结合法 分类分段结合法在抽取试题时先分类，然后根据设定给类分段，每类的分段数可以不同，从每个分段中抽取一题。这种方法要求在数据库中另建分类分段表，存贮每个分类中的抽题数量，数量可以是零，表示该类中不抽取，可以是大于零并小于该类题量的任何一个数Ni，表示将该类分成Ni段，每段抽取一题。从实现角度上看，分段法和分类法使用的是一维循环，分类分段法使用的是二维循环；从访问数据库角度看，分段法和分类法仅访问试题库，分类分段法除了访问试题库外还要访问分类分段表。
2 特殊要求下随机抽题的应对策略
在实际应用中，会对试题的抽取有一些特殊的要求。如何合理利用随机函数，在同一个试题库中抽取出适合不同系别、专业使用的试卷？随机函数并不是万能的，不可能独立处理以上问题，但是可以创造一个环境，随机函数在这个环境中通过简单的计算公式和相应的算法为不同系别、专业抽取需求不同的试卷。为了营造这种环境，通常会通过两方面来实现：一方面是修改表结构；另一方面是提供一个界面可以针对不同系别、专业设计不同的抽题条件。
2.1 修改表结构 修改表结构通常会在试题库中添加章、节、难度系数、出题日期、出题教师等字段。添加章、节字段既可以精确抽题范围，也可以避免抽到未学习的章节。在抽取试题时针对完全学习的章和学习过部分小节的章可以采用不同的查询方法，对完全学习的章，可以仅对章字段进行查询：select*from试题库where章=k查询2，其中k为章数，对学习过部分小节的章，除了对章字段查询外还要对节进行查询，可以针对某一节进行查询：select*from试题库where章=k and节=j查询3，j为节数，也可以针对与所有学习过的小节：select*from试题库where章=k and节in(j1，j2，…jn) 查询4，其中j1，j2，…jn为该章中所有学习过的节数。难度系数字段可以根据系、专业学习的难易程度，抽取对应试题的字段，针对不同的章、节的学习程度不同可以有不同的难度系数，以查询3为例查询可改为：select*from试题库where章=k and节=j and难度系数=i查询5，i为难度系数值。为了抽取方便，可以在试题库的表结构中添加出题日期字段，字段值为试题编辑日期，可以按日期的范围抽取出符合条件的试题。每个老师教学的重点会有差别，使用其他教师的试题可能难以评定学生的学习成果，可在试题库中加入命题教师字段，其值为命题教师工号，可以使用该字段为教师所带班级抽取试题。
2.2 提供设置抽题条件界面 试题库虽然需要很多人不断的维护，但其表结构是相对稳定的，只是在题目数量和内容方面有所变化。但是作为使用在线考试系统的系部、专业，每一年、每一个学期都会变化，他们的抽题要求不尽相同，因此，在考试系统的后台操作中需要一个设置系部、专业抽题要求的界面，在这个界面中可以通过简单的选择为每个系部、专业、班级设置若干抽题条件并存储在抽题条件数据表中。学生抽题时先判断学生的系部、专业、班级，然后从抽题条件数据表中读取对应的抽题要求，并将其转化成查询语句，在试题库中查出符合条件的试题进行抽取。
3 交换算法在随机抽题中的应用
在大部分在线考试系统中采用现场随机抽取，试题不完全相同；也有一部分考试系统中采用提前随机抽取，即在考试前由老师启动试题抽取程序，考试时所有的考生都使用这套试题，只是试题的顺序不同。作为现场随机抽取的方法前面已经讨论了，下面重点讨论提前随机抽取，提前随机抽取前半部分由老师抽取一套试题和现场抽取实现方法完全相同，后半部分是从抽取的试题当中使用随机函数重新抽取一遍以保证试题顺序不同。为了避免重复抽取，降低实现难度，有些考试系统在改变试题顺序时采用了随机函数结合交换算法的方法，设抽取的题目数量为M，将抽取的所有题号存储在数组中，下标从1到M，则抽题公式为j=Int(Rnd*M)+1公式6，使用循环For i=1toM，抽题公式放入循环，将下标为i的数组元素值和下标为j的数组元素值互换，这样可以得到一个新的试题排列。
4 结束语
本文对随机抽题的方法进行了深入的研究。文中不仅讨论了优化使用随机函数避免抽题重复的方法和满足特殊抽题要求的应对策略，而且在试题重新排列中引入了交换算法结合随机函数。灵活运用，可以设计出高效率、灵活性强、大覆盖面、重点突出的抽题模块。
参考文献：
[1]王宇颖，侯爽.题库系统试卷自动生成算法研究[D].哈尔滨工业大学学报.2003年第35卷第3期.
[2]文娴.试题库系统智能组卷与试卷分析的研究[D].湖南师范大学.2007年.
[3]李大辉.题库系统的智能性分析与研究[J].哈尔滨师范大学自然科学学报.2006年02期.
[4]张月玲，禄乐滨，曹晓敏.一种组卷策略算法[J].微电子学与计算机.2003.(6):18-20.
[5]贾振华，庄连英.浅谈网上考试系统中自动抽题的实现[J].大众科技.2006年03期.
[6]刘亚琼.基于加强学习的自动组卷算法的研究[D];天津大学.2006年.
[7]王灿辉.计算机自动组卷算法研究[J].福州大学学报.2001.29(增刊):8-10.
一种随机游走图像自动分割算法 篇4
图像分割［1］是把图像分成多个具有相同特征的区域,并对感兴趣的目标进行提取的技术和过程。图像分割是众多图像处理和计算机视觉系统的重要组成部分,是图像处理与分析中的一个基本问题。按照在图像分割中是否需要人工干预,可以划分为手工分割、半自动分割和自动分割算法［2］。手动分割完全由操作者使用鼠标等工具进行选取轮廓或关键点,速度慢,效率低。典型的半自动分割算法一般都是基于图论的分割算法,例如智能剪刀算法( In-telligent scissors )［3］,livewire［4］,图割法( Graph cuts)［5］等。自动图像分割方法在分割过程中不需要任何用户的参与,可以自动获取分割结果。
目前,图像分割方法主要向快速、自动、精确、鲁棒等方向发展。追求智能化、最优化、自主学习分割将成为图像分割领域的新热点。近年来,彩色图像分割领域虽不断涌现新方法,但是仍旧无法满足实际应用的需要,因此通过对图像分割方法进行深入的研究,不断改进原有方法,提出更加新颖有效的方法,亦或将多种方法综合运用,发挥各自的优势进行图像处理具有重要意义。例如,文献[6]提出了一种将二次分水岭和归一化割( Ncut) 相结合的SWNcut方法,先用二次分水岭预处理输入图像,采用Ncut算法得到最终结果。随机游走( RW) 算法是2006 年Grady等提出的一种基于图论的交互式图像分割算法［7］,它计算速度快,无需迭代,对噪声具有较强的鲁棒性,对弱边缘具有较好的响应,可作用于任意维图像,能够解决较难分割的任务。近几年来随机游走算法因其自身的优势备受关注,文献[8]提出了一种基于结构张量与随机游走的图像分割算法,它将结构张量与高斯权函数相结合来描述节点间相似性,实现了复杂结构图像的精确分割; 但由于算法引入结构张量增加了计算的复杂性,降低了算法运行效率。文献[9]提出了基于滑降的随机游走图像分割算法,将预分割得到的同质区域代替传统随机游走图像分割算法中的像素点来建立图结构,提高了算法的运行效率; 但由于该算法采用万有引力算子描述区域,无法精确地表达区域间的相似性,影响了算法的分割精度。
文中的目的是将交互式的随机游走变成更加灵活的自动型,提出了一种基于二次分水岭［6］和种子区域自动选取［10］的随机游走分割算法—SWRW算法。为验证文中算法的可行性,选取5 组自然彩色图像分别进行分割精度和时间效率测试,实验结果表明,文中算法分割效果和运行速度都有很大提高。
1 传统随机游走图像分割算法
Grady将随机游走算法引入图像分割领域,提出了一种交互式的图像分割方法,该算法将待分割的图像映射为带权的无向图G = ( V,E) ,结点集V是图像像素的集合,边集E是4 邻接关系的集合,边的权值表示沿着这条边行走的概率。首先由用户标记N个类别的种子像素点,然后为每个未标记像素赋予一个N元组的向量来表示从这个非种子点第一次到达N类种子点的概率,N个概率中最大者对应其最可能属于的类别,从而实现图像的分割。
传统的随机游走算法使用Gaussian函数［11］计算边的权值:
其中,gi、gj分别表示像素点vi、vj的灰度,β1是算法中唯一的可变参数。为方便处理彩色图像,常采用像素颜色距离代替( gi －gj)2。
首次到达一个种子点的概率恰好等于种子点边界条件下的Dirichlet问题的解［12］,即随机游走问题实质上是求边界值为0 或者1 的Dirichlet问题。该问题求解步骤为:
1定义Laplacian矩阵L ,如式( 2) 所示:
其中,Lij为节点vi和vj的关联矩阵,di= ∑ wij称为节点vi的度。
2将图G的顶点分为两个集合: VM( 已经标记的种子结点) 、VU( 未标记的结点) ,满足VM∪ VU=V ,VM∩ VU= Φ ,按照先种子点后非种子点的顺序来排列Laplacian矩阵L中的点,L被分成已经标记及未标记的块,如式( 3) 所示:
3令xsi表示未标记点vi∈VU首次到达标签s的概率,将每个种子点的标记集合定义为一个函数F(vj)=s,vj∈VM,0<s≤N。为每个在vj∈VM的点标记s定义|VM|*1的矩阵:
则xis可通过求解式( 5) 获得:
4通过为每个未标记点vi设置相应于的标签,获得分割结果。
从上面的算法描述可以看出,基于随机游走的图像分割算法充分利用了图像像素的邻接关系这一空间信息,SWRW算法将利用这一特点来改进传统随机游走图像分割算法。
2改进的随机游走图像分割算法—SWRW算法
2. 1 二次分水岭预分割
针对分水岭算法对图像中的噪声、物体表面细微的灰度变化都可能产生过分割的局限性,文献[13]中提到了几种解决过分割的预处理技术,主要有中值滤波、低通滤波和高斯滤波、彩色形态学等。由于这些技术去除的大多是图像中频率较高的信息,致使对边缘信息的保持效果较差。文中采用形态学中比较常见的闭- 开运算进行梯度平滑,形态学［13］开闭重构运算是建立在膨胀和腐蚀基础上的,先腐蚀后膨胀为开,先膨胀后腐蚀为闭; 闭和开这两种运算可除去比结构元素小的特定图像细节,同时避免产生全局几何失真。
梯度图像能较好地反映原图像的变化趋势,在梯度图像上进行分水岭分割能取得更好的效果,分割后的结果也较为准确。本文在求彩色图像的梯度图的时候,不能仅仅分别求得图像的R 、G 、B三个彩色分量的梯度,然后相加。因为三个图像的边缘的方向极有可能不同,甚至是相反,这样三个独立的分量图像的梯度图像可能合成错误的结果图,本文使用彩色图像的梯度图的求解方法,具体如下:
假设输入彩色图像为f( x,y) ,RGB彩色模型沿R 、G 、B轴方向的单位向量用r 、g 、b表示,定义向量为:
点乘u、v两个向量,得到结果gxx、gyy、gxy。
根据Di Zenzo理论,彩色图像中任意的向量c( x,y) 梯度即最大变化率的方向用角度表示为:
点( x,y) 在 θ 方向上的变化率Fθ( x,y) 为:
预分割首先对输入图像进行彩色图像梯度求解,然后用分水岭方法对彩色图像梯度进行一次分割处理,即以梯度图像中的极小值为起点进行淹没过程,得到各个谷地之间的分水线,这是一次分水岭的过程; 鉴于分出的区域较多,不能大幅度地降低计算复杂度; 在此基础上,对一次分水岭得到的彩色梯度图像使用形态学闭- 开运算平滑,进行第二次分水岭分割,由此不仅保持了充足信息量,也大大减少了区域数目,有利于更加精准地描述区域的统计特征。
2. 2 种子区域的自动选取并标记
在进行种子区域选取之前,先建一个N * ( N +3) 的关系矩阵A ,其中N为分水岭算法分割后的区域个数。第一列存放第i个区域相邻的个数k ; 第二列到第k +1 列存放区域i的邻接矩阵; 第k +2 列存放区域i及邻接区域的色调均值; 第k + 3 列存放区域i的标记值。如何选择种子区域进行自动分割关系到分割的好坏,本文采用了一种基于色调均值差的自动种子区域选取方法: 因为色调是决定颜色本质的基本特性,所以要求种子区域的色调均值与其邻接区域的色调均值差最大不能超过阈值。
首先选择HSI彩色模型,HSI空间利用色调、饱和度和亮度3 个属性来描述彩色图像,与人眼的色彩感知相吻合。假如一个区域Ri,它的邻接区域是Rj( j = 1,2,…,k ) ,k是邻接区域的个数,则它们的色调均值差计算公式为:
其中,x( i) 是区域Ri的色调均值,x( t) 是每个邻接区域的色调均值。而区域Ri与它邻接区域的最大色调均值差为:
满足以上相似性准则的区域就定义为种子区域,这里的阈值根据经验取为0. 03。如果取值过低,就会有更多的区域被选为种子区域,而且不同的区域也会相互连接起来; 如果取值过高,则所取得的种子区域数量就减少,且图像中的某些对象就会失去［10］。
对己选出的种子区域进行标记之前,需要先求出目标和背景的阈值T 。Otsu［14］是一种使类间方差最大的自动确定阈值的方法,具有简单、处理速度快的特点,本文使用该方法计算得到阈值T 。将区域像素灰度值与阈值T进行比较,逐个标记关系矩阵A的第k + 3 列的值。设原图像为f( x,y) ,则有如下的初始标号表达公式:
2. 3 基于区域的随机游走图像分割
本文将巴氏( Bhattacharyya ) 系数［15］与高斯权函数［11］相结合,较精准地描述了区域间的相似性。巴氏系数是由印度统计学家Bhattacharyya提出的,是对两个统计样本的重叠量的近似计算。巴氏系数可用来对两组样本的相关性进行测量。假设区域Ri和区域Rj是相邻的区域,本文用彩色直方图( 目标区域的颜色统计特征) 来进行区域描述,首先将每个通道使用16 个灰度级来表示,则共有16* 16* 16 =4096 种颜色表示,令HistＲi和HistＲj分别表示区域Ri和区域Rj的归一化直方图,p( Ri,Rj) 表示区域Ri和区域Rj的相似度,巴氏系数计算公式如下:
式( 13) 中上标u表示第u个分量。
结合高斯权函数,区域间的相似性公式为:
其中,β2>0为自由度参数,0≤p(Ri,Rj)≤1。权函数wRi,Rj较好地描述了区域间的相似性。当区域Ri和区域Rj相似时,它们的彩色直方图也相似,其巴氏系数较大,故而区域间相似性权重较大;反之,当区域Ri和区域Rj不相似时,它们的彩色直方图相似性较小,其巴氏系数较小,故而区域间相似性权重较小。
SWRW算法首先对给定的彩色图像做二次分水岭预处理,得到图像的粗略分割,然后进行形态学闭- 开运算平滑处理,融合区域中的一些孤立点,较好地避免过度分割和信息丢失,得到有限个数的初始分割小区域; 创建关系矩阵A ,利用色调均值差制定准则自动选取种子区域,并在关系矩阵中对种子区域进行标记; 将巴氏系数与高斯权函数相结合,用来描述区域间的相似性,与传统RW图像分割算法相似的是,SWRW算法同样是应用Dirichlet边界条件求解出图中所有未标记的区域首次到达各类标记区域的概率值( 电势值) ,即矩阵X - xis是其中的元素。并根据概率值的大小对未标记区域进行标记: 如果未标记的区域到达标号1 的区域概率较大,则在关系矩阵A的第k + 3 列对未标记区域标记1; 反之,则标记为2。所有的小区域都完成标号后,将标号1 的区域进行合并,合并后的区域作为SWRW算法的前景信息;同样合并标号2 的区域作为SWRW算法的背景信息,如此无需用户手动操作,自动划分出前景和背景区域,实现最终的分割。流程如图1 所示。
3 仿真实验
文中以彩色图像为主要研究对象,实验所用计算机配置为Intel( R) Core( TM) i3 - 2120 CPU @3. 30GHz 2. 94 GB内存,MATLAB R2010b环境; 文中所提出的SWRW算法适用于自然场景下彩色图像的目标分割,图2 给出了SWRW算法对彩色图像的每一步分割结果。
为了客观地评价不同的算法,文中采用分割效果和分割速度这两种性能指标。图3( a) 是待分割的彩色图像,对其进行不同的基于图论的分割方法,随后将SWRW算法与其它算法的结果进行比较。SWRW算法与传统RW算法相比,分割效果更稳定,传统RW由于只考虑了灰度值,在分割彩色图像的时候可能会造成过分割或欠分割,图3( b) 啄木鸟的嘴就没有分割完整。图3( c) 是用户指定背景后执行Grab Cut算法［5］的结果,未做进一步的交互修改。Grab Cut允许不完全的标注,通过进一步的交互修改能够得到令人满意的效果,与交互的Grab Cut算法相比,SWRW算法不仅实现自动分割,且分割效果令人满意。表1 的时间比较说明了SWRW算法花费的时间远远低于其它分割方法。
为了进一步验证文中算法的有效性,文中直接将实验结果与文献[6]中SWNcut算法的实验结果进行比较,图像的大小均为200* 200。如图4 所示,SWNcut算法虽能准确地定位边缘轮廓,但在分割时却不能准确地将目标提取出来; 相比之下,SWRW算法能得到更精确更完整的目标区域。SWNcut算法和SWRW算法运行时间对比如表2 所示,从表2 可以看出两种方法都先经过二次分水岭算法进行预分割,且预分割后的区域数目相同,在此条件下SWRW算法的运算时间要小于SWNcut算法的运算时间。
4 结束语
一个基于多种运算的随机密码算法 篇5
本文采纳各类密码算法的长处,摒弃它们各自的缺点,设计了一个基于多种简单运算、安全性高、加解密处理效率高的随机密码算法,相对有效地解决了当前各种密码算法存在的问题。
1 密码理念和设计方案
1.1 密码理念
密码技术可以保证信息的机密性、完整性和责任性。所有密码算法的加密目标都在于,“即使未经授权的人获得加密的信息并知道用来加密它的算法,要想获得对信息的访问也会非常困难。”[5]。
密码体制的实用性应该从以下两点考虑:
1)加解密算法的通用性和处理效率。
2)“体制的安全性只依赖于密钥的保密”[6],而不在于算法的保密。
1.2 设计方案
基于以上的密码理念,本文着重从加解密算法的安全性、通用性、经济指标及其处理效率出发,结合目前各种强有力的密码分析技术如差分密码分析、(非)线性密码分析和基于统计特性的密码分析等,同时吸取多种经典密码算法的优点,设计出一种不同于其他随机密码技术的基于一次一密的密码算法。
1)为了保证算法的安全性,即能够抵抗各种密码分析,应该使密文尽可能地复杂化,这里乘积密码技术(即以某种方式连续执行两个或多个密码,以使得所得到的最后结果或乘积从密码编码的角度比其任意一个组成密码都更强)是一个很好的典型。
2)密码算法的经济指标和处理效率需要从算法的计算量、加解密的速度、软硬件实现条件等方面去考虑。
3)算法的通用性侧重于算法的表达能力。
2 密码算法的描述
2.1 基本概念和符号约定
1)余数用S表示;除数用D表示;乘数用M表示。
2)密钥K由四个子密钥组成,即k1k2k3k4,而且顺序不能改变。其中,k4是余数S;k3表示除数D或乘数M;k2是表示换位方式的函数T(l1,l2)或R(l1,l2,---,lm),这里T(l1,l2)表示把某字符串中的l1和l2位置所指向的字符进行交换,R(l1,l2,---,lm)表示把某字符串中的l1,l2,---,lm各个位置所指向的字符进行循环交换,即l1=l2,l2=l3,---,lm=l1,其中l1,l2,---,lm大小可以随机排列,以增大破译的难度。k1是用来表示与余数S进行异或运算的各子串的起始位置的定位函数I(li,lj,---,lx)。
2.2 加密过程
1)假设明文P=p1p2---pn,把它表示为ASCII码值。先随机选择一个数作为余数S,即k4。为了使密文具有较高的保密性,S位数一般在4位以上且各位数尽量相异。然后根据n的大小来选择第一次加密采用除法还是乘法运算,除数D和乘数M的位数根据明文的长度来合理选择。具体实现过程如下:
#define N 30//N值可以根据具体情况来设定
这样产生了第一次密文C。
2)从C中随机选择需要换位的位置以及换位方式,通过换位产生第二次密文C’。可用C语言表示如下:
l1,l2,---,lm散布范围尽量大些且相邻位置所指向的数字要相异,这样才能有效地保证密文的安全性。
3)在C’中随机选择一些子串的起始位置,产生k1=I(li,lj,---,lx),li,lj,---,lx散布范围也应该尽量大些,并按从左到右的顺序依次与余数S进行异或运算,则C’转化为C’’,C’’为待发送的密文。C’’要用十六进制表示,这是因为异或运算的结果若仍用ASCII码表示就可能出现溢位,这样会使接收方无法正确解密。
同时产生密钥K=k1k2k3k4,为了减少密钥长度,可以简化K的格式,即省略k1,k2,k4的首字母和双括号,但为了接收方能够正确判断第一次密文C进行的是何种运算,k3的首字母不可省略,不过可以省略其双括号。同时在子密钥间用分号隔开。即:K=li,lj,---,lx;l1,l2(,---,lm);D(M);S。
最后把密钥K通过安全信道发送给接收方,并将密文C’’通过普通信道发送到接收方。
2.3 解密过程
接收方收到发送方传送过来的密钥K和密文C’’后,使用K按照与加密完全相反的运算顺序对密文进行解密。
1)首先利用k1=I(li,lj,---,lx)按从右到左的顺序与k4进行异或运算,产生C’。值得注意的是,由于各子串间可能部分重叠(其实这种情况会增大了破译密码的难度),因此必须按与加密时相反的运算次序进行异或运算,以保证C’’准确无误地转化成C’。
2)然后根据k2=T(l1,l2)或R(l1,l2,---,lm)将C’中各位还原到原来的位置,得到C。
3)最后依据k3的首字母,判断原文P进行何种运算,如果采用乘法,则有:
P=(C-S)/M
如果采用除法,则有:
P=(C-S)*D
这样接收方就可以得到明文P,即发送方要表达的信息。
3性能分析
1)与其他的密码算法不同,该算法不是在加密前就事先选定某密码,而是在加密过程中根据合理的方案逐步产生子密钥,从而具有一定的随机性和高安全性。
2)由于该算法只采用了三个非常简单的运算,便于软硬件的实现,因此加解密的处理速度比许多经典的密码算法要快得多。
3)此算法采用了综合三个不同运算的技巧,不但掩盖了语言的统计特性,如在英语中最常用的是字母e,其次是t,a,o,n等,避免了基于语言统计特性的密文分析;而且满足严格的雪崩效应;更重要的是,它给出了对于穷举攻击的高复杂度。例如,在一个待发送密文长度为100位(十六进制)、余数为8位数,除数为6位数、换位位数为5、进行异或运算的子串数为6的信息中,即使密码破译者知道了它们各自的位数和子串数,其穷举攻击的复杂度是非常高的,即约为9*107*9*105*P(100,5)*P(100,6),约为1037。
4 示例验证
假定要加密的信息为:P={PLEASE GO TO THE BANK}。为了方便起见,这里假设的明文长度较短。该明文的ASCII值为:{8076 69 65 83 69 71 79 84 79 84 72 69 66 65 78 75}。
1)令S=5136,因为P长度较短,所以宜采用乘法运算,令M=20。根据C=P*M+S得到C={16 15 33 93 16 73 94 35 96 9596 94 53 93 33 16 26 36}。
2)由于S位数较少,为了加强保密性,宜采用循环交换R(l1,l2,---,lm),令R(6,16,27),即把第6位的3换作5,把第16位的5换作9,把第27位的9换作3,这样得到C’={16 15 35 9316 73 94 39 96 95 96 94 53 33 33 16 26 36}。
3)令I(1,3,23,31),即将100F(1615的十六进制)与3324(5136的十六进制)进行异或运算得到的结果是232B,再将2B23与3324异或得到1807,接着把5E35(9453的十六进制)与3324异或得到6D11,最后把101A(1626的十六进制)与3324异或得到233E。则产生待发送的密文C’’={23 18 07 5D 10 49 5E27 60 5F 60 6D 11 21 21 23 3E 24}。
4)同时生成密钥K=1,3,23,31;6,16,27;M20;5136。发送方把密钥K通过安全信道发送给接收方,并将密文C’’通过普通信道发送到接收方。
5)接收方收到发送方传送来的密钥K和密文C’’后,先利用k1=I(1,3,23,31)和k4,把C’’转化为C’={16 15 35 9316 73 94 39 96 95 96 94 53 33 33 16 26 36}。
6)接着利用k2=R(6,16,27),把C’变换为C={16 15 3393 16 73 94 35 96 95 96 94 53 93 33 16 26 36}。
7)最后利用k3和k4把C还原为明文P={80 76 69 65 8369 71 79 84 79 84 72 69 66 65 78 75},亦即PLEASE GO TO THE BANK。
由于本示例中明文长度很短,因此从密钥长度跟明文长度差不多的角度来看,此算法没能体现出它的优点。然而在现实通信中,信息明文长度一般比较长,此时该算法就体现出其强大的优越性。
5 结束语
本文通过比较分析各类密码技术的优缺点,设计出一个综合性能好的基于三种简单运算的随机密码算法。它有效地防御各种密码分析,具有很高的安全性和较好的实用性。然而该算法也是属于对称密钥密码体制,有它自身的一些缺点,如密钥管理与分配等问题。因此,密钥必须通过安全的信道来传送。
摘要：本文着眼于密码体制的实用性,设计了一个基于四则运算、换位、异或等多种运算的具有一定的随机性的密码算法。它在具有高效率的加解密处理的同时给出了对于穷举攻击的复杂度,保证了算法对各种密码分析的安全性。
关键词：简单运算,随机密码,加解密,密钥,算法
参考文献
[1]袁家政.计算机网络安全与应用技术[M].北京:清华大学出版社,2002.
[2]卢开澄.计算机密码学[M].北京:清华大学出版社,2003.
[3]罗毅.信息安全与密码算法[J].湖北教育学院学报,2006,23,(08):37-39.
[4]戚君贤,周建钦.密码理论算法综述[J].电讯技术,2006,(05):18-22.
[5]Maiwald.E著.马海军,王泽波,等译.网络安全基础教程[M].北京:清华大学出版社,2005.
随机仓库布局问题模型与算法研究 篇6
仓库运作是企业物料管理的重要部分,Tompkins[1]指出,货物的存储成本大约占货物生产总成本的15%~70%,降低仓库运作成本是减少生产成本,提高企业经济效益的重要突破口。仓库布局问题旨在解决如何制定科学的货物存储计划来合理地存储各种不同型号的货物,使总的搬运成本最小化。科学的仓库布局能有效地指导货物的存放与搬运,减少货物损伤,加速货物周转流通,从而降低存储成本。
对于仓库布局问题的研究,大部分都是基于以下四种存储策略:基于类的存储策略、专门存储策略、随机存储策略和共享存储策略。Francis etal[2]对设备布局和选址问题进行了综述,并详细地探讨了上述四种基本存储策略;K.K.Lai etal[3,4]利用基于类的存储策略对纸卷仓库的布局问题进行了研究。他们把仓库的可利用空间划分为面积大小相等的单元,在此基础上,提出把遗传算法用于两阶段迭代的启发式方法,来分析仓库布局问题,使纸卷总的搬运成本最小化;Larson etal[5]提出把货物根据其周转率的不同分为不同的等级,周转率越高的货物堆放在离出口越近的位置,根据专门存储策略能有效地调节存储空间以满足存储作业的需求,从而降低物料管理的成本;Van Oudheusdeh etal[6]利用旅行商算法,提出了针对货架布局的解决方法;Chang和Egbelu[7]分析了在自动存取系统中,搬运工具停放位置的规划对减少最大反应时间的前提作用。他们研究的问题要求一辆搬运机械负责系统中一条或者多条专门的通道,并且通道在系统中的位置不变。随着不确定优化理论广泛应用,一些学者将其应用到对仓库布局问题的研究上来。Zhang、Lai和Yang[8]研究了模糊条件下的多层仓库的布局问题,并设计出针对这问题的算法;Yang和Sun[9]对仓库在模糊随机条件下的布局问题进行了探讨和研究,考虑不同货物的贮存要求,建立了期望值模型,并为仓库布局问题设计了混合智能算法。
本文讨论了随机条件下仓库布局问题,建立机会约束规划模型,并设计出基于随机模拟的禁忌搜索算法求解模型,最后设计算例来验证模型的正确性与算法的有效性。
1 仓库布局问题概述
当货物到达仓库时,被卸放在进出口外,决策者决定其存放位置后,由叉车把这些货物搬运至存放位置,相应的仓库存货清单将随之更新,当有订单时将执行相反的作业过程。在这个过程中,不考虑搬运机械的能力限制。在给仓库布局的过程中,需要最大化地减少货物总的搬运成本。
本文假定仓库只有一个进出口,且为单层结构。仓库被分为面积大小相等几列,每列又分为大小相等的单元,货物将存储在这些小单元中,某些单元将用于停放叉车等工具。同时设置一定数量的叉车通道以便货物搬运,通道位于每两列存储单元之间。
为了方便叉车在存储单元的存取作业,更好地利用仓库的存储空间,应对货物进行分类。货物分类方式多种多样,可根据其性质、体积、重量或周转率等进行分类。例如根据体积分类,一类货物包括某一体积范围内的所有型号的货物,如体积在2 m~2.5m范围内的所有型号的货物,这样,每类货物又包含不同的型号。为了方便操作,本文规定每个存储单元只能存储同一类货物,并且最多只能堆放同类中两种不同型号的货物。当某存储单元堆放有两种不同型号的同类货物时,必须按照一定的次序摆放,比如同一型号的货物堆放在同一柱面上,周转率高的货物堆放在靠近通道的位置,比重大的货物堆放的底层等。
当货物到达时,决策者将决定货物的存储位置,同时根据到达的货物量安排一定的存储空间,这样便形成了货物的存储需求,即货物对存储空间的需求。到达的每种型号的货物都有一定的存储需求,本文假定在布局决策之前,各型号货物的存储需求已经确定,它用来决定分配给各型号货物的存储空间。在本文中,只考虑各型号货物的月需求量,以此作为货物的搬运量,各型号货物月需求量为一个随机变量。
在为仓库布局的过程中,会出现某型号货物的存储需求大于一个存储单元存储能力的现象,这时货物会占用两个或两个以上的单元,这种货物被称为“分割型货物”。为了方便表述,把这型号的货物根据其月需求量和存储需求按比例分为不同的部分,并视为几种不同的相互独立的型号。例如,一种分割型货物需要2.8个存储单元来堆放,则这型号的货物将按比例被分为三个部分,每部分占初始需求量和存储需求的1/2.5、1/2.5、0.8/2.5。为了简化问题,本文假定要布局决策前货物已经完成了上述的分割,这样,每种型号货物的存储需求不会超出存储单元的存储能力。
假定仓库拥有足够的存储空间来存放货物,同时不考虑叉车的能力限制,仓库布局问题研究的目的是使货物总的搬运费用最小化。货物搬运费用可看作是搬运的货物量与其搬运距离的乘积,货物搬运的总费用就是各型号的货物搬运费用之和。其中的搬运的货物量由各型号货物的月需求量计算得出,搬运距离为叉车搬运货物时的行走距离。事实上,叉车不可能严格的按照直线路程行走,其行走距离的计算是不精确的,它的值可以利用存储单元中心到进出口的水平距离来估计得出。
2 随机仓库布局问题的机会约束规划模型
在模型建立之前,先引进以下参数:为可以利用的存储单元;Qi表示i型号货物的月需求量,统计为一随机变量;Dk表示叉车从k单元到进出口的行走距离,统计为一随机变量;Si为i型号货物的存储需求;C表示存储单元的存储能力;Hi表示每单位i型号货物搬运单位距离所需的费用。
根据上述参数,可随机仓库布局问题的机会约束规划模型:
模型的目标函数为∑iI∑kKHiDkQixik,minf&是目标函数的β悲观值。模型中约束条件(1)保证每种型号的货物存放在同单元中;约束条件(2)为每个存储单元最多只能存放两种不同型号的货物;约束条件(3)保证每个单元存放的货物量不会超过其存储能力;约束条件(4)保证每个存储单元只能存放同类的货物。其中的β可由决策者根据问题的需要给定。
3 基于随机模拟的禁忌搜索算法
Liu[10]指出可以利用混合智能算法来解决不确定规划问题,受这种思想的启发,本文将用禁忌搜索算法和随机模拟技术相结合的混合智能算法来求解前面所建立的模型。
3.1 随机模拟
下面介绍如何利用随机模拟技术来求得随机仓库布局问题的机会约束规划模型中的目标函数值。
算法步骤为:
Step1:置N'为βN整数部分;
Step2:从随机向量的概率分布空间抽取样本（x,Qn,Dn）n=1,2,…,N;
Step3:对于每一组（x,Qn,Dn）n=1,2,…,N,求解目标值f（x,Qn,Dn）,n=1,2,…,N;
Step4:返回中的第N'个最小的元素。f x,Q1,D1’),f x,Q2,D2’),…,f x,QN,DN’)$%
3.2 禁忌搜索算法
3.2.1 解的表示形式
在算法中,解的表示形式直接影响到算法的有效性和计算速度,本文采用下面这样一个二维数组形式作为解的表示形式:
其中li为整数且1≤li≤K,在此数组中,第一行中的数是个货物型号的代号,第二行为存储单元的代号,即li表示i型号货物存放在li单元中。这种表示形式满足每种型号的货物只存放在同一个单元中,在解码后所对应的变量xik的值为:
3.2.2 邻居结构
候选集合由邻域中的邻居组成,本文设计的候选集合是对当前解进行变化形成的所有可行解组成。本文中解的变化为:二维表中第一行保持不变,变li另一个整数l'i’1≤l'i≤K),便可得到一个新解x'。如果x'为可行解,则解的变化可行且x'为可行邻居。
3.2.3 特赦规则
本文的特赦规则为:设x'为当前最优解,x为候选集合中的最优解,如果x的变化被禁且满足x所对应的目标值优于x'对应的目标值,则将对应x的禁忌变化解禁。
3.2.4 算法步骤
Step1:生成一个可行解x,设当前的迭代步数presentiter=0,当前最优解所在的迭代步数bestiter=0,当前解presentsol=x,当前最优解bestsol=x,初始化禁忌表;
Step2:由presentsol生成候选集合V,其中集合中的元素要求为非禁忌的或是特赦的,令presentiter=presentiter+1;
Step3:对候选集合中的元素进行解码,生成对应的xik;
Step4:求出候选集合中解所对应的目标值;
Step5:在V中找出目标值的最优解x';
Step6:若x'对应的目标值由于bsetsol对应的目标值,则bestsol=x',presentsol=x',bestiter=presentiter,否则,presentsol=x';
Step7:更新禁忌表;
Step8:若presentiter<M(M的值有决策者决定),则重复Step2;否则,跳至Step9;
Step9:输出最优解,结束计算。
4 算例分析
本文采用图1所示的仓库结构,此仓库中有38个存储单元,假定仓库中每个存储单元的面积为8×8m2,通道宽度为4m。
假定有20种型号(用1~20的数字分别编号)的货物需要存放在此仓库中,货物都是立方体形状,各型号货物的边长分别为:1.00,1.00,1.10,1.15,1.20,1.20,1.30,1.40,1.45,1.45,1.50,1.60,1.60,1.65,1.65,1.701.90,1.90,1.95,2.00。根据边长把这些货物分为三类,[1.00,1.30]为第一类,包括前七种型号的货物;第二类的边长范围为(1.30,1.60),包含第八种到第十三种型号的货物;(1.60,2.00)为第三类,包含后七种型号的货物。对于每类货物,搬运单位该类货物行走单位距离所需的费用分别为0.05,0.06,0.08。各型号货物相应的存储需求分别为36,36,36,30,36,11,25,25,25,9,16,25,19,16,14,16,16,10,9,7。
本算例把叉车搬运货物的行走距离和货物的月需求量都视为三角随机数。首先测定存储单元中心到进出口的最短直线距离为x,则其随机距离可视为T’x,x+4,x+2)。各型号货物的月需求量如表1:
利用随机模拟来求解模型的目标函数值,其中的β取值为0.95(决策者可以根据需要调节β值),模拟样本数的抽取由决策者选择。在处理器为赛扬2.4,内存256MB的计算机上运算可得算例的结果如表2。
经过4 000次模拟,131次迭代后,本例得到近似最优解2 889.85,最大误差不超过0.07%,目标值和误差的平均值分别是2 889.34和0.019%。相应的货物的布局形式如图2。
5 总结
本文探讨了随机条件下的仓库布局问题,在对介绍仓库布局相关问题后,建立的随机仓库布局问题的机会约束规划模型,分析了该模型的数学性质,并设计了基于随机模拟的禁忌搜索算法来求解模型,最后通过算例验证所设计算法的有效性。计算结果表明,本文提出的模型与算法是有效的。
参考文献
[1]J.A.Tompkins,J.A.White,Y.A.Bozer,E.H.Frazelle,J.M.A.Tanchoco,J.Trvino,Facilities Planning[M].New York:Wiley,1996.
[2]R.L.Francis,L.F.McGinnis Jr.,J.A.While,Facility Layout and Location:An Analytical Approach[M].Prentice-Hall,En-glewood Cliffs,NJ,1992.
[3]Lai K.K.,Xue J.and Zhang G.Q..Layout design for a paper reel warehouse:A two-stage heuristic approach[J].International Journal of Production Economics,2002,75:231-243.
[4]Zhang G.Q.,Xue J.,Lai K.K..A genetic algorithm based heuristic for adjacent paper-reel layout problem[J].International Journal of Production Research,2000,20:3343-3356.
[5]T.N.Larson,H.March,A.Kusiak,A heuristic approach to warehouse layout with class-based storage[J].IIE Transactions,1997(29):337-348.
[6]Van Oudheusdeh,D.L.,Sharma,D.,and Tzen,Y.J.,An evaluation of storage policies for the assignment of facilities to lo-cation[J].International Journal of Production Economics,1968,16:150-173.
[7]S.H.Chang,P.J.Egbelu,Relative pre-positioning of storage/Retrieval machines in automated storage/retrieval systems to minimize maximum system response time[J].IIE Transactions,1997(29):303-312.
[8]Zhang G.Q.,Lai K.K.and Lixing Yang.A fuzzy multiple-level warehouse layout problem[C]//Proceedings of the9th Bell-man Continuum International Workshop on Uncertain Systems and Soft Computing,2002:236-239.
[9]Yang.L.X.,Sun.Y.B.Expected Value Model for A Fuzzy Random Warehouse Layout Problem[J].IEEE International Con-ference on Fuzzy Systems,2004,25(29):751-756.
随机算法 篇7
OFDM (Orthogonal Frequency Division Multiplexing) 是一种并行的多载波传输技术, 它通过相互正交的多个子载波来传输信息, 使受到干扰的信号能够可靠地接收。目前, OFDM技术已经成功地应用于数字音频广播 (Digital Audio Broadcasting, DAB) 、数字视频广播 (Digital Video Broadcasting, DVB) 、无线局域网 (Wireless Local Area Network, WLAN) 等高速率数据传输系统中。
OFDM的不足之处主要表现在对定时和频率偏移敏感和高峰均功率比 (Peak to Average Power Ratio, PAPR) 。较高的PAPR会导致发送端对高频放大器 (HPA) 的线性要求很高而且发送效率极低, 接收端对前端放大器的线性要求也很高而且会增加D/A和A/D转换器的复杂度。
目前已有的降低OFDM信号PAPR值的方法大致可分为三类:最简单的方法就是通过对OFDM信号进行限幅来降低PAPR值, 但限幅引入了非线性失真, 导致系统的误码率性能下降;分组编码类方法降低PAPR的基本思想是将原来的信息码字映射到PAPR较小的序列来进行传输, 从而避开会使OFDM信号出现峰值的码字, 编码技术[1]的计算复杂度非常高, 编解码麻烦且使信息速率大大降低, 只适用于子载波数目较小的情况;信号扰码类方法则着眼于降低OFDM信号峰值出现的概率[2], 可有效降低信号的PAPR值又不对信号产生畸变, 尽管其计算复杂度较大, 但随着数字信号处理技术的发展, 该技术最有希望解决OFDM系统中的峰均比问题。部分传输序列 (Partial Transmit Squence, PTS) 法就属于信号扰码类技术, 本文提出了将随机分割子序列的分块方法与迭代移位搜索加权因子方法相结合的改进PTS算法, 通过仿真证明改进方法降低了系统的PAPR。
1 PAPR基本原理
OFDM系统中的PAPR是指OFDM信号的峰值功率与平均功率的比值, 因此PAPR可定义为:
式中:x (t) 代表一个OFDM符号的波形, 分子表示x (t) 的最大瞬时功率, 分母表示x (t) 的平均功率[2]。对于包含N个子载波的OFDM系统来说, 当N个子载波都以相同的相位求和时, 所得符号的PAPR (dB) 就是平均功率E{|x (t) |2}的N倍。因此, 基带信号的PAPR可以表示为PAPR=10lg N。可见当N较大时, OFDM系统的PAPR就会很高。
根据中心极限定理, 当子载波数N较大时 (一般取N>64) , OFDM信号的包络服从瑞利分布, 其功率服从均值为零、自由度为2的χ2分布, 其分布函数的数学表达式为F (z) =1-e-z。在实际应用中, 习惯用PAPR超过某一门限值PAPR0的概率即互补累积概率分布函数 (CCDF) 来表征PAPR的分布, 其表达式为:P (PAPR>z) =1- (1-e-z) N。
2 降低PAPR的PTS算法
PTS原理如图1所示。输入数据块X被分割成M个不相交子块, 每一块进行IFFT变换后的时域信号再乘以相位序列叠加合并来降低PAPR。 PTS方法是要通过适当地选择辅助加权系数, 使得峰值信号达到最优化。
文献[3]中所提到的降低OFDM系统峰均功率比的PTS方法是将输入的数据符号分割成几个子块, 并分别给每一子块乘以不同的权值, 然后通过选择适当的权值来减小传输信号的PAPR。现已提出很多方法来减少其运算的复杂度, 如在文献[4]提出次优化方法寻找加权系数, 其加权系数取值范围只限于[+1, -1]。还有文献[5]提出的格形因子搜索的方法, 文献[6]提出的迭代移位线性搜索法及文献[7]提出的循环移位线性搜索法。
3 基于随机分割的PTS改进算法研究
PTS-OFDM系统中有三种分割子块的方法:相邻分割法、随机分割法和交织分割法[8]。相邻分割法是把N/M个连续的子载波按顺序分别分在同一个子块里面;随机分割法中每个子载波被随机地任意分配到M个PTS内;交织分割则将相邻间隔为M的子载波分配到一个子块中。
以上提到PTS的三种不同分割方法中, 如其他条件一致, 随机分割方法在降低OFDM系统PAPR的性能方面最佳, 如图2所示。
本文在随机分割方法的基础上, 对最优加权系数的寻找方法进行了改进。
3.1 原PTS方法的遍历搜索过程
(1) 将N个子载波随机分割为M个子序列, 相位因子bm=±1;
(2) 令bm=1 (m=1, 2, …, M) , 计算此时的峰均功率比PAPR0;令b1=-1, 且计算此时的PAPR1;如果PAPR1>PAPR0, 则b1=1, 否则b1=-1不变;
(3) 按照同样方法依次优化bm (m=1, 2, …, M) , 当优化完bm后, 完成搜索。
3.2 新PTS方法的遍历搜索过程
(1) 将N个子载波随机分割为M个子序列, 相位因子bm=±1 (m=1, 2, …, M) ;
(2) 令b2i-1=1 (i=1, 2, …, M/2) , b2i=-1 (i=1, 2, …, M/2) , 计算此时的峰均功率比PAPR0;令b1=-1, 且计算此时的PAPR1;如果PAPR1>PAPR0, 则b1=1, 否则b1=-1不变;
(3) 按照同样方法依次优化bm (m=1, 2, …, M) , 当优化完bm后, 完成搜索。
上述两种方法利用随机分割子序列的方式将N个子载波分割为M个子序列, 降低了双层搜索法[9]的复杂度, 虽然对系统PAPR的改善有所降低, 但是在实际应用中仍是可行的。
为了描述改进方法对OFDM信号峰均功率比的改善情况, 本文进行了计算机仿真, 仿真的条件是:子载波数为N=128, 子块M=4, 调制方式采用QPSK调制。
由图3的仿真分析可知, 新方法的CCDF性能优于原随机分割法的CCDF性能, 在CCDF=10-4时, PAPR改善了近0.5 dB。
4 结 语
本文提出了一种降低OFDM信号峰均比的改进算法, 该算法降低了PTS系统双层搜索法计算复杂度, 改善了原随机分割法的CCDF性能。
摘要：正交频分复用 (OFDM) 系统的一个主要缺点是信号的峰均功率比 (PAPR) 很高。提出了一种将随机分割方法与迭代移位搜索加权因子相结合的改进PTS算法。仿真结果表明, 改进后的算法在改善PAPR性能和计算的复杂度之间取得了较好的折衷。
关键词：正交频分复用,峰均功率比,部分传输序列,随机分割方法
参考文献
[1]DAVIS J A, JEDWAB J.Peak-to-meanpower control anderror correction for OEDM transmission using Golay se-quences and Reed-Muller codes[J].Electronics Letters, 1997:267-268.
[2]邵佳, 董辰辉.Matlab/Simulink通信系统建模与仿真实例精讲[M].北京:电子工业出版社, 2009.
[3]MULLER S H, BAUML R W.OFDM with reduced peak-to-average power ratio by multiple signal representation[J].In Annals of Telecommunications, 1997, 52 (1) :58-67.
[4]CIMINI L J, SOLLENBERGER N R.Peak-to-averagepower ratio reduction of an OFDM signal using partialtransmit sequence[J].IEEE Commun.Lett., 2000, 4 (3) :86-88.
[5]WU Bing-yang, CHENG Shi-xin.Patrial transmitting se-quence method based on trellis factor search[J].Journal ofSoutheast University, 2005, 21 (2) :123-126.
[6]尹东辉, 褚姝韫, 崔伟.降低OFDM系统中峰平比方法研究[J].科技广场, 2006 (11) :14-16.
[7]王裕民.OFDM关键技术与应用[M].北京:机械工业出版社, 2006.
[8]MULLER S H, HUBER J B.OFDM with reduced peak-to-average power ratio by optimum combination of transmit se-quences[J].Electronics Letter, 1997, 33 (5) :368-369.
[9]HOWS, MADHUKUMAR A S, Chin F.Peak-to-averagepower ratio reduction using partial transmit sequences:asuboptimal approach based on dual layered phase sequencing[J].IEEE Trans.on Broadcast., 2003, 49 (2) :225-231.
随机算法 篇8
随机早期检测RED(Random Early Detection)算法是最早提出的主动队列管理算法。RED能够在拥塞发生的初期对其进行控制，从而防止了拥塞加剧。研究表明，RED较传统的弃尾(DropTail)算法在保证Internet的稳定、健壮、高效上效果更好。但是该算法不能进行自适应参数调节，而且平均队长不可预测。本文对主要的RED算法进行了深入研究，从理论上分析了其优缺点，并验证了改良算法对网络性能的改善。
1 随机早期检测(RED)算法
随机早期检测(RED)算法的基本思想是通过监控路由器输出端口队列的平均长度来探测拥塞，一旦发现拥塞迫近，用丢弃数据包或对包头置位的方法向连接通报拥塞，使他们在队列溢出之前减少拥塞窗口并降低发送数据速率，以缓解网络拥塞。RED算法能够在维持较低的队列长度的同时容忍一定的突发流量。
RED算法可分为两部分：一是计算平均队列长度，决定网关允许的流量突发的程度，以此来反映拥塞的状况;二是计算包标记的概率以决定在当前拥塞程度下路由器该以多大的概率丢弃数据包。在这两部分中权值w和阈值的设置最为关键。
1.1 平均队列的计算
RED算法在计算平均队列长度avgQ时，采用了类似低通滤波器(low-passfilter)带权值的方法：
其中WQ为计算队列的平均长度时采用的权值，相当于低滤波器的时间常数，决定了路由器对输人流量变化的反应程度，WQ设置得过大会使平均队长不能滤掉突发流，若过小则难以检测到初始拥塞。q为采样测量时实际队列长度，avgQ是平均队列长度。这样由Internet的突发流量或者短暂拥塞导致的实际队列长度暂时的增长将不会使得平均队列有明显的变化，从而“过滤”掉短期的队长变化，尽量反映长期的拥塞变化并据此来计算丢包概率。
1.2 包标记概率的计算
RED设置了两个与队列长度相关的阈值minth和maxth，当有包到达路由器时，RED计算出平均队列长度avgQ。若avgQ
概率P的计算方法如下：
其中，maxp是最大丢弃概率,minth为队列长度的最小阈值，maxth为队列长度的最大阈值，Pb是当前队列实际丢弃概率，count表示上次丢弃分组后收到的分组个数，Pa为Pb的修正概率，是为了保证被丢弃分组间隔的均匀分布，用于避免连续丢包,故以后仅考虑Pa。由于Pa是随着当前队列长度的变化而变动的,该机制的最大适应范围为丢包率在[0,maxQ]流量，当然，实际范围要小得多。概率Pb不仅与avgQ有关，而且还与上一次丢包开始到现在进入队列的包的数量count有关。
2 RED算法的优缺点
相比于DropTail,RED算法基本实现了以下目标：(1)最小化包的丢失和队列延迟;(2)避免了全局同步问题，较大地提高了物理线路的利用率;(3)某个连接的分组被丢弃的概率大致与该连接所占用的带宽成正比，从而保证了一定的公平性。
虽然RED有以上的优点，但是它也存在一些还有待完善的地方：(1)RED的平均队长对于拥塞的程度和RED参数设置十分敏感，从而导致了平均队列长度不可预测，这将引起网络时延不确定;(2)当存在非响应连接时，不能有效地隔离和保护TCP连接。当拥塞发生时也无法保证各个流的公平性，需要依赖用户终端协作与配合才能真正发挥作用;(3)RED网关虽然能够确定一些恶意流(misbehaving flow)，但是并未提出如何控制它们的机制;(4)对于非TCP协议(如基于速率的开环、闭环协议)，RED网关的行为难以确定。
3 RED算法的改进
RED算法是基于平均队列长度进行包的接受和丢弃的，这样做的好处是允许一些短暂的突发业务量。Sally等提出两种RED算法，如表1算法RED-1和算法RED-2)，并对这两种算法进行改进，提出了RED-3和RED-4算法。
RED-1在计算丢包概率时，没有考虑包的大小。首先，count每次包到达时都加1，第二步利用先前的平均队列长度avgQ、最大门限maxth、最小门限minth计算临时概率Pb，接着算出丢包率。而RED-2则考虑包的大小，它在第三步中把包的长度L和包的大小M引入，对临时概率重新计算，加入此步可以更好的计算丢包率。
Pb是计算中临时使用的概率,minth和maxth分别是队列的最大和最小门限值,L是刚到达的包长度,M是包的最大长度,RED-1和RED-2的区别在于第三步。RED-1的优点是count服从均匀分布,这样就避免了droptail中连串丢包现象,从而防止了TCP的全局同步。
Sally等人证明了RED-1服从均匀分布：表2 RED算法改进计算步骤
n是前后两次丢包之间收到的包数据。
TCP的有效吞吐率公式
C是常量，它依赖于所采用的TCP类型;MTU为最大传输单元(Maximum Transport Unit);RTT是往返时间(round trip time);p是丢包率。假设MTU1和MTU2是两个具有相同RTT的TCP流的不同的MTU，为了获得一致的公平性，应该满足,P1和P2分别是两TCP连接各自的丢包率，用L替代MTU1,M替代MTU2,RED-2的改进形式的计算步骤如表2。
RED-3是对RED-2的修改，它在计算最终丢包率时考虑了接受的包大小，RED-4是对RED-3的修改，可以证明RED-4也服从均匀分布，假设n是两次丢包之间收到的包数目(包括丢弃的包)，Li是第i个包的长度。
从理论上说RED-4可以获得最好的公平性，但是要实现完全的公平是很难达到的，RED-4比RED-3的吞吐量略高的原因是RED-4的丢包概率服从均匀分布，这样可以避免全局同步，从而提高链路的利用率。
4 总结
RED算法是主动队列管理算法的代表，目前的改进算法都有各自的优点和有待改进的地方，文章综述了RED算法的基本思想和实现机制。根据TCP的有效吞吐量公式，对Sally等人提出的两种对RED算法进行了改进。对其进行分析表明该算法在获得高吞吐量的同时，能取得更好的公平性。但是值得注意的是，改进算法在完善了RED的基础上大都很难解决自身的参数设置问题，如何解决这个问题有待我们进一步研究。
摘要：随机早期检测RED(Random Early Detection)算法是主动队列管理(Active Queue Management)算法研究的重点之一。它的主要思想是在拥塞发生以前,通过计算队列中包的丢失概率,从而随机丢弃一部分数据包,以达到实现网络拥塞控制的目的。但该算法在应用中仍有不足。该文详细讨论了随机早期检测算法的关键技术问题,研究了对RED算法的改进,并总结了这几种算法的优缺点及其有待改进之处。
关键词：随即早期检测,平均队列长度,丢弃概率
参考文献
[1]FLOYD S,JACOBSON V.Random Earl Detection Gateways for Congestion Avoidance[J].IEEE/ACM Trans on Networking,1993,1(4):397-413.
[2]BRADEN B.Recommendations on Queue Management and Congestion Avoidance in the Intemet[EB/OL].http://citeseer.ist.psu.edu/braden97 recomm endations.Html.
[3]Floyd Sally,Oummadi Ramakrishna.Shenker Scott.Adaptive RED:An algorithm for increasing the robustness of red'S active queue man-agement[EB/OL].http://www.icir.org/floyd/papers/adaptive Red.Pdf.
随机算法 篇9
客户需求的响应速度, 提高服务质量, 降低运营成本。本文在综合考虑企业运输成本最小化和客户满意度最大化的基础上, 针对不确定配送时间的随机车辆路径问题, 建立随机机会规划模型。最后通过实例对模型求解, 结果表明该算法能取得更好的优化结果和更快的收敛速度。
物流配送是现代化物流系统的一个重要环节, 它是指按照用户的订货要求, 在配送中心进行配货, 并将配好的货物及时的送交收货人的活动。配送活动中的配送车辆的行驶线路优化确定问题, 是近20多年来国际运筹学界的研究热点之一。国外将物流配送车辆优化调度问题归结为VRP (Vehicle Routing Problem, 即车辆路径问题) 、VSP (Vehicle Scheduling Problem, 即车辆调度问题) 和MTSP (Multiple Traveling Salesman Problem, 即多路径旅行商问题) 。在以往的研究中, 在规划路线之前, 相关的信息和参数都是确定的。因此相应的配送车辆路径的安排也是固定的, 然而在实际的VRP问题中经常会遇到许多不确定性的因素, 如客户需求数量的不确定、车辆运行时间的不确定性, 服务时间的不确定性等等, 这些不确定性因素给决策部门增加了不少困难.已有的关于VRP的文献中, 包含时间窗口约束的文章很多。例如Chaug-Ing Hsu等描述了带时间窗约束易腐食品的VRP问题, 给出模型以及相应的求解方法;Repoussis P P描述了带车辆返回和时间窗约束的VRP模型, 重点给出了基于自适应编程下的几种算法, 并给出算例;Roberto cordone则在文中重点研究了带时间窗约束的启发式算法;而对随机车辆路径问题 (Stochastic Vehicle Routing Rroblem, SVRP) 的车辆的不确定运行时间和客户有时间窗要求的相关的研究文章比较少, 因此本文对随机配送时间和有时间窗约束的车辆路径优化调度问题的研究具有广泛的应用背景和经济价值。
1 问题的提出及模型建立
1.1 问题的提出
在物流配送过程中, 配送车辆的路径规划是很关键的一环, 合理的路径规划能够提高配送效率、节省成本, 提高客户的满意度。一般带时间窗约束的随机配送时间车辆路径优化问题描述为:一个配送中心里有k辆车, 车辆m的固定运载能力为Qm。现向n个客户运送货物, 客户j的需求量为q j (q j小于车辆的固定运载能力) , 客户j的卸货时间窗口为[aj, bj], 问题是求在满足货运需求, 行驶路程最小的配送车辆行驶路线, 每个配送点只被一辆车访问一次。配送车辆到达配送点的时间应尽可能的在时间窗范围内进行。每辆车的行驶路线只有一条, 且一条线路上的货物量总和不超过车辆的固定运作能力。
1.2 模型建立
随机约束规划车辆配送路径规划问题, 假设:
(1) 仅考虑单一的配送中心, 所有的配送车辆从配送中心出发, 并最终回到配送中心;
(2) 配送中心有若干相同容量的车辆, 每辆车只有一条行驶路线, 其间可以为多名顾客服务;
(3) 每条线路上的总运输量不超过车辆的装载能力;
(5) 每个客户点所需货物只能由一辆车供给;
(6) 每个客户点都有指定的服务时间窗口, 配送时间应尽可能地在时间窗口范围内进行;
(7) 配送车辆在不同客户间的行驶时间服从正态分布。
1.2.1参数和变量定义如下:
j=0:代表配送中心;
j=1, 2, …, n:客户数目;
k=1, 2, …, m:配送中心的车辆数;
qj为配送点j的需求量;qj
dij:配送点i和j之间的行驶距离,
Q为车辆的容量, B为车辆最大配送时间;
Ti为配送点i的服务时间, Ti=λqi (λ=0.3) , 对于不同的配送货物取λ不同的值;
ti车辆到达i的时间;
wi车辆提前到达客户i的等待时间;
tijk为车辆k在路段 (i, j) 上的行驶时间, 服从正态分布为平均服务时间, σi j为标准差;
[aj, bj]:配送点j的时间窗, 其中aj和bj分别是客户j时间窗口的起始和结束时间, j=1, 2, …n;
g (x, y) 车辆行驶的总距离
该问题的随机机会约束规划数学模型:
目标函数 (4) 是使车辆配送路径最短。约束 (5) 保证每个客户只由一辆车进行配送服务;约束 (6) 保证车辆从配送中心出发, 最后又回到配送中心;约束 (7) 保证一个客户仅被服务一次;约束 (8) 每辆车到达服务的客户并离开;约束 (9) 每条路线上的需求量之和小于车辆承载量;约束 (10) 为时间窗约束, 车辆k在时间窗口内到达的概率不小于α;约束 (11) 车辆k的配送时间小于最大配送时间B的概率不小于β。约束 (11) 为奇异子回路排除约束。
2 随机配送车辆路径问题的混合智能算法
2.1 编码、初始种群的构造、解码
根据该问题的求解特点, 采用实数编码的方式, 等位基因即为实数的值, 染色体为一个实数向量, 染色体的长度即为实数向量的大小, 这种编码具有精度高, 便于搜索等优点。本文为一个配送中心为N个客户提供服务。每个染色体用一个2行N列的矩阵表示, 矩阵的列序号对应客户的编号, 第一行的数字表示配送车辆的编号, 取值为1, 2, …, m, 即该数字所在列的客户由该数字表示的车辆配送, 第二行的数字表示客户由同一车辆配送的顺序号, 例如M=3, N=14即配送中心的3个车辆为14个顾客配送货物, 车辆编号分别为1、2、3。一个染色体的表示形式如图1所示:
在矩阵中的第5列对应客户5, 该列的第一行数字表示客户5由车辆3配送, 该列的第二行数字表示为客户5被同一车辆配送的顺序号为2, 那么第5列数字表示为客户5由车辆3安排的配送顺序号为2。在解码当中, 由上述编码方式可以知道车辆的所配送的客户以及客户的配送顺序号, 如上式表示的染色体中, 有第一行可以确定车辆1配送的客户为1、4、9、10, 由第二行知客户1、4、9、10的配送顺序号为4, 、1、2、3从而确定配送客户顺序为4—9—10—1, 同样可以确定车辆2的配送客户顺序为13—14—6—3—2—8—11, 车辆3配送的客户顺序号为7—5—12。在得到各个车辆的配送路径后, 在根据约束条件检验染色体的可行性。
2.2 交叉与变异
两个父代个体之间的交叉操作如图2所示进行, 依次遍历父代的每一列, 如果两个父代对应列是不相同的, 则以一定的概率交换两列, 如父代个体1和2, 除了第1、4、7、9、和13列相同不交换之外, 其余各列按交叉概率交换, 假设第3列与第8列发生交换。
两个父代交叉产生两个子代, 交叉后代中同一个车辆所配送的客户顺序号会出现重复、间断的现象, 采用修复策略将非法个体变为合法个体。该修复策略是将同一车辆所配送的客户按其顺序号排列, 最后将客户顺序号修正为排列后的位置顺序号。
父代个体:
子代个体1:车辆1对应的客户的顺序号从小到大排列为1、2、3、4、4, 其中顺序号4对应的客户为1和3, 现对车辆1配送的客户顺序号进行修复, 针对客户1和3进行随机排列, 其余客户所在位置不变, 重新排列得到的客户顺序号为:4、9、10、1、3和4、9、10、3、1两种排法, 假设随机得到的是后者的排列法, 按客户重新排列后对应的位置顺序号修正客户顺序号, 对于车辆2和3客户顺序号没有出现重复的情况, 直接按对应的位置顺序号修正客户顺序号。得到的后代个体如图3所示。
子代个体:
交叉结束后, 按变异的概率随机的选取进行变异的个体, 在该个体中随机选取属于同一配送车辆的两个客户并将其顺序号进行交换, 从而完成变异。如图4所示, 随机选取的变异染色体, 在该染色体中随机选取属于配送车辆2的客户6和13, 将其顺序号交换, 客户6的配送顺序号由原来的3变为1, 而客户13的顺序号由原来的1变成了3。
2.3 选择
计算每代群体中的个体的适应度, 并按其值由大到小进行排序, 排在最前面的染色体性能最优, 它将直接进人下一代, 并排在第一位。下一代群体的另外pop_slze-1个染色体将通过旋转赌轮的方式, 按一定的选择机制产生。每次旋转都为新的种群选择一个染色体, 这样产生一个新种群。
3 算法流程
Step1初始化种群产生pop-size个染色体, 进化代数G=0。
Step2选择:使用随机模拟检验后代的可行性, 根据目标值, 使用基于序的评价函数计算每个染色体的适应度, 选择个体, G=G+1。
Step3交叉:基于配偶染色体基因位置的交叉算子进行交叉操作。
Step4变异:变换变异算子对随机选择的染色体进行变异。
Step5更新最优解。
Stpe6终止条件判断, 若满足将最好的染色体作为最优解输出, 否则转步骤2。
4 算例分析
某物流公司有一个配送中心和10个客户 (n=10) , 分别记为“0”和“1, 2, …, 10”;配送中心有三辆
配送车辆 (m=3) , 其运载能力为700;客户需求如表1所示。配送中心与客户之间以及客户之间的时间分布 (υij, σij2) (i, j=1, 2, ..., 1 0) 如表2所示。遗传算法的相关参数如表3所示。
利用计算机进行模拟求解, 经模拟500次遗传迭代我们得到最优的配送路径方案:
5 结论
物流配送路线的优化问题本身是一个NP难题, 近几年来有许多的学者进行了很多的研究。但是, 在实际配送路线优化过程中, 由于存在许多的不确定因素, 这就给物流决策者做出合理的决策带来了许多困难。本文在许多学者研究的基础上, 提出了随机机会约束规划的物流配送车辆路线优化的模型, 并给出了相应的求解算法, 计算结果表明, 用基于随机机会约束规划的遗传算法求解本问题具有良好的性能, 利用此方法可以方便有效地求得物流配送车辆路径优化问题的最优解或近似最优解。
参考文献
[1]刘宝锭, 赵瑞清, 王钢.不确定规划及应用[M].北京:清华大学出版社, 2003:79-90
[2]Chaug-Ing Hsu, Sheng-feng Hung, HuiChieh Li.Vehicle routing problem with time-windows for perishable food delivery[J].Journal of food Engineering, 2007 (80) :465-475.
[3]Roberto Cordone, Roberto Wolfer Calvo.A heuristic for the vehicle routing problem with time windows[J].Journal of Heuristics.2001 (7) :107-129.
[4]谢桂芩.车辆路径问题建模及多目标进化算法[D].广东工业大学, 2012:5-13.
[5]娄山佐, 史忠科.基于交叉熵法解决随机用户和需求车辆路径问题[J].控制与决策, 2007, 22 (1) :7-10.
[6]谢秉磊, 郭耀煌, 郭强.动态车辆路径问题:现状与展望[J].系统工程理论方法应用, 2002, 11 (2) :116-120.
[7]Baker B, A yechew M.A genetic algorithm for the vehicle routing problem[J].Compu-ter&Operation Research, 2003, 30:787-800.
[8]XING Wenxun, XIE Jinxing.Modern optimization method[M].Beijing:Tsinghua University, 2005.