文摘

实际的多目标优化问题的特点是多种类型的决策变量。在本文中,我们解决武器选择和规划问题(WSPPs),其中包括武器种类选择的决策变量和武器数量的决心。大型解决方案空间不连续、非凸帕累托前增加解决问题的难度。本文解决了解决问题通过一个基于分解的多目标进化算法(MOEA / D)。两种机制设计的复杂组合WSPPs的特征。首先,每个划分的小区选择和替换的社区。第二,社区大小变化在通过引入进化距离参数限制每个子问题的搜索范围。该算法与基于距离称为MOEA / D /社区(MOEA / D-DDNs)可克服可能的原始缺陷MOEA / D与加权和方法对于复杂组合问题。基准生成实例来验证该方法。实验结果表明该算法的有效性。

1。介绍

投资组合优化问题和项目规划问题是两个领域的经典主题运筹学和管理科学。许多行业的优化问题,经济学,和生产可以建模为投资组合问题或计划和调度问题。例如,在国防规划领域,大多数国家都重视基于权力规划(CBP)从本世纪初1]。CBP通常涉及新型武器的发展未来的功能实现。通过预算有限,决策者需要平衡不同目标之间的诸如成本、效率和风险(2- - - - - -4]。

在CBP的过程中,决策者需要决定“购买”和“何时买,”对应的概念组合和项目计划。然而,在现有的文献,投资组合问题和项目计划问题是两个相对独立的分支。前者侧重于项目中选择可用的集合,而后者关注活动安排的时间范围。同时考虑这两种类型的优化过程,而很少在文献中。在先前的研究中,CBP武器发展的基本优化过程建模作为武器选择和规划问题(WSPP) [5]。

在这篇文章中,我们完善WSPP模型和关注的设计有效的多目标进化算法来解决这个问题。本文的主要贡献是双重的:(1)本文改进WSPPs的多目标优化模型。WSPP的主要特征之一是每个武器装备都有自己的服务。这是一个主要区别WSPPs和其他计划和调度问题。以前的工作没有考虑这个属性(5]。武器装备效果只在他们的服务时间。解决方案有效性的计算需要考虑每个单元的开始点和结束点的武器装备。因此,解决方案评估变得更加昂贵。因此,将服务的属性,从根本上说,变化的结构问题,增加了问题的复杂性。在提出的模型中,同时考虑解决方案的有效性和风险为决策者提供重要的权衡。为了说明解决问题,我们生成三套测试问题包括与不同尺度15实例。(2)WSPP是离散的决策空间,帕累托前面是不连续和凸。因此,多目标进化算法(MOEAs)是首选的解决问题。尽管经典MOEAs报告和测试在许多基准,MOEAs解决复杂组合问题的表现仍然是开放式问题。我们解决问题的框架基于分解的多目标进化算法(MOEA / D)。MOEA / D,凸的加权和的方法是简单而有效的问题,但性能是有限的,当帕累托方面非凸和/或断开连接。此外,原始MOEA / D的组件,如社区的定义,选择,和替换,可能有问题的组合问题。为了解决这些问题,基于距离划分社区(DDN)的机制设计和纳入MOEA / D。该算法称为MOEA / D-DDN。实验结果表明,DDN机制是有效和MOEA / D-DDN解决WSPPs表现良好。

剩下的纸是组织如下。节2,我们简要回顾文献组合问题和能力规划问题。问题制定和提出MOEA / D-DDN部分中描述3和4,分别。部分5介绍了WSPPs遗传算子。实验结果发表在部分6。最后,一些结论是在部分7。

2。回顾相关的文献

自解决WSPP是投资组合的融合和规划问题,我们简要回顾相关工作在这两个领域在这一节中。

2.1。投资组合优化与进化计算

投资组合问题固有的多目标特征。在实际情况下,由于非凸约束metaheuristic算法进化计算(EC)等优先解决组合问题。Arnone et al。6)是最早尝试应用进化算法来解决这个问题。作者建议应用基因方法的可能性和实现的一些想法。马林和凯勒7]基数约束组合优化设计一个算法结合模拟退火和进化策略。看台(8)提出了一种粒子群优化方法来解决组合优化问题,并将结果与其他metaheuristic方法。虽然上述作品不同的算法应用于投资组合问题,共同的一个特点是,问题转化为单目标优化问题的加权和的方法。

