周孟然1， 吴雷明2
(1.安徽理工大学 电气与信息工程学院, 安徽 淮南 232001；2.安徽理工大学 计算机科学与工程学院， 安徽 淮南 232001)
摘要：针对传统遗传算法应用在矿区配电网规划中易发生早熟收敛从而影响规划的准确度问题，提出了一种多种群模拟退火遗传算法。该算法以年规划费用最小为目标函数，结合模拟退火算法的优点，同时加入多种群的特征，解决了配电网规划中易发生早熟收敛问题，提高了搜索效率，方便获得规划中全局最优解。实验结果表明，利用多种群模拟退火遗传算法对矿区配电网优化后，规划成本、种群迭代次数都有明显降低，运行时间比原有算法降低约6%，误差率降低约3%，更加实用高效。
关键词：煤矿配电网； 配电网规划； 多种群； 模拟退火； 遗传算法
配电网规划是在负荷预测的基础上，通过优化线路的手段，得到网损小、经济适用度高、可靠性高的配电网，在煤矿生产中起到了重要的作用。在配电网实际规划中，需要考虑到多个优化问题变量，因而配电网规划问题是一个带有多种约束的、非线性多目标的组合优化问题。传统的配电网规划方法如线性规划、混合整数规划等容易发生搜索方向错误，渐渐不再使用。基于这种情况，遗传算法被逐渐应用到配电网的规划中。传统的遗传算法虽然对配电网规划起到了较好的效果，但在操作过程中，会因为一些实际的问题，如节点负荷、电网故障等，产生误差，因此，需要对传统遗传算法进行改进，得到更加符合实际的算法[1]。文献[2-3]利用遗传算法的优点，加入模拟退火算法，在网络优化上取得了良好效果。文献[4]研究的基础是直流配电相较于交流配电更节能，建造及运行成本低，线路损耗小且容量易于扩展,渐渐成为煤矿配电网研究热点。文献[5-6]提出了利用模拟退火遗传算法对配电网进行规划，但是该算法中缺少了多种群，会影响到种群的多样性。文献[7]提出了一种自适应的遗传算法，在种群进化过程中，根据种群进化的程度，改变种群的交换、变异概率，同样取得了很好的效果。文献[8]提出了一种模糊自适应的遗传算法，根据交叉变异概率分成不同的模糊子集，供算法参数选择，不同的情况选择不同模糊子集。文献[9]根据矿井高电压的特点采用非线性规划方式对矿井高压配电网无功补偿进行优化，减少了线损率，降低了成本。
上述文献中有的利用硬件手段，如直接使用直流电规划煤矿配电网，有的利用算法规划对遗传算法进行改进，提出不同的改进策略，都取得了相应的成果。本文在上述文献的基础上，提出了一种多种群模拟退火遗传算法，并将其应用到矿区配电网规划中。该算法利用模拟退火算法可以跳出局部最优解、全局搜索能力强、收敛速度可控等优点，加入多种群特征，对标准遗传算法中容易出现的过早收敛、早熟、陷入局部最优解等情况进行了改进，提高了搜索效率，方便获得规划中全局最优解。
配电网规划问题主要是大规模的非线性规划问题。非线性规划问题主要包含目标函数和约束条件2个部分。而在目标函数和约束条件问题上，数学模型的选择很大程度上影响着最优方案的确定。本文以电网年规划费用最小为目标函数，数学模型的表达式为
(1)
式中：Zcost为年规划费用；λi为投资回收率；f1为网络的年运行费用；f2为网损费用；n为架设线路总数；C1i=λi+αi，其中αi为设备折旧维修费用率；Ti为新建支路i的投资费用；Li为架设的线路，当支路i新建时取1，否则取0；C2i为单位电价；τmaxi为最大负荷利用小时数；ΔSi为支路有功损耗。
约束条件影响着配电网的规划是否合理有效，有以下3个约束条件：
(1) 节点电压不等式约束：要求电压降必须满足给定要求,达到安全供电的标准。
(2)
式中：Ku为节点电压惩罚因子，作为对偏离运行极限的惩罚；Ui为节点i的电压；Uimax，Uimin分别为Ui的上下限。
(2) 导线电流不等式约束：要求导线长期载流量小于导线额定载流量。
(3)
式中：Ki为导线电流惩罚因子;Ii为支路i的电流；Ihi为支路i导线的载流量。
(3) 变电站容载比约束:约束公式为
(4)
式中：Krzb为变电站容载比惩罚因子；PG为变电站总负载容量;PGmax，PGmin分别为变电站总负载容量的上、下限;PL为当前变电站负载容量。
2.1 遗传算法及模拟退火算法
遗传算法是将生物界的遗传、进化、变异等多种特征应用于计算机上的模拟研究。遗传算法借鉴的主要思想学说是达尔文学说和孟德尔遗传定律。其中参考了达尔文学说中的物竞天择、优胜劣汰思想和孟德尔遗传定律中的分离定律和自由组合定律。该算法主要将模拟自然界存在的变异、选择、组合等多种方式应用于计算机应用研究中,将最适合生存的种群保留下来，循环往复,直到达到需要的条件为止[10-11]。
模拟退火算法主要基于固体退火原理。金属在高温加工过程中，温度高时，原子运动活跃，不稳定的因素也就较多，但随着温度慢慢下降，固体中原子的活跃度逐渐降低。根据这一原理，模拟退火算法总是从一个不确定性的解开始，渐渐稳定，达到一个满足条件的解。该算法实为一种贪心算法，会陷入局部最优情况，但在算法中加入随机变量因素，让结果有一定概率接受更差的解，就可以很好地跳出局部最优的情况，得到全局最优解。为了解决遗传算法中存在的早熟、过早收敛、全局搜索能力较弱、且容易发生陷入局部最优解等问题，本文提出了一种改进的遗传算法，即多种群模拟退火遗传算法。
2.2 多种群模拟退火遗传算法原理
多种群模拟退火遗传算法以增加种群多样性为目的，其设计思想为初始化状态下种群足够丰富，或者算法在运行过程中依旧保持种群多样性[12]。首先在算法初始化状态下，选取适当的参数，例如交叉概率、变异概率、种群进化代数、初始温度值等，再加入多个独立的种群，分别让其独立进化，互不干扰，最大化保证种群独立的多样性。其次，因模拟退火算法具有渐进收敛性，全局搜索能力强，在算法运行过程中，可以接受当前不是最优解的概率存在，因而可以跳出局部最优情况[13]。所以，将二者的优良属性结合在一起，形成多种群模拟退火遗传算法，该算法全局搜索能力强，具有渐进收敛性。算法流程如图1所示。
第1步：初始化参数,参数包括种群规模M，进化代数G，交叉概率pc，变异概率pm。
第2步：初始化种群1,2,3，计算种群中各个个体的适应度f。
第3步：进行选择、交叉、变异操作，生成子代个体，计算子代个体的适应度f。
第4步：判断是否满足接受函数，若是,接受新个体，否则以一定概率接受新个体。
第5步：对新个体进行降温操作。
第6步：判断值是否满足预期函数值，若是,输出最优解，否则转到第3步。
在算法运行过程中，初始参数选择尤为重要。
图1 多种群模拟退火遗传算法操作流程
Fig.1 Operation flow chart of multi-population simulated annealing genetic algorithm
本文将pc设为0.95，pm设为0.05。在降温退火过程中，应尽量避免降温速度过快，导致失去优良解的情况。在算法运算过程中，主要包含外循环和内循环2种循环模式，外循环主要为遗传算法，控制着最优解的决定权;内循环主要为模拟退火算法，主要控制降温操作，以跳出局部最优解，从而具有更大可能性去获取全局最优解。
利用矿区内的配电网规划作为实验案例。实验配电系统由12个负荷节点和1个变电站构成，初始网络如图2所示,最优网络如图3所示。现有支路为10条，可以扩展的支路为9条，取年维护系数C1i=0.15，电价C2i=0.35，各负荷节点最大负荷利用小时数τmaxi=3 000。配电网节点容量见表1。利用多种群模拟退火遗传算法、标准遗传算法及模拟退火算法对配电系统进行优化,并对3种算法的优化结果进行对比分析。
图2 初始网络
Fig.2 Initial network
图3 最优化网络
Fig.3 Optimization network
表1 配电网节点容量
Table 1 Node capacity of distribution network
考虑到实际结果存在一定的误差和不确定性，因而进行了100次实验，去掉当中最差的10组解，计算出其余90组最优解的平均值。不同算法的年规划费用计算结果见表2。
表2 不同算法的年规划费用计算结果
Table 2 Calculation results of annual planning cost by different algorithms
不同算法的种群迭代次数对比结果如图4所示。
图4 不同算法的种群迭代次数对比结果
Fig.4 Comparison results of number of population iterations of different algorithms
由图4可知，刚开始时，多种群模拟退火算法和模拟退火算法二者迭代次数几乎差不多，而遗传算法迭代次数偏多。但随着运行次数的增加，多种群模拟退火遗传算法展现出它的优势，优于其他2种算法。
分别采用运行100，200,300次对不同算法的运行时间做对比，结果如图5所示。
图5 不同算法的运行时间
Fig.5 Running time of different algorithms
由图5可知，刚开始时，3种算法的运行时间几乎差不多，但随着运行次数的增加，可以看出，遗传算法和模拟退火算法二者运行时间基本上相同,而多种群模拟退火遗传算法运行时间渐渐减少。
依然采用运行100，200,300次对不同算法的运行误差率做对比，结果如图6所示。
图6 不同算法的误差率对比
Fig.6 Comparison of error probability of different algorithms
由图6可知，多种群模拟退火遗传算法在结合遗传算法和模拟退火算法的优点后，误差率有明显下降，运行次数在100次之后，稳定在5%左右，优于其他2种算法。
提出了多种群模拟退火遗传算法，并将其应用到煤矿配电网规划中。该算法利用年规划费用最小为目标函数，结合模拟退火算法的优点，同时加入多种群的特征，大大改进了传统遗传算法中出现早熟收敛、种群过于单一、无法找到全局最优解的情况。实验结果表明，该算法运行速度、误差率都好于原有的遗传算法，运行时间比原有算法降低约6%，误差率降低约3%，更加实用高效。
参考文献(References)：
[1] 吴焕,张琪君.基于遗传退火算法的智能组卷系统研究[J].工业控制计算机,2017(1):112-113.
WU Huan，ZHANG Qijun.Research on system of intelligent test paper composition based on genetic algorithm and simulated annealing algorithm[J].Industrial Control and Computer,2017(1):112-113.
[2] 苏艳刚.基于模拟退火遗传算法的网络优化应用研究[J].信息通信,2016(9):6-8.
SU Yangang.Application of network optimization based on simulated annealing genetic algorithm[J].Information & Communications,2016(9):6-8.
[3] 何国华,解建仓,汪妮,等.基于模拟退火遗传算法的水资源优化配置研究[J].西北农林科技大学学报(自然科学版),2016,44(6):196-202.
HE Guohua，XIE Jiancang，WANG Ni,et al.Optimal allocation of water resources based on simulated annealing-genetic algorithm[J].Journal of Northwest A&F University(Natural Science Edition),2016,44(6):196-202.
[4] 卢其威,高彦，刘静，等.构建煤矿直流配电网的关键技术及可行性分析[J].煤炭学报，2015,40(10)：2496-2502.
LU Qiwei,GAO Yan,LIU Jing,et al.Key technologies and feasibility analysis of coal mine DC power distribution network[J].Journal of China Coal Society，2015,40(10)：2496-2502.
[5] 王玮, 刘德龙,吴学智,等.基于改进CGA的配电网重构[J].北京交通大学学报,2016,40(5):100-103.
WANG Wei,LIU Delong,WU Xuezhi,et al.Distribution network reconfiguration based on improved CGA[J].Journal of Beijing Jiaotong University,2016,40(5):100-103.
[6] 余健明，吴海峰，杨文宇，等.改进多种群遗传算法在中压配电网规划中的应用 [J].西安理工大学学报，2005,21(1)：69-72.
YU Jianming,WU Haifeng,YANG Wenyu，et al. Application of improved poly-population genetic algorithm in distribution electric network planning[J].Journal of Xi'an University of Technology，2005,21(1)：69-72.
[7] 马志刚,侯颖.基于自适应多种群遗传算法的配电网重构[J].华中电力,2010,23(6):16-19.
MA Zhigang,HOU Yin.Distribution network reconfiguration based on adaptive multiple population genetic algorithm[J].Central China Electric Power,2010,23(6):16-19.
[8] 徐密,孙莹,李可军，等.基于模糊自适应模拟退火遗传算法的配电网故障定位[J].电测与仪表,2016,53(17):44-48.
XU Mi,SUN Ying,LI Kejun,et al.Fault location of distribution networks based on fuzzy adaptive simulated annealing genetic algorithm[J].Electrical Measurement & Instrumentation,2016,53(17):44-48.
[9] 柳春生,焦留成.非线性规划法在矿井高压配电网无功补偿优化中的应用研究[J].煤炭学报,2002,27(4):444-448.
LIU Chunsheng,JIAO Liucheng.Application of nonlinear programming method in the reactive power compensation optimization of mine high voltage distribution network[J].Journal of China Coal Society,2002,27(4):444-448.
[10] 刘锦伟，谢雄刚，方井.基于遗传算法-BP神经网络的煤层注水效果分析[J].工矿自动化，2016，42(1):48-51.
LIU Jingwei,XIE Xionggang,FANG Jing.Effect analysis of coal seam water infusion based on genetic algorithm-BP neural network[J].Industry and Mine Automation，2016，42(1):48-51.
[11] 厉康平,汪鹏君,张会红.基于模拟退火遗传算法的三值FPRM电路功耗优化[J].浙江大学学报(理学版),2016,43(2):190-194.
LI Kangping,WANG Pengjun,ZHANG Huihong.The search of the best power polarity of ternary FPRM circuit based on simulated annealing genetic algorithm[J].Journal of Zhejiang University(Science Edition),2016,43(2):190-194.
[12] 黄俊辉,汪惟源,王海潜,等.基于模拟退火遗传算法的交直流系统无功优化与电压控制研究[J].电力系统保护与控制,2016,44(10):37-43.
HUANG Junhui,WANG Weiyuan,WANG Haiqian,et al.Study of hybrid genetic algorithm and annealing algorithm on reactive power optimization and voltage control in AC/DC transmission system[J].Power System Protection and Control,2016,44(10):37-43.
[13] 王安义,郗茜.基于遗传算法优化的LS-SVM井下场强预测[J].工矿自动化,2016,42(12):46-50.
WANG Anyi,HAO Qian.Forecasting of underground field intensity based on LS-SVM optimized by genetic algorithm[J].Industry and Mine Automation,2016,42(12):46-50.
Optimization application of an improved genetic algorithm in coal mine distribution network planning
ZHOU Mengran1, WU Leiming2
(1.School of Electrical and Information Engineering, Anhui University of Science and Technology, Huainan 232001, China; 2.School of Computer Science and Engineering, Anhui University of Science and Technology, Huainan 232001, China)
Abstract:In view of problems of premature convergence of application of traditional genetic algorithm in distribution network planning in mining area to affect accuracy of planning, a multi-population simulated annealing and genetic algorithm was proposed. The algorithm takes the minimum year planning cost as objective function , and combines with advantage of simulated annealing algorithm, adds multi-population characteristics at the same time, so as to solve the problem of premature convergence in power distribution network planning and improve search efficiency and convenient to obtain the global optimal solution in the planning. The experimental results show that cost planning, iteration times are significantly reduced by use of multi-population simulated annealing and genetic algorithm to optimize mine distribution network, the running time is reduced by about six percent, the error rate is reduced by about three percent compared with the original algorithm, and the algorithm is more effective and efficient.
Key words:coal mine distribution network; distribution network planning; multi-population; simulated annealing; genetic algorithm
收稿日期：2017-04-20；
修回日期：2017-07-11；责任编辑：张强。
基金项目：国家自然科学基金项目(51174258)；国家安全生产监督管理总局安全生产重大事故防治关键技术科技项目(anhui-0001-2016AQ)。
作者简介：周孟然(1965-),男，安徽淮南人，教授，博士研究生导师，博士，主要研究方向为煤矿安全监测，E-mail:mrzhou8521@163.com。
引用格式：周孟然，吴雷明.改进型遗传算法在煤矿配电网规划中的优化应用[J].工矿自动化，2017,43(9)：70-74. ZHOU Mengran, WU Leiming. Optimization application of an improved genetic algorithm in coal mine distribution network planning[J].Industry and Mine Automation，2017,43(9)：70-74.
文章编号：1671-251X(2017)09-0070-05
DOI：10.13272/j.issn.1671-251x.2017.09.013
中图分类号：TD611
文献标志码：A 网络出版时间：2017-08-28 11:36
网络出版地址：http://kns.cnki.net/kcms/detail/32.1627.TP.20170828.1136.013.html