Hyper-mutation antibody clone algorithms for TSP

According to the analysis of the affections of the coding strategies and the basic operators, including crossover and mutation, we find that the schema theory can not analyse the Genetic Algorithm very well when it is used to solve the Traveling Salesman Problems (TSP). Because the non-binary coding strategy and the crossover overly destroy the TSP path, the good schema of the parents can not be inherited effectively. In order to overcome the above shortcoming of the Genetic Algorithm, a new artificial immune system algorithm for TSP, Hyper-mutation Antibody Clone Selection Algorithm (HACSA), is put forward in this paper. A new triangle-based path representation is adopted, and some heuristic mutation strategies based on the triangle coding method are also designed. The antibody clonal selection theory of immunology is used to enhance the local search performance of the antibody. Both HACSA algorithm and the corresponding genetic algorithms are implemented to the typical traveling salesman problems respectively. Experiments indicate that HACSA, behaving as an evolutionary strategy, is shown to be capable of solving complex machine learning tasks effectively like TSP. The experimental results show that HACSA can achieve or exceed the known optimal solution in over 60% problems, but that almost all the corresponding immune system algorithms and genetic algorithms fall into the local maximum, and they can not lead to the satisfied solutions.