作为MOEAs的发展,近二十年来的成长见证了利用MOEAs求解投资组合问题。Doerner et al。9)研究项目组合的目标利益和剩余资源的问题。作者提出了一个两阶段的过程解决方案的方法,在第一阶段,帕累托蚁群优化是用来确定解决方案空间的有效组合。Branke et al。10)解决组合问题非凸约束将有效集算法集成到MOEA,称为envelope-based MOEA。Pai和米歇尔11)第一次使用k聚类分析则消除基数约束,然后设计了一个与进化策略算法解决组合优化问题的一个子类。Gutjahr et al。12)和Kremmel et al。13解决了项目组合问题。在Gutjahr et al。12),经济和人员能力的好处同时优化。整个问题分解为一个主问题和一个奴隶的问题。作者分别实现NSGA-II [14)和帕累托蚁群优化子问题来解决。Kremmel et al。13专注于软件项目组合问题,多目标优化方法基于原型与进化优化改进措施(mPOEMS)被用来解决这个问题。在Anagnostopoulos说道和Mamanis的研究15),表演不同的MOEAs投资组合问题进行了比较。实验结果表明,表演的力量帕累托进化算法1(SPEA1)和帕累托Envelope-based选择算法(PESA)具有可比性和NSGA-II的比这更好。在后面的研究相同的作者16),表演五MOEAs基数约束的组合优化问题。最近由MOEAs解决组合问题的全面调查,读者被称为Metaxiotis和Liagkouras17)和Ponsich et al。18]。

相对于其他领域,如金融和项目管理,很少有应用程序投资组合优化的国防领域。他一一et al。19]研究了武器系统开发项目的筛选及其现实应用的空军。在研究中,作者提出了一个决策支持方法结合层次分析法(AHP)和0 - 1整数组合优化模型。杨et al。20.)采用启发式算法来处理军事投资资产组合选择问题。Kangaspunta et al。4]研究了武器系统组合问题的武器组合添加剂价值评估的功能。

2.2。计划和调度在国防领域

在国防领域,决定武器采购给定一个时间范围可以称为长期规划问题。阿巴斯et al。21]研究资源规划下时间约束问题的主要任务是优化混合车辆实现未来的任务。作者开发了一个进化多目标的方法,以获得高效的解决方案。Bui et al。22)被认为是军事能力规划问题作为一个资源受限的项目调度和资源的组合投资问题。规划过程建模为一个多目标问题,和一个进化算法旨在解决优化任务。在武器系统的规划,规划方案的有效性通常受到持有的武器。Golany et al。23)关注发展问题的有效对策给予有限的资源。通常,武器采购需要同时考虑选择和规划过程获得整体的最优解。然而,在项目规划和调度领域,文学同时解决这些流程的组合相当缺乏,除了Ghasemzadeh et al。24),太阳和马25),Gutjahr et al。12],Carazo et al。26]。在这些作品中,决策者只需要确定一个项目将被选中。问题解决本文从模型区别现有的工作通过考虑不同的武器类型的数量在每一个决策点。因为武器的发展受到资源约束和解决方案的有效性应衡量考虑所有选择武器,整体水平的问题需要解决。武器的选择过程,同时考虑所选的类型和相应的数量扩张的决策空间,大大增加了问题的复杂性。因此,有必要设计更有效的算法来解决WSPPs。

3所示。武器选择和规划问题

3.1。问题描述

WSPP可以简单地描述为决策者选择武器的过程中,在每一个决策时间点计划他们的发展。规划周期分为米单位和索引 。每个单元表示一个月(12]。有W类型的武器,每个武器类型具有以下属性:(我) :最大可用每种武器的数量(2) :一个单位的成本每个武器类型(3) :一个单位的每个武器类型的值(iv) :一个单位的每个武器类型的风险(v) :的武器从一开始的武器发展的部署武器(vi) :服务期间,每个武器类型

