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

Method for initial population of TSP

作　　者：李志宾[1] 侯世旺[2] 程厚虎 LI Zhibin;HOU Shiwang;CHENG Houhu(School of Mechanical and Power Engineering, North University of China, Taiyuan 030051, China;School of Business Administration, Huaihua University, Huaihua, Hunan 418000, China)

机构地区：[1]中北大学机械与动力工程学院,太原030051 [2]怀化学院商学院,湖南怀化418000

出　　处：《计算机工程与应用》2016年第17期172-176,共5页Computer Engineering and Applications

基　　金：山西省青年科技研究基金项目(No.2013021021-2);教育部人文社会科学研究青年基金项目(No.13YJC630049)

摘　　要：为提升求解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.

关 键 词：旅行商问题 初始种群 邻域法 三角概率 自适应函数 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]