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

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

求解集合联盟背包问题的二次贪心变异乌鸦算法

针对确定性算法难以求解的集合联盟背包问题(Set-Union Knapsack Problem,SUKP),提出了二次贪心变异乌鸦算法(quadratic greedy mutated crow search algorithm,QGMCSA).首先结合SUKP问题模型对贪心策略进行改进,提出了处理其潜在解的二次贪心修复和优化策略;其次,为了扩大乌鸦个体的搜索范围,对乌鸦算法进行变异操作,在跟踪过程中引入莱维飞行;最后,利用三类SUKP实例验证本文算法.仿真结果表明:QGMCSA是比二进制人工蜂群算法求解SUKP的结果更优的一个高效算法.

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

基于拉马克进化的差分进化算法求解KPC问题

具有单连续变量的背包问题(knapsack problem with a single continuous variable,KPC)是标准0-1背包问题的自然推广,在KPC中背包容量不是固定的,因此其求解难度变大。针对现有差分进化(differential evolution,DE)算法在高维KPC实例上求解精度不够高的不足,提出基于拉马克进化的DE(Lamarckian evolution-based DE,LEDE)算法,将贪心修复优化算子产生的改进遗传给后代,以加快DE算法的收敛速度,提高DE算法在高维KPC实例上的求解精度。同时,在贪心修复优化算子中引入基于价值的贪心优化策略,用于优化使用基于价值密度的贪心修复策略生成的可行解,以帮助算法跳出局部最优。在40个KPC实例上对LEDE算法进行了实验分析,结果表明拉马克进化和基于价值的贪心优化策略能够提高LEDE算法的求精能力,LEDE算法在获得最优解和平均解方面均优于其他智能优化算法。

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

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

自适应细菌觅食算法求解折扣{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更优。

一种求解软硬件划分问题的混合编码二进制差分演化算法

软硬件划分(HW/SW)是软硬件协同设计中的一个重要问题,也是一个NP-hard问题。当问题规模较大时,不仅求解困难而且非常耗时。为了快速高效地求解HW/SW,本文提出了一种利用混合编码的二进制差分演化算法(HBDE)求解HW/SW的新思路。首先,根据HW/SW的自身特点提出了一种处理不可行解的贪心修复优化算法GROA。然后,在利用GROA消除不可行解的基础上,使用HBDE求解HW/SW的问题。最后,使用HBDE和遗传算法(GA)求解11个不同规模的HW/SW实例。从计算结果可以看出,对于所有实例,HBDE求解性能明显优于GA,因此基于HBDE求解HW/SW问题是一种高效可行的方法。

基于混合编码的二进制差分演化算法求解软硬件划分问题

软硬件划分(HW/SW)是软硬件协同设计中的一个重要问题,也是一个NP-hard问题。当问题规模较大时,不仅求解困难而且非常耗时。为了快速高效地求解HW/SW,本文提出了一种利用混合编码的二进制差分演化算法(HBDE)求解HW/SW的新思路。首先,根据HW/SW的自身特点提出了一种处理不可行解的贪心修复优化算法GROA。然后,在利用GROA消除不可行解的基础上,使用HBDE求解HW/SW的问题。最后,使用HBDE和遗传算法(GA)求解11个不同规模的HW/SW实例。从计算结果可以看出,对于所有实例,HBDE求解性能明显优于GA,因此基于HBDE求解HW/SW问题是一种高效可行的方法。