类似于项目组合收入(13),初始值对应于每个单元的武器是pregiven。然而,在我们的研究中,可以被理解为单位时间内速度造成的损害的武器吗在同行23]。不失一般性,我们假设初始武器单位价值和归一化,这样的风险和 。我们假设军事部门向承包商支付任何代价的发展。在每个时间点,决策者需要决定选择的数量为每个武器类型,表示 。然后,为每个武器类型可以选择总额计算 ,和所选武器单位为每个索引的类型从1到 。为一种武器类型 ,选择武器的发展起始时间单位表示为 ;例如,表明开发的起始时间单元2 1型的武器。

在每个时间点,有两个实体需要解决对每个武器类型:(我) :武器的数量正在开发的时间点米(2) :武器的数量在时间点操作米

注意,的值和是由 。例如,我们考虑一个计划与地平线 。让和和 。我们假设这种武器类型的选定的总额 。武器开发单位在第一和第五次点和 。然后,的值和可以得到如下:

WSPP主题如下约束。

3.1.1。最大的每年预算

预算每年为政府提供的武器发展限制和表示 。资本可以在每年的开始。实际花费资金在每年来标示 。类似于Carazo et al。26),我们假设资本不是在前几年可以积累和转移到明年。每年的实际可用资金 。然后,有和 。

3.1.2。最少的操作

解决方案的武器计划,某些类型的武器不能形成战斗力,除非他们有一个相当规模。具体来说,我们使用来表示的最小数量的武器运行在每个时间点,形成战斗力。如果 ,然后武器的效能值在时间点米是0。这个约束是类似的支持阈值(10,27约束在项目组合管理问题。

3.1.3。正在开发的最大数量

正在开发一种武器的最大数量是有限的,因为限制承包商的制造能力。我们使用显示的最大武器单位发展,还有 。

3.2。客观的计算

在本文中,我们专注于解决方案的有效性和风险之间的权衡。

3.2.1之上。计算效率

WSPP解决,需要评估有效性的整体水平在整个规划周期。通常,国防机构打算最大化开发武器的损伤率(23]。类似的武器组合,整体效果与添加剂可以表示值函数(4]。然而,一个简单的附加价值不考虑资产在整个规划过程有效性。在实践中,决策者可能更喜欢一种武器计划可以保持高和稳定的有效性在整个规划周期。因此,在这篇文章中,我们测量的有效性武器计划,每个时间单位的平均效率以及效率在整个计划的偏差。

此外,我们假设值时间单位减少米。在实践中这种假设是合理的,因为武器的有效性将因性能降低或减少发生的对策。我们使用以下公式来捕获这个特点: 在哪里是一个系数来表示的最小单位在规划周期的有效性。我们设置为了计算在这个研究。

然后,在每个时间单位米的有效性是所有武器作为添加剂的有效性值的单位操作: 在哪里如果 ;否则, 。WSPP解决方案的整体有效性,表示 ,可以通过均值-方差模型: 在哪里是在整个规划周期和平均值标准偏差。类似于山下式等。28),参数β是一个方差因素决定的有效性程度不平衡厌恶的决策者。请注意,最大化。

3.2.2。计算的风险

对应于每个武器开发风险被认为是nonincreasing开发时间的函数。具体来说,如果一个武器单元开发计划在稍后的时间点,它所面临的风险将会降低。这是因为技术武器研发的不确定性将降低未来随着新技术的发展。同样,解决方案的整体风险可以通过一个附加价值函数建模的时间因素。在这里,我们使用每个选择的武器单元的平均风险显示解决方案的风险值: 在哪里开发时间开始th单位的武器 。

众所周知,一个多目标问题(MOP)需要不同的目标之间的冲突。在我们的问题中,目标冲突主要来源于单位选择武器的计划。例如,如果一个新武器开发,规划未来的研发活动可以减少失败的风险,因为可能的技术突破。然而,武器的有效性将会降低未来,而当期的武器操作。

3.3。WSPPs多目标优化模型

WSPPs,最大化和要最小化。不失一般性,我们转换问题最小化通过优化负的格式 。模型的多目标优化问题WSPP可以概括如下。

3.3.1。决策变量

对于一个整体解决方案,决策变量 , 。请注意,是一个非负整数的值。

3.3.2。目标

目标和 ,分别代表的最大化有效性和最小化风险武器选择和规划的解决方案。

3.3.3。约束

约束是一个预算限制强加在每年。约束反映出的最大能力发展中每种类型的武器。

4所示。MOEA / D与基于距离划分社区

