Modeling and solving the rooted distance-constrained minimum spanning tree problem

In this paper we discuss models and methods for solving the rooted distance constrained minimum spanning tree problem which is defined as follows: given a graph G=(V,E)$G=(V,E)$ with node set V={0,1,…,n}$V=\{0,1,\dots ,n\}$ and edge set E$E$, two integer weights, a cost _ce$c_e$ and a delay _we$w_e$ associated with each edge e$e$ of E$E$, and a natural (time limit) number H$H$, we wish to find a spanning tree T$T$ of the graph with minimum total cost and such that the unique path from a specified root node, node 0, to any other node has total delay not greater than H$H$. This problem generalizes the well known hop-constrained spanning tree problem and arises in the design of centralized networks with quality of service constraints and also in package shipment with service guarantee constraints. We present three theoretically equivalent modeling approaches, a column generation scheme, a Lagrangian relaxation combined with subgradient optimization procedure, both based on a path formulation of the problem, and a shortest path (compact) reformulation of the problem which views the underlying subproblem as defined in a layered extended graph. We present results for complete graph instances with up to 40 nodes. Our results indicate that the layered graph path reformulation model is still quite good when the arc weights are reasonably small. Lagrangian relaxation combined with subgradient optimization procedure appears to work much better than column generation and seems to be a quite reasonable approach to the problem for large weight, and even small weight, instances.     

Information-theoretic Approaches Based on Sequential Monte Carlo to Collaborative Distributed Sensors for Mobile Robot Localization

We consider the Sequential Monte Carlo (SMC) method for Bayesian inference applied to the problem of information-theoretic distributed sensor collaboration in complex environments. The robot kinematics and sensor observation under consideration are described by nonlinear models. The exact solution to this problem is prohibitively complex due to the nonlinear nature of the system. The SMC method is, therefore, employed to track the probabilistic kinematics of the robot and to make the corresponding Bayesian estimates and predictions. To meet the specific requirements inherent in distributed sensors, such as low-communication consumption and collaborative information processing, we propose a novel SMC solution that makes use of the particle filter technique for data fusion, and the density tree representation of the a posterior distribution for information exchange between sensor nodes. Meanwhile, an efficient numerical method is proposed for approximating the information utility in sensor selection. A further experiment, obtained with a real robot in an indoor environment, illustrates that under the SMC framework, the optimal sensor selection and collaboration can be implemented naturally, and significant improvement in localization accuracy is achieved when compared to conventional methods using all sensors.     

AptaCDSS-E: A classifier ensemble-based clinical decision support system for cardiovascular disease level prediction

Conventional clinical decision support systems are generally based on a single classifier or a simple combination of these models, showing moderate performance. In this paper, we propose a classifier ensemble-based method for supporting the diagnosis of cardiovascular disease (CVD) based on aptamer chips. This AptaCDSS-E system overcomes conventional performance limitations by utilizing ensembles of different classifiers. Recent surveys show that CVD is one of the leading causes of death and that significant life savings can be achieved if precise diagnosis can be made. For CVD diagnosis, our system combines a set of four different classifiers with ensembles. Support vector machines and neural networks are adopted as base classifiers. Decision trees and Bayesian networks are also adopted to augment the system. Four aptamer-based biochip data sets including CVD data containing 66 samples were used to train and test the system. Three other supplementary data sets are used to alleviate data insufficiency. We investigated the effectiveness of the ensemble-based system with several different aggregation approaches by comparing the results with single classifier-based models. The prediction performance of the AptaCDSS-E system was assessed with a cross-validation test. The experimental results show that our system achieves high diagnosis accuracy (>94%) and comparably small prediction difference intervals (<6%), proving its usefulness in the clinical decision process of disease diagnosis. Additionally, 10 possible biomarkers are found for further investigation.     

基于PS-RRT算法的机械臂避障路径规划

针对应用快速搜索随机树（RRT）算法进行机械臂路径规划时,存在采样区域大、有效区域小、路径冗余节点多、剪枝时间长等问题,提出一种基于分区动态采样策略和重复区域节点拒绝机制的高效RRT路径规划算法PS-RRT（partitioned sampling RRT）。首先,通过PS-RRT快速规划机械臂末端初始路径;其次,分段检测机械臂跟随该路径时的连杆碰撞情况,对碰撞路段进行带臂形约束的第二次规划;最后,将初始路径和第二次规划的路径拼接后进行路径裁剪。将所提方法在多种场景中进行仿真验证,结果表明：基于PS-RRT算法的机械臂避障路径规划策略使得无效节点数大幅减少,可高效规划出机械臂的无碰路径,验证了算法的可行性。     

基于分段电容阵列的改进型逐次逼近型ADC

为缩短高速模数转换器(ADC)中高位(MSB)电容建立时间以及减小功耗,提出了一种基于分段式电容阵列的改进型逐次逼近型(SAR)ADC结构,通过翻转小电容阵列代替翻转大电容阵列以产生高位数字码,并利用180 nm CMOS工艺实现和验证了此ADC结构。该结构一方面可以缩短产生高位数码字过程中的转换时间,提高量化速度;另一方面其可以延长大电容的稳定时间,减小参考电压的负载。通过缩小比较器输入对管的面积以减小寄生电容带来的误差,提升高位数字码的准确度。同时,利用一次性校准技术减小比较器的失配电压。最终,采用180 nm CMOS工艺实现该10 bit SAR ADC,以验证该改进型结构。结果表明,在1.8 V电源电压、780μW功耗、有电路噪声和电容失配情况下,该改进型SAR ADC得到了58.0 dB的信噪失真比(SNDR)。     

