求解随机时变背包问题的精确算法与进化算法

随机时变背包问题(RTVKP)是一种新的动态背包问题,也是一种新的动态组合优化问题,目前它的求解算法主要是动态规划的精确算法、近似算法和遗传算法.本文首先利用动态规划提出了一个求解RTVKP问题的新精确算法,对算法时间复杂度的比较结果表明:它比已有的精确算法更适于求解背包载重较大的一类RTVKP实例.然后,分别基于差分演化和粒子群优化与贪心修正策略相结合,提出了求解RTVKP问题的两个进化算法.对5个RTVKP实例的数值计算结果比较表明: 精确算法一般不宜求解大规模的RTVKP实例,而基于差分演化、粒子群优化和遗传算法与贪心修正策略相结合的进化算法却不受实例规模与数据大小的影响,对于振荡频率大且具有较大数据的大规模RTVKP实例均能求得的一个极好的近似解.     

一种求解动态背包问题的离散粒子群优化算法

动态背包问题(DKP)是一类经典的动态优化问题,可以用来描述许多实际的问题。迄今为止,针对动态背包问题的研究主要集中在遗传算法上,而对粒子群优化算法的研究较少。在离散粒子群优化模型的基础上,引入环境变化的探测以及环境变化后的响应机制,提出一种求解动态背包问题的离散粒子群优化算法(DSDPSO)。将该算法和现有经典的自适应原对偶遗传算法(APDGA)在两个动态背包问题上进行了对比实验,结果表明,DSDPSO算法在环境变化后能迅速地找到最优解并稳定下来,更适合于求解动态背包问题。     

利用动态规划算法解决购物单问题

购物单问题是0-1背包问题的一种应用,解决购物单问题已有贪婪法,动态规划法,蚁群算法,回溯法等.动态规划算法是求解决策过程最优化的方法,通常用于求解具有某种最优性质的问题.根据动态规划原理解决购物单问题,说明了动态规划算法解决实际生活问题的高效性.     

利用遗传算法求解静态与动态背包问题的研究

为了有效处理遗传算法在求解静态与动态背包问题时产生非正常编码个体的问题,在分析已有处理方法不足的基础上,基于贪心策略提出了一种贪心修正算子与贪心优化算子相结合的新方法,并将该方法与遗传算法相融合给出了求解静态与动态背包问题的有效算法.仿真计算结果表明,在求解静态与动态背包问题时,利用所提出的新方法不仅可以解决非正常编码个体的问题,而且还能够显著提高个体所对应的可行解的质量,极大地改善了遗传算法的求解效果.     

基于0/1背包问题的算法探究

0／1背包问题是计算机科学中的一个经典问题。动态规划法，递归法，回溯法是求解该问题的三种典型方法，使用这三种方法求解0／1背包问题，并对各算法进行了理论分析。用不同规模的0／1背包问题对三种算法进行测试，比较它们的运行时间，发现测试结果与其理论分析结果相符．最后指出就求解不同规模的0／1背包问题而言各算法的优劣。     

约束动态免疫算法及对背包问题性能测试研究

借鉴人工免疫系统的记忆、动态识别等功能,提出一种约束动态免疫算法(CDIOA),并用于高维约束动态背包问题的求解。通过随机约束选择策略选择可行及非可行抗体,非可行抗体参与群体的进化;利用抗体修正策略确保进化群中有一定比例可行抗体,提高算法搜索功能;设计环境识别模块判断环境变化与否,建立环境记忆池保存较优秀记忆细胞,记忆细胞参与相似(相同)环境初始群的产生,加速算法在相似环境搜索速度。建立三种不同环境的动态背包问题作为标准测试实例,将CDIOA与已有的四种动态优化算法进行测试比较,结果表明:CDIOA对各测试问题在不同环境表现出较好的收敛性能,在相似环境能快速跟踪最优值。     

基于模拟退火选择的动态免疫算法及其应用

借鉴人工免疫系统的记忆、动态识别等功能及模拟退火选择理论,提出一种适用于求解动态环境优化问题的动态免疫算法(DIASA),并将其用于高维动态约束背包问题。算法设计包括:(1)抗体的亲和力随群体进化而变化;(2)可行抗体被克隆和动态突变,突变概率与抗体浓度相关,而非可行抗体按价值密度贪婪修正;(3)新环境初始群经环境识别算子按不同方式生成,相似环境初始群由记忆细胞及随机抗体产生。数值实验中,选取著名的动态进化算法(ETGA)和动态免疫遗传算法(ISGA),通过不同难度的高维动态约束背包问题进行仿真比较,结果表明:DIASA较算法ISGA和ETGA对不同问题在各环境内表现较强的优化性能,群体中抗体多样性保持较好,能快速跟踪不同环境的最优值,收敛性强。     

背包问题的算法设计与分析研究

背包问题是算法设计分析中的经典问题,本文采用贪婪法、动态规划法及递归法三种方法分别对背包问题、0-1背包问题及简单0-1背包问题进行算法设计和时间复杂度分析,给出具体算法设计和实现过程,并以具体实例详细描述不同方法求解问题解时算法基本思想,总结三种方法实现的优缺点并得出结论。     

