求解TSP问题的三角形编码抗体克隆选择算法

Hyper-mutation antibody clone algorithms for TSP

在探讨遗传算法求解TSP问题中编码方式和交叉、变异算子作用特点的基础上,发现模板理论已经不能很好地适应TSP问题,主要是因为非二值符号编码和交叉算子对边的过度破坏导致子代难以继承父代的优良模式.为了克服上述问题,提出一种三角形表示的路径编码方案,并给出相应的启发式路径搜索策略;引入生物免疫系统的克隆选择机理加强局部搜索,进而构造一种适合TSP问题求解的人工免疫系统算法———超变异抗体克隆选择算法(HACSA).典型TSP问题的求解表明,和Endoh等人的免疫算法和遗传算法相比,HACSA的计算复杂度相当,60%以上的求解结果达到或者超过问题已知的最优值,而相应的免疫算法和遗传算法几乎均陷入局部极值,无法获得满意的求解结果.

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.