动态规划算法在基于子区间消除的随机点定位问题中的应用

针对原有基于判决方程的子区间消除算法中所存在的判决结果与决策表不相符,以及当子区间划分规模增大时,运行时间呈平方次增长的问题,本文提出了一种全新的基于动态规划的子区间消除算法。新算法充分利用动态规划在多阶段决策问题中的卓越性能,将子区间的消除问题划分为合理性判断和新区间生成两部分,这两个部分均可以利用动态规划中子问题分割的思想来解决。文中证明了通过解决这些子问题可以构造得到原问题的最优解,分析了算法的时间复杂度和空间复杂度。为了检验新算法的性能,本文从理论和实验两种维度,进行了新旧两种算法的对比。实验结果表明,该方法大大降低了算法的时间复杂度,有效克服了子区间规模增大所导致的问题,提高了算法的灵活性和运行速度。     

基于频繁项集树的时态关联规则挖掘算法

针对目前时态关联规则研究中存在的挖掘效率不高、规则可解释性低、未考虑项集时间关联关系等问题,在原有相关研究的基础上,提出一种新的基于频繁项集树的时态关联规则挖掘算法.通过对时间序列数据进行降维离散化处理,采用向量运算生成频繁项集,提高频繁项集挖掘效率.考虑到项集之间的时态关系以及树结构的优势,提出一种新的频繁项集树结构挖掘时态关联规则,其挖掘频繁项集与树结构构建同时进行,无需产生候选项集,提高了规则挖掘效率.实验表明,对比于其他算法,所提出算法在挖掘效率和规则解释性方面效果更好,具有较好的应用前景.     

一种改进的多边形数据内点自动生成算法

基于最小外切矩形(MBR)的多边形内点生成算法在奇异情况下容易失效。针对该问题,引入矢量数据的不确定性区间,提出一种改进的多边形数据内点自动生成算法。采用不确定性区间和相交区间的处理方法对奇异情况进行统一修正,避免MBR算法对于切割线与节点相交情况的过多异常处理和分支结构。通过对比实验验证了该算法的健壮性和高效性。     

直线扫描转换中的最小生成机制

深入研究了直线扫描转换的最小生成机制,提出一种扫描转化算法．该算法使得直线扫描转换不必对每一点进行,只需对直线段的最小生成区间进行扫描转换即可,而直线段的其他部分可以利用最小生成段的平移得到,从而能显著地提高直线扫描转换的速度．在生成最小生成段时通过当前点能求出接下来的一系列扫描点,进一步提升了直线扫描转化的效率．     

改进的Bresenham直线生成算法

提出一种新的直线生成算法,该算法通过预知每个像素行要选取的像素点个数,实现在一个像素行上同时处理多个像素,并对斜率k在（0．5,1）时的直线生成算法进行优化,使Bresenham算法的执行效率有很大提高。     

基于事务映射区间求交的高效频繁模式挖掘算法

关联规则挖掘是数据挖掘重要研究课题,大数据处理对关联规则挖掘算法效率提出了更高要求,而关联规则挖掘的最耗时的步骤是频繁模式挖掘。针对当前频繁模式挖掘算法效率不高的问题,结合Apriori算法和FP-growth算法,提出一种基于事务映射区间求交的频繁模式挖掘算法IITM（interval interaction and transaction mapping）,只需扫描数据集两次来生成FP树,然后扫描FP树将每个项的ID映射到区间中,通过区间求交来进行模式增长。该算法解决了Apriori算法需要多次扫描数据集,FP-growth算法需要迭代地生成条件FP树来进行模式增长而带来的效率下降的问题。在真实数据集上的实验显示,在不同的支持度下IITM算法都要要优于Apriori、FP-growth以及PIETM算法。     

基于两段排样方式的矩形件优化下料算法

针对矩形件下料问题,提出一种基于两段排样方式的优化下料算法。首先构造一 种约束排样算法,生成矩形件在板材上的两段排样方式。然后采用列生成算法依据矩形件剩余 需求量迭代调用上述约束排样算法生成一个虚拟下料方案,按照不产生多余矩形件原则选取虚 拟下料方案中的部分排样方式加入到实际下料方案中,更新矩形件剩余需求量;重复上述步骤 直到矩形件剩余需求量为零。采用文献中基准例题将该算法与2 种文献算法进行比较,数值实 验结果表明该算法下料利用率比2 种文献算法分别高1.61%和0.78%。     

基于属性相关性的决策树规则生成算法

决策树方法因结构简单、便于理解和具有较高的分类精度而在数据挖掘中被广泛采用,其规则生成算法实现对决策树规则的提取和化简。属性相关性分析的基本思想是计算某种度量,用于量化属性与给定概念的相关性。提出了一种基于属性相关性的c4．5决策树规则生成算法c—c4．5rules,可替代c4．5原有的规则生成算法。c—c4．5rules在对规则进行化简时充分考虑了属性之间的关联性,实验表明该算法在保持原有分类精度的前提下,能有效提高规则生成时的计算速度和效率。     

