文摘

精英量子行为粒子群优化(EQPSO)算法,在精英策略是对全球最好的粒子群的防止过早收敛。EQPSO算法用于求解二层多目标规划问题(BLMPP)在这项研究中,它从来没有在其他文献报道。最后,我们使用八个不同的测试问题来衡量和评估算法,包括低维度和高维度BLMPPs,以及尝试解决理论上的帕累托最优的BLMPPs前是未知的。实验结果表明,该算法是可行的和有效的方法解决BLMPPs。

1。介绍

二层规划问题(BLPP)出现在各种各样的科学和工程应用中包括最优控制、流程优化,游戏的战略发展,交通问题,等等。因此,BLPP已经被许多学者开发和研究。专著,评论和调查BLPP可以参考(1- - - - - -11]。此外,进化算法解决BLPP (EAs)曾在论文[12- - - - - -16]。

广泛存在的多目标特征BLPP,二层多目标规划问题(BLMPP)吸引了许多研究人员对其进行研究。例如,史和夏17,18],Abo-Sinna和Baky [19],Nishizaki和Sakawa [20.),郑et al。21]提出了BLMPP的交互式算法。Eichfelder [22)提出了一个求解非线性耦合问题高层的二层多目标最优化问题的约束。此后,Eichfelder [23)开发了一种数值方法来求解非线性二层多目标优化问题。近年来,metaheuristic BLMPP作为替代方法引起了相当大的关注。例如,Deb和Sinha24- - - - - -26],以及Sinha和Deb [27]BLMPP讨论基于进化多目标优化原则。基于这些研究,Deb和Sinha28)提出了一个可行的和基于混合evolutionary-local-search算法和具有挑战性的测试问题。Sinha [29日)提出了一个逐步BLMPP交互式进化多目标优化方法。

粒子群优化(PSO)是一个相对新颖的启发式算法编排的启发,一只鸟,被发现是非常成功的在各种各样的优化任务30.]。由于其高收敛速度和相对简单,PSO算法解决BLPPs已被许多研究人员使用。例如,李et al。31日解决BLPP]提出了一种分层算法。郭和黄32]运用PSO算法求解二层线性规划问题。高et al。33)提出了一个方法来解决供应链使用PSO上下两层的定价问题。然而,值得注意的是,上面提到的论文只求解单目标问题和BLMPP使用PSO迄今为止很少被研究。这种情况可能有两个原因。原因之一是,增加的复杂性与解决每一层,另一个原因是,无法保证算法的全局收敛性(34]。

本文提出了一种全局收敛性保证方法称为EQPSO,施加一个精英策略的全球最佳粒子群的防止过早收敛。EQPSO是用于解决BLMPP在这项研究中,没有在其他文献报道。对于这样的问题,该算法直接模拟了二层规划的决策过程,它不同于大多数传统算法设计的特定版本或基于特定的假设。BLMPP转换来解决多目标优化问题在高层和低层EQPSO交互。和一组近似BLMPP帕累托最优解决方案利用精英策略。这个互动过程反复进行,直到找到准确的原始问题的帕累托最优解。剩下的纸是组织如下。节2,提供问题公式化。该算法求解二层多目标问题提出了部分3。节4给出了一些数值例子,说明了该算法的可行性和有效性。

2。问题公式化

让,,,,。的一般模型BLMPP可以写成: 在哪里和上层和下层目标函数,分别。和表示上层和低水平约束,分别。

让,,,和固定的,让表示弱效率的解决低层次的问题,问题的可行解集(2.1)被表示为:。

定义2.1。对于一个固定的,如果是一个帕累托最优解较低水平的问题,然后呢是一个可行的解决问题的办法(2.1)。

定义2.2。如果是一个可行的解决问题的办法(2.1),没有,这样,然后是一个帕累托最优解的问题(2.1),“”表示帕累托的偏好。

