Сдам Сам

ПОЛЕЗНОЕ


КАТЕГОРИИ







Решение оптимизационных задач средствами MATLAB.





Лекция 7

Решение оптимизационных задач средствами MATLAB.

 

Задачи оптимизации в проектировании. Методы оптимизации. Оптимизация с помощью Optimization Toolbox. Задание целевых функций. Типы ограничений. Определение линейных ограничений. Границы и общие линейные неравенства. Линейные уравнения. Определение нелинейных ограничений. Выбор решателя и опций. Параметры и настройки оптимизации. Поиск глобального оптимума. Генетические алгоритмы.

 

Проектирование должно быть результативным, а стать реализованным «в металле» имеет шанс только оптимальный проект. Оптимальность – фундаментальный принцип природы (примеры: из всех виртуальных состояний физически возможны только состояния с минимальной потенциальной энергией; свет в преломляющей среде «выбирает» путь скорейшего прохождения).

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

Методы оптимизации

 

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

 

В настоящее время для решения оптимальных задач применяют в основном следующие методы:

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

 

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

 

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

 

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

 

Линейное программирование представляет собой математический аппарат, разработанный для решения оптимальных задач с линейными выражениями для критерия оптимальности и линейными ограничениями на область изменения переменных. Такие задачи обычно встречаются при решении вопросов оптимального планирования производства с ограниченным количеством ресурсов, при определении оптимального плана перевозок (транспортные задачи) и т. д.

 

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

 

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

 

Как правило, нельзя рекомендовать какой-либо один метод, который можно использовать для решения всех без исключения задач, возникающих на практике.

 


Классификация методов оптимизации по математической природе оптимизируемых величин.

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

 

Одномерная оптимизация

Понятно, что конструкцию нет смысла оптимизировать по одному из размеров, но методы оптимизации скалярных величин X Î R 1 могут использоваться как вспомогательные для оптимизации по направлению (например, по направлению градиента). Одномерная оптимизация может иметь смысл при поиске оптимальных условий применения, например, угла возвышения при выстреле или задержки срабатывания ракетного двигателя для получения максимальной дальности полета, высоты раскрытия кассеты для получения максимальной эффективности действия и т.п.

 

Многомерная оптимизация

Поиск наилучшего значения целевой функции в n -мерном пространстве X Î Rn (или в ограниченной области X Î D Ì Rn) называется многомерной или конечномерной оптимизацией. Методы многомерной оптимизации составляют основу аппарата оптимального проектирования, выполняющего поиск оптимального сочетания проектных параметров. К этому классу методов принадлежат большинство существующих программ для ЭВМ и сам термин математическое программирование.

 

Оптимальное управление

Объектами оптимизации могут быть функции на отрезке [ a, b ] ( ), например, закон управления, минимизирующий затраты на совершение маневра, форма образующей головной части с минимальным сопротивлением движению в воздухе или прочной преграде. Математические методы решения задач оптимального управления связаны с минимизацией целевого функционала в банаховых и гильбертовых пространствах. Доказательство применимости этих методов (выпуклость функционалов и т.п.) не всегда возможно. Универсальные методы конечномерной численной оптимизации в меньшей степени используют априорные свойства математической модели, их можно применить и для решения бесконечномерных задач после дискретизации разбиением отрезка [ a, b ] на конечное число интервалов. Еще один способ – сужение класса функций (параболы, полиномы) – сводит задачу поиска оптимальной функции к оптимизации параметров известной функции.

 

Безусловная оптимизация

При отсутствии ограничений на возможные значения переменных оптимизации решением задачи является значение скалярной или векторной переменной X, доставляющее максимальное (max) или минимальное (min) значение скалярной функции W (X) на всем пространстве En:

. (1)

