Efficient parallel algorithms for numerical simulation

COUPL+ is a programming environment for applications using unstructured and hybrid grids for numerical simulations. It automates parallelization by handling the partitioning of data and dependent data and maintaining halo interfaces and copy coherency. We explore some algorithms behind this package. A multi-level partitioning method is described which is effective in the presence of skewed data, solving the multi-set median-finding problem. Partitioning elements over a set of pre-partitioned nodes is explored and a novel method is suggested for reducing communication in the resulting distribution.     

Fuzzy adaptive genetic algorithms: design,taxonomy, and future directions

The genetic algorithm behaviour is determined by the exploitation and exploration relationship kept throughout the run. Adaptive genetic algorithms, that dynamically adjust selected control parameters or genetic operators during the evolution have been built. Their objective is to offer the most appropriate exploration and exploitation behaviour to avoid the premature convergence problem and improve the final results. One of the adaptive approaches are the adaptive parameter setting techniques based on the use of fuzzy logic controllers, the fuzzy adaptive genetic algorithms (FAGAs). In this paper, we analyse the FAGAs in depth. First, we describe the steps for their design and present an instance, which is studied from an empirical point of view. Then, we propose a taxonomy for FAGAs, attending on the combination of two aspects: the level where the adaptation takes place and the way the Rule-Bases are obtained. Furthermore, FAGAs belonging to different groups of the taxonomy are reviewed. Finally, we identify some open issues, and summarise a few new promising research directions on the topic. From the results provided by the approaches presented in the literature and the experimental results achieved in this paper, an important conclusion is obtained: the use of fuzzy logic controllers to adapt genetic algorithm parameters may really improve the genetic algorithm performance. This research has been supported by DGICYT PB98-1319.     

An experimental study of adaptive control for evolutionary algorithms

In this paper, we investigate how adaptive operator selection techniques are able to efficiently manage the balance between exploration and exploitation in an evolutionary algorithm, when solving combinatorial optimization problems. We introduce new high level reactive search strategies based on a generic algorithm's controller that is able to schedule the basic variation operators of the evolutionary algorithm, according to the observed state of the search. Our experiments on SAT instances show that reactive search strategies improve the performance of the solving algorithm.     

Randomized algorithms for the synthesis of cautious adaptive controllers

We introduce a new methodology for the design of cautious adaptive controllers based on the following two-step procedure: (i) a probability measure describing the likelihood of different models is updated on-line based on observations, and (ii) a controller with certain robust control specifications is tuned to the updated probability by means of randomized algorithms. The robust control specifications are assigned as average specifications with respect to the estimated probability measure, and randomized algorithms are used to make the controller tuning computationally tractable.This paper provides a general overview of the proposed new methodology. Still, many issues remain open and represent interesting topics for future research.     

Simulating non-stationary operators in search algorithms

In this paper, we propose new scenarios for simulating search operators whose behaviors often change continuously during the search. In these scenarios, the performance of such operators decreases while they are applied. This is motivated by the fact that operators for optimization problems are often roughly classified into exploitation and exploration operators. Our simulation model is used to compare the performances of operator selection policies and to identify their ability to handle specific non-stationary operators. An experimental study highlights respective behaviors of operator selection policies when faced to such non-stationary search scenarios.     

Gas–liquid separator modelling and simulation with Gaussian-process models

The Gaussian-process (GP) model is an example of a probabilistic, nonparametric model with uncertainty predictions. It can be used for the modelling of complex nonlinear systems and also for dynamic systems identification. The output of the GP model is a normal distribution, expressed in terms of the mean and variance. The modelling case study of a gas–liquid separator is presented in this paper. It describes the comparison of three methods for dynamic GP model simulation in the phase of model validation. The level of the computational burden associated with each approach increases with the complexity of the computation necessary for an approximation of the uncertainty propagation.     

Fast parallel Preconditioned Conjugate Gradient algorithms for robot manipulator dynamics simulation

