Markov chain modelling of the solution surface in local search

When local search methods are applied to combinatorial optimisation problems it is the characteristics of the solution surface that determine the effectiveness of the method. This paper aims to advance our understanding of solution surface characteristics. The focus is on the basin of attraction associated with each local minimum; that is the set of solutions from which a particular local minimum is reached by following downhill local search. A Markov chain model is proposed for the behaviour of the function values occurring in a random walk on the solution surface. The probability transition matrix can be estimated and this is used to estimate both the shape and the size of the basins of attraction. In order to test this approach a study is made of the problem of minimising weighted flowtime on unrelated parallel machines.     

Dissipative relativistic standard map: Periodic attractors and basins of attraction

The dissipative relativistic standard map, introduced by Ciubotariu et al. [Ciubotariu C, Badelita L, Stancu V. Chaos in dissipative relativistic standard maps. Chaos, Solitons & Fractals 2002;13:1253–67.], is further studied numerically for small damping in the resonant case. We find that the attractors are all periodic; their basins of attraction have fractal boundaries and are closely interwoven. The number of attractors increases with decreasing damping. For a very small damping, there are thousands of periodic attractors, comprising mostly of the lowest-period attractors of period one or two; the basin of attraction of these lowest-period attractors is significantly larger compared to the basins of the higher-period attractors.     

Effect of bounded noise on the chaotic motion of a Duffing Van der pol oscillator in a ϕ6 potential

This paper investigates the chaotic behavior of an extended Duffing Van der pol oscillator in a ϕ⁶ potential under additive harmonic and bounded noise excitations for a specific parameter choice. From Melnikov theorem, we obtain the conditions for the existence of homoclinic or heteroclinic bifurcation in the case of the ϕ⁶ potential is bounded, which are complemented by the numerical simulations from which we illustrate the bifurcation surfaces and the fractality of the basins of attraction. The results show that the threshold amplitude of bounded noise for onset of chaos will move upwards as the noise intensity increases, which is further validated by the top Lyapunov exponents of the original system. Thus the larger the noise intensity results in the less possible chaotic domain in parameter space. The effect of bounded noise on Poincare maps is also investigated.     

Approximate solutions and chaotic motions of a piecewise nonlinear–linear oscillator

A global symmetric period-1 approximate solution is analytically constructed for the non-resonant periodic response of a periodically excited piecewise nonlinear–linear oscillator. The approximate solutions are found to be in good agreement with the exact solutions that are obtained from the numerical integration of the original equations. In addition, the dynamic behaviour of the oscillator is numerically investigated with the help of bifurcation diagrams, Lyapunov exponents, Poincare maps, phase portraits and basins of attraction. The existence of subharmonic and chaotic motions and the coexistence of four attractors are observed for some combinations of the system parameters.     

Influence of the multiplicity of the roots on the basins of attraction of Newton’s method

In this work, we develop and implement two algorithms for plotting and computing the measure of the basins of attraction of rational maps defined on the Riemann sphere. These algorithms are based on the subdivisions of a cubical decomposition of a sphere and they have been made by using different computational environments. As an application, we study the basins of attraction of the fixed points of the rational functions obtained when Newton’s method is applied to a polynomial with two roots of multiplicities m and n. We focus our attention on the analysis of the influence of the multiplicities m and n on the measure of the two basins of attraction. As a consequence of the numerical results given in this work, we conclude that, if m > n, the probability that a point in the Riemann Sphere belongs to the basin of the root with multiplicity m is bigger than the other case. In addition, if n is fixed and m tends to infinity, the probability of reaching the root with multiplicity n tends to zero.     

Effect of random noise on chaotic motion of a particle in a ϕ6 potential

The chaotic behaviors of a particle in a triple well ϕ⁶ potential possessing both homoclinic and heteroclinic orbits under harmonic and Gaussian white noise excitations are discussed in detail. Following Melnikov theory, conditions for the existence of transverse intersection on the surface of homoclinic or heteroclinic orbits for triple potential well case are derived, which are complemented by the numerical simulations from which we show the bifurcation surfaces and the fractality of the basins of attraction. The results reveal that the threshold amplitude of harmonic excitation for onset of chaos will move downwards as the noise intensity increases, which is further verified by the top Lyapunov exponents of the original system. Thus the larger the noise intensity results in the more possible chaotic domain in parameter space. The effect of noise on Poincare maps is also investigated.     

How to make dull cellular automata complex by adding memory: Rule 126 case study

Using Rule 126 elementary cellular automaton (ECA), we demonstrate that a chaotic discrete system — when enriched with memory — hence exhibits complex dynamics where such space exploits on an ample universe of periodic patterns induced from original information of the ahistorical system. First, we analyze classic ECA Rule 126 to identify basic characteristics with mean field theory, basins, and de Bruijn diagrams. To derive this complex dynamics, we use a kind of memory on Rule 126; from here interactions between gliders are studied for detecting stationary patterns, glider guns, and simulating specific simple computable functions produced by glider collisions. © 2010 Wiley Periodicals, Inc. Complexity, 2010     

Selection of windows, attractors and self-similar patterns in a coupled map lattice

It is shown that a lattice of diffusively coupled logistic maps displays self-similar period-doubling cascades to chaos with all the known stages of pattern formation. The location of the self-similar patterns is determined. The basins of attraction yielding window structures, so far believed to be negligibly small, are shown to cover virtually all initial conditions given a certain maximum amplitude to the random initial conditions. As a consequence a means for selecting attractors in a CML is obtained. A new pattern selection regime at high nonlinearity is reported and the basins of attraction of some attractors of small lattices are investigated.     

