Font Size: a A A

Improvement And Parallelization Of Real-Coded Genetic Algorithm For Function Optimization Problems

Posted on:2020-09-10Degree:MasterType:Thesis
Country:ChinaCandidate:X F WangFull Text:PDF
GTID:2428330596985121Subject:Computer Science and Technology
Abstract/Summary:PDF Full Text Request
In daily production and life,there are various optimization problems,such as find out the "shortest path" to arriving a certain place or the "maximum utilization rate" of a certain resource and so on.The usual method is to transform these problems into function optimization problems by mathematical modeling.Since the optimization problem of the required solution is various,the objective function formed by mathematical modeling will present various mathematical features.At this time,it is difficult to solve the problem by using the mathematical solution.The real-coded genetic algorithm has been widely used in functional optimization problems since it was put forward,because of its simple structure and not constrained by specific problems and high precision.However,the real-coded genetic algorithm has the disadvantages of easy to fall into local extremum and slow convergence rate in the process of function solving.Moreover,in solving complex high-dimensional functions,the initial population size required by the algorithm is very large.This lead to the calculation time of the algorithm to be too long.In order to solve the above problems,the improvement and parallelization of real-coded genetic algorithm are studied.The main work is as follows:1.In order to avoid premature phenomenon of real coded genetic algorithm and enhance the local search ability and convergence of the algorithm,the improvement measures of the algorithm are given.Firstly,a new crossover operator is proposed which can ensure that the progeny chromosome generated after the crossover has a higher fitness values than its parent chromosome.Secondly,the mutation strategy of the traditional mutation operator is changed so that it only mutates the chromosomes with low fitness value in the population.Finally,based on the adaptive change of crossover rate and variance rate proposed by predecessors,the consideration of evolutionary algebra of the algorithm is increased,which makes the value of crossover rate and variation rate more reasonable and effective.2.In order to reduce the computational time of real coded genetic algorithm in solving complex high dimensional functions,the improved algorithm is implemented in parallel basedon GPU.The parallelization of the algorithm is embodied in five aspects: the parallelization of population initialization,the parallelization of the computation of fitness value,the parallelization of crossover operator,the parallelization of mutation operator and the parallelization of chromosome ordering in population.By solving the functions of different dimensions,the results show that compared with the serial program of CPU version,the algorithm based on GPU parallelization can reduce the computing time of solving high-dimensional functions without losing the accuracy of the solution,and the higher the dimension of the function is,the larger the initial population size of the algorithm is,the stronger the performance of the graphics card is,the more obvious the acceleration effect is.
Keywords/Search Tags:Function Optimization, Real-Coded, Genetic Algorithm, Algorithm Improvement, GPU Parallelism
PDF Full Text Request
Related items