增强型群论优化算法求解折扣{0-1}背包问题

群论优化算法(GTOA)是基于群论方法提出的一个离散演化算法,非常适于求解以整型向量为可行解的组合优化问题。为了进一步提高GTOA求解折扣{0-1}背包问题(D{0-1}KP)的性能,首先指出了它的随机线性组合算子(RLCO)未能充分考虑当前个体位置信息的不足,基于个体基因保留策略对其进行改进。然后,在随机反向变异算子(IRMO)中引入增强0分量变异策略,用于处理因个体0分量无法及时变异而导致的解的质量下降、种群多样性降低等问题。在改进上述两个算子的基础上,提出了增强型GTOA(EGTOA),并基于它给出求解D{0-1}KP的新方法。随后,将改进策略应用于二进制GTOA(GTOA-2),提出了增强型GTOA-2(EGTOA-2)及其求解D{0-1}KP的新方法。为了验证EGTOA和EGTOA-2的性能提高程度与优异性,分别利用它们求解四类大规模D{0-1}KP实例,通过与GTOA、GTOA-2以及求解D{0-1}KP的已有8个最先进算法的比较表明:EGTOA和EGTOA-2求得最优解的能力比GTOA和GTOA-2提高了至少1.14倍,比8个最先进算法提高了5%~60%,它们的平均性能比GTOA、GTOA-2以及8个最先进算法的性能更佳。因此,EGTOA和EGTOA-2是当前求解D{0-1}KP的最佳算法。

基于DNA链置换反应网络求解0-1背包问题

目的基于DNA链置换的化学反应网络可以作为一种有效的编程语言来解决各种数学问题,而0-1背包问题是一个经典的NP问题。为了求解0-1背包问题。方法提出利用DNA链置换反应网络,并利用Visual DSD设计仿真实验。结果通过加权、求和和阈值3个反应模块进行求解,最后由输出的单链DNA来表达结果。由于浓度的检测存在一定误差,使用带有荧光分子的单链DNA输出表达操作结果。最后,使用DSD仿真软件得到变量转换模块相对应的链置换反应网络图、变量仿真图以及阈值比较图。模型表明,该算法能够有效降低0-1背包问题的复杂度,并且具有较高的求解精度和稳定性。结论所提出的模型进一步丰富了DNA计算,并拓宽了DNA链位移的计算宽度。

求解0-1背包问题的牵制平衡算法

为扩充对于经典NP-hard问题中的0-1背包问题的求解方法,模拟生态系统中各物种间相互依存、牵制,最终达到动态平衡的自然机制,提出一种新型仿生算法:牵制平衡算法。算法以种群规模描述设计变量,以牵制关系为优化驱动力,以系统达到稳态为优化目标,设计了自成长函数、牵制函数、成长函数用以描述设计变量的变化规律,促进解的寻优进程。将牵制平衡算法对于10个不同规模0-1背包问题的求解结果与近年来文献数据进行对比,结果显示算法在8个不同规模的问题中能获得当前已知最优解,验证了牵制平衡算法的收敛性与求解性能,表明算法对于0-1背包问题的求解具有有效性和竞争力。

折扣{0-1}背包问题之分段排序贪心核算法研究

折扣{0-1}背包问题(D{0-1}KP)的贪心核算法是一种近似解算法,常通过估算核区间划分子问题,采用分治算法设计求解算法,算法性能与核区间估计准确性密切相关,核区间估算优化是算法改进的主要途径。在研究{0-1}KP核概念基础上,提出D{0-1}KP核区间的修正定义,构建分段排序策略以缩减核区间规模,改进了D{0-1}KP贪心核算法,设计了修复贪心核动态规划加速算法(RGCADP)、分段排序贪心核动态规划加速算法(RGCADP_PS)。两个算法在D{0-1}KP标准数据集上的实验结果表明:与基本动态规划算法(BDP)相比,RGCADP、RGCADP_PS算法平均求解时间提升率为71.3%、77.2%;RGCADP、RGCADP_PS算法平均解误差率低于粒子群贪心修复算法(PSO-GRDKP)0.5个百分点,低于贪心核加速动态规划(GCADP)算法4.7个百分点;RGCADP_PS时间性能提升率高于RGCADP算法5.9%。

求解0-1背包问题的改进二进制捕鱼算法

经典群智能算法在求解0-1背包问题时普遍存在全局搜索能力不强、求解精度不高、收敛速度慢等缺点。针对这一情况,将二进制编码引入捕鱼算法中,提出二进制捕鱼算法。在此基础上,结合算法本身的特点,添加靠近搜索方法,改善渔夫之间的协作效果;借鉴贪心算法和轮盘赌的思想,设计贪心轮盘赌策略,并结合随机比例参数来改善算法初值;同时引入自适应半径系数来解决步长参数设置的问题,进而提出了一种改进二进制捕鱼算法。实验与对比部分对15个0-1背包问题进行求解测试,结果表明,对于常用算例而言,与其它群智能算法相比,改进二进制捕鱼算法能找到全部问题的最优解,且在总体性能上看较优;对于100维及以上的高维背包问题而言,改进算法在求解精度、稳定性、收敛速度、运行耗时等方面均具有明显优势。因此,将改进二进制捕鱼算法应用于求解0-1背包问题是有效的和可行的。

