所有算法均利用Microsoft Visual studio编程实现, 在Intel(R) Core(TM) i5-4210M CPU @ 2.60GHz,4.00GB内存物理地址扩展, Microsoft Windows 8.1系统电脑上运行.
文献[9]中算例的产生方法如下: 假设任意物品的重量wj和价值pj独立均匀分布在区间[1, 100]内,背包容量W=σ∑wj。按照N=100, 200, 500和σ=0.3, 0.5, 0.7的组合,生成9组算例。求解的参数设置保持不变的条件下, 针对每组算例,分别使用标准差分进化算法和参数自适应差分进化算法独立运行50次,得到的优化结果如表1所示。
由表1可见,对于所有算例,参数自适应差分进化算法都能获得更好的最好解、均值和最差解,对于大部分算例,参数自适应差分进化算法能获得更好的标准差。这说明了参数自适应差分进化算法具有更好的有效性和稳定性,显示出良好的优化潜力。
5 结论
针对带有背包利用率的凸型罚函数的新型背包问题,建立了数学模型,分析了线性松弛最优解性质和揭示了整数最优解结构,并提出了一个求解该问题的参数自适应差分进化算法。该算法中提出变异和交叉参数的自适应选择方法,在进化的过程中可以动态评估每组被选参数的性能,并用于指导下一个迭代过程的参数配置,从而避免了基本差分进化算法中参数选择的困难。通过对不同规模算例的计算实验,表明所提出的改进差分进化算法在求解这类新型背包问题上具有良好的优化潜力和稳定性,将来可以扩展到求解其他类型的背包问题。 2/2 首页 上一页 1 2 |