A Weight-Coded Evolutionary Algorithm for the Multidimensional Knapsack Problem

A revised weight-coded evolutionary algorithm (RWCEA) is proposed for solving multidimensional knapsack problems. This RWCEA uses a new decoding method and incorporates a heuristic method in initialization. Computational results show that the RWCEA performs better than a weight-coded evolutionary algorithm pro-posed by Raidl (1999) and to some existing benchmarks, it can yield better results than the ones reported in the OR-library.

求解多维背包问题的双决策交互差异算法

针对传统多维背包问题的求解算法存在的修复方式单一、种群动态适应性差等问题,提出一种双决策交互差异算法(DDEA)。融合自主学习思想,设计多维加权价值密度和相对价值概率指标,双重决策确定物品选择顺序,制定相应解的修复优化策略。采用双种群交互差异进化算法,设置主群和辅助群2个种群,种群间进行信息交互,提高种群多样性,避免陷入局部最优,提高算法寻优能力。主群实施差异进化机制,依照个体优劣依次划分为3个子群,分别按照特定方式进化,并在进化过程中完成与辅助群的交互,增强算法群智能性。引入刺激-响应机制,平衡算法的全局和局部搜索能力,并加入精英库协同寻优,加快算法收敛速度。仿真结果表明,DDEA算法可求出全部最优解,平均相对误差率为3.04×10-5,相比于同类算法降低2个数量级,有效提升了多维背包问题的求解精度、效率和稳定性。

基于蚁群数量动态调整的改进蚁群优化算法

蚁群优化(ACO)算法是一种常用的元启发式算法,它通过模拟蚁群寻找食物的过程,为求解多维背包问题(MKP)等NP难(Non-deterministic Polynomial hard)问题提供可行途径。原始ACO算法及其改进算法,通常分为多个轮次,每个轮次均会生成一个蚂蚁种群寻找可行解。在不同轮次中,每轮蚁群中蚂蚁的数量是固定的,因此,如果将其指定一个较大的值,会导致算法出现不必要的时间消耗;反之,如果指定的值较小,则会降低算法全局最优解搜索能力。为此,提出了一种基于蚁群数量动态调整的改进蚁群优化算法ACO-ANDA(ACO algorithm based on Ant Number Dynamic Adjustment),所提算法在可行解搜索过程中,引入了一种新的蚁群数量动态调整机制。在每轮可行解搜索结束后,均根据近几轮可行解和历史最优解之间的关系,调整下一轮蚁群数量,实现对算法时间耗费和最优解搜索能力的平衡。再基于MKP基准测试集SAC-94的多组实验结果表明,相较于原始ACO算法,所提算法能够在最优解利润平均降低0.02%的情况下,平均降低77.85%的时间耗费。

求解多维背包问题的MapReduce蚁群优化算法

应用MapReduce编程模式实现蚁群优化算法的并行化计算,提出基于MapReduce的改进背包问题蚁群算法。通过改进概率计算时机、轮盘赌、交叉、变异等技术,降低蚁群算法的计算复杂度。在云计算环境中应用该算法分布式并行地求解大规模多维背包问题,仿真实验结果表明,该算法能改善蚁群算法搜索时间长的缺陷,增强对大规模问题的处理能力。

求解多维0/1背包问题的二元粒子群算法

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

求解多背包问题的人工鱼群算法

多背包问题是出现在现实世界中许多领域的一个NP-hard组合优化问题。提出一种基于人工鱼觅食,追尾、聚群等行为的求解多背包问题的优化算法。针对多约束导致大量非可行解的产生而使算法性能劣化的问题,采用基于启发式规则的调整算子,使人工鱼始终在可行解域中寻优。数值实验结果表明,提出的算法能够快速搜索到最优解。算法对其他有约束组合优化问题也具有应用价值。

基于有导向变异算子求解多维背包问题

多维背包问题(MKP)是经典的NP难的组合优化问题。引入有导向变异算子的进化算法GM-EA(Guided Mutation EA)来求解该问题,通过结合粒子群优化的方法改进郭涛算法,更好地利用种群中的全局信息,取得较好的效果。实验结果表明GM-EA是求解MKP有效的算法。

求解大规模多背包问题的高级人工鱼群算法

