A list,



I. Problem analysis

As shown in the figure, node numbers are successively 1.2.3.4.5.6.7.8.9.10.11. Based on the knowledge of graph theory, its weighted adjacency matrix can be written as:

0 2 8 1 500 500 500 500 500 500 500 500 500 500 2 0 6 500 1 500 500 500 500 500 500 500 8 6 7 500 1 500 500 500 500 500 500 500 1 500 7 0 500 500 9 500 500 500 500 500Copy the code

500 1 500 500 0 3 500 2 500 500 500 500 500

500 500 1 500 3 0 4 500 6 500 500

500 500 500 9 500 4 0 500 500 1 500

500 500 500 500 2 500 500 0 7 500 9

500 500 500 500 500 6 500 7 0 1 2

500 500 500 500 500 500 500 1 500 1 0 4

500 500 500 500 500 500 500 9 2 4 0

Note: Inf =500 is set here to avoid infinitely large numbers eating decimals.

The problem requires to find the shortest path between any two points. Floyd algorithm uses the method of trying to insert vertices between two points and comparing distances. After thinking about it, I decided that it would be difficult to find a unified shortest path function using genetic algorithms, but I could calculate each pair of points separately and then add a for loop to solve all the cases between them. Observing the problem, it can be found that all nodes are bidirectional, so only the path and distance from I to J can be calculated, and then all data can be obtained by folding the matrix according to the main diagonal.

2. Experimental principle and mathematical model

The implementation principle is the principle of genetic algorithm:

According to the selected fitness function and through the genetic replication, crossover and variation of the individual screening, so that the individuals with high fitness are retained and formed a new population, the new population not only inherited the information of the previous generation, but also better than the previous generation. Over and over again, the fitness of individuals in the population increases until certain conditions are met.

The mathematical model is as follows:



Specific experiment:

First: encoding and initialization

Since natural coding is adopted and the code generated cannot be repeated, I use randperm function to generate random natural numbers that do not repeat. Since the method to solve the problem is to calculate each pair of points, the first node is put into the code separately and combined into a complete code.

Since there are 11 nodes, a matrix of 1 row and 11 columns can be used to store data. At the same time, since the number is numerical, the chromosome of the path can be directly represented by numerical coding. Details are as follows:

For example, if the path from 2 to 9 is adopted, the chromosome code may be (2, 5, 1, 8, 4, 6, 9, 3, 10, 7, 11). The code after 9 is used for operator operation, which has no practical significance.

Second: to calculate fitness, the shortest path value, namely the minimum value, is commonly used as C-F(x) or C/F(x) (C is a constant), the former method is adopted here. Therefore, relative fitness can be further calculated.

Third: select and copy

The roulette algorithm is used to generate a random value and compare its relationship with the cumulative relative fitness, so as to select excellent individuals into the next generation.

Fourth: crossover.

Since the encoding is a non-repeating number, using the traditional crossing method, that is, crossing the previous line with the next line, will produce invalid paths. Therefore, different crossing methods are adopted, as follows:

(1) Two loci (not starting loci) I and J were randomly selected from chromosome Tx and Ty representing the path, that is, each loci between locus I and locus JTH was defined as a crossover domain, and the contents of the crossover were memorized as TEMP1 and temp2 respectively.

(2) According to the mapping relationship in the cross region, find all elements identical with temp2 in individual Tx and all elements identical with temp1 in individual Ty, and set them all to 0.

(3) The individual Tx and Ty are cyclically moved to the left, and deleted when 0 is encountered, until there is no more 0 at the left end of the crossover region in the coding string: then all vacancies are concentrated in the crossover region, and the original genes in the crossover region are moved backward successively. Because 0 elements may be more, in the implementation of the program, I will be the non-zero elements, and then synthesized.

(4) Insert temp2 into the cross region of Tx and temp1 into the cross region of Ty. Forming new chromosomes.

No.5: Variation

The chromosomes are coded from 1 to 11 without repetition, so the usual method of generating a random number instead cannot be used. The exchange variation method is used here. That is, two numbers are randomly generated and the order of the two nodes is switched.

Ii. Source code

