基于改进免疫遗传算法和Holt-Winters的电能计量器具配送优化

王 杰，孙 林，郑 直，张嘉浩，黄 雷

(1.国电南瑞科技股份有限公司，江苏 南京 210032；2.金现代信息产业股份有限公司，山东 济南 250101；3.湖南大学电气与信息工程学院，湖南 长沙 410082)

随着智能电网的迅速发展，电能计量器具也逐步由传统电能表转变为智能电表。智能电表相比于传统电能表可以给用户提供更加精确的用电信息，通过科学记录，可以让用户用电更趋合理，同时可以调整电能质量，及时处理电能故障，提高人身与设备的安全性。然而，大规模安装使用智能电表会导致仓储规模的持续扩大和物流量的不断增长。这就要求电网计量中心不仅要采取相应措施降低物流配送成本,还要保持较高的客户服务水平[1-2]。

目前，国家电网提出了“整体授权、自动检定、智能仓储、高效配送”的基本目标，然而现今智能电表的各项配送活动主要以人工安排和调度为主，以计量中心为起始点，通过人工上报的数据将智能电表送往各个调度中心，用户购买时进行配送，此情况下的配送效率相对较低，配送信息的共享性较差。因此，有必要规划计量中心—配送中心—客户的二级物流配送网络，才能实现不同运输方式的有机配合。规划物流配送网络要确定网络中配送中心数量、所处位置及其客户分配情况，配送网络的合理化程度对企业物流配送效益的高低起着决定性作用，开展关于电能计量器具物流配送网络优化的相关研究十分有必要[3]。

配送网络优化问题大致可分为预测和选址两部分，大量学者对此开展了研究工作。关于时间序列预测，文献[4]根据配电系统的历史负荷信息，运用Holt-Winters模型预测了负荷的伪测量值，进而优化了用于配电系统状态评估的无迹卡尔曼模型；文献[5]提出了一种基于业务特征的电能表需求预测模型，该模型根据安装类型对电能表分类，再利用平稳性检验来分析安装类型影响需求量的主要因素，进而自适应地使用时间序列模型(autoregressive integrated moving average model，ARIMA)对电能表需求量进行分析预测，预测数据可靠。关于选址优化问题，免疫遗传算法具有保证种群多样性的特征，克服了粒子群算法容易陷入局部最优的缺点，且具有较高的收敛速度，能够很好地解决多目标优化问题[6-7]。免疫遗传算法还可通过多种方式对其进行改进，文献[8]运用改进免疫遗传算法，通过重新定义抗体浓度，提出一种抗体浓度新定义下的策略，解决电压无功优化问题时改进算法在计算速度和优化效果方面都具有明显的优势。

本文采用Holt-Winters模型预测变化规律具有线性趋势性和季节性的电能计量器具需求量时间序列，需求量和客户位置信息作为已知量，以运输成本最小为目标建立数学模型，采用免疫遗传算法对电能计量器具配送网络进行优化，为了改善算法的收敛性，提高种群的多样性，基于相似性和矢量距对抗体浓度进行调整，改进免疫遗传算法，并应用于电能计量器具配送网络的选址、定位以及分配客户。

1 理论基础

1.1 Holt-Winter模型

Holt-Winters模型是多参数季节模型，适用于预测具有线性变化趋势且变化规律具有明显季节性的短期时间序列，Holt-Winters模型是在一、二次指数平滑算法的基础上推导的，也被称为三次指数平滑模型[9]。

一次指数平滑模型适用于预测无明显变化趋势的时间序列，预测公式如下：

Si=αxi+(1-α)Si-1

(1)

式中Si为第i期的一次指数平滑值；xi为第i期的实际值(i=1,2,…,n)；α为平滑系数(0≤α≤1)。

二次指数平滑模型加入趋势项t，可用于预测具有线性变化趋势的时间序列，预测公式如下：

(2)

