| Based on the analysis of Simple genetic algorithm, the paper points out the disadvantages of simple genetic algorithm in the aspects of slow convergence speed and being unable to converge to the optimum solution and puts forward on improved genetic algorithm, that is , multi-species competition genetic algorithm. With competition among different species as its background the improred algorithm use randomly produced species as initial species erery sub-species carries on its selection reproduction and rarition separately and indepedently the individuals after operator operation are arranged aaovding to their adaptability the superior individuals are costantly used to replace the interlor ones we can expand the searching scope for speaes make the number of the comparatively improre continuously at last we can converge to an optimum solution. The implementation process of the algorithm is as following: For a specific question we can have N ( N≥2) sub-species at random every sub-species contains n individuals every sub-species can be treated individually with different genetic operations. The operators of these genetic operations differ greatly in installing characteristics. Then we can give some treatment for the results of N sub-species after algorithm operation till the constraint condition is reached. (1)According to the characteristic of the question, determining the length of binary code, producing N ( N≥2) sub-species randomly, every sub-species containing n individuals. (2) Give every independent sub-specie different selection, crossing and radiation operations. Recording the result to array R [i , j] (i = 1, L ,N, j=1, L, N). Calculating every individual adaptation value and recording them to array A[ i , j] (i = 1, L ,N, j=1, L, n). (3) Arranging A[ i , j] (i = 1, L ,N, j=1, L, n)according to its adaptation value, recording then as array B [i ] ( i = 1,L ,(n ?N)) from big to small. Then calculating the generalized Hamming distance H between neighbouring individuals. When the values of His smaller than the value value d , deleting the individuals whose adaptability is comparatively smaller, replacing them with the first individual B [1 ] in B [i ], and so on and so forth. Otherwise, keep the two individuals and add the intermediate species. (4) For the intermediate species got in the step 3, We can carry on step 2 and step 3 repeatedly till the satisfactory result is reached. Through theoretical clarification, We can see multi-species competition genetic algorithm complies with the pattern theorem of genetic algorithm. So it can insure the convergence of algorithm under probability. Its convergence is superior to simple genetic algorithm. The convergence speed of the algorithm is a little slow at the beginning operation, but there is an obvious increase in speed on the later stage .Its general convergence speed is superior to simple genetic algorithm. The algorithm flow diagram of multi-species competition genetic algorithm is given. It gives simulated operation to typical function and engineering example by the use of Matlab lanuage.The result indicates that the improved algorithm put forward in the paper can supply the lackings of the simple genetic algorithm. The treatment toward thr questions is suitable and the result meets our expectation. The empirical equation of value d is put forward. d k (l O ( h ))(1 t) (k 1.0)= ? ? T< It can be better control the execution speed and convergence of the algorithm. There is a great flexibility for the selection of d . Through simulated experiment, we can see the d got from above equation is effective in controlling the progress and convergence. Optimisation is an old question. People's discussion on its theory and methods never stops, Obviously, the multi-species competition genetic algorithm is great help in dealing with discrete, multi-objective and non-linear optimum questions. This algorithm can be used in the field of engineering, economics and operational research for the treatment of optimisation.
|
PDF Full Text Request