一种基于改进蚁群算法与GIS的多约束配送中心选址方法

针对单一指派约束和容量约束的设施选址问题（Single Source Capacitated Facility Location Problem, SSCFLP）,建立了一种基于改进蚁群算法与GIS的配送中心选址方法。构建了以总成本费用最小为目标的配送中心选址模型;提出了适合求解SSCFLP问题的改进双层蚁群算法,将求解过程划分为彼此关联的设施选择层和需求指派层2层蚁群,采用改进的全局信息素更新策略加强双层蚁群交流,并对迭代最优解的指派关系进行局部优化;将方法应用于汽车配送中心的选址,利用GIS工具构建选址空间。实验结果表明,该选址方法能找到质量较好的选址及指派结果,对于求解同类问题具有较强的借鉴意义。     

一种面向栅格的空间-属性双重约束聚类方法

针对栅格数据,传统聚类方法大都基于专题属性进行聚类,分裂了栅格对象的空间特性与专题属性,而兼顾空间与专题属性的现有空间聚类方法又存在算法复杂、参数设置多等问题,因此本文提出了一种面向栅格的空间-属性双重约束聚类算法（A Raster-oriented Clustering Method with Space-Attribute Constraints, RoCMSAC）。RoCMSAC利用栅格数据空间邻域和空间连通特性,重新定义栅格簇的相似性度量准则,通过属性均质簇生成,空间相邻栅格簇合并和空间邻近栅格簇合并3个步骤对栅格数据进行空间-属性双重约束聚类。利用太平洋海域海表温度栅格数据对算法的可行性以及有效性进行验证,并与现有算法进行对比分析。通过实例验证与对比发现：① RoCMSAC方法能够保证栅格簇空间域的邻近性和属性域的均质性;② RoCMSAC方法可发现复杂形状的栅格簇,且算法时间复杂度低,需输入参数较少。     

一种改进蚁群算法及其应用

蚁群算法是近年来出现的一种新的仿生优化算法.针对基本蚁群算法在求解过程中容易出现收敛时间过长以及易陷入局部最优解的不足,对算法中的状态转移、搜索方式以及信息素更新进行改进,提出了一种新的改进蚁群算法.一类典型旅行商问题的仿真实验表明改进的蚁群算法具有收敛速度快、全局搜索能力强和计算时间短的特点,证明了方法的可行性和有效性.     

基于遗传蚁群算法的云资源调度问题研究

讨论利用蚁群算法解决云计算资源的调度问题。蚁群算法利用正反馈机制加快了收敛速度,但同时具有易早熟,易陷入局部最优解等不足。针对此问题,提出用遗传算法优化蚁群优化算法,同时引入最大最小蚁群系统改进基本蚁群算法,从而形成新的遗传蚁群算法。实验结果表明,新算法应用于云计算资源调度中,能有效地缩短调度所用的平均时间,提高调度效率。     

栅格数据矢量化及其相关问题的解决方法

矢量结构和栅格结构是GIS的两种主要数据结构形式,而栅格数据不能满足GIS中进行空间分析的要求,因此栅格数据的矢量化在GIS中具有十分重要的意义。本文在总结前人算法的基础上,以拓扑关系的原理为指导,提出了改进的栅格结构数据矢量化方法,即根据4个相邻栅格的异同关系来判定交汇点是坐标点还是结点,并且在提取结点和坐标点过程中,同时提取水平和垂直的所有线段信息,以便快速、有效地实现栅格数据的矢量化。此外,还采用动态打断和粗网格等方法,解决了在栅格数据矢量化过程中,经常出现的诸如多边形自交、孤岛等问题。作者用VisualC⁺⁺语言实现了本文的算法,与ENVI矢量化结果相比,该方法的矢量化结果具有简单方便、编辑工作量小、实用性强等显著优点。因此,该改进方法更有利于遥感图像的信息提取及其与GIS技术的集成。     

基于非匀质空间下Voronoi图的城市影响范围研究

