В этом примере показано, как создавать и управлять опциями функции мультиобъективного генетического алгоритма gamultiobj использование optimoptins на панели инструментов глобальной оптимизации.
gamultiobjgamultiobj находит локальный фронт Парето для нескольких объективных функций с помощью генетического алгоритма. Для этого примера мы будем использовать gamultiobj для получения фронта Парето для двух объективных функций, описанных в файле MATLAB kur_multiobjective.m. Это действительная функция, которая состоит из двух целей, каждая из трех переменных решения. Мы также накладываем ограничения на переменные принятия решения -5 < = x (i) < = 5, i = 1,2,3.
type kur_multiobjective.mfunction 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 решатель и отображение количества решений, найденных на передней панели Pareto, и количества поколений.
[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
График Парето отображает две конкурирующие цели. Известно, что для этой проблемы передняя часть Pareto отсоединена. Решение из gamultiobj может захватить фронт Парето, даже если он отключен. Обратите внимание, что при выполнении этого примера результат может отличаться от показанных, поскольку gamultiobj использует генераторы случайных чисел.
Мультиобъективный генетический алгоритм (gamultiobj) работает с населением, используя набор операторов, которые применяются к населению. Совокупность - это набор точек в пространстве проектирования. Начальное заполнение генерируется случайным образом по умолчанию. Следующее поколение популяции вычисляется с использованием не доминирующего ранга и меры расстояния особей в текущем поколении.
Неглавинный ранг присваивается каждому человеку с использованием относительной пригодности. Индивид «p» доминирует над «q» («p» имеет ранг ниже, чем «q»), если «p» строго лучше, чем «q» по крайней мере в одной цели и «p» не хуже, чем «q» во всех целях. Это то же самое, что сказать, что в «q» преобладает «p» или «p» не уступает «q». Два индивида «p» и «q» считаются имеющими равные ранги, если ни одно из них не доминирует над другим. Мера расстояния индивида используется для сравнения индивидов с равным рангом. Это мера того, как далеко человек находится от других людей с тем же рангом.
Мультиобъективная функция GA gamultiobj использует управляемый элитарный генетический алгоритм (вариант NSGA-II [1]). Элитарная ГА всегда отдает предпочтение лицам с лучшей фитнес-ценностью (рангом), тогда как контролируемая элитарная ГА также отдает предпочтение лицам, которые могут помочь увеличить разнообразие населения, даже если они имеют более низкую фитнес-ценность. Очень важно сохранить разнообразие населения для схождения к оптимальному фронту Парето. Это делается путем контроля элитных представителей населения по мере продвижения алгоритма. Для управления элитарностью используются два параметра «ParetoFraction» и «DistureFcn». Вариант фракции Парето ограничивает число лиц на фронте Парето (элитные члены), и функция расстояния помогает поддерживать разнообразие на фронте, отдавая предпочтение лицам, которые находятся относительно далеко на фронте.
Можно выбрать функцию измерения расстояния по умолчанию, 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 решатель и отображение количества решений, найденных на передней панели Pareto, и количества поколений.
[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
Мы будем использовать гибридную схему, чтобы найти оптимальный фронт Парето для нашей многообъективной проблемы. gamultiobj может достичь области вблизи оптимального фронта Парето относительно быстро, но для достижения сходимости может потребоваться много оценок функций. Обычно используется метод запуска gamultiobj для небольшого числа поколений, чтобы приблизиться к оптимальному фронту. Затем решение из gamultiobj используется в качестве начальной точки для другого решателя оптимизации, который быстрее и эффективнее для локального поиска. Мы используем fgoalattain в качестве гибридного решателя с gamultiobj. fgoalattain решает задачу достижения цели, которая является одной формулировкой для минимизации задачи многообъективной оптимизации.
Гибридная функциональность в мультиобъективной функции gamultiobj несколько отличается от функции одиночной цели 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.