Обычно задачу оптимизации формулируют как минимизацию, имея в виду, что алгоритм минимизации целевой функции с противоположным знаком найдет ее максимальное значение. Решение задачи безусловной оптимизации определяется только экстремальными свойствами целевой функции, что упрощает процедуру решения, но для оптимального проектирования этот класс задач не характерен, так как достижению наилучшего значения целевой функции обязательно препятствуют какие-то существенные ограничения (например, увеличению коэффициента наполнения препятствуют прочностные ограничения). Но свободный оптимум могут иметь условия стрельбы (угла возвышения для максимальной дальности стрельбы, высоты или задержки срабатывания), при которых нужно искать оптимальные проектные параметры. Есть еще одна причина не пренебрегать безусловной оптимизацией в оптимальном проектировании: большинство численных методов оптимизации разработано именно для этого класса задач, поскольку признак оптимальности решения в данном случае (экстремум целевой функции) наиболее универсален.

 

Условная оптимизация

Задачи оптимизации со скалярной целевой функцией, функциональными и прямыми ограничениями можно записать в виде:

min W (X)

Fk (X) ³ Fk тр, k = 1, …, m,

ai £ x i £ bi, i= 1, …, n,

где символ'³' в функциональных ограничениях обозначает знак строгого или нестрогого неравенства, или знак равенства. Наличие ограничений сильно усложняет процесс поиска условного экстремума. Мощный класс методов условной оптимизации – методы возможных направлений – реализуют сложные коммерческие программные продукты. Методы штрафных и барьерных функций позволяют приводить задачу к виду (1) и использовать для решения задач с ограничениями методы безусловной оптимизации.

 

Метод барьерных функций

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

L (x) = f (x) + ,

где С – достаточно малая величина. В пределах допустимой области вдали от ее границ функция L (x)практически совпадает с f (x), но с приближением к границам знаменатель стремится к нулю, а функция L (x) – к бесконечности. Таким образом, минимизация L (x)приводит почти к тому же результату, что и условная минимизация f (x)(рис. 2 б). Степень близости приближенного решения к истинному зависит от значения коэффициента С (обычно решается последовательность задач с уменьшающимся С). В комплексной целевой функции некоторые штрафные слагаемые, которые соответствуют «непреодолимым» ограничениям, можно заменить выражениями

.


Линейное программирование

Простейший частный случай задачи математического программирования – линейное программирование (ЛП) – состоит в минимизации или максимизации линейной функции на допустимом множестве, заданном линейными ограничениями:

, k = 1, …, m.

Особенность задач ЛП в том, линейная целевая функция в системе линейных ограничений достигает минимума в одной из угловых точек (рис. 3 а). На этом свойстве основан симплекс-метод решения задач ЛП за конечное число шагов направленного перебора угловых точек допустимой области с последовательным уменьшением значений целевой функции (рис. 3 б).

а б в

Рис. 3. Иллюстрация двумерной (а) и трехмерной (б) задач ЛП и задачи КП (в)

 

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

 

Квадратичное программирование

Целевая функция, заданная квадратичной формой с симметричной, положительно определенной матрицей g

имеет единственную точку минимума, ее линии уровня – эллипсы. Методы квадратичного программирования (КП) решения задач с квадратичной целевой функцией и линейными ограничениями (рис. 3 в) так же хорошо разработаны, как и методы ЛП, и используются как вспомогательные при решении общих задач.

 

Выпуклое программирование

Из всех задач оптимизации с нелинейными функционалами самые благоприятные для решения задачи выпуклого программирования, в которых целевая функция и функции-ограничения обладают свойствами выпуклости. Как известно, график выпуклой функции лежит выше касательной в любой его точке. Ограничения сверху на выпуклые функции образуют выпуклую допустимую область, содержащую вместе с любой парой точек и отрезок между ними. Это очень важное свойство с точки зрения поиска экстремума, но еще важнее то, что экстремальная точка единственна и является искомым решением задачи. Большинство методов нелинейного программирования (НЛП) предполагают наличие единственного локального экстремума, но только в выпуклой области может существовать не более одной точки, в которой выполняется критерий оптимальности выпуклой целевой функции.

 

Задачи нелинейного программирования общего вида

