外文翻譯--具有基于多樣性的變異因子的自適應(yīng)遺傳算法及其全局收斂性（英文）

1、Vol. 11 No. 3 J. CENT. SOUTH UNIV. TECHNOL. Sep. 2004 A r t i d e I D : 1 0 0 5 - 9784(2004)03 - 0323 - 0 5 An adaptive genetic algorithm with diversity-guided mutation and its global convergence property LI Mei-

2、yi(~J~]t~),CAI Zi-xing(~. I~I~),SUN Guo-yun({~l~l~) (College of Information Science and Engineering, Central South University, Changsha 410083, China) Abstract: An adaptive genetic algorithm with diversity-guided mutat

3、ion, which combines adaptive probabilities of crossover and mutation was proposed. By means of homogeneous finite Markov chains, it is proved that adaptive ge- netic algorithm with diversity-guided mutation and gen

4、etic 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 mutat

5、ion 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 con- vergence generation

6、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 ad

7、aptive 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 ca

8、n be gotten. Key words: diversity-guided mutation; adaptive genetic algorithm; Markov chain; global convergence CLC number: TP18 Document code: A 1 INTRODUCTION It is known that the performance of the genetic algori

9、thms (GAs) is dependent upon the operator probabilities used. Adaptability of opera- tor probabilities is an attempt to make the genetic algorithm a more effective optimizer. By adopting adaptive operator probabilities s

10、ome benefits, such as increasing the quality of the obtained solutions and allowing the GAs to find a solution of given quality more quickly, can be attained. Therefore, by employing some methods, some researchers at- t

11、empted to automatically adjust the operator proba- bilities according to the quality of solutions E'-33. It is also known that the premature convergence is a major problem in GAs and adaptive genetic algo- rithms m

12、ay lead to premature convergence Eq. In order to overcome the premature convergence, the term “diversity“ is employed. Diversity is closely related to the performance of GAs, especially when attempts are made to avoid

13、premature convergence and escape local optima. A few researchers C 5 - 8 3used diversity measure to control the search direc- tion of evolutionary algorithms. By means of mixing adaptive crossover and mutation of Sri

14、nivas c'3 with diversity-guided muta- tion and modifying adaptive crossover stratagies, an adaptive genetic algorithm with diversity-guided mutation(AGADM) was developed. It is proved that AGADM and genetic algorit

15、hms with diversi- ty-guided mutation(GADM) will converge to the global optimum when maintaining the best solution by homogeneous finite Markov chains, but adap- tive genetic algorithms with adaptive probabilities of cros

16、sover and mutation (AGA) do not always do so. The performances of AGA, GADM and AGADM were compared. 2 P~L~IN~Y Genetic algorithms are used to tackle static optimization problem. There are N individuals (candidate so

17、lutions) within the population, which can be expressed as binary strings of fixed length l: gilgiz'“git, (g~j=O,l,j=l,2,'“,l, i=1,2,-“, N) and the correspond fitness values are { fi 10 fi<oo, i=l,2,...,N}. D

18、efinition 1 Let Zt be a sequence of random variables which represent the best fitness within a population represented by state i at step t, and f“ he the global optimum of the problem. If limp(Z,=f“ )=1 (1) t--~ then

19、 a genetic algorithm converges to the global optimum solution. In the implement of GAs, if the best fitness values in the population are not improved in Ng~ generations, the algorithm will go to the end, which is often t

20、he convergence critical. The con- vergence speed is the generation (terminal-genera- tion) that GA runs before the convergence criterion ® Foundation item: Project (60234030) supported by the National Natural Scien