In this paper fast parallel Preconditioned Conjugate Gradient (PCG) algorithms for robot manipulator forward dynamics, or dynamic simulation, problem are presented. By exploiting the inherent structure of the forward dynamics problem, suitable preconditioners are devised to accelerate the iterations. Also, based on the choice of preconditioners, a modified dynamic formulation is used to speedup both serial and parallel computation of each iteration. The implementation of the parallel algorithms on two interconnected processor arrays is discussed and their computation and communication complexities are analyzed. The simulation results for a Puma Arm are presented to illustrate the effectiveness of the proposed preconditioners. With a faster convergence due to preconditioning and a faster computation of iterations due to parallelization, the developed parallel PCG algorithms represent the fastest alternative for parallel computation of the problem withO(n) processors.     

并行智能优化算法研究进展

基于种群迭代搜索的智能优化算法在农业、交通、工业等很多领域都取得了广泛的应用.但是该类算法迭代寻优的特点使其求解效率通常较低,很难应用到大规模、高维或实时性要求较高的复杂优化问题中.随并行分布式技术的发展,国内外很多学者开始着手研究智能优化算法的并行化.本文首要介绍了并行智能优化算法的基本概念;其次从协同机制、并行模型以及硬件结构3个维度综述了几类常见的并行智能优化算法,详细分析阐述了它们优点及不足;最后对并行智能优化算法的未来研究进行了展望.     

Parameter adaptive control algorithms—A tutorial

An introduction is given to adaptive (self-tuning) control algorithms with recursive parameter estimation, which have obtained increasing attention in recent years. These algorithms result from combinations of recursive parameter estimation algorithms and easy to design control algorithms. Firstly a short review is given on proper recursive parameter estimation methods, including their application in a closed loop. This is followed by the design equations for various control algorithms and ways for d.c.-value estimation and for offset compensation. Various explicit and implicit combinations can be designed with different properties of the resulting adaptive control algorithms for both deterministic and stochastic disturbances. Their convergence properties are discussed. Simulation examples are presented and examples for the adaptive control of an air conditioner and a pH-process are shown. The introduction of a third feedback level for coordination and supervision is considered. Finally further problems are discussed.     

Strategy and Simulation of Adaptive RID for Distributed Dynamic Load Balancing in Parallel Systems

Dynamic load balancing schemes are significant for efficiently executing nonuniform problems in highly parallel multicomputer systems.The objective is to minimize the total exectuion time of single applications.This paper has proposed an ARID strategy for distributed dynamic load balancing.Its principle and control protocol are described,and te communication overhead,the effect on system stability and the performance efficiency are analyzed.Finally,simulation experiments are carried out to compare the adaptive strategy with other dynamic load balancing schemes.     

Fast adaptive algorithms and networks for class-separability features

In this article, we introduce accelerated algorithms for linear discriminant analysis (LDA) and feature extraction from unimodal multiclass Gaussian data. Current adaptive methods based on the gradient descent optimization technique use a fixed or a monotonically decreasing step size in each iteration, which results in a slow convergence rate. Here, we use a variable step size, optimally computed in each iteration using the steepest descent method, in order to accelerate the convergence of the algorithm. Based on the new adaptive algorithm, we present a self-organizing neural network for adaptive computation of the square root of the inverse covariance matrix (Σ^−1/2) and use it (i) in a network for optimal feature extraction from Gaussian data and (ii) in cascaded form with a principal component analysis network for LDA. Experimental results demonstrate fast convergence and high stability of the algorithm and justify its advantages for on-line pattern recognition applications with stationary and non-stationary input data.     

Evolutionary algorithms and dynamic programming

Recently, it has been proven that evolutionary algorithms produce good results for a wide range of combinatorial optimization problems. Some of the considered problems are tackled by evolutionary algorithms that use a representation which enables them to construct solutions in a dynamic programming fashion. We take a general approach and relate the construction of such algorithms to the development of algorithms using dynamic programming techniques. Thereby, we give general guidelines on how to develop evolutionary algorithms that have the additional ability of carrying out dynamic programming steps. Finally, we show that for a wide class of the so-called DP-benevolent problems (which are known to admit FPTAS) there exists a fully polynomial-time randomized approximation scheme based on an evolutionary algorithm.     

