Research On Schema Characters In Genetic Algorithm

Genetic Algorithm is a simulated evolutionary algorithm, which shows the natural selection character of "superior win and inferior wash out, the fittest survives". By selection crossover and mutation, it makes the population evolve to the best. It has a good quality of robustness and self-adaptation. Now it has been already successfully used in many fields and been a hot research point. But as for the application, the GA's theory is not perfect and its development is very slow, which hinders the further development of application. The paper carries on a thorough study and system research in view of genetic algorithm's schema nature part, the main achievements are as follows:1. Basing on Bethke's early work, Goldberg advanced competitive schema to study deceptive functions, through which to analyze its complexity. But the measuring method is not proper enough, so the paper gives a new measuring method of deceptive functions, which is schema competitive degree. It gives some characters, proves the connections between competitive degree and important schema. By using competitive degree, it rationally explains how the GA solves two representative functions. As for the problem of the complete deceptive functions, the paper uses schema competitive degree to deeply analyze the schema. It discusses the schema competitive condition during the solution of a class of complete deceptive functions. To complete deceptive proportion's defect, it advances one order main deceptive degree to measure schema deception of complete deceptive functions, proves its rationality by using representative functions. And based on the peculiarity of schema competitive condition, it defines hard complete deceptive functions, also gives its characters.2. According to the specific characters of TSP and monitoring the spirit of neighborhood search, the paper advances a new genetic algorithm solution basing on the nearest neighbor strategy to solve TSP. First, it calculates the nearest neighbor schema according to the TSP and uses the schema to generate the initial population, and then introduces the schema randomly into every generation. The new algorithm can dramatically decrease searching space, shorten calculating process, and improve efficiency. Simulation tests prove it superiority which has also made a deep analysis theoretically.