改进修复策略遗传算法求解折扣{0-1}背包问题

第一遗传算法（FirEGA）在求解折扣{0-1}背包问题（D{0-1}KP）过程中对非正常编码的修复未能较好运用物品折扣关系,影响修复效果,导致求解结果不理想。针对该问题,对FirEGA中的贪心修复与优化算法（GROA）进行修正：传统贪心修复按照价值密度对项进行选取,当出现同一项集中两个项均被选取时,文中不再选取价值密度较大项,而是选择价值较大项,得到处理非正常编码个体的新的贪心修复优化算法（NGROA）。在FirEGA中采用NGROA,构成求解D{0-1}KP新的第一遗传算法（NFirEGA）。最后,利用NFirEGA求解四类大规模D{0-1}KP问题,结果表明,NFirEGA在求解精度上明显优于FirEGA。     

基于蜂群遗传算法的0-1背包问题

针对0-1背包问题,本文提出了基于蜂群遗传算法的优化求解方案。该算法包括两个种群,一个主要用于全局搜索,另一个主要用于局部搜索;每个个体采用二进制编码;采用最优个体交叉策略;对当前解的处理措施是将还未装入背包且性价比最好的物品装进背包,直至不能装为止;不符合约束条件的解采用诱变因子指导变异处理;遗传算子包括单点交叉算子、简单变异算子、主动进化算子和抑制算子。本算法充分发挥了遗传算法的群体搜索和全局收敛的特性,快速地并行搜索,有效地克服了经典遗传算法容易陷入局部最优问题。数值实验表明,该算法在求解0-1背包问题中取得了较好的效果,同样可以应用于其它的组合优化问题。     

求解多限制0-1背包问题的混合遗传算法

为求解多限制0-1背包问题,设计一种新的价值密度,提出一种基于贪心法的混合遗传算法,采用二进制编码对适应值进行升序排列,并运用轮盘赌选择方法对背包资源利用不足的可行解进行修正处理,对不可行解进行修复处理,并将其与传统遗传算法进行比较。实验结果表明,该算法能够有效提高问题求解的速度和精度,具有一定优越性。     

0-1背包问题及其算法分析

0-1背包问题是算法设计分析中的经典问题,本文主要通过对回溯法、动态规划、贪心算法和遗传算法的研究,分析这四种方法在求解0-1背包问题时的优缺点并进行了比较.     

一种基于模式替代的遗传算法解0/1背包问题*

背包问题是一个典型的 NP完全问题。提出一种基于模式替代的遗传算法解0/1背包问题思想,通过收集每代种群中最好的几个个体生成模式来引导种群的搜索方向,以提高遗传算法的搜索速度和寻找最优解的能力。通过仿真数值实验,将该方法与简单遗传算法、贪心算法计算结果比较分析,充分证明了使用基于模式替代遗传算法来求解背包问题的有效性和实用性。     

几种背包问题的算法分析与比较

背包问题是算法设计分析中的经典问题,本文主要通过对回溯法、动态规划、贪心算法和遗传算法的研究,比较这四种方法在求解背包问题时的优缺点。     

二进制混合蛙跳算法求解0-1背包问题

为利用混合蛙跳算法（SFLA）求解具有二进制编码特点的组合优化问题,基于双重编码机制,提出了一种二进制混合蛙跳算法（记为BSFLA）。基于罚函数法和贪心变换策略,探讨了利用BSFLA求解背包问题（KP）的可行性与有效性。计算结果表明BSFLA与贪心策略相结合是求解KP问题的一种有效的新方法。     

求解多背包问题的混合遗传算法

针对多背包问题最优解的求解,设计了一种新的价值密度;在此基础上结合传统的贪心算法,提出了一种求解多背包问题的混合遗传算法。该算法采用整数编码,并采用轮盘赌选择方法,对背包资源利用不足的可行解进行修正处理,对不可行解进行修复处理。并在大量的数值实验的基础上,将该方法与传统方法及简单遗传算法进行比较,实验结果表明,该混合遗传算法提高了问题求解的速度和精度,有一定的优越性。     

利用双重结构编码PSO求解动态背包问题

时变背包问题（TVKP）是一种典型的动态组合优化问题,由于其中某些量的动态变化,导致此问题非常难以求解。基于双重结构编码微粒群算法（DPSO）与贪心修正策略（GCOS）相结合,给出了一种求解TVKP 的新方法,通过对2个大规模TVKP实例的仿真计算表明：该方法比原对偶遗传算法适应环境变化能力和跟踪最优解的能力更强,非常适于求解TVKP问题。     

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

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

求解0-1背包问题的混沌遗传算法

提出一种改进的混沌遗传算法来求解0-1背包问题。通过利用幂函数载波技术增强混沌搜索的遍历性,把混沌搜索得到的最优解直接作为新群体嵌入遗传算法来改善遗传算法的早熟问题,从而使算法有能力避免陷入局部极值而快速收敛于全局最优解。仿真实验结果表明了该算法求解0-1背包问题的有效性和适用性。     

