萤火虫算法改进及在背包问题求解中的应用

发布时间：2021-01-08 03:31

　　生产生活中的一些实际问题可建模成背包问题进行求解,比如决策投资、资源分配、预算控制等。其中0-1背包问题是最基础的一类背包问题,许多的背包问题都可以转化为0-1背包问题进行求解。求解0-1背包问题的关键是在满足约束条件的情况下使得最终装入背包的物品价值总和最大。背包问题是一类离散化问题,利用群智能算法进行求解时,第一个需要解决的问题即是选择编码方式将算法离散化。群智能算法计算时会产生大量不可行解,如果对不可行解直接舍弃的话,会破坏种群多样性,所以此时需要修复算法将不可行解可行化,保证种群多样性。本文提出两种改进算法对0-1背包问题进行求解。第一种是自适应萤火虫算法。对萤火虫的位置赋予自适应权重,在算法前期减小权重弱化萤火虫自身位置,增加全局搜索能力,算法后期增加权重,为了使算法具有更强的局部搜索能力。根据权重可以使算法在快速有效的接近理论最优值,最后对每一代更新后个体根据变异概率进行变异操作。第二种是基于模拟退火的改进萤火虫算法。利用萤火虫算法对个体进行位置更新,模拟退火操作对更新后个体取舍,在一定程度上保证种群多样性。根据种群的拥挤程度设置变异概率,当种群较拥挤时,增加变异概率,增强... 

【文章来源】：西华师范大学四川省

【文章页数】：49 页

【学位级别】：硕士

【部分图文】：

FA求解0-1背包问题的算法流程图

第3章萤火虫算法求解0-1背包问题12200247295284.3360-1KP250100200FA10249001018955.90209031024965.43852999947.700-1KP350100200FA3103271229042795.80502731288328090275629162833.100-1KP450100200FA5183327838353524.7080339738693617.40319139533669.900-1KP550100200FA26559193482136120170.10100197152197020445.20198852145120553.60通过表3-2知FA在求解规模较小的0-1背包问题可以在较小迭代次数下寻到最优值，当物品规模超过20个，即使增加迭代次数至200代也不能寻得理论最优值，且随着物品个数的增多，算法对于问题的寻优结果越来越不理想，与理论最优值之间的差距越来越大。为了进一步了解萤火虫算法的求解效果，下面综合30次运算结果的迭代平均值作出萤火虫算法求解0-1背包问题的迭代效果图：图3-3FA求解0-1KP1的收敛效果图3-4FA求解0-1KP2的收敛效果Fig.3-3FAConvergenceEffectfor0-1KP1Fig.3-4FAConvergenceEffectfor0-1KP2

第3章萤火虫算法求解0-1背包问题12200247295284.3360-1KP250100200FA10249001018955.90209031024965.43852999947.700-1KP350100200FA3103271229042795.80502731288328090275629162833.100-1KP450100200FA5183327838353524.7080339738693617.40319139533669.900-1KP550100200FA26559193482136120170.10100197152197020445.20198852145120553.60通过表3-2知FA在求解规模较小的0-1背包问题可以在较小迭代次数下寻到最优值，当物品规模超过20个，即使增加迭代次数至200代也不能寻得理论最优值，且随着物品个数的增多，算法对于问题的寻优结果越来越不理想，与理论最优值之间的差距越来越大。为了进一步了解萤火虫算法的求解效果，下面综合30次运算结果的迭代平均值作出萤火虫算法求解0-1背包问题的迭代效果图：图3-3FA求解0-1KP1的收敛效果图3-4FA求解0-1KP2的收敛效果Fig.3-3FAConvergenceEffectfor0-1KP1Fig.3-4FAConvergenceEffectfor0-1KP2


本文编号：2963824