为解决城市影响范围研究中忽略非匀质空间的问题,本文以光栅扫描算法为基础,提出了一种非匀质空间下面状加权Voronoi图生成算法。首先,对面状目标和栅格空间赋予不同的权重;其次,采用3×3邻域模板进行十字交叉4次光栅扫描,在距离变换中按栅格像元传递权重对距离进行分解,完成非匀质空间下面状加权Voronoi图的生成;最后,以山西省11个地级市为研究区,进行了验证。结果表明,改进后的算法实现了非匀质空间面状加权Voronoi图的生成;相比点状加权V图,城市之间权重差异较大,距离较近时,面状加权V图更适合城市影响范围划分。     

免疫遗传算法及其在VRP中的应用

物流配送车辆路径问题（VRP）是一类典型的NP问题。在基本遗传算法的基础上,根据生物的免疫系统原理,提出一种改进的算法——免疫遗传算法。在算法中构造一种基于抗体浓度的群体多样性保持策略,引入免疫算子和免疫记忆库。将该算法应用于求解VRP问题,实验结果表明算法可以实现解的多样性,避免出现早熟收敛,可以有效防止进化过程中最优解退化的可能,是求解车辆路径问题的一种有效的算法。     

顾及地形的滇中引水工程最低成本线路研究

以滇中引水工程线路规划为例,以资源三号测绘卫星ZY-3 DSM为数据源,以均值变点分析法为理论依据,借助Python语言编程实现研究区地势起伏度最佳统计单元的确定,并运用GIS技术生成地势起伏度和坡度图。再运用专家打分评价方法,确定地势起伏度和坡度的权重,采用基于栅格的成本加权分析法,构建滇中引水工程地形成本栅格。在此基础上,将引水工程线路规划问题转化为GIS最低成本路径求解问题,以栅格数据Dijkstra算法为基础,求解出滇中引水工程最低成本线路。从地形的角度,研究了复杂地形状况下滇中引水工程智能线路规划的方法,可为引水工程提供一定的参考和借鉴。     

栅格数据地学可视化分析环境的构建分析

以遥感数据、数字高程数据等为代表的栅格数据获取技术的进步,以及栅格数据本身适合地学模拟的特点,使得栅格数据应用越来越广泛.当前以定量计算为主的方法难以有效支撑栅格数据分析任务,将可视化引入,充分利用人机协同优势,形成栅格数据地学可视化分析环境是一个较好的解决途径.但是,栅格数据大数据量的特征会引起属性空间可视化时的遮挡...     

聚落遗址迁移最优路径模拟

古遗址作为古人生产、生活的重要场所和文化遗存,客观反映了在长期的人地关系相互作用下的地理空间特征及其分异情况,但是由于史前人类生产力水平低下,在聚落迁移或对周边资源探索中更多地考虑自然环境因素,这种行为符合“最优路径”的思想。本文旨在基于考古调查和基础地理数据,模拟构建古人在聚落选择上的迁移最优路径,探讨古人行为模式,重点研究成本数据确定和成本栅格数据的集成方法及最优路径应用分析。以长江中游新石器晚期的大溪文化、屈家岭文化、石家河文化为连续研究文化期,对其中1200多处遗址的基础地理数据和考古数据进行分析;选取高程、坡度/坡向、地形起伏度、距水系距离等自变量,基于二分类逻辑回归模型,构建研究区史前聚落遗址分布模型。为分析聚落群的时空演变,首先基于期望最大化方法（EM算法）和Voronoi方法对聚落遗址数据进行聚类划分聚落群的中心点的确定,选取分布模型中的自然因子系数作为权重计算成本栅格数据,进而模拟聚落遗址按时序迁移的最优路径。研究结果符合古人类在迁移过程中多考虑以最低成本从山谷、丘陵中穿行的基本规律。并对比已探明的聚落遗址信息,验证模拟的最优路径具有一定的合理性。本文提出的方法,避免了人为选择权重生成成本栅格所带来的仅依靠主观因素的局限,提高了考古研究的科学性,其研究方法和结论对于探究史前聚落遗址时空演变规律和人地关系有一定的参考价值。     

SA*：一种多线程路径规划算法

