比例风险模型下参数极大似然估计的自适应优化算法及其改进算法

自适应优化算法可避免很多常用数值算法遭遇的困难,例如:高维矩阵求逆问题,初值选取的问题和算法的收敛问题等等.因此,自适应优化算法得到了迅速的发展和广泛的应用,本文研究了比例风险模型下的自适应优化算法.首先利用三种自适应优化算法-Adam算法、RMSprop算法、Adagrad算法求解比例风险模型下的参数估计数值解问题,获得了自适应算法的计算优良性.然后,推广了比例风险模型下的Adam算法的研究,发展了一种改进的Adam算法,进一步提高了算法的计算速度并展现了其计算优势.     

求解全局优化问题的改进蝙蝠算法[英文]

蝙蝠算法(BA)是一类基于试探技巧的群智能优化算法,该算法已被广泛用于诸多领域问题的求解.本文提出一个改进的蝙蝠算法NIBA.在算法中,为了加强蝙蝠算法的局部和全局搜索能力,提出了三个改进策略.首先,为了改进蝙蝠的局部搜索能力,在当前最优解处给出了一个新的搜索方程.其次,为了改进算法的全局搜索能力,平衡算法的开发能力和探索能力,算法吸收并改进了和声搜索机制.最后,为了进一步提高NIBA算法的搜索能力,在当前最优解处,算法采用了混沌搜索机制.为了验证算法的性能,针对18个标准测试函数进行了数值实验.与其它算法的比较结果显示,NIBA算法具有更好的稳定性,且效率更高.     

学习算法的稳定性与泛化(Ⅱ):有界差分稳定框架

根据有界差分条件,提出了学习算法的有界差分稳定框架.依据新框架,研究了机器学习阈值选择算法,再生核Hilbert空间中的正则化学习算法,Ranking学习算法和Bagging算法,证明了对应学习算法的有界差分稳定性.所获结果断言了这些算法均具有有界差分稳定性,从而为这些算法的应用奠定了理论基础.     

一种古代的中国算法:盈不足术与牛顿迭代算法的比较

详细讨论了大约在公元前二世纪广泛流行的一种中国算法,这种算法在西方被称作为双假设法。强调指出双假设法是中国算法的一种译版。首次给出了中国算法与牛顿迭代算法之间的联系,如果引入了导数的概念,中国算法可以非常方便地转化为牛顿迭代算法。提出了一种改进的中国算法,并给出中国算法在非线性振动方程中的应用。     

GA-BP嵌套算法的理论及应用

分析了BP算法、遗传算法以及GA-BP-APARTING算法的特点,提出了GA-BP-NESTING算法.在人工神经网络的在线学习和离线学习方式下,分别对BP算法、GA算法、GA-BP-APARTING算法和GA-BP-NESTING算法进行了比较研究,研究发现:第一,网络初始权值的赋值对人工神经网络训练影响很大;第二,离线学习方式下GA-BP-NESTING算法效果最佳.     

整数扩展欧几里得矩阵序列的选择项算法的修正

Wang和Pan提出了一个计算整数扩展欧几里得矩阵序列的选择项的算法,并把此算法应用于模有理数重构问题和数值有理数重构问题.这个算法仅消耗接近线性的时间复杂度,与目前已知的整数gcd算法的最佳时间复杂度相一致,而整数gcd算法只是此算法的一个特殊情形.分析了这个算法,指出了算法中由于考虑的不够全面而存在的错误,补充了矩阵序列性质的理论部分,并修正这个算法.     

利用模拟退火遗传算法实现图像阈值分割

本文提出了一种利用模拟退火算法和遗传算法相结合的图像阈值分割算法,试验结果表明该算法增强了算法的全局收敛性,加快了算法的收敛速度,提高了图像阈值分割的效率.     

矩阵填充的硬阈值修正算法

提出了使用硬阈值进行矩阵填充的修正算法.算法通过对迭代矩阵进行对角修正来完成矩阵填充,并给出了算法的收敛性分析.最后通过数值实验比较了修正算法与硬阈值算法填充的数值结果,显示出了新算法的优越性.     

蚂蚁算法和小生境遗传算法的融合

蚂蚁算法是一种新型的模拟进化算法,也是一种随机型智能搜索算法.较为系统的总结了算法的基本理论,分析了其基本算法解决TSP问题的模型,针对蚂蚁算法易出现停滞的缺点,把小生境遗传算法和蚂蚁算法融合,仿真比较实验结果表明优于基本蚂蚁算法.     

一类凸优化的加速混合下降算法

凸优化问题的混合下降算法利用近似条件的已知信息和随机数扩张预测校正步得到了一组下降方向.而前向加速收缩算法利用高斯赛德尔迭代算法的技术,结合邻近点算法和近似邻近点算法的思想,构造了富有扩张性的下降方向.本文借鉴混合下降算法和前向加速收缩算法的思想,利用已有近似规则信息改善了混合下降算法的下降方向,得到了一类凸优化问题的加速混合下降算法.随后利用Markov不等式、凸函数性质和投影的基本性质等,实现了算法的依概率收敛证明.一系列数值试验表明了加速混合下降算法的有效性和效率性.     

An efficient and numerically correct algorithm for the 2D convex hull problem

