# MATLAB - 遗传算法（GA）求解旅行商问题（TSP）

## 二、MATLAB 步骤

### 1.引入库

load('usborder.mat','x','y','xx','yy');
plot(x,y,'Color','red'); hold on;

cities = 40;
locations = zeros(cities,2);
n = 1;
while (n <= cities)
xp = rand*1.5;
yp = rand;
if inpolygon(xp,yp,xx,yy)
locations(n,1) = xp;
locations(n,2) = yp;
n = n+1;
end
end
plot(locations(:,1),locations(:,2),'bo');

distances = zeros(cities);
for count1=1:cities,
for count2=1:count1,
x1 = locations(count1,1);
y1 = locations(count1,2);
x2 = locations(count2,1);
y2 = locations(count2,2);
distances(count1,count2)=sqrt((x1-x2)^2+(y1-y2)^2);
distances(count2,count1)=distances(count1,count2);
end;
end;

### 3. 旅行商问题所需函数

type create_permutations.m
function pop = create_permutations(NVARS,FitnessFcn,options)
%CREATE_PERMUTATIONS Creates a population of permutations.
%   POP = CREATE_PERMUTATION(NVARS,FITNESSFCN,OPTIONS) creates a population
%  of permutations POP each with a length of NVARS.
%
%   The arguments to the function are
%     NVARS: Number of variables
%     FITNESSFCN: Fitness function
%     OPTIONS: Options structure used by the GA
%   Copyright 2004-2007 The MathWorks, Inc.
totalPopulationSize = sum(options.PopulationSize);
n = NVARS;
pop = cell(totalPopulationSize,1);
for i = 1:totalPopulationSize
pop{i} = randperm(n);
end

type crossover_permutation.m
function xoverKids  = crossover_permutation(parents,options,NVARS, ...
FitnessFcn,thisScore,thisPopulation)
%   CROSSOVER_PERMUTATION Custom crossover function for traveling salesman.
%   XOVERKIDS = CROSSOVER_PERMUTATION(PARENTS,OPTIONS,NVARS, ...
%   FITNESSFCN,THISSCORE,THISPOPULATION) crossovers PARENTS to produce
%   the children XOVERKIDS.
%
%   The arguments to the function are
%     PARENTS: Parents chosen by the selection function
%     OPTIONS: Options created from OPTIMOPTIONS
%     NVARS: Number of variables
%     FITNESSFCN: Fitness function
%     STATE: State structure used by the GA solver
%     THISSCORE: Vector of scores of the current population
%     THISPOPULATION: Matrix of individuals in the current population
%   Copyright 2004-2015 The MathWorks, Inc.
nKids = length(parents)/2;
xoverKids = cell(nKids,1); % Normally zeros(nKids,NVARS);
index = 1;
for i=1:nKids
% here is where the special knowledge that the population is a cell
% array is used. Normally, this would be thisPopulation(parents(index),:);
parent = thisPopulation{parents(index)};
index = index + 2;
% Flip a section of parent1.
p1 = ceil((length(parent) -1) * rand);
p2 = p1 + ceil((length(parent) - p1- 1) * rand);
child = parent;
child(p1:p2) = fliplr(child(p1:p2));
xoverKids{i} = child; % Normally, xoverKids(i,:);
end

type mutate_permutation.m
function mutationChildren = mutate_permutation(parents ,options,NVARS, ...
FitnessFcn, state, thisScore,thisPopulation,mutationRate)
%   MUTATE_PERMUTATION Custom mutation function for traveling salesman.
%   MUTATIONCHILDREN = MUTATE_PERMUTATION(PARENTS,OPTIONS,NVARS, ...
%   FITNESSFCN,STATE,THISSCORE,THISPOPULATION,MUTATIONRATE) mutate the
%   PARENTS to produce mutated children MUTATIONCHILDREN.
%
%   The arguments to the function are
%     PARENTS: Parents chosen by the selection function
%     OPTIONS: Options created from OPTIMOPTIONS
%     NVARS: Number of variables
%     FITNESSFCN: Fitness function
%     STATE: State structure used by the GA solver
%     THISSCORE: Vector of scores of the current population
%     THISPOPULATION: Matrix of individuals in the current population
%     MUTATIONRATE: Rate of mutation
%   Copyright 2004-2015 The MathWorks, Inc.
% Here we swap two elements of the permutation
mutationChildren = cell(length(parents),1);% Normally zeros(length(parents),NVARS);
for i=1:length(parents)
parent = thisPopulation{parents(i)}; % Normally thisPopulation(parents(i),:)
p = ceil(length(parent) * rand(1,2));
child = parent;
child(p(1)) = parent(p(2));
child(p(2)) = parent(p(1));
mutationChildren{i} = child; % Normally mutationChildren(i,:)
end

