Skeleton-Fat Fusion Algorithm And Its Application On TSP

Skeleton calculation and fat calculation has been the latest one of TSP algorithm study.Skeleton refers to the intersection of all global optimal solution variables in problematical instances. Local optimal solution of TSP intersection is much similar to skeleton, so the inter section of local optimal solution can be as the similar skeleton.While fat refers to variable set that do not belong to any of global optimal solution. And the basic idea of fat calculation is to gain fat and remove it from instances in order to reduce research space.Obviously, in the purpose of “reduce research space,”SA and FA are the same,but the differences is to adopt two different technical routes: skeleton technical routes is intersection extension,and fat is extrusion of complementary set. However,extrusion of complementary set has a insuperable boundary,that is union set. Fat is complementary set as union set extruded by fat. Skeleton calculation is within complementary set,while fat remains beyond complementary set. Therefore,complementary set is the rendezvous of the two algorithm.The final result of algorithm iteration is that union set and complementary set tends to be similar, which is very interesting. Based on this view,new thoughts of SFFA is produced.That the paper introduces SFFA is based on SA algorithm and FA algorithm. First by random 3opt algorithm emerge initialized elite solution,by whose complementary set produce skeleton. Skelton as TSP lag is reserved to directly join in the next generation of elite solution.Then generate fat through union set of elite solution. Fat network diagram remains as the research space of next generation of elite solution, and use certain strategy based on the edge frequency to produce new elite solution in the fat network diagram. Finally conduct the union set and complementary set until find all skeleton forming complete Hamiltonian circuit. In the process of iteration,calculation speed of algorithm improved much as the increase of skeleton and decrease of fat.In traveling salesman problem(TSP), TSP and sets is identified by union calculation of edge of some elite routes and realize the shift from uncertain space to certain one. Also,the union set calculation of the edge in these routes provide a dynamic and shrinking research space to effectively decrease the time complexity of algorithm. The experimental results reveals that the convergent performance of algorithm make more obvious progress than traditional algorithm in quality or time. TSP as benchmark platform in testing algorithm performance fully proves the effectiveness and feasibility the model.Identifying TSP set and edge, algorithm provides possibility of exploring explosive andnegative growth of solution space in big scale TSP, which offers a thought to solve combination explosive problem.For reasons of time, to do more in-depth study of fat algorithm is late, so the fusion of the two algorithms is not enough deep described, studing fat algorithm is the direction of efforts in the future.