The Efficiency Of Genetic Algorithm Research

Genetic Algorithms(GAs) originate from natural selection and genetics. They have been applied in many areas of search, optimization, and machine learning, such as the well-known traveling salesman problem, scheduling problem, optimization of Steiner trees, and establishing the initial points of a neural network. As practical applications in VLSI circuit design, GAs were used for gate-array placement, standard-cell placement, and compaction of symbolic layout. Today, GAs have engaged the curiosity of many different research communities including researchers in Computer Science, Engineering, Economics, Political Science, Psychology, Linguistics, Immunology, Biology and Mathematics. As stochastic search algorithms, GAs are general-purpose, simple and efficient. Because of its implicit parallelism, GAs can search complex problem space efficiently.In this thesis, GAs' basic mechanism and their history are outlined and retro spected. My major research work is about how to improve the performance of GAs. Using heuristic techniques with problem domain knowledge, GAs can be of great efficiency to specific problems. Two new heuristic operators(Ncrossover and Nmuta tion) for 3-SAT problems, and three new heuristic operators for the traveling salesman problems(TSPs) are designed. Moreover, a set of new general operators(VOTE and NVOTE) are designed, which paralleled with the ordinary operators(crossover and mutation).Since weakness of GAs for local search is well acknowledged, this thesis also examines hybridization of GA and local search mechanisms, and proposed that combination of multiple local searchers and GA as a general architecture of the hybrid GA. Through all these improvement, in experiments on 3-SAT problems, it outperforms the known algorithms. In experiments on the typical 100-city TSP, it can obtain the optimal solution. In the experiments on the well-known 318-city and 532-city TSP, it can obtain near optimal results, only 0.05% and 0.6% longer than the optimum respectiely. Such results have not been seen in publications yet. In the final part, GA's parallel implementation is analyzed.