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...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.展开更多
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.
An improved genetic algorithm (GA) is proposed based on the analysis of population diversity within the framework of Markov chain. The chaos operator to combat premature convergence concerning two goals of maintaining...An improved genetic algorithm (GA) is proposed based on the analysis of population diversity within the framework of Markov chain. The chaos operator to combat premature convergence concerning two goals of maintaining diversity in the population and sustaining the convergence capacity of the GA is introduced. In the CHaos Genetic Algorithm (CHGA), the population is recycled dynamically whereas the most highly fit chromosome is intact so as to restore diversity and reserve the best schemata which may belong to the optimal solution. The characters of chaos as well as advanced operators and parameter settings can improve both exploration and exploitation capacities of the algorithm. The results of multimodal function optimization show that CHGA performs simple genetic algorithms and effectively alleviates the problem of premature convergence.展开更多
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 conditio...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.展开更多
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 theconstructio...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.展开更多
The identification and characteristics of premature convergence in genetic algorithms (GAs) are investigated Through a detailed quantitative analysis on the search capability and the degree of population diversity, th...The identification and characteristics of premature convergence in genetic algorithms (GAs) are investigated Through a detailed quantitative analysis on the search capability and the degree of population diversity, the cause of premature convergence in GAs is recognized, and attributed to the maturation effect of the GAs: The minimum schema deduced from current population, which is the largest search space of a GA, converges to a homogeneous population in probability 1 ( so the search capability of the GA decreases and premature convergence occurs). It is shown that, as quantitative features of the maturation effect, the degree of population diversity converges to zero with probability 1, and the tendency for premature convergence is inversely proportional to the population size and directly proportional to the variance of the fitness ratio of zero allele at any gene position of the current population. Based on the theoretical analysis, several strategies for preventing premature convergence are suggested A specific GA formulation that converges assuredly to the global optimum without appearance of premature convergence is proposed.展开更多
Evolutionary Computation(EC)has strengths in terms of computation for gait optimization.However,conventional evolutionary algorithms use typical gait parameters such as step length and swing height,which limit the tra...Evolutionary Computation(EC)has strengths in terms of computation for gait optimization.However,conventional evolutionary algorithms use typical gait parameters such as step length and swing height,which limit the trajectory deformation for optimization of the foot trajectory.Furthermore,the quantitative index of fitness convergence is insufficient.In this paper,we perform gait optimization of a quadruped robot using foot placement perturbation based on EC.The proposed algorithm has an atypical solution search range,which is generated by independent manipulation of each placement that forms the foot trajectory.A convergence index is also introduced to prevent premature cessation of learning.The conventional algorithm and the proposed algorithm are applied to a quadruped robot;walking performances are then compared by gait simulation.Although the two algorithms exhibit similar computation rates,the proposed algorithm shows better fitness and a wider search range.The evolutionary tendency of the walking trajectory is analyzed using the optimized results,and the findings provide insight into reliable leg trajectory design.展开更多
文摘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.
文摘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.
基金The National Natural Science Foundation of China !(No .699740 43 )
文摘An improved genetic algorithm (GA) is proposed based on the analysis of population diversity within the framework of Markov chain. The chaos operator to combat premature convergence concerning two goals of maintaining diversity in the population and sustaining the convergence capacity of the GA is introduced. In the CHaos Genetic Algorithm (CHGA), the population is recycled dynamically whereas the most highly fit chromosome is intact so as to restore diversity and reserve the best schemata which may belong to the optimal solution. The characters of chaos as well as advanced operators and parameter settings can improve both exploration and exploitation capacities of the algorithm. The results of multimodal function optimization show that CHGA performs simple genetic algorithms and effectively alleviates the problem of premature convergence.
基金This work is supported by the National Natural Science Foundation of ChinaVisiting Scholar Foundation of Key Lab, in Univers
文摘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.
文摘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.
基金Project supported by the National Natural Science Foundation of China.
文摘The identification and characteristics of premature convergence in genetic algorithms (GAs) are investigated Through a detailed quantitative analysis on the search capability and the degree of population diversity, the cause of premature convergence in GAs is recognized, and attributed to the maturation effect of the GAs: The minimum schema deduced from current population, which is the largest search space of a GA, converges to a homogeneous population in probability 1 ( so the search capability of the GA decreases and premature convergence occurs). It is shown that, as quantitative features of the maturation effect, the degree of population diversity converges to zero with probability 1, and the tendency for premature convergence is inversely proportional to the population size and directly proportional to the variance of the fitness ratio of zero allele at any gene position of the current population. Based on the theoretical analysis, several strategies for preventing premature convergence are suggested A specific GA formulation that converges assuredly to the global optimum without appearance of premature convergence is proposed.
基金This work was supported in part by the National Research Foundation of Korea(NRF)Grant funded by the Korean Government(MSIT)(No.NRF-2019R1A2C2084677)the 2021 Research Fund(1.210052.01)of UNIST(Ulsan National Institute of Science and Technology).
文摘Evolutionary Computation(EC)has strengths in terms of computation for gait optimization.However,conventional evolutionary algorithms use typical gait parameters such as step length and swing height,which limit the trajectory deformation for optimization of the foot trajectory.Furthermore,the quantitative index of fitness convergence is insufficient.In this paper,we perform gait optimization of a quadruped robot using foot placement perturbation based on EC.The proposed algorithm has an atypical solution search range,which is generated by independent manipulation of each placement that forms the foot trajectory.A convergence index is also introduced to prevent premature cessation of learning.The conventional algorithm and the proposed algorithm are applied to a quadruped robot;walking performances are then compared by gait simulation.Although the two algorithms exhibit similar computation rates,the proposed algorithm shows better fitness and a wider search range.The evolutionary tendency of the walking trajectory is analyzed using the optimized results,and the findings provide insight into reliable leg trajectory design.