在这个研究中,我们解决这个问题,基于分解的多目标遗传算法(MOEA / D) [29日]。MOEA拖把/ D分解成一系列子问题的目标函数可以是一个加权线性或非线性的聚合函数。所有子问题的最优解是帕累托最优的一组原始拖把。在MOEA / D,所有标量目标同时优化子问题优化在一个单一的运行。邻里关系中定义的所有子问题是基于他们的重量之间的距离。应该注意的是,各种算法组件MOEA / D的追究性能改善(30.- - - - - -32]。有几种方法来构造一个标量优化功能(32]。为简单起见,本文使用了加权和的方法。

在本节中,我们提出一个基于距离划分社区MOEA / D (ddn)策略。

4.1。动机

首先,我们要精心设计的动机通过以下评论:(1)MOEA / D背后的基本假设是,相邻子问题应该得到类似的最优解。尽管这种假设是合理的对大多数函数优化问题,有一些例外,特别是对于一些组合问题[33,34]。如果帕累托前断开连接或不均匀分布,父母选择以一个恒定的邻居小区的大小子问题可能更低的生成有前途的后代的机会。这是因为个人也不同一般比类似的个人不太可能产生健康的后代通过交配35]。背后的动机非常数的邻居的使用尺寸如下图所示1。(2)在原始MOEA / D,父母从附近的一个随机选择的子问题。然而,父母用不同的统治阶层不同处理的能力产生新的后代,导致收敛和多样性。这是相当精确的早期发展阶段。图2说明了可能的原始选择机制的限制。我们意识到,这种情况下取决于问题本身的特点。然而,对于大多数组合问题,最后的帕累托最优解,而稀疏。对于一个人口相对较大,这种情况在进化过程中并不稀缺。(3)一些变种MOEA / D解决人口替代的策略。另一种是一个新的解决方案可以取代任何其他的整个人口34]。在周和张的研究36),可以提高一个新的解决方案取代了大部分在所有的子问题。(王等人的研究中37),相邻的一个合适的子问题的解决方案替换为一个新的解决方案更好的标量函数值。然而,在两种情况下,一个获得nondominated解决方案可以取代一个劣质的解决方案。第一个是帕累托前凸,第二是每个子问题都有不同的收敛速度。此外,当帕累托前凸,加权和的方法不能很好地工作。这个缺点可以被克服,如果搜索方向的子问题是限制在一个相对狭窄的范围。使用这样一个限制的动机如下图所示3。

4.2。基于距离划分社区的策略

先前的研究表明,使用不同的社区,即。,米ating neighborhood and replacement neighborhood, can achieve better performance for MOEA/D [37,38]。沿着这大道,提出基于距离划分社区(DDN)策略,原始社区(o社区)子问题分为选择社区(年代附近)和替代社区(r附近)。此外,原社区的大小限制,根据pregiven改变搜索范围。DDN策略如图4。

一个解决方案子问题对应我,基本DDN策略如下:(1)决定了年代社区和r社区,分别(2)交配:选择的两种解决方案年代附近的并生成一个新的解决方案通过使用遗传算子(3)更换:更新r附近的通过替换最多n解决方案与糟糕的标量函数值

之前定义年代社区和r社区,我们引入一个参数,d显示子问题的搜索范围。我们首先确定一个参考点 。一个解决方案 ,一条线穿过和可以构造。注意,在这两个目标问题解决的研究,可以另外由线及其相关的权向量。然后,被定义为距离另一个解决方案吗线。计算的距离 ,客观值为每个目标向量归一化,利用获得的每个目标的最大和最小值。解决方案年代社区和r社区,分别定义如下。

定义1。给出一个解决方案 ,一个邻居被称为选择邻居(例如, )如果(1) (2)

