The standard particle swarm optimization algorithm completes the optimization of the extremum by following the individual extremum and the group extremum. Although the operation is simple and it can converge rapidly, with the increasing number of iterations, the particles become more and more similar when the population converges, and they may not be able to jump out around the local optimal solution. Hybrid particle swarm optimization (HPSO) abandons the traditional particle swarm optimization (PSO) to update the particle position by tracking the extreme value, but introduces the crossover and mutation operation in genetic algorithm (GA) to search for the global optimal solution by crossing the particle with the individual extreme value and the population extreme value and the particle’s own mutation.

Traveling Salesman Problem (TSP), also known as salesman problem, is the most basic route problem. The problem seeks the minimum path cost for a single traveler to start from the starting point, pass through all given demand points, and finally return to the starting point. The earliest mathematical model of the traveling salesman problem was proposed by Dantzig(1959) et al. Traveling salesman problem is a special case of vehicle routing problem (VRP), and it has been proved that traveling salesman problem is NP problem.

The TSP algorithm flow based on hybrid particle swarm optimization is shown in Figure 1.

FIG. 1 Flow of hybrid particle swarm optimization

The particle swarm initialization module initializes the particle swarm. The fitness value calculation module calculates the fitness value of individual particle swarm. Updating the particle module updates the individual optimal particle and the population optimal particle according to the particle fitness value. Individual optimal crossover is to get new particles by crossing individual and individual optimal particles. Swarm optimal crossover is to cross individual and swarm optimal particles to get new particles. Particle mutation refers to the mutation of the particle itself to get a new particle.

• For example, when the number of cities experienced is 10, the individual code is [9 4 2 1 3 7 6 10 8 5], which means that the city traversal starts from 9 and finally returns to the starting city 9 after 4, 2, 1, 3… \dotsm… Thus completing the TSP traversal.
• Fitness value particle fitness value is expressed as the length of traversal path, F I t n e s s (I) = ∑ I, j = 1 n p a t h I, J (1) the fitness (I) = \ sum_ {I, j = 1} ^ path_ {n} {I, j} \ tag {1} fitness (I) = I, j = 1 ∑ npathi, j (1), n nn as the number of cities; P ath I,j path_{I,j}pathi,j is the path length between city I,j I,ji,j.
• Cross operation individuals are updated by crossing individual extremum and population extremum, and the crossing method is integer crossing method. Firstly, two crossing positions are selected, and then the individual and individual extremum or individual and group extremum are crossed. Assume that the randomly selected crossing positions are 3 and 5, and the operation method is as follows: Individual [9 4 2 1 3 7 6 10 8 5] extreme value [9 2 1 6 3 7 4 10 8 5] cross into the new individual [9 4 1 6 3 7 6 10 8 5] generated by the new individual, if there is a repeat position, adjust it. The adjustment method is to replace the repeatedly included cities with cities not included in individuals, as shown below: [9 4 1 6 3 7 6 10 8 5] Is adjusted to [9 4 2 1 3 7 6 10 8 5]. The strategy of retaining excellent individuals is adopted for the obtained new individuals, and particles are updated only when the fitness value of the new particles is better than that of the old particles.
• Mutation operation mutation method using the individual internal two-position swap method, first randomly select the mutation position P O S 1 POS1POS1 and P O S 2 POS2POS2, and then the two mutation position swap, assuming that the selected mutation position is 2 and 4, mutation operation is shown as follows: [9 4 2 1 3 7 6 10 8 5] changed into [9 1 2 4 3 7 6 10 8 5]. The strategy of retaining excellent individuals was adopted for the new individuals, and the new particles were updated only when the fitness value of the new particles was better than that of the old particles.

According to the principle of mixed particle swarm algorithm, the TSP search algorithm based on mixed particle swarm algorithm is realized in MATLAB programming.

• Fitness function The fitness function calculates the individual fitness value, which is the total length of the route. The code is as follows:

function indiFit = fitness(x, cityCoor, % x Input % cityCoor Input % cityDist Input % indiFit Output % cityDist input % indiFit Output m = size(x, 1); n = size(cityCoor, 1); indiFit = zeros(m, 1); for i = 1:m for j = 1:n-1 indiFit(i) = indiFit(i)+cityDist(x(i, j), x(i, j+1)); end indiFit(i) = indiFit(i)+cityDist(x(i, 1), x(i, n)); endCopy the code

• Particle initialization Particle initialization is used to initialize particles, calculate particle fitness values, and determine the optimal individual particle and population particle based on fitness values. The program code is as follows:

nMax = 200; % indiNumber = 1000; % Number of individuals Individual = Zeros (indiNumber,n); For I = 1:indiNumber individual(I, :) = randperm(n); IndiFit = fitness(Individual, cityCoor, cityDist); [value, index] = min(indiFit); tourPbest = individual; % tourGbest = individual(index, :); % recordPbest = INF *ones(1, indiNumber); % recordGbest = indiFit(index); % value % Group optimal record xnew1 = individual;Copy the code

• Crossover operation The crossover operation intersects particles with individual extremums and population extremums to get better individuals. The crossover operation code is as follows:

Function a = Recombin(a, b) %% cross % input: % a is the individual to be crossed, b is the extremum of the individual to be crossed % output: % a is the new individual to be crossed n = length(a); c1 = unidrnd(n-1); % produces cross bit c2 = unidrnd(n-1); C1 = round(rand*(n-2))+1; c2 = round(rand*(n-2))+1; end chb1 = min(c1, c2); chb2 = max(c1, c2); cros = b(chb1:chb2); % cross area element ncros = length(cros); For j=1:ncros for k=1:n if a(k) == cros(j) a(k) = 0; for t = 1:n-k temp = a(k+t-1); a(k+t-1) = a(k+t); a(k+t)=temp; End end % insert a(n-ncros+1:n) = cros; % a0 = a; b0 = b; % for i = chb1:chb2 % a1 = a; b1 = b; % a(i) = b0(i); % b(i) = a0(i); % x = find(a == a(i)); % y = find(b == b(i)); % i1 = x(x ~= i); % i2 = y(y ~= i); % if ~isempty(i1) % a(i1) = a1(i); % end % if ~isempty(i2) % b(i2) = b1(i); % end % endCopy the code

• Mutating operation Mutating operation mutating itself to get a better individual. The mutation operation code is as follows:

Function x = Mutate(x) % input: x individual % output: x individual = length(x); while true c1 = round(rand*(n-1))+1; C2 = round(rand*(n-1))+1; If c1 ~= c2 break; end end temp = x(c1); x(c1) = x(c2); x(c2) = temp;Copy the code

• The simulation results
  
  A hybrid particle swarm optimization algorithm is adopted to plan the TSP path, and the initial location of each city is shown in Figure 2.
  
  

FIG. 2 Initial location of the city

The number of evolution of the hybrid particle swarm optimization algorithm is 100, and the population size is 100. The changes of the fitness value of the optimal particle and the optimal path planned during the algorithm evolution are shown in Figure 3 and Figure 4.

FIG. 3 Changes in fitness values

Figure 4 shows the optimal path

Hybrid particle swarm optimization is used to plan the shortest paths of other city models.

The urban distribution map is shown in Figure 5. The number of evolution of the hybrid particle swarm optimization algorithm is 200, and the population size is 1000. The path planned by hybrid particle swarm optimization is shown in Figure 6.

FIG. 5 Urban distribution map

Figure 6. Planning the path

It can be seen from FIG. 2 to FIG. 6 that the TSP algorithm based on hybrid particle swarm optimization algorithm can solve the traveling salesman problem of small scale, and the hybrid particle swarm optimization algorithm can also obtain a better path for the traveling salesman problem of large scale.

Code download or simulation consultation to add QQ1575304183

[1] Kennedy J . Particle swarm optimization[J]. Proc. of 1995 IEEE Int. Conf. Neural Networks, (Perth, Australia), Nov. 27-Dec. 2011, 4(8):1942-1948 Vol.4. [2] Wang Wei. [3] YU Lei et al. Hybrid Particle Swarm Optimization Algorithm and Its Optimization Efficiency Evaluation [J]. China Water Transport: Academic Edition, 2007, 7(006):102-103. MATLAB Intelligent Algorithm 30 Case Analysis (2nd edition)[M]. Beijing University of Aeronautics and Astronautics Press.2015.