1.一种求解电网解裂问题的迭代局部搜索方法,其特征在于:所述方法包括以下步骤:步骤一:使用两阶段方法生成可行的初始解,并将初始解作为现有解;
所述步骤一中的两阶段初始化方法为:第一阶段,对每一个子集 构造斯坦纳树Ti,使得 中所有节点都位于树Ti中,由斯坦纳树Ti生成的所有节点和边均视为的组成部分;第二阶段,在保证各子图中所有节点满足连通性约束和输电容量约束的条件下,将剩余的负载节点逐一地随机分配给与其邻接的一个子图,直到所有节点分配完成,所得到的K组划分 即为可行的初始解;
步骤二:对现有解执行局部搜索程序,获得局部最优解并将其作当前解s0;
所述步骤二中对现有解执行局部搜索的方法包括以下步骤:b
步骤2.1:输入一个现有解s,并将其作为局部最优解s;
步骤2.2:用单点移动操作来构造现有解s的邻域N(s);
步骤2.3:在邻域N(s)中搜索现有解s的一个邻居解s'(s'∈N(s)),并将s'作为邻域N(s)中的最佳改进解snb;
步骤2.4:检测邻域N(s),根据代价函数对搜索到的每一个邻居解s'∈N(s)进行质量评估,若C(s')<C(snb),说明该邻居解s'的质量优于解snb,将质量优的邻居解作为新的邻域最佳改进解snb;反之则搜索下一个邻居解,并将其与邻域最佳改进解snb进行质量对比;如此不断更新,直到邻域N(s)中不存在质量更优的候选解时,迭代停止;
步骤2.5:对snb进行质量评估,并将其与现有解s比较,若snb质量优于现有解s,则将snbb b作为新的现有解s,同时更新局部最优解s ,令snb为新的局部最优解s ,转入步骤2.2;若snb质量不优于现有解s,说明该邻域中不存在质量优于现有解的最佳改进解,局部搜索程序结b束,输出局部最优解s,完成局部搜索;
步骤三:设置扰动强度k为kmin,令kmin=10+0.01*|VL|,VL表示负载节点集合,同时将当*前解s0作为最优解s;
步骤四:设置截止时间tmax并计算运行时间,当运行时间未及tmax时,转入步骤五,当运行时间到达tmax时,转入步骤九;
步骤五:执行扰动程序,以扰动强度k对当前解s0进行扰动,获得扰动解s';
所述步骤五中的执行扰动程序的方法步骤如下:
步骤5.1:输入当前解s0和扰动强度k;
步骤5.2:设变量c为0,由步骤2.2中构造邻域的方法获得当前解的单点移动邻域N(s0);
步骤5.3:从当前解的邻域中随机选择一个邻居解s',将s'作为一个扰动解sb,变量c的值增加1;
步骤5.4:由步骤2.2中构造邻域的方法获得扰动解的单点移动邻域N(sb),并从中随机选择一个邻居解s'b作为新的扰动解sb,变量c的值增加1;
步骤5.5:比较c和k,若c<k,转入步骤5.4;若c≥k,扰动程序结束;
步骤六:使用步骤二中的局部搜索方法对获得的扰动解进行优化,得到局部最优解s”;
步骤七:对当前解s0和s”进行质量评优,即将二者的代价函数作比较,若C(s”)<C(s0),说明当前解经过扰动和局部搜索之后得以改进,则将s”作为当前解s0,并转入步骤三;若C(s”)≥C(s0),说明当前解经过扰动和局部搜索之后没有得到改进,则增加扰动强度k,令k=k+kstep,kstep=(kmax‑kmin)/Q,Q=60,再转入步骤八;
步骤八:设kmax=β*|VL|,β=0.8,若扰动强度k<kmax,直接转入步骤四,否则先将k重置为kmin,再转入步骤四;
*
步骤九:当运行时间到达tmax时,算法结束,返回最优解s。