Realization of genetic algorithm for travel salesperson
Abstract: This paper gives a solution method of travel salesman's better solutions with the genetic algorithm, and implemented with C # language.
1. Description and correlation theorem for travel salesperson
In order to facilitate the discussion of Traveling Saleman Problem, referred to as TSP, first give some definitions in the chart theory:
Definition 1 After each vertex of Figure G is just once, it is called G's Hamilton, referred to as an H low.
Definition 2 in Weighted Chart G = (V, E)
(1) The smallest H low is called the best H low;
(2) The closed road with at least once and the smallest right is called the best salesman loop.
The question to be solved in this article is the best salesman loop to ask for weight maps. The problem with the best salesman circuit can be converted to the best H circle problem.
Set to the added weight map g = (v, e), use it to construct the full graph G '= (V, E') of V as a vertex set, where E 'is equivalent to each side (x, y) The length of the shortest path X to the vertex y is the length of the shortest path.
Arbitrary ∈E ', right
The related theorem is as follows:
Theorem 1 Weighted Figure G The length of the PLA loop is the same length as the length of the G ''s best H low.
The best H low problem in the weighted complete figure is NPC problem.
According to the aimer 1 We can translate the travel salesperson of any weighted map to the best H circle issues on its weighted complete graph. According to the aim 2, we know that the problem is looking for a multi-term time algorithm, we can only construct some promptly solved the problem of heuristic approximation algorithm.
2. Realization of Genetic Algorithm for Travel Salespeople Questions
2.1 Shortest path to any two vertices in the picture with the floyd-warshall algorithm
Floyd-Warshall Algorithm Steps:
Step0 k = 0; for all nodes i and j, order
(It can be considered
),
;
Step1 k = k 1; for all vertices I and J, if
, Then
Otherwise
;
Step2 If k == n, end; otherwise turn Step1.
The code is as follows:
: Number of vertices of Figure G
: The weight of the arc of the top I to J in Figure G
: Figure g The length of the shortest path of the top of the top of the top of the top of the top.
: Figure G Top i to j in the shortest path of the shortest path of the top K top point
Obviously,
It is the length of the shortest path of the vertices I to J.
Note: This algorithm is implemented by the FLOYD class under the namespace TSP.
2.2 Selection of Genetic Operators
In this article, the coding scheme we use may be the most natural expression - path expression of a travel. For example, a trip
5-1-7-8-9-4-6-2-3
Can be simply reached
(5 1 7 8 9 4 6 2 3).
The operation steps of genetic algorithms:
{
Random initialized population P (0), t = 0;
Calculate the individuality of individuals in P (0);
While (do not meet the conditions)
{
For (k = 0; k { Two processes were generated after two parent cross operations from P (T); Add these two descendants to the intermediate group P '(T); } Variation operations for each individual in the intermediate population P '(t); The selection operation is performed from P (T) and P '(T) to obtain N individuals to impart a new population P (T 1); the adaptation degree of each individual in P (T 1) is calculated; T ; } } According to the measured results, we only choose a few performance operators from many genetic operators. 2.2.1 Cross Operator The designer is constructed by a subsequence of the OX Operators in Davis - by picking a child sequence from one parent and saving the other parent city relative order. For example, two pharmaceuticals (cutting points are "|" tagged) P1 = (1 2 3 | 4 5 6 7 | 8 9) P2 = (4 5 2 | 1 8 7 6 | 9 3) The descendants will be produced in the following manner. First, the fragment between the cutting point is copied to the descendent: O1 = (x x x | 4 5 6 7 | X x) O2 = (x x x | 1 8 7 6 | x x) In order to get O1, we only need to remove the urban 4, 5, 6 and 7 in the O1 in P2, get 2-1-8-9-3 This sequence is sequentially placed in O1: O1 = (2 1 8 | 4 5 6 7 | 9 3) Similarly, we can get another progeny: O2 = (2 3 4 | 1 8 7 6 | 5 9) OX cross-development of a feature of path expression, that is, the order of the city (not their location) is important, that is, two travel 5-1-7-8-9-4-6-2-3 8-9-4-6-2-3-5-1-7 In fact, it is actually the same. Note: This operator is implemented by the public member function crossox () in the class GA in the namespace TSP. 2.2.2 Variation Operator We use an inverted variation for mutual operators. Inverted variation is to randomly select two points on the chromosome, and the skewers between the two points are reversed. described as follows: Original individual: (1 2 3 4 5 6 7 8 9) Random choice two points: (1 2 | 3 4 5 6 | 7 8 9) Inverted individual: (1 2 | 6 5 4 3 | 7 8 9) Note: This operator is implemented by the public member function mutateReverse () in the class GA in the namespace TSP. 2.2.3 Select Operators We use the championship to choose an operator for the selection operator. When selecting, selecting a comparison of k individuals in the group, and the appropriate individual will be selected to copy to the next generation, the parameter k is called the race, often K = 2. Note: This operator is implemented by the public member function SelectMatch () in the class GA in the namespace TSP. My Email: Wanbaocheng@163.com Note: Most of the source code can't stick, who needs to contact me!