对于问题(2.1指出),这是一个解决方案是可行的,当且仅当上层问题是一个下层问题的最优解决方案。在实践中,我们常常使近似低层次问题的帕累托最优解的最优响应反馈到上层问题,这通常的观点被接受。基于这一事实,EQPSO算法求解BLMPP可能有巨大的潜力。另一方面,与传统的逐点详述的方法中提到的部分1,EQPSO算法使用一组点的操作,因此,EQPSO可以开发作为解决BLMPP新方法。我们下一个算法基于EQPSO提出(2.1)。

3所示。该算法

3.1。的EQPSO

量子行为粒子群优化(QPSO)算法的集成和量子计算理论的发展,35- - - - - -38]。与PSO相比,它不需要速度矢量对粒子和更少的参数调整。此外,它可以保证全局收敛性(39]。由于其全局收敛性和相对简单,它被发现是非常成功的在各种各样的优化任务。例如,一个广泛的连续优化问题(40- - - - - -45)解决了QPSO算法,实验结果表明,QPSO比标准算法更有效。一些改进QPSO算法可以参考(46- - - - - -48]。摘要EQPSO算法,其中一个精英策略是对全球最好的粒子,防止过早收敛群,这使得该算法具有良好的性能BLMPPS解决高维度。EQPSO具有相同的设计原则和QPSO除了全局最优粒子的选择标准,因此,全局收敛性的证明EQPSO可以参考(39]。EQPSO,粒子根据以下迭代方程: 在哪里 在哪里表示粒子的位置。表示的意思是最佳位置的所有粒子的最佳位置。的,,均匀分布随机数,分别。是expansion-contraction系数。一般来说,,是当前迭代数,然后呢是迭代的最大数量。的和粒子的个人最佳位置和全球最佳位置,分别。是精英集介绍了以下部分(见算法:步骤3)。

3.2。该算法为解决BLMPP

该算法求解BLMPP的过程是一个互动的共同进化的过程。我们首先初始化种群,然后解决多目标优化问题在高层和低层使用EQPSO交互。一次的迭代中,一组近似的帕累托最优解决方案问题1是采用精英策略,获得的Deb et al。49]。这个互动过程反复进行,直到准确的帕累托最优解的问题(2.1)被发现。给出了该算法的细节如下。

算法
步骤1。初始化。
步骤1.1。初始化种群与这是由粒子subswarms大小每一个。的粒子的位置()subswarm提出:(),随机采样的可行空间。
步骤1.2。初始化外部循环计数器。
步骤2。为subswarm (),每个粒子分配nondomination等级和一个拥挤的价值在空间。然后,所有导致subswarms结合成一个人口命名的。后来,每个粒子被赋予一个nondomination等级和一个拥挤的价值在空间。
步骤3。nondomination粒子分配和从保存在精英吗。
步骤4。为subswarm ()、更新决策变量的低水平。
步骤4.1。初始化循环计数器的低水平。
步骤4.2。更新()粒子的位置固定根据(3.1)和(3.2)。
步骤4.3。 。
步骤4.4。如果请转到步骤4.5。否则,转到步骤4.2
步骤4.5。每个粒子的subswarm nondomination等级重新分配和一个拥挤的价值在空间。然后,所有导致subswarms结合成一个人口重命名为。后来,每个粒子重新分配nondomination等级和一个拥挤的价值在空间。
步骤5。结合人口和形成。合并后的人口重新分配是nondomination排名吗,粒子在一个相同的nondomination等级分配拥挤距离值在空间。
步骤6。选择一半粒子从。粒子的排名被认为是第一位的。粒子的等级的粒子指出的顺序一个接一个地减少拥挤距离,对于每一次这样的粒子相应subswarm人口(无论是从其来源或)复制在人群中间。如果一个subswarm已经复制和未来的粒子从同一subswarm发现再次,subswarm不是复制。当所有的粒子被认为是,类似的考虑是继续直到完全等等subswarms复制在。
步骤7。更新精英组。nondomination粒子分配和从保存在精英吗。
步骤8。更新的上层决策变量。
步骤8.1。发起上层循环计数器。
步骤8.2。更新()粒子的位置固定根据(3.1)和(3.2)。
步骤8.3。 。
步骤8.4。如果请转到步骤8.5。否则,转到步骤8.2。
步骤8.5。每一个成员被分配一个nondomination等级和拥挤距离值在空间。
步骤9。 。
第十步。如果、输出精英集。否则,转到第2步。

