在消息传递并行机上的高效的最小生成树算法

基于传统的Borǔ vka串行最小生成树算法,提出了一个在消息传递并行机上的高效的最小生成树算法.并且采用3种方法来提高该算法的效率,即通过两趟合并及打包收缩的方法来减少通信开销,通过平衡数据分布的办法使各个处理器的计算量平衡.该算法的计算和通信复杂度分别为O(n²/p)和O((t_sp+t_wn)n/p).在曙光-1000并行机上运行的实际效果是,对于有10 000个顶点的稀疏图,通过16个节点的运行加速比是12.     

有Mate-Pairs的个体单体型MSR问题的参数化算法

个体单体型MSR(minimum SNP removal)问题是指如何利用个体的基因测序片断数据去掉最少的SNP(single-nucleotide polymorphisms)位点,以确定该个体单体型的计算问题.对此问题,Bafna等人提出了时间复杂度为O(2^kn²m)的算法,其中,m为DNA片断总数,n为SNP位点总数,k为片断中洞(片断中的空值位点)的个数.由于一个Mate-Pair片段中洞的个数可以达到100,因此,在片段数据中有Mate-Pair的情况下,Bafna的算法通常是不可行的.根据片段数据的特点提出了一个时间复杂度为O((n-1)(k₁-1)k₂2^2h+(k₁+1)^2h+nk₂+mk₁)的新算法,其中,k₁为一个片断覆盖的最大SNP位点数(不大于n),k₂为覆盖同一SNP位点的片段的最大数(通常不大于19),h为覆盖同一SNP位点且在该位点取空值的片断的最大数(不大于k₂).该算法的时间复杂度与片断中洞的个数的最大值k没有直接的关系,在有Mate-Pair片断数据的情况下仍然能够有效地进行计算,具有良好的可扩展性和较高的实用价值.     

基于SSA-LSTM模型的日水位预测—以涡河流域涡阳闸为例

水位的准确预测可以指导城市的防洪减灾举措及水利工程建设, 提升城市洪涝灾害应急响应速度. 基于数据驱动的水位预测模型, 尤其是LSTM模型, 在模拟自然界中水文要素的强非线性关系时展现出优势从而得到广泛应用. 然而, 自然界中水文数据的采集往往伴随着噪声以及人为干扰因素, 这些问题影响了模型的预测性能. 针对这一问题, 本文开发了一种新的组合模型, 即SSA-LSTM模型. 该模型首先利用SSA方法将观测到的时间序列分解为周期、趋势和噪声分量, 接着利用LSTM对SSA方法去噪后的序列进行模型训练并得到最终预测结果.本文选取涡河流域涡阳闸1971年5月至2020年12月的闸上水位为数据集, 1)利用奇异谱分析方法将原始水位时序数据分解为多个趋势和噪声分量(RC₁–RC₁₂), 选取分量(RC₁–RC₁₀)为趋势项并重构为新的水位时序信号; 2)利用LSTM模型对重构的信号进行了训练和验证, 并将预测结果与LSTM模型的结果进行了对比; 3)为得到最优的SSA-LSTM模型, 针对不同的时间步长(7、14、21、28、35天)开展了单步预测性能评估实验, 实验结果表明, 在不同的时间步长下, SSA-LSTM水位预测模型的决定系数R²、均方根误差RMSE、平均绝对误差百分比MAPE均优于LSTM模型. 由此可见, 采用 SSA方法对涡阳闸水位的预处理可有效提高 LSTM 的预测效果, 相比于传统 LSTM 模型, SSA-LSTM模型具有高可靠和低误差的特点, 在水位预测应用中更具适应性, 可以为城市防洪、灌溉、供水等水利措施的合理调度提供更优的决策依据.     

PUMA机器人运动学逆解新算法

6R串联机器人的逆解求解复杂,使用传统的D-H算法求解该问题计算量大且无法避免奇异点.将PUMA机器人的逆运动学的求解分为位置求解和姿态求解两个过程.首先使用D-H方法进行位置求解得到关节角θ₁,θ₂,θ₃,然后使用单位四元数的方法求解出θ₄,θ₅,θ₆.最后,在PUMA机器上进行验证,新的方法能够正确求解出所有解析解.对比新方法、D-H方法和倍四元数的方法,新方法较D-H方法速度提高了15%左右.     

结合可信度的km-means算法

