基于学习的迭代局部搜索解决内生安全服务器选择的方法

1.本发明属于人工智能技术领域，涉及组合优化技术，具体涉及一种基于学习的迭代局部搜索解决内生安全服务器选择的方法。


背景技术：

2.随着数字化时代的到来，网络形势越发严峻，传统附加式安全手段愈加难以满足复杂网络安全需求。内生安全理论在理论探索、技术突破、系统研制等方面均取得了重要成果，有望成为未来网络安全的发展方向。在人体内生免疫系统中，免疫细胞依据其来源可以分为固有免疫细胞组(包含巨噬细胞、nk细胞、树突状细胞等)、t细胞组(包含th1、th2、th
17
、t
reg
等)和b细胞组(包含b1、b2等)等，每一种免疫细胞及其所在组的调用都会消耗人体资源。同时，每种免疫细胞可以分泌多种免疫调控因子，对人体的免疫应答和抗病原体感染等具有重要作用。当检测到病原体时，人体免疫系统将针对性地调用免疫细胞分泌各类免疫调控因子，以最小的代价实现对病原体的有效防御。受人体免疫系统启发，我们通过将免疫细胞类比为候选服务器、免疫细胞所在的组类比为候选服务器所在的网段、免疫调控因子类比为接受服务的计算机，便可以将人体免疫系统调用免疫细胞防御病原体的过程应用于内生安全网络中的服务器选择问题。
3.服务器选择问题是内生安全中十分重要的研究课题，因此，对于内生安全下的服务器选择问题展开深入研究具有极高的理论价值和实践价值。具体而言，一方面，内生安全下的服务器选择利益最大化集合覆盖问题是一类极难被求解的np-hard组合优化问题，并且目前研究方兴未艾。另一方面，该问题可以应用于其他工业上十分活跃的研究课题，包括采矿业中的钻孔布置问题、相机传感器覆盖问题等。因此，对内生安全下的服务器选择问题展开深入研究，具有极高的理论价值和实践价值。在该问题中，候选服务器根据其所在网段被分为不同的组，且每个候选服务器可以为若干个网络中的计算机(节点)提供服务。每个被服务的节点会产生收益，建立和维护服务器会存在成本，同时每个建立服务器的网段也会存在运维成本。该问题的目标在于选择若干个服务器，以最大限度地提高利润，其利润为被服务的节点所获得的总收益减去运维服务器和网段所需要的总成本。通过将网络节点作为元素，候选服务器作为元素子集，网段作为组，即可将内生安全下的服务器选择问题建模为利益最大化集合覆盖问题。
4.所建模成的利益最大化集合覆盖问题定义如下：给定一组具有收益的元素和一组具有成本的元素子集，这些子集被分为若干个组，利润最大化集合覆盖问题的目标是选择一些子集，以最大化总利润，即被覆盖元素的总收益减去所选子集及其相关组的成本。
5.面对利益最大化集合覆盖问题计算上的挑战，以及问题本身的内在困难，许多研究者致力于开发精确算法或启发式算法。对于np-hard组合优化问题，启发式算法是最有效的方法之一。但是，现有的启发式算法在处理内生安全服务器选择问题上存在以下两个缺陷：
6.(1)现有算法忽略了学习驱动的算法框架。目前，代表性的启发式算法包含迭代局
部搜索算法和并行迭代局部搜索算法，然而没有针对利益最大化集合覆盖问题精心设计的学习驱动的搜索算法。最近的研究表明，集成学习技术和传统启发式方法的算法可以成功解决许多集合覆盖相关的np-hard难题，如集合覆盖问题和预算最大覆盖问题。
7.(2)现有算法的稳定性不足。根据已知的结果，现有的针对利益最大化集合覆盖问题的启发式算法是不稳定的，尤其是在具有至少5192个元素，15252个子集和62个组的大型算例上。


技术实现要素：

