Additive Scaling and the DIRECT Algorithm

In this paper we show that the convergence behavior of the DIviding RECTangles (DIRECT) algorithm is sensitive to additive scaling of the objective function. We illustrate this problem with a computation and show how the algorithm can be modified to eliminate this sensitivity.     

Design and implementation of a massively parallel version of DIRECT

This paper describes several massively parallel implementations for a global search algorithm DIRECT. Two parallel schemes take different approaches to address DIRECT’s design challenges imposed by memory requirements and data dependency. Three design aspects in topology, data structures, and task allocation are compared in detail. The goal is to analytically investigate the strengths and weaknesses of these parallel schemes, identify several key sources of inefficiency, and experimentally evaluate a number of improvements in the latest parallel DIRECT implementation. The performance studies demonstrate improved data structure efficiency and load balancing on a 2200 processor cluster.     

Dynamic Data Structures for a Direct Search Algorithm

The DIRECT (DIviding RECTangles) algorithm of Jones, Perttunen, and Stuckman (Journal of Optimization Theory and Applications, vol. 79, no. 1, pp. 157–181, 1993), a variant of Lipschitzian methods for bound constrained global optimization, has proved effective even in higher dimensions. However, the performance of a DIRECT implementation in real applications depends on the characteristics of the objective function, the problem dimension, and the desired solution accuracy. Implementations with static data structures often fail in practice, since it is difficult to predict memory resource requirements in advance. This is especially critical in multidisciplinary engineering design applications, where the DIRECT optimization is just one small component of a much larger computation, and any component failure aborts the entire design process. To make the DIRECT global optimization algorithm efficient and robust on large-scale, multidisciplinary engineering problems, a set of dynamic data structures is proposed here to balance the memory requirements with execution time, while simultaneously adapting to arbitrary problem size. The focus of this paper is on design issues of the dynamic data structures, and related memory management strategies. Numerical computing techniques and modifications of Jones' original DIRECT algorithm in terms of stopping rules and box selection rules are also explored. Performance studies are done for synthetic test problems with multiple local optima. Results for application to a site-specific system simulator for wireless communications systems (S ⁴ W) are also presented to demonstrate the effectiveness of the proposed dynamic data structures for an implementation of DIRECT.     

模糊聚类分析的新算法

提出了一种模糊聚类分析的新算法——追踪法 ,解决了以往模糊聚类分析计算量过大以及难于编程实现的问题 .该方法尤其适用于大规模数据的模糊聚类分析 ,对于模糊聚类分析的推广使用有重要意义 .     

一种基于匈牙利算法的二次分配问题求解方法

二次分配问题(Quadratic assignment problem,QAP)属于NP-hard组合优化难题.二次分配问题的线性化及下界计算方法,是求解二次分配问题的重要途径.以Frieze-Yadegar线性化模型和Gilmore-Lawler下界为基础,详细论述了二次分配问题线性化模型的结构特征,并分析了Gilmore-Lawler下界值往往远离目标函数最优值的原因.在此基础上,提出一种基于匈牙利算法的二次分配问题对偶上升下界求解法.通过求解QAPLIB中的部分实例,说明了方法的有效和可行性.     

一种基于区间数多指标信息的FCM聚类算法

针对一类具有不确定性区间数多指标信息的聚类分析问题，依据传统的基于数值信息的FCM聚类算法的思路，提出了一种新的聚类分析算法。章首先描述了具有区间数多指标信息的聚类分析问题；其次给出了基于区间数多指标信息的关于最优划分和最优聚类中心确定的两个定理；然后给出了基于区间数多指标信息的FCM聚类算法的计算步骤。该算法的特点是聚类中心的表现形式为精确的数值，给出的两个定理说明了该聚类算法的收敛性。最后，通过给出一个算例说明了本给出的聚类算法。     

A Fast and Stable Updating Algorithm for Bivariate Nonparametric Curve Estimation

Abstract

An updating algorithm for bivariate local linear regression is proposed. Thereby, we assume a rectangular design and a polynomial kernel constrained to rectangular support as weight function. Results of univariate regression estimators are extended to the bivariate setting. The updates are performed in a way that most of the well-known numerical instabilities of a naive update implementation can be avoided. Some simulation results illustrate the properties of several algorithms with respect to computing time and numerical stability.     

区间模糊ISODATA动态聚类算法

目前模糊技术已经应用于许多智能系统,如模糊关系与模糊聚类.聚类是数据挖掘的重要任务,它将数据对像分成多个聚类,在同一个聚类中,对象的属性特征之间具有较高的相似度,有很大研究及应用价值.结合数据库中的挖掘技术,对属性特征为区间数的多属性决策问题,提出了一种基于区间数隶属度的区间模糊ISODATA动态聚类方法.     

一种嵌入思维进化的新的进化算法

对于运筹学问题学中的函数优化问题,本文提出一种嵌入思维进化的新的进化算法,将思维进化计算(Mind Evolutionary Computation,MEC)的"趋同"和"异化"操作加入到进化算法中,充分利用其特有记忆机制、定向机制和探测与开采功能之间的协调机制的好性能,并加入K-meams聚类算法,保证群体多样性。最后,数值模拟验证了新算法的有效性。     

非线性约束优化问题的一个修正 Lagrangian 算法

基于一个含有控制参数的修正Lagrangian函数,该文建立了一个求解非线性约束优化问题的修正Lagrangian算法.在一些适当的条件下,证明了控制参数存在一个阀值,当控制参数小于这一阀值时,由这一算法产生的序列解局部收敛于问题的Kuhn-Tucker点,并且建立了解的误差上界.最后给出一些约束优化问题的数值结果.     

