求解折扣{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的方法。

改进的差分演化算法求解多维背包问题

多维背包(MKP)是组合优化中一个典型的NP难问题,广泛应用于工程和管理中。提出了一种改进的二进制差分演化算法(Modified Binary Differential Evolution algorithm,MBDE)求解MKP问题,算法关键步骤可分为两部分:二进制群体生成;得到候选可行解。提出了一种有效的衡量商品价值密度的方法用于对二进制个体修正和优化;设计了反向测试搜索和精英局部搜索策略来提高算法探索和开发能力,从而进一步提高了MBDE的求解精度和收敛速度。为验证MBDE算法的有效性,进行了三组实验,并和近期提出的解决MKP问题的其他启发式算法进行了比较,实验结果显示,MBDE算法求解精度更高。从算法运行时间看,求解速度快,非常适合求解大规模的MKP问题。

改进的教与学优化算法求解集合联盟背包问题

针对集合联盟背包问题(set-union knapsack problem,SUKP)难以使用确定性算法求解的情况,提出了一种快速求解SUKP问题的改进二进制教与学优化算法(modified binary teaching-learning-based optimization,MBTLBO)。首先,给出了教与学优化算法的二进制编码方法;然后,针对求解SUKP问题中的候选解,提出改进的修复优化策略(modified SUKP greedy repairing and optimization algorithm,MS-GROA)。该策略增加了修复后可行解的二次优化,从而提升了对SUKP问题的求解精度。另外为了克服教与学优化算法易早熟,求解精度低,后期收敛速度慢等弱点,在"教"阶段和"学"阶段引入差分算法的交叉算子,通过平衡算法的开发能力和勘探能力,避免算法过早陷入局部极值;在精英个体周围按正态分布进行自适应局部搜索,提高算法的收敛速度和求解精度。三类SUKP实例测试表明,MBTLBO算法具有较高的求解精度和更快的收敛速度,是有效求解SUKP问题的方法。

基于精英反向学习的阶段性变异杂草算法

提出了基于精英反向学习的阶段性变异杂草算法(Elite opposition-based learning mutil-stage mutated invasive weed optimization,EOMMIWO).该算法将正态分布的标准差初始值和终止值由固定设置转化为根据问题自适应产生;在杂草进化过程中让精英个体反向学习,提高了算法的勘探能力;另外,在算法进化的不同阶段对杂草实施不同变异,增强个体交流,提高算法的开发能力.通过8个经典的Benchmark函数测试,结果表明该算法提高了杂草算法的求解精度和收敛速度,具有很强的鲁棒性.