论文部分内容阅读
近年来,通过模拟自然生态系统,涌现出大量的智能仿生算法求解复杂优化问题,如遗传算法,粒子群算法,蚁群算法,人工免疫算法,萤火虫算法等。这些智能生物系统有着相似的特点:单个个体行为简单而且具有随机性,但由这些个体组成的生物群体可以相互协作完成一系列复杂的任务。这些智能优化算法,应用范围广泛,尤其在工程设计、资源分配、生存计划安排、交通运输等各个领域有着深入的应用。根据最近的研究,一种叫作多头绒泡菌(Physarum polycephalum)的单细胞多核生物体在路径寻优、网络设计等方面展现出非常智能的特性。研究发现,分布于迷宫中的多头绒泡菌,能够在觅食过程中找到入口与出口之间的最短路径:更厉害的是,多头绒泡菌连接食物源构造出来的管道网络在效率、成本和容错性能等方面都堪比真实的东京铁路网。由此,多头绒泡菌的这种智能特性已经越来越受到学术界的重视。目前,关于多头绒泡菌的智能行为,已有众多算法、模型用来分析、模拟其内在优化特性。本文,我们着重围绕多头绒泡菌路径寻优模型(Physarum Solver)来展开工作。在多头绒泡菌路径寻优模型中,首先假定管道内液体的流动满足泊肃叶定律,再利用导通性定量地衡量管道的粗细,继而用演化方程模拟管道导通性与内部流量之间的正反馈机制——导通性越大,则内部流量越大;内部流量越大,导通性也越大;反之则亦然——最后成功地解决了迷宫问题。多头绒泡菌路径寻优模型在具有自适应性(根据流量大小自动调整管道粗细)等优点的同时,也存在以下的缺点:(1)在多头绒泡菌路径寻优模型的内部迭代过程中,解关于压力的基尔霍夫方程组的计算复杂度高,为O(n3);(2)传统的多头绒泡菌路径寻优模型只能处理无向图,而在有向图中无法施展用处;(3)多头绒泡菌路径寻优模型需要网络图的全局结构信息,这一强制性要求限制了它的应用范围:(4)多头绒泡菌路径寻优模型利用基尔霍夫方程组来计算节点的压力值,由此带来了管道之间无法相互独立计算的缺点,也意味着多头绒泡菌路径寻优模型无法进行并行计算处理。为此,我们有必要对现有的多头绒泡菌路径寻优模型进行改进,从而能提出更有效、应用范围更广的算法模型。本文首先分析多头绒泡菌路径寻优模型的内在正反馈优化机制,率先将该算法模型用于具有多源多汇的网络图中,探究其能否解决经典运输问题和推广的运输问题。然后,基于多头绒泡菌的正反馈机制,提出一种全新的能量传播模型,解决一系列实际优化问题,包括运输问题、迷宫问题、最短路径树问题、动态最短路径树问题和最大流问题。本文的主要工作包括以下几个方面:(1)介绍多头绒泡菌路径寻优模型介绍了多头绒泡菌路径迷宫实验,分析并解释其智能行为的核心机制:管道粗细与管道里流量之间的正反馈机制。又详细介绍多头绒泡菌路径寻优模型,最后介绍在有向图下的多头绒泡菌路径寻优模型。(2)提出多头绒泡菌解运输问题算法原始的多头绒泡菌路径寻优模型并未考虑多源多汇情形下是如何优化的。正对此问题,我们尝试将正反馈优化机制应用到具有多源多汇的有向图中,建立多源多汇多头绒泡菌路径寻优模型-最后实验结果表明,该模型可以有效地解决平衡运输问题、非平衡运输问题和推广的运输问题。(3)提出一种基于能量传播的路径选择模型传统的多头绒泡菌路径寻优模型无法依靠局部信息寻找最短路径,且管道间无法并行处理。由流体力学中的泊肃叶定律、热力学中的傅里叶定律和电力学的欧母定律得到启发,我们首先提出一种一般性的能量传播法则,引入的能量粒子能够临时地“存储”在节点上,且具有液体、热量、电流运动的特点。在新构建的模型中,各条边能量流的更新仅仅需要邻接节点的能量信息来独立地计算。最后,引入多头绒泡菌路径寻优模型的正反馈机制,建立了一种基于能量传播的路径选择模型。该模型具有传统多头绒泡菌路径寻优模型不具备的特点-局部性和并行性。(4)将提出的能量传播模型应用于解决一些优化问题最先提出的能量传播模型仅用于解决迷宫问题。这里,我们扩展模型,将其应用到多源多汇、单源单汇等不同情形下,进行优化行为研究,实验结果表明,该模型可以正确地解决运输问题和最短路径树问题。最后,我们将该模型应用到动态无线传感器网络中,发现该模型能够很好地进行通信路径选择,同时数值仿真结果也验证了该模型能够在动态网络中解决最短路径树问题。(5)能量传播模型解最大流问题的初步方案正反馈机制在优化问题上的应用方式还有很多种。在本文中提出了基于能量传播模型解决最大流的初步方案:建立一条长度大于任意一条源汇节点间的可能路径,利用正反馈机制,使得原先沿着虚拟边的流量逐步收敛到原网络中,直至各条边上的流量不在发生变化,从而得到原网络的最大流。