Intertwined Basins of Attraction in Systems of O.D.E.

We investigate the basins of attraction in two dimensional ordinary differential equations (O.D.E.), and show that under certain conditions the basins of attraction are of fine and intertwined structure, which giving rise to an obstruction to predictability.     

Coexistence of domains of attraction of nonautonomous neural networks with time-varying delays

This paper presents new dynamical behavior, i.e., the coexistence of 2^N domains of attraction of N-dimensional nonautonomous neural networks with time-varying delays. By imposing some new assumptions on activation functions and system parameters, we construct 2^N invariant basins for neural system and derive some criteria on the boundedness and exponential attractivity for each invariant basin. Particularly, when neural system degenerates into periodic case, we not only attain the coexistence of 2^N periodic orbits in bounded invariant basins but also give their domains of attraction. Moreover, our results are suitable for autonomous neural systems. Our new results improve and generalize former ones. Finally, computer simulation is performed to illustrate the feasibility of our results.     

A discrete dynamical system as a model of a neural network with generalized Hebbian synapses

We study the dynamical behavior of a discrete time dynamical system which can serve as a model of a learning process. We determine fixed points of this system and basins of attraction of attracting points. This system was studied by Fernanda Botelho and James J. Jamison in [A learning rule with generalized Hebbian synapses, J. Math. Anal. Appl. 273 (2002) 529-547] but authors used its continuous counterpart to describe basins of attraction.     

PageRank centrality for performance prediction: the impact of the local optima network model

A local optima network (LON) compresses relevant features of fitness landscapes in a complex network, where nodes are local optima and edges represent transition probabilities between different basins of attraction. Previous work has found that the PageRank centrality of local optima can be used to predict the success rate and average fitness achieved by local search based metaheuristics. Results are available for LONs where edges describe either basin transition probabilities or escape edges. This paper studies the interplay between the type of LON edges and the ability of the PageRank centrality for the resulting LON to predict the performance of local search based metaheuristics. It finds that LONs are stochastic models of the search heuristic. Thus, to achieve an accurate prediction, the definition of the LON edges must properly reflect the type of diversification steps used in the metaheuristic. LONs with edges representing basin transition probabilities capture well the diversification mechanism of simulated annealing which sometimes also accepts worse solutions that allow the search process to pass between basins. In contrast, LONs with escape edges capture well the diversification step of iterated local search, which escapes from local optima by applying a larger perturbation step.     

On the construction of samples for testing approximate optimization methods for estimate calculation algorithms

To validate approximate optimization schemes for estimate calculation algorithms (ECAs), it is necessary to compute the optimal height, which cannot be done in a reasonable amount of time. A variety of samples are built for which the optimal height of the ECAs is known by construction.     

Stochastic control of attractor preference in a multistable system

When talking about the size of basins of attraction of coexisting states in a noisy multistable system, one can only refer to its probabilistic properties. In this context, the most probable size of basins of attraction of some coexisting states exhibits an obvious non-monotonous dependence on the noise amplitude, i.e., there exists a certain noise level for which the most probable basin’s size is larger than for other noise values, while the average size always decreases as the noise amplitude increases. Such a behavior is demonstrated through the study of the Hénon map with three coexisting attractors (period 1, period 3, and period 9). Since the position of the probabilistic extrema depends on the amplitude and frequency of external modulation applied to a system parameter, noise, periodic modulation and a combination of both provide an efficient control of attractor preference in a system with multiple coexisting states.     

Minimal genus problem for pseudo-real Riemann surfaces

A Riemann surface is said to be pseudo-real if it admits an antiholomorphic automorphism but not an antiholomorphic involution (also known as a symmetry). The importance of such surfaces comes from the fact that in the moduli space of compact Riemann surfaces of given genus, they represent the points with real moduli. Clearly, real surfaces have real moduli. However, as observed by Earle, the converse is not true. Moreover, it was shown by Seppälä that such surfaces are coverings of real surfaces. Here we prove that the latter may always be assumed to be purely imaginary. We also give a characterization of finite groups being groups of automorphisms of pseudo-real Riemann surfaces. Finally, we solve the minimal genus problem for the cyclic case.     

Investigating the Newton–Raphson basins of attraction in the restricted three-body problem with modified Newtonian gravity

The planar circular restricted three-body problem with modified Newtonian gravity is used in order to determine the Newton–Raphson basins of attraction associated with the equilibrium points. The evolution of the position of the five Lagrange points is monitored when the value of the power p of the gravitational potential of the second primary varies in predefined intervals. The regions on the configuration (x, y) plane occupied by the basins of attraction are revealed using the multivariate version of the Newton–Raphson iterative scheme. The correlations between the basins of convergence of the equilibrium points and the corresponding number of iterations needed for obtaining the desired accuracy are also illustrated. We conduct a thorough and systematic numerical investigation by demonstrating how the dynamical quantity p influences the shape as well as the geometry of the basins of attractions. Our results strongly suggest that the power p is indeed a very influential parameter in both cases of weaker or stronger Newtonian gravity.     

Two characteristics of planar intertwined basins of attraction

In this paper, we investigate the intertwined basins of attraction for planar dynamical systems. We prove that the intertwining property is preserved by topologically equivalent systems. Two necessary and sufficient conditions for a planar system having intertwined basins are given.     

Newton's method on the complex exponential function

We show that when Newton's method is applied to the product of a polynomial and the exponential function in the complex plane, the basins of attraction of roots have finite area.