An Optimal Parallel Algorithm for the Knapsack Problem Based on EREW

IntroductionGivenn positiveintegersW =(w1,w2 ,… ,wn)andapositiveintegerM ,theknapsack problem (alsocalledthesubsetsum problembysomeauthors)isthedecisionproblemoffindingasetI {1 ,2 ,… ,n},suchthat∑i∈I=M ,i∈I .ThisproblemwasprovedtobeNP complete[1] ;i     

Discretization Algorithm Based on Particle Swarm Optimization and Its Application in Attributes Reduction for Fault Data

In order to increase the fault diagnosis efficiency and make the fault data mining be realized, the decision table containing numerical attributes must be discretized for further calculations. The discernibility matrix-based reduction method depends on whether the numerical attributes can be properly discretized or not. So a discretization algorithm based on particle swarm optimization (PSO) is proposed. Moreover, hybrid weights are adopted in the process of particles evolution. Comparative calculations for certain equipment are completed to demonstrate the effectiveness of the proposed algorithm. The results indicate that the proposed algorithm has better performance than other popular algorithms such as class-attribute interdependence maximization (CAIM) discretization method and entropy-based discretization method.     

应用形态学方法提高SAR目标检测中的聚类效果

Lincoln实验室提出的SAR(synthetic aperture radar)ATR(automatic target recognition)算法由于其经典性而被广泛采用,该算法为三级结构模式,处于其中Prescreener级和Discriminator级之间的聚类算法对于检测算法整体性能有重要的影响,文中介绍了SAR ATR算法采用的常规聚类算法,分析了常规算法在聚类过程中存在的杂波干扰问题,针对问题在聚类前引入形态学操作方法,将待聚类图像中包含的孤立点删除而只保留团状分布的样本,从而消除了杂波点对聚类的干扰,基于实际SAR图像的聚类结果验证了应用形态学方法对提高聚类效果的有效性.     

大数快速模幂算法的硬件设计

将快速模幂算法、快速模乘算法和快速加法组合,提出了一种大数快速RSA算法,并利用该算法给出了一个RSA公开密钥的加解密硬件实现方案.首先采用m ary方法,减少模乘运算次数;其次采用Montgomery改进算法,减少模加运算次数;最后,采用高速加法器并调整加法与乘法的结构使其同时运行,以节约资源.对于1024位操作数,在100MHz时钟频率下,加密速率约为390kbit/s.     

Improved Parallel Three-List Algorithm for the Knapsack Problem without Memory Conflicts

Based on the two-list algorithm and the parallel three-list algorithm, an improved parallel three-list algorithm for knapsack problem is proposed, in which the method of divide and conquer, and parallel merging without memory conflicts are adopted. To find a solution for the n-element knapsack problem, the proposed algorithm needs O（2^3n/8） time when O（2^3n/8） shared memory units and O（2^n/4） processors are available. The comparisons between the proposed algorithm and 10 existing algorithms show that the improved parallel three-fist algorithm is the first exclusive-read exclusive-write （EREW） parallel algorithm that can solve the knapsack instances in less than O（2^n/2） time when the available hardware resource is smaller than O（2^n/2） , and hence is an improved result over the past researches.     

非平稳信号自适应最大信噪比盲源分离方法

为了提高时变非平稳信号的盲源分离效果,提出了自适应最大信噪比盲源分离新方法.该方法以信噪比函数作为代价函数,并基于改进的多项式系数自回归模型,进行最优滑窗长度的自适应估计.仿真计算表明,FastICA算法需要预设源信号的概率密度函数,以选择适宜的非线性函数近似估计源信号的非高斯性,当假设的概率密度函数与实际不符时无法正确分离源信号;累积量算法在信源的峰度相同时无法正确分离源信号.新方法与经典的FastICA算法和基于累积量的盲源分离算法比较结果表明,对于经典的FastICA算法、累积量算法无法正确分离的时变非平稳信号,新方法能够有效地进行盲源分离,分离结果不受源信号的概率分布、信源的峰度等统计因素影响.      

Research on a Task Planning Method for Multi-Ship Cooperative Driving

A new method for a cooperative multi-task allocation problem(CMTAP) is proposed in this paper,taking into account the multi-ship, multi-target, multi-task and multi-constraint characteristics in a multi-ship cooperative driving(MCD) system. On the basis of the general CMTAP model, an MCD task assignment model is established. Furthermore, a genetic ant colony hybrid algorithm(GACHA) is proposed for this model using constraints, including timing constraints, multi-ship collaboration constraints and ship capacity constraints. This algorithm uses a genetic algorithm(GA) based on a task sequence, while the crossover and mutation operators are based on similar tasks. In order to reduce the dependence of the GA on the initial population, an ant colony algorithm(ACA) is used to produce the initial population. In order to meet the environmental constraints of ship navigation, the results of the task allocation and path planning are combined to generate an MCD task planning scheme. The results of a simulated experiment using simulated data show that the proposed method can make the assignment more optimized on the basis of satisfying the task assignment constraints and the ship navigation environment constraints. Moreover, the experimental results using real data also indicate that the proposed method can find the optimal solution rapidly, and thus improve the task allocation efficiency.     

