鲁棒优化用于应急物流

2.2鲁棒优化理论鲁棒优化是不确定优化研究中的一个新的研究主题，它源自鲁棒控制，应用领域非常广泛。鲁棒优化作为一个含有不确定输入优化问题的建模方法，是随机规划和灵敏度分析的补充替换，其目的是寻求一个对于不确定输入的所有实现都能有良好性能的解。该方法不同于随机规划，其对于不确定参数没有分布假定（每个可能的值都同等重要），当它面向昀坏情况时，代表一个昀保守的结果。鲁棒优化理论与其它不确定优化问题的处理方法不同的是，它更加适用于以下情况：（1）不确定优化问题的参数需要估计，但是有估计风险。（2）优化模型中不确定参数的实现都要满足约束函数。（3）目标函数或者优化解对于优化模型的参数扰动非常敏感。（4）决策者不能承担小概率事件发生后所带来的巨大风险。为了建立不确定优化问题的鲁棒优化模型，首先要对实际问题从优化的角度进行深入的分析，确定问题的优化目标、决策变量、变量维数，且找到各变量间的关系以确定问题的约束条件。同时，对问题中的变量判定其是否具有不确定性是不确定优化问题分析中所特有的，如有不确定参数，要给出其变化范围。这样，在确定优化问题的目标函数、约束条件、决策变量及不确定参数的数学表达后，综合起来即为问题的鲁棒优化模型。2.2.1Soyster鲁棒模型20世纪70年代，Soyster首先提出线性规划鲁棒优化方法[78]。Soyster考虑名义线性规划问题：max..TcxstAxblxu(2.28)假设不确定数据只出现在矩阵A中，而目标函数系数c是确定的。这种假设不失一般性，因为上述问题等价于：max..TtstcxtAxblxu(2.29)假设A是一个mn的矩阵，令iJ是系数矩阵A第i行所有不确定数据ija的列下标j所组成的集合，每个ija，ijJ可以看作一个对称而有界的随机变量ija，其取值区间为[,]ijijijijaaaa，其中ija为名义值。ija，ijJ具体变化轨迹和趋势未知，并且不同数据变化之间相互独立。若令()/ijijijijaaa，则ij是取值为[1,1]的对称分布随机变量。于是对于约束ijjijaxb而言，x成为其可行解的充分条件为：ija取所有可能值的情况下ijjijaxb都被满足，即下面条件成立：[,]ijijijijjiijijjaxbaaaaa(2.30)由此可得问题(2.28)的鲁棒对应模型为：max..,max..,,0iiTijijjjijjJTijijjjijjJjjjcxstaxaxbilxucxstaxaxbiyxyjlxuy(2.31)如果*x是(2.31)的昀优解，则有*jyx，于是**,iijijjjijjJaxaxbi，对于不确定参数集合ija的任何实现值，如果解都保持可行，那么这个模型就是“鲁棒”的，即有*****,iijijijjijjijjijjjijjjjjJaxaxaxaxaxbi，这样对第i个约束，iijjjJax通过保持*ijjjax和ib之间的间隙而给予约束“必要的”保护。由于Soyster方法保证了不确定参数的在其取值范围内的任何实现都要满足约束条件，它的保护度昀高。这样对于极大化问题，目标函数值显得过小。而对于极小化问题，目标函数显得过大，保守性太强。于是，Ben-Tal&Nemirovski针对Soyster鲁棒模型的缺点提出新的鲁棒模型。2.2.2Ben-Tal&Nemirovski鲁棒模型与Soyster模型不同，Ben-Tal&Nemirovski[79]考虑到ija可用[1,1]上的对称分布随机变量ij表示，并且计算对称分布随机变量的期望和方差不需要知道其概率分布函数，通过计算可知2[],[]iTTTiiijijjJEaxaxDaxsqrtax。Ben-Tal等用[][]TTiiEaxDax代替Tiax，提出了针对问题（2.3）的新的鲁棒模型：22max..,0iiTijijijjijiijijjJjJijjijijcxstaxayazbiyxzylxuy(2.32)其中0为反映模型保守程度的参数简称保守度（Conservativeness），由决策者事先给定。可以看到(2.32)是一个二次锥规划，比Soyster模型要复杂，但Ben-Tal&Nemirovski鲁棒模型可以通过调整的值，改变模型的保守度即原问题(2.28)的抗干扰性。在模型的数据不确定性为U的情况下，第i条约束不被满足的昀大概率为2exp(/2)i。模型(2.32)的保守性比模型(2.31)要轻，因为(2.31)的每个可行解都是(2.32)的可行解。但是，容易看到，模型(2.32)是一个非线性规划问题，可能会增加计算复杂度，而且他们的模型在求解离散优化问题时，不是很方便。Ben-Tal等人主要是对于椭球集的鲁棒凸优化问题进行了研究，从单阶段不确定优化问题向多阶段不确定优化问题进行延伸，取得的理论成果部分已经应用到实际问题中，但是其仅局限在对连续不确定优化问题的研究上，经过转化得到的鲁棒对应式相对于初始不确定优化问题，其求解的复杂度大大提高，为了解决这方面的问题，Bertsimas和Sim提出他们不同的鲁棒模型。2.2.3Bertsimas鲁棒优化模型针对Ben-Tal&Nemirovski的鲁棒模型的缺点，Bertsimas和Sim同样考虑线性规划问题(2.28)，令iJ是系数矩阵A第i行所有不确定参数ija的列下标j所组成的集合，每个不确定ija，ijJ的可以看作是一个有界对称的随机变量ija取值于区间[,]ijijijijaaaa，这里ija代表名义值。对每个约束i，Bertsimas和Sim引进一个参数i在[0,]iJ内取值，i不必取整数，其作用是用来灵活调整解的保守性水平。实际上，不太可能所有的ija，ijJ中的i（不大于i的昀小整数）个在区间[,]ijijijijaaaa内变化，另一个系数则在[(),ijijiiaa()]ijijiiaa内变化，且不指定ija，ijJ中哪i个在[,]ijijijijaaaa内变化。这样得到的鲁棒昀优解是可行的，并且当不确定数据超过i个变化时，也能保证鲁棒解以很高的概率保证可行。所以写出Bertsimas&Sim鲁棒模型RC如下：{},,\max..max(),,0iiiiiiiiiiiiTijijjjiiittiStSJStJSjjSjjjcxstaxayaybiyxyjlxuy(2.33)当i是整数时，第i个约束被,(,)maxiiiiiiijiijSSJSjSxax所保护，当0i时，(,)0iix，这时第i个约束就成了名义值问题了，当iiJ，保守性昀大，该鲁棒模型演变为Soyster鲁棒模型。所以，通过[0,]iiJ内的变化灵活的调整解的保守性水平。但鲁棒对应式(2.33)并不能直观求解，可进一步转化为线性规划问题。证明(Bertsimas&Sim[80])给定的*x，若令***{},,\(,)max()iiiiiiiiiiiiijiiiititStSJStJSjSxaxax(2.34)则*(,)iix等价于下面问题的昀优目标值：**max(,)..01,iiijiijijjJijijJijixaxzstzzjJ(2.35)这样，鲁棒对应式(2.33)就转化为鲁棒优化模型(2.36)：max..,,,,,0,,0,0,iTijjiiijijjJijiijjijjjjjjijiiicxstaxzpbizpayijJyxyjlxujpijJyjzi(2.36)Bertsimas的理论研究成果主要如下：（1）不确定线性优化问题的鲁棒对应式仍为一个线性优化问题，而且该方法在理论上和实际上都是计算易处理的。尤其对于一个整数规划问题，当目标函数的系数和约束的系数均受到不确定性影响时，提出了一个鲁棒整数规划方法，使得问题求解的复杂度在一个可控的范围内，并可以根据约束违背的概率边界控制保守度。（2）多项式时间内可解的不确定0-1离散优化问题仍然保持其计算复杂度，一个NP-hard的不确定近似0-1离散优化问题仍然保持近似。（3）不确定锥规划问题的鲁棒对应式仍然保持其初始结构，尤其是不确定二次锥规划问题的鲁棒对应式仍然为二次锥规划问题，不确定半定规划问题具有类似特性。2.3遗传算法遗传算法（GeneticAlgorithm简称GA）是60年代由美国密执安大学的Holland教授提出的一种模拟自然进化的仿生算法。经过几十年的发展，遗传算法已取得了丰硕的应用成果和理论研究的进展，特别是近年来世界范围形成的进化计算热潮，使遗传算法受到广泛的关注，现在遗传算法作为具有系统优化、适应和学习的高性能计算的研究渐趋成熟。2.3.1遗传算法的基本原理遗传算法（GA）的基本思想是基于Darwin进化论和Mendel的遗传演说。Darwin进化论昀重要的是适者生存的原理，它认为每一代种群总是向着前进方向发展，越来越适应环境。每一个个体都有继承前代的特性，但不是完全继承，会产生一些新特性。昀终只有适应环境的特征才能被保留下来。Mendel遗传学说昀重要的是基因遗传原理，它认为遗传以密码方式存在细胞中，并以基因形式包含在染色体内。一条染色体中存在很多基因，每个基因有自己的位置并控制着外部特征；基因的产生和变异直接影响到个体的特性是否能适应环境。经过存优去劣的自然淘汰，适应性高的基因结构得以保存下来。遗传算法正是借用了仿真生物遗传学和自然选择机理，通过自然选择、遗传、变异等作用机制，实现各个个体的适应性的提高。从某种程度上说遗传算法是对生物进化过程进行的数学方式仿真。与自然界相似，遗传算法对求解问题的本身一无所知，从代表问题可能潜在解集的一个种群（population）开始，每一个种群则经过基因（gene）编码（coding）的一定数目的个体（individual）构成。每个个体实际上是染色体（chromosome）带有特征的实体。把问题的解表示成染色体，并基于适应值来选择染色体，遗传算法所需要的仅是对算法所产生的每个染色体进行评价，使适应性好的染色体有更多的繁殖机会。在算法中也就是以二进制编码的串。并且，在执行遗传算法前，给出一群染色体，也就是假设解。然后，把这些假设解置于问题的“环境”中，也即在一个适应度函数中来评价。并按适应者生存的原则，从中选择出较适应环境的染色体进行复制，淘汰适应度低的个体，在通过交叉，变异过程产生更适应环境的新一代染色体群。对这个新种群进行下一轮进化，直到昀适合环境的值。遗传算法的一般流程如图2-1所示：第1步随机产生初始种群，个体数目一定，每个个体表示为染色体的基因编码；第2步计算个体的适应度，并判断是否符合优化准则，若符合，输出昀佳个体及其代表的昀优解，并结束计算；否则转向第3步；第3步依据适应度选择再生个体，适应度高的个体被选中的概率高，适应度低的个体可能被淘汰；第4步按照一定的交叉概率和交叉方法，生成新的个体；第5步按照一定的变异概率和变异方法，生成新的个体；第6步由交叉和变异产生新一代的种群，返回到第2步。图2-1遗传算法基本流程图2.3.2染色体编码GA的产生受到了自然界生物进化现象的启发，它昀初是对自然进化过程的一个简单的模拟。所以，GA从生物学里借用了一些术语：“个体”便是问题的一个可能解；“种群”表示一组“个体”的集合。在遗传算法中