增强型群论优化算法求解折扣{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的最佳算法。

基于遗传算法求解折扣{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的更优.

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

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

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

折扣{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。

贪心核加速动态规划算法求解折扣{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}背包问题的改进动态规划算法

集值折扣{0-1}背包问题(Discounted{0-1}Knapsack Problem with Setup,D{0-1}KPS)指在同一类别中可选择多个项,每个类别对目标函数和约束条件都增加了额外的固定设置成本。提出一种求解D{0-1}KPS的改进动态规划算法,算法针对D{0-1}KPS问题本身结构特征,融合多目标优化问题中非支配解集思想,通过利用状态之间的支配与非支配关系,对每个阶段的状态集进行剪枝,形成非支配状态集,从而提出改进动态规划算法。通过实例验证了该算法的有效性和可行性。

改进蚁群优化算法求解折扣{0-1}背包问题

折扣{0-1}背包问题(Discounted{0-1}Knapsack Problem,DKP)是一个NP-困难的组合优化问题,尽管已经存在一些求解DKP的智能优化算法,但目前尚没有用蚁群优化(Ant Colony Optimization,ACO)算法求解DKP的研究。提出了一个求解DKP的改进ACO(Modified ACO,MACO)算法。MACO算法使用整数编码以保证每组物品最多只有一个物品被选中,在MACO算法构造解的每一步,采用组内竞争选择来降低算法的时间复杂性,对计算选择概率的公式,放弃启发式信息以减少参数并简化算法参数设置,对蚂蚁构造出的解,经修复后使用基于价值密度和价值的混合贪婪优化算子来提高算法的寻优能力。在四类测试用例上对MACO算法进行了测试并与其他算法进行比较,实验结果表明MACO算法的性能明显优于其他算法。

差分进化帝王蝶优化算法求解折扣{0-1}背包问题

帝王蝶优化算法(Monarch Butterfly Optimization,MBO)是一种新颖的群体智能算法,自从提出就在实际优化问题上表现出很好的性能.但是,帝王蝶优化算法的迁移算子采用随机选择两个个体来生成新个体,并没有记忆整个种群的最优解,容易造成全局最优帝王蝶搜索经验的丢失.根据MBO寻优过程的内在机制以及差分进化算法的变异算子能够利用个体间的差异信息,将MBO分别与目前性能最优、应用范围最广的7种差分进化(Differential Evolution,DE)变异策略相结合,实验验证了7种不同算法的性能.基于性能最优的DE/best/2/bin变异模式,提出了一种差分进化帝王蝶优化算法(Monarch Butterfly Optimization Algorithm with Differential Evolution,DEMBO),使得算法能够记忆种群最优解并实现种群内部信息的充分共享,达到既加快收敛速度又提高解的精度的目的.在30个典型折扣{0-1}背包问题(D{0-1}KP)实例上进行了一系列实验,实验结果表明:(1)DEMBO能够在时间复杂度不变的条件下,显著提高算法的求解精度和收敛速度;(2)DEMBO在求解所有D{0-1}KP实例时,均能够获得一个近似比非常接近1的近似解.

变异蝙蝠算法求解折扣{0-1}背包问题

针对确定性算法难于求解规模大、数据范围广的折扣{0-1}背包问题(D{0-1}KP),提出了基于蝙蝠算法的快速求解D{0-1}KP的变异蝙蝠算法(MDBBA)。首先,利用双重编码解决D{0-1}KP的编码问题;其次,将贪心修复与优化算法(GROA)应用于蝙蝠个体适应度计算中,使算法快速得到有效解;然后,选择使用差分演化(DE)的变异策略提高算法的全局寻优能力;最后,蝙蝠个体按一定概率进行Lévy飞行,增强算法探索能力和跳出局部极值的能力。对四类大规模实例的仿真计算表明:MDBBA非常适于求解大规模的D{0-1}KP,比第一遗传算法(FirEGA)和双重编码蝙蝠算法(DBBA)求得的最优值和平均值都更优,MDBBA收敛速度明显快于DBBA。

基于差分演化策略的混沌乌鸦算法求解折扣{0-1}背包问题

针对确定性算法难于求解的各项的重量系数和价值系数在大范围内取值的折扣{0-1}背包问题(D{0-1}KP),提出了基于差分演化策略的混沌乌鸦算法(DECCSA)。首先,采用混沌映射生成初始乌鸦种群;然后,采用混合编码方式和贪心修复与优化策略(GROS)解决了D{0-1}KP的编码问题;最后,引入差分演化策略提高算法的收敛速度。对4类大规模D{0-1}KP实例的计算结果表明:DECCSA比遗传算法、细菌觅食算法和变异蝙蝠算法求得的最好值和平均值更优,能得到最优解或更好的近似解,非常适于求解D{0-1}KP。

基于Lévy飞行的差分乌鸦算法求解折扣{0-1}背包问题

针对大规模的折扣{0-1}背包问题(D{0-1}KP)难以用确定性算法求解的问题,提出了基于Lévy飞行的差分乌鸦算法(LDECSA)。首先,利用混合编码解决D{0-1}KP的第二数学模型的编码问题;其次,利用新的贪心修复与优化算法(NROA)处理求解过程中产生的不可行解;然后,针对乌鸦个体过早陷入局部最优和收敛较慢等缺陷,引入Lévy飞行和差分策略;最后,通过实验确定了感知概率和飞行长度的合理取值以及差分策略的选择。对四类大规模D{0-1}KP实例的计算结果表明:LDECSA非常适合求解大规模D{0-1}KP,能得到满意的近似解。

基于细菌觅食算法求解折扣{0-1}背包问题的研究

折扣{0-1}背包问题(D{0-1}KP)是新型的0-1背包问题。提出了基于细菌觅食算法(BFO)求解D{0-1}KP的方法,首先描述了D{0-1}KP的两个数学模型,然后将BFO分别与两个数学模型相结合,即细菌个体分别采用二进制向量和四进制向量的编码方法,并利用贪心策略优化初始解和修复非正常编码个体,给出了求解D{0-1}KP的FirBFO和SecBFO算法。对四类实例的计算结果表明,FirBFO和SecBFO都非常适于求解大规模的D{0-1}KP实例,能得到最优解或近似比接近1的近似解。

核加速遗传算法求解折扣{0-1}背包问题

针对现有遗传算法求解折扣{0-1}背包问题(D{0-1}KP)易陷入局部最优解,同时存在大量无效交叉变异操作使得算法收敛较慢等问题,本文基于精英保存策略(EGA)和贪心修复算法(GROA),将核算法与遗传算法进行融合,提出求解D{0-1}KP的核加速遗传算法(CEGA)。将CEGA用于求解四类大规模D{0-1}KP实例,结果表明:CEGA适用于求解D{0-1}KP,且精确度和收敛速度均好于第一遗传算法(FirEGA)。

自适应细菌觅食算法求解折扣{0-1}背包问题

针对确定性算法难以求解的大规模折扣{0-1}背包问题(D{0-1}KP),提出了自适应细菌觅食算法(ABFO)求解D{0-1}KP的两种算法。首先,给出了D{0-1}KP的两种数学模型;然后,针对细菌觅食算法的趋化操作提出了自适应趋化策略;最后,利用两种贪心修复与优化策略处理两种数学模型中的不可行解,得到求解D{0-1}KP的Fir ABFO和Sec ABFO算法。仿真实验表明,Fir ABFO和Sec ABFO均能得到最优解或近似比几乎等于1的近似解,非常适于求解D{0-1}KP,并且Sec ABFO的求解性能比Fir ABFO更优。

求解折扣{0-1}背包问题的新遗传算法

折扣{0-1}背包问题(Discounted{0-1}Knapsack Problem,D{0-1}KP)是比0-1背包还要难以求解的NP-hard问题。提出了一种求解D{0-1}KP的新遗传算法GADKP。GADKP针对D{0-1}KP问题本身结构特征,借鉴启发式搜索思想设计了3种有效的交叉算子和1种变异算子。4种算子的操作都能够保证进化过程中解的可行性;3种交叉算子从3个不同的角度提高算法的搜索能力;变异算子采用逐层贪心机制提高个体的局部开发能力。通过4组共40个D{0-1}KP实例测试,和已有的求解D{0-1}KP的遗传算法相比,GADKP求解精度更高,是一种新颖有效的求解D{0-1}KP的方法。

折扣{0-1}背包问题粒子群算法的贪婪修复策略探究

群智能启发式算法求解折扣{0-1}背包问题(D{0-1}KP)时,为提升求解效率和求解质量,需采用某种修复与优化策略将非正常编码个体转换为符合解约束条件的编码个体。在引入项集价值密度概念基础上,以粒子群算法(PSO)为例,提出一组基于项集的贪婪修复与优化方法(group greedy repair and optimization algorithm,GGROA),并进一步构造PSO-GGRDKP算法(PSO based GGROA for solving D{0-1}KP)以探究GGROA方法的可行性和性能。PSO-NGROADKP(PSO based NGROA for solving D{0-1}KP)和PSO-GRDKP(PSO based GROA for solving D{0-1}KP)是基于项贪心修复与优化方法的粒子群算法。在D{0-1}KP标准数据集的实验结果表明:与PSO-NGROADKP和PSO-GRDKP相比,PSO-GGRDKP算法的解误差率略高,但算法时间性能分别提升了13.8%、12.9%。

基于离散混合多宇宙算法求解折扣{0-1}背包问题

为了利用多宇宙算法(MVO)求解折扣{0-1}背包问题(D{0-1}KP),基于模运算建立了离散型隧道模型和离散虫洞模型,引入具有反向搜索与突变特性的局部搜索策略,提出了第一个具有四进制编码的离散混合多宇宙算法DHMVO。在利用修复与优化算法消除不可行解的基础上,基于DHMVO提出了求解D{0-1}KP的一个新方法。为了检验DHMVO求解D{0-1}KP的性能,利用Kruskal-walli检验确定了其参数的最佳取值;将DHMVO求解四类大规模D{0-1}KP实例的计算结果与已有最好算法的计算结果进行比较,比较结果表明:DHMVO比其他算法的求解精度更高、稳定性更强,非常适合高效求解大规模D{0-1}KP实例。