路径规划问题是路网交通应用中的一个基础问题。A*算法是一个求解点到点最短路径问题的高效算法。但随着路网数据规模的增长,A*难以保证求解的实时性。利用并行计算进行加速是常用的算法性能提高手段,然而A*算法是由一系列前后依赖的迭代步骤组成,因此难以进行直接的并行化。本文提出一种分段化搜索的改进A*算法（SA*）。该算法在搜索路径前先选择若干可能在最短路径上的结点作为导航点,然后多线程并行地分别求出导航点之间的最短路径,并拼接这些路径作为原问题的一个近似解。分段搜索本身可以减少路径规划的搜索空间,借助多线程并行则可以进一步提高求解速度。实验结果表明,在真实路网数据上,利用16核的机器,SA*的性能可以达到A*算法的10-30倍。     

基于改进蚁群算法的无人机低空公共航路构建方法

日益增加的无人机数量和飞手自由规划航线给航空安全带来极大隐患。构建一个安全、高效的航空飞行环境,可以为无人机活动设立隔离空域,并在隔离空域内规划无人机低空公共航路,以提高低空空域利用率,为无人机交通管理提供决策依据。本研究充分考虑无人机近地表飞行及其即时通讯等特点,以天津市为例,基于地理信息技术构建以多源地理空间数据为基础的无人机低空飞行环境,包括低空蜂窝网络环境、大气环境和政策空域环境等,并改进传统蚁群算法以搜索无人机最优路径,得到该区无人机低空公共航路网。研究结果表明,改进的蚁群算法大大提高了路径搜索效率,满足无人机航路规划的高时效性、动态更新等要求;并且天津市航路长度符合市场上现有的无人机最远航程要求,基本满足现有的无人机运输要求。本研究描述的无人机低空公共航路研究的核心算法和关键技术,可以为无人机管控系统提供核心技术支撑。     

基于蚁群算法的多面函数在GPS高程拟合中的应用

针对多面函数拟合法的中心节点难以选取的问题，提出将蚁群算法引入多面函数并结合稳健估计构建高精度拟合模型的方法。利用蚁群算法在复杂地形中快速寻找特征点，与少量非特征点共同作为中心节点参与模型构建，将稳健估计加入多面函数，运用选权迭代法剔除粗差对拟合模型的影响。GPS高程拟合数据处理实例表明，基于蚁群算法的多面函数结合稳健估计的拟合方法可有效剔除粗差的影响，且拟合精度比只用均匀格网法提高26%。     

基于地形数据的长距离越野路径快速规划方法研究

越野环境下机动车辆的快速路径规划在野外搜救、应急抢险及军事作战等领域均具有重要意义,在以上场景中,随着空间维数的增加,传统路径搜索算法计算复杂性急剧增长,可能无法在既定时间内求解可靠路径。为解决上述不足,本文结合越野路径规划不受路网通行限制以及两点之间直线最短的特点,提出以方向指向作为搜索策略的启发式算法,该算法搜索效率大幅提升,却难以保证求解质量。为进一步提高求解质量,提出了带有方向指向的Dijkstra分段算法,该算法在较低精度环境模型下通过Dijkstra算法找到最优路径,并将该路径进行分段,各分段以方向指向作为搜索策略进行路径搜索,从而在长距离越野路径规划中快速规划通行方案。为验证该算法的有效性,本文利用山西省某市的数字高程模型数据进行实验,引入了窗口移动法对地形进行先期的坡度计算和通行性分析,构建越野环境模型,调用路径搜索算法进行规划。实验结果表明,本文所提算法相比Dijkstra算法计算效率得到了大幅提升,且规划路径的长度接近于最优解。     

基于最优路径策略方法快速计算字符串编辑距离

传统编辑距离算法采用动态规划方法用一个维度大小分别为源字符串长度和目标字符串长度的二维数组保存计算过程中求得编辑距离值。这种传统求解方式在时间效率和空间效率上开销较大,限制了编辑距离算法在长字符串中地应用。针对传统方法存在的问题,经深入研究编辑距离的求解过程,发现在某个关键区域内存在一条最优路径,通过确定最优路径所在关键区域可以快速地求解两字符串之间的编辑距离值。实验表明,方法在计算两字符串之间的编辑距离与传统方法相比可以降低问题的求解规模,提高算法的时间效率和空间效率。所描述的方法同样适用于图论中使用动态规划方法求解一般问题地应用,比如最优分配问题和背包问题等。     

基于LDA和优化蚁群的OD流向时空语义聚类算法

