A multi-start central force optimization for global optimization

Central force optimization (CFO) is an efficient and powerful population-based intelligence algorithm for optimization problems. CFO is deterministic in nature, unlike the most widely used metaheuristics. CFO, however, is not completely free from the problems of premature convergence. One way to overcome local optimality is to utilize the multi-start strategy. By combining the respective advantages of CFO and the multi-start strategy, a multi-start central force optimization (MCFO) algorithm is proposed in this paper. The performance of the MCFO approach is evaluated on a comprehensive set of benchmark functions. The experimental results demonstrate that MCFO not only saves the computational cost, but also performs better than some state-of-the-art CFO algorithms. MCFO is also compared with representative evolutionary algorithms. The results show that MCFO is highly competitive, achieving promising performance.     

Deterministic learning of completely resonant nonlinear wave systems with Dirichlet boundary conditions

In this paper, we investigate the approximation of completely resonant nonlinear wave systems via deterministic learning. The plants are distributed parameter systems (DPS) describing homogeneous and isotropic elastic vibrating strings with fixed endpoints. The purpose of the paper is to approximate the infinite-dimensional dynamics, rather than the parameters of the wave systems. To solve the problem, the wave systems are first transformed into finite-dimensional dynamical systems described by ordinary differential equation (ODE). The properties of the finite-dimensional systems, including the convergence of the solution, as well as the dominance of partial system dynamics according to point-wise measurements, are analyzed. Based on the properties, second, by using the deterministic learning algorithm, an approximately accurate neural network (NN) approximation of the the finite-dimensional system dynamics is achieved in a local region along the recurrent trajectories. Simulation studies are included to demonstrate the effectiveness of the proposed approach.     

Robust state estimation for uncertain linear systems with deterministic input signals

In this paper, we investigate state estimations of a dynamical system in which not only process and measurement noise, but also parameter uncertainties and deterministic input signals are involved. The sensitivity penalization based robust state estimation is extended to uncertain linear systems with deterministic input signals and parametric uncertainties which may nonlinearly affect a state-space plant model. The form of the derived robust estimator is similar to that of the well-known Kalman filter with a comparable computational complexity. Under a few weak assumptions, it is proved that though the derived state estimator is biased, the bound of estimation errors is finite and the covariance matrix of estimation errors is bounded. Numerical simulations show that the obtained robust filter has relatively nice estimation performances.     

An overview of methods to evaluate uncertainty of deterministic models in decision support

There is an increasing need for environmental management advice that is wide-scoped, covering various interlinked policies, and realistic about the uncertainties related to the possible management actions. To achieve this, efficient decision support integrates the results of pre-existing models. Many environmental models are deterministic, but the uncertainty of their outcomes needs to be estimated when they are utilized for decision support. We review various methods that have been or could be applied to evaluate the uncertainty related to deterministic models' outputs. We cover expert judgement, model emulation, sensitivity analysis, temporal and spatial variability in the model outputs, the use of multiple models, and statistical approaches, and evaluate when these methods are appropriate and what must be taken into account when utilizing them. The best way to evaluate the uncertainty depends on the definitions of the source models and the amount and quality of information available to the modeller.     

Interference automata

We propose a computing model, the Two-Way Optical Interference Automata (2OIA), that makes use of the phenomenon of optical interference. We introduce this model to investigate the increase in power, in terms of language recognition, of a classical Deterministic Finite Automaton (DFA) when endowed with the facility of interference. The question is in the spirit of Two-Way Finite Automata With Quantum and Classical States (2QCFA) [A. Ambainis, J. Watrous, Two-way finite automata with quantum and classical states, Theoret. Comput. Sci. 287 (1) (2002) 299–311] wherein the classical DFA is augmented with a quantum component of constant size. We test the power of 2OIA against the languages mentioned in the above paper. We give efficient 2OIA algorithms to recognize languages for which 2QCFA machines have been shown to exist, as well as languages whose status vis-a-vis 2QCFA has been posed as open questions. Having a DFA as a component, it trivially recognizes regular languages. We show that our model can recognize all languages recognized by 1-way deterministic blind counter automata. Finally we show the existence of a language that cannot be recognized by a 2OIA but which can be recognized by an O(n³)$O\left(n^3\right)$ space Turing machine.     

Motion Planning for Haptic Guidance

Haptic devices allow a user to feel either reaction forces from virtual interactions or reaction forces reflected from a remote site during a bilateral teleoperation task. Also, guiding forces can be exerted to train the user in the performance of a virtual task or to assist him/her to safely teleoperate a robot. The generation of guiding forces relies on the existence of a motion plan that provides the direction to be followed to reach the goal from any free configuration of the configuration space (-space). This paper proposes a method to obtain such a plan that interleaves a sampling-based exploration of -space with an efficient computation of harmonic functions. A deterministic sampling sequence (with a bias based on harmonic function values) is used to obtain a hierarchical cell decomposition model of -space. A harmonic function is iteratively computed over the partially known model using a novel approach. The harmonic function is the navigation function used as motion plan. The approach has been implemented in a planner (called the Kautham planner) that, given an initial and a goal configuration, provides: (a) a channel of cells connecting the cell that contains the initial configuration with the cell that contains the goal configuration; (b) two harmonic functions over the whole -space, one that guides motions towards the channel and another that guides motions within the channel towards the goal; and (c) a path computed over a roadmap built with the free samples of the channel. The harmonic functions and the solution path are then used to generate the guiding forces for the haptic device. The planning approach is illustrated with examples on 2D and 3D workspaces. This work was partially supported by the CICYT projects DPI2005-00112 and DPI2007-63665.     

A neural networks learning algorithm for minor component analysis and its convergence analysis

The eigenvector associated with the smallest eigenvalue of the autocorrelation matrix of input signals is called minor component. Minor component analysis (MCA) is a statistical approach for extracting minor component from input signals and has been applied in many fields of signal processing and data analysis. In this letter, we propose a neural networks learning algorithm for estimating adaptively minor component from input signals. Dynamics of the proposed algorithm are analyzed via a deterministic discrete time (DDT) method. Some sufficient conditions are obtained to guarantee convergence of the proposed algorithm.     

On the Black-Box Complexity of Sperner’s Lemma

We present several results on the complexity of various forms of Sperner’s Lemma in the black-box model of computing. We give a deterministic algorithm for Sperner problems over pseudo-manifolds of arbitrary dimension. The query complexity of our algorithm is linear in the separation number of the skeleton graph of the manifold and the size of its boundary. As a corollary we get an deterministic query algorithm for the black-box version of the problem 2D-SPERNER, a well studied member of Papadimitriou’s complexity class PPAD. This upper bound matches the deterministic lower bound of Crescenzi and Silvestri. The tightness of this bound was not known before. In another result we prove for the same problem an lower bound for its probabilistic, and an lower bound for its quantum query complexity, showing that all these measures are polynomially related. Research supported by the European Commission IST Integrated Project Qubit Application (QAP) 015848, the OTKA grants T42559 and T46234, and by the ANR Blanc AlgoQP grant of the French Research Ministry.