以K-means为代表的聚类算法被广泛地应用在许多领域, 但是K-means不能直接处理不完整数据集. k_m-means是一种处理不完整数据集的聚类算法, 通过调整局部距离计算方式, 减少不完整数据对聚类过程的影响. 然而k_m-means初始化阶段选取的聚类中心存在较大的不可靠性, 容易陷入局部最优解. 针对此问题, 本文引入可信度, 提出了结合可信度的k_m-means聚类算法, 通过可信度调整距离计算, 增大初始化过程中选取聚类中心的可靠性, 提高聚类算法的准确度. 最后, 通过UCI和UCR数据集验证算法的有效性.     

改进的加权稀疏表示人脸识别算法

针对传统的加权稀疏表示分类方法在获取训练样本权重以及求解l₁范数最小化问题中计算效率低的问题,提出了一种加权稀疏表示和对偶增广拉格朗日乘子法（DALM）相结合的人脸识别算法WSRC_DALM算法.该算法主要采用高斯核函数计算每个训练样本与测试样本之间的相关性,即获得训练样本相对于测试样本的权重;接着利用DALM算法求解l₁范数最小化模型,实现测试样本的精准重构和分类,最后在ORL和FEI人脸数据集上进行算法验证.在ORL数据集中,WSRC_DALM算法的识别率高达99%,相比经典的SRC和WSRC算法,识别率分别提高了7%和4.8%,同时计算效率比WSRC算法提高了约20倍;在FEI数据集中,多姿态变化下的人脸识别率接近于92%.实验结果表明,WSRC_DALM算法在识别准确度和计算效率上具有明显的优势,并且对较大类内变化具有较好的鲁棒性.     

深度学习模型中的公平性研究

近几年深度神经网络正被广泛应用于现实决策系统,决策系统中的不公平现象会加剧社会不平等,造成社会危害.因此研究者们开始对深度学习系统的公平性展开大量研究,但大部分研究都从群体公平的角度切入,且这些缓解群体偏见的方法无法保证群体内部的公平.针对以上问题,本文定义了两种个体公平率计算方法,分别为基于输出标签的个体公平率（IFR_b）,即相似样本对在模型预测中标签相同的概率和基于输出分布的个体公平率（IFR_p）,即相似样本对的预测分布差异在阈值范围内的概率,后者是更严格的个体公平.更进一步,本文提出一种提高模型个体公平性的算法IIFR,该算法通过余弦相似度计算样本之间的差异程度,利用相似临界值筛选出满足条件的相似训练样本对,最后在训练过程中将相似训练样本对的输出差异作为个体公平损失项添加到目标函数中,惩罚模型输出差异过大的相似训练样本对,以达到提高模型个体公平性的目的.实验结果表明,IIFR算法在个体公平的提升上优于最先进的个体公平提升方法.此外IIFR算法能够在提高模型个体公平性的同时,较好地维持模型的群体公平性.     

RB模型实例集上置信传播算法的收敛性

置信传播算法求解RB（k,n,α,r_c,p）模型实例时非常有效,几乎能够有效求解接近可满足性相变点的难解实例.然而,因子图带有回路的实例,置信传播算法不总有效,常表现为不收敛.对于这种现象,至今缺少系统的理论解释.置信传播算法是最为基础的信息传播算法,对置信传播算法的收敛性分析是其他信息传播算法收敛性分析的重要基础.在RB（k,n,α,r_c,p）模型中,取k=2,α>（1/k）,r_c>0均为常数,且满足ke^{-（α/（r_c））}≥1.证明了如果p∈（0,n^-2α）,则置信传播算法在RB（k,n,α,r_c,p）模型产生的随机实例集上高概率收敛.最后,在RB（k,n,α,r_c,p）模型上选取了几组不同的数据进行数值模拟,实验结果表明该结论有效.当问题规模n增大时,在RB（k,n,α,r_c,p）模型的可满足区域,实验收敛区间趋于一个固定范围,而理论收敛区间逐渐变窄.原因在于,RB（k,n,α,r_c,p）模型是一个具有增长定义域的随机CSP实例产生模型,不协调赋值的数目与参数p及问题规模n有关.     

k-Median近似计算复杂度与局部搜索近似算法分析

