细菌觅食优化算法在组合优化问题中的研究与应用

摘要

智能优化算法是近年来新兴的优化方法，是人们研究自然界和生物界的原理，模仿其规律设计而成的算法。与线性规划，非线性规划，单纯形法等传统的优化方法相比，算法原理更容易被人们理解，算法设计简洁，更适合编程计算，对目标函数的可导性没有特殊的要求，为那些传统优化方法难以处理的优化问题提供了切实可行的解决方案。
　　 细菌觅食优化算法(BacteriaForagingOptimization，BFO)是2002年提出的智能优化算法，通过模拟细菌在觅食过程中体现出来的智能行为设计而成。由于算法提出的时间不长，相关的应用和理论研究成果不多。目前，国内外学者已将算法应用于求解函数优化，非线性模型辨识，PID参数优化，谐波估计，神经网络参数调节，车间作业调度等问题。然而，BFO求解组合优化问题的性能究竟如何尚不太清楚。因此，本文通过求解两种典型的组合优化问题：多背包问题和QoS组播路由问题，考察算法解决这两类组合优化问题的有效性，并从算法的寻优机制出发进行分析讨论。
　　 本文通过细菌觅食算法的分析，对算法中的趋向行为和驱散行为提出了改进的方案，将改进后的算法应用于求解多背包问题和QoS组播路由问题。在此基础上，通过仿真实验验证了改进算法的有效性；结合具体实验讨论了算法的参数选择并给出经验取值；通过与其他智能优化算法的对比，分析了细菌觅食优化算法解决这两类组合优化问题的优势和劣势。

目录

声明

摘要

1 绪论

1．1 课题背景及意义

1．2 课题的研究现状

1．3 论文主要研究内容

1．4 论文结构

2 基本细菌觅食优化算法

2．1 BFO介绍

2．2 BFO算法模型

2．3 细菌行为描述

2．3．1 趋向行为

2．3．2 复制行为

2．3．3 驱散行为

2．3．4 群聚性

2．4 算法全局收敛性

2．5 小结

3 改进细菌觅食优化算法求多背包问题

3．1 多背包问题及其数学模型(Multiple Knapsack Problem)

3．2 编码

3．3 约束处理

3．4 算法设计

3．4．1 新引入参数

3．4．2 改进算法中的邻域与距离

3．4．3 趋向行为的改进

3．4．4 驱散行为的改进

3．4．5 精英保留策略

3．5 参数讨论

3．5．1 细菌种群数S，趋向行为次数Nc和游动次数Ns

3．5．2 感知范围和步长

3．5．3 密度因子β

3．5．4 其他参数

3．6 仿真试验及分析

3．6．1 小规模物品实验

3．6．2 大规模物品实验

3．6．3 算法一致性测试

3．6．4 实验分析

3．7 小结

4 改进细菌觅食优化算法求解QoS组播路由问题

4．1 QoS组播路由问题

4．2 QoS组播路由问题的数学模型

4．3 编码

4．4 约束处理

4．5 算法设计

4．6 仿真实验及分析

4．6．1 无约束条件下算法性能测试

4．6．2 有约束条件下算法性能测试

4．6．3 实验分析

4．7 小结

5 总结和展望

致谢

参考文献