Research On An Immune Genetic Algorithm And Its Application On Tsp

Genetic Algorithm (GA) is a kind of search algorithm which simulates natural biological evolution. It is simple, strong robust and easy to implement, especially it doesn't need the special knowledge, but only to direct the search process with fitness function, so it has been used in many broad fields. But some major drawbacks such as premature convergence, low local search ability and slow speed of convergence will occur when GA is used in solving practical engineering optimal problems. Based on studying these problems deeply, a few points of innovative achievements will be proposed in this paper.1. According to some excellent features of biological immune system, a novel algorithm framework called Immune Genetic Algorithm (IGA) based on vaccine immune concentration regulation mechanism is proposed, which incorporates some functions of Artificial Immune Algorithm (AIA) such as immune memory, diversity maintaining, self-adjustability and metabolism. The performance of IGA proposed is theoretically analyzed, including global convergence analysis with Markov chain and schema increasing analysis. It is proved that IGA maintaining the best individual can converge to the global optimum with probability 1. IGA schema theorem is achieved after the concept of Average Concentration Threshold is proposed, which concludes that immune operation can accelerate the speed of better schema.Put the IGA framework proposed to the application of Traveling Salesman Problem (TSP), and MATLAB simulation experiment is conducted to test the cities of benchmarks in TSPLIB. The comparative results show that searching results and convergence speed of IGA are both better than that of SGA, and it is verified feasible and effective. A definition of diversity evaluative function is proposed, and the diversity maintaining ability of IGA is verified to overcome the shortcomings of premature convergence and local optimum of GA.2. As to slow running defect of AIA based on information entropy, the reason that affects its running speed is analyzed. After studying the calculation process of entropy deeply, a method of accelerating the running speed of computing population information entropy is developed. Simulation results show that the method can improve the running speed of AIA enormously.3. As to the characteristic of TSP, combining the greedy idea of Heuristic Crossover (HX) with the double edge idea of Edge Reorganization Crossover (ER), a new crossover operator -double edge greedy crossover operator (DEGX) is proposed. Simulation results show that searching results and convergence speed of DEGX are both better than that of HX and ER. Thus, DEGX can effectively enhance the local searching abilities and accelerate convergence speed.