检索结果-南通市图书馆

在线全文

学校读者我要写书评

暂无评论

一种求解0-1背包问题的置信传播算法

郑州大学学报（理学版） 2021年第1期53卷 29-34页

作者：张丹丹王晓峰冯琬晶左逢源北方民族大学计算机科学与工程学院宁夏银川750021 宁夏智能信息与大数据处理重点实验室宁夏银川750021

针对启发式算法在求解0-1背包问题时易陷入局部最优以及寻优精度低等不足,提出一种求解0-1背包问题的置信传播算法。根据0-1背包问题的线性规划,构造该问题的因子图模型,并基于该模型的特点设计对应的标识函数,进而设计一种求解0-1背包... 详细信息

针对启发式算法在求解0-1背包问题时易陷入局部最优以及寻优精度低等不足,提出一种求解0-1背包问题的置信传播算法。根据0-1背包问题的线性规划,构造该问题的因子图模型,并基于该模型的特点设计对应的标识函数,进而设计一种求解0-1背包问题的置信传播算法。当算法收敛时,计算每个物体节点的置信度,以确定该物体的装包概率,从而高概率地给出0-1背包问题的解。与其他启发式算法进行了比较,结果表明,该算法具有较好的全局搜索能力。

关键词： 0-1背包问题线性规划因子图置信传播算法

在线全文

学校读者我要写书评

暂无评论

求解0-1背包问题的二进制狼群算法

系统工程与电子技术 2014年第8期36卷 1660-1667页

作者：吴虎胜张凤鸣战仁军汪送张超空军工程大学装备管理与安全工程学院陕西西安710051 武警工程大学装备工程学院陕西西安710086

狼群算法(wolf pack algorithm,WPA)源于狼群在捕食及其猎物分配中所体现的群体智能,已被成功应用于复杂函数求解。在此基础上,通过定义运动算子,对人工狼位置、步长和智能行为重新进行二进制编码设计,提出了一种解决离散空间组合优化... 详细信息

狼群算法(wolf pack algorithm,WPA)源于狼群在捕食及其猎物分配中所体现的群体智能,已被成功应用于复杂函数求解。在此基础上,通过定义运动算子,对人工狼位置、步长和智能行为重新进行二进制编码设计,提出了一种解决离散空间组合优化问题的二进制狼群算法(binary wolf pack algorithm,BWPA)。该算法保留了狼群算法基于职责分工的协作式搜索特性,选取离散空间的经典问题——0-1背包问题进行仿真实验,具体通过10组经典的背包问题算例和BWPA算法与经典的二进制粒子群算法、贪婪遗传算法、量子遗传算法在求解3组高维背包问题时的对比计算,例证了算法具有相对更好的稳定性和全局寻优能力。

关键词：进化计算群体智能二进制狼群算法组合优化 0-1背包问题

在线全文

学校读者我要写书评

暂无评论

DNA折纸术在0-1背包问题中的应用

计算机应用研究 2021年第3期38卷 777-781页

作者：杨新木杨静殷志祥唐震崔建中安徽理工大学数学与大数据学院安徽淮南232001 安徽理工大学电气与信息工程学院安徽淮南232001 香港大学教育学院香港999077 上海工程技术大学数理与统计学院上海201620 淮南联合大学计算机系安徽淮南232001

DNA折纸术因其反应的可编程性、纳米可寻址性等优点被广泛地应用于DNA计算中。利用DNA折纸术和杂交链式反应构建0-1背包问题的计算模型。以四个变量的0-1背包问题为例,首先将九种发夹结构和一种分子信标锚定在DNA折纸基底上并加入足量... 详细信息

DNA折纸术因其反应的可编程性、纳米可寻址性等优点被广泛地应用于DNA计算中。利用DNA折纸术和杂交链式反应构建0-1背包问题的计算模型。以四个变量的0-1背包问题为例,首先将九种发夹结构和一种分子信标锚定在DNA折纸基底上并加入足量的辅助链;其次通过加入不同的引发链可以触发不同路径上的杂交链式反应,并得到问题的所有可能解;最后,通过荧光信号的数量确定可行解,从而找到问题的最优解。该模型不受权重过大或过小的影响,在折纸基底上可等比例的缩放权重。用Visual DSD软件对该模型进行仿真,模型显示出良好的可行性。

关键词： 0-1背包问题 DNA折纸术 DNA计算 Visual DSD软件

