论文部分内容阅读
基于生物系统建立的模型能够为实际复杂问题的解决启发新的思路。一种名为多头绒泡菌的单细胞多核黏菌在近年来逐渐成为研究焦点,原因在于,多头绒泡菌属于低等生物,然而其觅食过程展现了一系列诸如构建高效网络、自组织、决策、有记忆等的智能特性。受这些特性启发,研究者从不同角度、结合不同领域特色建立了多种仿生模型。这些模型在刻画多头绒泡菌智能行为,解决复杂问题等方面均展现一定优势,推动了相关学科发展。尽管如此,仍存在一些不足及潜在应用价值:(1)模型普遍存在演化周期长、计算复杂度高、随问题规模变大所需时间呈指数级增长等缺点;(2)多头绒泡菌以简单演化机制构建高效网络的能力,正是路网规划关注的焦点,将多头绒泡菌仿生模型用于路网规划是一项迫切需求,将对网络重构与新建提供有力指导;(3)蚁群算法在解决旅行商问题时容易出现停滞、搜索效率低和陷入局部最优等缺点,而目前蚁群优化算法只是间接对信息素矩阵更新优化,效率提升有限,Tero等提出的多头绒泡菌数学模型在网络演化过程中展现了一种正反馈机制,该机制与蚁群算法中道路信息素含量与道路被蚂蚁选择概率之间的正反馈机制相似,应用数学模型进行蚁群算法优化,提出一种普适的直接优化信息素矩阵更新的策略,对提高蚁群算法的寻优能力和鲁棒性具有重要意义。综上,本文根据多头绒泡菌仿生模型研究现状,并结合实际问题,主要做了以下3项工作:(1)优化仿生模型CELL。其它仿生模型相比,Gunji等提出的CELL模型首次将多头绒泡菌移动与网络组建相关联,两者关系在网络演化过程中发挥重要作用。因此,本文以CELL模型为例进行多头绒泡菌仿生模型优化研究。经实验发现CELL模型存在气泡受限局部区域移动和单一气泡演化效率低的缺点,本文利用单元格时间标签策略和多气泡并行演化策略对CELL模型进行改进,提出一种新的演化模型IBTM(Improved Bubble Transportation Model)。该模型利用时间标签驱动气泡扩大移动区域,并利用多气泡并行提高网络演化效率。通过利用IBTM模型模拟多头绒泡菌网络演化过程,比较CELL模型与IBTM模型的演化时间,分析气泡数目和食物源数目对演化效率的影响,验证了IBTM模型的准确性、高效性和自组织特性。(2)基于VP-S模型进行路网规划。VP-S模型(Vacant-Particle Model with Shrinkage)由Gunji等于2011年在CELL模型基础上改进所得,较CELL模型,VP-S模型可展现多头绒泡菌在食物源的累积,从而可实现模拟多头绒泡菌连接多食物源构建自适应网络。因此,本文选用VP-S模型进行路网规划。首先,利用实际数据构建模型演化环境,并将演化网络转换为带权规则网络,同时与实际路网统一量纲。然后,从平均路径长度、网络效率和鲁棒性等方面比较模型演化网络与实际路网的特征。尤其是,综合考虑了网络的拓扑鲁棒性和功能鲁棒性。最后,实验结果显示,模型演化网络在所有衡量指标下均优于真实路网。该项工作表明仿生模型能够为实际路网规划提供有力建议。(3)基于数学模型进行蚁群算法优化解决旅行商问题。利用数学模型“重点管道重点培养”的正反馈机制,提出了一种直接优化蚁群算法信息素矩阵更新的策略,该优化策略可优化一类带信息素矩阵更新的蚁群算法。本文以现实世界旅行路线规划问题建模并作数据集,选取传统的元启发式算法(例如,粒子群算法、遗传算法)与优化前后蚁群算法的运算结果与鲁棒性进行比较。实验结果显示,优化算法在寻优能力、运行时间和鲁棒性方面均优于其它元启发式算法。