eptsp.m

其中提到遺傳學的程式碼與應用提供給次淚相向的研究者參考下載

% eptsp.m
% Matlab program to implement the TSP program using EP.
%
%
% Inputs:
%     k		: Parent population size
%     N		: number of cities
%     r		: tournament size
%     no_gens	: number of generations
%     thershold : theoretically expected solution
% 		  If we reach this solution we return
%     plotiters : Plotting is done every 'plotiters'
%
% Outputs:
%     xopt	: best solution found
%     OptJ	: fitness trajectory of the best member in each generation
%     P		: final population
%     S		: final Probabilities
%
% function [xopt, optJ, P, S] = eptsp(k,N,r,no_gens,threshold,plotiters)
%
% Kumar Chellapilla
% Oct 16,1996.

function [xopt, optJ, P, S, xoptAll] = eptsp(k,N,r,no_gens,threshold,plotiters)
% Global variable needed by tspmutat.m
global D Dm Dn phimat key

xoptAll = [];
key = 1;
% During the debugging phase set seeds to 0
%randn('seed',0);
%rand('seed',0);

% number of cities
%N = 100;
%no_gens = 1000;

% Selection of the cities:
% The cities are generates as in a 'uniform TSP' i.e., uniform random
% numbers in [0,100] in 2 dimensions.
Cities = 100*rand(N,2);

% Generate the Distances matrix.
% In the distances matrix the distance between city i and city j is
% given by Distances(i,j)
[X1,X2] = meshgrid(Cities(:,1),Cities(:,1));
[Y1,Y2] = meshgrid(Cities(:,2),Cities(:,2));

% Compute the distance matrix
D = sqrt((X1-X2).^2 + (Y1-Y2).^2);
[Dm Dn] = size(D);

% Get the population parameters
n = N;	% number of parameters
%k = 50; % parent pop size

% phimat is a temporary matrix used by phitsp.m
phimat = zeros(N,2*k);

% Generate the initial population 
% each member is a reordering of the numbers 1,2,...,N
[junk P] = sort(rand(n,2*k)); 
clear junk

tic
for gen = 1:no_gens
    % Get the fitness
    J = phitsp(P);
    
    % Take the best fitness statistics
    optJ(gen) = min(J);
    
    % Tournament step
    Jop = phitour(k,r,J);
    
    % sort the fitness and the population
    [Jop indices] = sort(Jop);
    P = P(:,indices);
    
    % Mutate the k parents to get the k offsprings
    P(:,k+1:2*k) = tspmutat(P(:,1:k));
    
    % If we have reached our target solution return
    if(optJ(gen) <= threshold)
        disp(sprintf('BEST SOLUTION REACHED AT GENERATION %g',gen));
        % return the best solution
        xopt = P(:,1);
%        return;
    end
    
    if(rem(gen,plotiters) == 0)
        disp(sprintf('gen = %g fitness = %g Out of 110 = %g ratio = %g',gen,optJ(gen),threshold,optJ(gen)/(threshold/1.1))); 
        toc
        
        subplot(2,2,1)
        semilogy(optJ);
        
        subplot(2,2,2)
        plot(J);
        
        subplot(2,2,3)
        plot(P(:,1));
        
        % show the best tour
        showtour(Cities,P(:,1));
        
        drawnow
        tic
    end
    
    if( rem(gen,1000) == 0 )
        xoptAll = [xoptAll xopt];
    end
end