Genetic Algorithm Based Tikhonov Regularization Method for Displacement Reconstruction

In this paper,a genetic algorithm based Tikhonov regularization method is proposed for determination of globally optimal regularization factor in displacement reconstruction.Optimization mathematic models are built by using the generalized cross-validation(GCV)criterion,L-curve criterion and Engl's error minimization(EEM)criterion as the objective functions to prevent the regularization factor sinking into the locally optimal solution.The validity of the proposed algorithm is demonstrated through a numerical study of the frame structure model.Additionally,the influence of the noise level and the number of sampling points on the optimal regularization factor is analyzed.The results show that the proposed algorithm improves the robustness of the algorithm effectively,and reconstructs the displacement accurately.     

基于GA-PSO混合优化的BPNN车速预测方法

BP神经网络(BPNN)已经用于车速预测方面的研究.针对BPNN不同的初始权值和阈值会影响车速预测精度的问题,提出一种基于GA-PSO混合优化的BPNN车速预测方法.以北工大西门到百葛桥为研究路径,构建基于BPNN的车速预测模型;将遗传算法(GA)和粒子群算法(PSO)的寻优过程进行融合,通过逐次迭代取最优的方式确定BPNN的最优初始权值和阈值,以此设计基于GA-PSO混合优化的BPNN车速预测方法.最后,以所选路径为对象,利用基于GA-BPNN的预测法、基于PSO-BPNN的预测法,以及提出的方法对车速进行了实验预测.结果表明,相较于前两种车速预测改进方法,本文方法的平均车速预测误差分别降低了37.1%和24.1%,有效地提高了车速的预测精度.     

高阶DLMS型方法求解线性方程组

结合动态系统参数识别算法（LMS）和高阶两参数并行Jacobi型算法的优点，得到一种称之为高阶DLMS方法．该方法避免传统迭代方法求解线性方程组时使用逆矩阵参与迭代矩阵的构造，避免了矩阵求逆；同时对传统线性方程组要求系数矩阵必须为方阵加以推广，具有适用范围广、计算量少等优点．同时并讨论了算法的收敛性和最优参数的选取．     

IMPLEMENTATION OF GRADIENT-BASED ESTIMATION OF HMM PARAMETERS

IntroductionIn Hidden Markov Model ( HMM) - basedspeech recognition systems,it is very importanttoset the parameters of HMMs correctly.Conven-tional training algorithms such as Baum- Welch al-gorithm,are based on the criterion of maximumlikelihood( ML) .The strength of Baum- Welch al-gorithm lies in its fast convergence andmonotonous improvement[1] . For other criteriasuch as maximum mutual information,however,such an algorithm does not exist.In this case,acommon resort is a gradient- b…     

第Ⅰ类双边装配线平衡问题的改进蚁群算法

为克服传统算法求解大规模双边装配线平衡问题计算时间长、性能不稳定的缺陷,针对第Ⅰ类双边装配线平衡问题,应用综合信息素搜索规则与全局信息素更新规则,提出了一种先产生任务排列序列、后按启发式分配规则产生可行解的蚁群算法,可有效脱离陷入局部最优解.用改进蚁群算法对30个不同规模的问题进行求解,并与标准蚁群算法和禁忌搜索算法进行了对比.结果表明:改进蚁群算法求出29个最优解,比普通蚁群算法、禁忌搜索算法分别能多求得6个和3个最优解;应用于汽车双边装配线算例,在保持平衡效率的条件下,改进蚁群算法计算时间为21.01 s,比普通蚁群算法减少了9.14 s,计算效率提高了30.3%.      

An Iterative Algorithm for Computed Tomography Image Reconstruction from Limited-Angle Projections

In application of tomography imaging, limited-angle problem is a quite practical and important issue.In this paper, an iterative reprojection-reconstruction(IRR) algorithm using a modified Papoulis-Gerchberg(PG)iterative scheme is developed for reconstruction from limited-angle projections which contain noise. The proposed algorithm has two iterative update processes, one is the extrapolation of unknown data, and the other is the modification of the known noisy observation data. And the algorithm introduces scaling factors to control the two processes, respectively. The convergence of the algorithm is guaranteed, and the method of choosing the scaling factors is given with energy constraints. The simulation result demonstrates our conclusions and indicates that the algorithm proposed in this paper can obviously improve the reconstruction quality.     

测量控制网优化设计中建模与求解的一般方法

