基于文化烟花算法的电动汽车充电站规划研究

李小川 刘媛华

摘要：针对电动汽车充电站规划问题，建立以最小化充电站服务与用户需求综合成本为目标的数学模型，并提出基于文化思想的改进烟花算法求解该问题。将烟花算法嵌入文化算法计算框架中，进行底层搜索寻优，提取其进化过程中的有用信息组成信仰空间知识。信仰空间以粒子群迭代规则更新知识并通过接受函数指导种群空间进化，以提高搜索效率。仿真实验结果证明，文化烟花算法在求解电动汽车充电站规划问题时具有良好的稳定性和较高的求解效率。

关键词：电动汽车充电站；最优规划；烟花算法；文化算法

DOIDOI：10.11907/rjdk.181021

中图分类号：TP311

文献标识码：A 文章编号文章编号：1672-7800（2018）008-0017-04

英文摘要Abstract：In order to optimize the layout of electric vehicle charging station，a mathematical model for the minimum gross costs of charginge station and users was established and an improved fireworks algorithm based on cultural algorithm was proposed.The initial fireworks algorithm was embedded in the computational framework of cultural algorithm to do the bottom search.The favorable information of the current optimal solution was taken as the knowledge of the belief space to guide the evolution direction of the fireworks through the acceptance function and improve the search efficiency.The simulation experiments show that the cultural fireworks algorithm has high stability and efficiency in solving the planning problem of electric vehicle charging station.

英文关键词Key Words：electric vehicle charging station；optimal planning；fireworks algorithm；cultural algorithm

0 引言

电动汽车符合当今绿色出行理念，受到各国政策的大力支持，我国电动汽车销量也逐年增加。与此同时，充电站等基础设施的缺乏限制了电动汽车的大范围推广[1]。因此，研究充电站的合理布局问题具有重要现实意义，受到各国学者的广泛关注。Awasthi等[2]首先利用遗传算法求解充电站选址问题，再采用粒子群算法对求得的解作进一步优化，提高了寻优精度；闫天泽等[3]基于模拟退火思想对粒子群算法惯性权重进行改进，通过算例验证了算法的可行性；冯超等[4]基于GIS提出多种群混合遗传算法求解充电站布局规划问题，有效避开了不适宜建立站点的区域；齐琳等[5]基于K中心点云模型思想调整粒子群算法惯性权重，增强了算法局部搜索能力。以上智能算法在求解精度方面已经取得一定成果，但是大多数求解效率较低。因此，本文尝试利用烟花算法的爆发性以提高该问题的求解效率。

烟花算法（Fireworks Algorithm，FWA）是一种具有爆发性的新型智能优化算法，由北京大学学者Tan等[6]于2010年受到烟花爆炸过程可产生不同爆炸半径和火花个数的启发而提出。该算法原理简单明确、参数少、搜索效率高且较易于实现，已成功应用于工作车间调度[7-8]、背包问题[9]、Web服务优化[10]、物流中心选址[11]等组合优化领域，但目前尚未有文献用烟花算法求解充电站规划问题。文化算法（Cultural Algorithm，CA ）由Reynolds[12]受人类通过吸取经验指导自身或他人行为的启发而提出，对智能算法的自组织过程赋予显性指导条件。CA为智能算法的改进提供了一种思想，各种符合CA结构的算法都可作为种群空间的一部分参与进化[13]，从而提高基本算法的性能。本文提出一种文化烟花算法（Cultural Fireworks Algrithm，CWPA）用于求解电动汽车充电站规划问题，将烟花算法嵌入文化算法计算框架，烟花算法作为种群空间进行底层迭代寻优，提取其进化过程中的有用信息组成信仰空间知识，信仰空间独立进化更新知识并通过接受函数指导种群空间进化方向，避免进化的盲目性，从而提高搜索效率，为电动汽车充电站规划問题求解提供了一种新思路。

1 电动汽车充电站规划数学模型

1.1 问题描述

