Good Point Set Genetic Algorithm Theory And Application

Genetic Algorithms (GA) are optimization algorithms imitating biological evolution with computers. They were first put forward by Holland in University of Michigan in 1975. With the fixed population size, GAs only use fitness value to guide searching and regenerate population through executing genetic operations such as selection, crossover and mutation with probability. Thus the GAs are in fact a "Blind heuristic searching strategy with probabilities" Because of their simplicity, flexibility, and being prone to parellel computing, they are widely used in various fields.In the thesis, the applications of Number-theoretic methods in statistics are introduced. On the basis of the good-point set theory, the crossover operation in GA is redesigned. Then a new GA called good-point set GA is presented. The new algorithm is applied to some typical combinatorial optimization problems such as knapsack problem, TSP problem, etc. Being compared with traditional GA, the satisfied emulation results show that the good-point set GA not only improves efficiency and accuracy, but also effectively avoids the pre-rnaturity.The method of how to get a set of test samples for any given NPC problems is discussed. Using this test set, the computational capability and complexity of the NPC problem can be estimated reasonably, so this test set can be used to analyze the inferior or superior of the algorithms. On the basis of the good-point set theory, the way to make test set of the algorithm is presented. Finally, some test sets are given for TSP and knapsack problem.The thesis consists of five chapters. Chapter 1 briefly introduces the GAs?principle,I..characteristics an(I developing progress. Chapter 2 discusses the applications of Number4lieoretic methods in statistics, amid l)reselitS an effective way to produce theNT-net on C+ , that is good-point set method. Chapter 3 describes the fundamentaldefinition and propeity of good-point set, and improves the crossover operation to get the good-point set GA. Chapter 4 analyzes the implementation and the test results of the good-point set GA applied in knapsack problem and TSP. Chapter 5 presents the way to make test set of the algorithm, and gives some instances.