求解背包问题的多位极贪婪遗传算法

赵新超; 吴召军

doi:10.16088/j.issn.1001-6600.2013.04.026

广西师范大学学报（自然科学版） ›› 2013, Vol. 31 ›› Issue (04) : 41 -47. DOI: 10.16088/j.issn.1001-6600.2013.04.026

求解背包问题的多位极贪婪遗传算法

赵新超, 吴召军

作者信息 +

Author information +

文章历史 +

PDF

摘要

交叉和变异运算是遗传算法的核心操作,高效的变异算子不但起到改善遗传算法局部搜索能力和维持多样性的作用,还能基于针对性的修改策略在变异运算过程中实现对子代个体的优化处理,修正当前的搜索路径,进而提高算法的寻优效率。本文首先在更贪心算法的基础上提出了效果更佳的极贪婪变异算法,设计了一种多位贪婪变异算子,对遗传算法染色体(装包方案)的连续或间断的几位等位基因进行极贪婪变异处理。对经典背包算例的仿真结果表明,多位极贪婪变异遗传算法(MBGGA)同文献新近提出的多种算法相比具有快速、高效、稳定的性能表现。