三次指数平滑模型是在二次指数平滑的基础上再平滑，加入季节项p，可分为加法和乘法模型。加法模型适用于变化季节性较为稳定的时间序列，而乘法模型适用于季节性呈现比例变化的情况。加法、乘法模型分别如下：

(3)

(4)

确定初始化水平值、趋势值的计算公式分别为

Si=αxi+(1-α)(Si-1+ti-1)

(5)

(6)

确定初始化季节性值的方法：首先，将所给的时间序列包含的周期数计算出来；然后，将各个周期内时间序列值的平均值计算出来。对于加法模型来说，要将时间序列每个时刻的实际值减去其所对应周期的平均值来获得每个时刻的差值，然后将这些差值取平均就能得到其第1个周期的初始化季节值。而对于乘法模型来说，需将时间序列每个时刻的实际值除以相应周期的平均值得到每个时刻的比值，然后将这些比值进行平均，得到第1个周期的初始化季节性值。

Holt-Winters模型预测趋势是否符合实际的关键在于平滑系数a的选取、平滑系数控制权数下降速度，a接近1时近期数据的权重较大，a接近0时历史数据的权重较大。它既表征了模型对时间序列数据变化的反应速度，又决定了预测模型修匀误差的能力。为了提高预测模型的准确性，本文采用黄金分割法筛选最优平滑系数[10]。

黄金分割法搜寻最优平滑系数的原理是在平滑系数的取值区间找到2个黄金分割点，并将区间分为三部分，对比平滑系数分别取这2个值时的预测值，确定预测值较为准确的黄金分割点，保留该点的相邻两区间，保留区间即为缩小后的平滑系数取值区间。循环上述过程，逐步缩小搜索区间，直到区间长度在允许误差范围时，区间内的任意一点都可看作极小点的近似值，以此来确定最佳的平滑系数a。

1.2 改进免疫遗传算法

遗传算法是一种模拟自然选择和生物进化过程搜索最优解的随机优化方法，基本操作包括选择、交叉和变异。免疫遗传算法是将免疫系统相关概念及其理论应用于遗传算法中的一种智能优化算法，该算法综合了遗传算法的搜索特性和免疫算法求解目标函数的自适应特性，能有效地抑制进化过程中出现退化现象，同时避免搜索结果收敛于局部极值，具有良好的全局搜索能力[11-13]。免疫遗传算法的重要概念和操作步骤如下。

1)随机生成N个初始抗体种群。

Xi=L+U+rand(U-L)

(7)

式中Xi为第i个抗体；L、U分别为可行解的下界、上界。

2)计算抗体与抗原之间的亲和力。亲和度表示可行解对目标问题的匹配程度，由于本文为物流配送优化问题，因此，抗体与抗原之间的亲和度为目标方程的倒数：

(8)

式中f(Xi)、f(Xj)分别为第i、j个抗体的适应度值；N为抗体总数。

抗体与抗体之间的亲和度主要表示2个抗体之间的相似程度，根据欧氏距离，计算公式为

(9)

抗体浓度是指抗体种群中相似抗体所占据的比重，常规免疫遗传算法的抗体浓度：

(10)

其中，H(Xi,Xj)≥T时取H(Xi,Xj)=1；否则，取H(Xi,Xj)=0，T为相似度阈值。

每个抗体激励度由抗体和抗原之间的亲和度与抗体浓度构成，即

(11)

其中ε为常数(0≤ε≤1)。当抗体的亲和度越高时，抑制浓度高的抗体，这样可以有效的保持抗体的多样性。

3)选取亲和度高的Nc个个体进行克隆作为记忆库，按照一定的概率对克隆的抗体进行交叉和变异，用亲和度高的变异抗体替代亲和度低的克隆抗体，同时保留当代种群中亲和度最大的抗体并更新记忆库，进入到下一抗体群。

4)对种群进行刷新，随机产生N-Nc个抗体与记忆库中的Nc个抗体形成新的种群。

5)判断程序是否满足终止条件，满足则输出结果，否则转步骤2。