文化基因算法在多约束背包问题中的应用

文化基因算法是一种启发式算法,与一些经典数学方法相比,更适于求解多约束背包问题.文化基因算法是一种基于种群的全局搜索和基于个体的局部启发式搜索的结合体,针对多约束问题,提出采用贪婪策略通过违反度排序的方法处理多约束条件,全局搜索采用遗传算法,局部搜索采用模拟退火策略,解决具有多约束条件的0-1背包问题.通过对几个实例的求解,表明文化基因算法与标准遗传算法相比,具有更优的搜索性能.     

Embedding cryptographic trapdoors in arbitrary knapsack systems

In this paper we show that after sufficiently many modular multiplications, any knapsack system becomes a trapdoor system that can be used in public-key cryptography.     

基于动态规划法求解动态o-1背包问题

随机时变背包问题(RTVKP)是一种动态组合优化问题,也是一种典型的NP-hard问题。由于RTVKP问题中物品的价值、重量和背包载重均是动态变化的,导致问题的求解非常困难。在动态规划法基础上,提出了一种求解背包载重随机变化的RTVKP问题的确定性算法,分析了其复杂度和成功求解需要满足的条件。对两个大规模实例的计算表明,该算法是求解RTVKP问题的一种高效算法。     

一种带修复函数的QGA及其在背包问题中的应用

提出了一种带修复函数的量子遗传算法来求解背包问题。该算法采用量子比特概率编码方式构造染色体，由量子旋转门操作实现种群进化。在求解背包问题时，采用修复函数来修正不可行编码。文中给出了该算法的具体实现方法和流程，并用几个典型背包问题实例对其进行测试，结果表明带修复函数的量子遗传算法在求解背包问题时，综合性能优于传统遗传算法。     

一种新的求解多维背包问题的分散算法

为了避免蚁群算法在优化搜索过程中易陷入局部最优和早熟收敛,提出一种求解多维背包问题的新型分散搜索算法。该算法是把蚁群算法的构解方法引入到分散搜索算法中,在搜索过程中,既考虑解的质量,又考虑解的分散性。同时,该分散算法还采用了动态更新参考集与阈值接收算法的阈值参数,以控制搜索空间来加快收敛速度。通过选取国际通用MDKP实例库中的多个实例进行测试表明,该算法可以避免陷入局部最优解,能提高全局寻优能力,其结果优于其他现有的方法,并获得了较好的结果。     

A novel differential evolution mapping technique for generic combinatorial optimization problems

Differential evolution is primarily designed and used to solve continuous optimization problems. Therefore, it has not been widely considered as applicable for real-world problems that are characterized by permutation-based combinatorial domains. Many algorithms for solving discrete problems using differential evolution have been proposed, some of which have achieved promising results. However, to enhance their performance, they require improvements in many aspects, such as their convergence speeds, computational times and capabilities to solve large discrete problems. In this paper, we present a new mapping method that may be used with differential evolution to solve combinatorial optimization problems. This paper focuses specifically on the mapping component and its effect on the performance of differential evolution. Our method maps continuous variables to discrete ones, while at the same time, it directs the discrete solutions produced towards optimality, by using the best solution in each generation as a guide. To judge its performance, its solutions for instances of well-known discrete problems, namely: 0/1 knapsack, traveling salesman and traveling thief problems, are compared with those obtained by 8 other state-of-the-art mapping techniques. To do this, all mapping techniques are used with the same differential evolution settings. The results demonstrated that our technique significantly outperforms the other mapping methods in terms of the average error from the best-known solution for the traveling salesman problems, and achieves promising results for both the 0/1 knapsack and the traveling thief problems.     

基于文化进化的并行粒子群算法

为了改善粒子群算法对大规模问题求解的性能,提出一种基于文化进化的并行粒子群算法,阐述了该算法的原理和具体实施方案。选取背包问题作为算法的应用对象,通过对仿真实例进行计算和结果比较,表明该算法在最优值、求解速度、稳定性等方面具有较好的 效果。     

The multiobjective multidimensional knapsack problem: a survey and a new approach

The knapsack problem (KP) and its multidimensional version (MKP) are basic problems in combinatorial optimization. In this paper, we consider their multiobjective extension (MOKP and MOMKP), for which the aim is to obtain or approximate the set of efficient solutions. In the first step, we classify and briefly describe the existing works that are essentially based on the use of metaheuristics. In the second step, we propose the adaptation of the two‐phase Pareto local search (2PPLS) to the resolution of the MOMKP. With this aim, we use a very large scale neighborhood in the second phase of the method, that is the PLS. We compare our results with state‐of‐the‐art results and show that the results we obtained were never reached before by heuristics for biobjective instances. Finally, we consider the extension to three‐objective instances.