Analysis of the diversity of population and convergence of genetic algorithms based on Negentropy

With its wide use in different fields, the problem of the convergence of simple genetic algorithms (GAs) has been concerned. In the past, the research on the convergence of GAs was based on Holland's model theorem. The diversity of the evolutionary population and the convergence of GAs are studied by using the concept of negentropy based on the discussion of the characteristic of GA. Some test functions are used to test the convergence of GAs, and good results have been obtained. It is shown that the global optimization may be obtained by selecting appropriate parameters of simple GAs if the evolution time is enough.

The Markov Chain Analysis of Premature Convergence of Genetic Algorithms

This paper discussed CGA population Markov chain with mutation probability. For premature convergence of this algorithm, one concerned, we give its analysis of Markov chain.

Drift Analysis in Studying the Convergence and Hitting Times of Evolutionary Algorithms: An Overview

This paper introduces drift analysis approach in studying the convergence and hitting times of evolutionary algorithms. First the methodology of drift analysis is introduced, which links evolutionary algorithms with Markov chains or supermartingales. Then the drift conditions which guarantee the convergence of evolutionary algorithms are described. And next the drift conditions which are used to estimate the hitting times of evolutionary algorithms are presented. Finally an example is given to show how to analyse hitting times of EAs by drift analysis approach.

A New Method for Fastening the Convergence of Immune Algorithms Using an Adaptive Mutation Approach

This paper presents a new adaptive mutation approach for fastening the convergence of immune algorithms (IAs). This method is adopted to realize the twin goals of maintaining diversity in the population and sustaining the convergence capacity of the IA. In this method, the mutation rate (pm) is adaptively varied depending on the fitness values of the solutions. Solutions of high fitness are protected, while solutions with sub-average fitness are totally disrupted. A solution to the problem of deciding the optimal value of pm is obtained. Experiments are carried out to compare the proposed approach to traditional one on a set of optimization problems. These are namely: 1) an exponential multi-variable function;2) a rapidly varying multimodal function and 3) design of a second order 2-D narrow band recursive LPF. Simulation results show that the proposed method efficiently improves IA’s performance and prevents it from getting stuck at a local optimum.

A Mathematical Model of Real-Time Simulation and the Convergence Analysis on Real-Time Runge-Kutta Algorithms

In this paper, a mathematical model of real-time simulation is given, and the problem of convergence on real-time Runge-Kutta algorithms is analysed. At last a theorem on the relation between the order of compensation and the convergent order of real-time algorithm is proved.

Stochastic analysis and convergence velocity estimation of genetic algorithms

Formulizations of mutation and crossover operators independent of representation of solutions are proposed. A kind of precisely quantitative Markov chain of populations of standard genetic algorithms is modeled. It is proved that inadequate parameters of mutation and crossover probabilities degenerate standard genetic algorithm to a class of random search algorithms without selection bias toward any solution based on fitness. After introducing elitist reservation, the stochastic matrix of Markov chain of the best-so-far individual with the highest fitness is derived.The average convergence velocity of genetic algorithms is defined as the mathematical expectation of the mean absorbing time steps that the best-so-far individual transfers from any initial solution to the global optimum. Using the stochastic matrix of the best-so-far individual, a theoretic method and the computing process of estimating the average convergence velocity are proposed.

CONVERGENCE RATES FOR A CLASS OF EVOLUTIONARY ALGORITHMS WITH ELITIST STRATEGY

This paper discusses the convergence rates about a class of evolutionary algorithms in general search spaces by means of the ergodic theory in Markov chain and some techniques in Banach algebra. Under certain conditions that transition probability functions of Markov chains corresponding to evolutionary algorithms satisfy, the authors obtain the convergence rates of the exponential order. Furthermore, they also analyze the characteristics of the conditions which can be met by genetic operators and selection strategies.

Multi-strategy hybrid whale optimization algorithms for complex constrained optimization problems