BP神经网络结合变量选择方法在牛奶蛋白质含量检测中的应用北大核心CSCD

牛奶中的蛋白质含量会影响牛奶的品质,利用高光谱图像的光谱特征信息研究对牛奶蛋白质含量预测的可行性。本文提出一种基于竞争性自适应重加权算法(competitive adaptive reweighted sampling, CARS)和连续投影算法(successive projections algorithm, SPA)结合多层前馈神经网络(back propagation, BP)的预测建模方法,实验以含有不同浓度蛋白质的牛奶为对象,利用可见光/近红外高光谱成像系统共采集到5种牛奶共计250组高光谱数据,通过实验对比选择采用标准化方法对获取到的吸收光谱预处理,然后采用CARS结合SPA筛选特征波长,得到18个特征波长,建立CARS-SPA-BP模型,经过试验,CARS-SPA-BP模型的训练集决定系数和测试集决定系数R;和R;分别达到0.971和0.968,训练集均方根误差(root mean square error of calibration,RMSEC)和测试集均方根误差(root mean square error of prediction,RMSEP)达到了0.033和0.034。研究发现,采用CARS结合SPA筛选的牛奶特征波长建立的多层前馈神经网络模型,其模型预测结果与全波长建模相比并没有明显降低,因此将CARS结合SPA用于波长筛选并且结合BP神经网络基本可以完成对牛奶蛋白质含量的预测。为验证CARS-SPA-BP模型的预测能力,在相同数据环境下,使用较为传统的偏最小二乘回归(partial least squares regression, PLSR)进行建模,实验结果表明,CARS-SPA-BP相较于PLSR,R;和RMSEP均有明显提升。研究表明,CARS-SPA-BP可充分利用牛奶光谱特征信息实现较高精度的牛奶蛋白质含量检测。     

A deterministic sequential maximin Latin hypercube design method using successive local enumeration for metamodel-based optimization

Space-filling and projective properties of design of computer experiments methods are desired features for metamodelling. To enable the production of high-quality sequential samples, this article presents a novel deterministic sequential maximin Latin hypercube design (LHD) method using successive local enumeration, notated as sequential-successive local enumeration (S-SLE). First, a mesh-mapping algorithm is proposed to map the positions of existing points into the new hyper-chessboard to ensure the projective property. According to the maximin distance criterion, new sequential samples are generated through successive local enumeration iterations to improve the space-filling uniformity. Through a number of comparative studies, several appealing merits of S-SLE are demonstrated: (1) S-SLE outperforms several existing LHD methods in terms of sequential sampling quality; (2) it is flexible and robust enough to produce high-quality multiple-stage sequential samples; and (3) the proposed method can improve the overall performance of sequential metamodel-based optimization algorithms. Thus, S-SLE is a promising sequential LHD method for metamodel-based optimization.     

一种基于分层的人类动作识别和定位算法研究

人类动作识别在视频自动分析、视频检索等领域获得广泛应用,是目前的研究热点。然而现有的动作识别方法重点关注视频的非静态部分而忽略大部分静态部分,从而影响了动作识别和定位的效果。本文提出一种新的分层空间-时间分段表示法,以分层方式实现部位和整个身体的多分辨率表示,可用于运动识别和定位。该算法分为3个步骤。第一步,首先对每个视频帧进行分层分段,以得到一组分段树,每颗树是身体分段树的候选。第二步,利用视频的轮廓、接合对象结构、全局前景色等信息对候选分段树进行修剪。第三步,在时域上对剩余分段层的每个分段进行前向和后向跟踪。我们以难度较大的UCF-Sports和HighFive数据集为实验对象,对本文方法进行性能评估,实验结果表明,本文方法的性能要优于当前最新运动检测算法性能,运动定位性能与当前最新算法相当。     

一类积分不等式的机器判定

将一类积分不等式转化为Tarski模型外的齐次对称多项式不等式,该类齐次对称多项式的次数是给定的,变元个数可以是任意多个,并且多项式的系数是与变元个数相关的变系数.这些特点与杨路等人最近提出的几个公开问题密切相关,是比较有代表性的一类齐次对称多项式.然后利用Timofte关于对称多项式不等式判定的降维方法,结合不等式证明软件BOTTEMA及差分代换方法,给出对应的一类Tarski模型外的齐次对称多项式不等式的机器判定算法,从而实现原积分不等式的机器判定.当给定的积分不等式及齐次对称多项式不等式不成立时,可给出具体不成立的数值反例.应用例子表明问题的广泛性及算法的有效性.     

Independent spanning trees vs. edge-disjoint spanning trees in locally twisted cubes

Fault-tolerant broadcasting and secure message distribution are important issues for numerous applications in networks. It is a common idea to design multiple spanning trees with a specific property in the underlying graph of a network to serve as a broadcasting scheme or a distribution protocol for receiving high levels of fault-tolerance and of security. A set of spanning trees in a graph is said to be edge-disjoint if these trees are rooted at the same node without sharing any common edge. Hsieh and Tu [S.-Y. Hsieh, C.-J. Tu, Constructing edge-disjoint spanning trees in locally twisted cubes, Theoretical Computer Science 410 (2009) 926-932] recently presented an algorithm for constructing n edge-disjoint spanning trees in an n-dimensional locally twisted cube. In this paper, we prove that indeed all spanning trees constructed by their algorithm are independent, i.e., any two spanning trees are rooted at the same node, say r, and for any other node v≠r, the two different paths from v to r, one path in each tree, are internally node-disjoint.