定义2。给出一个解决方案 ,一个邻居被称为替代邻居(例如, )如果(1) (2) 。可以看到从上面的两个定义,原来社区受到d根据标量函数和分裂。
在这里,我们做一些评价提出的DDN策略:(1)子问题,DDN战略划分社区年代社区和r社区。子问题的权向量,个人年代附近有更好的标量值函数比r社区。父母的个人选择年代社区将会有一个好机会产生更好的孩子。取代个人只有在r社区可以推动整个人口真正的帕累托前沿,因此增加了收敛能力。(2)个人数字在附近的变化根据每个子问题的搜索范围,控制的参数d。这种限制的好处是双重的:首先,交配可以限制在父个体相似。其次,收敛速度较差的子问题,潜在的良好的个人可以保持人口由于每个子问题只负责一个特定的狭窄的搜索方向。注意,个体的近似nondomination组在搜索过程中,当d接近0,一代孩子个人可以被视为一个本地搜索的过程。(3)参数的使用d有一些相似性约束分解的策略在MOEA / D (MOEA / D-CD) (39]。在王等。研究[39),一个约束施加到每个子问题改善地区限制。然后,子问题,偏序的两种解决方案是重新定义和更换是根据新的优势关系实现的。然而,在MOEA / D-CD,每个子问题的邻域大小是固定的。的同时,提出了DDN策略,社区规模控制的参数d。此外,选择和替换发生在不同地区的限制。(4)在拟议的DDN策略中,年代社区和r社区定义根据标量函数值对应于子问题的权重向量。的年代附近的每个解决方案至少包括本身。在这种情况下,两个父母是相同的,只有变异算子。然而,对于组合问题,几乎是不可能的,所有的子问题有相同的收敛速度。换句话说,在进化,这是不可能的,所有的人在人群中是均匀分布的,在同一在在前面。因此,年代社区可以包含一个以上的个人和它的大小依赖于参数d以及人口分布在不同的进化阶段。在实验分析的趋势年代社区的规模在进化过程中会报道。(5)克服的限制标准MOEA / D解决问题时一个复杂的帕累托面前,一些研究使用的策略自适应权向量调整(40,41]。通过调整权重向量,多样性可以提高算法的性能。提出了DDN战略和权向量调整策略共享相同的动机,即。,解决复杂的多目标优化问题。然而,DDN使用一种不同的机制。DDN策略着重于改善算法的收敛能力,考虑到不规则的帕累托前的财产。DDN策略,将改进算法的收敛能力限制父母当个体交配的不连续区域定位帕累托。而对权向量调整策略,算法得到更好的一致性的解决方案权重的重新分配子问题(40]。(6)我们知道有一些其他类型的标量函数MOEA / D,如Tchebycheff方法和penalty-based边界交点(PBI)方法。对于复杂的拖把,Tchebycheff和PBI方法可能实现更好的性能比加权和方法与原框架MOEA / D。然而,好处是要付出代价的。例如,有确定的参考点Tchebycheff方法和设置PBI的惩罚因子的值的方法。确定最优参数对复杂问题并不是一件容易的事情。拟议中的MOEA / D-DDN提供了另一种解决复杂拖把MOEA / D与最简单的标量函数,即:,加权和的方法。

4.3。MOEA DDN / D

拟议的框架MOEA / D-DDN显示算法2。分解成原来的拖把H标量客观的子问题。

算法MOEA / D规格如下。

4.3.1。新的解决方案生成

有很多方法可以生成一个尝试解MOEA / D。MOEA / D-DDN,审判的解决方案是使用遗传算子产生的两个随机选择的解决方案年代社区。的遗传算子将在以下部分阐述解决问题。

4.3.2。人口替代

MOEA / D及其变体取代人口根据标量的比较客观的价值新生成的解决方案和住在附近的其他人。我们使用相同的替代机制在李和张42];即。,at most ,在附近解决方案可以取代。在MOEA / D-DDN、更换是受限的r每个子问题的社区。

4.3.3。总结MOEA / D-DDN

基于上述讨论,输入MOEA / D-DDN可以概括如下:(我)H:子问题的数量。(2)D:社区的初始大小。(3) ,指数的一组原始相邻的子问题的子问题我,在那里 。(iv)d:搜索范围的距离。(v) :最大数量的解决方案取代了每个孩子的解决方案。(vi) :参考点的集合在目标空间中,可以由一个问题特定的方法。请注意, 。(七)G:一代的数量作为停止准则。(八)在每一代,MOEA / D-DDN加权和方法维护。(第九)人口的H个人 。(x) ,在哪里的健身价值吗 。(十一)外部人口(EP),这是用于存储nondominated搜索中发现的解决方案。

