基于改进蝙蝠算法的0-1背包问题求解研究文献综述
2020-05-02 17:59:47
1. 目的及意义
1.1研究目的
为了对燃汽轮机发电系统进行性能优化和状态监测,Tamiru将蝙蝠算法应用于燃汽轮机发电系统模型中。首先使用蝙蝠算法和局部线性模型树算法对模糊系统进行训练,然后利用该系统捕捉燃气轮机发电系统的能量损失分布及其变化情况,与局部线性模型树算法进行训练结果对比,证明蝙蝠算法和局部线性模型树算法结合的有效性。
自BA提出以来,已有不少学者将其应用于优化问题,包括简单函数优化、生产调度、分类类别、模式识别等,相对于PSO、GA以及HS等,BA具有更大潜能。
1.2研究意义
理论上来说,背包问题是经典的组合优化难题,具有较高的理论研究和实际应用价值,在投资决策、预算控制、项目选择、资源分配和货物装载等方面都有着非常重要的应用。快速高效的求解KP问题一直是演化计算领域中的一个研究热点,人们已相继研究了如何利用遗传算法、蚁群算法和微粒群算法和声算法等求解0-1背包问题,取得了许多有益的结果。
1.3国内外研究现状分析
20世纪50年代,美国数学家R.E.Bellman等人在研究多阶段决策过程的优化问题时,提出了著名的最优化原理,把多阶段过程转化为一系列单阶段问题,利用个阶段之间的关系,逐个求解,创立了解决这类过程优化问题的新方法——动态规划。动态规划是基于递归的,通常不是一个解决KP有效的方式,因为空间消耗非常大,和最坏的和最好的计算工作通常是相同的。动态规划算法与分治法类似,其基本思想也是将带求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。与分治法不同的是,适合于用动态规划法求解的问题,经分解得到的子问题往往不是互相独立的。若用分治法解决这类问题,则分解得到的子问题数目太多,以至于最后解决原问题需要耗费指数时间。
然而,不同子问题的数目常常只有多项式量级。在用分治法求解时,有些子问题被重复计算了许多次。如果我们能够保证已解决的子问题的答案,而在需要时找出已求出的答案,这样就可以避免大量的重复计算,从而达到多项式时间算法。
{title}2. 研究的基本内容与方案
{title}2.研究(设计)的基本内容、目标、拟采用的技术方案及措施