Если целевая функция или хотя бы одна из функций-ограничений не обладают свойствами выпуклости, выполнение локальных условий экстремальности в какой-то точке не означает оптимальности этой точки в целом. Нужно найти все локальные экстремумы и выбрать из них самый лучший (глобальный) экстремум (рис. 4 а). В многомерной оптимизации исчерпывающий поиск практически невозможен из-за очень большой трудоемкости. Рациональные попытки многоэкстремальной оптимизации сводятся к разумному компромиссу между трудоемкостью и надежностью отыскания глобального экстремума. Используется априорная информация для сужения области поиска. Например, зная предельные значения первой производной целевой функции, можно выделить окрестности найденных локальных экстремумов, в которых исключено существование других возможных решений. К сожалению, важная априорная информация о поведении целевой функции отсутствует для алгоритмически заданных функций, поэтому применение сложных многоэкстремальных методов невозможно. В оптимальном проектировании применяют сочетание методов глобального зондирования области поиска для выбора исходных приближений и методов локального поиска для продвижения из перспективных исходных приближений к локальным экстремумам (рис. 4 б).

 

Рис. 4. Многоэкстремальная целевая функция


Minimization Problems

Type Formulation Solver
Scalar minimization such that l < x < u (x is scalar) fminbnd
Unconstrained minimization fminunc, fminsearch
Linear programming such that A·xb, Aeq·x = beq, lxu linprog
Quadratic programming such that A·xb, Aeq·x = beq, lxu quadprog
Constrained minimization such that c (x) ≤ 0, ceq (x) = 0, A·xb, Aeq·x = beq, lxu fmincon
Semi-infinite minimization such that K (x, w) ≤ 0 for all w, c (x) ≤ 0, ceq (x) = 0, A·xb, Aeq·x = beq, lxu fseminf
Binary integer programming such that A·xb, Aeq·x = beq, x binary bintprog

Multiobjective Problems

Type Formulation Solver
Goal attainment such that F (x) – w · γ ≤ goal, c (x) ≤ 0, ceq (x) = 0, A·xb, Aeq·x = beq, lxu fgoalattain
Minimax such that c (x) ≤ 0, ceq (x) = 0, A·xb, Aeq·x = beq, lxu fminimax

Equation Solving Problems

Type Formulation Solver
Linear equations C · x = d, n equations, n variables \ (matrix left division)
Nonlinear equation of one variable f (x) = 0 fzero
Nonlinear equations F (x) = 0, n equations, n variables fsolve

Пример минимакса

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

Рассмотрим задачу минимизации максимальных значений функций в заданных ограничениях.

,

где x, b, beq, lb, и ub - вектора, A и Aeq - матрицы, c(x), ceq(x), и F(x) – функции с результирующим значением в виде вектора. F(x), c(x), и ceq(x) могут быть нелинейными функциями.

 

Задача: найти x1, x2 при которых максимальное значение минимально.

 

М-файл:

function f = myfun(x)

f(1)= 2*x(1)^2+x(2)^2-48*x(1)-40*x(2)+304;

f(2)= -x(1)^2 - 3*x(2)^2;

f(3)= x(1) + 3*x(2) -18;

f(4)= -x(1)- x(2);

f(5)= x(1) + x(2) - 8;

 

x0 = [0.1; 0.1];

[x,fval] = fminimax(@myfun,x0)

 

Local minimum possible. Constraints satisfied.

fminimax stopped because the size of the current search direction is less than twice the default value of the step size tolerance and constraints are satisfied to within the default value of the constraint tolerance.

<stopping criteria details>

 

x =

3.999999886593829

4.000000113404526

 

fval =

 

0.000000000052694

-64.000001814459310

-1.999999773192592

-7.999999999998355

-0.000000000001645

 

Графическая иллюстрация результата оптимизации

 

figure;

[X1,X2] = meshgrid(-5:0.5:5,-5:0.5:5);

Z=2*X1.^2+X2.^2-48*X1-40*X2+304;

subplot(2, 2, 1); surf(X1,X2,Z);

hold on;

plot3(linspace(4, 4), linspace(4, 4), linspace(-100, 100), 'ro');

hold off;

 

[X1,X2] = meshgrid(-5:0.5:5,-5:0.5:5);

Z=-X2.^2-3*X2.^2;

subplot(2, 2, 2); surf(X1,X2,Z);

