论文部分内容阅读
路径寻优算法一直都是学术界的一个重要课题,从迪杰斯特拉算法以及弗洛伊德算法直至如今大量涌现的生物启发式算法,学术界一直致力于希望能够找到一个既准确又快速的算法去解决这类问题。根据最新研究,多头绒泡菌(Physarum polycephalum)这种多核单细胞生物所表现出来的智能行为给了研究者一个不错的启发方向,这种生物体在路径寻优问题方面表现出了非常智能的行为。研究者根据多头绒泡菌的这种特性做了相关的实验,比如迷宫实验和东京铁路网实验等等,这些实验让多头绒泡菌所表现出来的智能觅食行为引发了广泛的关注。众多学者利用这种智能行为构建了相关数学模型和算法,以此来模拟多头绒泡菌的这种智能觅食行为。在本篇论文当中,我们以多头绒泡菌寻优算法为基础来开展我们的研究工作。在多头绒泡菌的数学模型当中,由于多头绒泡菌在迷宫中形成管道主要是依靠流体在管道中不断的流动,最终慢慢的形成了一条最短路径,所以,我们可以利用泊肃叶定律来模拟管道中流体的流动。在多头绒泡菌正反馈仿生模型(Positive feedback mechanism model,PMM模型)当中,整个多头绒泡菌的扩张规律服从正反馈机制,即当管道中的流量变大的时候,管道的直径也会随之变大,而当管道中流量变小的时候,管道的直径也会随之变小。通过这种正反馈机制,在扩张的最终阶段,较长的路径上的流量会越来越少,因此管道也会逐渐萎缩,直至消失,最后只留下一条最短路径。依据多头绒泡菌觅食行为展现出的路径寻优能力而抽象出的相关模型,能够求解网络最优路径以及一些NP-hard问题,但现有模型仍存在一些缺点,比如:(1)在多头绒泡菌路径寻优算法当中,算法需要不断的进行迭代,而且每次的迭代都需要求解大量的线性方程和矩阵变换运算,以此来获得每次迭代过程中节点压力值的变化,所以该算法有着较高的计算复杂度;(2)传统的多头绒泡菌路径寻优算法无法有效的求解带约束的路径规划问题;(3)由于多头绒泡菌算法在运行过程中,需要在每次迭代过程中计算每个节点的压力值,而每个节点的压力值都与上一次迭代结果是相关的,所以该算法无法并行计算,这就导致了算法无法通过并行计算有效的缩短运行时间。我们首先对传统的多头绒泡菌算法进行了一定的优化,有效的提高算法的运行效率。与此同时,我们还优化了多头绒泡菌的正反馈机制来求解旅行商问题。本文的工作内容主要包括以下两个方面:(1):优化传统多头绒泡菌算法改进多头绒泡菌算法从而提高该算法的计算效率,为此本文提出了两种优化方法:快速删除冗余节点和冗余边、合并冗余节点,通过这两种优化方法,能够大幅降低传统多头绒泡菌算法的计算时间,同时也能够减少算法的迭代次数。并且,我们采用了真实以及随机生成的网络图来进行试验,并将试验结果与传统多头绒泡菌算法进行对比,以此来验证所提出来的优化方法的有效性。(2):基于多头绒泡菌正反馈机制求解旅行商问题旅行商问题是一个经典的NP-hard问题,为了求解该问题,基于多头绒泡菌PMM仿生模型提出了新的优化方法。由于传统的多头绒泡菌算法无法直接求解这些带约束条件的路径规划问题,因此找出了一个合适的约束方法加入到传统多头绒泡菌算法当中,优化多头绒泡菌算法在收敛的过程中的选择机制,使算法能够有效的求解旅行商问题。同时,在多个随机数据集以及经典数据集上验证该优化方案的效果。