Let <em>x</em> and <em>y</em> be two positive real numbers with <em>x</em> < <em>y</em>. Consider a traveler, on the interval [0, <em>y</em>/2], departing...Let <em>x</em> and <em>y</em> be two positive real numbers with <em>x</em> < <em>y</em>. Consider a traveler, on the interval [0, <em>y</em>/2], departing from 0 and taking steps of length equal to <em>x</em>. Every time a step reaches an endpoint of the interval, the traveler rebounds off the endpoint in order to complete the step length. We show that the footprints of the traveler are the output of a full Euclidean algorithm for <em>x</em> and <em>y</em>, whenever <em>y</em>/<em>x</em> is a rational number. In the case that <em>y</em>/<em>x</em> is irrational, the algorithm is, theoretically, not finite;however, it is a new tool for the study of its irrationality.展开更多
The problem of determining the number of steps needed to find the greatest common divisor of two positive integers by Euclidean algorithm has been investigated in elementary number theory for decades. Different upper ...The problem of determining the number of steps needed to find the greatest common divisor of two positive integers by Euclidean algorithm has been investigated in elementary number theory for decades. Different upper bounds have been found for this problem. Here, we provide a sharp upper bound for a function which has a direct relation to the numbers whom the greatest common divisor we are trying to calculate. We mainly use some features of Fibonacci numbers as our tools.展开更多
A new problem of degree-constrained Euclidean Steiner minimal tree is discussed, which is quite useful in several fields. Although it is slightly different from the traditional degree-constrained minimal spanning tree...A new problem of degree-constrained Euclidean Steiner minimal tree is discussed, which is quite useful in several fields. Although it is slightly different from the traditional degree-constrained minimal spanning tree, it is also NP-hard. Two intelligent algorithms are proposed in an attempt to solve this difficult problem. Series of numerical examples are tested, which demonstrate that the algorithms also work well in practice.展开更多
为有效识别桥梁健康监测数据的异常,减少误预警、漏预警现象,保障桥梁监测数据的质量和有效性,针对大跨度斜拉桥长期监测数据的缺失、离群和漂移3类异常数据,提出基于时间序列压缩分割的监测数据异常识别算法。该算法将原始监测数据时...为有效识别桥梁健康监测数据的异常,减少误预警、漏预警现象,保障桥梁监测数据的质量和有效性,针对大跨度斜拉桥长期监测数据的缺失、离群和漂移3类异常数据,提出基于时间序列压缩分割的监测数据异常识别算法。该算法将原始监测数据时间序列通过基于序列重要点(Series Importance Point, SIP)的时间序列线性分段(Piecewise Linear Represent, PLR)算法(PLR_SIP)得到数条时间子序列;然后采用欧氏距离进行时间子序列的相似性分析,并基于改进的局部离群因子(Local Outlier Factor, LOF)算法计算每条时间子序列的局部离群因子;最后将其与设定的阈值相比较,从而识别出监测数据的异常。为验证该算法的准确性与工程实用性,对某公路大跨度斜拉桥健康监测数据进行异常识别。结果表明:采用PLR_SIP算法对原始时间序列压缩分割得到的时间子序列能够准确地反映原序列的变化趋势和范围;改进的LOF算法突破了传统LOF算法仅能识别离群值这类无持续时间异常的局限性,能够排除噪声的干扰,实现对离群、缺失和漂移3种异常的识别。该算法无需定义训练集,直接以原始监测数据作为算法的输入,同时能够自适应调整阈值参数,具有良好的可扩展性、实时性、准确性和高效性,适用于处理实时、大量的桥梁健康监测数据。展开更多
K-means聚类算法随机确定初始聚类数目,而且原始数据集中含有大量的冗余特征会导致聚类时精度降低,而布谷鸟搜索(CS)算法存在收敛速度慢和局部搜索能力弱等问题,为此提出一种基于自适应布谷鸟优化特征选择的K-means聚类算法(DCFSK)。首...K-means聚类算法随机确定初始聚类数目,而且原始数据集中含有大量的冗余特征会导致聚类时精度降低,而布谷鸟搜索(CS)算法存在收敛速度慢和局部搜索能力弱等问题,为此提出一种基于自适应布谷鸟优化特征选择的K-means聚类算法(DCFSK)。首先,为提升CS算法的搜索速度和精度,在莱维飞行阶段,设计了自适应步长因子;为调节CS算法全局搜索和局部搜索之间的平衡、加快CS算法的收敛,动态调整发现概率,进而提出改进的动态CS算法(IDCS),在IDCS的基础上构建了结合动态CS的特征选择算法(DCFS)。其次,为提升传统欧氏距离的计算精确度,设计同时考虑样本和特征对距离计算贡献程度的加权欧氏距离;为了确定最佳聚类数目的选取方法,依据改进的加权欧氏距离构造了加权簇内距离和簇间距离。最后,为克服传统K-means聚类目标函数仅考虑簇内的距离而未考虑簇间距离的缺陷,提出基于中位数的轮廓系数的目标函数,进而设计了DCFSK。实验结果表明,在10个基准测试函数上,IDCS的各项指标取得了较优的结果;相较于K-means、DBSCAN(Density-Based Spatial Clustering of Applications with Noise)等算法,在6个合成数据集与6个UCI数据集上,DCFSK的聚类效果最佳。展开更多
We establish polynomial complexity corrector algorithms for linear programming over bounds of the Mehrotra-type predictor- symmetric cones. We first slightly modify the maximum step size in the predictor step of the s...We establish polynomial complexity corrector algorithms for linear programming over bounds of the Mehrotra-type predictor- symmetric cones. We first slightly modify the maximum step size in the predictor step of the safeguard based Mehrotra-type algorithm for linear programming, that was proposed by Salahi et al. Then, using the machinery of Euclidean Jordan algebras, we extend the modified algorithm to symmetric cones. Based on the Nesterov-Todd direction, we obtain O（r log ε1） iteration complexity bound of this algorithm, where r is the rank of the Jordan algebras and ε is the required precision. We also present a new variant of Mehrotra-type algorithm using a new adaptive updating scheme of centering parameter and show that this algorithm enjoys the same order of complexity bound as the safeguard algorithm. We illustrate the numerical behaviour of the methods on some small examples.展开更多
Minimum Partial Euclidean Distance (MPED) based K-best algorithm is proposed to detect the best signal for MIMO (Multiple Input Multiple Output) detector. It is based on Breadth-first search method. The proposed algor...Minimum Partial Euclidean Distance (MPED) based K-best algorithm is proposed to detect the best signal for MIMO (Multiple Input Multiple Output) detector. It is based on Breadth-first search method. The proposed algorithm is independent of the number of transmitting/receiving antennas and constellation size. It provides a high throughput and reduced Bit Error Rate (BER) with the performance close to Maximum Likelihood Detection (MLD) method. The main innovations are the nodes that are expanded and visited based on MPED algorithm and it keeps track of finally selecting the best candidates at each cycle. It allows its complexity to scale linearly with the modulation order. Using Quadrature Amplitude Modulation (QAM) the complex domain input signals are modulated and are converted into wavelet packets and these packets are transmitted using Additive White Gaussian Noise (AWGN) channel. Then from the number of received signals the best signal is detected using MPED based K-best algorithm. It provides the exact best node solution with reduced complexity. The pipelined VLSI architecture is the best suited for implementation because the expansion and sorting cores are data driven. The proposed method is implemented targeting Xilinx Virtex 5 device for a 4 × 4, 64-QAM system and it achieves throughput of 1.1 Gbps. The results of resource utilization are tabulated and compared with the existing algorithms.展开更多
文摘Let <em>x</em> and <em>y</em> be two positive real numbers with <em>x</em> < <em>y</em>. Consider a traveler, on the interval [0, <em>y</em>/2], departing from 0 and taking steps of length equal to <em>x</em>. Every time a step reaches an endpoint of the interval, the traveler rebounds off the endpoint in order to complete the step length. We show that the footprints of the traveler are the output of a full Euclidean algorithm for <em>x</em> and <em>y</em>, whenever <em>y</em>/<em>x</em> is a rational number. In the case that <em>y</em>/<em>x</em> is irrational, the algorithm is, theoretically, not finite;however, it is a new tool for the study of its irrationality.
文摘The problem of determining the number of steps needed to find the greatest common divisor of two positive integers by Euclidean algorithm has been investigated in elementary number theory for decades. Different upper bounds have been found for this problem. Here, we provide a sharp upper bound for a function which has a direct relation to the numbers whom the greatest common divisor we are trying to calculate. We mainly use some features of Fibonacci numbers as our tools.
基金the National Natural Science Foundation of China (70471065)the Shanghai Leading Academic Discipline Project (T0502).
文摘A new problem of degree-constrained Euclidean Steiner minimal tree is discussed, which is quite useful in several fields. Although it is slightly different from the traditional degree-constrained minimal spanning tree, it is also NP-hard. Two intelligent algorithms are proposed in an attempt to solve this difficult problem. Series of numerical examples are tested, which demonstrate that the algorithms also work well in practice.
文摘为有效识别桥梁健康监测数据的异常,减少误预警、漏预警现象,保障桥梁监测数据的质量和有效性,针对大跨度斜拉桥长期监测数据的缺失、离群和漂移3类异常数据,提出基于时间序列压缩分割的监测数据异常识别算法。该算法将原始监测数据时间序列通过基于序列重要点(Series Importance Point, SIP)的时间序列线性分段(Piecewise Linear Represent, PLR)算法(PLR_SIP)得到数条时间子序列;然后采用欧氏距离进行时间子序列的相似性分析,并基于改进的局部离群因子(Local Outlier Factor, LOF)算法计算每条时间子序列的局部离群因子;最后将其与设定的阈值相比较,从而识别出监测数据的异常。为验证该算法的准确性与工程实用性,对某公路大跨度斜拉桥健康监测数据进行异常识别。结果表明:采用PLR_SIP算法对原始时间序列压缩分割得到的时间子序列能够准确地反映原序列的变化趋势和范围;改进的LOF算法突破了传统LOF算法仅能识别离群值这类无持续时间异常的局限性,能够排除噪声的干扰,实现对离群、缺失和漂移3种异常的识别。该算法无需定义训练集,直接以原始监测数据作为算法的输入,同时能够自适应调整阈值参数,具有良好的可扩展性、实时性、准确性和高效性,适用于处理实时、大量的桥梁健康监测数据。
文摘K-means聚类算法随机确定初始聚类数目,而且原始数据集中含有大量的冗余特征会导致聚类时精度降低,而布谷鸟搜索(CS)算法存在收敛速度慢和局部搜索能力弱等问题,为此提出一种基于自适应布谷鸟优化特征选择的K-means聚类算法(DCFSK)。首先,为提升CS算法的搜索速度和精度,在莱维飞行阶段,设计了自适应步长因子;为调节CS算法全局搜索和局部搜索之间的平衡、加快CS算法的收敛,动态调整发现概率,进而提出改进的动态CS算法(IDCS),在IDCS的基础上构建了结合动态CS的特征选择算法(DCFS)。其次,为提升传统欧氏距离的计算精确度,设计同时考虑样本和特征对距离计算贡献程度的加权欧氏距离;为了确定最佳聚类数目的选取方法,依据改进的加权欧氏距离构造了加权簇内距离和簇间距离。最后,为克服传统K-means聚类目标函数仅考虑簇内的距离而未考虑簇间距离的缺陷,提出基于中位数的轮廓系数的目标函数,进而设计了DCFSK。实验结果表明,在10个基准测试函数上,IDCS的各项指标取得了较优的结果;相较于K-means、DBSCAN(Density-Based Spatial Clustering of Applications with Noise)等算法,在6个合成数据集与6个UCI数据集上,DCFSK的聚类效果最佳。
基金Supported by the National Natural Science Foundation of China(11471102,61301229)Supported by the Natural Science Foundation of Henan University of Science and Technology(2014QN039)
文摘We establish polynomial complexity corrector algorithms for linear programming over bounds of the Mehrotra-type predictor- symmetric cones. We first slightly modify the maximum step size in the predictor step of the safeguard based Mehrotra-type algorithm for linear programming, that was proposed by Salahi et al. Then, using the machinery of Euclidean Jordan algebras, we extend the modified algorithm to symmetric cones. Based on the Nesterov-Todd direction, we obtain O（r log ε1） iteration complexity bound of this algorithm, where r is the rank of the Jordan algebras and ε is the required precision. We also present a new variant of Mehrotra-type algorithm using a new adaptive updating scheme of centering parameter and show that this algorithm enjoys the same order of complexity bound as the safeguard algorithm. We illustrate the numerical behaviour of the methods on some small examples.
文摘Minimum Partial Euclidean Distance (MPED) based K-best algorithm is proposed to detect the best signal for MIMO (Multiple Input Multiple Output) detector. It is based on Breadth-first search method. The proposed algorithm is independent of the number of transmitting/receiving antennas and constellation size. It provides a high throughput and reduced Bit Error Rate (BER) with the performance close to Maximum Likelihood Detection (MLD) method. The main innovations are the nodes that are expanded and visited based on MPED algorithm and it keeps track of finally selecting the best candidates at each cycle. It allows its complexity to scale linearly with the modulation order. Using Quadrature Amplitude Modulation (QAM) the complex domain input signals are modulated and are converted into wavelet packets and these packets are transmitted using Additive White Gaussian Noise (AWGN) channel. Then from the number of received signals the best signal is detected using MPED based K-best algorithm. It provides the exact best node solution with reduced complexity. The pipelined VLSI architecture is the best suited for implementation because the expansion and sorting cores are data driven. The proposed method is implemented targeting Xilinx Virtex 5 device for a 4 × 4, 64-QAM system and it achieves throughput of 1.1 Gbps. The results of resource utilization are tabulated and compared with the existing algorithms.