A multi-strategy hybrid whale optimization algorithm(MSHWOA)for complex constrained optimization problems is proposed to overcome the drawbacks of easily trapping into local optimum,slow convergence speed and low optimization precision.Firstly,the population is initialized by introducing the theory of good point set,which increases the randomness and diversity of the population and lays the foundation for the global optimization of the algorithm.Then,a novel linearly update equation of convergence factor is designed to coordinate the abilities of exploration and exploitation.At the same time,the global exploration and local exploitation capabilities are improved through the siege mechanism of Harris Hawks optimization algorithm.Finally,the simulation experiments are conducted on the 6 benchmark functions and Wilcoxon rank sum test to evaluate the optimization performance of the improved algorithm.The experimental results show that the proposed algorithm has more significant improvement in optimization accuracy,convergence speed and robustness than the comparison algorithm.

AN ANALYSIS ABOUT BEHAVIOR OF EVOLUTIONARY ALGORITHMS:A KIND OF THEORETICAL DESCRIPTION BASED ON GLOBAL RANDOM SEARCH METHODS

Evolutionary computation is a kind of adaptive non--numerical computation method which is designed tosimulate evolution of nature. In this paper, evolutionary algorithm behavior is described in terms of theconstruction and evolution of the sampling distributions over the space of candidate solutions. Iterativeconstruction of the sampling distributions is based on the idea of the global random search of generationalmethods. Under this frame, propontional selection is characterized as a gobal search operator, and recombination is characerized as the search process that exploits similarities. It is shown-that by properly constraining the search breadth of recombination operators, weak convergence of evolutionary algorithms to aglobal optimum can be ensured.

SOME IMPROVED PROJECTED QUASI-NEWTON ALGORITHMS AND THEIR CONVERGENCE Ⅱ.LOCAL CONVERGENCE RATE AND NUMERICAL TESTS

For the improved two-sided projected quasi-Newton algorithms, which were presented in PartI, we prove in this paper that they are locally one-step or two-step superlinearly convergent. Numerical tests are reported thereafter. Results by solving a set of typical problems selectedfrom literature have demonstrated the extreme importance of these modifications in making Nocedal& Overton's original methon practical. Furthermore, these results show that the improved algoritnmsare very competitive in comparison with some highly praised sequential quadratic programmingmethods.

CONVERGENCE OF ALGORITHMS FOR FINDING EIGENVECTORS

In this paper we give a rigorous analysis of convergence of algorithms for finding eigenvectors of a real symmetric matrix. The algorithms are deterministic and our methods are very intuitive.

Monotone Additive Schwarz Algorithms for Solving Two-Side Obstacle Problems

Additive Schwarz algorithms for solving the discrete problems of twrvside obstacle problems are proposed. The monotone convergence of the algorithms is established for M-matrix and the h-independent convergence rate is proved for S-matrix. The so-called finite step convergence for coincident components is discussed for nondegenerate discreted problems.

Adaptive genetic algorithm with the criterion of premature convergence

To counter the defect of traditional genetic algorithms, an improved adaptivegenetic algorithm with the criterion of premature convergence is provided. The occurrence ofpremature convergence is forecasted using colony entropy and colony variance. When prematureconvergence occurs, new individuals are generated in proper scale randomly based on superiorindividuals in the colony. We use these new individuals to replace some individuals in the oldcolony. The updated individuals account for 30 percent - 40 percent of all individuals and the sizeof scale is related to the distribution of the extreme value of the target function. Simulationtests show that there is much improvement in the speed of convergence and the probability of globalconvergence.

Randomized Algorithms for Probabilistic Optimal Robust Performance Controller Design

Polynomial-time randomized algorithms were constructed to approximately solve optimal robust performance controller design problems in probabilistic sense and the rigorous mathematical justification of the approach was given. The randomized algorithms here were based on a property from statistical learning theory known as (uniform) convergence of empirical means (UCEM). It is argued that in order to assess the performance of a controller as the plant varies over a pre-specified family, it is better to use the average performance of the controller as the objective function to be optimized, rather than its worst-case performance. The approach is illustrated to be efficient through an example.

SOME IMPROVED PROJECTED QUASI-NEWTON ALGORITHMS AND THEIR CONVERGENCE Ⅰ.METHODS AND GLOBAL BEHAVIOR