在线全文

学校读者我要写书评

暂无评论

求解0-1背包问题的混合贪婪遗传算法

计算机应用 2021年第1期41卷 87-94页

作者：陈桢钟一文林娟福建农林大学计算机与信息学院福州350002 智慧农林福建省高等学校重点实验室(福建农林大学) 福州350002

求解0-1背包问题(KP)的最优解的时候,传统遗传算法(GA)的局部求精能力不足而简单局部搜索算法的全局探索能力有限,针对上述问题,将这两个算法整合并提出了混合贪婪遗传算法(HGGA)。在GA全局搜索框架下增加局部搜索模块,并改进传统仅基... 详细信息

求解0-1背包问题(KP)的最优解的时候,传统遗传算法(GA)的局部求精能力不足而简单局部搜索算法的全局探索能力有限,针对上述问题,将这两个算法整合并提出了混合贪婪遗传算法(HGGA)。在GA全局搜索框架下增加局部搜索模块,并改进传统仅基于物品价值密度的修复算子,增加基于物品价值的贪婪混合选项,从而加速寻优过程。HGGA一方面引导种群在进化的优质解空间中展开精细搜索,另一方面依靠GA的经典操作算子开拓全局搜索空间,从而达到算法求精能力和开拓能力的良好平衡。HGGA分别在三组数据上做了测试,结果表明在第一组15个测试用例中的12个上,HGGA能够百分百找到最优解,成功率达到80%;在第二组小规模数据集上,HGGA的性能明显好于其他同类GA和其他元启发算法;在第三组大规模数据集上,HGGA较其他元启发式算法具有更好的稳定性和高效性。

关键词： 0-1背包问题混合贪婪遗传算法求精能力求泛能力混合贪婪算子局部搜索

在线全文

学校读者我要写书评

暂无评论

求解0-1背包问题的二进制狮群算法

计算机工程与科学 2019年第11期41卷 2079-2087页

作者：刘生建杨艳周永权广州大学华软软件学院游戏系广东广州510990 广西民族大学信息科学与工程学院广西南宁530006

针对传统二进制群智能算法求解0-1背包问题易陷入局部最优、收敛速度慢的缺点,提出一种新的解决离散空间问题的二进制狮群算法BLSO。二进制狮群算法对狮王、母狮和幼狮的位置重新定义,引入反置运算、移动算子和学习算子建立全新的位置... 详细信息

针对传统二进制群智能算法求解0-1背包问题易陷入局部最优、收敛速度慢的缺点,提出一种新的解决离散空间问题的二进制狮群算法BLSO。二进制狮群算法对狮王、母狮和幼狮的位置重新定义,引入反置运算、移动算子和学习算子建立全新的位置转移方式和局部搜索规则;加入贪心策略进行解的可行化处理和充分利用,增强局部搜索能力,进一步提高收敛速度。对9个典型的0-1背包算例进行仿真实验,实验结果表明,该算法不仅可以有效求解0-1背包问题,而且还能够以较快的速度搜索到精度较高的次优解甚至全局最优解,具有较好的稳定性;同时,对高维背包问题的求解与参考算法相比,在寻优时间和精度上更具优势。

关键词：狮群算法 0-1背包问题组合约束优化 NP难题

在线全文

学校读者我要写书评

暂无评论

求解0-1背包问题的多种算法策略的分析

现代计算机 2023年第15期29卷 1-9页

作者：陈艳文晓棠钟广玲广州华商学院数据科学学院广州510520

0-1背包问题是一个经典的组合优化问题,常常被应用于资源分配、物流管理等领域,并且在计算机科学和数学中具有重要的理论价值。解决0-1背包问题有多种策略,常见的策略为动态规划法、回溯法和分支限界法,为了确定对该问题求解的最有效方... 详细信息

0-1背包问题是一个经典的组合优化问题,常常被应用于资源分配、物流管理等领域,并且在计算机科学和数学中具有重要的理论价值。解决0-1背包问题有多种策略,常见的策略为动态规划法、回溯法和分支限界法,为了确定对该问题求解的最有效方法,研究三种算法求解的性能表现是十分必要的。通过探讨求解0-1背包问题的三种不同算法,并给出该问题的动态规划法、回溯法和分支限界法的求解思路和算法设计,然后通过实验对比和分析三者的运行时间效率。实验表明,三种算法各具优缺点,要根据问题特点和需求来灵活选择算法。

