(19)中华 人民共和国 国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202111640803.X (22)申请日 2021.12.2 9 (71)申请人 湖南农业大 学 地址 410128 湖南省长 沙市芙蓉区农大路1 号 (72)发明人 童成彪　 (74)专利代理 机构 长沙朕扬知识产权代理事务 所(普通合伙) 43213 代理人 包雨函 (51)Int.Cl. G06F 30/20(2020.01) G06F 111/06(2020.01) (54)发明名称 基于搜救队算法求解0-1背包问题的方法及 系统 (57)摘要 本发明公开了基于搜 救队算法求解0 ‑1背包 问题的方法及系统， 通过从物品搜索范围中随机 选取物品构建初始样本空间； 从样 本空间中查找 目标函数值最优的样本点作为样本空间的中心 点； 根据搜索空间与步长确定每个样本点的搜索 空间， 并基于搜索空间查找备选样本点， 将备选 样本点的目标函数值与原样本点的目标函数值 进行比较， 根据比较结果更新样本空间的样本 点； 对概率控制参数进行缩小操作， 迭代次数加 1， 若达到终止条件， 则终止， 否则重复上述步骤。 本发明模拟 搜救队的救援行为， 每个队员保持一 定的独立性向其周围搜索， 同时组员之间不断协 同更新中心点的信息， 尝试着向中心搜索， 能在 得到全局最优解的同时提高求 解的收敛速率。 权利要求书2页 说明书8页 附图6页 CN 114297855 A 2022.04.08 CN 114297855 A 1.一种基于 搜救队算法求 解0‑1背包问题的方法， 其特 征在于， 包括以下步骤： S1、 初始化0 ‑1背包问题： 确定物品搜索范围， 并构建目标函数； S2、 从搜索范围中随机 选取物品构建样本空间； S3、 从样本空间中查找目标函数值 最优的样本点作为样本空间的中心点； S4、 在每一个样本点构造一个搜索空间， 搜索空间是一个方向矩阵， 并基于方向矩阵和 步长确定每个样本点对应的备选样本点， 计算备选样本点的目标函数值， 将备选样本点的 目标函数值与旧样本点的目标函数值进行比较， 并根据比较结果更新样本点； S5、 对每一个样本点执 行S4同样的操作， 从而形成新样本空间； S6、 对概率控制常数进行缩小操作， 迭代次数加1， 判断是否到达终止条件， 若达到终止 条件， 则终止， 否则重复步骤S3～S6 。 2.根据权利要求1所述的基于搜救队算法求解0 ‑1背包问题的方法， 其特征在于， 设样 本空间为X＝[x1,x2,...xj,...,xn],xj为第j个样本， j＝{1,2,3...,n}， n为样本空间的样本 总数； xj＝[xj(1),xj(2),.....xj(w)]， xj(t)为物品搜索范围内第t 个物品被xj选中的概率， t＝{1,2,...w}， w为物品搜索 范围内的物品总数或解空间 的维度； 设中心点为xB＝[xB(1), xB(2),.....xB(w)]， pg为中心点的函数值， 即pg＝f(xB)； 则第j个样本的搜索 空间为Dj＝[Dj1,Dj2,...Djh,...,DJk]T,k＝w+2； 其中， Djh为搜索空 间Dj中第h个方向向量； Djh＝[Djh(1),Djh(2).....,Djh(w)],h＝{1,2,...,w+2}； 其 中， 搜索 空间Dj中前w个方向向量随机生 成； Djw+1是该样本点上一次搜索的方向向量； Djw+2是第j个样 本指向中心点的方向 向量； 且Djw+2＝[Djw+2(1),Djw+2(2),.....Djw+2(w)]； 3.根据权利要求2所述的基于搜救队算法求解0 ‑1背包问题的方法， 其特征在于， 基于 方向矩阵和步长确定每 个样本点对应的备选样本点， 通过以下公式实现： XNj＝[XNj1,XNj2,...,XNjB,...,XNjk]T,k＝w+2； 其中， XNj为搜索空间内的备选样本点集合， Bj为搜索步长； 是将样本xj以行拷贝的形 式形成的(w+2) ×w维的矩阵。 4.根据权利要求3所述的基于搜救队算法求解0 ‑1背包问题的方法， 其特征在于， 搜索 步长Bj通过以下公式实现： 其中， m为 最大迭代次数， c为当前迭代计数。 5.根据权利要求3所述的基于搜救队算法求解0 ‑1背包问题的方法， 其特征在于， 根据 比较结果更新样本空间的样本点， 通过以下公式实现：权　利　要　求　书 1/2 页 2 CN 114297855 A 2若XNjB为搜索空间中的最优点， 是初始样本点xj经过c步迭代后的新 值； f(XNjB)＝min[(f(XNj1),f(XNj2),....f(XNjB),...,f(XNjk)],k＝w+2 其中， 上标c表示 当前样本的新迭代值， 上标c ‑1表示上一步的迭代值； f(xjc‑1)为更新前 的样本点的目标函数值， rand为位于(0,1)之间均匀分布的随机数， pg为 中心点的目标函数值， T为 概率控制常数。 6.根据权利要求5所述的基于搜救队算法求解0 ‑1背包问题的方法， 其特征在于， 在迭 代过程中， 当样 本点迭代至中心点处， 且所述样本点的迭代次数小于最大迭代次数时， 将搜 索方向改为选择 XNj中的最大 上升方向搜索， 以防止早熟和陷入局部最优。 7.根据权利要求5所述的基于搜救队算法求解0 ‑1背包问题的方法， 其特征在于， 每个 样本点在迭代更新过程中使用单独的步长， 每个样本点的步长取决于其与中心 点的距离和 步长系数， 对于步长的控制策略是， 当值被更新时， 步长不变， 否则对步长进 行放大处理； 当 步长达到最大距离时， 步长进行初始化。 8.根据权利要求7所述的基于搜救队算法求解0 ‑1背包问题的方法， 其特征在于， 每次 迭代的步长通过以下公式计算得到： 其中， 上标c为当前迭代次数， L 为放大系数， Ds为当前样本点到中心点的欧氏距离 。 9.根据权利要求1 ‑8中任意一项所述的基于搜救队算法求解0 ‑1背包问题的方法， 其特 征在于， 目标函数值 为： min‑P s.t.G<GL 其中， P为背包的总价值， G为背包的总重量； xi为第i个物品的选取概率， xi∈{0,1}； Gi 为第i个物品的重量； Vi为第i个物品的价 值， GL为背包的最大容 量； N为物品的总数。 10.一种计算机系统， 包括存储器、 处理器以及存储在存储器上并可在处理器上运行的 计算机程序， 其特征在于， 处理器执行计算机程序时实现上述权利要求1至9任一方法的步 骤。权　利　要　求　书 2/2 页 3 CN 114297855 A 3