电动汽车充电站规划问题可描述为：在同时满足充电站和用户双方需求的前提下，通过建立合理的选址和定容方案，使充电站建设成本、人力成本、维护成本等服务成本，以及用户电费成本、路途成本、排队等待等需求成本之和最小化。同时还需满足以下条件：①每个充电站的充电机数量需控制在一定范围内；②充电站应尽量分散，相互之间距离不宜过小；③每个充电站覆盖的服务区域不宜过大，即用户与最近充电站间距不宜过大；④每个充电站的车流量需控制在一定范围内；⑤充电机充电负荷应大于电动汽车充电负荷。

1.2 参数定义

式（2）表示最小化充电站服务和用户需求综合成本的目标函数；式（3）～（8）分别表示各项成本分量；式（9）约束了每个充电站充电机数量范围；式（10）约束了每个充电站车流量范围；式（11）约束了充电站总数范围；式（12）表示每个充电站的服务半径不能过大；式（13）表示相邻充电站间距不宜过小；式（14）表示充电机充电负荷大于电动汽车充电负荷。

2 求解電动汽车充电站规划的烟花文化算法

2.1 基本烟花算法

2.2 文化算法

文化算法为上层信仰空间（也称信度空间）和底层种群空间组成的双层并行结构[15]，基本框架如图1所示。信仰空间以接受函数的形式记录种群迭代过程中的有用信息，并对其分析总结形成知识，以指导种群空间中粒子的后续进化过程。文化算法框架为混合算法的协同进化提供了模型[16]，双层空间的信息共享机制使算法的自适应进化效率更高。

2.3 烟花算法改进

针对电动汽车充电站规划问题提出基于文化思想的改进烟花算法，烟花算法作为种群空间进行底层寻优，可以充分利用其强局部搜索能力，对此类不定点连续性区域的搜索效率较高。但是烟花算法个体之间进化独立，也容易陷入局部最优，为此选取每次迭代中的部分较优烟花作为信仰空间群体，以粒子群算法的迭代过程进行知识演化，并通过Accept（）函数指导烟花群体进化过程。两空间信息共享、相互促进，使算法同时具有较强的局部和全局搜索能力。

2.4 算法流程描述

（1）初始化算法参数，包括烟花个数n1、爆炸半径基数A、火花基数S、火花个数约束常数α与β、高斯变异烟花数m、最大迭代次数G、初始接受代数accept_stepinit。

（2）采用数值型编码初始化n1个烟花，设置信仰空间为空集。

（3）算法迭代。种群空间按照式（15）-（22）进行迭代寻优，信仰空间取烟花群体规模的2/3，按照粒子群算法的搜索过程进行自身迭代更新，每次迭代中提取当前最优烟花作为知识替换信仰空间中的最差个体。

3 仿真结果与分析

3.1 实验仿真

为验证本文提出的文化烟花算法求解复杂环境下电动汽车充电站选址规划问题的效能，利用Matlab R2012a软件，以拥有25个需求点的区域（见表1）为例进行仿真实验，并与基本烟花算法、基本粒子群算法以及文献＼[5＼]中提出的IPSO所求结果进行对比。仿真参数为：①CFWA参数为：烟花种群规模15，爆炸半径基数为A=2，基本爆炸火花数S=20，高斯变异烟花数l=6，α=0.05，β=05，初始接受代数accept_stepinit=5；②FWA基本参数与CFWA相同；③PSO参数为：种群规模15，学习因子c1=c2=2，惯性权重w=0.7。每种算法独立运行20次，最大迭代次数均为200。每个充电站的充电机数量为5～15台，每台充电机投入成本5万元，充电站建设成本50万元，设计年限为20年，贴现率5%，每台充电机平均人力成本3.6万元，平均维修成本0.8万元，充电机发生故障的惩罚成本0.5万元，平均故障次数10次，充电机每次故障的平均维修时间为2h，电动汽车充电电费单价为0.5元/KWh，每个充电站的最小车流量为30，电动汽车充电额定功率为20KW，充电机充电功率为500KW，每辆车年均充电100次，电动汽车充电的单位路途成本为0.5元，电动汽车充电平均等待时间为0.1h，相邻充电站最小间距1.5km。

3.2 仿真结果分析

