基因/禁忌组合算法在配电网
网架优化规划中的应用周玲　王兴念　丁晓群　颜自坚　李顺宗摘要　在比较了基因算法和禁忌算法各自优缺点的基础上,针对配电网网架优化规划中多约束、非线性和整数寻优的特点，提出采用基因/禁忌组合算法的策略，并应用于配电网网架优化规划。算例计算证明了该组合算法在配电网网架优化规划中应用的可行性和优越性。
关键词　基因算法禁忌算法组合算法配电网优化规划APPLICATIONOFGENETICALGORITHM/TABU
SEARCHCOMBINATIONALGORITHMINDISTRIBUTION
NETWORKSTRUCTUREPLANNINGZhouLing　WangXingnian　DingXiaoqun　YanZijian
HohaiUniversity
Nanjing,210098China
LiShunzong
TaizhouElectricPowerBureauTaizhou
Taizhou,225300ChinaABSTRACT　OnthebasisofcomparisonoftheadvantageandshortcomingofGeneticAlgorithm(GA)andTabuSearch(TS),aGA/TScombinationalgorithmisledindistributionnetworkstructureplanningwhichisnon-linear,non-differentiableandcombinatorial-constrainedoptimizationproblem.Thefeasibilityandefficiencyofthealgorithmareverifiedbytheresultofapplyingittoasamplesystem.
KEYWORDS　GeneticAlgorithm(GA);TabuSearch;combinationalgorithm;distributionnetworkstructureplanning;optimalplanning1　引言　　配电网网架优化规划可以减少停电、降低网损、提高供电质量，是实施配电网自动化的一个重要环节。但配电网网架优化是一个非线性整数优化问题，采用传统的数学优化方法，如线性规划、整数规划、混合整数规划等会常遇到搜索方向错误、迭代发散等问题。当变量和约束条件增多时，往往会陷入所谓的“组合爆炸”。
　　近年来发展起来的遗传算法(GA)和禁忌算法(TS)引起了各学科研究人员的普遍兴趣。这类方法适用于解决组合优化问题以及目标函数或某些约束条件不可微的非线性优化问题，在电力系统的优化调度、无功规划、配电系统中电容器的最优配置、机组检修计划、机组的最优组合和故障诊断、输电系统规划和城网规划等领域得到了广泛应用。但是由于基因算法速度慢，禁忌算法对初始值的依赖性强等原因，限制了它们在配电网网架优化规划中的应用。本文将基因/禁忌组合算法应用于配电网网架优化规划，取得了较好的效果。2　基因算法和禁忌算法2.1　基因算法(GA)^［1］
　　基因算法是求解全局优化问题的随机搜索算法，可以解决组合优化问题以及目标函数或某些约束条件不可微的非线性优化问题。
　　基因算法的主要步骤：
　　(1)产生初始解群体　计算开始时，产生一些待求优化问题的可能解，称为初始解群体，其中每个解称为个体。初始解群体可用随机方式产生，也可用其他优化方法或启发式方法给出。
　　(2)评价　定义一个适应度函数F，计算群体中每个个体相应的适应度f_i，f_i越大表示该个体适应度越高，更适应于F所定义的生存环境。
　　(3)选择　用某种方法从群体P(t)中选取n个串形成一个匹配集，匹配集是用于繁殖后代的双亲个体源。选择是遗传算法的关键，它体现了自然界中适者生存的思想。
　　(4)杂交　杂交是基因算法获得优良个体的重要手段。从代码群中随机选取两个作为双亲进行杂交，在杂交过程中，父代的部分码串遗传给子代，从而使优良特性被一代一代遗传下去。
　　(5)变异　变异是基因的一个很重要操作。它能使个体发生突然变异，导入新的遗传信息，使寻优有可能指向未探知区域，是提高全局最优能力的有效步骤，也是保持群体差异的重要手段。
2.2　禁忌算法(TS)^［2～3］
　　TS是一种亚启发式(meta-heuristic)随机搜索算法，它从一个初始可行解出发，选择一系列的特定搜索方向(移动)作为试探，选择实现让特定的目标函数值减少最多的移动。为了避免陷入局部最优解，TS搜索中采用了一种灵活的“记忆”技术，对已经进行的优化过程进行记录和选择，指导下一步的搜索方向，这就是Tabu表的建立。Tabu表中保存了最近若干次迭代过程中所实现的移动的反方向移动，凡是处于Tabu表中的移动，在当前迭代过程中是不允许实现的，这样可以避免算法重新访问在最近若干次迭代过程中已经访问过的解群，从而防止了循环，帮助算法摆脱局部最优解。另外，为了尽可能不错过产生最优解的“移动”，TS搜索还采用“释放准则”的策略。
　　禁忌算法的主要步骤：
　　(1)移动　TS搜索过程由“移动”来实现，一次“移动”产生一个实验解。现已有多种“移动”方法。
　　(2)Tabu表　Tabu表中允许储存的Tabu“移动”的最大数目称为Tabu表规模。如何给定Tabu表的规模对寻优过程有重要的影响。一般而言，应随问题规模的增大而增大，但如何给定其最优数值仍是一个有待研究的问题。
　　(3)释放水平　TS对Tabu表中的Tabu“移动”都赋予一个释放水平。如果一个Tabu“移动”达到了释放水平，则该“移动”不被限制，可以实现，即可作为下一步的搜索方向。释放水平的作用是为了在每次迭代中能实现最有价值的“移动”，从而可更有效地找到最优解。
2.3　基因算法与禁忌算法各自的缺点
　　(1)基因算法(GA)的缺点
　　GA在进化搜索过程中，每代总要维持一定规模的群体。若群体规模小，含有的信息量也少，不能使GA的作用得到充分发挥；若群体规模大，包含的信息量较大，但计算次数会激剧增加，因此限制了GA的使用。另一个缺点是“早熟”。造成这种成熟前收敛的原因：GA中重要的遗传算子——交叉算子使群体中的染色体具有局部相似性，父代染色体的信息交换量小，从而使搜索停滞不前；变异概率太小，以至于不能驱动搜索转向其他的解空间进行搜索。此外，GA的爬山能力较差。
　　(2)禁忌算法(TS)的缺点
　　尽管TS的搜索速度比GA快，但TS对于初始解的依赖性较强。一个好的初始解可使TS在解空间中搜索到更好的解，而一个差的初始解则会降低TS的收敛速度，搜索到的解也相对较差。TS的另一个缺点是搜索只是单-单操作，即搜索过程中初始解只能有一个，在每代也只是把一个解移动到另一解，而不象GA那样每代都是对多个解进行操作。3　基因算法/禁忌算法的组合算法　　把GA和TS算法进行组合，扬长避短，形成了多样性和收敛性都较好的新算法。GA和TS算法的组合策略主要有两种。
3.1　改进的基因算法(IGA)^［4］
　　改进的基因算法，针对GA爬山能力差的缺陷，把TS作为GA的变异算子来提高GA的爬山能力。这样综合了GA具有多出发点和TS爬山能力强的特点，克服了GA爬山能力差的弱点。其具体步骤如下：
　　①参数设置：最大代数N_gen、群体规模N_pop、交叉概率P_c、变异概率P_m；
　　②令t＝0，生成初始群体；
　　③计算当前代群体染色体的适应值；
　　④选择；
　　⑤重组。生成0、1之间的随机数r_i(i＝1，2，…，N_pop)，如果r_i≤p_c，则交配池中第i个染色体作为交叉的父代，产生均值为p_c×N_pop个的父代染色体，然后对每对双亲进行交叉操作，产生两个子代。
　　⑥变异。生成0、1之间的随机数r_i(i＝1，2，…，N_pop)，如果r_i≤p_m，则调用禁忌算法(TS)对交配池中第i个染色体进行变异操作。t＝t＋1，如果t<N_gen，则转③，否则输出最优解，终止算法。
3.2　改进的禁忌算法(ITS)^［4］
　　改进的禁忌算法针对TS对初始值依赖性较强的特点，引入GA算法为其找到较好的初始点，加快收敛速度，提高解的质量。算法实现过程如图1所示。图1　改进的禁忌算法框图
Fig.1　Flowchartofimprovedtabusearch
N—可行点个数,MAXGEN—基因法中最大迭代4　GA/TS组合算法在配电网网架优化规划中的应用4.1　目标函数的建立
　　所谓配电网网架优化问题是指在满足用户用电、保证电能需求的前提下，对各种可能的网架、线路回数、导线截面等方案进行比较，选出最优方案或次数,MAXTB—禁忌法中最大迭代次数次优方案作为规划和改造的方案。其目标函数一般应考虑的因素有：投资、可靠性、环保约束、生产费用、网损。目前，配电网的规划一般都考虑投资、网损、生产费用三项。本文以年综合费用最小为目标函数，其具体的公式如下：式中　Z_i为(0，1)变量，当支路i新建时取1，否则取0；T_{[1][2]下一页}