在步骤4和8中,全球精英的最佳位置是随机选取的。个人最佳位置选择的标准是,如果当前位置是由前面的位置,然后前面的位置保存;否则,当前位置取代了前一个;如果他们都不是由其他,然后随机选择其中一个。一个相对简单的方案是用于处理约束条件。只要两个人比较,检查约束。如果两者都是可行的,nondomination排序技术直接应用于决定选择哪一个。如果一个人是可行的,另一种是不可行,可行的主导。如果两者都不可行,那么最低数量的约束违反占主导地位。算法中使用的符号是详细的表1。

4所示。数值实验

在本节中,三个例子将被认为是对问题(说明该算法的可行性2.1)。为了评估之间的亲密关系得到帕累托最优和帕累托最优理论战线面前,以及得到帕累托最优解的多样性以及帕累托最优理论方面,我们采用了以下评价指标。

4.1。绩效评价指标

(一)代距离():这个指标使用Deb [50)采用本文的评估之间的亲密关系获得帕累托最优和帕累托最优理论战线前面。的度量表示之间的平均距离得到帕累托最优和帕累托最优理论面前前: 在哪里的数量获得帕累托最优解的算法吗是每一个获得了帕累托最优解之间的欧氏距离和最近的帕累托最优理论组的成员。

(b)间距():该指标用于评价的多样性得到帕累托最优解进行比较均匀分布和偏差的解决方案如黛比所述50]: 在哪里,,的意思是,是极端的解决方案之间的欧几里得距离得到帕累托最优解集和理论中的帕累托最优解集的目标,是上层目标函数的数量,然后呢是由该算法得到的解决方案。

取得了所有的结果提出了在个人计算机(CPU: AMD表征群2 X6 1055 t 2.80 GHz;内存:3.25 GB)使用c#实现的算法。

4.2。数值例子

4.2.1。准备低维BLMPPs

例4.1。例子4.1是来自22]。在这里。在这个例子中,人口规模和迭代时间设置如下:,,,,:
图1显示了得到帕累托面前这个例子的算法。从图1,可以看出得到帕累托面前非常接近帕累托最优理论方面,和之间的平均距离得到帕累托最优和帕累托最优理论面前面前,也就是说,(见表2)。此外,较低的值(,见表2)表明,该算法能够获得一个良好的解决方案对整个分布范围的理论帕累托最优。图2这个例子显示了获得解决方案,遵循的关系,也就是说,,和。同样清楚的是,所有获得解决方案接近上层约束边界()。

例4.2。例子4.2是来自51]。在这里。在这个例子中,人口规模和迭代时间设置如下:,,,,:
图3显示了这个示例面前得到帕累托最优的算法。从图3,很明显,得到帕累托最优面前非常接近帕累托最优理论方面,之间的平均距离得到帕累托最优和帕累托最优理论面前面前是0.00003(见表2)。另一方面,得到帕累托最优解决方案可以分配在整个范围的帕累托最优理论方面统一基础上的事实价值较低(,见表2)。图4显示了得到帕累托最优解,它们遵循的关系,也就是说,和。

4.2.2。高维度BLMPPs

例4.3。例子4.3是来自28]。在这里。在这个例子中,人口规模和迭代时间设置如下:,,,,:

