求解多维0-1背包问题的一种改进的遗传算法 被引量：15

1

作者 曾智 杨小帆 +2 位作者 陈静 陈文斌 唐荣旺 《计算机科学》 CSCD 北大核心 2006年第7期220-223,共4页

针对多维0-1背包问题,通过应用贪心法和二分搜索法的思想,本文提出了一种新的杂交算子———中值杂交,并且基于此算子提出了求解多维0-1背包问题的一种改进的遗传算法。最后本文通过一系列数值实验,把改进算法与传统的遗传算法以及其他... 针对多维0-1背包问题,通过应用贪心法和二分搜索法的思想,本文提出了一种新的杂交算子———中值杂交,并且基于此算子提出了求解多维0-1背包问题的一种改进的遗传算法。最后本文通过一系列数值实验,把改进算法与传统的遗传算法以及其他最新的遗传算法进行比较,经过对求得近似解的精度及计算所需时间两方面的对比,验证了其有效性。 展开更多

关键词 多维0-1背包问题 遗传算法 中值杂交算子

下载PDF 职称材料

多维背包问题的禁忌搜索求解 被引量：12

2

作者 贺一 邱玉辉 +1 位作者 刘光远 曾绍华 《计算机科学》 CSCD 北大核心 2006年第9期169-172,共4页

借鉴认知心理学有关记忆系统的表述,在禁忌搜索算法中引入长时记忆,构造了基于双禁忌表的禁忌搜索算法。多维0-1背包问题的仿真实验表明,该算法是可行的、有效的。

关键词 禁忌搜索 双禁忌表 多维0-1背包问题

下载PDF 职称材料

求解多维0/1背包问题的二元粒子群算法 被引量：12

3

作者 程美英 熊伟清 +1 位作者 严彬 叶青 《系统仿真学报》 CAS CSCD 北大核心 2009年第18期5735-5739,5743,共6页

从一维细胞自动机模型入手,设计了一种求解二元离散优化问题的二元粒子群算法细胞自动机模型(BPSO-CA)。粒子从起始细胞出发,根据本身携带的信息并感知存储在细胞中的全局最优粒子位置的信息随机选择状态(0或1),从而实现复杂智能的"... 从一维细胞自动机模型入手,设计了一种求解二元离散优化问题的二元粒子群算法细胞自动机模型(BPSO-CA)。粒子从起始细胞出发,根据本身携带的信息并感知存储在细胞中的全局最优粒子位置的信息随机选择状态(0或1),从而实现复杂智能的"涌现"。然后将其用来求解多维0/1背包问题,同时引入贪心算法对不符合约束条件的非法个体进行修正。通过对Zuse Institute Berlin公布的测试集进行实验,表明该模型能在多项式时间内完成求解过程,且实验结果优于测试集记录的结果。 展开更多

关键词 二元粒子群算法(BPSO) 细胞自动机(CA) 贪心算法 多维0/1背包问题 NPC问题

下载PDF 职称材料

基于蚁群算法的多维0-1背包问题的研究 被引量：6

4

作者 汪采萍 胡学钢 王会颖 《计算机工程与应用》 CSCD 北大核心 2007年第30期74-76,161,共4页

系统地阐述了蚁群算法,并对它进行改进、优化。将蚁群算法应用于求解多维0-1背包问题,提出一种求解多维0-1背包问题的算法——多维0-1背包问题蚁群算法。它大大减少了蚁群算法的搜索时间,有效改善了蚁群算法易于过早地收敛于非最优解的... 系统地阐述了蚁群算法,并对它进行改进、优化。将蚁群算法应用于求解多维0-1背包问题,提出一种求解多维0-1背包问题的算法——多维0-1背包问题蚁群算法。它大大减少了蚁群算法的搜索时间,有效改善了蚁群算法易于过早地收敛于非最优解的缺陷。仿真实验取得了较好的结果。 展开更多

关键词 多维0-1背包问题 蚁群算法 多维0-1背包问题蚁群算法

下载PDF 职称材料

基于多交换邻域搜索的多维0/1背包问题竞争决策算法 被引量：8

5

作者 熊小华 宁爱兵 马良 《系统工程理论与实践》 EI CSSCI CSCD 北大核心 2010年第8期1448-1456,共9页