8.为解决上述问题，本发明提出学习驱动的迭代局部搜索框架来研究内生安全服务器选择问题的解决方案，旨在给出一种快速的、性能优异的启发式迭代局部搜索方法。
9.为了达到上述目的，本发明提供如下技术方案：
10.基于学习的迭代局部搜索解决内生安全服务器选择的方法，包括如下步骤：
11.步骤1，使用缩减过程来预处理给定的问题实例i＝(e,s,g)，e代表元素所构成的集合、s代表元素子集所构成的集合、g代表元素子集所在的组构成的集合；通过遍历s中的所有子集并移除任何满足该条件的子集来实现对问题实例的预处理；
12.步骤2，根据历史信息向量迭代地选择s中的子集并将其插入到当前解决方案，构造学习驱动的初始解；
13.步骤3，采用集约化迭代局部搜索算法优化步骤2构造的初始解决方案，集约化驱动的迭代局部搜索迭代地执行三个阶段：两阶段局部搜索、基于学习的扰动和历史信息更新，直到连续ω次迭代无法改进最佳解，ω是集约化迭代局部搜索的深度。
14.进一步的，所述步骤1中，e＝{e1,e2,
…
,em}包含m个元素，每个元素ei存在一个收益ai；s＝{s1,s2,
…
,sn}包含n个子集，每个子集sj覆盖了e中的一些元素，且存在一个成本bj；g＝{g1,g2,
…
,gq}包含q个组，每个组gk包含了s中的一些子集，且存在一个成本ck；如果s中的子集所覆盖元素的总增益不超过该子集的成本，则直接从s中移除该子集。
15.进一步的，所述步骤2具体包括如下过程：
16.学习驱动的解决方案构建程序根据历史信息向量η＝{η1，η2，...，ηn}，迭代地将一个子集从s中插入到当前解x0中，其中ηj记录了子集sj被插入到解中的概率；在每次迭代中，首先，以概率∈选择具有最大概率ηj的子集sj∈s
′
，否则随机选择一个的子集sj∈s
′
；然后，如果被选择的子集sj所覆盖的元素增益之和高于其成本并且ηj大于一个随机概率，则将sj插入当前解决方案；否则，忽略sj；当s
′
为空集时，构造过程停止。
17.进一步的，所述步骤3中所述两阶段局部搜索包括第一阶段基于翻转的禁忌搜索和第二阶段交换下降搜索，所述基于翻转的禁忌搜索用于执行探索性快速搜索，所述交换下降搜索用于执行集中搜索，两个阶段交替进行，直到无法进一步改进当前解；
18.所述基于翻转的禁忌搜索遵循禁忌搜索方法从输入解x开始，迭代地改进当前解决方案：在每次迭代中该算法在翻转邻域nf(x)中选择一个最佳可容许邻域解x
′
以替换当前解，并在禁忌列表中记录相应的翻转移动；如果当前解优于该禁忌搜索过程中所获得的最优解xb，则更新xb；当该搜索过程中找到的最优解xb经过连续β次迭代仍未更新时，则终止该禁忌搜索过程，β是禁忌搜索的深度；
19.所述交换下降搜索过程从基于翻转的禁忌搜索返回的解开始，通过使用由交换算
子构造的大邻域ns中找到更好的解；在下降搜索的每次迭代中，如果ns(x)中找到的最佳邻域解x
′
优于x，则当前解x由x
′
代替；当交换邻域中达到局部最优解时，基于交换的下降搜索停止。
20.进一步的，所述基于翻转的禁忌搜索步骤中翻转算子包括如下步骤：
21.设x是给定的解决方案，此翻转算子flip(x，j)将不属于当前解x的子集sj添加到x或从x中删除子集sj；令代表将flip(x，j)应用到x所产生的邻域解，则由翻转算子flip(x，j)产生的邻域nf(x)由下式给出：
[0022][0023]
邻域nf(x)的大小为o(|s|)；所述翻转算子的快速邻域评估技术包括如下步骤：
[0024]
采用快速增量评估技术，以有效地计算移动增益(δf)，该技术识别了应用flip(x，j)算子后目标值f的变化；维持一个大小为n的向量δ，其中δ[j]对于每个sj记录其被翻转的增量评估值，1≤j≤n，sj所在组为gk；按照如下公式初始化向量δ：
[0025][0026]
其中，ai代表元素ei的收益，bj代表子集sj的成本，ck代表组gk的成本；θ1和θ2是由gk和x确定的二进制参数，1≤i≤m，1≤k≤q，如果gk和x没有交集，则θ1＝1；否则，θ1＝0；如果gk和x的交集大小为1，则θ2＝1；否则，θ2＝0；ei表示属于子集sj的元素，ri表示覆盖元素ei的子集的并集；
[0027]
每次执行涉及子集sj的flip(x，j)移动时，移动增益δf(flip(x，j))可由下式获得：
[0028][0029]
执行翻转移动时，受影响的数据结构δ将更新如下：
[0030]
1)对于被翻转的子集sj，δ[j]＝-δ[j]；
[0031]
2)对于与被翻转的子集sj处于相同组gk中的每个子集s
l
，l≠j，δ[l]更新为
[0032][0033]
3)对于覆盖子集sj中的元素ei的每个子集sr，r≠j，δ[r]更新为
[0034][0035]
在最坏的情况下，更新δ的时间复杂度为o(mn)。
[0036]
进一步的，所述基于翻转的禁忌搜索步骤中禁忌列表管理策略用于避免重新访问已经访问过的解决方案，包括如下步骤：
[0037]
对于下一个tt(j)次迭代，不能重新翻转曾经被翻转过的子集sj，tt(j)为禁忌期限；
[0038]
当将子集sj添加到x时，翻转移动的禁忌长度是1到c之间的随机数，其中c代表禁
忌长度阈值；当从x中删除子集sj时，设置tt(j)＝|s|，其中|s|是缩减过程后剩余子集的数量；
[0039]
采用期望准则，它总是接受比禁忌搜索过程中记录的最佳解决方案更好的邻域解。
[0040]
进一步的，所述交换算子交换来自x的子集sj和x之外的子集s
l
，产生以下ns邻域
[0041][0042]ns
邻域的大小以o(|x|
×
|s\x|)为界；
[0043]
所述交换算子的快速邻域评估技术包括如下步骤：
[0044]
swap(x，j，l)移动可以作为两个连续翻转移动的组合来执行，即即因此，计算移动增益通过δf(swap(x，j，l))＝δ[j]+δ
′
[l]，其中δ[j]是翻转sj的移动增益，δ
′
[l]是在翻转sj之后翻转s
l
的移动增益；
[0045]
δ
′
[l]可由下式获得：
[0046][0047]
执行交换移动时，可以根据翻转移动的更新规则更新受影响的数据结构δ；δ
′
将根据上式重新计算；交换移动的复杂度为o(mn)。
[0048]
进一步的，所述步骤3中基于学习的扰动过程包括以下步骤：
[0049]
使用两种类型的扰动：集合扰动和组扰动；对于每一次扰动迭代，扰动程序根据学习的策略执行其中一种扰动；扰动概率向量γ记录了选择第t类扰动的可能性初始时，每个扰动类型被选择的概率是相同的，即γ
t
＝1/2；每次扰动过程中，生成一个介于0和1之间的随机数“rand”；如果rand＜γ1，则选择集合扰动；否则，选择组扰动。
[0050]
进一步的，所述两种类型的扰动具体包括如下内容：
[0051]
集合扰动：该扰动首先以概率p移除迭代局部搜索过程中的最优解x
best
的所有子集；设h为移除的子集的数量；然后，从s中随机选择h个子集，如果所选择的子集不在解x
best
中，则将其添加到当前解中；否则，跳过它；
[0052]
组扰动：该扰动首先识别一个组的集合其中每个组与x
best
的交集不为空；然后从z中随机选择max{p
×
|z|，1｝个组，并移除所选组与x
best
之间的子集交集；最后，从g\z中随机选择max{p
×
|z|，1}个组，并随机翻转每个所选组中的[|x
best
|/|z|个子集。
[0053]
进一步的，所述步骤3中历史信息更新过程包括以下步骤：
[0054]
使用历史信息向量η来构造初始解和扰动概率向量γ来选择扰动类型；每次改进迭代局部搜索过程中的最佳解x
best
时，都会更新这两个向量；
[0055]
更新历史信息向量η：如果当前解x优于x
best
，则提高选择当前解x中的子集的概率，同时则降低在x之外的子集的概率；通过如下公式修改每个子集的概率值：
[0056][0057]
其中，1≤j≤n，φ1和φ2分别为奖励因子，0＜φ1＜1，0＜φ2＜1；
[0058]
采用概率平滑技术防止历史信息误导当前搜索，一旦历史信息向量中的子集概率达到给定的阈值，它将根据平滑因子φ3增加或减少以忽略一些早期信息，0＜φ3＜1；具体如下公式所述：
[0059][0060]
其中，α为平滑阈值；
[0061]
更新扰动概率向量γ：扰动概率向量γ＝{γ1，γ2}按照概率学习方法进行更新，该方法的概率更新方案为：
[0062][0063]
其中，t是扰动类型，d0是调节参数，d
t
是通过采用第t种扰动来更新局部最优解x
best
的频率。
[0064]
与现有技术相比，本发明具有如下优点和有益效果：
[0065]
本发明提出了一种快速寻找内生安全服务器选择问题最优解或者近似最优解的方法，首次提出基于学习的迭代局部搜索框架，该方法具有几个互补的搜索组件，包括用于对候选解进行有效探索的两阶段局部搜索，用于获得有希望的初始解的学习驱动构造程序，以及用于选择适当扰动的基于学习的扰动程序。本发明设计针对问题的学习驱动策略，对于解决内生安全服务器选择问题及相应的问题具有重要的研究和实用价值。本发明提出的算法能够快速且更好地解决现实世界中np-hard类的集合覆盖优化问题。
附图说明
[0066]
图1为人体免疫系统调用免疫细胞的过程与内生安全中服务器选择问题对应关系图。
[0067]
图2为基于学习的迭代局部搜索解决内生安全服务器选择问题的方法总流程图。
[0068]
图3是基于缩减的预处理程序示例图，其中(a)表示预处理前的问题实例；(b)表示预处理后的问题实例。图中方框代表元素，方框内的数字代表元素序号，方框边的数字代表元素的收益；圆圈代表子集，圆圈内的数字代表子集序号，圆圈边的数字代表子集的成本；虚线框代表组，虚线框边的数字代表组的成本。
[0069]
图4表示集约化迭代局部搜索方案的流程图。
[0070]
图5是两种扰动的过程示例图，其中(a)表示集合扰动；(b)表示组扰动。
具体实施方式
[0071]
以下将结合具体实施例对本发明提供的技术方案进行详细说明，应理解下述具体实施方式仅用于说明本发明而不用于限制本发明的范围。
[0072]
本发明提供一种基于学习的迭代局部搜索解决内生安全服务器选择的方法，图1展示了人体免疫系统调用免疫细胞的过程与内生安全中服务器选择问题的对应关系，具体算法流程如图2所示，包括如下步骤：
[0073]
(1)基于缩减的预处理
[0074]
如图3所示，在开始搜索之前，我们使用一个缩减过程来预处理给定的问题实例i＝(e,s,g)，e代表元素所构成的集合、s代表元素子集所构成的集合、g代表元素子集所在的组构成的集合；其中e＝{e1，e2，...，em}包含m个元素，每个元素ei存在一个收益ai；s＝{s1，s2，...，sn}包含n个子集，每个子集sj覆盖了e中的一些元素，且存在一个成本bj；g＝{g1，g2，...，gq}包含q个组，每个组gk包含了s中的一些子集，且存在一个成本ck。通过考虑到如果s中的子集所覆盖元素的总增益不超过该子集的成本，则可以直接从s中移除该子集。本方法通过遍历s中的所有子集并移除任何满足该条件的子集来实现对问题实例的预处理。
[0075]
(2)根据历史信息向量迭代地选择s中的子集并将其插入到当前解决方案，构造学习驱动的初始解，其过程具体如下：
[0076]
学习驱动的解决方案构建程序根据历史信息向量η＝{η1，η2，...，ηn}，迭代地将一个子集从s中插入到当前解x0中，其中ηj记录了子集sj被插入到解中的概率。对于ηj被初始化为0.5，x0被初始化为空集，s被初始化为s，其中s
′
代表未被选择过的子集所构成的集合。在每次迭代中，首先，以概率∈(∈的取值范围可为[0.5，1])选择具有最大概率ηj的子集sj∈s
′
，否则随机选择一个的子集sj∈s
′
；然后，如果被选择的子集sj所覆盖的元素增益之和高于其成本并且ηj大于一个随机概率，则将sj插入当前解决方案；否则，忽略sj。当s
′
为空集时，构造过程停止。
[0077]
(3)设计如图4所示的集约化迭代局部搜索算法，从而进一步优化步骤(2)构造的初始解决方案，以保证强化和多样化的平衡。具体而言，集约化驱动的迭代局部搜索迭代地执行三个阶段：两阶段局部搜索过程、基于学习的扰动过程和历史信息更新，直到它连续ω次迭代无法改进最佳解(ω是集约化迭代局部搜索的深度，ω的取值范围可为[100，300])。
[0078]
1)两阶段局部搜索：第一阶段称为基于翻转的禁忌搜索，执行探索性快速搜索，而第二阶段称为交换下降搜索，执行集中搜索。这两个阶段交替进行，直到无法进一步改进当前解。
[0079]
基于翻转的禁忌搜索遵循禁忌搜索方法从输入解x开始，迭代地改进当前解决方案。在每次迭代中该算法在翻转邻域nf(x)中选择一个最佳可容许邻域解x
′
以替换当前解，并在禁忌列表中记录相应的翻转移动。如果当前解优于该禁忌搜索过程中所获得的最优解xb，则更新xb。当该搜索过程中找到的最优解xb经过连续β次迭代仍未更新时，则终止该禁忌搜索过程(β是禁忌搜索的深度，β的取值范围可为[500，2500])。
[0080]
设x是给定的解决方案，此翻转算子flip(x，j)将不属于当前解x的子集sj添加到x或从x中删除子集sj。令代表将flip(x，j)应用到x所产生的邻域解，则由翻转算子flip(x，j)产生的邻域nf(x)由下式给出：
[0081][0082]
很容易看出，邻域nf(x)的大小为o(|s|)。
[0083]
此外，我们设计了一种快速增量评估技术，以有效地计算移动增益(δf)，该技术识别了应用flip(x，j)算子后目标值f的变化。我们维持一个大小为n的向量δ，其中δ[j](1
≤j≤n)对于每个sj(sj所在组为gk)记录其被翻转的增量评估值。我们可以按照如下公式初始化向量δ：
[0084][0085]
其中，ai代表元素ei的收益，bj代表子集sj的成本，ck代表组gk的成本；θ1和θ2是由gk和x确定的二进制参数，如果gk和x没有交集(即)，则θ1＝1；否则，θ1＝0。如果gk和x的交集大小为1(即gk∩x＝{sj})，则θ2＝1；否则，θ2＝0。ei表示属于子集sj的元素，ri表示覆盖元素ei的子集的并集。
[0086]
每次执行涉及子集sj的flip(x，j)移动时，移动增益δf(flip(x，j))可由下式获得：
[0087][0088]
执行翻转移动时，受影响的数据结构δ将更新如下。
[0089]
对于被翻转的子集sj，δ[j]＝-δ[j]。
[0090]
对于与被翻转的子集sj处于相同组gk中的每个子集s
l
(l≠j)，δ[l]更新为
[0091][0092]
对于覆盖子集sj中的元素ei的每个子集sr(r≠j)，δ[r]更新为
[0093][0094]
显然，在最坏的情况下，更新δ的时间复杂度为o(mn)。
[0095]
禁忌列表用于避免重新访问已经访问过的解决方案。对于下一个tt(j)(禁忌期限)次迭代，不能重新翻转曾经被翻转过的子集sj。当将子集sj添加到x时，翻转移动的禁忌长度是1到c之间的随机数，其中c代表禁忌长度阈值，c的取值范围可为[1，20]；当从x中删除子集sj时，我们设置tt(j)＝|s|，其中|s|是缩减过程后剩余子集的数量。通常，从当前解决方案x中删除子集比向解决方案中添加新子集更具限制性。原因是x中子集数目远远少于x之外的子集数目。此外，我们还采用了一个期望准则，它总是接受比禁忌搜索过程中记录的最佳解决方案更好的邻域解。
[0096]
基于交换的下降搜索旨在通过使用由交换算子构造的大邻域ns中找到更好的解。在下降搜索的每次迭代中，如果ns(x)中找到的最佳邻域解x
′
优于x，则当前解x由x
′
代替。当交换邻域中达到局部最优解时，基于交换的下降搜索停止。
[0097]
交换算子交换来自x的子集sj和x之外的子集s
l
，产生以下ns邻域
[0098][0099]ns
邻域的大小以o(|x|
×
|s\x|)为界。
[0100]
交换算子的快速邻域评估技术包括如下步骤：
[0101]
值得一提的是，swap(x，j，l)移动可以作为两个连续翻转移动的组合来执行，即
因此，我们可以计算移动增益通过δf(swap(x，j，l))＝δ[j]+δ
′
[l]，其中δ[j]是翻转sj的移动增益，δ
′
[l]是在翻转sj之后翻转s
l
的移动增益。
[0102]
δ
′
[l]可由下式获得，
[0103][0104]
执行交换移动时，可以根据翻转移动的更新规则更新受影响的数据结构δ。δ
′
将根据上式重新计算。交换移动的复杂度为o(mn)。
[0105]
2)基于学习的扰动：扰动过程旨在从当前搜索区域跳到其他区域。我们的扰动程序使用两种类型的扰动：集合扰动和组扰动。对于每一次扰动迭代，扰动程序根据学习的策略执行其中一种扰动。扰动概率向量γ记录了选择第t类扰动的可能性γ
t
，初始时，每个扰动类型被选择的概率是相同的，即γ
t
＝1/2。每次扰动过程中，生成一个介于0和1之间的随机数“rand”。如果rand＜γ1，则选择集合扰动(第一类扰动)；否则，选择组扰动(第二类扰动)。集合扰动和组扰动的过程如图5所示。
[0106]
集合扰动：该扰动首先以概率p(p的取值范围可为[0.1，0.5])移除迭代局部搜索过程中的最优解x
best
的所有子集。设h为移除的子集的数量。然后，从s中随机选择h个子集，如果所选择的子集不在解x
best
中，则将其添加到当前解中；否则，跳过它。
[0107]
组扰动：该扰动首先识别一个组的集合其中每个组与x
best
的交集不为空。然后从z中随机选择max{p
×
|z|，1}个组，并移除所选组与x
best
之间的子集交集。最后，从g\z中随机选择max{p
×
|z|，1}个组，并随机翻转每个所选组中的个子集。
[0108]
3)历史信息更新：本方法使用历史信息向量η来构造初始解和扰动概率向量γ来选择扰动类型。每次改进迭代局部搜索过程中的最佳解x
best
时，都会更新这两个向量。
[0109]
更新历史信息向量η：如果当前解x优于x
best
，则提高选择当前解x中的子集的概率，同时则降低在x之外的子集的概率。具体地，我们通过如下公式修改每个子集的概率值，
[0110][0111]
其中，奖励因子φ1和φ2的取值范围均为(0,1)。
[0112]
此外，采用概率平滑技术防止历史信息误导当前搜索。一旦历史信息向量中的子集概率达到给定的阈值，它将根据平滑因子增加或减少(即φ3,0《φ3《1)，以忽略一些早期信息。
[0113]
具体如下公式所述，
[0114][0115]
其中，α为平滑阈值，α的取值范围可为[0.8,0.99]；更新扰动概率向量γ：扰动概
率向量γ＝{γ1,γ2}按照概率学习方法进行更新，这有助于确定最佳候选策略。该方法的概率更新方案为：
[0116][0117]
其中，t是扰动类型，d0是调节参数(d0的取值范围可为[1,100])，d
t
是通过采用第t种扰动来更新局部最优解x
best
的频率。
[0118]
本发明方案所公开的技术手段不仅限于上述实施方式所公开的技术手段，还包括由以上技术特征任意组合所组成的技术方案。应当指出，对于本技术领域的普通技术人员来说，在不脱离本发明原理的前提下，还可以做出若干改进和润饰，这些改进和润饰也视为本发明的保护范围。

