交通网络旅行商路径优化的遗传禁忌搜索算法

旅行商路径优化问题是经典的网络分析问题之一。由于旅行商问题具有NP Hard特性,主要通过智能优化方法或启发式算法来获得近似最优解。然而,单一智能优化方法存在运算量过大、参数选择苛刻,对初值依赖性强等缺陷,很难快速实现全局优化。结合多种优化机制和邻域搜索结构设计混合启发式算法可在一定程度上解决这一问题。本文结合遗传算法的全局寻优能力和禁忌搜索的记忆功能,设计实现了一种基于分散集中策略的禁忌遗传算法,即采用遗传变异算子作为分散策略构造邻域,开辟新的搜索空间,有效提升获得全局最优解的概率;将禁忌搜索作为集中策略进行局部寻优,避免迂回探测,充分体现禁忌搜索较强的“爬山”能力,并通过实际交通网络和不同规模的节点集合,从求解精度、稳定性和效率三个方面对算法进行了评价。结果表明,本文提出的交通网络旅行商路径优化的禁忌遗传算法平均求解精度比禁忌搜索算法提高了9%,略优于ArcGIS;当与ArcGIS求解的TSP路径长度差异在1%以内时,禁忌搜索算法已经难以获得对应精度的TSP路径,而禁忌遗传算法效率比遗传算法提高了50%。且禁忌遗传算法具有很好的并行化潜力。     

设施服务分区问题的求解算法框架设计

设施服务分区问题(facility service districting problem,FSDP)是指在一个地理区域内,根据服务设施位置和服务能力为其划分服务区,满足供需平衡、形状紧凑和空间连续等要求。空间连续约束使FSDP能更好地满足学区划分、医疗区划分等问题的政策需求,但同时增加了它的求解难度。构造了一个FSDP混合整型线性规划模型,并设计了一个算法框架。框架包括问题定义、初始解、搜索算子和策略等基本模块,支持精确算法、元启发算法和混合算法设计。基于算法框架,实现了数学模型、模拟退火算法、迭代局部搜索算法和数学启发混合算法,并使用4个中大规模案例进行算法测试。实验结果表明,算法框架能够很好地处理空间连续约束的FSDP,支持多种算法快速实现,且求解质量接近案例目标值下界。     

一种多出口室内应急疏散路径规划算法北大核心CSCD

针对多源多汇多路径问题若分别以多个出口为源点,通过多次直接调用Dijkstra算法求解,节点会被多次重复扩展,导致算法搜索效率过低的问题,该文结合Dijkstra算法的执行原理和特点,提出了一种解决多出口室内应急疏散路径规划的新算法。首先通过引入一个连接所有出口节点的虚拟节点作为源点来改变原始网络结构,将多源多汇多路径规划问题转化为单源多汇多路径规划问题;然后以虚拟节点为源点,直接调用Dijkstra算法来搜索源点到各个汇点的最优路径。该算法有效避免了多次调用Dijkstra算法带来的重复搜索节点问题,提高路径搜索效率。实验结果表明,该算法运行时间随着路网总节点数的增加而增加,与出口数关系不大;当出口数越多时,该算法较之现有算法效率提升越明显,具有较高的实用性。     

基于ICSO的DGPS整周模糊度的求解方法

针对差分全球定位系统(DGPS)模糊度解算过程中效率低,搜索慢的问题,对鸡群优化算法(CSO)进行适应性改进,并将改进后的鸡群优化算法(ICSO)应用到整周模糊度的快速解算中,利用卡尔曼滤波求出双差模糊度的浮点解和协方差矩阵,采用Lenstra-Lenstra-Lovasz (LLL)降相关算法对模糊度的浮点解和方差协方差矩阵进行降相关处理,以降低模糊度各分量之间的相关性,在基线长度固定的情况下,利用ICSO搜索整周模糊度的最优解. 采用经典算例进行仿真,仿真结果表明,与已有文献相比在整周模糊度的解算过程中改进的鸡群优化算法能有效提高搜索速度和求解成功率.      

道路网匹配的蚁群算法求解模型