表2为CFWA、FWA、PSO以及文献[5]提出的IPSO4种算法求解电动汽车充电站规划问题统计结果，图2～图4分别为CFWA、FWA和PSO求得的最优规划方案。由表2可知，CFWA所求最优综合成本为392.96万元，充电站个数为5个，FWA和PSO所求最优综合成本分别为470.28和527.93万元，充电站个数均为6个，说明CFWA求解结果较FWA和PSO更优；在平均综合成本方面，CFWA的结果明显优于FWA和PSO，说明CFWA具有更好的稳定性；在平均收敛代数和平均收敛时间方面，CFWA也优于FWA和PSO，说明CFWA求解效率更高；CFWA求得充电站个数与IPSO相同，但最优综合成本与收敛时间均优于IPSO。总体而言，CFWA相较于FWA和PSO，在求解电动汽车选址规划问题时表现出更优的性能，较IPSO求解效率更高。

4 结语

本文首次尝试采用烟花算法求解电动汽车充电站选址规划问题，将烟花算法嵌入文化算法计算框架，信仰空间利用两空间的信息共享机制指导种群空间进化方向，改进了基本烟花算法在求解电动汽车充电站选址规划研究时易陷入局部最优的不足，提高了全局搜索能力。实验仿真验证了基于文化思想的改进烟花算法在求解电动汽车充电站选址规划研究问题时的高效性和稳定性。

参考文献：

[1] 刘文霞，张蕾蕾，刘宗歧，等.城市纯电动汽车发展模式论证方法[J].电力系统自动化，2014，38（24）：34-40.

[2] AWASTHI A，VENKITUSAMY K，PADMAN S.Optimal planning of electric vehicle charging station at the distribution system using hybrid optimization algorithm[J].Energy，2017，133（5）：70-78.

[3] 闫天泽，邱晓燕，刘延博，等.基于引入模拟退火思想的改进粒子群算法的电动汽车充电站最优规划[J].电测与仪表，2017，54（6）：11-16.

[4] 冯超，周步祥，林楠，等.电动汽车充电站规划的多种群混合遗传算法[J].电力系统及其自动化学报，2013，25（6）：123-129.

[5] 齐琳，姚俭，王心月.基于改进粒子群算法的电动汽车充电站布局优化[J].公路交通科技，2017，34（6）：136-143.

[6] TAN Y，ZHU Y C.Fireworks algorithm for optimization[C].International Conference on Advances in Swarm Intelligence，2010：355-364.

[7] 包晓晓，叶春明，黄霞.烟花算法求解JSP问题的研究[J].计算机工程与应用，2017，53（3）：247-252.

[8] 曹磊，叶春明，黄霞.应用混沌烟花算法求解置换流水车间问题[J].计算机应用与软件，2016，33（11）：188-192.

[9] 薛俊杰，王瑛，孟祥飞，等.二进制反向学习烟花算法求解多维背包问题[J].系统工程与电子技术，2017，39（2）：451-458.

[10] 张以文，吴金涛，赵姝，等.基于改进烟花算法的Web服务组合优化[J].计算机集成制造系统，2016，22（2）：422-432.

[11] 李小川，刘媛华.基于改进烟花算法的物流配送中心选址研究[J].软件导刊，2017，16（11）：153-156.

[12] REYNOLDS R G.An introduction to cultural algorithms [C].Proceedings the 3rd Annual Conference on Evolutionary Programming，1994：131-139.

[13] 黎明，江乐旗，陈昊.基于文化算法的无人飞行器航迹规划[J].模式识别与人智能，2017，30（2）：152-161.

[14] GAO H Y，DIAO M.Cultural firework algorithm and its application for digital filters design[J].International Journal of Modeling，Identification and Control，2011，14（4）：324-331.

[15] REYNOLDS R G，KINNAIRD H L.Optimization problem solving with auctions in cultural algorithms [J].Memetic Computing，2013，5（2）：83-94.

[16] 吴亚丽，徐丽青.一种基于粒子群算法的改进多目标文化算法[J].控制与决策，2012，27（8）：1127-1132.

（責任编辑：黄 健）