可以看到从上面的讨论,MOEA / D-DDN只有一个额外的参数,即。,搜索范围的距离d。算法的性能与不同的值d将进行实验分析。自提出MOEA / D-DDN不会改变MOEA / D的基本框架,计算复杂度MOEA /原始MOEA / D D-DDN仍然是一样的。

5。基因表达和WSPPs运营商

5.1。染色体表示

在投资组合问题,混合二进制/实值编码基因表达的建议Streichert et al。43)也用于其他作品(10,16]。用这个编码,实值向量用于指示预算的比例在不同资产或项目,而二进制向量用于指示是否选择资产。WSPPs,应该包括染色体表示信息的武器类型,数量,和规划时间。然而,投资组合的混合表示问题不考虑时间范围的因素。问题解决在本研究,我们设计包括两个部分的染色体表示:预算分配和优先级矩阵分别显示为数字5和6。

这两个预算分配和优先级矩阵实值。向量 表明每年预算股票在每个时间单位。优先级矩阵中的元素, ,在哪里 ,是由真正的编码值之间的间隔 。一个较低的值表示一个更高的优先级。初始化的值在间隔是随机生成的 ,和所有的值是nonredundant。例如,给定一个单一类型的武器与6单位,可以生成并表示成染色体 。然后,第二单元的武器将选择第一个如果预算可用。

5.2。解码过程

染色体表示应该解码选择和规划方案评价客观的价值。在每个时间单位,原来的预算是由股票价值决定的 ,在哪里和 。注意,实际可用的预算不同,由于之前的积累不是预算。选择的武器类型和数量是根据优先级决定。给出了解码程序算法1。

注意,解码过程可以确保满足约束条件和在方程中所示的多目标优化问题(7)。我们使用一个简单的例子说明了解码过程。我们考虑一个问题12规划单位(1年)和一个单一类型的武器与6单位。每个武器单元的成本 ,和可用的预算 。预算分配的染色体 ,和优先级矩阵 。然后,有和 。在第一次时候,由于可用预算的约束,只有一个单位的武器选择。具体来说,第二单元选择的武器。然后,我们有和 。在第二次点,可用的预算 。然后,3单位的武器可以选择,即。武器单元5 3和4。在第二个时间点,和 。然后,我们可以获得决策变量的值和 。

5.3。交叉和变异

遗传算法交叉和变异是两个重要的运营商。我们使用BLX -α交叉在Streichert et al。27)因为这交叉执行最好的投资组合问题。的值的两个父母都表示和 ,分别。BLX -α交叉随机重新启动的值从一个扩展范围 ,在哪里 , ,和 。我们设置如Streichert et al。27]。类似的交叉算子用于优先级矩阵。

执行变异算子如下:预算分配名单,每年的突变点是随机决定的。然后,随机生成真正的值在0和1之间,在突变点的值替换。一种武器类型是随机选择和表示 。优先级矩阵中的元素对应于所选择的类型, , ,取而代之的是值随机分布的画吗 。如果一个新生成的值是负的,那么我们设置值 。注意,这个变异算子也类似于Streichert et al。27]决策变量的变异通过添加一个随机高斯数与一个特定的偏移。

6。实验分析

6.1。测试实例的生成

由于没有现有文献地址准确WSPPs,没有基准实例可以用来测试算法。具体说明研究问题和调查MOEA / D-DDN的性能,不同实例是随机生成的。试验台由三组不同大小的实例。表1显示了实例生成的参数。每组包括5个实例和相应的值是统一从给定的时间间隔。测试集之间的主要区别是武器类型的大小。注意,表中的值1是保密的人工的原因。然而,区间值的识别也指的是一些真正的武器选择和规划。具体地说,所有的参数参考数据从2005 - 2015年期间中国军队的管理部门。虽然人工测试实例,结果generalisable真实情况的武器选择和规划未来。

6.2。参数设置

用c#实现的算法。人口规模设置为100,初始邻域大小被设置为20。交叉和变异的利率是细调,确认为0.95和0.9,分别。最大数量的解决方案取代了每个孩子的解决方案是2。该算法是100代后终止。在实验中,所有算法都为每个实例运行独立20次。性能比较,我们进行了统计显著性测试结果的显著性水平 。

6.3。性能指标

