基于迭代局部搜索的区划问题算法研究

区划问题是将特定地理区域划分为若干空间连续的分区,满足分区内差异最小和分区间差异最大这一基本原则,广泛应用于地理、环境、生态、经济、农业、城市等领域。1960s以来,学者尝试建立各种区划问题数学模型,设计了一系列的求解算法,代表性的算法主要有：AZP、ARISEL、SKATER和REDCAP。本文提出了一个基于迭代局部搜索(ILS)的区划问题算法,进一步提升算法性能。该算法主要机制包括：邻域单元移动搜索改进分区质量;参照中心单元快速计算分区方差,提升算法速度;使用扰动机制跳出当前解局部最优状态;更新分区中心点提升分区方案目标值;使用群搜索探索更大的解空间;以及算法各步骤中通过分区空间连续判断和破碎修复保持分区空间连续。55个基准案例测试表明： ILS算法求解质量优于ARISEL和SKATER算法。一个多指标气候分区实验也表明： ILS算法求解质量优于SKATER、REDCAP和ARISEL算法。     

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

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

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

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

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

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

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

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

一种基于SuperMap GIS的改进Dijkstra算法

为提高传统Dijkstra算法的搜索效率,满足车载导航中路径规划实时性的要求,本文利用SuperMapGIS平台的网络编辑功能,设计了一种基于SuperMap的改进Dijkstra算法。首先,结合道路网络的空间分布特性,在SuperMap中构建了道路网络;其次,设计算法,根据起止节点合理限制算法的搜索区域,并以经典Dijkstra为理论基础实现最短路径的求解;最后,结合需要设计了约束条件下的路径规划算法。在城市道路网络中的应用实例验证了算法的有效性。     

附有基线长约束的改进CLAMBDA算法研究

探讨附有基线长约束的最小二乘模糊度降相关搜索算法(CLAMBDA)的基本原理和实现过程,针对其处理高维模糊度时存在搜索效率低的问题,提出一种基于部分模糊度搜索策略的改进CLAMBDA算法。新算法通过优选部分模糊度子集,在改善搜索空间形状的同时,降低了模糊度搜索空间的维数,有效提高了模糊度的搜索效率。利用澳大利亚科廷大学静态短基线网数据和实测动静态定位数据进行验证,结果表明,改进的模糊度搜索方案可以在保证模糊度固定成功率的情况下,有效地缩短搜索时间,能更好地满足载体实时姿态测量的要求。     

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

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

排序对模糊度解算中降相关性能的影响分析

针对不同排序算法对模糊度解算存在降相关性能影响的问题,从理论上分析了自然升序法、对称旋转法及扰动升序法的降相关原理,并基于模拟数据和实测数据,从降相关时间、搜索时间、总体耗时、Bootstrapping成功率及条件数5个方面对3种算法进行对比分析。结果表明,降相关效率与搜索椭球压缩程度呈负相关关系,搜索椭球压缩程度越高,降相关效率越低;对于不同的排序算法,提高降相关性能的关键在于减少降相关时间及对条件方差按一定方向排序,进而提高搜索效率。     

一种基于路网等级启发式策略的路径搜索算法

本文提出了一种基于路网等级启发式策略的路径搜索算法。通过引入考虑路网等级因素的代价评估函数,有目的地引导搜索过程考虑路网道路等级特征,限制路径搜索规模,在精度可控的前提下,大幅度提高时间最短路径算法的效率,并使得搜索路径结果更符合心理认知过程。其与经典的层次空间推理算法相比,本文提出的算法实现过程简单,效率和精度相似。理论分析和实验过程验证了本文所提出算法的有效性。     

基于O-TREE树表示的总线约束在VLSI/PCB布局中的应用

布局是VLSI物理设计的关键环节，采用了O-TREE的编码表示方法来解决在超大规模集成电路布局中，具有预定义坐标结群约束模块的布局问题(简称PCA问题)。目前，存在一些成功的算法来解决PCA问题，然而，它们的算法有些复杂，有些耗时。由此提出了一种新的布局算法来解决这个问题，该算法是基于O-TREE结构，旨在减少总的运行时间且简便。通过对MCNC的标准例子ami33和ami49上仿真实验表明：与参考文献5提到的结果相比，新算法是可行的并且很有效。它不仅使芯片面积利用率得到改善，而且节约了一半以上的时间开销。     

