Genetic Algorithm With Fitness Estimation And Its Application

Genetic Algorithm based on Darwin's Evolutionary Theory and Mendel's laws of inheritance is a kind of optimization algorithm which aims to solve the complex global optimization problems. It was put forward by John Holland who was in the University of Michigan of United States during 60's of 20th century. For the obvious advantages of high ability in getting global optimization, adaptive search and robust, and so on, it is used in function optimization, structural optimization, artificial intelligence, machine learning and other field widely.The individual fitness is importance of making the algorithm converge to the global optimal solution effectively when using genetic algorithm to solve optimization problems. But for some engineering problems, the real evaluation of individual fitness always takes long time to calculate or costs a lot of money. For example, the structural optimization designing, geological model parameter optimization, design of missile parameters, crystal structure optimization and so on. In the crystal structure optimization problem, the cell parameters, atomic number and atomic positions are given to simulate the crystal structure by using molecular dynamics. Time-consuming problem means that a high-performance computer runs a few hours or hundreds of hours for simulating a structure. The classical genetic algorithm evaluation the fitness based on the population which greatly restricts the application of genetic algorithm in the time-consuming problem. So in this paper, a new method of evaluation fitness is put forward which combines genetic algorithm and clustering algorithm and uses class center of cluster algorithm to evaluate other individual's fitness.At the beginning of this article, it describes the background of genetic algorithm, development history and its application. Genetic algorithm consists of coding, fitness calculation, selection, crossover and mutation. Then in the second chapter of the article, there will be a simple introduction about these five parts.Clustering algorithm contains five methods which are division, level, based on density, based on grid and based on model. The k-means clustering algorithm is the earliest, the most widely used and simple clustering algorithm. K-modes are the derivation of k-means which is used to solve the discrete clustering problems. There is another typical maximal tree clustering method which is based on the smallest connected graph. Affinity Propagation(AP) Clustering algorithm which is based on the nearest neighbor information dissemination clustering algorithm, the purpose is to find the set of optimum exemplars(One exemplar corresponds to one data point of the real data set) to make the sum of similarity between exemplar and the closest data point be the largest. Because it can get a better clustering result, and it needs few parameters, it is used widely. AP Clustering Algorithm needs two parameters, one is the similar matrix, and another one is the disturbance factor. By updating the responsibility and availability matrix to get a steady clustering result.By researching the genetic algorithm and clustering algorithm, this article combines genetic algorithm and AP clustering algorithm to get a new algorithm, called as APGA. Base on the APGA we propose the APGA algorithm with individual model algorithm; firstly we should identity the individuals of the current groups which have the real fitness to make pattern model discovering operation, according to the typical model which are contained by the individuals to modify the fitness that gotten by the estimation, then it will get a better result. The numerical simulation shows that the optimization of standard test function and the optimization of the crystal structure under this method have gotten better results.