类似于大多数组合问题,真正的帕累托前是未知的。因此,我们使用超体积和覆盖性能指标如在柯et al。34]:(1)超体积指标( )(44):让是一个点在目标空间中由任何帕累托最优目标向量。的价值进行近似得到帕累托前区域的体积是由近似和主导 。超体积值越高,越好近似。因为在WSPPs,两个目标有不同的维度,对超体积的计算值归一化。规范化,最大和最小值的目标被确定为0和−25,最大和最小值0.4、0。正常化后,参考点设置为(1,1)在超体积的计算值。注意,如果参考点考虑问题的范围,没有必要规范化的客观价值nondominated解决方案(45]。(2)设置范围(C度量)[44):让一个和B帕累托前面两个近似。 被定义为解决方案的百分比吗B由至少一个解决方案一个。例如, 表明,所有的解决方案B是由一些解决方案吗一个。请注意, 并不一定等于什么 。更高的价值 和一个较低的值的 意味着一个有更好的收敛性能。计算的C度规,复制解决方案中获得nondominated集。

6.4。敏感性分析

提出MOEA / D-DDN,有额外parameter-search距离范围d。我们首先研究了不同的表现d值。超体积的统计分析得到帕累托解表明,大多数情况下没有显著差异。

注意,超体积是归一化相对广泛。这可能影响超体积测量的分析。我们进一步研究了一组报道。我们获得最终nondominated解决方案与20为每个值的参数运行d。一个分数计算如下:

表2分数报告所有测试值的参数d15日实例。一个较低的价值表明较低的比例获得主导解决方案。表中,如果结果与一个特定的值d达到最低的分数,分数值与突出显示大胆的的脸。表中的结果还表明,参数的最优值d随不同的实例。我们的基准测试的参数7在15个实例表现最佳,而数字分别为4、3、1。然后,如果参数d需要所确定的所有实例的值者优先。

6.5。影响算法组件

拟议中的MOEA / D-DDN特点是两种机制:(1)划分社区选择左邻右舍和更换和使用参数(2)d控制社区大小。在本节中,我们研究了上述两种机制的影响。该算法只与划分社区MOEA / D-DivN来标示;即。,the parameterd是放松的。然而,该算法包括参数d基于原始MOEA / D MOEA / D-DisN来标示。我们选择的参数MOEA / D-DisN和MOEA / D-DDN。表3报告结果超体积的三个算法版本,以及原始MOEA / D。为每个实例,最好的价值,平均和标准偏差报告。MOEA / D-DDN获得的价值,如果它是重要的比其他三个算法之一,平均了大胆的的脸。从表3我们可以看到,MOEA / ddn表现最好的所有实例。然而,表演MOEA / D-DivN MOEA / D-DisN, MOEA / D具有可比性。它表明两个算法组件的组合MOEA / D-DDN是有效的解决问题。

6.6。算法动态

与原始MOEA / D相比,主要的区别MOEA / D-DDN在于划分社区的变化。的大小年代社区和r社区在进化过程中不同。在本节中,我们研究了邻域大小对个人的动力。第一次运行的数据例如10被用于分析。我们第一次呈现两种不同模式的社区大小差异。30和96个人在人口中被确认。附近的大小显示为数字7和8,分别。

一般来说,一个较低的价值年代社区可能表示一个人更好的收敛性能,反之亦然。可以看到从图7,30个人的趋势年代附近的大小是随进化。在演化过程的开始,年代邻域大小13岁,而价值仍1算法结束时。这表明30个人的表现不佳nondominated排名在初始种群。然而,这在进化成螺旋形地提高性能。的改变年代社区大小从高值到一个较低的值代表nondominated排名的提高性能。图8展示了一个不同的模式。96个人有一个更好的nondominated排名在初始种群,而性能下降以及进化。图9显示了人口第一、50和100代,表示为点,三角形,分别和明星。30和96人的位置,分别以六边形和循环。第96个人定位在第一nondominated排名在初始种群。然而,它主要是在50和100代。然而,30个人的情况相反。

在这里,一个问题为什么好的解决方案在最初的人口没有导致出现的收敛性能。回想一下,类似于原始MOEA / D, MOEA / D-DDN均匀生成的向量为每个单独的重量,然后人口随机初始化。权向量的整个进化过程中保持不变。可能分配给个人的权向量并不是最合适的一个个人本身。例如,在最初的人口,96个人中间几乎撒谎的人口目标空间。然而,分配的权向量决定第96个人沿着一边搜索方向。换句话说,这种类型的人有较长的路径搜索的目标空间。鉴于均匀分配计算资源,性能可能会更糟。

