求解0-1背包问题的牵制平衡算法
罗亚波
滕红玺
武汉理工大学 机电工程学院,湖北 武汉 430070
摘要：为扩充对于经典NP-hard问题中的0-1背包问题的求解方法,模拟生态系统中各物种间相互依存、牵制,最终达到动态平衡的自然机制,提出一种新型仿生算法:牵制平衡算法.算法以种群规模描述设计变量,以牵制关系为优化驱动力,以系统达到稳态为优化目标,设计了自成长函数、牵制函数、成长函数用以描述设计变量的变化规律,促进解的寻优进程.将牵制平衡算法对于10个不同规模0-1背包问题的求解结果与近年来文献数据进行对比,结果显示算法在8个不同规模的问题中能获得当前已知最优解,验证了牵制平衡算法的收敛性与求解性能,表明算法对于0-1背包问题的求解具有有效性和竞争力.
关键词：0-1背包问题NP-hard问题仿生算法元启发式算法生态平衡机制
分类号：TP18(自动化基础理论)
资助基金：国家自然科学基金(51875430)
论文发表日期：2023-06-28
在线出版日期：2025-08-15（本平台首次上网日期，不代表文献的发表时间）
页数：8( 116-123 )
英文信息