贪心算法结合Hopfield神经网络优化配电变电站规划

高炜欣，罗先觉，朱颖

(西安交通大学电气工程学院，陕西省西安市710049)
摘要：提出了一种城市电网规划中变电站规划优化的新算法。该算法先用贪心算法(greedyalgorithm)快速求解新建变电站的座数及各变电站的容量，再利用Hopfield神经网络校核新建变电站的位置和各变电站的供电范围，最后确定各变电站的真实容量。在求解过程中，该方法考虑了已有变电站的改造问题。从全局最优的原则出发，可求得具有实际价值的最优或近似最优解。该方法在求解变电站供电范围时无需对数据进行归一化处理，且易于编程。该方法可为变电站规划提供一种新的思路。
关键词：电力系统；配电变电站；最优化；神经网络；贪心算法ANEWDISTRIBUTIONSUBSTATIONPLANNINGALGORITHMBASEDON
GREEDYALGORITHMANDHOPFIELDNEURALNETWORK

GAOWei-xin，LUOXian-jue，ZHUYing

(SchoolofElectricalEngineering，Xi’anJiaotongUniversity，Xi’an710049，ShaanxiProvince，China)
ABSTRACT:Anewalgorithmfordistributionsubstationplanningispresented.Inwhichthegreedyalgorithmisfirstusedtoworkoutthenumberofnewsubstationsandthecapacityofeachsubstation(includingtheexistentsubstation),thentheHopfieldneuralnetworkisusedtodeterminethepositionsofnewsubstationsandtheserviceregionofeachsubstation,finally,accordingtotheserviceregionofeachsubstation,therealcapacityofeachsubstationisdecidedwhiletherenovationoftheexistentsubstationsisconsidered.Startfromtheprincipleofglobaloptimizationtheoptimumsolutionorapproximateoptimumsolutioncanbeobtained.Usingthisalgorithmthedataneednotnormalizeintheworking-outoftheserviceregionsofthesubstations.Thenewalgorithmcanmaketheexistentsubstationsadequatelyinvolvedintotheoptimizingprocedure,andtheprogrammingofthisalgorithmiseasytoimplement.Thisalgorithmcanprovideanewapproachtosubstationplanning.
KEYWORDS:Powersystem；Distributionsubstation；Optimize；Neuralnetwork；Greedyalgorithm
1引言
城市电网规划是电力系统规划的重要组成部分。配电变电站规划优化是城市电网规划中起着承上启下作用的重要环节。长期以来，各国学者对此做了大量研究。
1974年，Masud首先采用线性整数规划方法优化变电站容量^[1]。文献[2]采用最小路径算法和运输问题模型进行变电站的规划和优化。文献[3]采用分枝定界法进行规划计算。文献[4]列举了配电网规划的8种方法，并进行了测试和比较。
近几年又有很多新方法用于配电网规划，如遗传算法^[5]等。我国学者在配电网变电站规划领域也开展了富有成效的研究，提出了很多模型和算法。如运用运输问题模型来校核变电站的最佳位置、容量和供电范围^[6]，采用混合整数规划法和分枝定界法求解规划问题^[7]，而且提出了无需提供待选站址的变电站选址、定容的算法方案^[8,9]。
目前已有的规划、优化算法大都是利用启发式算法或近似算法，但这些算法在求解变电站供电范围时往往缺少有效的手段。Hopfield神经网络通过使能量函数降到最低值的方法可以成功地求解类似复杂的组合优化问题。旅行商问题(TSP)就是Hopfield神经网络成功应用的一个典型实例。本文利用贪心算法(greedyalgorithm)求出变电站容量问题的初始可行解，然后用Hopfield神经网络优化变电站供电范围及新建站址，最后求得配电变电站规划、优化方案。实例计算表明该方法可以取得较好的规划效果。

2数学模型
对文献[8]的数学模型做了改进后的配电变电站规划优化的数学模型为

式中s_i为变电站i的带载容量；W_j为负荷点j的负荷值；N为规划后变电站数；f(S_i)为变电站i计及土地费用后的投资；u(S_i)为变电站i的年运行费用；J_i为变电站i所供负荷点编号的集合；ξ为地理复杂系数；d_ij为变电站i和负荷点j之间的直线距离；L(W_j)为和W_j对应的变电站出线单位长度建设费用；α₁为电价；α_2j为和W_j对应的变电站出线的单位长度电阻；α₃为年损耗小时数；U为线电压；cosφ为功率因数；r₀为贴现率；S_i为变电站i的标称容量；e(S_i)为变电站i的运行率；T为折旧年限。
变电站的费用中包含土地费用，情况十分复杂。本文假设各点单位面积的土地费用一致。这样，变电站费用的差别就取决于其主变的情况。从实际情况出发，可约定：一个城市中的主变压器类型不超过3种，每座变电站的主变2-4台。变电站的可选带载容量构成其可选带载容量集合，该集合中元素的个数不超过9种。参加规划的已有变电站可选带载容量集合可能各不相同，但新建变电站的可选带载容量集合是相同的。
如果直接求解式(1)和(2)，则必须同时考虑集合量、连续量、离散量和整数，但目前尚无完善的数学方法。因此，本文确定的规划策略为：首先利用贪心算法确定新建变电站的座数及各座变电站的容量，将其作为初始可行解，进而利用Hopfield神经网络求解新建变电站的位置及各变电站的供电范围，再根据各变电站的实际供电情况对变电站容量进行减容，最终求得满足式(1)和(2)的最优解或近似最优解。

3用贪心算法求初始可行解
贪心算法(greedyalgorithm)是一种在数学上每步都按照最优度量法取局部最优，最后求解的方法。本文利用贪心算法求变电站容量问题的初始可行解。具体计算步骤如图1所示。
图1中各带载容量s_i所对应的价性比C_csi为

显然，以图1所示方法求得的解是刚好满足容量要求的总价性比最优的可行解。
在此基础上，利用Hopfield神经网络求解各变电站供电范围及新建变电站站址，同时进一步校核各变电站的容量，将定容、定供电范围、定新建站站址联系起来同时确定。

4定站址、定供电范围的神经网络法
在确定了新建变电站数和各座变电站的容量后，规划的目标是求C_L的最小值，即近似等效为求的最小值。显然，这和供电范围密切相关。用常规方法划分变电站的供电范围是比较困难的，因此本文利用Hopfield神经网络来求解各变电站的供电范围，通过反复迭代计算最终求得新建站的位置及其供电范围和容量。具体的算法框图如图2所示。图中铜心的定义及求法可参见文献[10]。
为了用Hopfield神经网络求解各变电站的供电范围，必须建立表明规划状态的神经网络模型，为此本文建立了如表1所示的矩阵。表中，A₁-A_n表示n个变电站；B₁-B_{[1][2][3]下一页}