然后,我们假设的不同部分人群中个体贡献不同的收敛性能。我们选择3组人群中个体。第一组包括前10个人,第二组包括从45到54个人,并设置3由过去的10个人。的年代邻域大小为每个单独的设置在进化,分别报告数据10- - - - - -12。由3套共享一个共同的特征就是变化的频率年代社区规模下降与进化。这表明收敛的人口。通过观察初始种群,一个可以看到的利差年代邻域大小每组是相似的。集1和3,年代社区大小增加的算法对大多数人。然而,大多数人相同的值下降的2。给定一个均匀分布的人口,价值较低年代社区规模通常表示一个更好的价值nondomination排名的一个独立的个体。可能是安全状态,鉴于均匀分配的权向量和随机生成的初始种群,更难把个体位于接近帕累托的结束部分前向真正的帕累托面前。一些作品解决类似的问题。李等人。46)提出了一个稳定的匹配模型选择过程MOEA / D。可以使用这种技术,MOEA的性能/ D-DDN可能更复杂问题的进一步好转。然而,本文关注组合问题的基于距离划分社区的影响。然后,进一步改善MOEA / D-DDN并不认为目前但留在未来的研究。

6.7。进一步的性能比较

MOEA / D和NSGA-II是两个经典的算法解决多目标问题。现有文献表明,MOEA / D优于或执行类似NSGA-II连续和组合多目标问题[29日]。最近,组合分解机制和NSGA-II组件被成功用于解决组合问题[47]。最新研究还建议的有效性NSGA-II为解决类似的调度问题(48- - - - - -50]。因此,在本文中,我们选择NSGA-II作为基线算法进行比较。在本节中,我们的表现相比MOEA / D-DDN NSGA-II以及原始MOEA / D。所有参数都设置为与MOEA / D-DDN相同。图13报告得到帕累托最优解的近似MOEA / D-DDN MOEA / D, NSGA-II所有实例。很明显,MOEA / D-DDN实现最好的结果收敛所有实例。然而,应该注意的是,在某些情况下,NSGA-II表现更好的最大传播,例如,实例1、3、14和15。MOEA / D的表演和NSGA-II收敛和最大传播具有可比性。然后,我们可以得出结论,提出MOEA / D-DDN可以解决解决WSPPs更好,与原始MOEA / D和NSGA-II相比。

7所示。结论

在能力规划区域,决策者面临的问题决定的类型和数量的武器。此外,决策者必须计划何时发展每一单位的武器。这类问题称为武器选择和规划问题(WSPPs)。本文改进了WSPPs的多目标模型。问题是组合,多种类型的决策变量增加问题的复杂性。采用MOEA / D作为基本的优化求解问题。然而,原始MOEA / D与加权和的能力是有限的由于不连续,凸,不规则的帕累托。克服可能的缺点或MOEA / D,两种机制的设计是:(1)将原社区的每一个选择和更换社区和(2)控制社区大小通过约束每个子问题的搜索范围。该算法称为MOEA / D-DDN。附近是除以标量函数值的方法。 An additional parameterd介绍了控制每个子问题的搜索范围。

说明解决问题和调查MOEA的性能/ D-DDN基准实例生成不同尺度。灵敏度分析的d表明最优值d需要确定不同的问题。这可能是一个共同的挑战出现进化算法。这个问题值得在将来的研究中得到解决。两种设计机制的有效性已被调查。MOEA的性能/ D-DDN求解WSPPs与原始MOEA / D和NSGA-II。结果表明,MOEA / D-DDN表现优于其它算法。

目前,各种MOEAs已经开发和应用在不同的领域来解决问题。然而,大多数基准测试是连续问题。的能力和可能的缺点各种MOEAs复杂组合问题仍然未解决的问题。它可能是有趣的在未来的研究来解决这些问题。

数据可用性

论文中使用的数据包括生成基准和结果。所有数据用于支持本研究的发现可以从相应的作者。

的利益冲突

作者宣称没有利益冲突有关的出版。

确认

这项工作得到了国家自然科学基金资助下71501181和71501181。