一种改进的禁忌搜索算法求解背包问题

提出一种改进的禁忌搜索算法来求解背包问题。该算法基于禁忌搜索技术,并采用I&D策略,同时设计了两种针对局部最优解的变异算子。改进后的算法能有效地弥补标准禁忌算法对初始解依赖的缺陷,同时也避免了搜索停滞的现象。通过对具体实例和随机问题的测试,表明改进后的禁忌搜索算法有更好的性能。

多维背包问题的禁忌搜索求解

借鉴认知心理学有关记忆系统的表述,在禁忌搜索算法中引入长时记忆,构造了基于双禁忌表的禁忌搜索算法。多维0-1背包问题的仿真实验表明,该算法是可行的、有效的。

基于禁忌搜索的启发式求解背包问题算法

设计了一种基于禁忌搜索的遗传算法,利用遗传算法提供的并行搜索主框架,结合禁忌算法的个体串行搜索方式,能扩大搜索空间,快速实现全局优化。把基于禁忌搜索的遗传算法与启发式方法相结合用来求解背包问题,经过计算机仿真,其优化性能指标及搜索效率均有大幅度的提高。

求解0-1背包问题的基于双禁忌对象的TS算法

0-1背包问题是一个典型的组合优化问题.针对这个问题,给出了一种基于双禁忌对象的禁忌搜索求解算法.该算法首先以解向量的分量为解对象进行禁忌搜索,当这个搜索过程完成后,然后以当前最优解为初始解对象再进行禁忌搜索.实验结果表明该算法可有效地解决0-1背包问题.

高效软硬件划分算法及其提升技术

软硬件划分是软硬件协同设计的关键环节,它决定系统中哪些组件由软件实现,哪些由硬件实现。软硬件划分问题已被证明是NP完全问题。将一类软硬件划分问题看作变异的0-1背包问题,在求解背包问题的算法基础上构造出软硬件划分问题的优质启发解。此外,采用禁忌搜索(Tabu Search)算法对求得的启发解进行改进,在软件开销和通信开销满足一定约束的条件下,使得硬件开销尽可能小。实验结果证明,所提算法对当前最新算法的改进最大可达到28%。

改进禁忌搜索算法求解CVRP问题

改进了禁忌搜索算法,用于解决带有容量限制的车辆路径问题(CVRP)。该算法在标准禁忌搜索算法的基础上,采用了I&D搜索策略,给出了两种作用于局部最优解的变异算子来扩大搜索区域,并设计了一种CVRP问题的初始解的产生方式。改进后的算法克服了标准禁忌搜索算法对初始解的依赖较强的缺陷,减小了算法在搜索过程中陷入局部最优的可能,提高了算法的搜索质量与效率。

基于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),提出了基于差分演化策略的混沌乌鸦算法(DECCSA)。首先,采用混沌映射生成初始乌鸦种群;然后,采用混合编码方式和贪心修复与优化策略(GROS)解决了D{0-1}KP的编码问题;最后,引入差分演化策略提高算法的收敛速度。对4类大规模D{0-1}KP实例的计算结果表明:DECCSA比遗传算法、细菌觅食算法和变异蝙蝠算法求得的最好值和平均值更优,能得到最优解或更好的近似解,非常适于求解D{0-1}KP。

Memetic算法求解多维背包问题

针对多维背包问题较难找到全局最优解的情况,提出了一种求解多维背包问题的Memetic算法,该算法主要由带反馈机制的禁忌局部搜索算法、交叉算子和种群更新策略组成.其中,种群更新策略需要同时考虑种群中解的质量与种群的多样性,以提高算法搜索的多样性.测试表明,该算法能够有效避免陷入局部最优解并找到比现有算法更好的结果.