[科普中国]-相关性回溯法

相关性回溯法，实际上一个类式枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解及关联程度，当发现已不满足求解条件时，就‘’回溯‘’返回，利用相关优势尝试别的路径。

广度优先回溯算法的试题搜索算法结合回溯算法的特点和试题的相关性，采用广度优先策略改进了回溯算法。 通过分析试卷资源的数学模型，提出了基于广度优先回溯算法的试题搜索算法。 实验证明：该算法减少了试题搜索中的冲突，提高了题库系统的智能性。1

试题相关性定义运算‘’∧‘’。 tdi ，tdj∈Td，有形如tdi∧tdj=max ( td1 ，td2 ，td3 ，td4 ) 运算，若tdi ∧tdj=1，则称tdi ,tdj为相关; 否则，为无关，i，j=1，2…n。 在题库中，tdi ，tdj的相关性通过阈值△( 事先输入) 控制，一般情况下，只要tdi∧tdj≥△，即相关。1

优先思想的回溯算法对安排的候选试题进行检测，若无冲突，则作为候选试题; 若有冲突，则根据相应约束条件对发生冲突的试题进行回溯重排。 回溯时要降低冲突的扩大，避免回溯雪崩的发生。

回溯法是满足一定约束条件的穷举式搜索法，其搜索方式与树的深度优先搜索方式相似，它按选优条件向前搜索，直到达到目标。 当搜索到某一步时，发现原先的选择并不优或达不到目标时，就退回一步重新选择。 由于规定选优必须满足一些约束条件，故需搜索的空间大大减少，但这种回溯法，无法解决求解过程中先前的解分量对后续解分量造成的冲突，为此，提出一种基于广度优先思想的回溯算法。1

复杂度最好的情况，不经过回溯直接求到E中满足D的解，计算复杂度为n; 最坏的情况，所有分量两两相关，且每个分量xi都需穷举在定义域中的值，才得到解，计算复杂度为m。 由此可知，基于广度优先的回溯法适用于解分量之间相关性较小的问题。1

多风电场相关性的场景概率潮流计算针对结合K-means聚类和Copula函数建立场景概率模型时，K-means聚类不能根据风电出力数据分布特点自发确定最佳聚类数这一不足，提出通过基于密度的聚类有效性指标确定最佳聚类数。并以此建立最优场景概率模型，采用改进型回溯搜索算法(BSA)进行无功优化。以澳大利亚的两个相邻风电场实测出力为例，在含多风电场的 IEEE30节点系统中对所提方法进行验证，算例结果表明采用所提方法确定的最优场景概率模型能准确描述多风电场输出功率之间的相关性。2

Copula函数Copula函数能够将多维随机变量的联合分布函数与各自的边缘分布函数连接起来，主要用于描述随机变量之间的相关性，其不同Copula函数对随机变量相关性的描述具有明显差异。在利用Copula函数描述K-means聚类处理后的不同类别的相关风电出力数据时，相关问题说明如下：

(1) 采用非参数核密度估计法求取风电出力边缘分布函数；

(2) 采用欧式距离法来确定最优Copula函数。2

改进型BSA回溯搜索算法(BSA)是由Civicioglu在2013年提出来的一种新型进化算法，具有全局搜索能力强、收敛速度较快的优点，为进一步提高收敛精度，防止陷入局部最优，本文参考文献[17]对 BSA 算法进行改进，改进后的BSA 算法步骤如下。

(1) 种群初始化操作

BSA的种群初始化操作包括在约束条件内随机产生种群P和历史种群oldP 。设种群的规模为N ，种群的维度为D ，那么第i 个个体向量可以表示为Pi=(Pi1，Pi2 ,…，PiD ) ，其中每个个体都利用公式进行种群初始化。

(2) 选择I操作

选择I操作用历史种群计算搜索方向，BSA在每次迭代开始之前，都要进行选择操作，满足条件则重新定义历史种群，不满足条件则继续下一步操作。

(3) 变异操作

BSA获取变异种群的方式为：Mutant=P+F·(oldp-p)。

式中F是变异尺度系数，用于控制变异的幅度，基本BSA中F的选取方式如式为：F=3·randn 。

(4) 交叉操作

基本BSA在进行交叉操作时首先选择一个交叉长度n ，然后从上一代种群P中随机选取n个元素与Mutant中的相同位置个体的同维元素进行互换，以此产生新的个体。n的每一次取值都有两种交叉策略。

(5) 选择II操作

BSA的选择II操作会对种群父代和子代的个体适应度进行比较，当子代的个体适应度小于父代时，则用子代个体更新父代，否则不进行更新。2

多风电场相关性的电力系统的运行状态考虑多风电场相关性的概率潮流计算关键在于建立多风电场出力的场景概率模型。针对场景概率模型建立过程中K-means 聚类不能根据风电出力数据的分布特点自发确定最佳聚类数的不足，提出通过分析K-means聚类的基于密度的有效性指标来确定最优场景概率模型，结论如下：

(1) 通过对比分析场景数分别为2~10的场景概率模型对实测数据样本模拟精度以及实算概率潮流的还原情况，结果表明，根据DBI指标所确定的最优场景概率模型，能够得到更准确的模拟样本、获得更精确的潮流计算结果。

(2) 在含多风电场的IEEE30节点系统中采用改进回溯搜索算法对考虑多风电场相关性的电力系统进行多目标无功优化，得到了各场景下使得目标函数精确度更高的最优控制策略。

所提的方法可用于分析考虑多风电场相关性的电力系统在不同场景下的运行状态，让运行与规划人员制定相应的控制策略，使系统以最大概率运行在最优状态下。2

本词条内容贡献者为:

王沛 - 副教授、副研究员 - 中国科学院工程热物理研究所