关键词： 0-1背包问题动态规划回溯法分支限界法时间复杂度

学习型和声搜索算法及其在0-1背包问题中的应用

在线全文

学校读者我要写书评

暂无评论

控制与决策 2013年第2期28卷 205-210页

作者：李若平欧阳海滨高立群邹德旋东北大学信息科学与工程学院沈阳110819 徐州师范大学电气工程及自动化学院江苏徐州221116

针对现有和声搜索算法存在的不足,提出一种学习型和声搜索算法(LHS).根据目标函数值的变化,自适应调整和声记忆考虑概率(HMCR);引入学习机制,加快算法的搜索速度;动态调节基音调整概率(PAR),增强算法的全局搜索能力.对16个标准函数的测... 详细信息

针对现有和声搜索算法存在的不足,提出一种学习型和声搜索算法(LHS).根据目标函数值的变化,自适应调整和声记忆考虑概率(HMCR);引入学习机制,加快算法的搜索速度;动态调节基音调整概率(PAR),增强算法的全局搜索能力.对16个标准函数的测试结果表明,所提出的LHS算法与其他4种和声搜索算法相比具有较好的效果.最后将改进算法应用于10个0-1背包问题和1个经典的50维背包实例,实验结果表明LHS算法优于其他算法.

关键词：和声搜索算法自适应学习策略搜索速度 0-1背包问题

一种求解0-1背包问题的二进制修正和声搜索算法

在线全文

学校读者我要写书评

暂无评论

控制与决策 2014年第7期29卷 1174-1180页

作者：欧阳海滨高立群孔祥勇刘宏志东北大学信息科学与工程学院沈阳110004

针对0-1背包问题,提出一种二进制修正和声搜索算法.该算法修正了即兴创作过程,对参数PAR进行动态调整,同时提出一种随机修复机制,有效修复不可行的和声,增强算法的局部搜索.采用一种可行和声初始化方式,保证初始和声都是可行的,整个搜... 详细信息

针对0-1背包问题,提出一种二进制修正和声搜索算法.该算法修正了即兴创作过程,对参数PAR进行动态调整,同时提出一种随机修复机制,有效修复不可行的和声,增强算法的局部搜索.采用一种可行和声初始化方式,保证初始和声都是可行的,整个搜索过程完全采用0-1二进制模式,对14个0-1背包问题进行测试.将所提出算法与其他算法进行比较,结果验证了所提出算法的有效性.

关键词： 0-1背包问题二进制修正和声搜索算法局部搜索随机修复机制

求解0-1背包问题的融合贪心策略的回溯算法

在线全文

学校读者我要写书评

暂无评论

计算机技术与发展 2022年第2期32卷 190-195页

作者：孙佳宁马海龙张立臣李鹏现代教学技术教育部重点实验室陕西西安710062 陕西省教学信息技术工程实验室陕西西安710119 陕西师范大学计算机科学学院陕西西安710119

0-1背包问题作为经典的NP完全问题一直得到广泛的关注和研究。研究发现,经典回溯算法在解决0-1背包问题时的算法时间复杂度较高,尤其是在物品数量较多时,短时间内不能得到问题的解,导致算法的适用性较差。虽然经典贪心算法和现阶段涌现... 详细信息

0-1背包问题作为经典的NP完全问题一直得到广泛的关注和研究。研究发现,经典回溯算法在解决0-1背包问题时的算法时间复杂度较高,尤其是在物品数量较多时,短时间内不能得到问题的解,导致算法的适用性较差。虽然经典贪心算法和现阶段涌现出的大量新型算法能够极大地缩减算法的运行时间,但普遍是以牺牲算法的准确性为代价的,不能保证可以找到问题的最优解。针对这些问题,提出一种融合贪心策略和剪枝策略的新型回溯算法。该算法将贪心算法得到的问题近似解用于剪枝策略的判断条件中,并在物品取舍时将当前的物品重量与背包的剩余容量进行比较,以避免重复计算,减少迭代次数,提高算法的执行效率。大量的仿真实验结果表明,在一定问题规模下,与经典回溯算法相比,所提出的新型回溯算法仍能够在短时间内准确找到问题的最优解,且具有更高的执行效率。

关键词： 0-1背包问题贪心算法回溯算法剪枝策略递归算法