求解随机规划问题的差分进化算法DESP

埃及信息学杂志（2017）18，75开罗大学埃及信息学杂志www.elsevier.com/locate/eijwww.sciencedirect.com全长文章求解随机规划问题的一种新的差分进化算法Ali Wagdy Mohamed开罗大学统计研究所业务研究部，埃及接收日期2015年10月2日;修订日期2016年8月24日;接受日期2016年9月27日2016年10月27日在线发布摘要提出了一种求解随机规划问题的差分进化算法DESP。该算法引入了一种新的三角形变异规则，该规则基于三角形的凸组合向量和三个随机选择向量中最优个体与最劣个体之间的差向量。与传统差分进化算法相比，新的变异算子增强了算法的全局和局部搜索能力，提高了算法的收敛速度。DESP使用Deb此外，还采用了一种新的动态容差技术来处理等式约束。本文考虑了两种随机规划问题模型：线性随机分式规划问题和多目标随机线性规划问题。将DESP算法与基本DE算法、基本粒子群算法（PSO）、遗传算法（GA）及已有的结果进行了比较，结果表明，与文献中引用的结果相比，©2016制作和主办由Elsevier B.V.代表计算机与信息学院开罗大学。这是一篇基于CC BY-NC-ND许可证的开放获取文章（http：//creativecommons.org/licenses/by-nc-nd/4.0/）。1. 介绍随机或概率规划（SP）处理的情况下，一些或所有的参数的优化电子邮件地址：aliwagdy@gmail.com开罗大学计算机和信息系负责同行审查。问题是由随机或概率变量描述的，而不是由确定性的量[1]。这些问题的数学模型可以遵循模型系数的任何特定概率分布[2]。其主要目的是寻找受随机事件影响的模型参数的最优值。随机规划的基本思想是将随机问题转化为等价的确定性问题，并利用适当的经典和/或现代数值方法求解SP被广泛应用于管理科学、工程和技术的许多现实世界的决策问题此外，它已被应用于各种领域，如金融[3]，制造业产品http://dx.doi.org/10.1016/j.eij.2016.09.0021110-8665© 2016制作和主办Elsevier B. V.代表开罗大学计算机和信息学院这是一个在CC BY-NC-ND许可证下的开放获取文章（http：//creativecommons.org/licenses/by-nc-nd/4.0/）。制作和主办：Elsevier关键词微分进化;随机规划;分式规划;多目标规划76A.W. 穆罕默德..2容量规划[4]，发电容量规划[5]，供应链管理[6]，水资源配置模型[7]，投资组合选择[8]，项目选择[9]，交通运输[10]、电信[11]、能源规划[12]，医疗管理[13]和营销[14]。约束线性随机分式规划（LSFP）问题是指两个线性函数在一定约束条件下的比值最优化问题，其中至少有一个问题的数据是随机的，且具有非负性对变量的约束。此外，一些约束可以是确定性的。因此，LSFP框架试图通过假设输入或其一部分由概率分布指定而不是确定性来对数据中的不确定性进行建模[15]。有许多算法来解决LSFPP，如[16此外，SP已被应用于具有多个，冲突和不可协调的目标，而通常不存在的问题一个单一的解决方案，可以优化所有的目标[20]。文献[20另一方面，在过去的三十年里，进化算法（EA）已经发展到解决非线性，高维和复杂的计算优化问题。实际上，进化算法最初是为了克服全局优化问题的挑战，如非线性，非凸性，非连续性、不可微性和/或多峰性，而传统的数值优化技术难以处理这些问题。差分进化（DE）是一种基于随机种群的搜索方法，由Storn和Price[24]提出。DE被认为是解决实参数优化问题的最新EA[25]。虽然DE与其他EA有相似之处，但在DE中，距离和方向信息用于指导搜索过程[26]。本文研究了随机规划问题的两种模型：线性随机分式规划问题和多目标随机线性规划问题。 对于LSFPP和MOSLP，分别遵循Charles和Dutta[19]以及Charles等人[20]采用一种新的差分进化算法DESP求解这两类随机规划模型的确定性等价模型。 该算法基于三角形的凸组合向量和三个随机选择向量中最优和最劣个体的差向量，引入了一种新的三角形变异规则。与传统差分进化算法相比，所提出的变异算子DESP使用Deb的约束处理技术，基于可行性和约束违反的总和，没有任何额外的参数。此外，还采用了一种新的动态容差技术来处理等式约束。DESP算法得到的结果与DE和PSO的基本版本以及文献[19，20]中引用的结果一致。值得注意的是，虽然本文的工作是对文献[27]中工作的扩展和修改，但仍有以下显著区别：（1）文献[27]中的工作是针对无约束问题提出的，而本文的工作是针对约束问题提出的。 因此，（2）一种新的动态公差技术来处理等式约束也被采用，（3）交叉率，[27]由动态非线性增加概率方案给出，但在这项工作中，交叉率固定为0.95。(4)本文只使用了三角形变异规则，而在文献[27]中，三角形变异策略被嵌入到DE算法中，并通过非线性递减概率规则与基本变异策略DE/rand/1/bin相结合。(5)在以前的工作[27]中，基于随机突变和修改的BGA突变的重启机制用于避免停滞或过早收敛，而这项工作没有。本文的其余部分第2节介绍了我们感兴趣的问题和Deb处理约束的程序。在第3节中，介绍了标准DE算法，并对其算子和参数进行了回顾。 接下来，在第4节中，描述了所提出的DESP算法。问题定义见第5节。在第6节中，所提出的方法，实验设置和数值结果的有效性进行了讨论。最后，在第7节中得出结论和未来的工作。2. 问题陈述一般来说，约束优化问题可以表示如下（不失一般性，这里考虑最小化）：尽量减少f！xx x;！x1;x2;.. . ;xn 2ffin1受制于：gj！x≤60;1;. . . ;q2hj！x=0;j<$q1;. . . ;m 3在哪里！XX∈S，X是可行域，S是由参数约束l i6xi6u i; 1 6i6n定义的n维矩形空间，其中l i和u i分别是决策变量x i的上下界。为一个不平等约束的满足gj！x60j21;. . . ;q在任何点！x2X，我们说它是活跃的！X. 所有等式约束hj！x0;jq1;.. . ;m被认为在X的所有点上都是有效的。大多数与EA一起使用的约束处理方法倾向于只处理不等式约束。 因此，等式约束被转换为转化为形式为hj的不等式约束！x-e60，其中e是允许的公差（非常小的值）[28]。为了处理约束，我们使用DebDeb[29]提出了一种新的有效的基于可行性的规则来处理遗传算法的约束，其中使用以下标准比较成对解：在两个可行的解决方案中，具有最高拟合值的方案获胜。如果一个解决方案是可行的，另一个是不可行的，可行的解决方案获胜。如果两个解都不可行，则优先选择约束违反总和最小的解因此，Deb[29]引入了可行解选择过程的优越性，其基础是约束搜索空间中的任何个体都必须首先遵守●●●求解随机规划问题772fg我（Ran ddjuji6CRorjuji6randnjuji6r;IJð ÞC我8 ¼我R1R2R3MJMax我我我JJIJJJ我J我.Σ3.5. 选择然后是目标函数。 实际上，Deb通常，从上面的问题公式中，有m个约束，因此个体的约束违反量由m维向量表示。使用允许相等的公差（e），约束，决策向量或索引的约束违反3.3. 突变在G代，对于每个靶载体xG，突变载体根据以下公式vG 1：vG1¼xGFω。xG-xG;r1vidual！第j个约束上的x由下式计算：具有随机选择的索引r1;r2; r31; 2;. ;NP. F是控制差值vec的放大的实数！（max0;gj！xx x x;j1;. . . ;q托尔。xG-xG根据Storn和Price[34]，cvj xmax0;. 啊！x100。 -e;j<$q1;。 . . ;mð4Þr2r3J如果是一个决策向量或一个个体！x满足第j个约束条件cj！x=0。如[30]所述，为了同时考虑所有约束或平等对待每个约束，然后对每个约束违反进行归一化除以人口中最大的违反限制的情况。因此，群体中每个约束的最大违反由下式给出：F在[0，2]中。如果突变向量的一个分量违反了搜索空间，则使用（7）或新的其他修复方法生成该分量的值。3.4. 交叉二项式交叉，使用以下方案将目标向量与突变向量混合，以产生试验向量uG 1。JMaxMaxx！2scj！x100万5千uG1.5G1IJxG;rand_j_n>CR和j- randn_i_n;ð9Þ这些最大约束冲突值用于规范化每个约束冲突。规范化的约束违反被加在一起以产生标量约束违反c！x表示该个体，其取值为0和1IJ其中，j≠1;2;. . . ;D，ran d<$j< $2½0;1]是均匀随机生成器数的第j次评估。 CR2½0;1]为交叉率，randn=1/2 f 1;2;... ;Dg是随机选择的指数使得uG<$1从vG<$1中得到至少一个元素;我我否则，将不产生新的父载体，m！c！x1Xcjxj1ð6Þ人口不会改变。3. 方法3.1. 差分进化DE采用贪婪选择策略。当且仅当试验向量uG 1产生的适应度函数值与比xG，则uG<$1被设置为xG<$1。否则，旧向量xG为我我我本节提供基本差分进化（DE）算法的简要总结在简单DE中，通常称为DE/rand/1/bin[31，32]，初始随机总体由以下组成：保留。选择方案如下（对于最小化问题）：（f.uG16fxG我NP向量X！我-我1;2;. . . ;NP，并且是随机生成的根据下边界和上边界内的均匀分布，初始化后，这些个体通过DE算子（变异和交叉）进化以生成试验向量。然后进行亲本和其试验载体之间的比较，以选择应该存活到下一代的载体[33]。DE步骤讨论如下：3.2. 初始化为了建立优化过程的起点，必须创建初始种群。通常，初始种群的每个向量中的每个决策变量都被分配了一个从边界约束中随机选择的值：x01/4 x Lrand j·.xU-xL其中randj表示[0，1]之间的均匀分布的数，为每个决策变量生成新值。ixG;否则标准DE算法的详细描述在图中给出。1.一、4. DESP算法所有的进化算法，包括DE，都是基于随机种群的搜索方法。因此，不能保证将一致地达到全局最优解此外，它们最初不是为了解决约束优化问题而设计的。然而，调整控制参数，如比例因子，交叉率和人口规模，以及开发一个适当的变异方案和耦合适当的和有效的约束处理技术可以显着提高DE算法的搜索能力。此外，在复杂的数值和工程约束优化中取得有前途和成功结果的可能性，问题越来越多。因此，本文提出了三种修正方法，阳离子的引入，以显着提高标准DE算法的整体性能。C¼xG1.5ð10Þ78A.W. 穆罕默德CRðÞC图1标准DE算法的描述。rand [0，1）是一个返回0到1之间的实数的函数。randint（min，max）是一个函数，返回一个介于min和max之间的整数。NP、GEN、CR和F是用户定义的参数。D是问题的维数。4.1. 三角突变通过许多已开发的进化算法和实验研究的实践经验证明，基于种群的搜索算法的成功是基于在两个矛盾方面之间保持平衡：探索和利用[35]。此外，突变为了提高DE算法的全局搜索能力，加快DE算法的收敛速度，提出了一种新的三角形变异规则，该规则基于三角形的凸组合向量和三个随机选择向量中最优个体与最劣个体的差向量。修改后的突变方案如下：方案在DE搜索能力和mG1¼x<$G2F·。xGxΣð11Þ收敛速度然而，即使DE算法具有良好的全局搜索能力，但局部搜索能力弱i;jc;j最好的;j最差;j开发能力和收敛速度仍然太低其中x<$G是三角形的凸组合向量，最佳解的最大值[36]。很显然，G最好G最糟糕是最好和最坏的人从突变Eq.在公式（8）中，可以观察到随机选择三个向量用于突变，然后在这三个向量中随机选择基向量。因此，基本变异策略DE/rand/1/bin能够保持种群多样性和全局搜索能力，但速度变慢这三个随机选择的向量。F是一个单-形式的随机变量，u0; 1返回0和1之间的实数，具有均匀随机概率分布，G是当前生成数。该修改旨在替换等式（1）中的随机基向量xG。（8）由凸1差分进化算法的收敛性因此，为了提高组合向量x<$G剩下的两个向量是GX和x求解随机规划问题79GGG.F·xG最好CPiið Þ ðÞ¼ ¼ ¼ ð Þ¼最好最好CCC..最好最糟糕i;jc;j最好的;j更好;j更好;j最差;jC最好我i¼1i.Σ由三个随机选择的矢量中的最佳和最差矢量代替，以产生差矢量。在Eq. 式（11）最初根据以下突变方程执行：mG1¼x<$GF·。XG-x你好F.XG-xΣ在xG方向上每个x<$G的区域-x每一个变异的载体。简而言之，它集中利用搜索空间的一些子区域。因此，它具有更好的局部搜索趋势，从而加快了所提出的算法的收敛速度此外，全球探索算法的能力是显着提高，形成其中xGG最好的;jG更好-x最差;jG最糟糕Σð12Þ是最好的比赛，更好，通过优化过程在可行域中生成许多不同大小和形状的三角形。因此，所提出的定向突变平衡了全局探索能力最差的三个随机选择的向量，分别。三角形的凸组合向量x<$G是三个随机选择的向量的线性组合，定义如下：地方开发倾向。4.2. 比例因子x<$G¼w1·xGW2·x3.xð13Þ在突变Eq. （8）微分常数F是a差向量的缩放因子这是一个重要其中实权重w满足wP0和31/1w1/4。控制种群进化速率的参数其中，实际权重wi由wi^p=P3给出 p;关于全局无约束优化，在原始DE算法在[30]中，微分常数F为我1; 2; 3.哪里p11,p2rand0： 5; 1和p3rand0; 0：5，rand a;b是返回a和b之间的实数的函数，其中a和b不包括在内。对于在任何世代g > 1的约束优化问题，三个随机选择的向量的锦标赛选择和分配权重遵循可能存在于世代中的以下三种场景之一。不失一般性，我们只考虑最小化问题：场景1：如果三个随机选择的向量是可行的，则根据其目标将其升序选择为[0，2]中的值F的值对探索有相当大的影响：F的小值导致过早收敛。此外，它可以导致加速收敛，并且高值会减慢搜索[36]。本文对变异方程中的差向量进行了改进。（11），可以看出，它是整个群体中从最差向量到最好向量的有向差向量。因此，F必须是正值，以便将所有试验向量的搜索方向偏向同一方向。因此，F被引入为（0，1]内的均匀随机变量。而不是保持F不变函数值并将w1，w2，w3赋给xGG更好 和在搜索过程中，F被设置为随机变量，G最糟糕，分别。每个试验向量，以便通过以下方式扰动随机基向量：场景2：如果三个随机选择的向量是不可见的，则根据它们的概念将它们按升序排序。约束违规（CV）值并将w1、w2、w3分配给xG，不同的定向权重。因此，新的定向突变类似于梯度的概念，因为差异向量是从最差向量到最佳向量[37，38]。G更好G最糟糕，分别。场景3：如果三个随机选择的向量是混合的（可行的和不可行的），则通过使用三个标准对向量进行排序：（a）在不可行解之前对可行向量进行排序，（b）根据其目标函数值对可行解进行排序，以及（c）根据其约束违反对不可行解进行排序。因此，将w1，w2，w3赋值为4.3. 等式约束法对于由一组约束限制的任何可行域，如果这些约束之一由等式表示，则可行域变为线段。此外，如果所有这些限制是等式约束，则可行域缩小G最好G更好G最糟糕，分别。 显然，从突变到一个点，即所有约束的交点。在那里-等式（11）和（13），可以观察到，目标函数值和约束违反的变异方案有两个好处。首先，变异的扰动部分由三角形的三条边在三个随机选择的向量中的最佳向量的方向上形成因此，所提出的突变中的定向扰动类似于梯度的概念，因为差异向量从最差向量到最佳向量定向[36]。因此，它是相当多的用于探索景观的目标函数被优化在不同的子区域周围的最佳向量在约束的搜索空间内通过优化过程。其次，凸组合向量x<$G是三个随机选择的向量的加权和，其中最佳向量具有最高贡献。因此，x<$G受到最佳向量的影响和偏置比其余两个向量更大。因此，如果所有向量除了遵循随机选择的向量中最差向量的相反方向之外还遵循最佳向量的方向，则事实上，新的突变过程利用了附近因此，虽然等式约束被转换成形式hj！x-e60其中e是允许的容限（非常小的值），但与搜索空间相比，它仍然使得可行区域非常小，这加剧了使用任何进化算法来找到可行解的优化过程。因此，公差值越大，找到的可行解越可靠[28，39]。换句话说，在可行空间的临时增加过程中，搜索过程的初始代将有一些可行个体从优化过程开始。然后，通过减小容差值（e）来缩小搜索空间，使原可行解适应新的可行域并满足新的等式约束。因此，为了处理等式约束，研究人员引入了一种新的方法，通过几代人动态地改变（e）的值。公差值（e）通过使用以下数学表达式进行调整并逐代降低：，x和xGG，xXX和xX，x和x更好最糟糕80A.W. 穆罕默德>>>8>>：4;0：806G=GEN61：00<¼ð Þ¼-1\f2ω log104=log1010; 0： 006G=GEN 0： 05<-1\f25ω log103=log1010; 0： 056G=GEN 0： 10<-1\f25ω log102 =log1010; 0： 106G=GEN 0： 15<系数-1ωlog101=log1010; 0： 156G=GEN 0： 20<1;0： 206G=GEN 0：40<2;0： 406G=GEN 0：60<3;0： 606G=GEN 0：80<ð14Þ其中et10-因子，G是当前代数，GEN是最大代数。从上述表达式可以很容易地得出，随着G=GEN向1增加，公差值et从4减小到10 - 104，并在以后的世代中保持不变。换句话说，当G=GEN增加时，加宽的可行域显著地收缩到真正的可行域。实际上，随着等式约束的数量增加，初始容差在创建合适的初始可行区域时也具有显著影响，该初始可行区域可能吸引太多的不可行点，这些不可行点可以通过代来改进以成为可行的。此外，如前所述，可以观察到，可行空间在搜索过程的初始20%的总代期间以总代的5%的恒定速率快速减小。为了去除不适当的解并保持实际最优值，在剩余的代数中，可行DESP的描述如图所示。 二、5. 问题定义本节分为两个小节;在第1节中，给出了LSFPPs的问题表述，在第2节中给出了具有两个测试示例的多目标SP问题的一般模型。5.1. 线性随机分式规划模型线性随机分式规划（LSFP）问题涉及优化服从某些约束的两个线性函数的比率，其中至少一个问题数据本质上是随机的，对变量具有非负约束此外，一些约束可能是决定性的[40]。LSFP框架试图模拟不确定性图2DESP算法描述。>>>求解随机规划问题81XIJ我þ þ þþXX--þ þþx2S1231123DyXbytx6b1P1-p1;i1 2;. . . ;m;15000q222tx6b2;i¼m1;. . . ;h16x1x2x363： 16;5x1 3x2 4x3615;x1;x2;x3;k1;k2;k3P0：1211221232019-01- 2401：28：28x1x263;12X��123通过假设输入或输入的一部分由概率分布指定，而不是确定性的。当所研究的数据是随机的时，多个函数比之和的优化问题称为随机概率分式规划和（SSFP）问题。下一节给出了SSFP问题的一般模型。随机SSFP问题的数学模型可以表示如下[19]：K最大RXR y=X;受制于：a11x1a12x2a13x36b1;a31x1a32x2a33x3620;x1x 2x 36b 3;5x1 3x2 4x3615;x1;x2;x3P 0上述问题的确定性模型可以给出如下：最大Fxk1k2k3受制于：ðkþ2kþ 4k-17Þxþ ðkþkþk-19ÞxNXa2017年12月27日，第二届中国国际汽车工业展览会在北京举行，中国国际汽车工业展览会在北京举行。其中，Ry= 1，2，.. . ，k.q第1章：6452012年12月20日，在第二次世界大战期间，以色列占领军占领了黎巴嫩南部，并占领了黎巴嫩南部。受制于：. Xn！231100x100232233我的天j1IJJ我第1章：6450： 5x10： 25x2 0：5x30： 256 12;q2019-01-26 01：28：28j1x20： 5x2 0： 75x26 20;其中0 6 Xn×11 ×x j R n是可行集，R：R n！ R n，测试实施例3（SSFP 3）Tm×n 我是说，2最大RXcy1x1cy2x2ayb1m×1b2我是一个.. . . ;m; j;1;2;. . . ;n;b约2立方米1; . . ;h;a;b是标量：y¼1dy1x1dy2x2by根据：a11x1a12x2a13x3627; 5x1 3x2 x36 12;x1;x2;x3P0：上述问题的确定性模型可以给出h-m1m×1nNy Xj1我cyj xj和DyXnj¼1yydyjx j如下所示最大Fxk1k2受制于：在这个模型中，Ny<$X<$;Dy<$X<$;T和b<$1<$中至少有一个可以是随机变量。S={X}等式（15）和（16），X P 0，X<$R n}非空，20-2k14k2x116-3k1-2k2x212-5k1-2k210k1 12k2-1：28qk2k210x2k224x23k225x2 P3;测试实施例1（SSFP1）2019 - 05 - 2200：00：00 00：00 00：00 00 00：00 0000：00 00 00：00 00：00 00 00：00 00 00：00 0000：0000 00 00 00：00 00 00 00：00 00 00 00：00 00 00 0000：0000 00 00 00：0000 00 00 00：00 00 0000000X2cy1x1cy2x2ayx1;x2;x3;k1;k2P0：1 2 3y¼1dy1x 1dy 2x 2by受：a11x1a12x261;a21x1a22x26b2; 16x1x264;x1;x2P0：上述问题的确定性模型可以给出如下：最大Fxk1k2受制于：你好，有关上述示例的更多详细信息，请参阅[19]。5.2. 多目标随机线性规划模型本研究中使用的MOSLP问题的数学模型在下面的小节中给出。约束MOSLP的一般数学模型可以给出为[20]：XnJ电话：+86-21-5555555传真：+86-21- 55555555q22最大化zk¼受j1 c k x j; k ¼ 1; 2;.. . ; k2019 - 01 -22 00：00：00 2019 - 01 - 2200：00 2019 - 01 - 22 00：00 2019 -01 - 22 00：00 2019 - 01 - 22 00：002019 - 01 - 22 00：00 2019 - 01 - 2200：00 2019- 01 - 22 00：00 2019 - 01 - 22 00：00 2019 - 01 - 22 00：00 2019 - 01：002 0 1 9-0 1 ： 0 02 0 1 9- 0 1 ： 0 02 0 1 9- 0 1 ： 00 2019 - 01：00：00 2019 -01：00：00 2019 - 01：00：00. XnXnXn！最大RXy¼12p凸紧集。a 2 jx j6b 2;. ;amj xj6bm;82A.W. 穆罕默德a1jxj6b 1;dy1x 1dy 2x 2by0：84qj1j1j11 2PP;x jP 0;j 1; 2;.. . ; n：测试实施例2（SSFP2）其中0