clc; clear; % Initialization parameter % Note: popsize=200,MaxGeneration=100About running,2Minutes. If too precise is not required, the number of cycles can be reduced. pointnumber=11; % Number of nodes Popsize=200; % population size, can only be even (because67MaxGeneration=100; % Max algebra Pc=0.8; Pm=0.3; % crossover probability and mutation probability A=[0 2 8 1 50 50 50 50 50 50 50
    2 0 6 50 1 50 50 50 50 50 50
    8 6 0 7 50 1 50 50 50 50 50
    1 50 7 0 50 50 9 50 50 50 50
    50 1 50 50 0 3 50 2 50 50 50
    50 50 1 50 3 0 4 50 6 50 50
    50 50 50 9 50 4 0 50 50 1 50
    50 50 50 50 2 50 50 0 7 50 9
    50 50 50 50 50 6 50 7 0 1 2
    50 50 50 50 50 50 1 50 1 0 4
    50 50 50 50 50 50 50 9 2 4 0]; % weighted adjacency matrix. A(A==50) =500; % values50Too small and corrected to500; Bestindividual=zeros(MaxGeneration,1);
outdistance=zeros(11.11);
outpath=cell(11.11); % to store11The shortest path between the points %****** generates the initial population ******for a=1: pointNumber % Indicates the starting point %a=1;                                      
tempvary=[1 2 3 4 5 6 7 8 9 10 11]; tempvary(a)=[]; Tempmatrix =a*ones(Popsize,1); % place the starting point in a separate matrix path=zeros(Popsize,pointnumber- 1); % declare the matrix size to avoid slowing downfor i=1:Popsize
    temprand=randperm(pointnumber- 1);
    path(i,:)=tempvary(temprand(1:end)); % Generate a series of random paths excluding the starting point end path=[tempmatrix path]; % Compose the entire path including the starting point [row,col]=size(path);forB =a: pointNumber % endpoint number %b=10;


for k=1:1:MaxGeneration
    for i=1:row position2=find(path(i,:)==b); % Find the destination in the path pathLong (I)=0;
        for j=1:position2- 1
            pathlong(i)=pathlong(i)+A(path(i,j),path(i,j+1)); Fitness=length(A)* Max (A) -pathlong; Fitness=Fitness./sum(Fitness); %****** Step1: Select the optimal individual ****** Bestindividual(k)=min(pathlong); [Orderfi,Indexfi]=sort(Fitness); Bestfi=Orderfi(Popsize); BestS=path(Indexfi(Popsize),:); % records the path of the optimal individual in each generation %****** Step2: select and copy operation ****** temppath=path; roulette=cumsum(Fitness);for i=1:Popsize
        tempP=rand(1);
        for j=1:length(roulette)
            if tempP<roulette(j)
                break;
            end
        end
        path(i,:)=temppath(j,:);
    end
    %************ Step 3: interleaved operation ************ temppath2=path;for i=1:2:row
        tempP2=rand(1);                         
        if(tempP2<rand(1))
            temPm2=fix((rand(1) +0.2) *10); % Because the origin gene cannot change temPm3=fix((rand(1) +0.2) *10); % Randomly pick two positions as2to11Loci temPm4 = min (temPm2 temPm3); temPm5=max(temPm2,temPm3); temp1=path(i,temPm4:temPm5); % store genes between two points, facilitating cross temp2=path(I +1,temPm4:temPm5);
            [c d]=find(ismember(path(i,:),temp2));
            path(i,d)=0; % find the I line at I +1Row retrieves the number in the region and sets it to0
            [e f]=find(ismember(path(i+1,:),temp1));
            path(i+1,f)=0; Find the I + %1The number of rows in the fetch area of row I is set to zero0
            [g h]=find(path(i,:)~=0); v1=path(i,h); [l m]=find(path(I +)1, :) ~ =0);
            v2=path(i+1,m); % out I +1Path (I,:)=[v1()1:temPm4- 1) temp2 v1(temPm4- 1+size(temp1):end)];      
            path(i+1,:)=[v2(1:temPm4- 1) temp1 v2(temPm4- 1+size(temp2):end)]; % gene crossoverend
    end
    path(Popsize,:)=BestS;
    %************ Step 4: Mutation operation **************for i=1:Popsize
        tempPm=rand(1);
        if(tempPm<Pm)
            temPm6=fix((rand(1) +0.2) *10);
            temPm7=fix((rand(1) +0.2) *10); % generate two random numbers for exchange tempvessel=path(I,temPm6); Path (I,temPm6)=path(I,temPm7); path(i,temPm7)=tempvessel; % variation exchangeend 
    end
    path(Popsize,:)=BestS; end [aa bb]=find(BestS==b); % find the destination Bestpath=BestS(1:bb); % OutDistance (a,b)=Bestindividual(k); % write the shortest distance to the matrix outPath {a,b}=Bestpath; % write path, because the data type is matrix, so use cell array store end endfor i=1:pointnumber
    for j=1:i outdistance(i,j)=outdistance(j,i); Outpath {I,j}=fliplr(outpath{j, I}); % % implementation path of symmetry and flip end end * * * * * * * * * * * * * * * results output * * * * * * * * * * * * * * * * *outdistance
celldisp(outpath)
%xlswrite('tempdata.xls', outpath)% is stored in Excel for operationCopy the code

3. Operation results

Distance matrix: A (I,j) where I represents the starting point and j represents the ending point.

outdistance =

0 2 7 13 6 10 5 12 11 14 2 0 5 3 14 8 3 10 9 12 7 5 0 7 4 1 5 6 7 6 9 13 7 0 4 8 9 6 11 10 13 3 14 4 0 3 7 2 9 8 11 11 6 4 1 8 3 0 4 5 6 5 8 10 8 5 9 7 4 0 9 2 1 4 5 3 6 6 2 5 9 0 7 8 9 12 10 7 11 9 6 2 7 0 12 11 9 6 10 8 5 1 8 10 3Copy the code

8 4 9 2 3 0

Path: b(I,j) I represents the starting point and j represents the ending point.

outpath:

Fourth, note

Version: 2014 a