1、基于改进教与学优化算法的最小断点集求解高漪，石恒初，孔德志，游昊，陈璟，陈金富（强电磁工程与新技术国家重点实验室（华中科技大学），湖北 武汉 ；云南电力调度中心，云南 昆明 ）摘要：对继电保护装置开展合理的整定计算工作是保障电网安全稳定运行的重中之重。环网继电保护整定过程中可能出现“死锁”问题导致整定无法进行，需要寻找网络最小断点集（，）以解开“死锁”。实际工程中，由于电网运行状态或评价角度的改变，被选作最优断点集的一组 应当更新。针对该问题，致力于寻找一种能够快速高效地找到网络拓扑中尽可能多组 的方法，为更新当前最优断点集提供可能。将寻找 的问题归结为求解一个整数二次规划问题，引入教与学优化
2、算法，并对算法进行一定改进以提升搜索性能。与其他启发式算法相比，该算法只需要设置较少的超参数，可行性较高；并且收敛性好，能够以较少的迭代次数得到全局解；同时，该算法一次独立计算能够得到足够多组 ，为在工程实际中结合电网运行参数确定环网最优断点集提供条件。通过算例验证了该方法的有效性。关键词：图论；最小断点集；电力系统保护整定计算；教与学优化算法中图分类号：，（），；，）：，（），：；基金 项 目：中 国 南 方 电 网 有 限 公 司 创 新 项 目 资 助（编 号 ）收稿日期：作者简介：高漪（），硕士研究生，研究方向为电力系统继电保护整定计算；陈金富（），通信作者，博士，研究员，硕士生导师，
3、研究方向为电力系统分析计算、人工智能在电力系统分析计算中的应用等。引言随着电力系统不断发展，网络拓扑结构的日益复杂化给继电保护整定工作带来了困难。确定大规模复杂环网方向保护的最优配合关系是现代电力系统继电保护整定计算领域的一个关键问题，解决该问题的核心是确定全网最小断点 集（）。年，和 在文献 中首次介绍了基于图论的断点求取算法，并率先提出了“双向回路矩阵”“相关顺序矩阵”等概念。早期的基于图论的方法，首先用基本回路线性组合法或深度优先搜索回溯法找到拓扑图中的有向简单回路，再用布尔代数法获得环网的最小断点集，此类方法应用在大规模电网中计算量较大、效率较低。为提高计算效电力自动化电工技术 率，文
4、献 中使用函数相关算法，利用关系代数中的函数依赖概念表示各保护之间的依赖关系，从而定义各保护之间相关性的函数表达式来进行断点集的求取；文献 中提出用网络的关联矩阵求取断点的方法；文献中根据网络特性及断点在网络拓扑中的位置特性求取断点集。这些方法一定程度上提高了计算速度，但不能保证找到断点数目最小的集合且难以同时求取多组相同基数的断点集，存在一定不足。随着智能算法的发展，遗传算法（）、粒子群优化算法（）、蚁群算法（）、人工蜂群算法（）等启发式算法也被应用到求解 的问题中。这些算法求解问题快速、高效，能够找到断点数目最小的集合，但算法设计过程复杂，需要设置合理的超参数，实现难度较大，并且易陷入局部
5、最优，无法保证找到的 为工程最优解，无法根据实际需求更新 。教与学 优 化 算 法（，）的出现为解决此问题提供了新的思路，该算法已成功应用于电网中布局、无功优化、继电器时间配合优化 等问题。本文将教与学优化算法进行改进，将其应用于寻找网络 的问题中。仿真结果表明，基于改进教与学优化算法求解 具有良好的优越性。教与学优化算法教与学优化算法是由 等人于 年提出的一种新的启发式优化算法。该算法基于现实课堂中教师的教学过程与学生的学习模式，提高每个个体的学习成绩。该算法超参数少、收敛速度快、全局收敛性好，并且能够输出一个或多个最优解（具有相同目标函数值），具有良好的优越性。教与学优化算法包含“教”与“
6、学”两个阶段。假设班级中共有 个学员，教师是这 个学员中成绩最好的个体，学员需要学习 门课程；映射优化搜索空间维度数目为 ，搜索点数目为 。搜索空间表示为，、分别为搜索空间的上、下界；搜索点表示为（，），。（）“教”阶段。要提高班级中每个个体的成绩，首先选择当前成绩最好的一名学员作为教师，记为 ，教师通过教学的方式提高班级成绩。在此过程中，除教师外的学员（，且 ）基于教师与全体学员平均值间的差异进行学习：（）（，）（）式中，和 分别为第个学员学习前和学习后的成绩；为教师对学员的教学内容；为第 次学习过程中全体学员成绩的平均值；取之间的随机数为学习步长，以表征不同学员的学习能力；为教学因子，表征
7、教师的教学能力。学员经过“教学”后，评估学习结果，若学习成绩（）提高，即（）（），则将 更新为 ，否则保持不变。（）“学”阶段。经过“教”阶段后，学员的整体成绩有了提高，但各学员仍然未达到最优成绩。此时采取学员间相互学习的方式，提高各个体成绩。每个学员（，）随机选取另一学员（），通过分析自己和学员间的差异进行学习调整：d d （）（）（）（）（）式中，d 为学员与学员之间的学习内容；仍取之间的随机数为学习步长，以表征学员的学习能力；（）为学员的学习成绩。学员经过“相互学习”后，评估学习结果，若学习成绩（）提高，即（）（），则将 更新为 ，否则保持不变。（）终止条件。与其他启发式优化算法类似，教
8、与学优化算法在迭代初期能够显著提高学员成绩，但在迭代后期对学员成绩的提高并不明显，需要合理设置终止条件使得算法在有限步骤内结束。通常，当连续两次迭代学员成绩变化在一定范围内或学员平均成绩达到预定值或迭代次数达到预定最大值时，算法终止。最小断点集问题求解为求解环网最小断点集问题，首先根据断点问题产生的本质对网络拓扑进行化简；接着用数学语言描述待求解问题，即建立数学模型；再以适用于问题描述的改进二进制形式教与学优化算法进行求解。网络化简对于大规模复杂环网，网络结构中回路数目众多，回路数目随着网络规模的扩大呈现指数型增加。若不进行有效的网络化简，直接依照拓扑图的关系寻找全网断点集是不符合工程应用且不
9、切实际的。网络化简 步骤如下。（）进行全网保护的预整定，只保留产生“死锁”的保护配合关系图。产生“死锁”需要满足两个必要条件：一是所有的保护配合关系处于同一有向回路中；二是这些保护的配合关系必须为同段配合。因此，首先进行全网保护的预整定，去除不同时满足两个必要条件的保护，形成保护配合关系图，准确减小网络规模。（）对于存在薄弱边或薄弱点的弱连通保护配合关系电工技术电力自动化图，将其在薄弱边及薄弱点处进行分割，分解成若干个连通子图。此时，原连通图的断点即为若干连通子图的断点之和，只需分别对各连通子图求取断点即可，减小单次求解断点的网络规模。（）对每个有向连通子图，若图中含有根节点，则去除根节点及与
10、该节点相连的有向边；若图中含有派生点，则将派生点进行组合。至此，网络拓扑有向图化简完毕。对化简后的有向图确定其所有简单回路，形成完全简单回路矩阵。完全简单回路矩阵 的每一行代表一个有向简单回路；每一列代表一条有向边，即环网中对应的方向保护继电器。矩阵 中仅包含和两个元素。若 中第行、第列元素 为，则表示第个有向简单回路包含编号为的有向边；若 中第行、第列元素 为，则表示第个有向简单回路不包含编号为的有向边。数学模型建立寻找电网的最小断点集即是寻找数目最少的能够断开网络中所有存在“死锁”问题的有向回路的保护组，也就是寻找有向图的完全简单回路矩阵的最小覆盖。所谓矩阵的覆盖，是指矩阵的一些列的集合，
11、在这个集合中，矩阵的每一行都能至少找到一个元素是该行的非零元素。矩阵的最小覆盖，就是集合中所含元素数目最少的覆盖。映射到最小断点集的问题中，如果将完全简单回路矩阵的最小覆盖所对应的保护断开，那么就断开了每一个有向回路，这就解开了“死锁”。故寻找最小断点集的过程即是寻找矩阵 最小覆盖的过程。记所有个保护集合，若选择保护为断点，则，否则，其中，。寻找最小断点集的问题归结为欠定方程组的求解问题：，（，）（）式中，（，）为矩阵 的行数，即为图中所有简单回路个数；为断点集中包含的断点数目，对任一确定的网络拓扑，中包含的断点数 为确定值。求解欠定方程组的问题等价为求解一个整数二次规划问题：（），（，）（）
12、改进教与学优化算法过程下面采用教与学优化算法求解上述问题，并对基本教与学方法进行改进，以期得到更好的性能。初始化首先设定迭代次数及初始断点集规模。假设随机生成 个断点集（学员），每个断点集中包含 个元素表示网络中的所有保护（课程），用矩阵 表示所有断点集中的断点选择情况（学习情况）。矩阵 中所有元素用或表示，若矩阵中元素为，则表示选择对应方向保护作为一个断点；若元素为，则表示不选择对应保护为断点。初始化生成的断点集满足二次规划问题约束条件，以保证断点集能够解开网络中所有产生“死锁”的回路。计算代价函数定义断点集的代价函数作为算法寻优的依据：（）（）式中，为矩阵 中第行、第列的元素，。断点集的代
13、价函数表示该断点集中 个保护对应元素的和。由于每个保护对应元素仅有、两个取值，因此断点集中所有元素的和即为该断点集中被选择为断点的保护数量。在寻找最小断点集的过程中，希望断点集代价函数取最小值，即对应断点集中断点数目最少。在算法中，将每个断点集的代价函数取值作为每位学员的学习成绩，代价函数取值越小，对应该学员成绩越好。算法目标为减小断点集代价函数取值并输出取值最小的断点集组，即提高学员学习成绩并输出最优学员的学习情况。“自学”阶段为进一步提高算法的全局搜索能力，将“自学”的过程引入算法流程，改进基本教与学优化算法。每位学员在“教”和“学”阶段之前先进行“自学”。在求取最小断点集的问题中，为一次
14、独立计算得到尽可能多的同基最小断点集，对初始化生成的断点集中元素进行随机更新（“自学”）：，（，）（）式中，和 ，分别为第个断点集的第个保护更新前与更新后的取值，即为矩阵元素 的值；，取间的 随 机 数 作 为 对 应 ，的 扰 动，。初始化生成的每个断点集经扰动后，检查代价函数（）。若代价函数减小，则说明此过程使得断点集中断点数目减少，将更新断点集中被选为断点的保护对应元素，否则仍然保留原断点集中元素。“教”阶段计算第 次迭代过程中所有断点集保护对应元素取值的平均值 ，并找出代价函数取值最小的一个断点集（教师），记为 。，表示所有断点集第个保护的平均取值；，为 中第个保护取值；以 ，表示断点
15、集（，且 ）中第个保护元素，根据 ，与 ，间的差异的调整情况，即：电力自动化电工技术 ，（，），（，），（，）（）式中，、，为相对应随机数。断点集元素，更新（“教学”）式为：，.，（）式中，和 ，分别为，更新前后的取值。断点集经过与当前最小断点集 相关更新后，检查代价函数（）。若代价函数减小，则说明断点集中被选为断点的保护数目减少，此次更新有效，否则仍然保留该断点集更新前的元素值。“学”阶段“教”阶段完成之后，更新断点集进入“学”阶段。每个断点集（，）随机选取另一断点集（），通过分析自身与另一断点集选择不同保护为断点的差异性进行学习和调整。记 为断点集与断点集的各保护对应取值之差，即：（）（）
16、（）（）（）式中，为一个 的行向量。断点集元素，更新（“相互学习”）式为：，d ，.，d ，（，）（）式中，和 ，分别为，更新前后的取值；，为相对应随 机 数；d ，为 行 向 量 的 第个元素。断点集经过与断点集相关的更新后，检查代价函数（）。若代价函数减小，则说明断点集中被选为断点的保护数目减少，将更新断点集中各保护取值，否则仍然保留该断点集在“学”阶段更新前的元素值。终止条件教与学算法是一种反复迭代的优化搜索算法，设置合理的迭代次数及初始化断点集个数（学员规模），可以使得算法以概率收敛 于 。所有迭代完成后，即可终止循环，输出一组或者多组 （最优学员）。算法步骤基于改进教与学优化算法（，）求解最小断点集问题的具体流程如图所示。算例分析 算例一：求解一典型网络所有 某具有典型保护配置的网络 如图所示。假设网图 基于改进教与学优化算法求解最小断点集问题的流程图络中所有保护间的配合均为同段配合，形成“死锁”。在 上形成网络有向图的完全简单回路矩阵 。设置不同初始化断点集数 ，考虑算法的随机性，将改进前后算法独立运行 次。统计设置不同 值得到的同基 组数平均值，对比教与学优化算法改进前后