DEM中基于遗传与蚁群的混合路径规划算法

现有启发式算法在DEM路径规划中因数据量巨大,效率较低。针对该问题,提出一种基于遗传和蚁群的混合路径规划算法。该算法在遗传过程中,通过在初始群体生成阶段构建选择因子,使得在节点搜索时更加倾向于终点方向,提高初始群体生成效率;对变异过程中变异节点的变异区间进行限制,避免产生路径断点;在蚁群寻优过程中,根据遗传过程产生的路径信息,采用自适应信息素初始化与更新策略,提高算法搜索效率。测试结果表明,混合算法能够在规则网格DEM数据下搜索出符合条件的路径,并具有较好的效率。     

一种改进的动态源路由协议研究

原有的权值簇生成算法及其改进都未能很好解决节点移动性问题。针对这一点在一种新的改进权值簇生成算法基础上,提出了新的基于簇的动态源路由协议NCDSR（New Clustered Dynamic Source Routing）。该权值簇生成算法克服了原有算法的在处理节点的移动速度上的缺陷,在计算权重、生成簇头时,对节点的绝对移动速度进行了判断和限定。NCDSR在GloMoSim模拟器下定义了数据结构,进行了模拟仿真,实验证明当节点的绝对移动速度超过限定值时,NCDSR协议端到端延迟、吞吐率和投递率等性能在网络中载的情况下是可以接收的,较原有的动态源路由协议有效。     

基于改进最低水平线方法与遗传算法的矩形件排样优化算法

传统的最低水平线方法用于矩形件排样时可能产生较多未被利用的空白区域,造 成不必要的材料浪费。针对此缺陷,在搜索过程中引入启发式判断,实现空白区域的填充处理, 提高板材利用率。在应用遗传算法优化矩形件排样顺序时,在进化过程中采用分阶段设置遗传 算子的方法,改善算法的搜索性能与效果。通过改进最低水平线方法与基于分阶段遗传算子的 遗传算法相结合,共同求解矩形件排样问题。排样测试数据表明,所提出的矩形件排样优化算 法能够有效改善排样效果,提高材料利用率。     

一种新型的航空图像城区建筑物自动提取方法

提出了一种新的从航空城区图像中自动提取矩形建筑物的方法．该方法基于从航空城区图像中提取的边缘，经过轮廓跟踪，采用Splitting方法提取直线，得出其相应的直线几何图形；针对航空图像的复杂及现有边缘检测算法的不足，提出了一系列直线处理的方法(如直线的分类、排序、合并、调整等)有效地弥补了前述处理的不足；为提高矩形房屋提取的准确率，引入知识定义了几种近似的矩形结构．文章采用几何结构元分析的方法，提取图形中构成矩形的各种基本结构元，再根据结构元合并的准则，将各种基本结构元通过一定的合并算法合并成矩形结构．大量试验结果证明该方法提取矩形房屋的准确率较高，鲁棒性好，运算速度快，具有较强的实际应用价值．     

Fault analysis in TCSC-compensated lines using wavelets and a PNN

This paper describes an algorithm to detect, localize and classify fault events in overhead transmission lines compensated with a thyristor-controlled series capacitor (TCSC). During a fault event, a complex pattern of traveling wave reflections and refractions is generated at the point of fault inception. The proposed algorithm uses the discrete wavelet transform combined with a probabilistic neural network to analyze all this information and determine whether a fault condition exists in the line, the fault type and also the fault distance. In order to assess the algorithm performance, several studies were carried out under varied conditions. The obtained results demonstrate that the algorithm accuracy for calculating the fault distance is smaller than 1% of the total line length, and a 100% efficiency for determining the fault type. The algorithm is also immune to harmonic interaction due to low-frequency harmonics generated by the TCSC. A comparative advantage over previous algorithms for TCSC-compensated transmission lines is the fact that the proposed algorithm not only identifies the faulted line section but also localizes accurately the distance to the fault, using only measurements at one end of the line.

     

导向定位测序数据的甲基化序列比对算法优化

导向定位测序(GPS)是一种全基因组DNA甲基化检测的新测序技术,产生的测序数据具有成本低、没有序列偏好等优势.目前,甲基化分析中最重要的一步是将其测序产生的序列比对到参考基因组上.但是,现有导向定位测序的方法使用Smith-Waterman进行局部序列比对,时间消耗过大且容易对序列比对位置产生误判.因此,提出一种导向定位测序数据的改进比对算法,该算法利用其双端测序的优势,先用甲基化序列端数据进行序列比对,对多位置匹配的序列再利用常规数据端数据进行比对位置确定.实验结果表明:本文方法和现有方法的准确率相当,而具有更高的唯一比对比率,时间性能有3倍以上的提升.     

