Настройка задачи для gamultiobj

gamultiobj находит локальный фронт Парето для нескольких целевых функций, используя генетический алгоритм. Для этого примера будем использовать gamultiobj чтобы получить фронт Парето для двух целевых функций, описанных в файле MATLAB kur_multiobjective.m. Это реальная функция, которая состоит из двух целей, каждая из трех переменных принятия решений. Мы также накладываем ограничения на переменные решения -5 < = x (i) < = 5, i = 1,2,3.

type kur_multiobjective.m

function y = kur_multiobjective(x)
%KUR_MULTIOBJECTIVE Objective function for a multiobjective problem. 
%   The Pareto-optimal set for this two-objective problem is nonconvex as
%   well as disconnected. The function KUR_MULTIOBJECTIVE computes two
%   objectives and returns a vector y of size 2-by-1.
%
%   Reference: Kalyanmoy Deb, "Multi-Objective Optimization using
%   Evolutionary Algorithms", John Wiley & Sons ISBN 047187339 

%   Copyright 2007 The MathWorks, Inc.


% Initialize for two objectives 
y = zeros(2,1);

% Compute first objective
for i = 1:2
  y(1) = y(1)  - 10*exp(-0.2*sqrt(x(i)^2 + x(i+1)^2));
end

% Compute second objective
for i = 1:3
   y(2) = y(2) +  abs(x(i))^0.8 + 5*sin(x(i)^3);
end

Мы должны предоставить функцию соответствия, количество переменных и связанные ограничения в задаче, чтобы gamultiobj функция. Обратитесь к справке по gamultiobj функция для синтаксиса. Здесь же мы хотим построить график фронта Парето в каждой генерации с помощью функции построения графика @gaplotpareto. Используем optimoptions функция, чтобы задать эту функцию построения графика.

FitnessFunction = @kur_multiobjective; % Function handle to the fitness function
numberOfVariables = 3; % Number of decision variables
lb = [-5 -5 -5]; % Lower bound
ub = [5 5 5]; % Upper bound
A = []; % No linear inequality constraints
b = []; % No linear inequality constraints
Aeq = []; % No linear equality constraints
beq = []; % No linear equality constraints
options = optimoptions(@gamultiobj,'PlotFcn',@gaplotpareto);

Запуск gamultiobj решатель и отобразить количество решений, найденных на фронте Парето, и количество поколений.

[x,Fval,exitFlag,Output] = gamultiobj(FitnessFunction,numberOfVariables,A, ...
    b,Aeq,beq,lb,ub,options);

Optimization terminated: average change in the spread of Pareto solutions less than options.FunctionTolerance.

fprintf('The number of points on the Pareto front was: %d\n', size(x,1));

The number of points on the Pareto front was: 18

fprintf('The number of generations was : %d\n', Output.generations);

The number of generations was : 317

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

Элитный мультиобъективный генетический алгоритм

Мультиобъективный генетический алгоритм (gamultiobj) работает с населением, используя набор операторов, которые применяются к населению. Население является набором точек в проект пространстве. По умолчанию начальная генеральная совокупность генерируется случайным образом. Следующая генерация населения вычисляется с использованием не доминирующего ранга и дистанционной меры индивидуумов в текущем поколении.

Не доминирующий ранг присваивается каждому индивидууму с помощью относительной соответствия. Индивидуальный 'p' доминирует 'q' ('p' имеет более низкий ранг, чем 'q'), если 'p' строго лучше, чем 'q', по крайней мере, в одной цели и 'p' не хуже, чем 'q' во всех целях. Это то же самое, что и сказать, что в 'q' преобладает 'p' или 'p' не уступает 'q'. Считается, что два индивидуумов и 'q' имеют равные ранги, если ни одна из них не доминирует над другой. Дистанционная мера индивидуума используется для сравнения индивидуумов с равным рангом. Это мера того, как далеко индивидуум находится от других индивидуумов с таким же рангом.

