一种求解TSP问题的改进人工免疫算法

Modified Artificial Immune Algorithm for TSP

TSP(旅行商)问题作为经典的组合优化问题,已经被证明是一个NP难题。文中提出一种基于改进的人工免疫算法的TSP求解方法。算法模拟了抗体的蛋白质多肽链结构、免疫系统的克隆选择机制以及浓度调节机制,使用了一种新的抗体间的相似性判断方法。另外,在算法的变异算子中还融合了贪婪算法。这些改进使得算法的搜索性能得到提高。实验结果表明与标准遗传算法相比,该算法全局搜索能力强、收敛速度快。

Traveling Salesman Problem（TSP） is a classic combined optimization problem and it is proved that TSP is NP hard. A modified artificial immune algorithm is proposed to solve it. The algorithm simulates the protein polypeptide structure of the antibody, the clonal selection principle and the density regulation mechanism of the immune system, and uses a new analytic approach for the similarity between the antibodies. Moreover, the mutation operator is added the greed algorithm. Those progresses improve the search performance of the algorithm. The experiment results show that using this algorithm in TSP have better global search ability and faster convergence speed than using the standard genetic algorithm.