利用蚁群算法的群体优势,寻找全局最优的道路网同名实体匹配方案。首先从几何矢量误差和结构特征两方面建立了匹配问题的数学约束模型;然后阐述了蚁群算法求解匹配问题的基本原理,设计了问题求解模型,并引入自适应和局部搜索策略提高了算法效率;最后给出了求解的关键步骤。实验证明,利用蚁群算法进行道路网匹配是有效、可行的,为求解匹配问题提供了新思路。     

遗传模拟退火算法优化BP神经网络的GPS高程拟合

针对传统BP神经网络收敛速度慢、易陷入局部最优和遗传算法优化BP神经网络(GA-BP)算法过早收敛的问题,提出了遗传模拟退火算法优化BP神经网络(GSA-BP)算法. 在遗传算法(GA)的种群更新中加入模拟退火算法(SA),保留种群的多样性. 用GSA-BP算法对某地区进行高程异常拟合,并与BP算法和GA-BP算法结果进行比较. 结果显示:GSA-BP算法精度可分别提高约51%、25%,速度提高约77%、39%,且能基本满足四等水准测量精度要求. 该方法在GPS高程拟合中具有可行性.      

多父体杂交演化算法求解约束优化问题

提出了一种求解约束函数优化问题的新算法。设计了3种新的多父体杂交算子。这3种算子都使用了统计信息来决定搜索方向，使算法具有较高的收敛速度，同时又具有互补的特性，使得种群在演化过程中能保持较好的多样性，不容易陷入局部最优。对常见测试函数的数值实验证实了新方法的有效性、通用性和稳健性，其性能优于现有的一些演化算法。     

蚁群智能及其在大区域基础设施选址中的应用

提出了基于蚁群智能的空间选址模型,通过蚁群智能和GIS的结合来解决复杂的空间优化配置问题.这种启发式的智能搜索方法大大提高了空间搜索能力.为符合选址问题的求解,从信息素更新方式和禁忌表调整策略两方面对基本蚁群算法进行改进.同时,为了使得模型能实用于大区域的基础设施选址,提出了"分步逼近"的策略,取得了较好的效果.将所提出的模型应用于广州市公共没施的空间优化选址.实验结果表明,该方法比简单搜索方法和遗传算法更有优势.     

FAN模型的双种群差分进化光谱解混算法

双线性混合模型是近年来非线性光谱解混的研究重点之一,其克服了线性混合模型无法描述地物多重散射作用的缺陷,能够更精确地还原真实的地物光谱混合过程。然而,限于模型的复杂性,目前在缺乏准确的端元先验知识的条件下进行双线性光谱解混仍是一项具有挑战性的任务。差分进化算法(DE)是一种具有良好全局搜索能力的群智能优化算法,其优化求解过程无需进行复杂的数学推导,为双线性光谱解混问题提供了一种有效的解决途径。为此,本文以FAN双线性混合模型为例,提出了一种双种群机制的差分进化算法(记为DEFAN),实现非监督双线性光谱解混。DE-FAN算法通过建立端元与丰度两个种群的交替进化机制寻找最优解,同时在迭代中引入自适应重构策略增强种群多样性,降低算法陷入局部最优解的风险,最终实现端元与丰度的同时估计。通过模拟图像及真实图像的解混实验进行算法检验,证明DE-FAN算法较之传统非线性解混算法具有更高的解混精度及解混效率。     

一种优化高斯过程回归的隧道围岩变形预测方法

为准确掌握隧道围岩变形的发展趋势,实现对隧道施工的准确指导,以及规避高斯过程回归(GPR)采用共轭梯度法求取超参数时存在的缺陷,该文提出利用一种改进果蝇优化算法(MFOA)优化GPR,构建MFOA-GPR预测模型.首先,对标准果蝇优化算法(FOA)的味道浓度函数进行修正,拓展求解的范围;同时引入了一个搜索半径动态调整参数,使得算法在迭代寻优过程中动态调节全局搜索能力和局部开发能力;再将改进的果蝇算法直接应用于GPR的超参数寻优.通过两个实际隧道工程算例进行分析和检验,结果表明,MFOA-GPR方法的预测精度最高,多个精度评价指标均优于GPR、FOA-GPR模型,验证了该方法的有效性.