基于像素链排序的直线绘制算法*

针对直线生成算法在直线斜率大于0.5时的低效率问题,提出一种基于像素链排序的直线绘制算法。将直线看做是由许多条平行像素链或对角像素链拼接而成,利用逆向生成直线的类Bresenham算法求得各像素链的长度,通过Bresenham算法生成相应直线的位移码对各像素链进行排序,一次判断生成一条像素链。仿真实验表明,基于像素链排序的直线绘制算法生成的直线与Bresenham算法生成的直线精度一致,且计算量显著减少。该算法只有加法和乘法两种整数运算,适合硬件实现,其绘制速度是Bresenham算法的4倍。     

基于像素链的直线绘制算法

针对直线生成算法在直线斜率大于0.5时的低效率问题,提出一种基于像素链的直线绘制算法。将直线看做是由许多条平行像素链或对角像素链拼接而成,提出并利用逆向生成直线的类Bresenham算法,将斜率在0.5~1的直线绘制转换为斜率在0~0.5的直线绘制,一次判断生成一条像素链。仿真实验表明,基于像素链的算法生成的直线与Bresenham算法生成直线一致,且计算量显著减少。该算法只有加法和乘法两种整数运算,适合硬件实现,其绘制速度是Bresenham算法的4倍。     

基于SparkStreaming的海量GPS数据实时地图匹配算法

浮动车GPS数据作为交通信息处理的基础,随着被监控车辆数量的高速增长,产生了海量GPS数据,对地图匹配提出了高挑战,为了解决传统匹配方法难以满足匹配效率和精度的不足,提出一种针对于海量GPS数据的实时并行地图匹配算法,能够同时保证较高匹配精度和运算效率。构建一种面向实时数据流的高效、准确实时地图匹配算法,首先通过引入速度、方向综合权重因子对依赖历史轨迹的离线地图匹配算法进行重构,进而引入Spark Streaming分布式计算框架,实现地图匹配算法的实时、并行运算,大幅提升实时地图匹配效率。实验结果表明,该算法在复杂路段的匹配准确率较常规拓扑匹配算法提高10%以上,整体匹配准确率达到95%以上;在匹配效率方面,较同等数量的单机服务器可提高效率4倍左右。实验结果表明,该算法在由11台机器组成的计算集群上实现8 000万个GPS数据点的实时地图匹配,证明了该算法可以完成城市地区的实时车辆匹配。     

基于最小边界扇形的移动对象轨迹实时化简算法

为了对全球定位系统(GPS)设备采集到的移动对象原始轨迹数据进行简化,提高轨迹数据的使用效率,降低移动终端的通信代价和计算开销,提出了一种基于最小边界扇形(MBS)的移动对象轨迹实时化简算法。该算法不同于用一条折线来近似原始轨迹的方法,它利用扇形预测范围来估计、简化原始轨迹,在角度和距离两个层面上对简化误差进行控制。提出了新的误差度量方法--基于等极径的误差度量方法,并讨论了GPS定位误差对简化算法的影响。实验结果表明,所提算法的简化轨迹高效、稳定,所得到的简化轨迹与原始轨迹之间误差较小(不超过误差阈值的20%),对GPS定位误差有较好的容错能力。     

带静不平衡约束的正交矩形布局问题的启发式模拟退火算法*

以卫星舱布局为背景,研究一类带静不平衡约束的正交矩形布局问题.借鉴拟物策略,定义矩形与矩形、矩形与圆形容器之间的嵌入度计算公式,将该问题转变为无约束的优化问题.通过将启发式格局更新策略、基于梯度法的局部搜索机制与具有全局优化功能的模拟退火算法相结合,提出一种求解带静不平衡约束的正交矩形布局问题的启发式模拟退火算法.算法中的启发式格局更新策略产生新格局和跳坑,梯度法搜索新格局附近能量更低的格局.另外,在布局优化过程中,通过在挤压弹性势能的基础上增加静不平衡量惩罚项,并采用质心平移的方法,使布局系统的静不平衡量达到约束要求.实验表明,文中算法是一种解决带静不平衡约束的正交矩形布局问题的有效算法.     

基于遗传模拟退火算法的布局优化研究

为提高矩形件排样算法的利用率与时间效率,提出将遗传算法和模拟退火算法融 合优化的矩形排样算法。采用带符号的十进制编码,依据矩形件长宽比和面积而生成基因序列用 于建立初始种群,以随机产生若干排样顺序与排样尺寸不一的个体,并以利用率为适应度函数, 修改后的最低水平线搜索算法作为排样策略,保证较优个体得以保留,减少闲置区域的产生。 采用10 组随机产生的矩形数据将本算法与现有文献提出的GA 算法进行对比实验,实验结果显 示：该算法有效地提升了排样结果的利用率与时间效率。