Studies in global and local histogram-guided relaxation algorithms

An image segmentation algorithm based on histogram clustering and probabilistic relaxation labeling is explored. The algorithm is evaluated by means of a set of artificially generated test images with known parameters. Two sources of pixel labeling errors are revealed. The first derives from distribution overlap in the histogram and leads to fragmented or missing regions in a segmentation. The second derives from the gloal nature of the compatibility coefficients used in the relaxation process. The coefficients are shown to be insufficient to correct certain labeling errors and can even cause the destruction of fine image details during the course of the relaxation updating process. A potential solution to these problems is shown to be obtainable by using orientation dependent compatibility coefficients and localizing the scope of the algorithm to small subimages followed by a merging of the segmented subimages.     

局部保持的流形学习算法对比研究

局部保持的流形学习通过从局部到整体的思想保持观测空间和内在嵌入空间的局部几何共性,发现嵌入在高维欧氏空间中的内在低维流形。分析了局部保持的流形学习算法的基本实现框架,详细比较了一些局部保持的流形学习算法的特点,提出了几个有益的研究主题。     

Robust control via concave minimization local and global algorithms

This paper is concerned with the robust control problem of linear fractional representation (LFT) uncertain systems depending on a time-varying parameter uncertainty. Our main result exploits a linear matrix inequality (LMI) characterization involving scalings and Lyapunov variables subject to an additional essentially nonconvex algebraic constraint. The nonconvexity enters the problem in the form of a rank deficiency condition or matrix inverse relation on the scalings only. It is shown that such problems, but also more generally rank inequalities and bilinear constraints, can be formulated as the minimization of a concave functional subject to LMI constraints. First of all, a local Frank and Wolfe (1956) feasible direction algorithm is introduced in this context to tackle this hard optimization problem. Exploiting the attractive concavity structure of the problem, several efficient global concave programming methods are then introduced and combined with the local feasible direction method to secure and certify global optimality of the solutions. Computational experiments indicate the viability of our algorithms, and in the worst case, they require the solution of a few LMI programs     

Design of local fuzzy models using evolutionary algorithms

The application of local fuzzy models to determine the remaining life of a unit in a fleet of vehicles is described. Instead of developing individual models based on the track history of each unit or developing a global model based on the collective track history of the fleet, local fuzzy models are used based on clusters of peers—similar units with comparable utilization and performance characteristics. A local fuzzy performance model is created for each cluster of peers. This is combined with an evolutionary framework to maintain the models. A process has been defined to generate a collection of competing models, evaluate their performance in light of the currently available data, refine the best models using evolutionary search, and select the best one after a finite number of iterations. This process is repeated periodically to automatically update and improve the overall model. To illustrate this methodology an asset selection problem has been identified: given a fleet of industrial vehicles (diesel electric locomotives), select the best subset for mission-critical utilization. To this end, the remaining life of each unit in the fleet is predicted. The fleet is then sorted using this prediction and the highest ranked units are selected. A series of experiments using data from locomotive operations was conducted and the results from an initial validation exercise are presented. The approach of constructing local predictive models using fuzzy similarity with neighboring points along appropriate dimensions is not specific to any asset type and may be applied to any problem where the premise of similarity along chosen attribute dimensions implies similarity in predicted future behavior.     

A hybrid approach of genetic algorithms and local optimizers in cell loading

In this paper, the potential application of genetic algorithms to cell loading is discussed. The objective is to minimize the number of tardy jobs. Three different approaches are proposed and later compared. The first approach consists of two steps where (1) genetic algorithms is used to generate a job sequence and (2) a classical scheduling rule is used to assign jobs to the cells. The second approach consists of three steps where steps 1 and 2 are identical to the first approach plus step (3) Local Optimizer is applied to each cell independently. The third approach is very similar to the second approach except that chromosomes are modified to reflect the changes due to learning with local optimizer. Experimentation results show that the number of cells and the crossover strategy adapted affect the number of tardy jobs found. The results also indicate that hybrid GA-local optimizer approach improves the solution quality drastically. However, it has been also shown that GA alone can duplicate the performance of the hybrid approach with increased population size and number of generations in some of the cases. Finally, the impact of learning on the solution quality was not as significant as expected.     

Aspects of the theory of local algorithms on graphs