本文在目前国际公认的求解带约束非线性规划最为有效的方法之一－逐步二次规划（ＳＱＰ）法的基础上，结合目标规划原理，导出一套适用于求解一般的多目标优化模型的逐步线性目标规划（ＳＬＧＰ）法，基于ＳＱＰ法和ＳＬＧＰ法的先进性，又提出解决一般测量控制网优化设计问题的总体思路和方法，并给出了新的建模方法。     

基于语义相似度的话题关联检测方法

为有效识别任意两篇报道的相似性,提出了一种基于语义相似度的话题关联检测算法.该算法首先通过计算特征词之间的相对熵作为两篇报道中特征词之间的语义相似度;其次,通过计算平均语义相似度获得特征词和报道之间的关联度;最后,结合特征词在语料库中的TF-IF(term frequency-inverse document frequency)权重计算两篇报道之间的关联度,实现报道之间的关联度检测.本文提出的方法与现有的向量空间模型方法和仅依赖于平均点互信息的方法进行了比较,并通过TDT4中文语料进行测评,结果表明,基于语义相似度的关联检测方法能够更好地利用文本的语境信息,提高了现有检测系统的性能,其最小DET(detection error tradeoff)代价降低了3%.      

A rate-distortion based quantization level adjustment algorithm in block-based video compression

In this paper, a rate-distortion based quantization level adjustment (RDQLA) algorithm is presented. Based on the rate-distortion criterion, the quantization level adjustment algorithm effectively improves coding efficiency by adaptively optimizing quantization levels of the signals near the boundaries of quantization cells and adjusting quantization levels per block. In addition, it has no overhead and is fully compatible with the existing compression standards. The proposed algorithm can be applied in any block based image and video coding method. In particular, the algorithm has been verified on the platform of H.264. Experimental results show that the proposed algorithm improves objective and subjective performances substantially. It is shown that the proposed algorithm has a gain of several dB comparing with the newest H.264 standard for high bit rates. Foundation item: the Special Foundation of Outstanding Young Teacher of Shanghai     

TDOA Passive Location Based on Cuckoo Search Algorithm

This paper formulates a new framework to estimate the target position by adopting cuckoo search(CS)positioning algorithm. Addressing the nonlinear optimization problem is a crucial spot in the location system of time difference of arrival(TDOA). With the application of the Levy flight mechanism, the preferential selection mechanism and the elimination mechanism, the proposed approach prevents positioning results from falling into local optimum. These intelligent mechanisms are useful to ensure the population diversity and improve the convergence speed. Simulation results demonstrate that the cuckoo localization algorithm has higher locating precision and better performance than the conventional methods. Compared with particle swarm optimization(PSO) algorithm and Newton iteration algorithm, the proposed method can obtain the Cram′er-Rao lower bound(CRLB) and quickly achieve the global optimal solutions.     

基于阈值和蚁群算法结合的聚类方法

为了改善聚类分析的质量，提出了一种基于阈值和蚁群算法相结合的聚类方法．按此方法，首先由基于阈值的聚类算法进行聚类，生成聚类中心，聚类个数也随之初步确定；然后将蚁群算法的转移概率引入K-平均算法，对上述聚类结果进行二次优化．实验表明，与尽平均算法等相比，该聚类方法的F-测度值（F-measure）更高．     

空间数据库中连续可视反向最近邻查询

为了解决障碍物环境中连续反向最近邻的查询问题,考虑到障碍物的存在,将可视性加到连续反向最近邻查询中,提出了一种新的连续反向最近邻查询的变体——连续可视反向最近邻查询.给出了线段可视性判断方法和相应的剪枝策略,提出了连续可视反向最近邻查询算法.该算法通过过滤步骤得到一个候选集,通过精炼步骤去掉错误的候选,通过分裂步骤找到查询结果.实验结果表明,该算法的执行时间与查询线段的长度呈线性关系增长,查询效率较高.     

基于GARCH的短时风速预测方法

为提高高速列车运行的安全性,基于线性递归的差分自回归移动平均模型(auto-regressive integrated moving average, ARIMA)和非线性递归的广义自回归条件异方差模型(generalized auto-regressive conditionally heteroscedastic, GARCH),提出一种组合模型ARIMA-GARCH进行高速铁路强风风速的短时预测.首先对数据的非平稳性进行预处理,以降低数据非平稳性对所提模型的影响;其次建立线性递归的ARIMA模型对数据进行分析和预测;最后,引入非线性递归的GARCH模型对数据进行分析和预测.基于现场测量的样本仿真分析表明:相比原始数据,ARIMA-GARCH模型的预测精度较高且随着预测步长的增加,平均绝对误差仅从0.836 m/s增加到1.272 m/s;ARIMA-GARCH模型考虑了异方差这一非线性特性,其预测精度明显好于线性的ARIMA模型,其中超前6步预测的平均绝对误差精度提高11.54%.