免疫遗传算法在评价抗体优秀程度时，常用抗体浓度控制的方法以保证物种多样性和全局最优解。对于电能计量器具配送网络优化问题，这些浓度控制方法的全局搜索能力较差，易因变异概率不合理而导致局部最优，抗体经过交叉变异后会产生大量的不可行解，且收敛速度较慢。为了解决这些问题，本文提出一种基于相似性矢量距改进抗体浓度的免疫遗传算法，将其应用于优化电能计量器具配送网络中。

根据抗体间相似度对抗体进行选择，相似度可根据信息熵或欧式距离求出，进而可得到基于相似性的抗体浓度函数：

(12)

式中H(Xi,Xj)为第i、j个抗体的相似度。

抗体矢量距是指该抗体与其他抗体间适应度值差值的总和，计算公式如下：

(13)

根据抗体矢量距对抗体进行选择，可得到基于矢量距的抗体浓度函数：

D2(Xi)=1/[N·V(Xi)]

(14)

综合考虑上述2种抗体选择策略，可得到抗体浓度函数：

D(Xi)=αD1(Xi)+(1-α)D2(Xi)

(15)

式中α为常数调节因子(0≤α≤1)，α的取值需一个训练的过程。

基于相似性和矢量距的抗体浓度函数选择低浓度、高适应度抗体的同时，可以维持种群的多样性，有效避免局部最优现象，提高免疫遗传算法的全局搜索能力。

1.3 目标函数

在进行电能计量器具配送网络优化时，需要获取每个客户的电能计量器具需求量，可通过建立预测模型的方式来计算得到。此外，计量中心和客户点的位置信息也是必不可少的。然而，收集到的原始信息通常是经纬度坐标，不能直接用于建模和计算。高斯投影法可将椭球面的经纬坐标转换为平面直角坐标，为便于计算，再将平面直角坐标进行平移，使所有的点都落在第1象限内。

对于电能计量器具配送网络优化问题，以电能计量器具的运输成本最小作为目标，配送单价和运输费用等数据为已知量，为了便于计算，假设客户点之间的运输距离为2点间的直线距离。构造配送网络优化的目标函数：

(16)

(17)

s.t.xc0

(18)

yc0

(19)

(20)

式中j为待建配送中心，j=1,2,…,m；i为客户点,i= l,2,…,n；dij为配送中心j到客户i的运输距离；(x0,y0)为计量中心的位置坐标；d0j为计量中心到配送中心j的运输距离；(Xj,Yj)为待建配送中心的位置坐标；cij为配送中心j到客户i的运输单价；c0j为计量中心到配送中心j的整车运输单价；zij为决策变量,当客户点i由待建配送中心j配送货物时取1,否则取0；(xc0,yc0)为配送区域的起始点坐标；Di为客户点需求量；(xc1,yc1)为配送区域的终止点坐标；H为运输车辆的最大载量；(xi,yi)为客户点位置坐标。

本文的电能计量器具配送网络优化策略包括需求预测、配送中心选址、分配客户点等，流程如图1所示。

图1 优化策略流程Figure 1 Flow chart of optimization strategy

首先，输入客户的电能计量器具需求量和客户的经纬度坐标，通过建立预测模型并计算预测结果误差，若误差不满足限制条件，则通过黄金分割法重新计算a、b和γ，建立新的预测模型；若误差满足限制条件，则陆续计算出未来一年客户计量器具月度需求量。然后，采用高斯投影法对用户的经纬度坐标进行处理，得到在第一象限的平面直角坐标，同时输入各个客户点的计量器具需求量，将其代入配送中心选址优化模型，采用改进免疫遗传算法进行计算，进化得到适应度值最优的物流配送方案。

2 实例分析

2.1 预测结果