Cybernetics and Systems Analysis -     

Comparison of two construction algorithms for local model networks

The divide-and-conquer approach of local model (LM) networks is a common engineering approach to the identification of a complex nonlinear dynamical system. The global representation is obtained from the weighted sum of locally valid, simpler submodels defined over small regions of the operating space. Constructing such networks requires the determination of appropriate partitioning and the parameters of the LMs. This paper focuses on the structural aspect of LM networks. It compares the computational requirements and performances of the Johansen and Foss (J&F) and LOLIMOT tree-construction algorithms. Several useful and important modifications to each algorithm are proposed. The modelling performances are evaluated using real data from a pilot plant of a pH neutralization process. Results show that while J&F achieves a more accurate nonlinear representation of the pH process, LOLIMOT requires significantly less computational effort.     

Systematic integration of parameterized local search into evolutionary algorithms

Application-specific, parameterized local search algorithms (PLSAs), in which optimization accuracy can be traded off with run time, arise naturally in many optimization contexts. We introduce a novel approach, called simulated heating, for systematically integrating parameterized local search into evolutionary algorithms (EAs). Using the framework of simulated heating, we investigate both static and dynamic strategies for systematically managing the tradeoff between PLSA accuracy and optimization effort. Our goal is to achieve maximum solution quality within a fixed optimization time budget. We show that the simulated heating technique better utilizes the given optimization time resources than standard hybrid methods that employ fixed parameters, and that the technique is less sensitive to these parameter settings. We apply this framework to three different optimization problems, compare our results to the standard hybrid methods, and show quantitatively that careful management of this tradeoff is necessary to achieve the full potential of an EA/PLSA combination.     

Fundamental limits of reconstruction-based superresolution algorithms under local translation

Superresolution is a technique that can produce images of a higher resolution than that of the originally captured ones. Nevertheless, improvement in resolution using such a technique is very limited in practice. This makes it significant to study the problem: "Do fundamental limits exist for superresolution?" In this paper, we focus on a major class of superresolution algorithms, called the reconstruction-based algorithms, which compute high-resolution images by simulating the image formation process. Assuming local translation among low-resolution images, this paper is the first attempt to determine the explicit limits of reconstruction-based algorithms, under both real and synthetic conditions. Based on the perturbation theory of linear systems, we obtain the superresolution limits from the conditioning analysis of the coefficient matrix. Moreover, we determine the number of low-resolution images that are sufficient to achieve the limit. Both real and synthetic experiments are carried out to verify our analysis.     

Efficient and scalable Pareto optimization by evolutionary local selection algorithms

Local selection is a simple selection scheme in evolutionary computation. Individual fitnesses are accumulated over time and compared to a fixed threshold, rather than to each other, to decide who gets to reproduce. Local selection, coupled with fitness functions stemming from the consumption of finite shared environmental resources, maintains diversity in a way similar to fitness sharing. However, it is more efficient than fitness sharing and lends itself to parallel implementations for distributed tasks. While local selection is not prone to premature convergence, it applies minimal selection pressure to the population. Local selection is, therefore, particularly suited to Pareto optimization or problem classes where diverse solutions must be covered. This paper introduces ELSA, an evolutionary algorithm employing local selection and outlines three experiments in which ELSA is applied to multiobjective problems: a multimodal graph search problem, and two Pareto optimization problems. In all these experiments, ELSA significantly outperforms other well-known evolutionary algorithms. The paper also discusses scalability, parameter dependence, and the potential distributed applications of the algorithm.     

An evaluation of sorting algorithms for common-bus local networks

Evaluating the performance of local area networks is a major concern of the research community and organizations that install this type of network. In data processing applications, sorting is one of the most important and frequently performed operations, because database operations can be performed efficiently on sorted files. The efficiency of sorting algorithms in local networks, therefore, plays a significant role in determining overall network performance. This paper evaluates four alternate methods of performing external sort in common-bus local networks. Each method has five steps: interrupt and synchronization, network data transfer by packets, local sorting, global sorting, and output. The execution time for each method is calculated for four cases using different overlaps among the time components. Each method is evaluated by observing its behavior at different network speeds, file sizes, network sizes, page sizes, I/O times, and interrupt and synchronization times. This paper shows how changing the value of these variables affects the performance of the sorting algorithms. These observations are useful in designing sorting algorithms and other general, parallel algorithms for common-bus local networks.     

