基于动态进化算法的多阶段备件供应优化决策
王亚东1, 石 全1, 张 芳2, 尤志锋1, 夏 伟1,3
(1. 陆军工程大学石家庄校区装备指挥与管理系, 河北 石家庄 050003; 2. 32178部队科技创新研究中心,北京 100012; 3. 陆军步兵学院石家庄校区机械化步兵系, 河北 石家庄 050003)
摘 要: 由于实际备件保障工作中备件需求以间歇性需求为主,备件供应通常为多阶段的动态优化。针对以上问题,构建了多阶段备件供应数学模型。为求解动态优化模型,提出了一种元启发式动态进化算法。首先,在经典差分进化算法中增加了环境变化检测算子和环境变化响应策略,使得差分进化算法能够解决环境变化的动态优化问题。其次,提出了自适应莱维飞行策略,使得算法在环境发生变化时仍能保持良好的全局搜索能力和局部寻优能力。算例表明,所提出的动态自适应差分算法能够求得模型的最优可行解,且算法的分布性和收敛性均得到了很大的提升。
关键词: 备件供应; 动态优化; 差分进化; 莱维飞行; 自适应
0 引 言
备件供应是备件保障的重要组成部分,它需要根据备件需求和保障单元实际情况,确定参与供应的单元位置、备件的库存以及备件在各单位之间的供应量[1]。由于在实际装备使用和维修过程中,用装分队的备件需求通常为间歇性需求,即备件的需求量为随机变量且需求发生的时间间隔均为离散型[2]。此时,备件供应通常为多阶段的供应问题。
在备件多阶段动态供应决策研究中,文献[3]研究了串件拼修对策下两级维修系统的备件供应和库存分配动态管理模型。文献[4]研究了供应保障体系结构动态变化时的三级备件保障模型,采用分阶段边际算法对备件方案进行优化。文献[5]以供应费用和备件可用度互为优化目标和约束,建立了面向系统优化、基于边际分析算法的备件配置模型,明确了备件动态补充时机。文献[6]针对不同军事任务,研究了带有时间窗的多阶段装甲装备备件携行配置问题。文献[7]研究了需求不定条件下多阶段资源配置优化模型,使用拉格朗日分解法对模型进行求解。文献[8]考虑不同运输路径和供应模式下的备件运输问题,在模型中同时包含了时变和非时变参数。文献[9]研究了“一带一路”网络的时变物流配送流程,提出了一种与马尔可夫链相结合的时空物流交互模型。文献[10]采用改进遗传算法对供应网络周期性路径优化进行研究。
一方面,目前的研究大多为需求响应侧的备件动态优化,很少有文献对环境因素的变化进行考虑。在实际保障中,各阶段的备件需求量是不等的,随着任务阶段的开展,运输费用、供应路线等也在发生变化。因此,动态优化模型的参数是时变的。另一方面,在求解算法上大多使用的是分支定界、动态规划、边际效益法等精确算法,这类算法过分依赖于模型本身,且对于非线性或非凸函数很难求解。此外,部分文献将动态优化模型转化为多个静态优化模型进行求解。这类方法在对下一阶段任务进行优化时没有考虑各个阶段之间的联系。
（二）保温防压 新生仔猪怕冷，常被母猪压死或冻死，适宜于新生仔猪的环境温度是35℃，生后至3日龄可控制在32℃，4～7日龄在30℃～28℃，15～30日龄在26℃～22℃，对新生仔猪的保温是提高哺育率的重要措施。将7日龄的仔猪分别置于环境8.3℃和7.2℃，前者日耗奶量为854 g，后者974 g，环境温度降低，耗奶量增加，代谢效率降低，影响了仔猪的增重。
为解决参数变化的动态优化问题,提出了一种动态自适应差分进化算法。在静态进化优化算法的基础上增加了环境变化检测算子以及环境变化响应策略。当优化问题中的参数发生变化时,能够迅速检测环境的变化,并根据环境变化程度进一步更新种群和进化机制。为保证动态进化算法的优化效率和效果,提出了自适应莱维飞行策略,并使用该算法很好地求解出了动态优化模型的最优可行解。
1 建立模型
1.1 问题描述及假设
步骤 1 变异操作
图1 三级备件供应网络
Fig.1 Three-level spare parts supply network
其各级节点主要功能如下:
供应点由后方仓库组成,储备各类备件并根据需求向下一级仓库进行供应。
中转点主要完成备件的储存和中转任务,接受后方仓库提供的备件并向各需求点进行供应。同时,对剩余的备件进行储存,直至下一阶段的供应开始。
第j 个中转点的开放成本;
需求点通常由各用装单位组成,其备件的需求为间歇性需求,即需求发生的时间为非连续的。另一方面,各阶段的需求量也不相同。
本模型旨在在各阶段开始前,根据备件的需求数量,制定一套多阶段动态供应方案。以最小的成本向各需求点供应备件满足各阶段的需求。该方案最终需要确定开放哪些中转点,以及各节点之间供应备件的具体数量,属于选址-分配联合优化问题。
本文多阶段备件供应模型建立在以下假设之上:①以某一类可修复关键备件为研究对象;②各阶段节点之间的备件运输成本均为已知,不同阶段各不相同,各节点之间运力充足;③中转点的开放费用、库存费用、最大储备量均为已知,且不随时间变化;④各阶段需求点的备件需求量和维修成本已知,不同阶段各不相同;⑤需求点有部分维修能力,备件修复率已知;⑥暂不考虑越级供应以及同级之间的横向供应。
1.2 参数说明
I :供应点的数量,i =1,2,…,I ;
从已有的文献中发现，影响主观幸福感的因素较多，综合考虑各因素的影响贡献之后，本文确定了8个解释变量：健康状况(包括：非常好；好；一般；不好；非常不好)、疾病、婚姻状况(包括已婚、未婚、离异、丧偶)、受教育程度(包括小学及以下、初中、高中、大专、大学及以上)、工作状态、性别、年龄(控制在21～65周岁)、对数收入、省份变量。各变量的具体统计性描述见表1。
(1) 变异算子
K :需求点的数量,k =1,2,…,K ;
2)煤矿安全问题推理解释系统(断)：针对状况评估打分的结果，基于专家知识库对发现的问题进行分析和解释，给出原因及处理措施。
第t 阶段,备件由第i 个供应点向第j 个中转点供应备件的运输成本;
第t 阶段,备件由第j 个中转点向第k 个需求点供应备件的运输成本;
结合实际情况,根据任务需要可能无须开放全部中转点。图1中实线表示开放的节点,虚线表示未开放的节点,如“中转点3”。当某一阶段中转点未开放时,其备件流入量和输出量均为0。备件供应方案需要确定哪些中转点开放,哪些中转点处于关闭状态。
第j 个中转点的单位备件库存成本;
第t 阶段,需求点k 的单位备件维修成本;
第t 阶段,需求点k 包含的该类备件的数量;
U j :该关键备件在第j 个中转点的最大储备量;
θ k :需求点k 的备件修复率。
决策变量:
第t 阶段,由第i 个供应点向第j 个中转点供应备件的数量;
第t 阶段,由第j 个中转点向第k 个需求点供应备件的数量;
二进制变量,用来标注中转点j 在第t 阶段的开放情况。
表示开放,
表示关闭。
1.3 模型及解释
优化模型的目标函数要求保证备件供应总成本最小。即
(1)
式中,
表示中转点的开放成本;
表示备件供应的运输成本;
表示备件在中转点的库存成本;
表示备件维修成本。各项成本计算如下:
(2)
(3)
(4)
(5)
模型满足约束条件如下:
s.t.
(6)
(7)
(8)
(9)
(10)
(11)
(12)
(13)
式中,P 0∈[0,1]为初始飞行概率;max_ itert 表示第t 阶段的最大迭代次数;itert 表示算法在第t 阶段的当前迭代次数;iter为整个算法的当前迭代次数。
2 动态进化算法
以上备件供应优化模型的目标函数和约束中存在随时间变化的参数,属于动态优化问题。优化过程中参数的改变会导致优化环境发生变化,当环境变化后优化问题的最优解会发生迁移,上一环境中求得的最优解不再适用于新的环境。因此动态优化算法要能够敏捷地检测到环境变化,并尽快找到每个动态环境下的最优解[11]。
差分进化算法作为一种元启发式智能优化算法,目前已广泛应用于各类静态单目标和多目标优化问题[12]。为求解所提出的备件供应动态优化模型,对差分进化算法进行改进,提出了动态自适应差分进化算法(dynamic self-adaptive differential evolutionary algorithm,DSAEA)。一方面,可以对动态优化中的环境变化进行检测和及时响应;另一方面,提升了差分进化算法在环境变化时的全局探索能力和局部开发能力,提高算法收敛速度的同时防止算法过早收敛而陷入局部最优。
2.1 算法框架
动态自适应差分进化算法在静态差分算法的基础上增加了环境变化检测算子、环境变化响应策略。并对传统差分进化算法的变异策略和选择策略进行了改进。DSAEA算法的伪代码如下:
下面分别对算法的个体的编码方式、适应度值函数计算、环境变化检测算子、环境变化响应策略以及差分进化寻优过程进行介绍。
2.2 适应度函数
由于所构建的动态优化模型属于带约束的优化问题。一方面,模型的最优解应当满足所有约束,在此基础上保证目标函数最小；另一方面，在寻优过程中,最优解可能出现在可行域边界或不可行域,通常在寻优的初期为了实现全局探索而需要利用部分不可行解的信息[13]。因此,在优化之前需要对模型进行无约束处理。目前常见的约束处理方法有罚函数法、基于可行规则的方法、基于多目标的方法等[14]。基于可行规则的方法需要制定合理的规则,用来在目标值和约束违反度之间进行权衡。而基于多目标的方法将约束转化为目标,大大增加了求解的难度。罚函数法作为最常见的方法,具有可行性高和易于理解等特点。罚函数法又包括定常罚函数法[15]、动态罚函数法[16]以及自适应罚函数法[17]。本文采用自适应罚函数法进行无约束化处理,将带约束优化问题转化为无约束优化问题,进而利用差分进化算法进行求解。
Analysis of current situation of safety evaluation of fragrance compounds in cosmetics in China 3 6
定义适应度函数由目标函数和惩罚项组成，适应度函数可表示为
f (x )=C (x )+M ·P (x )
(14)
式中,f (x )表示适应度函数;C (x )为模型的目标函数;M 为惩罚因子;P (x )为模型的约束违反度;x 为个体向量。
定义模型的约束违反度
(15)
式中,对于不等式约束c j (x )=max(0,g j (x )),g j (x )≤0为模型中第j 个不等式约束;对于等式约束有c j (x )=max(0,|h j (x )-ε |),h j (x )=0为模型中第j 个等式约束,ε 为一个很小的实数。
凡音乐材料来自级音的单节型过腔，即为单节型级音性过腔。如“昆南”阳去声字“恁”的唱调（《烂柯山·痴梦》【渔灯儿】“忒恁唓嗻”，722），该单字唱调的过腔是。该过腔的音乐材料来自级音，故谓单节型级音性过腔。
为了保证寻优过程前期的全局探索能力,以及后期最优解的可行性,定义M 为
(16)
式中,M 0为较大的常数;itert 表示第t 阶段的迭代次数;max_ itert 表示第t 阶段的最大迭代次数。可以看出随着迭代次数的增加,惩罚力度逐渐加大。
2.3 编码方式
在每个染色体个体上采用实数和二进制混合编码的方式。结合备件供应动态优化模型,令x =(x 1,x 2,…,x D )为一个染色体个体向量,则其编码方式如图2所示。其中,x 1～x i×j +j ×k 为实数编码,x i×j +j ×k +1～x i×j +j ×k +j 为二进制数编码。图2中的i 、j 和k 为对应模型中供应点、中转点和需求点。
图2 染色体个体编码方式示意
Fig.2 Chromosome individual coding pattern
2.4 环境变化检测算子
在以往的文献中,大多都是通过判断目标函数或约束条件的变化来检测环境的改变。例如,文献[18]在动态多目标优化中通过选取目标空间内均匀分布的11个非支配解作为“检测个体”,将其代入计算目标函数值或约束值,若相应值发生变化则代表环境发生变化。但是由于某些函数的特殊性,即便参数发生变化,其函数值也可能不发生变化。因此,设计了一种不依赖于决策变量的检测算子为
具体地说，这正是“在实践中学习”的基本涵义：无论就教师，或是其它具有较强实践性质的专业性工作而言，相关人士的专业成长都应直接服务于他们的实际工作．例如，主要就是基于这样一种认识，有学者提出，应将发展“实践性智慧”看成相关人士专业成长的主要目标[4]；又由于认为已有实践的反思正是增长实践性智慧最重要的途径，因此，人们又提出了关于实践性专业工作的这样一个定位——反思性实践者．
(17)
其中,阶跃函数
满足当x >0时阶跃函数值为1,当x =0时阶跃函数值为0。可以看出:①模型中只要有一个参数发生了变化,该参数对应阶跃函数值为1,则检测因子的值为1;②只有模型中所有参数均未发生变化时,所有参数阶跃函数值均为0,检测因子为0。因此,该检测算子可以不依赖于决策变量,而且可以第一时间检测环境是否发生变化。
2.5 环境变化响应策略
在动态进化算法中,当优化环境变化时有3种基本响应策略[19]。一是随机初始化种群,并重新开始寻优[20]。这类方法相当于将动态优化过程分解为多个静态优化过程,按顺序进行逐一优化。但是通常每个环境之间是存在一定联系的,完全舍弃上一环境的种群信息将不利于算法的快速收敛。另一种是当环境变化时继承上一环境中的种群,将其作为新环境下的初始种群开始寻优[21]。但是,由于上一环境下的种群是经过寻优后得到的,具有很强的收敛性,使用它作为新环境下的初始种群很容易使算法早熟,陷入局部最优。第三种是当环境变化时,保留一部分个体,另一部分随机初始化,进而产生混合种群作为下一环境的初始种群[22]。此类方法虽然保留了一部分种群信息,也增强了种群的多样性,但是很难确定保留哪一部分个体,属于一种盲目的响应策略。
DSAEA算法在对比以上策略(见第3.2节)的基础上主要采用第二种策略,即继承上一环境中的种群进行寻优。同时为了保证种群的多样性,又增加了莱维飞行策略以及自适应调整差分进化算法的相关参数。具体改进见第2.6节寻优算法部分。
2.6 寻优过程:自适应差分进化
差分进化算法作为一种新型智能优化算法,能够很好地解决单目标和多目标优化模型。差分进化包括3个核心步骤:变异、交叉和选择操作。
采用SPSS18.0统计软件，计量资料用（±s）表示，采用t检验，计数资料用百分比表示，采用χ2检验，P＜0.05为差异有统计学意义。
备件供应通常采用三级供应网络结构,如图1所示。
J :中转点的数量,j =1,2,…,J ;
各校食品质量与安全专业实习基本也存在上述问题。针对食品质量与安全专业学生在实习过程中发现的问题，我们在学校和学院层面采取了一些行之有效的措施。
为防止环境变化后,种群失去多样性导致算法陷入局部最优。DSAEA算法对变异个体上每一维度变量以一定的概率P flight进行一次莱维飞行[25]。莱维飞行是自然界中常见的运动方式,它使得粒子的布朗运动中穿插一次随机长距离飞行。具体位置更新方式为
扶持龙头企业，扩大规模生产。在推进农业产业化进程中，龙头企业所发挥的作用不容小觑，属于农业生产经营的主导者。龙头企业对外能够积极开拓农业市场并为社会提供优质的农产品，对内能够带动农民致富并为其农业生产提供有益帮助，因而是农业品牌建设核心力量的一部分。基于此，各级政府应当制定相关政策，积极培育并壮大龙头企业，充分发挥龙头企业的作用，加强各个农产品生产企业之间的协作，实现“统一规划、统一标准、统一生产”的规模化和标准化生产，特别是要在价值增值环节重视企业的密切交流，进行资源优势的整合互补，形成农业产业竞争优势，实现农业企业规模集聚效应，从而为农业品牌建设创造有利条件。
v i =x i +F ×(x best-x i )+F ×(x r1 -x r2 )
(18)
式中,x i 为父代个体;x best为当前种群中的最优个体且x i ≠x best≠x rk 。DE/current-to-rand/1策略可以充分利用当前种群中精英个体的信息,从而保持较好的收敛性。
(2) 莱维飞行
令x i =(x i,1 ,x i,2 ,…,x i,D )为第i 个父代个体向量,v i =(v i,1 ,v i,2 ,…,v i,D )为根据变异策略产生的变异个体向量。经典的差分进化算法使用的变异操作为DE/rand/1策略[23],即v i =x r1 +F ×(x r2 -x r3 )。其中,F 是变异率;x r1 、x r2 和x r3 是从当前种群中随机选择的3个个体。这种策略产生的变异个体组成的种群保持了很好的多样性,但是不利于个体向种群中的最优个体收敛。因此本文采用DE/current-to-rand/1策略进行变异[24]。
(19)
式中,v i,j 是种群中变异个体i 上的第j 维变量;
是飞行前的变量位置;
是其飞行后的变量位置;s 是飞行步长。s 通过Mantegna算法进行模拟,其计算方式为
(20)
式中,μ 和υ 满足均值为0的正态分布,其方差分别为
同步碎石封层技术在长期应用于交通公路建设中逐步显现出性能高且成本较低的优点。该项技术的主要原料是沥青和颗粒性石料，用料简单且耗资较少，相较于传统的养路铺路技术来说，投入的总成本较低。并且通过专业车辆反复碾压后，使得养路材料与地面充分接触，养路效果较好，总体的使用寿命长，地面性能高。
(21)
式中,β 为常数,通常取1.5[26]。
图3给出了粒子经过一系列莱维飞行后的运动轨迹。设一个个体为x 1=[10,12,15,8,20],其上每个变量进行一次莱维飞行:10→10,12→12,15→15,8→19,20→20。则飞行后的个体变为
可以看出种群中的每个个体进行莱维飞行时,布朗运动可以保证种群中个体在局部范围内的开发能力,而随机长距离飞行有利于保持种群的多样性。即莱维飞行使得算法在多样性和收敛性上取得平衡。
图3 莱维飞行运动轨迹
Fig.3 Trajectory of Levy flight
(3) 自适应飞行概率
由于在算法迭代后期,莱维飞行不利于个体向最优个体的收敛,因此本文设计了自适应飞行策略,用来控制个体在不同进化代数中的飞行概率。
(22)
式(6)、式(7)约束表示未开放中转点不能参与备件的供应。式(6)为备件的供入量约束,式(7)为备件的供出量约束;式(8)约束为满足度约束。对于每一个需求点,其供应量和修复量之和应当不小于备件需求量;式(9)、式(10)约束为流量平衡约束。式(9)规定了第一阶段中转点无库存的情况下,供出的备件量应不超过供入的备件量。式(10)规定了从第二阶段开始的每一阶段中转点存在库存的情况下,供出的备件量应不超过供入的备件量加上库存量;式(11)、式(12)约束为容量限制约束。式(11)规定了第一阶段中转点无库存情况下,供入的备件量不能超过中转点的最大容量。式(12)规定了存在库存的情况下,供入的备件量以及库存量之和不能超过中转点的最大容量;式(13)约束规定了决策变量的类型。
例 1 某个动态优化问题有5个阶段构成,算法共进行迭代500次,每100次迭代环境发生一次变化。则环境变化计数器t =
;第t 阶段个体的莱维飞行概率
可以看出该式既保证了算法在每个不同的环境下飞行概率随迭代次数逐渐减小,又可以保证在环境发生变化时能够初始化飞行概率,确保新环境的种群多样性。
步骤 2 交叉操作
交叉个体向量u i 由父代个体x i 和变异个体向量v i 经式(23)交叉操作产生。
(23)
式中,randi,j 为[0,1]之间均匀分布的随机数;CR∈[0,1]为交叉率,即当变异个体v i 上第j 个变量v i,j 对应的随机数小于交叉率时,该变量取父代个体对应值x i,j ,否则保留变异个体上的值。可以看出CR的值设置的越大,进行交叉操作的概率越大。
气管镜是比较成熟的一项微创手术，手术风险极低，蒋利学又是这方面的权威，手术经验极其丰富，本来以为手到病除的一个小手术，不想却遇到了前所未有的大挑战。挑战不是来自他本身，而是来自小家伙。
步骤 3 选择操作
在经典的差分进化算法中,采用以下策略进行选择:分别比较第i 个父代个体x i 和第i 个交叉个体u i 的适应度函数值,选择适应度最小的个体作为子代个体s i [27]。
在此基础上,首先将父代个体种群和交叉个体种群进行混合。再计算混合种群的个体适应度函数,根据适应度函数由小到大进行排序,选择前N (种群规模)个个体作为子代个体,进入下一次迭代。
传统双边匹配决策方法建立在期望效用理论基础之上，假设匹配主体是完全理性的，然而在实际匹配过程中，匹配主体在行为上并非完全理性，而表现为参照依赖和损失规避等心理行为特征。1979年Kahneman和Tversky通过大量的实验研究发现了决策者的实际决策行为与期望效用理论相背离的现象，并引入心理学的研究成果，提出了前景理论[22-23]。前景理论使用价值函数取代期望效用理论中的效用函数，能很好地描述和表达匹配主体在决策过程中的参照依赖和损失规避等心理行为特征。
3 算例分析
3.1 算例描述
为完成某次备件供应保障任务,共设置2个供应点和4个中转点,保障6个需求点的备件需求。供应任务分5个阶段完成,不同阶段需求点的备件需求、维修成本以及各节点间备件运输费用各不相同,具体相关信息如表1～表5所示。
表1 节点间单位备件运输成本
Table 1 Transportation cost per unit spare parts between nodes 百元
表2 中转点相关信息
Table 2 Related information of transfer centers
表3 需求点单位备件维修成本
Table 3 Maintenance cost of unit spare parts at demand centers 百元
表4 需求点备件修复率
Table 4 spare parts repair rate of demand centers
表5 需求点在各级段的备件需求量
Table 5 Spare parts demand of demand centers at each period 个
实验在Windows 7操作系统上采用Matlab 2014b进行编程,平台为个人笔记本(Intel Core i5-6300HQ 2.3 GHz/L3 CPU 和 4.00 GB RAM)。相关实验参数设置如下:种群规模N =100，最大迭代次数max_iter=500，阶段数period=5，环境变化计数器
t =
初始环境变化检测因子Detector1=0,初始约束违反度惩罚系数M 0=10 000,变异率F =0.9,初始莱维飞行概率P 0=0.9,交叉率CR=0.8。
3.2 结果分析
3.2.1 动态优化算法和静态优化比较
为了验证在解决备件多阶段供应决策时,动态优化与静态优化策略的效果,分别使用两种算法对模型进行优化求解。首先,在保持其他设置完全一致的情况下,对比了当优化环境发生变化时,环境变化响应策略采取随机初始化或者继承上代种群两种策略的优化结果。若随机初始化种群,则相当于将动态优化问题分成多个静态优化问题求解,因此将这种情况记为静态优化算法;将继承上代种群时的优化结果记为动态优化优化算法。优化结果如图4所示。
果然。何良诸咧嘴，挑起讥讽的笑。何良诸是小孩子吗，说拎就被你们一把拎过来，说审啥就审啥。何良诸蹙起眉头，回忆似说：“我有十多年，没去那里了。”
图4中纵坐标表示适应度函数的值,横坐标表示迭代次数。图4(b)为将图4(a)的底部放大后进行展示。从图4(a)中可以发现在第一阶段两种策略下的算法收敛速度基本一致。但是当环境发生变化(iter=100,200,300，400)时,静态优化算法收敛速度明显慢于动态优化算法。这是由于静态算法将优化问题分为多个单阶段并分别进行优化,在环境变化后对种群进行了随机初始化。新的种群完全舍弃上一阶段种群的信息导致算法局部开发能力降低。从图4(b)可以看出,第一阶段相同环境下,动态优化算法收敛速度略快于静态优化算法。在环境发生变化时,动态优化算法的波动范围更小,收敛速度明显更快。这是由于动态优化算法在环境变化时能够充分利用上一阶段种群信息,属于一种记忆机制,它保证算法在新环境中波动幅度很小且能迅速收敛。
图4 两种环境变化响应策略下优化结果
Fig.4 Optimization results under two environmental change response strategies
表6和表7分别给出了静态优化和动态优化算法得到的各个阶段的备件供应方案及其目标函数值。可以看出动态优化所得方案花费的总成本为9 495.73百元,要远小于静态优化所得方案的总成本14 731.63百元。再次表明动态优化算法在收敛性上的优势。
表6 静态优化算法求得供应方案
Table 6 Supply scheme with static optimization algorithm
续表6
Continued Table 6
表7 动态优化算法求得供应方案
Table 7 Supply scheme with dynamic optimization algorithm
续表7
Continued Table 7
3.2.2 自适应策略和非自适应比较
为了验证DSAEA算法中自适应策略对算法性能的提升,分别用3种算法对模型进行求解,比较其优化结果。3种算法分别为:①本文提出的带有自适应莱维飞行策略的差分进化算法,记作自适应莱维飞行算法;②不带莱维飞行策略的差分进化算法,记作无莱维飞行算法;③每次迭带均以相同概率进行莱维飞行的差分进化算法,记作全莱维飞行算法。为了排除环境变化响应机制对自适应策略造成影响,分别对随机初始化种群和继承上一环境种群两种环境响应策略进行实验和对比分析。
图5是采用随机初始化种群响应策略时(静态优化),分别采用无莱维飞行、全部莱维飞行和自适应莱维飞行策略的优化结果。图5(b)为图5(a)底部的放大展示。从图5(a)中可以看出,无莱维飞行算法结果远大于其他两种策略。这是因为无莱维飞行算法种群的多样性很差,在寻优过程中过早收敛而陷入了局部最优。其优化得到的结果是局部最优解,最终求得的备件供应方案为不可行解。从图5(b)可以看出全部莱维飞行算法以及自适应莱维飞行算法均跳出了局部最优。但是,全部莱维飞行算法在每个优化阶段后期仍然有较大的波动,收敛性较差。而自适应莱维飞行算法能够很快地收敛并找到全局最优解。
图5 静态优化时不同算法运算结果
Fig.5 Results of different algorithms in static optimization
表8给出了3种算法求得的备件供应方案对应的总成本。可以看出无莱维飞行算法未能求得模型的可行解,而全部莱维飞行算法和自适应莱维飞行算法能够求得模型可行解且自适应莱维飞行算法所得方案最优。
表8 静态优化不同算法结果
Table 8 Results of different algorithms in static optimization 百元
图6是采用继承上一环境种群响应策略时(动态优化),分别采用无莱维飞行算法、全部莱维飞行算法和自适应莱维飞行算法的优化结果。
图6(b)和图6(c)为图6(a)部分区域的放大展示。从图6(a)中可以看出无莱维飞行算法未能求得模型可行解,而带有莱维飞行策略的算法均求得可行解。从图6(b)中可以看出优化环境发生变时,算法求得的结果发生阶跃式变化,然后随着算法迭代并未收敛。表明此时算法陷入了局部最优,种群完全丧失多样性。从图6(c)可以看到自适应莱维飞行算法收敛性强于全部莱维飞行算法,能够找到全局最优解。
图6 动态优化时不同算法优化结果
Fig.6 Results of different algorithms in dynamic optimization
表9给出了3种算法求得的备件供应方案对应的总成本。同样的,无莱维飞行算法未能求得模型的可行解,自适应莱维飞行算法所得方案最优。
表9 动态优化不同算法结果
Table 9 Results of different algorithms in dynamic optimization 百元
4 结 论
研究了间歇性需求下备件多阶段供应的优化决策,考虑了不同阶段相关参数发生变化的情况,构建了备件供应动态优化模型。为了寻找模型的最优可行解,利用元启发式智能优化算法对模型进行优化计算。在经典静态差分进化算法的基础上,增加了环境变化检测算子以及环境变化响应机制,使得传统差分进化可以用来解决动态优化问题。同时,为了保证环境变化时算法的全局搜索能力以及局部开发能力,提出了自适应莱维飞行策略。改进的动态自适应差分进化算法很好地求解了备件多阶段供应模型的最优解,为部队备件供应提供了一套最佳的选址-分配方案。
同时分别对算法的改进部分进行了对比分析,结果表明：一方面,环境变化检测和相应策略使得差分算法可以用来解决动态优化问题,且取得了比静态优化更优的结果；另一方面,自适应策略可以在环境变化时很好地维持种群的多样性和收敛性,对算法的性能有很大的提升作用。
综上,本文研究了备件保障中的动态供应问题,提供了一套有效的建模和优化框架,并提出了相应的智能优化算法,为部队实际中的备件保障工作提供了重要的参考和思路。
参考文献：
[1] HU Q W,JOHN E B,CHEN H J,et al.OR in spare parts management:a review[J].European Journal of Operational Research,2018,266(2):395-414.
[2] 胡起伟,贾希胜,赵建民.考虑预防性维修的备件需求量计算模型[J].兵工学报,2016,37(5):916-922.
HU Q W,JIA X S,ZHAO J M.A model of calculating spare parts demand volume by considering preventive maintenance[J].Acta Armamentarii,2016,37(5):916-922.
[3] 王慎,李庆民,彭英武.串件拼修对策下两级备件维修供应系统动态管理模型[J].航空学报,2013,34(6):1326-1335.
WANG S,LI Q M,PENG Y W.Dynamic management model of two-echelon maintenance and supply system for spare parts with cannibalization[J].Acta Aeronautica et Astronautica Sinica,2013,34(6):1326-1335.
[4] 周亮,李庆民,彭英武,等.动态保障结构下多级多层备件配置优化建模[J].航空学报,2017,38(11):150-162.
ZHOU L,LI Q M,PENG Y W.et al.Optimization model for multi-level and multi-echelon spare part allocation in dynamic support structure[J].Acta Aeronautica et Astronautica Sinica,2017,38(11):150-162.
[5] 蔡泽明,康锐,龙军.面向系统优化的备件动态配置方法[J].系统工程与电子技术,2010,32(11):2363-2366.
CAI Z M,KANG R,LONG J.System optimization-oriented dynamic spares configuration method[J].Systems Engineering and Electronics,2010,32(11):2363-2366.
[6] 王铁宁,李浩,王生凤.面向作战任务的装甲装备群携行备件配置优化[J].兵工学报,2016,37(10):1881-1888.
WANG T N,LI H,WANG S F.Optimization of operational mission-oriented carried spares allocation of armored equipment[J].Acta Armamentarii,2016,37(10):1881-1888.
[7] YONGHENG J,RODRIGUEZ M A,HARJUNKOSKI I,et al.Optimal supply chain design and management over a multi-period horizon under demand uncertainty.Part Ⅱ:a lagrangean decomposition algorithm[J].Computers & Chemical Engineering,2014,62(3):211-224.
[8] AYELE Y Z,BARABADI A,BARABADI J.Dynamic spare parts transportation model for Arctic production facility[J].International Journal of System Assurance Engineering and Management,2015,7(1):84-98.
[9] SHEU J B,KUNDU T.Forecasting time-varying logistics distribution flows in the one belt-one road strategic context[J].Transportation Research Part E:Logistics and Transportation Review,2018,117:5-22.
[10] ABDALLAH A M F M,ESSAM D L,SARKER R A.On solving periodic re-optimization dynamic vehicle routing problems[J].Applied Soft Computing,2017,55(6):1-12.
[11] CHACHUAT B,SINGER A B,BARTON P I.Global methods for dynamic optimization and mixed-integer dynamic optimization[J]. Industrial & Engineering Chemistry Research, 2006, 45(25):8373-8392.
[12] YU X,YU X,LU Y,et al.Differential evolution mutation operators for constrained multi-objective optimization[J].Applied Soft Computing,2018,67:452-466.
[13] COELLO C A C.Constraint-handling techniques used with evolutionary algorithms[C]∥Proc.of the Genetic & Evolutionary Computation Conference,2012.
[14] PANDA A,PANI S.A symbiotic organisms search algorithm with adaptive penalty function to solve multi-objective constrained optimization problems[J]. Applied Soft Computing, 2016, 46: 344-360.
[15] LI L D,YU X,LI X,et al.A modified PSO algorithm for constrained multi-objective optimization[C]∥Proc.of the 3rd International Conference on Network & System Security,2009:462-467.
[16] COELLO C A C.Constraint-handling techniques used with evolutionary algorithms[C]∥Proc.of the Genetic & Evolutionary Computation Conference,2012.
[17] TESSEMA B,YEN G G.An adaptive penalty formulation for constrained evolutionary optimization[J].IEEE Trans.on Systems,Man,and Cybernetics-Part A:Systems and Humans,2009,39(3):565-578.
[18] WEI J X,JIA L P.A novel particle swarm optimization algorithm with local search for dynamic constrained multi-objective optimization problems[C]∥Proc.of the IEEE Congress on Evolutionary Computation,2013:2436-2443.
[19] 刘淳安,王宇平.动态多目标优化的进化算法及其收敛性分析[J].电子学报, 2007, 35(6):1118-1121.
LIU C A,WANG Y P.Evolutionary algorithm for dynamic multi-objective optimization problems and its convergence[J].Acta Electronica Sinica,2007,35(6):1118-1121.
[20] JIANG S,YANG S.A steady-state and generational evolutionary algorithm for dynamic multiobjective optimization[J].IEEE Trans.on Evolutionary Computation,2017,21(1):65-82.
[21] ZAMAN M F,ELSAYED S M,RAY T,et al.Evolutionary algorithms for dynamic economic dispatch problems[J].IEEE Trans.on Power Systems,2016,31(2):1486-1495.
[22] JIANG S,YANG S.Evolutionary dynamic multi-objective optimization:benchmarks and algorithm comparisons[J].IEEE Trans.on Cybernetics,2017,47(1):198-211.
[23] PSYCHAS I D,MARINAKI M,MARINAKIS Y,et al.Non-dominated sorting differential evolution algorithm for the minimization of route based fuel consumption multiobjective vehicle routing problems[J].Energy Systems,2017,8(4):785-814.
[24] AWAD N H,ALI M Z,MALLIPEDDI R,et al.An improved differential evolution algorithm using efficient adapted surrogate model for numerical optimization[J].Information Sciences,2018,451:326-347.
[25] YAO P,WANG H.Dynamic adaptive ant lion optimizer applied to route planning for unmanned aerial vehicle[J].Soft Computing,2016,21(18):5475-5488.
[26] YANG X S,DEB S.Engineering optimization by cuckoo search[J].International Journal of Mathematical Modelling and Numerical Optimisation,2010,1(4):330-343.
[27] TATSIS V A,PARSOPOULOS K E.Differential evolution with grid-based parameter adaptation[J].Soft Computing,2017,21(8):2105-2127.
Multi -stage spare parts supply optimization based on dynamic evolutionary algorithm
WANG Yadong1, SHI Quan1, ZHANG Fang2, YOU Zhifeng1, XIA Wei1,3
(1. Department of Equipment Command and Management ,Shijiazhuang Campus ,Army Engineering University ,Shijiazhuang 050003 ,China ;2. Research Center for Scientific and Technological Innovation ,Unit 32178 of the PLA ,Beijing 100012 ,China ;3. Department of Mechanized Infantry ,Shijiazhuang Campus ,the Army Infantry Academy of PLA ,Shijiazhuang 050003 ,China )
Abstract : Since the spare parts demand is almost the intermittent demand in real spare parts support, the supply of spare parts is usually a multi-stage dynamic optimization problem. Focusing on this, a multi-stage mathematical model of spare parts supply is constructed. In order to solve this kind of dynamic optimization problem, a meta-heuristic dynamic optimization algorithm is proposed. Firstly, an environment change detector and an environment change response strategy are added to the classical differential evolution algorithm, which enables the differential evolution algorithm to solve the dynamic optimization problem when the environment changes. Secondly, a self-adaptive Levy flight strategy is proposed, which enables the algorithm to maintain a good global exploration and local exploitation capability when the environment changes. Empirical test shows that the proposed dynamic self-adaptive difference algorithm can obtain the optimal feasible solution of the model, and the distribution and convergence of the algorithm are greatly improved.
Keywords : spare parts supply; dynamic optimization; differential evolutionary algorithm; Levy flight; self-adaptive
收稿日期: 2019-01-18;修回日期： 2019-03-07;网络优先出版日期: 2019-06-06。
网络优先出版地址: http:∥kns.cnki.net/kcms/detail/11.2422.TN.20190606.1639.010.html
基金项目: 武器装备“十三五”预先研究共用技术项目(41404050501);军内科研重点项目(KYSZJWJK1742)资助课题
中图分类号: E 91
文献标志码: A
DOI: 10.3969/j.issn.1001-506X.2019.11.15
作者简介：
王亚东 (1992-),男,博士研究生,主要研究方向为装备维修工程、军事运筹及优化算法。
E-mail:xwzj0003@163.com
石 全 (1966-),男,教授,博士研究生导师,博士,主要研究方向为装备维修保障理论与技术、战场抢修、军事运筹。
E-mail:airesearch01@gmail.com
张 芳 (1976-),女,高级工程师,硕士,主要研究方向为装备试验与协同创新。
E-mail:junshiyc@163.com
尤志锋 (1980-),男,讲师,博士,主要研究方向为装备维修工程及战场抢修。
E-mail:1442469514@qq.com
夏 伟 (1980-),女,讲师,博士,主要研究方向为军事装备学及网络化维修、军事通信。
E-mail:axwangel@126.com
标签：备件供应论文; 动态优化论文; 差分进化论文; 莱维飞行论文; 自适应论文; 陆军工程大学石家庄校区装备指挥与管理系论文; 32178部队科技创新研究中心论文; 陆军步兵学院石家庄校区机械化步兵系论文;