Searching the Hyper-heuristic for the Traveling Salesman Problem with Time Windows by Genetic Programming
This paper focuses on the solving constrained traveling salesman problem with time windows indirectly by finding useful hyper-heuristic via genetic programming. Resulting hyper-heuristic represents calculation of city priority along the traveling salesman
- PDF / 428,077 Bytes
- 8 Pages / 439.37 x 666.142 pts Page_size
- 84 Downloads / 241 Views
Abstract. This paper focuses on the solving constrained traveling salesman problem with time windows indirectly by finding useful hyper-heuristic via genetic programming. Resulting hyper-heuristic represents calculation of city priority along the traveling salesman path. The influences of different city properties (position in the Cartesian coordinate space, sum of distances to the n nearest cities, polar angle from the beginning of the coordinate system, etc.), math functions (addition, subtraction, division, sine, cosine, tangent) and penalty functions are tested. Trigonometric functions have no positive influence, best results are achieved with Cartesian coordinates and sum of distances to the n nearest cities. Polar angle gives more diverse solutions. Resulting hyperheuristics are good on training sets. When they are tested on another datasets, they find relatively short paths, but there are problems with respecting constraints in the form of time windows. Keywords: Genetic programming Hyper-heuristics problem with time windows Encoder
Traveling salesman
1 Introduction Uninformed search methods applied to some combinatorial problems work with very large state space [1]. The application of heuristic and metaheuristic methods for finding solutions to combinatorial problems is a relatively effective method of making such a search more efficient. This paper focuses on the traveling a salesman problem with time windows (TSPWT) and on the design of a state space encoder which transforms state space of possible traveling salesman’s paths into a heuristic state space search, where optimal traveling salesman’s path is found indirectly by finding rules for arranging cities along the traveling salesman’s path. The first part of the paper focuses on the use of genetic programming, heuristics and traveling salesman problem. The second part deals with use of genetic programming to find useful hyper-heuristic for TSPWT and describes performed experiments. Finally, we added an evaluation of our experiments and a summary of the achieved results and acquired knowledge. We also investigate whether the resulting hyper-heuristic is transferable to other datasets. © The Editor(s) (if applicable) and The Author(s), under exclusive license to Springer Nature Switzerland AG 2020 R. Silhavy et al. (Eds.): CoMeSySo 2020, AISC 1294, pp. 939–946, 2020. https://doi.org/10.1007/978-3-030-63322-6_81
940
V. Hrbek and J. Merta
2 Background 2.1
Genetic Programming
Genetic programming was introduced by Stanford computer scientist John R. Koza. This method is an extension of genetic algorithms that can develop programs through evolution. Program structures are represented by the chromosomes in the form of syntactic trees. The genetic alphabet consists of a set of non-terminals (functions) and terminals (constants, variables, random numbers) [2, 3]. Genetic programming has a similar mechanism to genetic algorithms. In the first step an initial population of randomly generated syntactic trees is created. Then the individuals are evaluated using
Data Loading...