hold on;

plot3(linspace(4, 4), linspace(4, 4), linspace(-100, 100), 'ro');

hold off;

 

[X1,X2] = meshgrid(-5:0.5:5,-5:0.5:5);

Z=X1+3*X2-18;

subplot(2, 2, 3); surf(X1,X2,Z);

hold on;

plot3(linspace(4, 4), linspace(4, 4), linspace(-100, 100), 'ro');

hold off;

 

[X1,X2] = meshgrid(-5:0.5:5,-5:0.5:5);

Z=-X1-X2;

subplot(2, 2, 4); surf(X1,X2,Z);

hold on;

plot3(linspace(4, 4), linspace(4, 4), linspace(-100, 100), 'ro');

hold off;

 

figure;

[X1,X2] = meshgrid(-5:0.5:5,-5:0.5:5);

Z=X1+X2-8;

surf(X1,X2,Z);

hold on;

plot3(linspace(4, 4), linspace(4, 4), linspace(-100, 100), 'ro');

hold off;

 

 


Поиск глобального оптимума

 

Методы численной оптимизации прекращают итерации при выполнении некоторого условия, гарантирующего, что решений, лучших, чем последняя рабочая точка не существует. Но эти гарантии распространяются только на ближайшую окрестность лучшей точки, потому что используются локальные признаки отсутствия возможных направлений улучшения целевой функции. Если целевая функция и ограничения не выпуклы, нельзя исключить, что локальные условия оптимальности выполняются и в других точках допустимой области, а найденное решение – не лучший из локальных экстремумов. Формальных признаков глобального экстремума (лучшего среди локальных) не существует, что создает проблему определения стратегии его поиска. Можно найти методами выпуклой оптимизации несколько локальных экстремумов в разных частях допустимой области и выбрать лучший из них. Другая стратегия – вычисление целевой функции в пробных точках, распределенных по всей области, и последующий локальный поиск из наилучшей точки. В последнее время развиваются стратегии, моделирующие бионическую мотивацию выживания в отборе точек, претендующих на глобальный экстремум.

 

Методы случайного поиска отличаются от детерминированных итерационных методов тем, что вместо определенного правила выбора направления рабочего шага исследуют некоторую часть области поиска, распределяя в ней пробные точки случайным образом. Простые методы случайного поиска разыгрывают n 1 пробных точек на гиперсфере малого радиуса r 1 (пробный шаг) вокруг текущей точки (рис. 5). В каждой точке на сфере и в центре вычисляются значения целевой функции, затем, если лучшая точка находится на сфере, а не в центре, из центральной точки через нее выполняется рабочий шаг длиной r 2 >> r 1. В новой точке процедура повторяется. Если наилучшей остается центральная точка, она проверяется на локальный экстремум.

Рис. 5. Траектория случайного поиска

 

Чтобы найти другие локальные экстремумы и выбрать из них глобальный, надо повторить всю процедуру из какой-либо точки, не принадлежащей окрестности найденного локального решения. Для этого выполняют очень большой шаг длиной r 3 >> r 2. Локальный экстремум находится с некоторой вероятностью, тем большей, чем больше число пробных точек. За приемлемую вероятность отыскания оптимума приходится платить слишком большим числом пробных точек. В оптимальном проектировании функционально сложных изделий полный расчет комплексного критерия оптимальности (целевой функции и всех функций-ограничений) одного пробного варианта может занять существенное время. Чтобы реализовать достаточное количество пробных вариантов за разумное время, приходится сокращать трудоемкость прикладных программ путем упрощения моделей, укрупнения шагов и т.п., что снижает ценность результата оптимизации до отрицательной (вредной): искаженный «оптимум» дезориентирует постановщика задачи.

Для проведения экспериментов сконструирована функция, имеющая четыре минимума (рис. 6), поскольку представляет собой сумму четырех функций плотности двумерного нормального распределения с обратным знаком.

 

function f=Min4(X,Y)

if nargin<2 Y=X(2,:); X=X(1,:); end