k-Median问题的近似算法研究一直是计算机科学工作者关注的焦点,现有研究结果大多是关于欧式空间和Metric空间的,一般距离空间k-Median的结果多年来一直未见.考虑一般距离空间k-Median问题,设d_max/d_min表示k-Median实例中与客户点邻接的最长边长比最短边长的最大者.首先证明d_max/d_min≤ω+ε的k-Median问题不存在近似度小于1+ω-1/e的多项式时间近似算法,除非,由此推出Metric k-Median问题不可近似到1+2/e,除非NP(∈)DTME(N^{O(log logn)}).然后给出k-Median问题的一个局部搜索算法,分析表明,若有d_max/d_min≤ω,则算法的近似度为1+ω-1/2.该结果亦适用于Metric k-Median,ω≤5时,局部搜索算法求解Metric k-Median的近似度为3,好于现有结果3+2/P.通过计算机实验,进一步研究了k-Median局部搜索求解算法的实际计算效果和该算法的改进方法.     

数据仓库系统中层次式Cube存储结构

区域查询是数据仓库上支持联机分析处理(on-line analytical processing,简称OLAP)的重要操作.近几年,人们提出了一些支持区域查询和数据更新的Cube存储结构.然而这些存储结构的空间复杂性和时间复杂性都很高,难以在实际中使用.为此,提出了一种层次式Cube存储结构HDC(hierarchical data cube)及其上的相关算法.HDC上区域查询的代价和数据更新代价均为O(log^dn),综合性能为O((logn)^2d)(使用C_qC_u模型)或O(K(logn)^d)(使用C_qn_q+C_un_u模型).理论分析与实验表明,HDC的区域查询代价、数据更新代价、空间代价以及综合性能都优于目前所有的Cube存储结构.     

基于大数据的分布式光伏接入配电网影响分析与功率预测研究

为提高分布式光伏发电功率预测的精度,满足电网调度和规划的高精度要求,本文利用光伏运行、电能量采集、电网调度等业务系统的海量数据,利用大数据分析方法研究大量分布式光伏接入对配电网负荷特性的影响,并提出基于气象相似日和粒子群算法优化BP神经网络的光伏电站功率预测方法。通过分析光伏发电功率随天气类型、温度、光照强度等气象因素变化规律,运用模糊聚类算法计算确定待预测日的气象相似日序列,选取气象相似日历史数据作为BP神经网络预测模型的输入变量,并采用粒子群算法方法优化BP神经网络的初始值,最终输出分布式光伏各时段发电功率的预测值。实验结果表明该方法可有效提高光伏电站功率预测模型的收敛能力和学习能力,具有较高的预测精度。     

自适应BP神经网络在日最高气温预报中的应用

气象数据规模飞速增长,BP神经网络由于其强大的非线性系统拟合能力,在气象数据尤其是气温相关数据的分析和预测中得到广泛应用。考虑到气温数据的海量规模,采用传统BP神经网络的预报面临误差收敛速度慢、容易陷入局部极小等问题,从而严重影响预测的效率和精准度。本文以BP算法为基础提出了一种改进的学习率自适应算法建立BP网络预报模型,并针对气象数据的多维性和周期性提出了优化方案。实验结果表明该方法可以高效的完成最高气温的预测,并且相对传统算法拥有更高的预报精度。     

基于遗传神经网络的网格资源预测模型

研究网格资源预测问题,网格资源具有非线性、混沌变化特点,传统BP神经网络具有局部极小、收敛速度慢等缺陷,预测精度较低。为提高了网格资源预测精度,提出一种基于遗传神经网络的网格资源预测模型。利用遗传算法对BP神经网络的权值和阈值进行优化,然后采用BP神经网络对网格资源建立预测模型,最后采用网格资源时间序列进行有效性仿真。仿真结果表明,遗传神经网络有效地解决了传统BP神经网络的不足,提高了网格资源的预测精度,降低了预测误差,十分适合于非线性、混沌的网格资源时间序列预测。     

基于关联规则的PSO-Elman短期风速预测

传统神经网络在短期风速预测中,存在易陷入局部极值和动态性能不足等问题,从而导致风速预测精度较低。为了提高风速预测精度,提出一种基于关联规则的粒子群优化Elman神经网络风速预测模型。利用粒子群算法优化Elman神经网络模型参数,以提高算法的收敛速度,避免陷入局部极值,以得到最优的预测值。同时结合关联规则分析考虑气象因素,采用Apriori算法对风速与其他气象因素进行关联规则挖掘,并利用得到的关联规则对风速预测值进行修正与补偿。实验结果表明,所提出的预测模型的预测效果比传统模型的效果更佳,同时验证了结合关联规则考虑气象因素能够降低风速预测误差。     

改进粒子群—BP神经网络模型的短期电力负荷预测