type traveling_salesman_fitness.m
function scores = traveling_salesman_fitness(x,distances)
%TRAVELING_SALESMAN_FITNESS  Custom fitness function for TSP.
%   SCORES = TRAVELING_SALESMAN_FITNESS(X,DISTANCES) Calculate the fitness
%   of an individual. The fitness is the total distance traveled for an
%   ordered set of cities in X. DISTANCE(A,B) is the distance from the city
%   A to the city B.
%   Copyright 2004-2007 The MathWorks, Inc.
scores = zeros(size(x,1),1);
for j = 1:size(x,1)
% here is where the special knowledge that the population is a cell
% array is used. Normally, this would be pop(j,:);
p = x{j};
f = distances(p(end),p(1));
for i = 2:length(p)
f = f + distances(p(i-1),p(i));
end
scores(j) = f;
end

ga 将只用一个参数 x 调用我们的适应度函数，但我们的适应度函数有两个参数：xdistances。我们可以使用一个匿名函数来获取额外的参数——距离矩阵的值。我们创建一个函数，将 FitnessFcn 处理为一个匿名函数，该函数接受一个输入 x，但使用 xdistances 调用 traveling_salesman_fitness。在创建函数 FitnessFcn 时，变量 distance 有一个值，因此这些值将被匿名函数捕获。

%distances defined earlier
FitnessFcn = @(x) traveling_salesman_fitness(x,distances);

type traveling_salesman_plot.m
function state = traveling_salesman_plot(options,state,flag,locations)
%   TRAVELING_SALESMAN_PLOT Custom plot function for traveling salesman.
%   STATE = TRAVELING_SALESMAN_PLOT(OPTIONS,STATE,FLAG,LOCATIONS) Plot city
%   LOCATIONS and connecting route between them. This function is specific
%   to the traveling salesman problem.
%   Copyright 2004-2006 The MathWorks, Inc.
persistent x y xx yy
if strcmpi(flag,'init')
end
plot(x,y,'Color','red');
axis([-0.1 1.5 -0.2 1.2]);
hold on;
[unused,i] = min(state.Score);
genotype = state.Population{i};
plot(locations(:,1),locations(:,2),'bo');
plot(locations(genotype,1),locations(genotype,2));
hold off

%locations defined earlier
my_plot = @(options,state,flag) traveling_salesman_plot(options, ...
state,flag,locations);

### 4.设置遗传算法选项

options = optimoptions(@ga, 'PopulationType', 'custom','InitialPopulationRange', ...
[1;cities]);

options = optimoptions(options,'CreationFcn',@create_permutations, ...
'CrossoverFcn',@crossover_permutation, ...
'MutationFcn',@mutate_permutation, ...
'PlotFcn', my_plot, ...
'MaxGenerations',500,'PopulationSize',60, ...
'MaxStallGenerations',200,'UseVectorized',true);

numberOfVariables = cities;
[x,fval,reason,output] = ...
ga(FitnessFcn,numberOfVariables,[],[],[],[],[],[],[],options)
ga stopped because it exceeded options.MaxGenerations.

x =
{[14 12 36 3 5 11 40 25 38 37 7 30 28 10 23 21 27 4 1 29 26 31 9 24 16 19 13 8 18 2 22 34 6 35 20 17 15 39 33 32]}
fval = 5.3846
reason = 0
output =
problemtype: 'unconstrained'
rngstate: [1×1 struct]
generations: 500
funccount: 28563
message: 'ga stopped because it exceeded options.MaxGenerations.'
maxconstraint: []
hybridflag: []

|
3天前
|

53 29
|
4天前
|

36 20
|
4天前
|

36 19
|
5天前
|

30 3
|
5天前
|

19 2
|
7天前
|

19 3
|
7天前
|

26 1
|
22天前
|

37 1
|
12天前
|

38 0
|
2月前
|

61 4

DDNS