1.本发明涉及存在多个局部最优解的大规模组合优化问题求解，具体为一种基于邻域方向诱导策略的差分进化算法。
背景技术：2.热电联产经济调度问题是组合优化中最具挑战性的问题之一，其目标是在各种约束条件下使系统成本最小化以满足系统需求。大量的研究集中于解决小规模的chped问题，而忽略了具有大量局部最优解的大规模chped问题的实现。针对具有大量局部最优解的大规模chped问题，提出了一种基于邻域方向诱导的差分进化算法，该算法将邻域和方向信息融合到差分进化算法中。在ndide中，提出了一种方向诱导策略，利用个体差异的方向信息来指导种群的搜索。然后，提出了一种改进的变异de/rand/1方案，称为 de/ldrand/1。变异有助于提高算法的探索能力和收敛性能。在具有84、96 和192个单元的三个大规模chped系统上评估了ndide的性能，并且将ndide 与其他现有方法进行了比较。数值结果验证了ndide在求解大规模chped问题中的可行性和有效性。
技术实现要素：3.(一)解决的技术问题
4.针对现有技术的不足，本发明提供了一种基于邻域方向诱导策略的差分进化算法，该问题存在一是随着维数的增加，搜索空间呈指数级增长。二是局部最优解的数量随问题规模大大增加。解决了大规模组合优化问题中，随着维数增加，搜索空间呈指数级增长，局部最优解极大，极易陷入局部最优解的问题。
5.(二)技术方案
6.为实现以上目的，本发明通过以下技术方案予以实现：一种基于邻域方向诱导策略的差分进化算法，具体包括以下步骤：
7.s1、、chped问题是优化运行规划中最具挑战性的问题，是一个非线性非凸的存在多峰值的复杂问题。其目标是在各种约束条件下使系统成本最小化以满足系统需求。该问题存在一是随着维数的增加，搜索空间呈指数级增长。二是局部最优解的数量随问题规模大大增加。chped问题的目标是在满足各种等式和不等式约束的情况下，使三类单元的总成本最小，chped问题的主要目标是最小化由三种类型单元的生产成本组成的总生产成本，chped的目标函数如下所示：
[0008][0009]
不同类型设备的成本公式如下：
[0010]ci
(p
ip
)＝αi(p
ip
)2+βi(p
ip
)+γi[0011]
[0012][0013][0014]
在chped系统的实际生产单元中，在单元曲线上产生波纹效应的称为阀点效应的过程可以近似建模为正弦项，该正弦项通常被添加到二次目标函数中以确保chped模型的准确性；方程中给出了考虑阀点效应的目标函数。
[0015]
s2、chped问题需要考虑各种约束，可以分为两种类型:等式约束和不等式约束，如下所示：
[0016][0017][0018][0019][0020][0021][0022]
其中p
ip
和分别是等式中第i个纯电单元和第j个热电联产单元的功率输出，和分别是方程式中的第k个纯热单元和第j个热电联产单元，n
p
、 nc和nh分别表示纯电、热电联产和纯热单元的数量，pd和hd分别代表功率和热量需求，p
ip
是纯电单元的发电量。
[0023]
s3、de是一种简单而有效的数值优化算法，通过种群在问题搜索空间中的迭代过程来寻找全局最优点，de由四个算子组成:初始化、变异、交叉和选择这些运算符描述如下：
[0024]
初始化：由n p个个体(解)组成的群体表示为pg＝{x
1,g
,x
2,g
,...,x
np,g
}，其中 x
i,g
(i＝1,2,...,np)表示一个d维向量。第j个维度中的第i个向量的是在初始群体中随机初始化(g＝0时)，如下所示：
[0025][0026]
其中rand代表[0，1]中均匀分布的随机数；
[0027]
突变:向量由突变算子更新，其中提出了不同变异策略。本文使用最频繁的策略如下：
[0028][0029]
其中对应于目标向量的是从g代群体中随机选择的。f是一个缩放因子，用于正向控制缩放差分向量。
[0030]
交叉:将突变向量v
i,g
与目标向量x
i,g
混合，通过交叉形成试验向量u
i,g
，可表示如下:
[0031]
[0032]
其中c r是交叉因子，j
rand
表示[1,d]中随机选择的整数。
[0033]
选择:试验向量u
i,g
与目标向量x
i,g
竞争，适应值较好的向量保留到下一代。该运算符表示如下:
[0034][0035]
其中f(u
i,g
)、f(x
i,g
)分别代表试验向量和目标向量的适应度。
[0036]
s4、利用种群的方向信息，设计了一种跳出局部最优的方向诱导策略的进化算法，该算法利用种群的邻域信息来搜索其邻域内的个体，而不是整个种群，从而增强算法的探索能力，增加种群的多样性。de有一个主要缺陷，称为“维度诅咒”，这意味着de的性能随着问题维度的增加而呈指数级下降。当面对具有多个局部最优解的大规模组合优化问题时，de容易陷入局部最优解，收敛性能弱，限制了个体寻找全局最优解。另外，de的种群多样性随着搜索的进度变得较差。因此，该算法通过修改变异策略来提高算法的全局性能，该策略通过邻域搜索和dis来选择父个体。
[0037]
1.邻域构造：首先，由整个种群中的一组向量索引组成一个环拓扑，第一个向量是最后一个向量的邻域，反之亦然。每个向量的左向量和右向量由群体指数识别。每个向量只与它左边和右边的直接向量相互作用。通过引入邻域半径k，向量的指数形成几个邻域。对于索引为i的向量，邻域不仅包括第i 个向量，还包括最接近第i个向量的左右k个向量。也就是说，每个向量的邻域包括2k+1个向量，其中k表示从0到(np-1)/2的非零整数。
[0038]
2.邻域组：第i个个体的邻域，即nba
i,g
，根据其适应度值分为ig
i,g
和sg
i,g
两组。
[0039]
ig
i,g
＝{x
k,g
|x
k,g
∈nba
i,g
∧f(x
k,g
)≥f(x
i,g
)}
[0040]
sg
i,g
＝nba
i,g-ig
i,g
[0041]
其中ig
i,g
表示组中每个个体解都比第i个个体解更差。sg
i,g
代表组中每个个体解都比第i个个体解更优。
[0042]
3.方向诱导策略：为了防止算法陷入局部最优，提出了一种新的差分向量，称为方向诱导策略，用于引导种群的进化方向，提高收敛性能。
[0043]
ed
i,g
＝{x
p,g-x
q,g
|f(x
p,g
)＜f(x
q,g
)}
[0044]
其中，i是目标向量的索引。x
i,g
，x
p,g
和x
q,g
(p≠q≠i)为第g代种群随机选取，分别代表起点和终点。ed
i,g
代表x
i,g
的进化方向，其在第g代种群指向一个较差而不是较优的个体。
[0045]
4.突变策略：de/rand/1方案更倾向于加强对搜索空间的探索，但面对大规模多模态问题的适应度场景时，容易陷入局部最优。针对这一缺陷，利用邻域和方向诱导策略对de/rand/1方案进行改进，提出了一种新的变异方法 de/ldrand/1。
[0046][0047]
其中和分别从nba
i,g
、ig
i,g
和sg
i,g
随机选取。
[0048]
de/ldrand/1与de/rand/1的区别仅在于突变算子的父代选取。在种群进化的早期阶段，邻域内的个体分布在搜索空间的不同区域，因为de/ldrand/1采用了基于索引的邻域结构，个体在位置上是随机的。de/ldrand/1不使用常见的局部搜索策略，而是通过在个体周围执行小步长扰动来生成新的解，它允许个体跳得更长，使它们相对容易地从一个峰值
移动到较低的峰值。dis有助于通过邻域内个体向劣解移动来充分挖掘种群的邻域信息，防止算法陷入局部最优，促进种群多样性。因此，通过变异de/ldrand/1，可以以更高的可能性找到全局最优解，大大提高了算法的收敛性能。
[0049]
优选的，所述s1中，方程(3)中给出了考虑阀点效应的目标函数，αi、βi、γi、λi和ρi是纯电单元的成本系数。
[0050]
优选的，所述s3中，v
i,g
是对应于目标向量x
i,g
的突变向量。
[0051]
优选的，所述s3中，选择试验向量u
i,g
相比目标向量x
i,g
具有更好的精度值且能保留到下一代。
[0052]
(三)有益效果
[0053]
本发明提供了一种基于邻域方向诱导策略的差分进化算法。与现有技术相比，具备以下有益效果：该基于邻域方向诱导策略的差分进化算法，能够在求解组合优化问题时，突破维数诅咒，在种群进化过程中保留群体多样性，能够引导群体向更优解进化，而不是陷入局部最优解，尤其在规模较大时，加快算法的收敛性能。
具体实施方式
[0054]
对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。
[0055]
本发明实施例提供一种技术方案：一种基于邻域方向诱导策略的差分进化算法，具体包括以下步骤：
[0056]
s1、chped问题是优化运行规划中最具挑战性的问题，是一个非线性非凸的存在多峰值的复杂问题。其目标是在各种约束条件下使系统成本最小化以满足系统需求。该问题存在一是随着维数的增加，搜索空间呈指数级增长。二是局部最优解的数量随问题规模大大增加。chped问题的目标是在满足各种等式和不等式约束的情况下，使三类单元的总成本最小，chped问题的主要目标是最小化由三种类型单元的生产成本组成的总生产成本，chped的目标函数如下所示：
[0057][0058]
不同类型设备的成本公式如下：
[0059]ci
(p
ip
)＝αi(p
ip
)2+βi(p
ip
)+γi[0060][0061][0062][0063]
在chped系统的实际生产单元中，在单元曲线上产生波纹效应的称为阀点效应的过程可以近似建模为正弦项，该正弦项通常被添加到二次目标函数中以确保chped模型的准确性；方程中给出了考虑阀点效应的目标函数。
[0064]
s2、chped问题需要考虑各种约束，可以分为两种类型:等式约束和不等式约束，如
下所示：
[0065][0066][0067][0068][0069][0070][0071]
其中p
ip
和分别是等式中第i个纯电单元和第j个热电联产单元的功率输出，和分别是方程式中的第k个纯热单元和第j个热电联产单元，n
p
、 nc和nh分别表示纯电、热电联产和纯热单元的数量，pd和hd分别代表功率和热量需求，p
ip
是纯电单元的发电量。
[0072]
s3、de是一种简单而有效的数值优化算法，通过种群在问题搜索空间中的迭代过程来寻找全局最优点，de由四个算子组成：初始化、变异、交叉和选择这些运算符描述如下：
[0073]
初始化：由n p个个体(解)组成的群体表示为pg＝{x
1,g
,x
2,g
,...,x
np,g
}，其中 x
i,g
(i＝1,2,...,np)表示一个d维向量。第j个维度中的第i个向量的是在初始群体中随机初始化(g＝0时)，如下所示：
[0074][0075]
其中rand代表[0，1]中均匀分布的随机数。
[0076]
突变：向量由突变算子更新，其具有不同变异策略。本文使用最频繁的策略如下：
[0077][0078]
其中对应于目标向量的是从g代群体中随机选择的。f为缩放因子，用于正向控制缩放差分向量。
[0079]
交叉:将突变向量v
i,g
与目标向量x
i,g
混合，通过交叉形成试验向量u
i,g
，可表示如下：
[0080][0081]
其中c r是交叉因子，j
rand
表示[1,d]中随机选择的整数。
[0082]ui,g
与目标向量x
i,g
竞争，适应值较好的向量保留到下一代。该运算符表示如下:
[0083][0084]
其中f(u
i,g
)、f(x
i,g
)分别代表试验向量和目标向量的适应度。
[0085]
s4、利用种群的方向信息，设计了一种跳出局部最优的方向诱导策略的进化算法，该算法利用种群的邻域信息来搜索其邻域内的个体，而不是整个种群，从而增强算法的探
索能力，增加种群的多样性。de有一个主要缺陷，称为“维度诅咒”，这意味着de的性能随着问题维度的增加而呈指数级下降。当面对具有多个局部最优解的大规模组合优化问题时，de容易陷入局部最优解，收敛性能弱，限制了个体寻找全局最优解。另外，de的种群多样性随着搜索的进度变得较差。因此，该算法通过修改变异策略来提高算法的全局性能，该策略通过邻域搜索和dis来选择父个体。
[0086]
1.邻域构造：首先，由整个种群中的一组向量索引组成一个环拓扑，第一个向量是最后一个向量的邻域，反之亦然。每个向量的左向量和右向量由群体指数识别。每个向量只与它左边和右边的直接向量相互作用。通过引入邻域半径k，向量的指数形成几个邻域。对于索引为i的向量，邻域不仅包括第i 个向量，还包括最接近第i个向量的左右k个向量。也就是说，每个向量的邻域包括2k+1个向量，其中k表示从0到(np-1)/2的非零整数。
[0087]
2.邻域组：第i个个体的邻域，即nba
i,g
，根据其适应度值分为ig
i,g
和sg
i,g
两组。
[0088]
ig
i,g
＝{x
k,g
|x
k,g
∈nba
i,g
^f(x
k,g
)≥f(x
i,g
)}
[0089]
sg
i,g
＝nba
i,g-ig
i,g
[0090]
其中ig
i,g
表示组中每个个体解都比第i个个体解更差。sg
i,g
代表组中每个个体解都比第i个个体解更优。
[0091]
3.方向诱导策略：为了防止算法陷入局部最优，提出了一种新的差分向量，称为方向诱导策略，用于引导种群的进化方向，提高收敛性能。
[0092]
ed
i,g
＝{x
p,g-x
q,g
|f(x
p,g
)＜f(x
q,g
)}
[0093]
其中，i是目标向量的索引。x
i,g
，x
p,g
和x
q,g
(p≠q≠i)为第g代种群随机选取，分别代表起点和终点。ed
i,g
代表x
i,g
的进化方向，其在第g代种群指向一个较差而不是较优的个体。
[0094]
4.突变策略：de/rand/1方案更倾向于加强对搜索空间的探索，但面对大规模多模态问题的适应度场景时，容易陷入局部最优。针对这一缺陷，利用邻域和方向诱导策略对de/rand/1方案进行改进，提出了一种新的变异方法 de/ldrand/1。
[0095][0096]
其中和分别从nba
i,g
、ig
i,g
和sg
i,g
随机选取。
[0097]
de/ldrand/1与de/rand/1的区别仅在于突变算子的父代选取。在种群进化的早期阶段，邻域内的个体分布在搜索空间的不同区域，因为de/ldrand/1采用了基于索引的邻域结构，个体在位置上是随机的。de/ldrand/1不使用常见的局部搜索策略，而是通过在个体周围执行小步长扰动来生成新的解，它允许个体跳得更长，使它们相对容易地从一个峰值移动到较低的峰值。dis有助于通过邻域内个体向劣解移动来充分挖掘种群的邻域信息，防止算法陷入局部最优，促进种群多样性。因此，通过变异de/ldrand/1，可以以更高的可能性找到全局最优解，大大提高了算法的收敛性能。
[0098]
本发明实施例中，s1中，方程中给出了考虑阀点效应的成本函数，αi、βi、γi、λi和ρi是纯电单位的成本系数。
[0099]
本发明实施例中，s3中，v
i,g
是对应于目标向量x
i,g
的突变向量。
[0100]
本发明实施例中，s3中，选择试验向量u
i,g
相比目标向量x
i,g
具有更好的精度值且能保留到下一代。
[0101]
同时本说明书中未作详细描述的内容均属于本领域技术人员公知的现有技术。
[0102]
需要说明的是，在本文中，诸如第一和第二等之类的关系术语仅仅用来将一个实体或者操作与另一个实体或操作区分开来，而不一定要求或者暗示这些实体或操作之间存在任何这种实际的关系或者顺序。而且，术语“包括”、“包含”或者其任何其他变体意在涵盖非排他性的包含，从而使得包括一系列要素的过程、方法、物品或者设备不仅包括那些要素，而且还包括没有明确列出的其他要素，或者是还包括为这种过程、方法、物品或者设备所固有的要素。
[0103]
尽管已经示出和描述了本发明的实施例，对于本领域的普通技术人员而言，可以理解在不脱离本发明的原理和精神的情况下可以对这些实施例进行多种变化、修改、替换和变型，本发明的范围由所附权利要求及其等同物限定。
