论文部分内容阅读
优化问题广泛存在于社会生活、工程实践与科学研究中,它的求解具有非常重要的实际意义与科研价值。群智能优化方法是求解复杂优化问题的一类有效技术,是目前现代优化领域中的一个研究热点。作为一种新型的群智能优化方法,细菌觅食优化(Bacterial Foraging Optimization,BFO)目前已经被成功应用于一些领域,但是它的研究还存在两方面的不足:一是算法理论的基础研究比较少,且已有的理论研究都特定于一维目标函数来进行分析;二是已有应用研究大多数都集中在单目标函数优化问题上,对更复杂的优化问题的关注还比较少。针对BFO算法研究中的上述不足,本文从理论研究、函数优化和离散优化三个层面开展了以下五个方面的创新性工作:1.在理论研究方面,将BFO中趋向机制的稳定性研究从一维拓展到了多维。首先推导出描述趋向机制在多维目标函数下逼近最优解的动态系统模型,并通过对其进行理论分析给出了趋向机制收敛的两个必要条件。然后利用李雅普诺夫稳定性定理证明了多维情形下趋向机制动态系统模型的渐进稳定性。最后通过在两个具体函数优化问题上的实验验证了趋向机制收敛的两个必要条件的有效性。2.针对单目标函数优化问题,提出了基于自适应趋向和接合策略的菌群算法。该算法首先将每个细菌个体初始化为解空间内的一个随机实数向量,并依据目标函数值的大小对个体解的优劣进行评价;然后利用自适应趋向、接合、繁殖和迁徙四个生物机制完成个体解的优化过程。其中,自适应趋向机制中的非均匀自适应步长策略使细菌个体能够根据进化代数和最优个体的信息自适应调整移动步长,有效地弥补了常规BFO中固定步长导致的局部搜索和全局搜索失衡的缺陷。自适应趋向机制中的基于标准基向量的移动方向策略不但省去了BFO中生成单位向量作为移动方向的计算量,而且能够有效地避免个体解更新时不同维之间的相互干扰现象。接合机制作为一个新模拟的生物机制,实现了每个细菌个体与其它细菌个体充分分享信息的功能,克服了BFO中信息交流不足的缺陷。最后,与多个不同群智能优化算法在标准测试函数和现实问题上的实验比较证实了该算法在求解精度和收敛速度两方面都有显著的优势。3.针对多目标函数优化问题,提出了基于精英解存储机制的多目标函数菌群算法。该算法首先将每个细菌个体初始化为解空间内的一个随机实数向量,并依据帕累托占优的概念对细菌个体的优劣进行评价。然后设置内部和外部两种菌群,内部菌群通过执行自适应趋向、接合、繁殖和迁徙四个生物机制完成个体解的优化过程,而外部菌群用于存储内部菌群在优化过程中发现的精英解(非支配解),并采用基于拥挤距离的删减策略剔除多余个体以保持精英解的多样性。内部种群每完成一次趋向机制,外部菌群执行一次更新过程。最后,与经典算法在标准测试函数上的实验比较证实了该算法得到的非支配解集能够较好地逼近理想非支配解集,且解的分布比较均匀。4.针对贝叶斯网络结构学习问题,提出了基于细菌觅食机理的贝叶斯网络结构学习算法。该算法首先将每个细菌个体初始化为一个拥有较少边的贝叶斯网络,并依据K2评分度量对细菌个体的优劣进行评价;然后利用趋向、繁殖和迁徙三个生物机制不断搜索K2评分高的贝叶斯网络结构以完成个体解的优化过程。最后,与多个不同类别的学习算法在多个标准数据集上的实验比较证实了该算法得到的贝叶斯网络结构不但K2评分比较高,而且与基准网络结构的差异比较小。5.针对蛋白质相互作用网络功能模块检测问题,提出了基于细菌觅食机理的功能模块检测算法。该算法首先基于随机游走行为将每个细菌个体初始化为一个功能模块划分,并依据模块度量对细菌个体的优劣进行评价;其次利用趋向、接合、繁殖和迁徙四个生物机制不断搜索模块度高的功能模块划分以完成个体解的优化过程;然后使用两个后处理操作对菌群优化过程中得到的功能模块集合做进一步的精细化处理。最后,与多个不同类别的检测算法在公共数据集上的实验比较证实了该算法能够更加有效地发现有生物学意义的功能模块。本文开展的上述工作,一方面完善了BFO算法的基础理论体系,为其在不同优化问题上的应用奠定了更加坚实的理论基础和依据;另一方面拓宽了BFO算法的应用领域,并为一些复杂优化问题的求解提供了新方法。因此本文的研究工作不仅具有理论意义,还同时具有应用价值。