基于遗传算法求解折扣{0-1}背包问题的研究

目前,求解折扣{0-1}背包问题(D{0-1}KP)的主要算法是基于动态规划的具有伪多项式时间的确定性算法,当D{0-1}KP实例中各项的价值系数与重量系数在大范围内取值时缺乏实用性.文中基于杰出者保留策略遗传算法(EGA)求解D{0-1}KP,首先建立了D{0-1}KP的两个新的数学模型;然后,为了利用EGA和第一数学模型求解D{0-1}KP,提出了一种处理非正常编码个体的贪心修复与优化算法GROA,并将其与EGA相结合给出了求解D{0-1}KP的第一遗传算法FirEGA;紧接着,利用EGA和第二数学模型求解D{0-1}KP,提出了处理非正常编码个体的另一种有效算法NROA,并将其与EGA相结合给出了求解D{0-1}KP的第二遗传算法SecEGA;最后,利用四类大规模D{0-1}KP实例,确定了FirEGA和SecEGA的交叉概率与变异概率的合理取值,比较了两个算法的实际求解性能.对四类实例的计算结果表明:FirEGA和SecEGA都非常适于求解大规模的难D{0-1}KP实例,均能够得到一个近似比非常接近于1的近似解,并且FirEGA的平均求解性能比SecEGA的更优.

基于S型传递函数的二进制乌鸦搜索算法求解0-1背包问题

基于传递函数,我们提出了一种新的二进制乌鸦搜索算法(BCSA)来求解0-1背包问题(0-1KP),它不仅保留了原有乌鸦搜索算法良好的探索能力,而且具有良好的开发能力。充分利用修复优化方法处理不可行解,在提升算法搜索能力的同时,也加快了算法的收敛速度。为验证BCSA求解0-1KP的性能,将其计算结果与七种不同算法的计算结果进行了比较,发现BCSA的求解精度高、算法稳定性良好,非常适合用来处理大规模0-1KP实例。

基于Lagrange插值的学习猴群算法求解折扣{0-1}背包问题

折扣{0-1}背包问题(D{0-1}KP)的目的是在不超过背包载重的前提下,使得装入背包的所有物品价值系数之和为最大。针对已有算法在求解规模大、复杂度高的D{0-1}KP时的求解精度低的问题,提出了Lagrange插值的学习猴群算法(LSTMA)。首先,在基本猴群算法的望过程中重新定义了视野长度;其次,在跳过程中引入了种群中最优的个体作为第二个支点,并调整搜索机制;最后,在跳过程之后引入Lagrange插值操作来提高算法的搜索性能。对四类实例的仿真结果表明:LSTMA在求解D{0-1}KP时的求解精度高于对比算法,并且具有良好的鲁棒性。

求解0-1背包问题的多种算法策略的分析

0-1背包问题是一个经典的组合优化问题,常常被应用于资源分配、物流管理等领域,并且在计算机科学和数学中具有重要的理论价值。解决0-1背包问题有多种策略,常见的策略为动态规划法、回溯法和分支限界法,为了确定对该问题求解的最有效方法,研究三种算法求解的性能表现是十分必要的。通过探讨求解0-1背包问题的三种不同算法,并给出该问题的动态规划法、回溯法和分支限界法的求解思路和算法设计,然后通过实验对比和分析三者的运行时间效率。实验表明,三种算法各具优缺点,要根据问题特点和需求来灵活选择算法。

基于混合贪婪烟花算法求解0-1背包问题

针对组合优化中的经典背包问题,为提高基本烟花算法寻找最优解的局部搜索能力和全局搜索能力,将基本烟花算法、贪婪优化策略和模拟退火算法结合,提出一种改进烟花算法。为保证初始种群的多样性,提出采用Tent映射初始化种群;引入贪心修复算子和贪心优化算子修正中间解;同时引入模拟退火机制使得较差解能有一定概率被接受提高算法跳出局部最优的能力。通过对典型测试函数的求解,发现改进烟花算法能精确求解出Griewank函数的理论最优解;对比基本烟花算法、模拟退火算法和粒子群算法,改进烟花算法能以更高精度寻找Sphere函数最优值。通过对4组不同维度的背包问题的求解,发现改进烟花算法能对于大多数测试数据以较大的概率命中最优解。实验结果说明,改进烟花算法具有较高的求解精度和较快的求解速度,能有效求解0-1背包问题。

扩展SD{0-1}KP背包问题的建模及其遗传算法求解

在SD{0-1}KP的基础上对项集中的物品数由两个扩展为三个,提出扩展SD{0-1}KP问题。在扩展问题中,各项集中物品组合选择情况采取三元组进行编码表示,建立扩展SD{0-1}KP模型,再将贪心策略与遗传算法融合构造求解模型的算法。为验证算法的求解效果,随机生成四种扩展SD{0-1}KP大规模数据实例。求解结果表明:该算法适合求解扩展SD{0-1}KP大规模数据,且效果较好。

