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

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

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

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

求解多背包问题的混合蛙跳算法

针对多背包问题,提出一种改进的离散混合蛙跳算法。算法中对青蛙个体采用十进制整数编码方式,应用遗传算法中的交叉操作来对个体进行更新,扩展了传统混合蛙跳算法模型。将改进的算法用于多背包问题求解,仿真实验表明了所提算法的有效性。     

基于佳点集遗传算法的0-1背包问题解决方法

提出了利用数论中的佳点集理论来解决一类典型的优化组合问题——0-1背包问题的新方法。该方法结合遗传算法和贪婪方法,利用佳点集来产生新的交叉算子,优化了子代的选择方法。实验结果证明了该方法的有效性。     

一种基于种群多样度的实数编码并行遗传算法

为了改善遗传算法的收敛性能,提出了一种基于个体适应度的种群多样性度量函数,恰当地反映了遗传算法的进化阶段,预报了早熟收敛的趋势. 设计了基于种群多样度函数的迁移算子和交叉算子,并对交叉、变异概率等进行了动态调整,构成了具有多层迁移特点的实数编码并行遗传算法. 通过和其他优秀遗传算法对测试函数的验证比较,结果表明,该算法对于解决遗传算法中早熟、收敛速度慢等问题具有优越的性能.     

改进的自适应遗传算法求解0/1背包问题

为提高遗传算法求解问题的性能,提出一种改进的自适应遗传算法,该算法在交叉概率和变异概率公式中引入了当代迭代次数因子,提出了基因差别比例（Ca）的概念。Ca越大的基因位发生交叉、变异的概率越大,产生新个体的可能性越大;在模式生成操作中,确定基因位的选取同样由Ca决定。仿真结果表明,此算法在求解0/1背包问题时,其寻优能力有很大提高。     

一种求解0-1背包问题的启发式遗传算法

分析求解背包问题的多种方法,研究背包问题的贪婪策略及最优值的特点,将贪婪策略融入到遗传算法的种群初始化、交叉算子、变异算子中,将分治策略引入到选择算子中,提出一种启发式遗传算法。实验结果表明:算法无论在求解速度上还是在求解质量上都有明显改进。     

多重群体遗传算法在多选择背包问题中的应用

为了解决多选择背包问题,引入了多重群体遗传算法作为求解方法,根据此问题的特点而制定了具体的杂交、变异方法,设计了遗传算法。在算法中以目标函数加惩罚函数为适应值评价函数,采用新陈代谢的选择策略,以更好地保持进化过程中的遗传多样性。实践表明,引入了多重群体遗传算法之后,求解此问题效率有明显的改善与提高。     

一种多模态优化的小生境遗传算法

针对目前多模态优化存在无法找到全部局部极值解的问题,提出了一种改进的小生境遗传算法．该算法在基于淘汰相似机制的小生境遗传算法中引入了预选择机制,并对自适应交叉概率算子和变异概率算子进行了改进,根据群体适应度值的大小来动态调整个体的交叉概率和变异概率大小,并将该算法用于Shubert函数的求解,实验结果表明该方法较之前的小生境遗传算法能够有效的搜寻出全部局部极值,并具有较快的搜索速度．同时,该方法在其他的多峰函数求解上具有通用性．     

基于遗传粒子群优化的嵌入式系统软硬件划分算法

针对单处理器嵌入式系统软硬件划分问题,采用带权有向无环图进行建模,并将之约简,进而转换为多约束条件的0/1背包问题求解.由于基本粒子群优化算法无法求解0/1背包问题,故将遗传算法中的交叉、变异思想引入粒子群优化算法,提出了求解离散组合优化问题的遗传粒子群优化(GPSO)算法,采用两点交叉算子和非均匀变异算子对粒子的位置和速度更新方法进行了重新定义.实验结果表明,采用文中算法能有效地解决软硬件划分问题,具有良好的全局搜索能力,其寻优能力和执行时间优于遗传算法和模拟退火算法.     

Approximate algorithms for some generalized knapsack problems

In this paper we construct approximate algorithms for the following problems: integer multiple-choice knapsack problem, binary multiple-choice knapsack problem and multi-dimensional knapsack problem. The main result can be described as follows: for every ε 0 one can construct a polynomial-time algorithm for each of the above problems such that the ratio of the value of the objective function by this algorithm and the optimal value is bounded below by 1 - ε.     

基于Visual C 的0-1背包问题的动态规划算法

0-1背包问题是经典的NP问题.本文对0-1背包问题的动态规划算法进行了分析,用Visual C 实现该算法.     

An improved monkey algorithm for a 0-1 knapsack problem

The 0-1 knapsack problem is a classic combinational optimization problem. However, many exiting algorithms have low precision and easily fall into local optimal solutions to solve the 0-1 knapsack problem. In order to overcome these problems, this paper proposes a binary version of the monkey algorithm where the greedy algorithm is used to strengthen the local search ability, the somersault process is modified to avoid falling into local optimal solutions, and the cooperation process is adopted to speed up the convergence rate of the algorithm. To validate the efficiency of the proposed algorithm, experiments are carried out with various data instances of 0-1 knapsack problems and the results are compared with those of five metaheuristic algorithms.     

基于0-1背包问题的两种算法

0-1背包问题是计算机科学中一个经典问题,0-1背包问题是一个最优化问题。因其结构简单,可扩展性强,可作为其他问题的子问题,因此通过对其研究可以解决更为复杂的优化问题。本文概述了两种求解0-1背包问题的算法设计方法,并对两种算法进行了分析和比较。     

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

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

0-1背包问题的两种扩展形式及其解法

0-1背包问题是经典的NP-HARD组合优化问题之一,由于其难解性,该问题在信息密码学和数论研究中具有极其重要的应用。首先对01背包问题及其解法进行了分析,然后提出01背包问题的两种扩展形式,并给出了基于动态规划和贪心算法的两种有效算法来解决这两类问题。实验结果验证了所提出方法的有效性。     

多重群体遗传算法在多选择背包问题中的应用

在解决多选择背包问题中，引入了多重群体遗传算法作为求解方法，根据此问题的特点，制定了具体的杂交、变异方法，设计了遗传算法。在算法中以目标函数加惩罚函数为适应值评价函数，采用新陈代谢的跨世代选择策略，以更好地保持进化过程中的遗传多样性。实践表明，引入了多重群体遗传算法之后，求解此问题效率有明显的改善与提高。     

解决0-1背包问题的遗传分布估计算法

0-1背包问题是典型的NP难问题,针对0-1背包问题提出分布估计算法（EDA）与遗传算法（GA）相结合的算法（E-GA）。该算法在每一次迭代中由二者共同产生种群,并行搜索,两种方法产生的个体数目动态变化,将EDA的全局搜索与GA的局部搜索能力、EDA的快速收敛性与GA的种群多样性结合,实现优势互补。通过三个背包问题算例进行算法验证,与以往文献相比,结果显示该算法所获最优值优于文献最优值,运行时间短且收敛速度快。     

基于猴群算法求解0-1背包问题

0-1背包问题是一个经典的NP完全问题,该问题在实际生活中具有广泛的应用.针对现有算法在求解0-1背包问题时精度不高的缺点,提出了一种诱导因子猴群算法.所给诱导因子猴群算法的基本思想是,在基本猴群算法的爬过程中引入诱导因子,诱导其向上爬行,从而可以逃逸局部最优解,找到全局最优解.在仿真试验中,与已有方法进行比较,结果说明利用所给诱导因子猴群算法求解0-1背包问题是有效的.