В этом примере показано, как использовать генетический алгоритм для минимизации функции с использованием пользовательского типа данных. Генетический алгоритм настраивается для решения проблемы коммивояжера.
Проблема коммивояжера является задачей оптимизации, когда существует ограниченное число городов, и стоимость поездки между каждым городом известна. Цель - найти упорядоченный набор всех городов для посещения продавцом таким образом, чтобы стоимость была сведена к минимуму. Чтобы решить проблему коммивояжера, нам нужен список городов и расстояний, или стоимость, между каждым из них.
Наш продавец посещает города США. Файл usborder.mat содержит карту США в переменных x и yи геометрически упрощенная версия одной и той же карты в переменных xx и yy.
load('usborder.mat','x','y','xx','yy'); plot(x,y,'Color','red'); hold on;
Мы будем генерировать случайные местоположения городов внутри границы США. Мы можем использовать inpolygon функция, чтобы убедиться, что все города находятся внутри или очень близко к границе США.
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;
По умолчанию решатель генетических алгоритмов решает задачи оптимизации, основываясь на двойных и двоичных строковых типах данных. Функции создания, кроссовера и мутации предполагают, что популяция является матрицей типа double, или логической в случае двоичных строк. Решатель генетических алгоритмов может также работать над оптимизацией задач, включающих произвольные типы данных. Можно использовать любую понравившуюся структуру данных для своего населения. Например, пользовательский тип данных может быть задан с помощью массива ячеек MATLAB ®. Для использования ga с популяцией типа cell array необходимо предоставить функцию создания, перекрестную функцию и функцию мутации, которая будет работать с вашим типом данных, например, с массивом cell.
В этом разделе показано, как создавать и регистрировать три требуемые функции. Индивидуум в популяции для задачи коммивояжера является упорядоченным набором, и, таким образом, популяция может быть легко представлена с помощью массива ячеек. Пользовательская функция создания для проблемы командированного продавца создаст массив ячеек, скажем P, где каждый элемент представляет упорядоченное множество городов в качестве вектора перестановки. То есть продавец будет ездить в порядке, указанном в P{i}. Функция создания возвращает массив ячеек размера PopulationSize.
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, но наша функция фитнеса имеет два аргумента: x, distances. Мы можем использовать анонимную функцию для захвата значений дополнительного аргумента, матрицы расстояний. Создадим дескриптор функции FitnessFcn анонимной функции, которая принимает один вход x, но звонит traveling_salesman_fitness с xи расстояния. Переменная, расстояния имеет значение, когда функция обрабатывает FitnessFcn создается, поэтому эти значения фиксируются анонимной функцией.
%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')
load('usborder.mat','x','y','xx','yy');
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
Снова мы будем использовать анонимную функцию, чтобы создать дескриптор функции для анонимной функции, которая вызывает traveling_salesman_plot с дополнительным аргументом locations.
%locations defined earlier my_plot = @(options,state,flag) traveling_salesman_plot(options, ... state,flag,locations);
Сначала мы создадим контейнер параметров для указания пользовательского типа данных и диапазона заполнения.
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)
Optimization terminated: maximum number of generations exceeded.
x =
1x1 cell array
{1x40 double}
fval =
5.3846
reason =
0
output =
struct with fields:
problemtype: 'unconstrained'
rngstate: [1x1 struct]
generations: 500
funccount: 28563
message: 'Optimization terminated: maximum number of generations exceeded.'
maxconstraint: []
hybridflag: []
На сюжете показано расположение городов в синих кругах, а также путь, найденный генетическим алгоритмом, которым будет путешествовать продавец. Продавец может начать в любом конце маршрута и в конце, вернуться в стартовый город, чтобы вернуться домой.