用带有免疫思想的改进遗传算法求解TSP问题

摘要

旅行商问题(TravelingSalesmanProblem,简称为TSP)是一个典型的组合优化问题,并且是一个NP完全问题,其可能的路径数目为(n-1)!,至今尚未找到有效的解决办法.虽然在理论上可以采用枚举法来解决这一问题,但是当n较大时,实际所需的时间会大到使对此问题的求解变得毫无意义.因此设计出一种时间多项式算法来求得TSP问题的最优解或近似最优解就具有重大的意义.TSP问题是经典NP完全问题，也有很多的实际应用。本文提出将免疫的思想引入遗传算法中求解TSP问题，既避免了同类中优秀个体的丢弃，又很好地保持了个体的多样性。因此该算法对于求解具有多个离散变量的优化问题及多结点的网络问题等一些工程中存在的问题具有很好的实用价值。