����Ӧ������LU�ֽⷨ����߲�̬������

?????????????????????????к??????????????????????????ì????????????????????????Ч?????????????????????????????????LU??????????????????????????????LU??????????????????????????????????????У??????????????????????в????????????????????С????????????????????????????????????????????????????     

基于Levenberg-Marquarat算法的非线性三维直角坐标转换方法

提出一种基于Levenberg-Marquarat算法的非线性三维直角坐标转换方法,在法矩阵病态或者奇异时依然有效,并通过修正旋转角参数的方法,有效解决了平移量与旋转角量纲不同造成的迭代发散问题。设计出简洁有效的迭代求解模式,获得了稳定的参数解。最后通过模拟数据对比分析,证明该方法的有效性和正确性。     

����IMM-PF�Ĺ���/�ش���ϵ����㷨

???????/????????????????????????????????????????????????????????????(PF)???IMM??????????IMM-PF???????????÷??????????????????????????????????????????????????????????????EKF??????IMM-PF??????????????????????????????????????????????????????????????     

����Vondrak�ֲ�̽��Ŀ���EKF�㷨��GPS�����е�Ӧ��

???????Vondrak?????????????EKF??,???????GPS??????λ??????????????EKF??????????????????Vondrak??????????????????μ????EKF???????????????д???????λ????????????????EKF???????????????????????д???????????????EKF????????????????д?????????????????????????????????????п????????????????????Ч???     

Multi-Objective Weather Routing Algorithm for Ships Based on Hybrid Particle Swarm Optimization

Maritime transportation has become an important part of the international trade system.To promote its sustainable de-velopment,it is necessary to reduce the fuel consumption of ships,decrease navigation risks,and shorten the navigation time.Ac-cordingly,planning a multi-objective route for ships is an effective way to achieve these goals.In this paper,we propose a multi-ob-jective optimal ship weather routing system framework.Based on this framework,a ship route model,ship fuel consumption model,and navigation risk model are established,and a non-dominated sorting and multi-objective ship weather routing algorithm based on particle swarm optimization is proposed.To fasten the convergence of the algorithm and improve the diversity of route solutions,a mutation operation and an elite selection operation are introduced in the algorithm.Based on the Pareto optimal front and Pareto optimal solution set obtained by the algorithm,a recommended route selection criterion is designed.Finally,two sets of simulated navigation simulation experiments on a container ship are conducted.The experimental results show that the proposed multi-objective optimal weather routing system can be used to plan a ship route with low navigation risk,short navigation time,and low fuel consumption,fulfilling the safety,efficiency,and economic goals.     

BDS/GPS差分系统间偏差估计算法及性能分析

基于BDS/GPS单频紧组合相对定位模型,提出联合卡尔曼滤波与粒子滤波估计差分系统间偏差(DISB)的算法,并利用实测短基线数据对比分析卡尔曼滤波算法与本文算法估计DISB的效果。实验表明,载波DISB的整数部分会影响参考卫星站间单差模糊度的估计,从而影响载波DISB小数部分的估计结果;利用本文算法估计并改正DISB后得到的模糊度解算的可靠性和固定解精度均优于卡尔曼滤波,固定解精度最大可提高10%～20%。     

克隆选择算法的线状要素图形简化模型

 线状要素作为占据地图图形80%以上的地图目标,其自动概括是制图综合的一个重要内容。线状要素图形简化是其制图综合的一个主要手段。本研究以克隆选择算法的基本原理,分析对线状要素数据进行压缩时图形简化的约束条件,顾及线状要素的几何精度和形状特征,设计相应的编码机制、变异机制和亲和度函数,提出一种新的线状要素图形自动简化模型。同时,结合不可行解修复机制,提高图形简化的精度。最后,将该模型与道格拉斯算法、遗传算法的简化结果作对比,实验表明,在相同的几何精度内,文中提出的线状要素图形简化模型,在保持线状要素图形形状方面表现更佳。