基于烟花算法的多维背包问题的求解

发布时间：2020-12-05 21:14

　　多维背包问题（Multidimensional knapsack problem,MKP）作为0-1背包问题的拓展,是一种典型的NP难问题,在日常生活中有着大量的应用场景,比如货物装载,资源分配,投资决策等等。因此,无论是理论上,还是实际应用中,对多维背包问题进行求解都具有重要意义。随着问题规模的逐渐增大,传统的精确求解算法和启发式算法逐渐显得力不从心,而群智能算法的发展,为这类问题的求解开辟了新的道路。群智能算法是通过模拟生物种群之间的信息交流以达到求解目的的一类新型算法。烟花算法是通过模拟夜空中烟花爆炸的过程而实现的。作为群智能算法的一种,烟花算法具有参数较少、执行过程简单、实现容易,鲁棒性强等特点,在解决大型复杂优化问题上具有一定优势,目前已经得到了学术界的广泛关注。本文介绍了用于求解多维背包问题的各类精确求解算法,启发式算法和群智能算法,深入分析了多维背包问题及烟花算法的特点,针对多维背包问题中,物品选择策略表现为二进制字符串的特点,以及烟花算法前期搜索速度快,后期收敛速度慢的优劣性,引入了二进制烟花算法和精英反向学习机制,设计了二进制精英反向学习烟花算法（Binary Eli... 

【文章来源】：吉林大学吉林省 211工程院校 985工程院校 教育部直属院校

【文章页数】：60 页

【学位级别】：硕士

【部分图文】：

遗传算法流程图

第2章背包问题及优化算法相关理论基础16图2.2烟花算法流程图2.4.2烟花算法实现过程1.爆炸算子烟花算法在运行过程中通过爆炸算子操作来生成下一代火花，爆炸算子通常包括爆炸强度，爆炸幅度，位移操作三个部分。爆炸算子是烟花算法中的核心操作，极其重要。

第3章二进制精英反向学习烟花算法25)))(()((1maxmaxmiiiixffxffmceilA··························(3-7)其中，ceil为向上取整函数；cN为一个和亲代烟花数量相关的系数，用于控制产生火花的数量；m为二进制维数；maxf为计算过程中已知的最优适应度值，minf为计算过程中已知的最差适应度值；610，保证分母不为0。烟花ix爆炸后在iA半径内产生iN个火花，其中第p个火花的生成规则为),,(0EiipirSxx····································(3-8)其中，},,2,1{0mS为全部m个二进制编码构成的集合；Eir为爆炸步长，二进制转换算子),,(0EiixrS表示以元素ix为基础字符串，从转换集0S中随机选出Eir个字符进行0-1转置。爆炸步长采用随机生成方式获得，随机数产生范围为0到爆炸半径。ceilrrandA)(ipi·································(3-9)爆炸算子运行过程示例如下：设选定烟花0,0,0,0,1,1,1,11x，8,7,6,5,4,3,2,10S，1pir，产生的火花个体数量21N，则爆炸算子结果如下图图3.1爆炸算子示意图最终产生的火花个体将会在全部8种可能的情况中随机选择2种。2.变异算子


本文编号：2900104