针对复杂的大规模多背包问题,提出了一种基于高级人工鱼群算法的求解方法。为了解决人工鱼群算法收敛速度慢、求解精度低的问题,所提算法通过改进其初始化方法,优化人工鱼个体的行为选择方式和追尾行为来加快问题求解的收敛速度;同时引入了动态视野及步长和人工鱼调整策略来提高算法搜索的精度。仿真实验表明:与现有的算法相比,所提算法不仅能快速收敛,而且可以达到更高的精度,尤其是对于规模越大的多背包问题算法性能提升越明显。

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

本文提出了一种新的组合优化问题—多背包问题,并给出了它的基于0/1规划的数学模型;提出了解决多背包问题的遗传算法。该算法以目标函数加约束惩罚函数作为适应值函数,交叉算子选用了一致交叉的方法,仿真的结果表明该遗传算法在求解多背包问题上的表现是良好的。

贪心二进制狮群优化算法求解多维背包问题

针对经典的多约束组合优化问题——多维背包问题(MKP),提出了一种贪心二进制狮群优化(GBLSO)算法。首先,采用二进制代码转换公式将狮群个体位置离散化,得到二进制的狮群算法;其次,引入反置移动算子对狮王位置进行更新,同时对母狮和幼狮位置重新定义;然后,充分利用贪心算法进行解的可行化处理,增强搜索能力并进一步提高收敛速度;最后,对10个MKP典型算例进行仿真实验,并把GBLSO算法与离散二进制粒子群(DPSO)算法和二进制蝙蝠算法(BBA)进行对比。实验结果表明,GBLSO算法是一种有效的求解MKP的新方法,在求解MKP时具有相对良好的收敛效率、较高的寻优精度和很好的鲁棒性。

改进二进制布谷鸟搜索算法求解多维背包问题

针对多约束组合优化问题——多维背包问题(MKP),提出了一种改进二进制布谷鸟搜索(MBCS)算法。首先,采用经典的二进制代码变换公式构建了二进制布谷鸟搜索(BCS)算法。其次,引入病毒生物进化机制和病毒感染操作,一方面赋予布谷鸟鸟巢位置自变异机制增加种群多样性;一方面将布谷鸟鸟巢位置所组成的主群体的纵向全局搜索和病毒群体的横向局部搜索进行动态结合,进一步提高了算法的收敛速度,降低了陷入局部极值的概率。再次,针对MKP特点设计了不可行解的混合修复策略。最后将MBCS算法同量子遗传算法(QGA)、二进制粒子群优化(BPSO)算法、BCS算法就来源于ELIB数据库和OR_LIB数据库的15个算例进行了仿真对比。实验结果表明,所提算法计算误差均小于1%,标准差小于170,相比这3种算法具有相对更好的寻优精度和求解稳定性,是一种求解多维背包等NP难问题有效的算法。

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

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

改进二进制和声搜索算法求解多维背包问题

和声搜索(HS)是一种已广泛应用于连续优化问题的元启发式方法。针对典型的组合优化问题——多维背包问题(MKP),提出一种改进二进制和声搜索(IBHS)算法。算法通过伯努利随机过程生成二进制群体,在候选和声生成算子中,引入动态自适应参数,通过算法参数的自适应调整来协调算法的全局搜索和局部搜索,并提出一种新的更有效的衡量商品多维加权价值密度的方法用于二进制个体修正和优化;引入精英局部搜索机制进行协同寻优,提高IBHS的收敛速度。通过求解10组不同规模的典型多维背包算例和与贪心二进制狮群优化(GBLSO)算法、改进的差分演化(MBDE)算法以及二进制修正和声(BMHS)算法的对比分析,实验结果表明,所提算法在求解MKP时有具有良好的收敛效率、较高的寻优精度和很好的鲁棒性。

一种新型量子演化算法及其应用研究

针对传统演化算法难以模拟量子物理特性的难题,提出一种新型量子演化算法模型。采用将进化算法与量子计算相结合的方法,在常规染色体结构上附加随机干涉,从数理角度模拟量子计算的叠态、纠缠等特性。将其应用于解决多维背包问题,实验结果表明,该算法能增加种群的基因多样性,并提高全局优化能力。