提出了一种求解多维0/1背包问题的竞争决策算法,算法采用一种新的资源交换规则——多交换的资源交换规则,使问题具有更大的邻域搜索空间,从而避免问题陷入局部最优解,同时通过对可行解的随机部分扰动进一步扩大问题的搜索空间.经过测试... 提出了一种求解多维0/1背包问题的竞争决策算法,算法采用一种新的资源交换规则——多交换的资源交换规则,使问题具有更大的邻域搜索空间,从而避免问题陷入局部最优解,同时通过对可行解的随机部分扰动进一步扩大问题的搜索空间.经过测试表明:算法具有计算时间短,求解效果好的特点. 展开更多

关键词 多维0/1背包问题 竞争决策算法 竞争力函数 决策函数 资源交换规则 多交换

原文传递

一种改进的蚁群算法求解多维背包问题 被引量：7

6

作者 王小彤 侯立刚 苏成利 《辽宁石油化工大学学报》 CAS 2015年第4期53-57,共5页

多维0-1背包问题是经典的非确定多项式问题(Non-Deterministic Polynomial,NP),针对蚁群算法求解该问题时易出现陷入局部最优、收敛速度慢等问题,提出了一种改进的蚁群算法。本文算法引入蛙跳算法的分群思想,将蚂蚁分为拥有不同文化的... 多维0-1背包问题是经典的非确定多项式问题(Non-Deterministic Polynomial,NP),针对蚁群算法求解该问题时易出现陷入局部最优、收敛速度慢等问题,提出了一种改进的蚁群算法。本文算法引入蛙跳算法的分群思想,将蚂蚁分为拥有不同文化的两个群体,提高了全局搜索能力;采用贪心策略修改公式,针对具体问题具体分析,提高了算法的精确度;融合轮盘赌算法简化了公式。仿真结果表明,本文算法加强了全局搜索能力,得到的结果更为精确。 展开更多

关键词 蛙跳算法 贪心策略 蚁群算法 多维0-1背包问题 轮盘赌算法

下载PDF 职称材料

基于交换策略的蚁群算法求解多维0-1背包问题 被引量：6

7

作者 潘夏福 倪子伟 《计算机与现代化》 2008年第3期83-85,共3页

在项目决策与规划、资源分配、货物装载等工作中,提出了多维0-1背包问题,对这一问题,国内外学者提出了许多算法。本文推广了文献[7]中求解单维0-1背包问题的蚁群算法,并从结合2-opt等局部优化的蚁群算法求解旅行商问题中得到启示:通过... 在项目决策与规划、资源分配、货物装载等工作中,提出了多维0-1背包问题,对这一问题,国内外学者提出了许多算法。本文推广了文献[7]中求解单维0-1背包问题的蚁群算法,并从结合2-opt等局部优化的蚁群算法求解旅行商问题中得到启示:通过交换策略可以加快算法的收敛速度和获取更高质量的解,因此提出了基于交换策略的蚁群算法。再把这种算法与AIAACA算法[8]进行比较,实验结果显示该算法与AIAACA算法效果相当,用时更少,是求解多维0-1背包问题的有效算法。 展开更多

关键词 多维0—1背包问题 蚁群算法 交换

下载PDF 职称材料

特殊多维0-1背包问题的约束简化方法——不等式单约束生成法 被引量：3

8

作者 高天 翟延慧 王梦光 《东北师大学报（自然科学版）》 CAS CSCD 北大核心 2002年第3期21-26,共6页

针对一类组合优化问题中多维 0 -1背包问题 (MKP) ,给出一种能减少求解难度的方法 :不等式单约束生成法 ;定义了MKP的紧约束概念 ,指出MKP也是一个NP -难问题 ;提出了一种代替多约束组的计算方法 ,并证明了经过替换后所得到的新问题与... 针对一类组合优化问题中多维 0 -1背包问题 (MKP) ,给出一种能减少求解难度的方法 :不等式单约束生成法 ;定义了MKP的紧约束概念 ,指出MKP也是一个NP -难问题 ;提出了一种代替多约束组的计算方法 ,并证明了经过替换后所得到的新问题与原问题在解精度上的等价性 . 展开更多

关键词 多维0-1背包问题 约束简化方法 不等式单约束生成法 NP-难问题 紧约束 解精度等价性 O-1规划 组合优化

下载PDF 职称材料

改进的量子粒子群多目标优化算法 被引量：4

9

作者 许昆 李智勇 《计算机工程与设计》 CSCD 北大核心 2009年第1期164-167,178,共5页

