Оптимизация пользовательского типа данных с использованием генетического алгоритма
В этом примере показано, как использовать генетический алгоритм для минимизации функции с помощью пользовательского типа данных. Генетический алгоритм настроен, чтобы решить задачу коммивояжера.
Задача коммивояжера
Задача коммивояжёра является задачей оптимизации, где существует конечное количество городов, и стоимость путешествия между каждым городом известна. Цель состоит в том, чтобы найти упорядоченный набор всех городов, чтобы продавец посетил так, чтобы стоимость была сведена к минимуму. Чтобы решить проблему коммивояжера, нам нужен список городских локаций и расстояний, или стоимости, между ними.
Наш продавец посещает города США. Файл 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 с населением массива ячеек типа вы должны предоставить функцию создания, перекрестную функцию и функцию мутации, которая будет работать с вашим типом данных, например, с массивом ячеек.
Необходимые функции для задачи коммивояжера
В этом разделе показано, как создать и зарегистрировать три необходимые функции. Индивидуум в население для задачи коммивояжера является упорядоченным множеством, и поэтому население можно легко представить с помощью массива ячеек. Пользовательская функция создания для задачи коммивояжера создаст массив ячеек, скажем 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);
Setup опций генетического алгоритма
Во-первых, мы создадим контейнер опций, чтобы указать пользовательский тип данных и область значений населения.
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: []
На графике показано расположение городов в синих кругах, а также путь, найденный генетическим алгоритмом, которым будет путешествовать продавец. Продавец может начать в любом конце маршрута и в конце вернуться в стартовый город, чтобы вернуться домой.