Mapping land-cover modifications over large areas: A comparison of machine learning algorithms

Large area land-cover monitoring scenarios, involving large volumes of data, are becoming more prevalent in remote sensing applications. Thus, there is a pressing need for increased automation in the change mapping process. The objective of this research is to compare the performance of three machine learning algorithms (MLAs); two classification tree software routines (S-plus and C4.5) and an artificial neural network (ARTMAP), in the context of mapping land-cover modifications in northern and southern California study sites between 1990/91 and 1996. Comparisons were based on several criteria: overall accuracy, sensitivity to data set size and variation, and noise. ARTMAP produced the most accurate maps overall ( 84%), for two study areas — in southern and northern California, and was most resistant to training data deficiencies. The change map generated using ARTMAP has similar accuracies to a human-interpreted map produced by the U.S. Forest Service in the southern study area. ARTMAP appears to be robust and accurate for automated, large area change monitoring as it performed equally well across the diverse study areas with minimal human intervention in the classification process.     

设备定位问题局部搜索算法的实验

讨论设备问题的局部搜索近似算法及其在实际计算中表现出的新性质。主要讨论局部搜索算法中初始解的产生方法,设备价值与服务价值大小对算法求解性能的影响。实验表明：约有99%以上的实例可直接利用局部搜索算法求得最优解;贪心算法产生初始解的局部搜索算法求解时间明显短于随机算法产生初始解的方法,但两者求解质量相当;设备价值和服务价值数值范围越大,局部搜索算法越容易求得最优解。     

Semiring induced valuation algebras: Exact and approximate local computation algorithms

Local computation in join trees or acyclic hypertrees has been shown to be linked to a particular algebraic structure, called valuation algebra. There are many models of this algebraic structure ranging from probability theory to numerical analysis, relational databases and various classical and non-classical logics. It turns out that many interesting models of valuation algebras may be derived from semiring valued mappings. In this paper we study how valuation algebras are induced by semirings and how the structure of the valuation algebra is related to the algebraic structure of the semiring. In particular, c-semirings with idempotent multiplication induce idempotent valuation algebras and therefore permit particularly efficient architectures for local computation. Also important are semirings whose multiplicative semigroup is embedded in a union of groups. They induce valuation algebras with a partially defined division. For these valuation algebras, the well-known architectures for Bayesian networks apply. We also extend the general computational framework to allow derivation of bounds and approximations, for when exact computation is not feasible.     

K-means-type algorithms: a generalized convergence theorem and characterization of local optimality

The K-means algorithm is a commonly used technique in cluster analysis. In this paper, several questions about the algorithm are addressed. The clustering problem is first cast as a nonconvex mathematical program. Then, a rigorous proof of the finite convergence of the K-means-type algorithm is given for any metric. It is shown that under certain conditions the algorithm may fail to converge to a local minimum, and that it converges under differentiability conditions to a Kuhn-Tucker point. Finally, a method for obtaining a local-minimum solution is given.     

Efficient algorithms of local discrete wavelet transform with Haar-like bases

In this paper, two new fast algorithms for calculating a local discrete wavelet transform for a one-dimensional signal based on the example of Haar’s wavelet basis are presented and their computational complexities are evaluated. The algorithms are compared with each other and with well-known algorithms of fast wavelet transform. Employment recommendations are given for each algorithm presented. Among other things the preference domains of these algorithms are shown, i.e., the parameters of wavelet transform calculating problem are specified so that these algorithms are computationally efficient. Conclusions regarding the advantages of the recursive algorithm over the alternative one and over the well-known algorithm of the fast wavelet transform are reached using the analysis of algorithmic complexities as the base and with regard to additional possibilities of the recursive algorithm. The extension of the algorithms considered to a two-dimensional case is presented. Vasilii N. Kopenkov. Was born in 1978. He was graduated in Samara State Aerospace University in 2001. At present time he works as an assistant on chair of geoinformatics in SSAU and as a junior research assistant in Institute of Image Processing Systems RAS. Head interests: image processing, earth remote sensing data and pattern recognition, geoinformatic systems. Author of 17 publications, including 7 articles. Member of the Russian Association Pattern Recognition and Image Analysis.