Мультиобъективная функция GA gamultiobj использует управляемый элитный генетический алгоритм (вариант NSGA-II [1]). Элитный GA всегда предпочитает индивидуумов с лучшим значением соответствия (рангом), в то время как контролируемый элитарный GA также предпочитает индивидуумов, которые могут помочь увеличить разнообразие населения, даже если они имеют более низкое значение соответствия. Очень важно сохранить разнообразие населения для сходимости к оптимальному фронту Парето. Это делается путем управления элитными представителями населения по мере прогрессирования алгоритма. Две опции и 'DistanceFcn' используются для контроля элитизма. Опция фракции Парето ограничивает количество индивидуумов на фронте Парето (элитные представители), и функция расстояния помогает поддерживать разнообразие на фронте, отдавая предпочтение индивидуумам, которые находятся относительно далеко на фронте.

Определение мультиобъективных опций GA

Мы можем выбрать функцию измерения расстояния по умолчанию, distancecrowding, что предусмотрено в тулбоксе или написать нашу собственную функцию, чтобы вычислить меру расстояния индивидуума. Функция измерения расстояния скученности в тулбоксе принимает необязательный аргумент, чтобы вычислить расстояние или в функциональном пространстве (фенотипе), или в проектном пространстве (генотипе). Если 'genotype' выбирается, тогда разнообразие на фронте Парето основывается на пространстве проекта. Выбор по умолчанию 'phenotype' и в этом случае разнесение основано на функциональном пространстве. Здесь мы выбираем 'genotype' для нашей функции расстояния. Мы непосредственно изменим значение параметра DistanceMeasureFcn.

options.DistanceMeasureFcn = {@distancecrowding,'genotype'};

Фракция Парето имеет значение по умолчанию 0,35, то есть решатель попытается ограничить количество индивидуумов в текущем населении, которые находятся на фронте Парето, 35 процентами от размера населения. Здесь мы устанавливаем долю Парето равную 0,5.

options = optimoptions(options,'ParetoFraction',0.5);

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

[x,Fval,exitFlag,Output] = gamultiobj(FitnessFunction,numberOfVariables,A, ...
                                        b,Aeq,beq,lb,ub,options);

Optimization terminated: average change in the spread of Pareto solutions less than options.FunctionTolerance.

fprintf('The number of points on the Pareto front was: %d\n', size(x,1));

The number of points on the Pareto front was: 25

fprintf('The average distance measure of the solutions on the Pareto front was: %g\n', Output.averagedistance);

The average distance measure of the solutions on the Pareto front was: 0.051005

fprintf('The spread measure of the Pareto front was: %g\n', Output.spread);

The spread measure of the Pareto front was: 0.181192

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

Изменение критерия остановки

gamultiobj использует три различных критерия, чтобы определить, когда остановить решатель. Решатель останавливается, когда достигается любой из критериев остановки. Он останавливается, когда достигается максимальное количество поколений; по умолчанию это число '200*numberOfVariables'. gamultiobj также останавливается, если среднее изменение распространения фронта Парето над MaxStallGenerations генерации (по умолчанию 100) меньше, чем допуск, указанный в options.FunctionTolerance. Третий критерий - это максимальное время, предел в секундах (по умолчанию это Inf). Здесь мы изменяем критерий остановки, чтобы изменить FunctionTolerance с 1e-4 до 1e-3 и увеличить MaxStallGenerations до 150.

options = optimoptions(options,'FunctionTolerance',1e-3,'MaxStallGenerations',150);

Запуск gamultiobj решатель и отобразить количество решений, найденных на фронте Парето, и количество поколений.

[x,Fval,exitFlag,Output] = gamultiobj(FitnessFunction,numberOfVariables,A, ...
    b,Aeq,beq,lb,ub,options);

Optimization terminated: average change in the spread of Pareto solutions less than options.FunctionTolerance.

fprintf('The number of points on the Pareto front was: %d\n', size(x,1));

The number of points on the Pareto front was: 25

fprintf('The number of generations was : %d\n', Output.generations);

The number of generations was : 152

Мультиобъективная гибридная функция GA

Мы будем использовать гибридную схему, чтобы найти оптимальный фронт Парето для нашей мультиобъективной задачи. gamultiobj может достигнуть области около оптимального фронта Парето относительно быстро, но для достижения сходимости может потребоваться много вычислений функции. Обычно используемый метод состоит в том, чтобы запускать gamultiobj для небольшого количества поколений, чтобы приблизиться к оптимальному фронту. Затем решение из gamultiobj используется в качестве начальной точки для другого решателя оптимизации, который быстрее и эффективнее для локального поиска. Используем fgoalattain как гибридный решатель с gamultiobj. fgoalattain решает задачу достижения цели, которая является одной из формулировок для минимизации мультиобъективной задачи оптимизации.