基于布谷鸟算法求解折扣{0-1}背包问题

有N个备选集的折扣{0-1}背包问题(D{0-1}KP)的规模大,对智能进化算法的选用要求高,为此提出了基于Levy飞行策略的布谷鸟算法(CS)。首先,利用贪心核加速算法往背包添加部分物品,降低后续计算的复杂度;其次,利用混合编码的布谷鸟算法求解,并对结果中非正常编码进行修复;然后,利用贪心修复策略进一步完善求解结果;最后,通过实验确定CS中相关参数合理取值。通过对四类大规模的D{0-1}KP实例的求解结果表明:CS对于求解大规模D{0-1}KP有很好的计算性能。

高维0-1背包问题的双种群角度调制DE算法

针对高维0-1背包问题,提出一种双种群新型DE算法。该算法采用双种群编码机制,其中一个为低维的实数编码种群,另一个为高维的二进制编码种群。借鉴通信领域的角度调制原理,通过低维种群中的个体,生成高维种群个体,实现将高维优化问题转换到低维空间进行优化求解。此外,新定义丢弃算子对演化过程中的不可行解实时进行修正。仿真实验结果表明了该算法求解高维0-1背包问题的有效性。

折扣{0-1}背包问题的简化新模型及遗传算法求解

当前折扣{0-1}背包问题(D{0-1}KP)模型将折扣关系作为一个新的个体,导致求解过程必需采取修复法对个体编码进行修复,求解方式较少。针对求解方法单一的问题,通过改变模型中二进制的编码表达方式,提出折扣关系不在个体编码中的表达方法。首先,设定对任意折扣关系,当且仅当所涉及个体编码值同时为1(即其乘积为1)时,折扣关系成立,据此建立简化折扣{0-1}背包问题(SD{0-1}KP)模型;然后,针对SD{0-1}KP模型,基于杰出者保留策略(EGA),结合贪心策略(GRE),提出改进遗传算法——第一遗传算法(FG);最后,再结合罚函数法,提出求解SD{0-1}KP高精度罚函数法——第二遗传算法(SG)。结果表明,SD{0-1}KP能够完全覆盖D{0-1}KP问题领域,与FirEGA相比,所提出的两类算法在求解速度方面优势明显,且SG算法首次引入罚函数法,有效地丰富了该问题的求解算法。

改进修复策略遗传算法求解折扣{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。

DNA折纸术在0-1背包问题中的应用

DNA折纸术因其反应的可编程性、纳米可寻址性等优点被广泛地应用于DNA计算中。利用DNA折纸术和杂交链式反应构建0-1背包问题的计算模型。以四个变量的0-1背包问题为例,首先将九种发夹结构和一种分子信标锚定在DNA折纸基底上并加入足量的辅助链;其次通过加入不同的引发链可以触发不同路径上的杂交链式反应,并得到问题的所有可能解;最后,通过荧光信号的数量确定可行解,从而找到问题的最优解。该模型不受权重过大或过小的影响,在折纸基底上可等比例的缩放权重。用Visual DSD软件对该模型进行仿真,模型显示出良好的可行性。

求解0-1背包问题的二进制狼群算法

狼群算法(wolf pack algorithm,WPA)源于狼群在捕食及其猎物分配中所体现的群体智能,已被成功应用于复杂函数求解。在此基础上,通过定义运动算子,对人工狼位置、步长和智能行为重新进行二进制编码设计,提出了一种解决离散空间组合优化问题的二进制狼群算法(binary wolf pack algorithm,BWPA)。该算法保留了狼群算法基于职责分工的协作式搜索特性,选取离散空间的经典问题——0-1背包问题进行仿真实验,具体通过10组经典的背包问题算例和BWPA算法与经典的二进制粒子群算法、贪婪遗传算法、量子遗传算法在求解3组高维背包问题时的对比计算,例证了算法具有相对更好的稳定性和全局寻优能力。

贪心核加速动态规划算法求解折扣{0-1}背包问题

针对现有动态规划算法求解折扣{0-1}背包问题(D{0-1}KP)缓慢的问题,基于动态规划思想并结合新型贪心修复优化算法(NGROA)与核算法,通过缩小问题规模加速问题求解来提出一种贪心核加速动态规划(GCADP)算法。首先利用NGROA对问题进行贪心求解,得到非完整项;然后通过计算得到模糊核区间的半径和模糊核区间范围;最后对于模糊核区间内的物品及同一项集内的物品利用基础动态规划(BDP)算法求解。实验结果表明:GCADP算法适用于求解D{0-1}KP,且在求解速度上相比BDP算法平均提升了76.24%,相比FirEGA算法平均提升了75.07%。

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

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

基于改进的微粒群优化算法的0-1背包问题求解

在介绍微粒群优化算法及其搜索策略的基础上,根据组合约束优化问题的特点,定义了等值变换、异值变换以及变换序列等概念,有针对性地设计了一种适合求解0-1背包问题的特殊微粒群优化算法。实验证明,改进后的微粒群优化算法在求解0-1背包问题上具有可行性和高效性。