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

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

Проблема коммивояжера

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

Наш продавец посещает города в Соединенных Штатах. Файл 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расстояния. Мы можем использовать анонимную функцию, чтобы получить значения дополнительного аргумента, матрицы расстояний. Мы создаем указатель на функцию 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: []

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

Документация