1.一种求解配电网传感器区域覆盖问题的迭代的局部搜索方法,其特征在于:所述方法包含如下步骤:步骤1:基于配电网传感器区域建立坐标系,构造用于评估未覆盖的面积大小的评估函数,建立配电网传感器区域覆盖问题的数学优化模型;
步骤2:输入表示传感器的小圆个数N,待覆盖的圆形区域的初始半径R0和小圆半径r;设定参数,包括最大时间限制MaxTime,最大搜索深度MaxNo Im p1,局部搜索算法的精度ρ,合法解的判定标准Elegal,扰动算子的扰动强度δ,最大搜索深度Q和惩罚因子α;
步骤3:令当前搜索时间Time=0;
步骤4:随机生成一个由N个小圆的布局X0和圆形区域初始半径R0构成的初始解S0,即S0=(X0,R0),然后利用拟牛顿算法对其进行局部优化,并记录其势能函数值 其具体步骤如下:步骤4.1:在初始半径R0的圆形区域内随机放入N个点,分别作为N个小圆的圆心;
步骤4.2:利用拟牛顿算法,对N个圆构成的布局进行局部优化,并记录其势能函数值步骤5:如果搜索时间Time未达到最大时间限制MaxTime,则转到步骤6,否则转到步骤
9;
步骤6:执行迭代的局部搜索方法ILS,其步骤如下:步骤6.1:将初始解S0记作当前解S1,令当前当前搜索深度Iterations1=0;
步骤6.2:对当前解S1中N个圆心坐标(xi,yi)i=1,2,...,N执行扰动强度为δ的一致随机扰动,即xi=xi+δ·θ,yi=yi+δ·θ,i=1,2,...,N,其中θ是一个在区间[‑1,1]范围内的随机数;
步骤6.3:利用拟牛顿算法,对扰动后的布局进行局部优化,所得解记为解S2,并记录其势能函数值步骤6.4:如果更新解S2的势能函数值 小于当前解S1的势能函数值 则转到步骤6.5,否则转到步骤6.6;
*
步骤6.5:最优解S 更新为S2,即 并设置当前搜索深度Iterations1=0;
* *
步骤6.6:则现有解S1更优,将其用于更新最优解S ,即S=S1, 并将当前搜索深度Iterations1加1;
步骤6.7:如果当前当前搜索深度Iterations1小于最大搜索深度MaxNoImp1,则转到步骤6.2,否则转到步骤6.8;
*
步骤6.8:输出最优解S;
*
步骤7:如果最优解S为合法解,即 则转到步骤8,否则转到步骤4;
* * *
步骤8:基于罚函数法对圆形区域的半径和布局(即S=(X ,R))进行调整,并保存当前*解为最优解S,其具体步骤如下:
*
步骤8.1:输入一个合法的最优解S;
步骤8.2:令当前搜索深度Iterations2=0;
步骤8.3:如果当前搜索深度Iterations2小于最大搜索深度Q,则转到步骤8.4,否则转到步骤8.6;
*
步骤8.4:调整最优解S的整圆形区域半径,并放大惩罚因子α,即α=10·α;
步骤8.5:当前搜索深度Iterations2加1,然后转到步骤8.3;
*
步骤8.6:输出最优解S,转到步骤4;
*
步骤9:输出最优解S。
2.根据权利要求1所述的一种求解配电网传感器区域覆盖问题的迭代的局部搜索方法,其特征在于:步骤1所述的配电网传感器区域覆盖问题的数学优化模型ER(X)与布局X,其具体定义如下:配电网传感器区域覆盖问题描述为:在半径为R的圆形区域中,放置N个传感半径为r的传感器,即将传感器用N个半径为r的小圆表示,要求小圆将圆形区域全部覆盖,目标是使圆形区域的半径R达到最大;
对配电网传感器区域覆盖问题进行数学建模,以区域的中心为坐标原点(0,0)建立笛卡尔坐标系,假设区域内第i(i=1,2,...,N)个传感器的小圆的圆心坐标为(xi,yi),每个小圆半径为r,对于给定的圆形区域半径R,为了测量区域被覆盖的程度,构造以下的评估函数,用于评估未覆盖的面积大小:
2N
其中X∈R 为圆心的坐标向量,即X=(x1,y1,x2,y2,...,xN,yN),Stot表示待覆盖区域的面积,Sij表示第i个圆和第j个圆之间的重叠面积,Sijk表示3个圆i、j、k的公共重叠面积,Si0表示第i个圆超出待覆盖区域的面积,S0ij表示第i个圆和第j个圆重叠面积超出待覆盖区域的部分,且Sij、Sijk、Si0和S0ij依赖于圆形坐标向量X;势能ER(X)表示未被覆盖的面积,ER(X)=0表示待覆盖区域已被完全覆盖,当前解为合法解,因此为了找到一个合法的区域覆盖,需极小化势能函数ER(X),找到一个ER(X)=0的解X。
3.根据权利要求1所述的一种求解配电网传感器区域覆盖问题的迭代的局部搜索方法,其特征在于:步骤8.4所述的调整圆形区域半径方法,其具体描述如下:给定一个合法解S=(X,R),调整圆形区域半径方法的目的是调整区域半径R和布局X,使半径R局部最大化时,维持布局X的合法性;为此,从给定的初始合法解S=(X,R)开始,局部优化函数Eα(X,R);采用了序列的无约束最小化技术,该约束极小化问题转化为一系列无约束最小化问题,即2
Minmize Eα(X,R)=α·E(X,R)‑R其中势能函数中R视为一个变量,α是惩罚因子,α的每一个值都定义了无约束的最小化问题;通过极小化一系列Eα(X,R),随着α达到一个很大的数,算法收敛于一个合法布局。