f = f_Norm2(X-1.5,Y-2,-0.7) + f_Norm2(X*0.9+1.5,Y+1,0.7);

f = f + f_Norm2(X+2,Y-2,-0.5) + f_Norm2(X-2,Y+2);

f = 0.25-f;

%Плотность стандартного 2-мерного нормального распределения

function f_n2= f_Norm2(x1,x2,r)

if nargin<3 r=0;end

if abs(r)<0.01

f_n2=exp(-(x1.^2+x2.^2)./2)/(pi*2);

else

a=1-r^2;

t=(x1.^2-2*r*x1.*x2+x2.^2)./(2*a);

f_n2=exp(-t)/(sqrt(a)*pi*2);

end

 

Вычислив с помощью файл-функции аппликаты функции F = Min4(x, y) на расчетной сетке (X,Y), построим поверхность и ее линии уровня:

 

[X Y]=meshgrid([-3:0.1:3],[-3:0.1:3]); F=Min4(X,Y); surfc(X,Y,F), hold on, min(min(F));

ans = 0.025612905653507

 

Рис. 6. Многократная локальная оптимизация методом случайного поиска

 

Минимум сеточной функции составляет 0.0256. Файл-функция Accidental_Search, реализует простейший алгоритм случайного поиска из заданной исходной точки. В окрестности рабочей точки она вычисляет целевую функцию в 20-и случайных точках, и еще столько же точек генерирует, если ни одна пробная точка не улучшает целевую функцию. Эта программа возвращает минимальное значение целевой функции, последовательность рабочих точек и общее количество обращений к вычислению целевой функции на траектории поиска.

 

function [z,T,M]=Accidental_Search(N,T)

if nargin<2 T=[0;0]; end

r1=0.3; n1=20;r2=0.9;M=0;

for i=1:N

Z=GenPoints(n1*2,r1)+repmat(T(:,end),1,n1*2);

F=Min4(Z(:,1:n1));M=M+n1;

z0=Min4(T(:,end));

[z,I]=min(F);

if z0<z

F=Min4(Z(:,n1+1:n1*2));M=M+n1;

[z,I]=min(F);I=I+n1;

if z0<z break, end

end

T(:,end+1)=T(:,end)+(Z(:,I)-T(:,end))*r2;

end

%

function f=GenPoints(n,r)

[X,I] = sort(rand(1,n)*2*pi);

f=[r*sin(X);r*cos(X)];

 

Следующие команды строят траектории поиска из исходных точек [0; 0], [1;-1], [-1; 1] и [1; 1]:

 

[f,T,M]=Accidental_Search(50,[0;0]);M, f, T(:,end)', plot(T(1,:),T(2,:),'k.')

[f,T,M]=Accidental_Search(50,[1;-1]); M, f, T(:,end)', plot(T(1,:),T(2,:),'r.')

[f,T,M]=Accidental_Search(80,[-1;1]);M, f, T(:,end)', plot(T(1,:),T(2,:),'m.')

[f,T,M]=Accidental_Search(80,[1;1]);M, f, T(:,end)', plot(T(1,:),T(2,:),'b.')

 

M = 380 f = 0.0306 ans = -1.6210 -0.9722

M = 140 f = 0.0945 ans = 1.9792 -1.9168

M = 280 f = 0.0722 ans = -2.0513 2.0355

M = 120 f = 0.0281 ans = 1.5557 1.8932

 

На рис. 6 видно, что все траектории поиска успешно заканчиваются в центре самых внутренних линий уровня. Глобальный минимум почти совпадает с минимумом сеточной функции 0.0281» 0.0256, но потребовалось две тысячи вычислений целевой функции, чтобы в этом убедиться. Если бы перебор исходных точек выполнялся случайным образом, число обращений к целевой функции было бы существенно больше.


Генетические алгоритмы

 