21、ce Foundation of China Received date: 2003 -09 -08; Accepted date: 2003 - 12 - 12 Correspo~ence:LI Mei-yi, Doctoral candidate; Tel: +86-731-8830583; E-mail: meiy_li(~yahoo, com. eta LI Mei-yi, et al.. An adaptive genetic

22、 algorithm with diversity-guided mutation and its global convergence property ? 325 ? the other is bad, then the bad one has more chance to achieve some building-blocks of the good indi- vidual, and the average fitness

23、of the population will become greater. Hence convergence speed will be greater (perhaps the algorithm converges to lo- cal minima). In order to overcome premature convergence a diversity measure to alternate between expl

24、oring and exploiting behavior is used. A diversity measure for N-dimensional numerical problems is defined as: l N 1 N(~a(gl,J--gi) z)a/z, I S I is wherep(j) -- I S~ i=1 the length of the diagonal in the search spac

25、e SC N t , gi,j is the value of the jth gene-bit in the ith in- dividual and gi is the jth gene-hit value of the aver- age point, N and l are the size of population and the length of a individual, respectively. 4 MARKO

26、V CHAIN ANALYSIS OF AGADM and GADM The adaptive genetic algorithm with diversity- guided mutation (AGADM) and the genetic algo- rithm with diversity-guided mutation (GADM) can be described as a Markov chain, whose finite

27、 state space is A= {0,1} iN of cardinality IAI =lN. The probabilistic changes of the individuals within the population caused by AGADM or GADM are cap- tured by the transition matrix P, which can he de- composed in a nat

28、ural way into a product of sto- chastic matrices P=CMMaS for AGADM and P= CMS for GADM, where C, M, Ma and S stand for the intermediate transition matrices caused by crossover with adaptive probabilities, mutation with

29、 diversity-guided mutation probabilities, mu- tation with adaptive probabilities and selection, re- spectively. So, the following results can be ob- tained. Theorem 2 If diversity-guided mutation prob- ability 0~pm~l, a

30、daptive mutation probability 0~pm(i)~l and adaptive crossover probability p¢(i,j)E[O,1], the transition matrix of the AGADM with proportional selection is primitive. Proof The crossover operator may be regar-

31、 ded as a random total function whose domain and range are A, ie, each state of A is mapped probabi- listically to the other state. Therefore, C is sto- chastic. The same holds for other operators and their transition ma

32、trices. Because the mutation op- erator is applied independently to each gene-bit in the population, the probability for state i to be- come state j after diversity-guided mutation can be aggregated to : mio “=pnmi'J

33、 (1--Pro) l-“i'j ~0, where Hi# denotes the Hamming distance between the binary representations of state i and state j. After mutation with adaptive probability, the diagonal elements in Mr, are pi,i=(1--pm(i) )l~O.

34、 Thus M is positive, and M, diagonally positive. Since S is column allowable E~°l , by lemma 1, P= CMM, S is positive. Since every positive matrix is primitive, the proof is completed. Corollary 1 The AGADM is an

35、 ergodic Markov chain, ie, there exists an unique limit dis- tribution for the state of the chain with nonzero probability to transformed to other state at any time regardless of the initial distribution. If M is replace

36、d with MM, of the theorems 6 and 7 in Ref. [10], the proof of the theorems 6 and 7 in Ref. [10] holds. So the following results can be obtained. Theorem 3 If AGADM maintains the best so- lution found over time after/be

37、fore selection, it will converge to the global optimum. If all the adaptive mutation probabilities k7 =- 0, ks = 0 and k6 = 0, AGADM will become GADM. From theorem 3 we have the following results. Corollary 2 If GADM ma

38、intains the best so- lution found over time after/before selection, it will converge to the global optimum. As shown in Ref. 1-11], although AGA pro- posed by Srinivas m is a Markov chain, if the best solution is not ma

39、intained, it will not converge to the global optimum. But if it maintains the best solution which is found over time after/before se- lection, since the transition matrix of AGA is not positive(the mutation probability o

40、f the best indi- vidual is 0), the result of convergence to the global optimum from the finite Markov chain theorem can not be inferred. 5 EXPERIMENTS In order to compare AGADM with AGA and GADM, one unimodal and two mu

41、ltimodal func- tions with varying complexities were employed as follows. Quaflrie For a unimodal function with signi- ficant interaction between its variables, the global maximum is located at f(0,0,... ,0)= 0. f(Xl, X