Многоцелевые опции генетического алгоритма
В этом примере показано, как создать и справиться, опции для многоцелевого генетического алгоритма функционируют gamultiobj использование optimoptins в Global Optimization Toolbox.
Подготовка проблемы для gamultiobj
gamultiobj находит локальную переднюю сторону Парето для нескольких целевых функций с помощью генетического алгоритма. В данном примере мы будем использовать 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 решатель и отображение количество решений, найденных на передней стороне Парето и количестве поколений.
[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 i.e., решатель попытается ограничить количество индивидуумов в текущем населении, которые находятся на передней стороне Парето к 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.127964
fprintf('The spread measure of the Pareto front was: %g\n', Output.spread);The spread measure of the Pareto front was: 0.421195
Если передние стороны Парето получены 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.0518031
fprintf('The spread measure of the Pareto front was: %g\n', Output.spread);The spread measure of the Pareto front was: 0.306712
Ссылки
[1] Kalyanmoy Deb, "Multi-Objective Optimization using Evolutionary Algorithms", John Wiley & Sons ISBN 047187339.