Генетические алгоритмы – это адаптивные методы поиска, которые в последнее время часто используются для решения задач функциональной и структурной оптимизации. Попытаемся разобраться в технологии генетических алгоритмов применительно к сложным задачам параметрической оптимизации. С этой целью рассмотрим задачу оптимального распределения ресурсов на примере оптимального проектирование боевой части (БЧ) ракеты. Оптимальное проектирование БЧ может осуществляться в два этапа: сначала оптимизируется поле поражающих элементов (ПЭ) по критерию эффективности действия, а на втором этапе создается конструкция, реализующая оптимальное распределение ПЭ по различным участкам поля. Важно, чтобы на этапе оптимизации поля учитывались существенные ограничения. В самом простом виде задачу оптимального распределения известного количества ПЭ можно записать как максимизацию полной вероятности поражения. Для этого, разделив область поля на n зон, определив вероятность pi поражения цели одним попавшим ПЭ в i -й зоне, выразим условную вероятность поражения цели при попадании в нее xi ПЭ в i -й зоне:

, где qi = 1 – pi.

Вероятности Ri нахождения цели в i -й зоне при накрытии ее полем также зависят от условий встречи. В результате находим оптимальное распределение данного количества ПЭ:

Это дискретная задача оптимизации, альтернативами которой являются последовательности целых чисел(x 1, x 2, … xn), xi Î [0, n ], ∑ xi = N. Количество таких альтернатив (по схеме выборки с возвратом) составляет nN. Если n имеет порядок 10, а N – тысячи, полный перебор вариантов немыслим. Необходимо найти эффективный метод выбора оптимальной альтернативы.

 

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

 

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

 

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

 

Общей закономерностью различных механизмов эволюции является вытеснение из популяции наименее приспособленных экземпляров.

 

Механизмы рекомбинации могут быть реализованы разными способами, общим для них является наследование генов m родителей (m = 1, 2, 3, …), то есть новая хромосома так или иначе представляет популяцию. На рис. 7 показан возможный вид оператора рекомбинации (2 родителя, 2 потомка), так называемый одноточечный кроссовер: хромосомы родителей разрываются на границе двух соседних генов, а затем происходит обмен частями хромосом родителей и «склеивание» их в новые хромосомы.

Рис. 7. Возможная схема рекомбинации хромосом

 

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

Сформируем популяцию из L хромосом одинаковой длины M, равной числу зон поля ПЭ. Целочисленными генами хромосом являются количества ПЭ, распределяемых в i -ю зону, (считая позиции гена в хромосоме перенумерованными так же, как и зоны поля ПЭ). Популяция – массив ячеек Pop, хромосомы – элементы этого массива, их гены вначале имеют случайное значение в интервале [0, 50]:

L=30; N=50; M=4; for i=1:L Pop{i} = fix(rand(1,M)*N); end

Pop{1}

ans = 47 11 30 24

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

Goal = 'sum(R.*(1-q.^Pop{j}))'; Penalty = 'max([0,sum(Pop{j})/N-1])*0.35';

После ввода исходных данных, приспособленность первой особи популяции можно вычислить так:

R=[0.2 0.3 0.4 0.1]; p=[0.04 0.05 0.03 0.05]; q=1-p;

j=1; F=eval(Goal)-eval(Penalty)

F = 0.1764

Чтобы осуществить механизм эволюции, назначим его основные параметры. Порог стабильности – число потомков, передаваемых в следующее поколение, установим на уровне 0,2 от объема популяции. Постоянную точку разрыва хромосомы при скрещивании установим в середине гена D=M/2+1. Зададим вероятность мутации 0,6 и максимальное число поколений 60:

Elit=fix(L*0.2); D=M/2+1; Pmut=0.6; Ngen=80;

 

Следующий скрипт-файл осуществляет эволюцию заданного числа поколений популяции:

%GeneticA

Npop = length(Pop);

for k=1:Ngen

for j=1:Npop G(j)=eval(Goal)-eval(Penalty);end

[Y,I] = sort(G); I=I(Npop:-1:1);

PopOld = Pop; Pop={};

[Par, n] = SelPair(I,Elit);

for j=1:n

Pop{j}=CrossOver(PopOld, 3, Par(j,:));

g(j)=eval(Goal)-eval(Penalty);

end

[y,i] = sort(g);

PP=find(G(I)<g(i)); if isempty(PP) continue, end

j= PP(1);