Гибридная функциональность в мультиобъективной функции gamultiobj немного отличается от функции GA с одной целью. В одной цели GA гибридная функция запускается в лучшей точке, возвращаемой GA. Однако в gamultiobj гибридный решатель начнется во всех точках на фронте Парето, возвращенных gamultiobj. Новые индивидуумы, возвращенные гибридным решателем, объединяются с существующим населением, и получается новый фронт Парето. Может быть полезно увидеть синтаксис fgoalattain функция, чтобы лучше понять, как выходы gamultiobj внутренне преобразуется во вход fgoalattain функция. gamultiobj оценивает псевдовесы (требуемый вход для fgoalattain) для каждой точки на фронте Парето и запускает гибридный решатель, начиная с каждой точки на фронте Парето. Другой необходимый вход, цель, является вектором, задающим цель для каждой цели. gamultiobj предоставляет этот вход в качестве крайних точек фронта Парето, найденных до сих пор.

Здесь мы бегаем gamultiobj без гибридной функции.

[x,Fval,exitFlag,Output] = gamultiobj(FitnessFunction,numberOfVariables,A, ...
    b,Aeq,beq,lb,ub,options);

Optimization terminated: average change in the spread of Pareto solutions less than options.FunctionTolerance.

fprintf('The number of points on the Pareto front was: %d\n', size(x,1));

The number of points on the Pareto front was: 25

fprintf('The average distance measure of the solutions on the Pareto front was: %g\n', Output.averagedistance);

The average distance measure of the solutions on the Pareto front was: 0.0434477

fprintf('The spread measure of the Pareto front was: %g\n', Output.spread);

The spread measure of the Pareto front was: 0.17833

Здесь мы используем fgoalattain как гибридная функция. Мы также сбрасываем генераторы случайных чисел, чтобы мы могли сравнить результаты с предыдущим запуском (без гибридной функции).

options = optimoptions(options,'HybridFcn',@fgoalattain);

Сброс случайного состояния (только для сравнения с предыдущим запуском)

strm = RandStream.getGlobalStream;
strm.State = Output.rngstate.State;

Запустите решатель GAMULTIOBJ с гибридной функцией.

[x,Fval,exitFlag,Output,Population,Score] = gamultiobj(FitnessFunction,numberOfVariables,A, ...
    b,Aeq,beq,lb,ub,options);

Optimization terminated: average change in the spread of Pareto solutions less than options.FunctionTolerance.

fprintf('The number of points on the Pareto front was: %d\n', size(x,1));

The number of points on the Pareto front was: 25

fprintf('The average distance measure of the solutions on the Pareto front was: %g\n', Output.averagedistance);

The average distance measure of the solutions on the Pareto front was: 0.128241

fprintf('The spread measure of the Pareto front was: %g\n', Output.spread);

The spread measure of the Pareto front was: 0.422208

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

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

options = optimoptions(options,'HybridFcn',[]); % No hybrid function
% Provide initial population and scores 
options = optimoptions(options,'InitialPopulationMatrix',Population,'InitialScoresMatrix',Score);
% Run the GAMULTIOBJ solver with hybrid function.
[x,Fval,exitFlag,Output,Population,Score] = gamultiobj(FitnessFunction,numberOfVariables,A, ...
    b,Aeq,beq,lb,ub,options);

Optimization terminated: average change in the spread of Pareto solutions less than options.FunctionTolerance.

fprintf('The number of points on the Pareto front was: %d\n', size(x,1));

The number of points on the Pareto front was: 25

fprintf('The average distance measure of the solutions on the Pareto front was: %g\n', Output.averagedistance);

The average distance measure of the solutions on the Pareto front was: 0.0595902

fprintf('The spread measure of the Pareto front was: %g\n', Output.spread);

The spread measure of the Pareto front was: 0.21967

Ссылки

[1] Kalyanmoy Deb, "Multi-Objective Optimization using Evolutionary
Algorithms", John Wiley & Sons ISBN 047187339.