求解带有利用率惩罚背包问题的参数自适应差分进化算法  

作　　者：刘静宜[1] 韩海燕[1] 

机构地区：[1]东北大学数学系,辽宁沈阳110819

出　　处：《科技视界》2016年第16期88-89,共2页Science & Technology Vision

基　　金：国家自然科学基金青年基金项目(71202151)

摘　　要：本文研究一类新型的背包问题,特征主要体现在目标函数不仅要最大化装载物品的价值,同时还包含关于背包利用率的凸型罚函数。首先分析该问题的线性松弛最优解性质,以揭示整数最优解的结构特征。为了有效求解该问题,设计了一种参数自适应差分进化算法。该算法中提出变异和交叉参数的自适应选择方法,在进化的过程中可以动态评估每组被选参数的性能,并用于指导下一个迭代过程的参数配置,从而避免了基本差分进化算法中参数选择的困难。实验结果显示提出的参数自适应差分进化算法性能显著优于基本差分进化算法,说明新算法在求解惩罚背包及类似问题上的有效性和稳定性。

关 键 词：背包问题 利用率惩罚 参数自适应 差分进化算法 

分 类 号：O224[理学—运筹学与控制论]