An efficient and numerically correct program called FastHull for computing the convex hulls of finite point sets in the plane is presented. It is based on the Akl-Toussaint algorithm and the MergeHull algorithm. Numerical correctness of the FastHull procedure is ensured by using special routines for interval arithmetic and multiple precision arithmetic. The FastHull algorithm guaranteesO(N logN) running time in the worst case and has linear time performance for many kinds of input patterns. It appears that the FastHull algorithm runs faster than any currently known 2D convex hull algorithm for many input point patterns.     

A note on parallel depth first search

The subject of this note is the parallel algorithm for depth first searching of a directed acyclic graph by Ghosh and Bhattacharjee. It is pointed out that their algorithm does not always work. A counter example is given. This paper also states the necessary and sufficient condition for the algorithm to fail, or to work correctly.     

Nonlinear Smoothing and the EM Algorithm for Positive Integral Equations of the First Kind

We study a modification of the EMS algorithm in which each step of the EMS algorithm is preceded by a nonlinear smoothing step of the form , where S is the smoothing operator of the EMS algorithm. In the context of positive integral equations (à la positron emission tomography) the resulting algorithm is related to a convex minimization problem which always admits a unique smooth solution, in contrast to the unmodified maximum likelihood setup. The new algorithm has slightly stronger monotonicity properties than the original EM algorithm. This suggests that the modified EMS algorithm is actually an EM algorithm for the modified problem. The existence of a smooth solution to the modified maximum likelihood problem and the monotonicity together imply the strong convergence of the new algorithm. We also present some simulation results for the integral equation of stereology, which suggests that the new algorithm behaves roughly like the EMS algorithm. Accepted 1 April 1997     

文献优选统计模型及其应用

本文给出了一个复完全有向图顶点排序标法，并利用该算法建立了具有实际应用价值的文献优选统计模型。     

Corrections to Lee's visibility polygon algorithm

We present a modification and extension of the (linear time) visibility polygon algorithm of Lee. The algorithm computes the visibility polygon of a simple polygon from a viewpoint that is either interior to the polygon, or in its blocked exterior (the cases of viewpoints on the boundary or in the free exterior being simple extensions of the interior case). We show by example that the original algorithm by Lee, and a more complex algorithm by El Gindy and Avis, can fail for polygons that wind sufficiently. We present a second version of the algorithm, which does not extend to the blocked exterior case.This work was partially supported by grants from the Central Research Fund of the University of Alberta and the Natural Sciences and Engineering Research Council of Canada.     

Minimal perfect hashing in polynomial time

We present a universally applicable algorithm for generating minimal perfect hashing functions. The method has (worst case) polynomial time complexity in units of bit operations. An adjunct algorithm for reducing parameter magnitudes in the generated hash functions is given. This probabilistic method makes hash function parameter magnitudes independent of argument (input key) magnitudes.     

A note on optimal multiway split trees

Split trees are suitable data structures for storing records with different access frequencies. Under assumption that the access frequencies are all distinct, Huang has proposed anO(n ⁴ logm) time algorithm to construct an (m+1)-way split tree for a set ofn keys. In this paper, we generalize Huang's algorithm to deal with the case of non-distinct access frequencies. The technique used in the generalized algorithm is a generalization of Hesteret al.'s, where the binary case was considered. The generalized algorithm runs inO(n ⁵ logm) time.     

Formal neighbourhoods, combinatory Böhm trees, and untyped normalization by evaluation

We prove the correctness of an algorithm for normalizing untyped combinator terms by evaluation. The algorithm is written in the functional programming language Haskell, and we prove that it lazily computes the combinatory Böhm tree of the term. The notion of combinatory Böhm tree is analogous to the usual notion of Böhm tree for the untyped lambda calculus. It is defined operationally by repeated head reduction of terms to head normal forms. We use formal neighbourhoods to characterize finite, partial information about data, and define a Böhm tree as a filter of such formal neighbourhoods. We also define formal topology style denotational semantics of a fragment of Haskell following Martin-Löf, and let each closed program denote a filter of formal neighbourhoods. We prove that the denotation of the output of our algorithm is the Böhm tree of the input term. The key construction in the proof is a “glueing” relation between terms and semantic neighbourhoods which is defined by induction on the latter. This relation is related to the glueing relation which was earlier used for proving the correctness of normalization by evaluation algorithm for typed combinatory logic.     

An optimal time algorithm for finding a maximum weight independent set in a tree

The maximum weight independent set problem for a general graph is NP-hard. But for some special classes of graphs, polynomial time algorithms do exist for solving it. Based on the divide-and-conquer strategy, Pawagi has presented anO(|V|log|V|) time algorithm for solving this problem on a tree. In this paper, we propose anO(|V|) time algorithm to improve Pawagi's result. The proposed algorithm is based on the dynamic programming strategy and is time optimal within a constant factor.     

Automatically replacing indices into parallel arrays with pointers to records

In older languages lists, trees and graphs are represented with sets of arrays where indices of elements correspond to pointers to the nodes of the data structure. We present an algorithm that replaces such arrays with objects allocated dynamically from the heap, and indices with true pointers. Generated pointers are strongly typed and elements of logically related arrays are combined into records. The algorithm is potentially useful, especially in automatic translation between high-level programming languages.