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

Подготовка проблемы для 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'. У двух индивидуумов 'p' и 'q', как рассматривается, есть равные ранги, если ни один не доминирует над другим. Мера по расстоянию человека используется, чтобы сравнить людей с равным рангом. Это - мера того, как далеко человек от других людей с тем же рангом.

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

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

The spread measure of the Pareto front was: 0.423028

Если передние стороны Парето, полученные одним только 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.0352758

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

The spread measure of the Pareto front was: 0.144154

Ссылки

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