土壤分类的模糊集成算法与应用

土壤是一个多性状的连续体,其分类的首选方法是模糊聚类分析.但是模糊聚类分析中现有的基于模糊等价关系的动态聚类法和模糊c-均值法各有利弊,采用其中一种方法聚类肯定存在不足.为此集成两种聚类方法的优点,避其缺点,提出了用基于模糊等价关系的动态聚类方法和方差分析方法确定聚类数目和初始聚类中心,再用模糊c-均值法决定最终分类结果的集成算法,并将其应用到松花江流域土壤分类中,得到了较为切合实际的分类结果.     

基于FCM算法的小脑基因模糊聚类分析

探讨基因表达数据的聚类分析方法,结合一种聚类结果的评判准则,应用于胎儿小脑基因表达数据,得到了最优的聚类结果,并做出了生物学解释.利用Matlab软件进行了仿真,利用模糊聚类Xie-Beni指数得到了最优聚类数,并把每一类对应的基因标号输出到txt文件,最后进行生物学解释.得到的小脑基因最优聚类数为3类,与生物学意义比较吻合,各类中的基因功能接近.基于FCM算法的基因模糊聚类是有效的,结果具有一定生物学意义,能对生物学基因聚类有一定指导作用.     

Cluster Analysis for Large Datasets: An Effective Algorithm for Maximizing the Mixture Likelihood

Abstract

The primary model for cluster analysis is the latent class model. This model yields the mixture likelihood. Due to numerous local maxima, the success of the EM algorithm in maximizing the mixture likelihood depends on the initial starting point of the algorithm. In this article, good starting points for the EM algorithm are obtained by applying classification methods to randomly selected subsamples of the data. The performance of the resulting two-step algorithm, classification followed by EM, is compared to, and found superior to, the baseline algorithm of EM started from a random partition of the data. Though the algorithm is not complicated, comparing it to the baseline algorithm and assessing its performance with several classification methods is nontrivial. The strategy employed for comparing the algorithms is to identify canonical forms for the easiest and most difficult datasets to cluster within a large collection of cluster datasets and then to compare the performance of the two algorithms on these datasets. This has led to the discovery that, in the case of three homogeneous clusters, the most difficult datasets to cluster are those in which the clusters are arranged on a line and the easiest are those in which the clusters are arranged on an equilateral triangle. The performance of the two-step algorithm is assessed using several classification methods and is shown to be able to cluster large, difficult datasets consisting of three highly overlapping clusters arranged on a line with 10,000 observations and 8 variables.     

基于加权相似性的BIRCH聚类算法

BIRCH方法是一个集成的层次聚类方法.它克服了凝聚层次聚类方法所面临的两个难点:可伸缩性和不能撤销前一步工作的问题.基于BIRCH聚类的多阶段聚类算法思想,结合基于权重的欧式距离度量和基于划分的K-means算法,提出了一种基于加权相似性的BIRCH聚类方法,并将方法应用在时间序列的气象数据分析中.     

Self-Adaptive Genetic Algorithm for Clustering

Clustering is a hard combinatorial problem which has many applications in science and practice. Genetic algorithms (GAs) have turned out to be very effective in solving the clustering problem. However, GAs have many parameters, the optimal selection of which depends on the problem instance. We introduce a new self-adaptive GA that finds the parameter setup on-line during the execution of the algorithm. In this way, the algorithm is able to find the most suitable combination of the available components. The method is robust and achieves results comparable to or better than a carefully fine-tuned non-adaptive GA.     

A DIRECT SEARCH FRAME-BASED CONJUGATE GRADIENTS METHOD

A derivative-free frame-based conjugate gradients algorithm is presented.Convergenceis shown for C~1 functions,and this is verified in numerical trials.The algorithm is tested ona variety of low dimensional problems,some of which are ill-conditioned,and is also testedon problems of high dimension.Numerical results show that the algorithm is effectiveon both classes of problems.The results are compared with those from a discrete quasi-Newton method,showing that the conjugate gradients algorithm is competitive.Thealgorithm exhibits the conjugate gradients speed-up on problems for which the Hessian atthe solution has repeated or clustered eigenvalues.The algorithm is easily parallelizable.     

Discrete Approximation of a Mixture Distribution via Restricted Divergence

Mixture distributions arise in many application areas, for example, as marginal distributions or convolutions of distributions. We present a method of constructing an easily tractable discrete mixture distribution as an approximation to a mixture distribution with a large to infinite number, discrete or continuous, of components. The proposed DIRECT (divergence restricting conditional tesselation) algorithm is set up such that a prespecified precision, defined in terms of Kullback–Leibler divergence between true distribution and approximation, is guaranteed. Application of the algorithm is demonstrated in two examples. Supplementary materials for this article are available online.     

关于总体分布的矩确定

本文引进了局部分布、局部矩、局部矩法估计、样本局部矩和局部分布的矩确定等概念。从而为著名的经典矩量问题提供了新的研究途径与方法并获得了若干新结果。     

x''''=g(x,t)+h(t)型方程的拓扑动力系统与Kurzweil-Henstock积分

本文借助Sell等人建立的局部动力系统理论,利用Kurzweil-Henstock积分,建立了x′=g(x,t)+h(t)型非自治微分方程的拓扑动力系统,为进一步讨论这种方程解的渐近行为作了基础性的工作.本文的工作也是Sell等人工作中有关结论的推广.