Introduction to TSP

Traveling Salesman Problem (TSP), also known as Traveling Salesman Problem, is one of the famous problems in mathematics. Suppose there is a traveling businessman who wants to visit n cities. He must choose the route to take. The limitation of the route is that he can only visit each city once, and he must return to the city from which he started. The goal of path selection is to obtain the minimum path length among all paths.The mathematical model of TSP

Introduction to genetic algorithm

1 the introduction 2 genetic algorithm theory2.1 Biological basis of genetic algorithm2.2 Theoretical basis of genetic algorithm 2.3 Basic concepts of genetic algorithm 2.4 Standard genetic algorithm 2.5 Features of genetic algorithm 2.6 Improvement direction of genetic algorithm 3 Genetic algorithm flow 4 Key Parameter Description

Three, part of the source code

clear; clc; tStart = tic; % algorithm timer % * * * * * * * * * * * * * * * * * * * * * * * * initialization parameter variables * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * [Num, Txt, Raw] = xlsread (' provincial_ capital_coordinate12.xlsx'); % cities = Num(:,5:6); cities=cities'; [~,cityNum]=size(cities); maxGEN = 500; popSize = 300; % Genetic algorithm population size crossoverProbabilty = 0.95; % Cross probability mutationbattery = 0.33; % Mutation probability %******** Initialize population *********** % Calculate distances between various cities generated above = calculateDistance(cities); % generate population, each individual represents a path gbest = Inf; Inf infinity parentPop = zeros(popSize, cityNum); For I =1:popSize parentPop(I,2: citynum-1) = Randperm (citynum-2); For a=2: parentPop(I,a)=parentPop(I,a)+1; for a=2: parentPop(I,a)=parentPop(I,a)+1; end parentPop(i,1)=1; parentPop(i,cityNum)=cityNum; End % define offspring population childPop = Zeros (popSize,cityNum); MinPathes = zeros(maxGEN,1); % * * * * * * * * * * * * * * * * * * * * * * * * * * * * % * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * % * * * * * * * * * * * * * * * * * * * * * GA crossover and mutation execution algorithm choose * * * * * * * * * * * * * * * * * * * * * * * * for genNum = 1: maxGEN % calculation of fitness value, = Fitness (distances, parentPop); tournamentSize=4; Set size for K =1:popSize %% below for tournamentSize method % Randomly select parent tourPopDistances= Zeros (tournamentSize,1); for i=1:tournamentSize randomRow = randi(popSize); % line: Returns a pseudo-random integer of tourPopDistances(I,1) = sumDistance(randomRow,1); End % select best, i.e. parent1 = min(tourPopDistances); [parent1X, parent1Y] = find (sumDistance = = parent1, 1, 'first'); Parent1Path = parentPop(parent1X(1,1),:); For I =1:tournamentSize randomRow = RANDI (popSize); tourPopDistances(i,1) = sumDistance(randomRow,1); end parent2 = min(tourPopDistances); [parent2X, parent2Y] = find (sumDistance = = parent2, 1, 'first'); Parent2Path = parentPop (parent2X (1, 1), :); Function [childPath] = Crossover (parent1Path, parent2Path, prob) % cross random = rand(); [l, length] = size(parent1Path); [l, length] = parent1Path); childPath = zeros(l,length); setSize = floor(length/2) -1; % line: floor round to negative infinity offset = randi(setSize); % line: randomly generate an integer between 1-setsize parent1OXstart=offset; % line: 0X cross, parent1OXend=setSize+offset-1; Line % : 0 x crossed, parent 1 pass on to their offspring fragment ends for I = parent1OXstart: parent1OXend childPath (1, I) = parent1Path (1, I); End childPath (1, 1) = parent1Path (1, 1); ChildPath (1,length) = parent1Path(1,length); % line: parent2 was placed in the subrogation coordinate parent2Point=2 in sequence; For x=2:length-1 if y=parent2Point:length-1 if ~any(childPath == parent2Path(1,y))% ChildPath (1,x)=parent2Path(1,y); parent2Point=y+1; break; end end end end else childPath = parent1Path; end end function [ bestPopPath ] = paint( cities, pop, minPath, totalDistances,gen) gNumber=gen; [~, length] = size(cities); xDots = cities(1,:); yDots = cities(2,:); %figure(1); Plot (xDots,yDots, 'p', 'MarkerSize', 10, 'MarkerFaceColor', 'green'); Xlabel (' longitude); Ylabel (' latitude); axis equal [num,txt,raw]=xlsread('provincial_ capital_coordinate12.xlsx'); % % latitude and longitude data text (xDots (1) + 0.2, yDots (1) + 0.2, TXT (1 + 1, 2), 'FontSize, 9.5,' Color ', 'red', 'FontWeight', 'Bold'); % First draw the starting point, Highlight the starting point for I = 2: text length - 1 (xDots (I) + 0.2, yDots (I) + 0.2, TXT (I + 1, 2), 'FontSize, 8,' Color ', 'blue', 'FontWeight', 'Bold'); End function [n_citys,city_position] = Read(filename) fid = fopen(filename,'rt'); Location =[]; A = [1 2]; tline = fgetl(fid); % line: Reads a line from a file and removes the newline at the end of the line. While ischar(tline) if(STRCMP (tline,'NODE_COORD_SECTION')) while ~isempty(A) A=fscanf(fid,'%f',[3,1]); if isempty(A) break; end location=[location;A(2:3)']; end end tline = fgetl(fid); if strcmp(tline,'EOF') break; endCopy the code

Fourth, the operation result

V. MATLAB version and references

1 Matlab version 2014A

Steamed stuffed bun [1] Yang, YU jizhou, Yang Shan. [2] ZHANG Yan, WU Shuigen. Intelligent Optimization Algorithm and MATLAB Example (2nd edition) [M]. Publishing House of Electronics Industry, 2016. MATLAB Optimization algorithm source code [M]. Tsinghua University Press, 2017.