Оптимизация пользовательского типа данных с использованием генетического алгоритма

В этом примере показано, как использовать генетический алгоритм для минимизации функции с помощью пользовательского типа данных. Генетический алгоритм настроен, чтобы решить задачу коммивояжера.

Задача коммивояжера

Задача коммивояжёра является задачей оптимизации, где существует конечное количество городов, и стоимость путешествия между каждым городом известна. Цель состоит в том, чтобы найти упорядоченный набор всех городов, чтобы продавец посетил так, чтобы стоимость была сведена к минимуму. Чтобы решить проблему коммивояжера, нам нужен список городских локаций и расстояний, или стоимости, между ними.

Наш продавец посещает города США. Файл 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: []

На графике показано расположение городов в синих кругах, а также путь, найденный генетическим алгоритмом, которым будет путешествовать продавец. Продавец может начать в любом конце маршрута и в конце вернуться в стартовый город, чтобы вернуться домой.

Похожие темы