I. Introduction to TSP

Traveling Salesman Problem, also known as TSP Problem, is one of the famous problems in mathematics. Suppose a traveling businessman wants to visit n cities. He must choose the route he wants to take. The limit of the route is that he can visit each city only once and return to the original city. The goal of path selection is to obtain the minimum path distance among all paths.Mathematical model of TSP

Introduction to genetic algorithm

1 the introduction Genetic algorithm theory2.1 Biological basis of genetic algorithm 2.2 Theoretical basis of genetic algorithm 2.3 Basic concepts of genetic algorithm 2.4 Standard genetic algorithm 2.5 Characteristics of genetic algorithm 2.6 Improvement direction of genetic algorithm 3. Genetic algorithm flow 4 Key Parameters

Three, some source code

clear
clc
close all
X =[16.47.96.10
    16.47.94.44
    20.09.92.54
    22.39.93.37
    25.23.97.24
    22.00.96.05
    20.47.97.02
    17.20.96.29
    16.30.97.38
    14.05.98.12
    16.53.97.38
    21.52.95.59
    19.41.97.13
    20.09.92.55]; Load cityposition1.mat NIND=100; % Population size MAXGEN=200;
Pc=0.9; % cross probability Pm=0.05; % variation probability GGAP=0.9; % Generation gap D=Distanse(X); N=size(D,1); % (34*34%% Initialize population Chrom=InitPop(NIND,N); % figure % plot(X(:,1),X(:,2),'o'); DrawPath(Chrom(1,:),X)
pause(0.0001) %% Output route and total distance of random solution disp('A random value in the initial population :')
OutputPath(Chrom(1:)); Rlength=PathLength(D,Chrom(1:)); disp(['Total distance:',num2str(Rlength)]);
disp('~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~') %% optimized gen=0;
figure;
hold on;box on
xlim([0,MAXGEN])
title('Optimization process')
xlabel('algebra')
ylabel('Optimal value')
ObjV=PathLength(D,Chrom); PreObjV =min(ObjV);whileGen <MAXGEN %% calculate fitness ObjV=PathLength(D,Chrom); % Calculates the route length %fprintf('% d % 1.10 f \ n',gen,min(ObjV))
    line([gen- 1,gen],[preObjV,min(ObjV)]); pause(0.0001) preObjV=min(ObjV); FitnV=Fitness(ObjV); % % choose SelCh = Select (Chrom, FitnV, GGAP); SelCh=Recombin(SelCh,Pc); % % variable SelCh = Mutate (SelCh, Pm); SelCh=Reverse(SelCh,D); %% Chrom=Reins(Chrom,SelCh,ObjV); %% Number of update iterations gen=gen+1 ;
end
%% 画出最优解的路线图
ObjV=PathLength(D,Chrom);  %计算路线长度
[minObjV,minInd]=min(ObjV);
DrawPath(Chrom(minInd(1),:),X) %% output route and total distance of optimal solution disp('Optimal solution :')
p=OutputPath(Chrom(minInd(1), :)); disp(['Total distance:',num2str(ObjV(minInd(1)))); disp('-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -'Function SelCh=Recombin(SelCh,Pc) NSel=size(SelCh, Pc)1);
for i=1:2:NSel-mod(NSel,2)
    ifPc>=rand % cross probability Pc [SelCh(I,:),SelCh(I +)1,:)]=intercross(SelCh(i,:),SelCh(i+1:)); Function [a,b]=intercross(a,b) L=length(a); function [b]=intercross(a,b) L=length(a); r1=randsrc(1.1[1:L]);
r2=randsrc(1.1[1:L]);
ifr1~=r2 a0=a; b0=b; s=min([r1,r2]); e=max([r1,r2]);fori=s:e 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); Function [a,b]=intercross(a,b) % L=length(a); function [b]=intercross(a,b) % L=length(a); % r1=ceil(rand*L);
% r2=ceil(rand*L);
% r1=4; r2=7;
% ifr1~=r2 % s=min([r1,r2]); % e=max([r1,r2]); % a1=a; b1=b; % a(s:e)=b1(s:e); % b(s:e)=a1(s:e); %for i=[setdiff(1:L,s:e)]
%         [tf, loc] = ismember(a(i),a(s:e));
%         if tf
%             a(i)=a1(loc+s- 1);
%         end
%         [tf, loc]=ismember(b(i),b(s:e));
%         if tf
%             b(i)=b1(loc+s- 1); Function SelCh=Reverse(SelCh,D) function SelCh=Reverse(SelCh,D) [row,col]=size(SelCh); ObjV=PathLength(D,SelCh); % Calculate path length SelCh1=SelCh;for i=1:row
    r1=randsrc(1.1[1:col]);
    r2=randsrc(1.1[1:col]);
    mininverse=min([r1 r2]);
    maxinverse=max([r1 r2]);
    SelCh1(i,mininverse:maxinverse)=SelCh1(i,maxinverse:- 1:mininverse); end ObjV1=PathLength(D,SelCh1); % Calculate path length index=ObjV1<ObjV; SelCh(index,:)=SelCh1(index,:); Function SelCh=Select(FitnV,GGAP) NIND=size(Chrom, FitnV,GGAP)1);
NSel=max(floor(NIND*GGAP+. 5),2); ChrIx=Sus(FitnV,NSel); SelCh=Chrom(ChrIx,:); Function D=Distanse(a) row=size(a, b) row=size(a, b)1);
D=zeros(row,row);
for i=1:row
    for j=i+1:row
        D(i,j)=((a(i,1)-a(j,1)) ^2+(a(i,2)-a(j,2)) ^2) ^0.5;
        D(j,i)=D(i,j);
    end
end

Copy the code

4. Operation results

Matlab version and references

1 matlab version 2014A

[1] Yang Baoyang, YU Jizhou, Yang Shan. Intelligent Optimization Algorithm and Its MATLAB Example (2nd Edition) [M]. Publishing House of Electronics Industry, 2016. [2] ZHANG Yan, WU Shuigen. MATLAB Optimization Algorithm source code [M]. Tsinghua University Press, 2017.