技术特征：
1.基于学习的迭代局部搜索解决内生安全服务器选择的方法，其特征在于，包括如下步骤：步骤1，使用缩减过程来预处理给定的问题实例i＝(e，s，g)，e代表元素所构成的集合、s代表元素子集所构成的集合、g代表元素子集所在的组构成的集合；通过遍历s中的所有子集并移除任何满足该条件的子集来实现对问题实例的预处理；步骤2，根据历史信息向量迭代地选择s中的子集并将其插入到当前解决方案，构造学习驱动的初始解；步骤3，采用集约化迭代局部搜索算法优化步骤2构造的初始解决方案，集约化驱动的迭代局部搜索迭代地执行三个阶段：两阶段局部搜索、基于学习的扰动和历史信息更新，直到连续ω次迭代无法改进最佳解，ω是集约化迭代局部搜索的深度。2.根据权利要求1所述的基于学习的迭代局部搜索解决内生安全服务器选择的方法，其特征在于，所述步骤1中，e＝{e1，e2，...，e
m
}包含m个元素，每个元素e
i
存在一个收益a
i
；s＝{s1，s2，...，s
n
}包含n个子集，每个子集s
j
覆盖了e中的一些元素，且存在一个成本b
j
；g＝{g1，g2，...，g
q
}包含q个组，每个组g
k
包含了s中的一些子集，且存在一个成本c
k
；如果s中的子集所覆盖元素的总增益不超过该子集的成本，则直接从s中移除该子集。3.根据权利要求1所述的基于学习的迭代局部搜索解决内生安全服务器选择的方法，其特征在于，所述步骤2具体包括如下过程：学习驱动的解决方案构建程序根据历史信息向量η＝{η1，η2，...，η
n
}，迭代地将一个子集从s中插入到当前解x0中，其中η
j
记录了子集s
j
被插入到解中的概率；在每次迭代中，首先，以概率∈选择具有最大概率η
j
的子集s
j
∈s
′
，否则随机选择一个的子集s
j
∈s
′
；然后，如果被选择的子集s
j
所覆盖的元素增益之和高于其成本并且η
j
大于一个随机概率，则将s
j
插入当前解决方案；否则，忽略s
j
；当s
′
为空集时，构造过程停止。4.根据权利要求1所述的基于学习的迭代局部搜索解决内生安全服务器选择的方法，其特征在于，所述步骤3中所述两阶段局部搜索包括第一阶段基于翻转的禁忌搜索和第二阶段交换下降搜索，所述基于翻转的禁忌搜索用于执行探索性快速搜索，所述交换下降搜索用于执行集中搜索，两个阶段交替进行，直到无法进一步改进当前解；所述基于翻转的禁忌搜索遵循禁忌搜索方法从输入解x开始，迭代地改进当前解决方案：在每次迭代中该算法在翻转邻域n
f
(x)中选择一个最佳可容许邻域解x
′
以替换当前解，并在禁忌列表中记录相应的翻转移动；如果当前解优于该禁忌搜索过程中所获得的最优解x
b
，则更新x
b
；当该搜索过程中找到的最优解x
b
经过连续β次迭代仍未更新时，则终止该禁忌搜索过程，β是禁忌搜索的深度；所述交换下降搜索过程从基于翻转的禁忌搜索返回的解开始，通过使用由交换算子构造的大邻域n
s
中找到更好的解；在下降搜索的每次迭代中，如果n
s
(x)中找到的最佳邻域解x
′
优于x，则当前解x由x
′
代替；当交换邻域中达到局部最优解时，基于交换的下降搜索停止。5.根据权利要求4所述的基于学习的迭代局部搜索解决内生安全服务器选择的方法，其特征在于，所述基于翻转的禁忌搜索步骤中翻转算子包括如下步骤：设x是给定的解决方案，此翻转算子flip(x，j)将不属于当前解x的子集s
j
添加到x或从x
中删除子集s
j
；因此，令代表将flip(x，j)应用到x所产生的邻域解，则由翻转算子flip(x，j)产生的邻域n
f
(x)由下式给出：邻域n
f
(x)的大小为o(|s|)；所述翻转算子的快速邻域评估技术包括如下步骤：采用快速增量评估技术，以有效地计算移动增益(δf)，该技术识别了应用flip(x，j)算子后目标值f的变化；维持一个大小为n的向量δ，其中δ[j]对于每个s
j
记录其被翻转的增量评估值，1≤j≤n，s
j
所在组为g
k
；按照如下公式初始化向量δ：其中，a
i
代表元素e
i
的收益，b
j
代表子集s
j
的成本，c
k
代表组g
k
的成本；θ1和θ2是由g
k
和x确定的二进制参数，1≤i≤m，1≤k≤q，如果g
k
和x没有交集，则θ1＝1；否则，θ1＝0；如果g
k
和x的交集大小为1，则θ2＝1；否则，θ2＝0；e
i
表示属于子集s
j
的元素，r
i
表示覆盖元素e
i
的子集的并集；每次执行涉及子集s
j
的flip(x，j)移动时，移动增益δf(flip(x，j))可由下式获得：执行翻转移动时，受影响的数据结构δ将更新如下：1)对于被翻转的子集s
j
，δ[j]＝-δ[j]；2)对于与被翻转的子集s
j
处于相同组g
k
中的每个子集s
l
，l≠j，δ[l]更新为3)对于覆盖子集s
j
中的元素e
i
的每个子集s
r
，r≠j，δ[r]更新为在最坏的情况下，更新δ的时间复杂度为o(mn)。6.根据权利要求4所述的基于学习的迭代局部搜索解决内生安全服务器选择的方法，其特征在于，所述基于翻转的禁忌搜索步骤中禁忌列表管理策略用于避免重新访问已经访问过的解决方案，包括如下步骤：对于下一个tt(j)次迭代，不能重新翻转曾经被翻转过的子集s
j
，tt(j)为禁忌期限；当将子集s
j
添加到x时，翻转移动的禁忌长度是1到c之间的随机数，其中c代表禁忌长度阈值；当从x中删除子集s
j
时，设置tt(j)＝|s|，其中|s|是缩减过程后剩余子集的数量；采用期望准则，它总是接受比禁忌搜索过程中记录的最佳解决方案更好的邻域解。7.根据权利要求4所述的基于学习的迭代局部搜索解决内生安全服务器选择的方法，其特征在于，所述交换算子交换来自x的子集s
j
和x之外的子集s
l
，产生以下n
s
邻域n
s
邻域的大小以o(|x|
×
|s\x|)为界；
所述交换算子的快速邻域评估技术包括如下步骤：swap(x，j，l)移动可以作为两个连续翻转移动的组合来执行，即即因此，计算移动增益通过δf(swap(x，j，l))＝δ[j]+δ
′
[l]，其中δ[j]是翻转s
j
的移动增益，δ
′
[l]是在翻转s
j
之后翻转s
l
的移动增益；δ
′
[l]可由下式获得：执行交换移动时，可以根据翻转移动的更新规则更新受影响的数据结构δ；δ
′
将根据上式重新计算；交换移动的复杂度为o(mn)。8.根据权利要求1所述的基于学习的迭代局部搜索解决内生安全服务器选择的方法，其特征在于，所述步骤3中基于学习的扰动过程包括以下步骤：使用两种类型的扰动：集合扰动和组扰动；对于每一次扰动迭代，扰动程序根据学习的策略执行其中一种扰动；扰动概率向量γ记录了选择第t类扰动的可能性γ
t
，初始时，每个扰动类型被选择的概率是相同的，即γ
t
＝1/2；每次扰动过程中，生成一个介于0和1之间的随机数“rand”；如果rand＜γ1，则选择集合扰动；否则，选择组扰动。9.根据权利要求8所述的基于学习的迭代局部搜索解决内生安全服务器选择的方法，其特征在于，所述两种类型的扰动具体包括如下内容：集合扰动：该扰动首先以概率p移除迭代局部搜索过程中的最优解x
best
的所有子集；设h为移除的子集的数量；然后，从s中随机选择h个子集，如果所选择的子集不在解x
best
中，则将其添加到当前解中；否则，跳过它；组扰动：该扰动首先识别一个组的集合其中每个组与x
best
的交集不为空；然后从z中随机选择max{p
×
|z|，1｝个组，并移除所选组与x
best
之间的子集交集；最后，从g\z中随机选择max{p
×
|z|，1｝个组，并随机翻转每个所选组中的个子集。10.根据权利要求1所述的基于学习的迭代局部搜索解决内生安全服务器选择的方法，其特征在于，所述步骤3中历史信息更新过程包括以下步骤：使用历史信息向量η来构造初始解和扰动概率向量γ来选择扰动类型；每次改进迭代局部搜索过程中的最佳解x
best
时，都会更新这两个向量；更新历史信息向量η：如果当前解x优于x
best
，则提高选择当前解x中的子集的概率，同时则降低在x之外的子集的概率；通过如下公式修改每个子集的概率值：其中，1≤j≤n，φ1和φ2分别为奖励因子，0＜φ1＜1，0＜φ2＜1；采用概率平滑技术防止历史信息误导当前搜索，一旦历史信息向量中的子集概率达到给定的阈值，它将根据平滑因子φ3增加或减少以忽略一些早期信息，0＜φ3＜1；具体如下
公式所述：其中，α为平滑阈值；更新扰动概率向量γ：扰动概率向量γ＝{γ1，γ2}按照概率学习方法进行更新，该方法的概率更新方案为：其中，t是扰动类型，d0是调节参数，d
t
是通过采用第t种扰动来更新局部最优解x
best
的频率。

技术总结
本发明提出了一种快速寻找内生安全服务器选择问题最优解或者近似最优解的方法，首次提出基于学习的迭代局部搜索框架，该方法具有几个互补的搜索组件，包括用于对候选解进行有效探索的两阶段局部搜索，用于获得有希望的初始解的学习驱动构造程序，以及用于选择适当扰动的基于学习的扰动程序。本发明设计针对问题的学习驱动策略，对于解决内生安全服务器选择问题及相应的问题具有重要的研究和实用价值。本发明提出的算法能够快速且更好地解决现实世界中NP-hard类的集合覆盖优化问题。hard类的集合覆盖优化问题。hard类的集合覆盖优化问题。


技术研发人员：孙雯 李文龙 胡爱群 陈超凡 李涛 王铸清
受保护的技术使用者：东南大学
技术研发日：2023.05.04
技术公布日：2023/9/12