图是用于刻画自然界或社会中事物关系的一种复杂数据结构。随着信息技术的飞速发展,图已经逐步覆盖了我们日常生活的各个方面,特别是在交通、社交等领域中,图模型的应用更是无处不在,极大程度地推动了图着色、车辆调度、传播源定位等理论研究的发展。对图着色、车辆调度、传播源定位等图问题的深入研究,既可以优化资源分配,也可以帮助改进物流配送机制、降低配送成本,还可以帮助政府快速掌握网络舆论源头、维持社会稳定。所以,如何高效地求解图着色、车辆调度、传播源定位等图问题已成为了当前学者们研究的热点。经过多年研究,学者们提出了一系列图问题的求解算法,可以分为精确算法和智能算法两大类。精确算法通常指能够求得全局最优解的算法,比如自然线性规划法、动态规划法、回溯法等。由于大多数图问题都属于NP-Hard难题,应用精确算法进行求解,算法计算成本会随着问题规模增加呈指数增长。显然,在社会数据井喷式增长,尤其是当前大数据时代的背景下,精确算法已无法满足图问题的求解需要。所以,学者们逐步将研究重心转移到了智能算法,提出了蚁群算法、遗传算法、粒子群算法、禁忌搜索算法等一系列算法用于图问题求解,且一直致力于追求更加高效的求解算法。近年来,一种名为多头绒泡菌的黏菌在觅食过程中展现出自组织、自优化等智能行为,受到理论界广泛关注,学者们先后建立了气泡模型、Agent模型、梯度模型、俄勒冈模型、正反馈模型等一系列仿生模型。其中,由于具有“重点管道重点培养”、快速收敛到最短路径等特点,多头绒泡菌网络正反馈模型应用最为广泛。基于上述分析,本文选取图着色、车辆调度和传播源定位三个经典图问题为研究对象,探索利用多头绒泡菌仿生模型进行优化求解。具体来说,主要包括以下3个方面工作:(1)基于多头绒泡菌仿生模型的图着色问题求解:根据图着色问题(Graph Coloring Problem,GCP)特点,利用多头绒泡菌正反馈仿生模型对蚁群算法(Ant Colony Optimization,ACO)信息素浓度更新机制进行改进,提出了求解GCP问题的多头绒泡菌蚁群算法(Physarum-ACO,PM-ACO),并采用国际标准算例进行仿真实验。结果表明,PM-ACO算法在控制时间开销的前提下,求得最好着色数、平均着色数或平均收敛代数等优于传统ACO算法和其他智能算法,说明利用多头绒泡菌正反馈仿生模型对ACO算法的改进是合理的,为GCP问题求解提供了一种新的研究思路。(2)基于多头绒泡菌仿生模型的车辆调度问题求解:根据车辆调度问题(Vehicle Routing Problem,VRP)特点,利用多头绒泡菌正反馈仿生模型的传导性矩阵代替混合遗传算法(Hybrid Genetic Algorithm,HGA)的距离矩阵,提出了求解VRP问题的多头绒泡菌遗传算法(Physarum-HGA,PM-HGA),并基于企业配送实例和国际标准算例进行仿真实验。结果表明,与其他智能算法相比,PM-HGA算法全局寻优能力更强、收敛速度更快、稳定性更好,能够较好地规划配送方案,有效缩短企业配送距离。(3)基于多头绒泡菌仿生模型的传播源定位:针对多头绒泡菌原生质网络学习传播网络理论时延分布特征的方法(Physarum_esti),在传播源定位时缺乏严谨科学依据、算法性能有待进一步提升的问题,提出了优化改进的方法(Physarum_cov)。该方法主要利用多头绒泡菌正反馈仿生模型计算理论传播时延,进而求出有效传播距离,然后通过相关系数公式求取有效传播距离和观测性时延的相关系数,选取相关性最大的候选源点作为预测的实际传播源。对传播源经典网络的仿真实验表明,Physarum_cov方法在不同观察点比例下的错误距离均优于Physarum_esti等方法,对于传播源定位有良好的预测能力,且稳定性较好。综上所述,本文主要利用多头绒泡菌仿生模型对图着色、车辆调度和传播源定位等图问题进行求解。大量仿真实验表明,基于多头绒泡菌仿生模型的求解方案,能够更加有效解决图问题。