A perspective on convergence of adaptive control algorithms

This paper presents an overview of the current status of convergence theory for adaptive control algorithms. Rather than giving a comprehensive survey, the paper aims to emphasize the conceptual common ground between different approaches. Possible areas for future research are also discussed.     

New approaches to deriving parallel algorithms

A method is proposed for converting an algorithm admitting no parallel treatment into a new algorithm, in essence, with much better parallel properties. The method is intended for tackling the so called T-algorithms, the term ensuing from first examples of such algorithms concerned in the context of Toeplitz-like matrices. Generalized T-algorithms are also considered.     

Fast adaptive algorithms for minor component analysis using Householder transformation

In this paper, we propose new adaptive algorithms for the extraction and tracking of the least (minor) or eventually, principal eigenvectors of a positive Hermitian covariance matrix. The main advantage of our proposed algorithms is their low computational complexity and numerical stability even in the minor component analysis case. The proposed algorithms are considered fast in the sense that their computational cost is O(np) flops per iteration where n is the size of the observation vector and p<n is the number of eigenvectors to estimate.We consider OJA-type minor component algorithms based on the constraint and non-constraint stochastic gradient technique. Using appropriate fast orthogonalization procedures, we introduce new fast algorithms that extract the minor (or principal) eigenvectors and guarantee good numerical stability as well as the orthogonality of their weight matrix at each iteration. In order to have a faster convergence rate, we propose a normalized version of these algorithms by seeking the optimal step-size. Our algorithms behave similarly or even better than other existing algorithms of higher complexity as illustrated by our simulation results.     

Localization of edges in graph models of two-level algorithms

Multidimensional computational models of two-level algorithms are introduced and investigated. Transformations of graph models of the algorithms are developed, which allow one to obtain modified models without global edges. The modified graph models can be transformed by the well-known transformation and mapping procedures into one-, two-, and three-dimensional array processors without global interconnections. Translated from Kibernetika i Sistemnyi Analiz, No. 6, pp. 63–71, November–December, 1999.     

Efficient adaptive collect using randomization

An adaptive algorithm, whose step complexity adjusts to the number of active processes, is attractive for distributed systems with a highly-variable number of processes. The cornerstone of many adaptive algorithms is an adaptive mechanism to collect up-to-date information from all participating processes. To date, all known collect algorithms either have non-linear step complexity or they are impractical because of unrealistic memory overhead. This paper presents new randomized collect algorithms with asymptotically optimal O(k) step complexity and linear memory overhead only. In addition we present a new deterministic collect algorithm that beats the best step complexity for previous polynomial-memory algorithms. Partially supported by NSF Grants CCR–0310970 and ANI–0326001. A preliminary version of this paper appeared in the Proceedings of the 18th Annual Conference on Distributed Computing (DISC) 2004 [10].     

A parallel adaptive tabu search approach

This paper presents a new approach for parallel tabu search based on adaptive parallelism. Adaptive parallelism was used to dynamically adjust the parallelism degree of the application with respect to the system load. Adaptive parallelism demonstrates that high-performance computing using a hundred of heterogeneous workstations combined with massively parallel machines is feasible to solve large optimization problems. The parallel tabu search algorithm includes different tabu list sizes and new intensification/diversification mechanisms. Encouraging results have been obtained in solving the quadratic assignment problem. We have improved the best known solutions for some large real-world problems.     

遗传算法中自适应方法的比较和分析

分析了前人提出的具有代表性的自适应遗传算法,使用23个测试函数对SGA和3种AGA进行实验比较,讨论并总结出各种AGA的优劣所在,为新研究理念的提出提供基础,也为工业应用提供一个参考标准.实验结果表明,基于聚类分析的AGA在算法性能上较其它自适应遗传算法更优,具有很高的实用价值和发展前景.