网架规划中现代启发式算法的研究

摘要：全面介绍了应用于网架规划中的各种现代启发式算法的思想、步骤以及在此基础上的电网规划方法；并就各自特点做出对比总结。
关键词：网架规划；现代启发式算法；蚁群算法；遗传算法；进化规划；免疫算法
1 引言
网架规划是电力系统规划的重要组成部分，其任务是根据规划期间的负荷增长及电源规划确定相应的电网结构，以满足经济可靠地输送电力的要求。过去电网规划方法有传统启发式和数学优化两大类，随着电力系统的发展以及其自身的特点，上述两种方法已很难满足实际要求。
近年来，一类基于生物学、物理学和人工智能的具有全局优化性能、鲁棒性强、通用性强且适于并行处理的现代启发式算法得到了发展。它比较接近于人类的思维方式，易于理解，用这类算法求解组合优化问题在得到最优解的同时也可以得到一些次优解，便于规划人员研究比较。此类算法主要有：遗传算法、进化规划、免疫算法、蚂蚁算法。
2 遗传算法
2.1 算法思想
遗传算法借用了生物遗传学的机理，通过编码将规划方案转变为一组组染色体，并列出一组待选方案作为祖先（初始可行解），以适应函数的优劣来控制搜索方向，通过自然选择、杂交和变异等操作，实现各个个体适应值的提高，将自然选择这一法则应用于科学研究和工程技术中的许多优化问题。
2.2 基于遗传算法的电网规划方法
1. 变量：变量有决策变量和状态变量两类。决策变量表示输电线路是否被选中加入网络。遗传算法中将每条待选线路作为染色体中的一个基因，用一位二进制码来表示，基因值为1时，表示本线路被选中加入网络；否则反之。例如当其网络有7条待选线路且染色体为 1011101时，说明规划中是将第1、3、4、5、7待选线路加入电网。状态变量表示线路的运行状态，如线路潮流、节点电压等。状态变量一般是实数型变量。
2. 约束条件：考虑线路过负荷约束和潮流方程约束。
3. 目标函数：规划目标应使总的费用为最小，对于给定的运行方式各条线路均不出现过负荷；若经济性只计及线路的建设投资费用，目标函数可写成：

式中C --待选线路i的建设费用； Z --染色体中的i位基因的值； l--待选线路总数； --线路出现过负荷的惩罚系数；P --线路i的有功潮流； P --线路i的传输容量。
4. 适应值：适应值要反映电网规划的目标及要求，即要使规划方案的建设投资最小且不出现过负荷。习惯上按从大到小来排列适应值，因而将其规定为：

式中C --事先给定的较大常数。
5. 运算流程如下图所示：

3 进化规划
3.1 算法思想
进化规划是模拟进化优化方法的一个分支，它模拟生物进化过程，通过变异、竞争、选择等算子的作用，得到优化结果。
3.2 基于进化算法的电网规划方法
在满足己有线路不过负荷的条件下，求得投资和运行费用最节省的扩展方案，在线性潮流估计的规划模型中目标函数为：

其中，N为网络结点数；第一项为网络中所有原有线路的年运行损耗费用；第二项为所有新建线路的年费用（总投资*投资效益系数＋年运行损耗费用）；P 、P 分别为现有线路上由i流向j和由j流向i的有功功率；OP 、OP 分别为新建线路上由i流向j和由j流向i的有功功率；l 为线路长度；L 为原有线路的损耗系数；G 为新建线路的投资乘投资效益系数加上损耗系数。

将P 、P 、OP 、OP 作为决策变量，同时考虑等式约束，对其中的自由变量进行排序，形成码串，每个码对应于一个变量。将目标函数Z跟适应值函数联系起来。而不等式约束以惩罚因子的形式在适应值函数中体现出来。
4 免疫算法
4.1 算法思想
免疫算法的思想来自模拟人体的免疫系统，并从体细胞理论和网络理论中得到启发，实现了类似于免疫系统的自我调节功能和生成不同抗体的功能。
4.2 基于免疫算法的电网规划方法
1. 电网规划的目标是在满足线路不过负荷的条件下，求得最优网络扩展方案。即投资最少的扩展方案，其目标函数为：

其中，n 是第i条待选线路的回路数，l 是相应的长度，c 是单位长度的投资。其约束条件为线路不过负荷。
2. 运算流程如上图所示：
5 蚁群算法
蚂蚁算法仿照蚂蚁群觅食机理，构造一定数量的人工蚂蚁，每个人工蚂蚁以路径上的荷尔蒙强度大小（按照一定的状态转移准则）选择前进路径，并在自己选择的行进路径上留下一定数量的荷尔蒙（进行荷尔蒙强度的局部更新），当所有蚂蚁均完成一次搜索后，再对荷尔蒙强度进行一次全局更新。通过反复的迭代，最终大多蚂蚁将沿着相同的路线（最优路线）完成搜索。该方法的主要特点是：正反馈、分布式计算、与某种启发式算法相结合，正反馈过程使得该方法能很快发现较好解；分布式计算使得该方法易于并行实现；与启发式算法相结合，使得该方法易于发现较好解。应用表明，其算法效率、寻优能力均强于目前己有的其它现代启发式优化算法，适宜于求解有约束问题，有着广阔应用前景。目前有学者尝试将其应用于电网规划中但是还没有很好地将规划模型处理成适合于蚂蚁算法求解的模型，系统规模增大时，难以求得高质量的解。如何合理地将规划模型转变成适合蚂蚁算法的模型，有待人们进一步的研究。
6 各种算法的总结对比

1. 遗传算法的显著优点是可以同时搜索空间中的许多点，而不是一个点，因而能够作到全局优化；由于其搜索最优解的过程是有指导性的，避免了某些优化算法的维数灾难问题。利用遗传算法进行电网规划，可得出若干个最优、次优方案，供规划人员根据实际情况进行决策选择。
但遗传算法也存在计算速度慢，有时会收敛到局部最优解等不足，目前对此也进行了一些改进和研究。例如，考虑到模拟退火算法可以有效防止陷入局部最优解这一特性，将模拟退火和遗传算法结合的混合遗传－模拟退火算法取得了不错的效果。
2. 进化规划不需要对变量进行编码和解码，它跟遗传算法相比．更适合于连续优化问题。 遗传算法在迭代次数和计算时间上显示出优越性。但可以对进化规划作进一步的改进，以减少迭代次数和计算时间。如利用遗传算法给出候选方案，再利用进化规划进行潮流计算。
3. 免疫算法与以上两种算法之的区别在于它在记忆单元基础上运行，确保了快速收敛于全局最优解；由于在免疫算法中考虑了抗体的亲和性，使与抗原亲和性高的抗体生存几率较大，又由于考虑了抗体的期望值，有效地抑制了高密度抗体的繁殖、从而使得免疫算法在全局寻优的性能方面要优于遗传算法。
_xyz