背包问题的算法设计与分析研究

背包问题是算法设计分析中的经典问题,本文采用贪婪法、动态规划法及递归法三种方法分别对背包问题、0-1背包问题及简单0-1背包问题进行算法设计和时间复杂度分析,给出具体算法设计和实现过程,并以具体实例详细描述不同方法求解问题解时算法基本思想,总结三种方法实现的优缺点并得出结论。     

0/1背包问题

本文对“0／1背包问题”采用贪婪算法、动态规划、回溯法、分枝限界四种不同方法进行求解和算法分析．并通过各种算法的实现．研究了0／1背包问题的实质。     

An efficient algorithm for the collapsing knapsack problem

The collapsing knapsack problem (CKP) is a type of nonlinear knapsack problem in which the knapsack size is a non-increasing function of the number of items included. This paper proposes an exact algorithm for CKP by partitioning CKP to some subproblems, then solving them with the improved expanding-core technique. The proposed algorithm solves the subproblems in the special processing order resulting in the reduction of computing time. Experimental results show that the proposed algorithm is an efficient approach for various random instances of size up to 1000.     

一种求解0-1背包问题的快速蚁群算法

0-1背包问题是典型的NP完全问题,且蚁群算法已成功地解决了许多组合优化的难题。因此,文中介绍一种基于蚁群算法求解0-1背包问题的算法,并对此算法进行优化,提出一种求解0-1背包问题的快速蚁群算法。它大大减少了蚁群算法的搜索时间,有效改善了蚁群算法易于过早地收敛于非最优解的缺陷,当物品数较大时,也取得了较好的求解质量。仿真实验取得了较好的结果。     

An improved firefly algorithm for solving dynamic multidimensional knapsack problems

There is a wide range of publications reported in the literature, considering optimization problems where the entire problem related data remains stationary throughout optimization. However, most of the real-life problems have indeed a dynamic nature arising from the uncertainty of future events. Optimization in dynamic environments is a relatively new and hot research area and has attracted notable attention of the researchers in the past decade. Firefly Algorithm (FA), Genetic Algorithm (GA) and Differential Evolution (DE) have been widely used for static optimization problems, but the applications of those algorithms in dynamic environments are relatively lacking. In the present study, an effective FA introducing diversity with partial random restarts and with an adaptive move procedure is developed and proposed for solving dynamic multidimensional knapsack problems. To the best of our knowledge this paper constitutes the first study on the performance of FA on a dynamic combinatorial problem. In order to evaluate the performance of the proposed algorithm the same problem is also modeled and solved by GA, DE and original FA. Based on the computational results and convergence capabilities we concluded that improved FA is a very powerful algorithm for solving the multidimensional knapsack problems for both static and dynamic environments.     

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

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

基于模运算的新颖离散差分演化算法求解多背包问题

多背包问题（MKP）是一个求解难度极大的背包问题。为了基于差分演化（DE）求解MKP,首先建立了MKP的整数规划模型,在利用模运算构造简单且有效的新型传递函数基础上,提出了一个新颖离散差分演化算法MODDE;基于贪心策略提出了消除MKP不可行解的一个有效算法GROA,由此利用MODDE给出了求解MKP的一种新方法。最后,利用MODDE求解30个国际通用的MKP实例,通过与四个代表性演化算法的比较表明,MODDE不仅计算结果优,而且算法的稳定性强,是求解MKP的一个高效算法。     

混合差异演化算法求解多维背包问题

提出了一种求解多维0-1背包问题的混合差异演化算法,算法使用了两个主要的思想策略,即依据物品单位容积价值的高低选择物品的贪婪算法和基于二进制编码的差异演化算法。对10个测试算例进行了仿真试验,结果表明文章提出的算法可以快速找到这些测试算例的最优解,是求解多维背包问题的一种有效方法。     

Solving efficiently the 0–1 multi-objective knapsack problem

In this paper, we present an approach, based on dynamic programming, for solving the 0–1 multi-objective knapsack problem. The main idea of the approach relies on the use of several complementary dominance relations to discard partial solutions that cannot lead to new non-dominated criterion vectors. This way, we obtain an efficient method that outperforms the existing methods both in terms of CPU time and size of solved instances.     

一种求解多维0-1背包问题的拟人算法

在项目决策与规划,资源分配,货物装载等工作中,提出了多维0-1背包问题,对这一问题,国内外学者提出了诸如模拟退火算法,遗传算法,蚁群算法及其它一些启发式算法等求解算法。该文提出了一种新的启发式求解算法。该算法使用了两个主要的思想策略,即依据物品单位容积价值的高低选择物品并对其进行标记的策略和拟人跳坑策略。用本文提出的算法,对55个测试算例进行了实算测试,得到了其中54个算例的最优解。测试结果表明,用该文提出的拟人算法求解多维0-1背包问题,计算结果的优度高,计算时间短,是求解此问题的有效算法。