Research Of Traveling Thief Problem Based On Discrete Particle Swarm Optimization And Its Application

The Traveling Thief Problem(TTP)originates from the similar combination optimization problems that people encounter more and more in the various field of production practices,such as the synchronous reduction and sorting of test cases,limited arc routing with service profit,distribution of meals on wheels and taxi-healing on the internet.TTP problem is a combination of traveling salesman problem(TSP)and knapsack problem(KP).It combines the complexity of the two problems,and so far there is still no high-performance deterministic method to solve it.As a typical swarm intelligence algorithm,discrete particle swarm optimization is easy to fall into some problems such as local optimal solution,particularity and complexity of combinatorial optimization.In view of these problems,the main research contents of this paper are as follows.(1)In order to improve the performance of discrete particle swarm optimization in solving TSP,this thesis proposes a perturbed algorithm inspired by the idea of gene editing,which can accelerate the population to jump out of the local optimum when the evolution of particle swarm stagnates.The perturbation algorithm takes the set as the particle coding unit and the elements in the set as the genes contained in the particle,and proposes the evaluation and editing strategy for the particle genes.Results of experiment simulation describe that the discrete particle swarm optimization with disturbance algorithm shows good performance.(2)Based on the heuristic experience of optimizing the distribution of goods and the improved particle swarm optimization algorithm,two methods,multi-objective particle swarm optimization and hybrid evolutionary algorithm,are proposed to solve the TTP problem.It can effectively reduce the rental cost to select the heavy goods near the end point.The multi-objective particle swarm optimization algorithm transforms this experience into a quantifiable optimization function for the distribution of goods.The TSP subproblem is composed of this function and the evaluation function for the length of the travel path.After obtaining the path,a new heuristic rule is used to solve the KP subproblem.Hybrid evolutionary algorithm is a mixture of improved discrete particle swarm optimization and genetic algorithm.Simulation experiments on the test set show that the two algorithms have strong competitiveness.(3)The problem of synchronous reduction and sorting of software test cases can be regarded as a typical application of TTP.In this thesis,discrete particle swarm optimization is applied to solve TTP.In the process of solving the problem,we designed the particle encoding method,the establishment and maintenance strategy of the non dominated set,and solved the data sparse problem that the particle encoding dimension is too high.Finally,the simulation experiment on the industrial test data set shows that the optimal solution set obtained by the algorithm has outstanding performance in the distribution HV index of the solution,and the obtained simplified test case set shows good representativeness and strong error detection ability.