摘要
TSP(TravelingSalesmanProblem)问题是最经典的NP-hard组合优化问题之一。长期以来,人们一直在寻求快速、高效的近似算法,以便在合理的时间内解决大规模问题。在文[5]提出的两交换启发交叉算子的基础上,通过分析,发现该算子的杂交结果与所选择的首城市有关,因而不同的首城市的选择会大大影响该算子的效率。为此,提出了一种新的有效利用局部信息的杂交算子,该算子能够有效的保存母体信息,进一步摆脱首城市的选择问题。实例仿真证明该算子的有效性。
The TSP (Traveling Salesman Problem) is one of the typical NP-hard problems in combinatorial optimization problem. The fast and effective approximate algorithms are needed to solve the large-scale problem in reasonable computing time. Based on 2-exchange crossover heuristic introduced by Tang Li-xin, whose efficiency is relation with the first city greatly, a new crossover operator is conducted using the local information effectively and being little relation with the first city. The optimization computing of some examples is made to show that the new crossover operator is useful and simple.
出处
《航空计算技术》
2003年第4期12-14,共3页
Aeronautical Computing Technique
基金
山西省自然科学基金资助(20031041)