PP=[PopOld(I(1:j)), Pop(i(j+1:Npop))];

for ii = 1:Npop if rand>Pmut PP{ii}=Mutation(PP{ii}); end; end

Pop = PP;

end

for j=1:Npop G(j)=eval(Goal);end % оценка последнего поколения

[y,i] = min(G); [Y,j] = max(G); % элементы с min и max оценками

 

Случайный выбор пар предков выполняется функцией SelPair, которая сначала сортирует по возрастанию элементы случайной матрицы с нулевой диагональю, а затем составляет пары индексов элементов согласно их порядку:

function [out, k]=SelPair_(N,Elit)

n=length(N); if nargin>1 n=Elit; end

k=n*(n-1); out=zeros(n,2);

A=rand(n); A=A-diag(diag(A)-1);

[V, I] = sort(A(:));

for i=1:k

T=fix((I(i)-1)/n);

out(i,:)=[N(I(i)-T*n),N(T+1)];

end

 

Мутацию – случайное изменение генов хромосомы – можно осуществить суммированием хромосомы с вектором такой же длины, элементами которого являются случайные комбинации чисел 1 и –1:

function X = Mutation(X)

Rnd=ones(size(X));

Rnd(rand(size(X))>0.5)=-1;

X=X+Rnd;

X(X<0)=0;

 

Такая схема мутации вполне подходит для случайных изменений распределения элементов по зонам (последним оператором предусмотрено, что число элементов в зоне не сможет стать отрицательным).

 

Механизмы рекомбинации определяются функцией CrossOver:

 

function [N1, N2] = CrossOver(X,D,Prnt)

N1 = X{Prnt(1)};N2 = X{Prnt(2)};

Rnd=rand(size(N1));Ind1=find(Rnd<0.5);Ind2=find(Rnd>0.5);

N1(Ind1) = X{Prnt(2)}(Ind1);

N2(Ind1) = X{Prnt(1)}(Ind1);

 

Все исходные данные для задачи введены, рабочие структуры созданы, необходимые процедуры для реализации генетического алгоритма разработаны. Выполним программу GeneticA и выведем основные результаты:

GeneticA, x=Pop{j}, W=sum(R.*(1-q.^x))

x = 8 21 24 0 W = 0.4610

 

Результатом выполнения алгоритма будет оптимальное распределение ПЭ по n зонам и полная вероятность поражения W.

Лекция 7

Решение оптимизационных задач средствами MATLAB.

 

Задачи оптимизации в проектировании. Методы оптимизации. Оптимизация с помощью Optimization Toolbox. Задание целевых функций. Типы ограничений. Определение линейных ограничений. Границы и общие линейные неравенства. Линейные уравнения. Определение нелинейных ограничений. Выбор решателя и опций. Параметры и настройки оптимизации. Поиск глобального оптимума. Генетические алгоритмы.

 

Проектирование должно быть результативным, а стать реализованным «в металле» имеет шанс только оптимальный проект. Оптимальность – фундаментальный принцип природы (примеры: из всех виртуальных состояний физически возможны только состояния с минимальной потенциальной энергией; свет в преломляющей среде «выбирает» путь скорейшего прохождения).

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







ЧТО ТАКОЕ УВЕРЕННОЕ ПОВЕДЕНИЕ В МЕЖЛИЧНОСТНЫХ ОТНОШЕНИЯХ? Исторически существует три основных модели различий, существующих между...

ЧТО ПРОИСХОДИТ, КОГДА МЫ ССОРИМСЯ Не понимая различий, существующих между мужчинами и женщинами, очень легко довести дело до ссоры...

Что вызывает тренды на фондовых и товарных рынках Объяснение теории грузового поезда Первые 17 лет моих рыночных исследований сводились к попыткам вычис­лить, когда этот...

Живите по правилу: МАЛО ЛИ ЧТО НА СВЕТЕ СУЩЕСТВУЕТ? Я неслучайно подчеркиваю, что место в голове ограничено, а информации вокруг много, и что ваше право...





Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте:


©2015- 2024 zdamsam.ru Размещенные материалы защищены законодательством РФ.