In this paper we improve the two versions of the two-sided projected quasi-Newton method-onewas proposed by Nocedal & Overton in [1] and the other was discussed in our previous paper, byintroducing three different merit functions to make inexact one-dimensional searches. It is shown that these improved quasi-Newton algorithms have gained global convergence propertywhich is not possessed by the original two algorithms.

Relative efficiency appraisal of discrete choice modeling algorithms using small-scale maximum likelihood estimator through empirically tailored computing environment

Discrete choice models are widely used in multiple sectors such as transportation, health, energy, and marketing, etc., where the model estimation is usually carried out by using commercial software. Nonetheless, tailored computer codes offer modellers greater flexibility and control of unique modelling situation. Aligned with empirically tailored computing environment, this research discusses the relative performance of six different algorithms of a discrete choice model using three key performance measures： convergence time, number of iterations, and iteration time. The computer codes are developed by using Visual Basic Application （VBA）. Maximum likelihood function （MLF） is formulated and the mathematical relationships of gradient and Hessian matrix are analytically derived to carry out the estimation process. The estimated parameter values clearly suggest that convergence criterion and initial guessing of parameters are the two critical factors in determining the overall estimation performance of a custom-built discrete choice model.

AN OVERALL STUDY OF CONVERGENCE CONDITIONS FOR ALGORITHMS IN NONLINEAR PROGRAMMING

Since the point-to-set maps were introduced by Zangwill in the study of conceptual algorithms, various sufficient conditions for the algorithms to be of global convergence have been established.In this paper, the relations among all these conditions are illustrated by a unified approach;still more, unlike the sufficient conditions previously given in the literature,a new necessary condition is put forward at the end of the paper, so that it implies more applications.

Global Convergence Analysis of Non-Crossover Genetic Algorithm and Its Application to Optimization

Selection, crossover, and mutation are three main operators of the canonical genetic algorithm (CGA). This paper presents a new approach to the genetic algorithm. This new approach applies only to mutation and selection operators. The paper proves that the search process of the non-crossover genetic algorithm (NCGA) is an ergodic homogeneous Markov chain. The proof of its convergence to global optimum is presented. Some nonlinear multi-modal optimization problems are applied to test the efficacy of the NCGA. NP-hard traveling salesman problem (TSP) is cited here as the benchmark problem to test the efficiency of the algorithm. The simulation result shows that NCGA achieves much faster convergence speed than CGA in terms of CPU time. The convergence speed per epoch of NCGA is also faster than that of CGA.

An adaptive genetic algorithm with diversity-guided mutation and its global convergence property

An adaptive genetic algorithm with diversity-guided mutation, which combines adaptive probabilities of crossover and mutation was proposed. By means of homogeneous finite Markov chains, it is proved that adaptive genetic algorithm with diversity-guided mutation and genetic algorithm with diversity-guided mutation converge to the global optimum if they maintain the best solutions, and the convergence of adaptive genetic algorithms with adaptive probabilities of crossover and mutation was studied. The performances of the above algorithms in optimizing several unimodal and multimodal functions were compared. The results show that for multimodal functions the average convergence generation of the adaptive genetic algorithm with diversity-guided mutation is about 900 less than that of (adaptive) genetic algorithm with adaptive probabilities and genetic algorithm with diversity-guided mutation, and the adaptive genetic algorithm with diversity-guided mutation does not lead to premature convergence. It is also shown that the better balance between overcoming premature convergence and quickening convergence speed can be gotten.

Two new predictor-corrector algorithms for second-order cone programming

Based on the ideas of infeasible interior-point methods and predictor-corrector algorithms, two interior-point predictor-corrector algorithms for the second-order cone programming （SOCP） are presented. The two algorithms use the Newton direction and the Euler direction as the predictor directions, respectively. The corrector directions belong to the category of the Alizadeh-Haeberly-Overton （AHO） directions. These algorithms are suitable to the cases of feasible and infeasible interior iterative points. A simpler neighborhood of the central path for the SOCP is proposed, which is the pivotal difference from other interior-point predictor-corrector algorithms. Under some assumptions, the algorithms possess the global, linear, and quadratic convergence. The complexity bound O（rln（εo/ε）） is obtained, where r denotes the number of the second-order cones in the SOCP problem. The numerical results show that the proposed algorithms are effective.