针对粒子群优化算法容易陷入局部极值点的问题,提出了一种新的量子比特粒子群算法,该算法采用Pareto支配关系来更新粒子的个体最优值和局部最优值;定义极大极小距离,并采用该距离方法裁减非支配解。实验结果表明该算法能更好地接近Paret... 针对粒子群优化算法容易陷入局部极值点的问题,提出了一种新的量子比特粒子群算法,该算法采用Pareto支配关系来更新粒子的个体最优值和局部最优值;定义极大极小距离,并采用该距离方法裁减非支配解。实验结果表明该算法能更好地接近Pareto前沿且具有更好的分布性,更适合于求解复杂高维优化问题,是一种非常有潜力的多目标优化方法。 展开更多

关键词 粒子群优化 多目标优化 量子 多维0-1背包问题 极大极小距离

下载PDF 职称材料

求解多维0-1背包问题的人工鱼群算法 被引量：4

10

作者 李春梅 马良 《数学的实践与认识》 CSCD 北大核心 2010年第17期195-199,共5页

对于多维0-1背包问题,国内外学者提出了诸如模拟退火、遗传算法、蚁群算法以及其他启发式算法.给出一种新的智能寻优方法——人工鱼群算法.算法通过各人工鱼的局部寻优,从而在群体中体现出全局最优.描述了人工鱼群算法的具体步骤并编程... 对于多维0-1背包问题,国内外学者提出了诸如模拟退火、遗传算法、蚁群算法以及其他启发式算法.给出一种新的智能寻优方法——人工鱼群算法.算法通过各人工鱼的局部寻优,从而在群体中体现出全局最优.描述了人工鱼群算法的具体步骤并编程实现,通过多维背包算例进行了求解测试,获得了满意的效果. 展开更多

关键词 多维0-1背包问题 人工鱼群算法 优化

原文传递

求解组合优化问题的改进型量子进化算法 被引量：3

11

作者 张宗飞 《计算机工程与设计》 CSCD 北大核心 2010年第17期3891-3894,共4页

根据组合优化问题的特点,提出了一种求解组合优化问题的改进型量子进化算法。借鉴小生境协同进化思想初始化种群,增加了个体多样性;采用动态策略调整量子门旋转角,加快了收敛速度;采用"优体交叉"策略实施染色体交叉操作,增强... 根据组合优化问题的特点,提出了一种求解组合优化问题的改进型量子进化算法。借鉴小生境协同进化思想初始化种群,增加了个体多样性;采用动态策略调整量子门旋转角,加快了收敛速度;采用"优体交叉"策略实施染色体交叉操作,增强了局部搜索能力。利用典型组合优化问题——2个多维0/1背包问题实例对算法性能进行验证,结果表明了该算法的可行性和有效性。 展开更多

关键词 量子进化算法 改进型量子遗传算法 改进型量子进化算法 组合优化问题 多维0/1背包问题

下载PDF 职称材料

求解多维0-1背包问题的蚁群算法研究 被引量：3

12

作者 张芹 宫洪芸 《软件导刊》 2008年第12期49-51,共3页

系统地阐述了蚁群算法,并对它进行改进、优化。将蚁群算法应用于求解多维0-1背包问题,提出一种新的求解多维0-1背包问题的算法——基于交换策略的蚁群算法。

关键词 多维0-1背包问题 蚁群算法 交换策略 优化

下载PDF 职称材料

一种对特殊多维0-1背包问题的约束简化方法

13

作者 迟东璇 《锦州师范学院学报（自然科学版）》 2001年第2期11-13,共3页

针对一类组合优化问题—多维 0 - 1背包问题 ( MKP) ,这是一个 NP-难问题 ,提出一种能减少求解难度的方法—约束化简方法。定义了 MKP的紧约束的概念。提出了一种代替多约束组的计算方法。对于经过替换后所得到的新问题 ,证明了与其原... 针对一类组合优化问题—多维 0 - 1背包问题 ( MKP) ,这是一个 NP-难问题 ,提出一种能减少求解难度的方法—约束化简方法。定义了 MKP的紧约束的概念。提出了一种代替多约束组的计算方法。对于经过替换后所得到的新问题 ,证明了与其原问题解精度上的等价性。 展开更多

关键词 NP-难问题 化简约束 紧约束 解精度等价性 组合优化问题 多维0-1背包问题 0-1规划

下载PDF 职称材料