针对OD流向聚类中语义信息考虑不足和流向语义提取困难的问题,本文提出了一种基于隐含狄利克雷分布模型（Latent Dirichlet Allocation,LDA）和优化蚁群的OD流向语义聚类算法。算法首先以流向终点的POI类别为词汇构建流向文档,采用LDA主题模型提取流向语义,量化OD流向间的语义相似度,融合时间、空间和语义相似度构建流向时空语义相似度;接着以流向为节点,以流向时空语义相似度为边构建流向图,利用高斯函数映射以及图连通分量,剔除不相似的流向,实现数据精简;之后借鉴了密度峰值聚类算法思想,利用节点的介数中心性优化蚁群初始位置选取;最后基于多路切图准则（Multiway Normalized Cut, MNCUT）强化蚁群搜索的目的性,优化蚁群搜索的聚类效果,实现OD流向的时空语义聚类。以厦门市出租车公开数据集与厦门市高德地图POI数据为例进行分析与验证,结果表明本文基于LDA模型的语义提取方法可以有效提取流向的语义信息,构建有效的流向相似度度量;基于高斯函数和图连通分量特性的映射策略可以有效剔除了流向数据中的噪音,有效节省无向图构建的计算开支,大约节省了88.5%~88.8%的运行时间;基于介数中心性和多路切图准则优化的蚁群搜索聚类算法,可以有效进行流向语义聚类。相比已有方法本文方法能够更好地衡量流向间的语义相似程度,可实现按主题进行聚类划分,划分更加精细,更方便有效地进行流向语义的相关分析。     

基于NSIDC海冰产品的FY北极海冰数据集优化

北极海冰对全球气候起着非常重要的调制作用,海冰范围是海冰监测的基本参数。近40年,北极地区持续变暖,北极海冰显著减少,进而引发北极自然环境恶化、北半球极端天气频发、全球海平面上升等一系列环境和气候问题。准确获取北极海冰范围及其演变趋势,确定海冰变化对全球气候系统的响应,是研究和预测全球气候变化趋势的关键之一。HasISST和OISST海冰数据集在海冰监测中应用最为广泛,可为北极地区长时间序列海冰变化研究提供基础数据,但这2套数据集空间分辨率相对较低,应用于北极关键区对中国气候响应研究方面存在很大的局限,为解决这一问题和弥补国内海冰监测微波遥感数据的空白,2011年6月27日,国家卫星气象中心（National Satellite Meteorological Center, NSMC）发布了FY（Fengyun, FY）北极海冰数据集,该数据集利用搭载在FY卫星上的微波成像仪（Microwave Radiation Imager, MWRI）数据,使用Enhance NASA Team算法制作,该算法利用前向辐射传输模型模拟北极地区4种海表类型（海水、新生冰、一年冰和多年冰）在不同大气条件下MWRI辐射亮温,进而得到每种大气条件下0~100%的海冰覆盖度查找表（海冰覆盖度每次增加1%）,通过观测值与模拟值的比对得到海冰覆盖度,由该数据集计算得到的北极海冰范围在大部分区域与实际情况相符。该产品虽已进行通道间匹配误差修正和定位精度偏差订正,但由于其搭载的微波成像仪（Microwave Radiation Imager, MWRI）天线长度有限,造成传感器探测到的地物回波信号相对较弱,难以区分海冰和近岸附近的陆地,影响了该数据集的精度和应用。为解决这一问题,本文基于美国冰雪中心（National Snow and Ice Data Center, NSIDC）发布的海冰产品对FY海冰数据集进行优化,NSIDC产品利用判断矩阵对海岸线附近的像元进行识别,并对误差像元进行不同程度的修正,由NSIDC产品计算得到的北极海冰范围与实际情况更为符合。数据集优化大大提高了FY海冰数据集的精度,研究结果表明,优化后FY海冰数据集与NSIDC产品相关系数高达0.9997,且二者日、月、年平均最大海冰范围偏差仅为3.5%、1.9%、0.9%,且FY海冰数据集优化过程对其较好的空间分异特征无明显影响。该数据集可正确地反映北极海冰范围及其变化情况,且海岸线附近海冰的分布情况更准确,可为北极海冰变化研究提供可靠的基础数据。