本站原创【摘 要 】基于差分进化算法在收敛快速性及粒子群算法在种群多样性保持上的优势,提出一种新的混合启发式优化算法,其基本思路是将粒子群种群作为辅助变异算子,与差分进化算法种群进行交叉操作,产生的新子代继承了父代和母代的优势特性,从而避免了单一算法的早熟收敛和收敛速度过慢的问题. 通过在测试函数上的仿真实验印证了该算法思想的可行性,并将其应用到物流配送路径优化问题的解决中.
【关 键 词 】差分进化,粒子群,定向变异,物流配送优化
1.引言
优化问题普遍存在于科学研究、经济管理和工程技术等诸多领域,近年来以遗传算法、粒子群算法和差分进化算法为代表的群智能优化算法得到了迅速的发展和广泛应用,与传统优化方法相比,这些智能优化算法的优势在于能够保证收敛的前提下,对所求优化问题动力学信息不苛求,具有全局优化能力.
差分进化算法（Differential Evolution, 简称DE）是一种新的进化计算技术,它其实是一种基于实数编码的具有保优思想的贪婪遗传算法.同遗传算法一样,差分进化算法包含变异和交叉操作,但同时相较于遗传算法的选择操作,差分进化算法采用一对一的淘汰机制来更新种群.它的特点是具有良好的优化性能,但是对于多峰值函数以及搜索空间较大时,算法收敛速度较慢,且易早熟.粒子群优化算法（Particle Swarm Optimization, 简称PSO）也是一种典型的群智能算法,它源于对鸟群、鱼群觅食行为的研究和模拟.PSO算法简单易于实现,并且在保持种群多样性上具有一定优势,且具有相对较快的收敛速度.在PSO算法中,群体中所有的粒子具有相同的搜索行为,并表现出相同的全局或局部搜索能力.
2.研究现状
PSO和DE算法都是一种基于群体进化的智能优化算法,他们有自身的特点和优势,同样也都存在缺陷和不足.具体讲就是DE是一种基于随机种群搜索的算法,它通过特有的变异、交叉和选择操作使种群能够快速进化到最优值附近,算法简单,控制参数少,易于实现.DE算法在具有简易和快速收敛性的同时,其在种群多样性方面优势不明显,算法易陷入局部极小.PSO算法也比较简单,便于实现,并且在种群多样性保持上具有一定优势,收敛速度相对较快.
国内外很多学者对DE和PSO算法进行了深入研究,文献[2]在基本差分进化算法的基础上,把自适应变空间思想融入提出了自适应变空间差分进化算法,在进化代数达到预设周期整数倍时,按变空间算法自动扩展或收缩搜索空间,实现了自动寻找合适搜索空间、提高收敛速度和精度的目的,文献提出了两种新的改进算法：DERL和DELB,并进行了大量对比仿真,验证了改进算法的有效性,文献改进了粒子速度的更新公式,引入了惯性权因子,并提出了自适应调整的策略,使算法在搜索初期有较大的搜索能力,而在后期又能得到较精确的结果.文献[9]提出了算法模型,PSO模型是基于繁殖和子种群的杂交,在子群的繁殖过程中,PSO算法引入繁殖概率,每次迭代可产生相同数目的后代微粒,父代微粒可用后代微粒取代,实现保持不变的种群的微粒数目,对于后代的微粒位置由父母位置的算术“交叉”得到,达到了防止早熟和加快收敛速度的效果.
另一方面,为突破单一算法的局限,继承和发扬算法各自的优点,国内外学者对混合种群智能优化算法进行了很多研究和探讨.文献[1]根据遗传算法和粒子群算法各自的特点,设计了一种遗传算法和粒子群优化的多子群分层混合算法,底层由遗传算法组成,贡献算法的全局搜索能力,上层由各子群的最有个体组成精英群,采用粒子群加速收敛.文献[10]结合混沌差分进化思想,提出混沌差分进化的粒子群优化算法,利用信息交换机制,引入混沌变异操作,用差分进化算法和粒子群算法将两组种群分别进行协同进化,提高了算法的局部搜索能力和收敛速度.文献[11]提出一种差分进化与粒子群双种群协同进化算法（DEPSO）,仿真结果显示了有效性.基于上述思想,本文对差分进化和粒子群算法以及两者的混合算法进行了深入研究,提出了一种新的混合差分粒子群优化算法（New hybrid differential evolution and particle swarm optimization algorithm,简称NHDEPSO）,仿真验证其有效性,并应用到物流配送问题研究中.
3.NHDEPSO算法
3.1 基本DE算法
DE算法是一种基于群体进化的算法,通过种群内个体间的合作与竞争来优化问题的解,具有记忆最优个体和共享种群内信息的特点,其本质就是一种用实数编码具有保优思想的贪婪遗传算法[19].
算法首先要取得一组在搜索空间上随机初始化的种群：
（1）
Np是种群规模,经过一系列规定的操作,第t代个体进化为：
（2）
式中,D为所优化问题的维数.
为防止陷于局部极值,可采用变异进化,有多种变异的方式,本文列出其中DE/rand/1和DE/best/2：两种基本的变异方式.
（3）
（4）
式（1）和（2）中,当前种群中随机个体是各不相同的,为适应度最好的个体,为缩放因子.
交叉策略为：在种群中检测设个体与进行交叉操作,产成试验个体,为了确证个体的进化,首先通过随机选择,使试验个体xT至少有一位由贡献.其他位则利用交叉概率因子CR,交叉操作方程为：
（5）
选择策略：采用“贪婪”的搜索策略,谁的适应值高,就选择谁作为子代：
（6）
上述算法中,父代两个不相同的随机个体相减得到差分矢量,随机选取第3个个体把差分矢量加到其上,产生一个变异的个体,依据一定的概率,将父代个体同变异个体之间进行交叉操作,得到试验的个体,然后按照应度函数值的大小在父代个体与试验个体之间进行选择,择优的个体作为子代,保证了最优的进化方向. 3.2 标准粒子群算法
标准PSO算法,是由m个粒子组成的群体在n维搜索空间中以一定的速度飞行,每个粒子在搜索时,考虑到了自己搜索到的历史最好点和群体内其他粒子的历史最好点,在此基础上进行位置的变化,直到满足条件时停止并输出最优解：
（6）
式中,上标i对应于第i个个体（,N为种群规模）,下标j对应于粒子的第j维,t表示当前迭代代数,和分别表示第i个粒子的位置和速度,其中,是惯性因子,c1、c2分别是个体历史最优和全体最优的加速因子,r1、r2为[0,1]内随机数.
3.3 算法改进
对于DE算法和粒子群算法的改进,已有很多学者进行了研究,这里采用两种简单的改进方式,来提高算法的性能.文献[12]提出一种新的差分变异方式,该变异方式能有效地提高算法的收敛速度,同时也在一定程度上还能保持较高的种群的多样性.在种群中新的差分变异方案是随机选取不同的四个个体,来生成差分矢量对每代个体进行变异操作.其变异的方程为：
（7）
在（7）式的变异中,对于第t代的种群的第i个个体,基向量仍然采用,表示在的基础上进行变异,这种变异方式使初始种群的多样性得到了很好保持,种群进化的方向同时也得到了兼顾.后面一项是作为“扰动项”引入的,经过这种方式处理后,使变异后的个体可以保持尽可能大的差异,从而使种群的多样性得到很好的保持.
文献[13]认为以往的粒子群算法都是基于“位置”和“速度”两个概念,并且改进算法也都是围绕这两个参数增加操作算子,如杂交、变异等,使得算法描述越来越复杂.对此作者经过研究分析相关文献资料,提出一种简化的不含速度项的粒子群位置变换公式：
（8）
式中,右边的第1项为“历史（history）”部分,表示过去对现在的影响,通过调节影响程度,第2项为“认知（cognition）”部分,表示粒子对自身的思考,第3项为“社会（social）”部分,表示与邻居粒子的比较和模仿,实现粒子间的信息共享与合作.
3.4 NHDEPSO算法步骤
Step1：设定参数Np、D、D、CR、xmin、xmax、c1、c2等参数,设置进化代数计数器t等于0,设置变空间次数最大值T.
Step2：初始化.在搜索空间[xmin,xmax]中随机产生Np个个体作为初始种（0）.
Step3：个体评价.计算群体P（t）中每一个体的评价函数值f（i）,并根据评价值对和进行赋值.
Step4：按照（7）式进行变异操作产生群体P1（t）,按照（8）式进行变异操作产生群体P2（t）.
Step5：P1（t）和P2（t）按照（5）式进行交叉操作产生下一代种'（t）.
Step6：按照（6）式对种1（t）和P'（t）进行选择操作产生子代种（t+1）,并对种（t+1）个体进行评价.
Step7：如满足精度则停止进化输出最优个体,否则,转步骤3.
4.算法性能分析
算法性能测试参数设置：设置维数D等于30,种群规模取维数的5～10倍[4],这里取NP等于200,最大迭代次数8000,差分缩放因子取F等于0.6,差分交叉概率取CR等于0.6.设置粒子群算法参数等于0.729,c1等于c2等于1.49445[14],测试函数如表1所示.
对比算法选取标准DE、PSO和DEPSO算法, DE和PSO参数的设置同上,DEPSO参数设置参见文献[11]中的设置,仿真精度VTR等于10-6.仿真结果如图1～3所示,为方便对比,在图1～3中取适应值的对数来画图.
对文献[15]测试函数F1-F4、文献[16]测试函数f 7和f 8进行仿真分析,参数设置同上.为便于比较4种方法计算6个测试函数的收敛情况,参考文献[15],若求得的结果与理想最优解的误差若小于10-4,则视其算法收敛性已实现,最大迭代代数为4000.记录算法第一次达到收敛的代数和时间,分别称为收敛代数、收敛时间.采用编程工具MATLAB 2013a,配置计算机的系统为：Pentium4 3.00GHz,4GHz内存,Win7.每个测试的算法分别独立执行50次,分别平均计算50次的试验结果如表2所示.
表1 测试函数
函数名 表达式 取值范围
Dejong
Griewank
Rosenbrock
表2 基准函数的优化结果比较
算法 性能 F1 F2 F3 F4 f7 f8
PSO 收敛率 0.27 0.31 0.21 0.19 0.35 0.3
平均收敛代数 2358 3520 3200 3321 1920 1832
平均收敛时间/ms 45.32 86.22 75.26 82.35 37.25 35.26
DE 收敛率 0.34 0.24 0.33 0.23 0.4 0.38
平均收敛代数 2198 3652 2635 3457 1735 1507
平均收敛时间/ms 41.25 61.23 49.67 58.35 32.48 27.89
DEPSO 收敛率 0.6 0.58 0.73 0.67 0.8 0.9
平均收敛代数 1423 2347 1378 1736 536 796
平均收敛时间/ms 37.25 46.35 35.26 39.57 15.6 23.12
NHDEPSO 收敛率 0.82 0.79 0.92 0.89 0.93 0.97
平均收敛代数 807 1423 652 1576 825 756 平均收敛时间/ms 25.12 37.35 20.14 37.58 22.25 20.35
从图1～图3及表2对比数据可以看出,NHDEPSO算法在f1～f3、F1～F4、f7～f8测试函数上的寻优性能普遍好于其他几种对比算法.例如图1中,在f1函数上DE、PSO和DEPSO算法均趋向于早熟收敛,但是NHDEPSO却能够在保持种群多样性,防止早熟收敛以及收敛速度上具有明显优势.
5.NHDEPSO算法在电子商务物流配送路径优化问题中的应用
5.1 B2C电子商务物流配送数学模型
文献[17]给出了B2C电子商务物流配送路径优化模型：
（9）
满足如下条件：
（10）
（11）
模型中的符号有两类：决策变量和模型参数.
决策变量：xijk表示车辆k是否从节点i开往节点j,yij表示顾客j是否由配送中心i配送,zjk表示顾客j是否由车辆k配送.
模型参数：G是配送中心、顾客两类节点和代表之间配送线路的边组成的不完全无向图,,其中：表示配送中心节点集合,表示顾客的节点集合,表示配送中心、顾客间直接线路边的集合,K配送车辆集合,每辆车仅属于一个配送中心,L配送商品种类集合,Ap配送中心p的可用车辆数,Bk车辆k的一次性启动费用,Cij车辆k在路线（i,j）单位路程的运输费用,qjl顾客j对商品l的需求量,dij顾客（或配送中心）i,j间的距离,Q单个车辆的装载量,商品l的重量系数,vil配送中心i商品l的供应量.
图1 目标函数f1的收敛曲线
图2 目标函数f2的收敛曲线
图3 目标函数f3的收敛曲线
图4 实际配送网络图
5.2 基于NHDEPSO算法的配送路线优化仿真
设某B2C电子商务企业在某时段由3个配送中心为17个顾客配送3类商品,配送网络节点（站点和客户）及他们之间的相互距离如图4所示.设三个配送中心可用车辆数均为Ap等于3辆,最大载重量均为Q等于10t,车辆启动费用元,单位距离费用元,3类商品的重量系数分别为吨/件、吨/件,其他相关参数见文献[18].为了验证基于NHDEPSO算法的物流分配方案的有效性,将基于该算法与基于DE算法和PSO算法所得到的目标函数优化值进行对比（各随机计算10次,求平均值）,如表3所示,基于NHDEPSO算法的B2C物流配送最优配送路径如图5所示,随机各选取其中一次目标函数收敛曲线对比如图6所示（为方便对比,选取同一初始种群）.
图5 基于NHDEPSO算法的车辆最优配送路径
图6 目标函数收敛曲线
从表3对比数据可以看出,虽然在程序运算时间上基于NHDEPSO的物流配送优化算法略长于基于DE算法的优化算法,但是在目标函数的优化值上基于NHDEPSO算法的优化值要具有明显优势,10次优化计算的最优值的平均值和标准值均小于基于其他两种基本算法的物流配送方案.因此,基于NHDEPSO算法的B2C物流配送路线方案是可行和高效的.
表3 仿真结果对比
计算次数 目标值/元 计算时间/秒
PSO DE NHDEPSO PSO DE NHDEPSO
1.2352 2148 2085 0.952 0.756 0.658
2.2248 2096 2085 1.253 0.563 0.547
3.2153 2085 2085 1.123 0.624 0.589
4.2458 2085 2085 1.258 0.524 0.668
5.2247 2124 2085 1.145 0.468 0.758
6.2189 2085 2085 0.975 0.587 0.987
7.2315 2178 2085 1.365 0.652 0.752
8 2478 2085 2097 1.287 0.498 0.675
9 2185 2179 2085 0.976 0.513 0.694
10 2368 2085 2085 0.953 0.487 0.587
平均值 2299.3 2115.0 2086.2 1.129 0.567 0.692
标准差 113.95 39.58 3.79 0.133 0.070 0.085
6.结论
本文基于生物遗传思想,设计了一种新的差分进化粒子群混合算法,该算法能够继承差分进化和粒子群算法的优势,提高算法的性能,通过仿真对比显示该算法在保持种群多样性和收敛性能上要优于所对比算法.最后将该算法应用到B2C电子商务物流配送中,仿真结果显示该算法要优于基于差分进化和粒子群算法的物流配送优化方案.