一种求解TSP初始化种群问题的方法

Method for initial population of TSP

为提升求解TSP问题的计算效率和求解精度,针对初始种群构造问题进行研究,提出了域内三角概率选择自适应邻域算法。为使邻域半径能够适应城市的分布情况,设计了一种基于Sigmoid函数的邻域半径自适应函数;为了避免在邻域内盲目随机地选择下一站城市,提出了在邻域内利用三角概率选择模型选择下一个城市。以自动化立体仓库安排出入库作业顺序优化作为TSP研究问题,通过Matlab仿真计算,将该算法和邻域法生成的初始种群进行对比分析,并分别用该算法和随机生成的初始种群作为遗传算法的初始种群进行计算。证明了该算法可快速生成高质量的初始种群,大大提升了求解TSP问题的计算效率和求解精度。

In order to improve the computational efficiency and solution accuracy of the TSP problem, Field Triangular Probability Choosing Adaptive Neighbor-hood Algorithm(FTPCANA)is proposed to solve the problem of initial population construction. To make the neighbor-hood radius adapt to the distribution of the city, a neighbor-hood radius adaptive function based on Sigmoid function is designed. Besides, the next city is selected by using the triangular probability selection model in the neighbor-hood, which can avoid the blind and random selection of the next station. The optimization of the storage operation sequence is selected as the research problem of TSP. Based on Matlab simulation, the initial population generated by the proposed algorithm is compared to the initial population generated by the neighbor-hood method.The two initial populations, one of which is generated by proposed algorithm, and the other is randomly generated, are respectively calculated by genetic algorithm. It is proved that the algorithm can quickly generate high quality initial population,which greatly improves the computational efficiency and accuracy of solving the TSP problem.