为了准确、快速、高效地预测电网短期负荷,提出了改进的粒子群算法(MPSO),并与BP算法相结合,形成改进的粒子群—BP(MPSO-BP)神经网络算法,用此算法训练神经网络,实现了神经网络参数优化,得到了基于MPSO-BP算法的神经网络模型。综合考虑气象、天气、日期类型等影响负荷的因素,进行电网短期负荷预测。算例分析表明,与传统BP神经网络法和PSO-BP神经网络方法相比,该方法改善了BP神经网络的泛化能力,预测精度高,收敛速度快,对电力系统短期负荷具有良好的预测能力。     

股票价格预测的建模与仿真研究

研究股票价格准确预测问题,由于股票价格数据具非线性、随机性等变化规律,同时股票市场与国内外经济政治变化有关,传统股票价格预测方法只能对其线性变化规律进行准确预测,无法反映股票价格非线性部分进行有效建模,导致股价预测精度不高。为了提高股票价格预测精度,提出了一种遗传优化BP神经网络的股票价格预测模型。充分利用BP神经网络良好的非线性映射能力,对股票价格变化规律进行建模,并通过遗传算法对BP神经网络模型参数进行优化,从而获最优股票价格最优预测模型。实验结果表明,相对于传统股票价格预测模型,遗传算法优化BP神经网络的股票价格预测模型拟合程度更好,预测精度更高,为股票价格预测提供了依据。     

基于粒子群优化的灰色神经网络组合预测模型研究

灰色神经网络在人工智能预测领域已经得到广泛的应用,但由于其自身存在局部最小化和收敛速度慢等问题,使其预测精度受到一定的限制。针对其不足,本文提出一种利用粒子群算法优化BP神经网络的学习算法,在此基础上,利用灰色预测方法对股指期货历史数据进行初步预测,并且把初步预测的结果作为优化BP神经网络的输入进行训练和预测,构建了基于粒子群优化的灰色神经网络组合预测模型(PSO-GMNN)。仿真实验结果表明,新预测模型的预测精度高于BP神经网络、灰色神经网络和灰色预测模型,同时也表明了该方法的有效性和可行性。     

基于改进的Adaboost-BP模型在降水中的预测

针对目前分类算法对降水预测过程存在着泛化能力低、精度不足的问题,提出改进Adaboost算法集成反向传播（BP）神经网络组合分类模型。该模型通过构造多个神经网络弱分类器,赋予弱分类器权值,将其线性组合为强分类器。改进后的Adaboost算法以最优化归一化因子为目标,在提升过程中调整样本权值更新策略,以此达到最小化归一化因子的目的,从而确保增加弱分类器个数的同时降低误差上界估计,通过最终集成的强分类器来提高模型的泛化能力和分类精度。选取江苏境内6个站点的逐日气象资料作为实验数据,建立7个降水等级的预报模型,从对降雨量有影响的众多因素中,选取12个与降水相关性较大的属性作为预报因子。通过多次实验统计,结果表明基于改进的Adaboost-BP组合模型具有较好的性能,尤其对58259站点的适应性较好,总体分类精度达到81%,在7个等级中,对0级降雨的预测精度最好,对其他等级的降雨预测有不同程度的精度提升,理论推导及实验结果证明该种改进可以提高预测精度。     

泊松分布灰色理论在物流需求预测中的应用

研究物流需求预测准确度问题。物流需求预测中存在数据小以及非线性特点,使预测系统存在不确定性。为解决上述问题,提出了一种泊松分布的神经网络需求预测算法,采用泊松分布算法对物流的整体需求进行分类,然后采用灰色理论算法选择物流需求影响因子,对物流的需求进行实时预测,仿真结果表明,改进物流需求预测方法比传统的灰色理论预测模型以及BP神经网络具有更高的预测精确度,有效地提高了区域物流需求的预测准确度,具有一定的实际应用价值。     

土壤墒情预测自适应遗传神经网络算法研究

针对传统遗传神经网络算法易出现的早熟收敛及锯齿等现象,提出一种新型算法应用于土壤墒情预测。该算法提出了衡量种群基因多样性的遗传多样性函数的概念,自适应调节交叉和变异策略,在全局范围内寻找最优初始网络权值和阈值,从而降低算法迭代次数,提高神经网络预测的精度和效率。仿真结果表明,与其他遗传神经网络算法相比较,该算法平均绝对误差从2%降低到1%,平均相对误差从5%降低到3%,最大相对误差从15%降低到8%,即新型算法可有效提高墒情的预测质量。