为了验证Holt-Winters模型预测电能计量器具月度需求量的准确性，本文选用2015—2017年某省网某品规单相电能表月度故障抢修需求量作为原始数据[14]。采用黄金分割法选取最优平滑系数，然后利用Holt-Winters模型对2018年月度的电能表需求量进行预测，并将预测值与实际值进行比较。原始数据如表1所示，原始数据与Holt-Winters模型拟合结果的对比如图2所示，可知拟合曲线与实际变化曲线重合，预测的变化趋势和季节性符合实际变化规律，预测效果较好。

表1 原始数据Table 1 Raw data

图2 Holt-Winters模型预测结果Figure 2 Prediction results of Holt-Winters model

2018年月度电能表需求量的实际值与预测值的对比如表2所示(预测误差=|预测值-实际值|/实际值×100%)，可知预测效果较好。由于政策、市场、特殊气候等实际因素对电能表需求量的影响较为复杂，少量的预测结果误差较大难以避免，但预测结果与实际结果的变化趋势性和季节性一致，验证了Holt-Winters模型用于电能计量器具需求预测的可行性。

表2 2018年月度电能表需求量的实际值与预测值Table 2 Actual value and predictive value of monthly power meter demand in 2018

2.2 配送方案

本文的电能计量器具配送网络优化策略将应用于求解一个计量中心—配送中心—客户的二级配送网络实例，实例包括52个客户点[15]和1个计量中心。利用高斯投影法可将用户和计量中心的经纬度坐标转换为平面直角坐标并进行坐标平移，利用Holt-Winters模型可预测未来1 a的电能表月度需求量，年度需求量由月度数据累加得到，最终结果如表3所示，其中计量中心坐标为(0,0)。

由于不同用户对电能表的需求量差异较大，本模型选取配送中心数量为5；假设计量中心到配送中心和配送中心到客户的单位长度运输成本相同，本文取100；电能表从计量中心运输到配送中心的运输方式为整车运输，从配送中心到客户的运输方式为零担运输，整车运输的最大载量取400；将不同位置点之间的直线距离视为其运输距离。

基于改进免疫遗传算法的配送中心位置和配送网络客户分配方案如图3所示，可以看出，客户点大致分为5个区域，每个区域由一个配送中心承担配送电能表的任务。配送中心靠近这些区域的中心，配送路线呈放射状到达每个客户。电能表配送方案如表4所示，表中粗体的客户编号为所选的5个配送中心。由于不同客户对电能表的需求存在较大差异，故不同配送中心的分配客户数量也存在着较大差异。

表3 客户点位置及电能表需求量Table 3 Customer location and power meter demand

图3 电能表配送方案Figure 3 Distribution scheme of power meter

表4 配送网络选址及客户分配Table 4 Distribution network location and customer allocation

2.3 收敛性对比

对常规免疫遗传和改进免疫遗传算法的收敛性进行对比。免疫遗传算法应用于本文实例的收敛特性曲线如图4所示，可以看出，基于相似性和矢量距改进抗体浓度的免疫遗传算法优化速度明显优于常规免疫遗传算法，进化代数达到50代左右时获得了该实例的最优解，具有更好的收敛性。

图4 收敛特性曲线Figure 4 Curve of convergence characteristic

在进化过程中，改进算法的最优适应度值和平均适应度值均维持相对稳定的下降趋势逼近最优解，而常规算法的平均适应度曲线出现了显著的振荡现象，说明在抗体选择过程中，改进算法比常规算法能更准确地保留低浓度、高适应度值的抗体，在保证物种多样性的同时，增大了优秀抗体的选择概率。

3 结语

1)客户对电能计量器具的需求量随时间变化的趋势较为平稳，但受季节影响十分显著。Holt-Winters模型适用于预测该类型的时间序列数据；采用黄金分割法逐步搜索并缩小平滑系数的可行区间，能求解出最优平滑系数的近似值,提高预测准确性。

2)免疫遗传算法能有效避免收敛于局部最优解，本文提出基于相似性和矢量距的浓度函数改进免疫遗传算法，其收敛性优于常规算法，能高效解决配送中心选址和客户分配问题。