改进的细菌觅食优化算法及其在0-1背包问题中的应用

作     者：何妙妙 

作者单位：西南大学 

学位级别：硕士

导师姓名：邓辉文

授予年度：2020年

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 081104[工学-模式识别与智能系统] 08[工学] 070105[理学-运筹学与控制论] 0835[工学-软件工程] 0811[工学-控制科学与工程] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主      题：细菌觅食优化算法 逐维更新 莱维飞行 自适应步长 0-1背包问题 

摘      要：人们常常在生产生活中遇到大量的优化问题,国内外广大学者已经对这些优化问题进行了全面的研究,并将其发展成为了一门不可或缺的学科门类。解决优化问题的传统方法主要包括最速下降算法、线性规划、单纯形法等一系列以梯度为基础的算法,这类算法只有在待优化问题的目标函数是凸集且连续可微可导的情况下计算效率较高。但在实际应用中,面临着许多大规模、非线性、多极值的复杂优化问题,传统的优化算法对这类复杂优化问题的求解精度已经不能满足生产生活需求。群体智能优化算法由于其参数少,效率高,操作简单,对待优化问题本身的数学性质要求较少等优点,被广泛应用于求解各类复杂的优化问题。细菌觅食优化算法（Bacterial Foraging Optimization Algorithm,BFO）是一种新发展起来的群体智能优化算法,该算法具有鲁棒性强,易于实现等优点,现在已经在某些领域被成功使用,但应用深入度还尚浅,并且该算法在某些应用过程中存在求解精度不够精确、收敛速度慢等缺点,尤其在求解多峰优化问题时易陷入局部最优,很难得到全局最优值。因此,分析BFO算法的理论、改进BFO算法的机制和发展该算法的应用对于科学研究和现实生产中的各个领域的优化问题求解都具有重大的意义。为此,本文主要从该算法的改进和应用方面做了一些工作。主要研究内容如下:1.提出了一种基于贪心逐维更新评价策略的细菌觅食优化算法细菌觅食优化算法对解采用整体更新评价策略。BFO算法在解决连续型多维优化问题时,因为各维之间彼此干预,采用整体更新评价策略会降低求解精度,影响收敛速度。针对以上问题提出了逐维改进细菌觅食算法（Bacterial Foraging Optimization Algorithm with Dimension by Dimension Improvement,DDIBFO）。实验结果说明,引入逐维更新评价策略后能够有效地提高解的质量。2.步长改进的细菌觅食优化算法在经典的细菌觅食优化算法中,采用固定步长进行细菌位置的更新导致算法的搜寻效率低,容易陷入局部最优。针对这一缺陷,本文把莱维飞行机制引入到BFO算法当中,提出了一种基于莱维飞行的细菌觅食优化算法（LBFO）。莱维飞行机制产生的步长具有很大的随机性,有利于细菌个体在更加广阔的区域进行搜索,提高了算法的全局探索能力。实验结果表明,LBFO算法性能有了很大提升。由于莱维飞行产生的步长过于随机,缺乏自适应性,使得算法后期局部寻优能力弱,收敛速度低。为此,本文再次对步长进行改进,在传统BFO算法的基础上采用指数型自适应步长策略,提出了一种自适应步长的细菌觅食优化算法（Self-adaptive Step Bacterial Foraging Optimization Algorithm,SSBFO）。通过使步长随迭代次数的增加呈指数衰减,保持了算法全局探索与局部探索之间的平衡性。实验结果表明,SSBFO算法具有较强的竞争力。为了检验SSBFO算法的实用性,本文还把SSBFO算法应用到AJM工艺中脆性材料和延性材料的参数估计上面,取得了很好的成效,进一步证明了SSBFO算法的有效性。3.改进的细菌觅食优化算法在0-1背包问题中的应用0-1背包问题是生产管理、投资选择及材料分割等领域的热点问题之一,也是典型的NP难问题。大多数启发式算法都是针对连续型问题的,细菌觅食优化算法也不例外,而0-1背包问题是典型的离散型问题。为了让BFO算法适配该问题,首先对物品进行编码,其次在本文所提SSBFO算法的基础上引入贪心逐维更新评价思想,提出了一种求解0-1背包问题的细菌觅食优化算法。在物品个数为20、50、100、200的0-1背包问题上进行了仿真实验,实验说明,改进的细菌觅食优化算法寻优结果良好。