例4.4。例子4.4是来自28]。在这里。在这个例子中,人口规模和迭代时间设置如下:,,,。 在哪里
这个问题是更加困难比前一问题(例子4.1和4.2),因为这个例子的低级问题具有多峰性,从而使低水平的问题很难找到上层帕累托最优。从图5,可以看出得到帕累托面前非常接近帕累托最优理论方面,和之间的平均距离得到帕累托最优和帕累托最优理论面前面前,也就是说,(见表2)。此外,较低的值(,见表2)表明,该算法能够获得一个良好的解决方案对整个分布范围的理论帕累托最优。此外,两个帕累托最优方面给出当获得更低的水平和。

图6显示了得到帕累托前面的例子4.4该算法。上层问题多峰性,造成一种算法很难找到上层帕累托最优。从图6,可以看出得到帕累托面前非常接近帕累托最优理论方面,和之间的平均距离得到帕累托最优和帕累托最优理论面前面前,也就是说,(见表2)。此外,较低的值(,见表2)表明,该算法能够获得一个良好的解决方案对整个分布范围的理论帕累托最优。此外,所有相应的低水平帕累托最优的方面。

例4.5。例子4.5是来自28]。在这里。在这个例子中,人口规模和迭代时间设置如下:,,,:

例4.6。例子4.6是来自28]。在这里。在这个例子中,人口规模和迭代时间设置如下:,,,:
图7显示了得到帕累托前面的例子4.5该算法。从图7,可以看出得到帕累托面前非常接近帕累托最优理论方面,和之间的平均距离得到帕累托最优和帕累托最优理论面前面前,也就是说,(见表2)。此外,较低的值(,见表2)表明,该算法能够获得一个良好的解决方案对整个分布范围的理论帕累托最优。此外,所有获得低级帕累托最优的方面。同样清楚的是,帕累托最优方面较低和上层躺在约束边界和每一个低层次的帕累托最优的前面都有一个不平等的贡献上层帕累托最优。
图8显示了得到帕累托前面的例子4.6该算法。从图8,可以看出得到帕累托面前非常接近帕累托最优理论方面,和之间的平均距离得到帕累托最优和帕累托最优理论面前面前,也就是说,(见表2)。此外,较低的值(,见表2)表明,该算法能够获得一个良好的解决方案对整个分布范围的理论帕累托最优。此外,三个帕累托最优方面给出当获得较低的水平,和。可以看出,只有一个帕累托最优点从每个参与低级别问题限定在上层帕累托最优。

4.2.3。BLMPPs与未知的帕累托最优理论方面

例4.7。例子4.7是来自52),帕累托最优理论没有得到前面。在这里。在这个例子中,人口规模和迭代时间设置如下:,,,:

例4.8。例子4.8是来自23]。在这里。在这个例子中,人口规模和迭代时间设置如下:,,:
图9显示了得到帕累托最优前面的例子4.7该算法。注意,Zhang et al。52只获得一个最优解和是最大的使用加权和的方法。相比之下,一组得到帕累托最优解的算法。然而,一个最优解(49)包含在得到帕累托最优解说明了算法的可行性。图10显示了最终归档解决方案的例子4.8该算法。对于这个问题,确切的帕累托最优的前面是未知的,但获得了帕累托最优算法类似于前面的报道在前面研究[23]。

5。结论

本文提出EQPSO,施加一个精英策略的全球最佳粒子防止群集群,使粒子逃离当地的最适条件。EQPSO算法用于求解二层多目标规划问题(BLMPP)第一次。在这项研究中,一些数值例子是用来探索该算法的可行性和有效性。帕累托前面获得的实验结果表明,该算法是非常接近帕累托最优理论方面,和解决方案也均匀分布在整个范围的理论帕累托最优。该算法简单,容易实现,为进一步研究提供另一个吸引人的方法在BLMPP。

确认

作者感谢裁判和副主编的洞察力和相关的评论。这项工作是由美国国家科学基金会支持的中国(71171150,71171150,71171150,61273179,11201039,20101304),学术奖优秀博士候选人由武汉大学和中央大学(基础研究基金。201120102020004),武汉大学的博士短期流动性计划。