WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     | 1 |   ...   | 3 | 4 || 6 | 7 |   ...   | 11 |

3.3.3 Метод "золотого сечения" Гораздо эффективнее, с точки зрения уменьшения затрат на вычисления, метод "золотого сечения":

интервал неопределенности делится не пополам, как в методе дихотомии, а в определенном иррациоac cb нальном соотношении = =.

cb ab 1+ Это соотношение выполняется при = = 1,618033989...

Метод заключается в том, что по заданным a и b как можно точнее определяется значение внутренней точки x1 (см. рис. 3.6, б) по формуле x1 = b – (b – a) / 1,618033989… (3.6) Точка x2 определяется как точка, симметричная точке x1 на отрезке (a – b).

На основе анализа значений F1 = Q (x1) и F2 = Q (x2) интервал неопределенности сокращается путем отбрасывания из рассмотрения отрезка в котором экстремум исключен, исходя из условий унимодальности Q (u). Далее мы определим симметричную точку внутри новых границ, вычисляем значение Q в этой точке, проводим анализ и т.д. до тех пор, пока разность между симметричными точками внутри интервала неопределенности больше. Блок-схема алгоритма метода "золотого сечения" представлена на рис. 3.7.

Q F F x1 x a a+b b u а) Начало ввод a, b, a + b a + b b = x2 x1 = - ; x2 = + ; a = x2 2 2 Qmin = F1 Qmin = FF1 = Q(x1); F2 = Q(x2) xmin = x1 xmin = x да a – b < нет вывод xmin, Qmin Останов да F1 < F2 нет б) Рис. 3.5 Метод деления отрезка пополам:

а – геометрическая интерпретация; б – блок-схема a c b а) F F x1 x a b б) Рис. 3.6 Метод "золотого сечения":

а – золотое сечение; б – геометрическое представление Начало ввод a, b, x2 = a + (b - a) / 1,618033989;

x1 = b - (x2 - a);

F1 = Q(x1); F2 = Q(x2) да нет F1 F да да нет нет x2-x1 x2-xmin = x2,F2 min = x1,Fa = x1; x1 = x2; b = x2; x2 = x1;

x2 = b - (x1 – a); x1 = a + (b – x2);

Вывод min F1 = F2; F2 = Q(x2) F2 = F1; F1 = Q(x1) Конец Рис. 3.7 Блок-схема метода "золотого сечения" 3.3.4 Метод Фибоначчи Метод, использующий числа Фибоначчи, позволяет наиболее эффективно достичь заданной точности в поиске экстремума функции Q (u). Числа Фибоначчи определяются соотношением F0 = F1 = 1; Fk = Fk–1 + Fk–2; k = 2, 3, … При большом "k" отношение соседних чисел Фибоначчи близко к отношению "золотого сечения".

Этот метод делит интервал неопределенности не в постоянном соотношении, а в переменном и предполагает некоторое, вполне определенное, зависящее от, число вычислений значений функции Q (u).

Начало ввод a, b, Определение n и F(n), соответствующее заданному да нет n = F(n) b - a x1 = a + (b - a);

min = ; Q(min) F(n + 2) F(n +1) x2 = a + (b - a);

Вывод min F(n + 2) F1 = Q(x1); F2 = Q(x2) Конец да нет n = да да F1 F2 нет F1 F2 нет min = x1 min = x2 b = x1; x2 = x1; a = x1; x1 = x2;

n = n – 1; n = n – 1;

F(n) F(n +1) x1 = a + (b - a); x2 = a + (b - a) Вывод min F(n + 2) F(n + 2) F1 = Q(x1) F2 = Q(x2) Конец Рис. 3.8 Блок-схема метода Фибоначчи По заданному определяется количество вычислений n и соответствующее ему число Фибоначчи Fn, исходя из соотношения b - a =.

2Fn+В остальном схема метода близка к методу "золотого сечения" в котором значение x1 и x2 (см. рис.

3.8) определяются отношением соответствующих чисел Фибоначчи.

3.4 МЕТОДЫ МНОГОМЕРНОЙ ОПТИМИЗАЦИИ В настоящее время разработано огромное число методов многомерной оптимизации, охватывающие почти все возможные случаи. Здесь рассматривается лишь несколько основных, считающихся классическими, методов поиска экстремума функции многих переменных.

Смысл всех методов нахождения безусловного экстремума функции нескольких переменных заключается в том, что по определенному правилу выбирается последовательность значений {u} вектора u такая, что Q (ul+1) () Q (ul). Так как целевая функция предполагается ограниченной, то такая последовательность ее значений стремится к пределу.

В зависимости от принятого алгоритма и выбора начальной точки этим пределом может быть локальный или глобальный экстремум функции Q (u).

3.4.1 Метод Гаусса-Зайделя Метод заключается в последовательном определении экстремума функции одной переменной с точностью до вдоль каждой координаты, т.е. фиксируются все координаты, кроме одной, по которой и осуществляется поиск экстремума Q. Потом та же процедура осуществляется при фиксации следующей координаты.

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

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

u uРис. 3.9 Характер движения к оптимуму в методе Гаусса-Зейделя Идея метода заключается в том, что находятся значения частных производных по всем независимым переменным – Q / u, = 1, n, которые определяют направление градиента в рассматриваемой Q Q Q точке Q = 1 + 2 +... + n, и осуществляется шаг в направлении обратном направлению градиенu1 u2 un та, т.е. в направлении наибыстрейшего убывания целевой функции (если ищется минимум). Итерационный процесс имеет вид uk +1 = uk - kQ(uk), (3.7) где параметр k 0 задает длину шага.

Алгоритм метода градиента при непосредственном его применении включает в себя следующие этапы.

0 0 1 Задается начальное значение вектора независимых переменных (u1, u2,..., un), определяющего точку, из которой начинается движение к минимуму.



0 0 2 Рассчитывается значение целевой функции в начальной точке Q0(u1, u2,..., un).

3 Определяется направление градиента в начальной точке (рис. 3.10).

u• uu u uРис. 3.10 Характер движения к оптимуму в методе градиента 4 Делается шаг в направлении антиградиента при поиске минимума, в результате чего попадают в точку u1.

5 Процесс поиска продолжается, повторяя все этапы с п. 2, т.е. вычисляется Q1(u1, u1,..., u1), опре2 деляется направление градиента в точке u1, делается шаг и т.д.

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

Итерационный процесс поиска обычно прекращается, если вы- полняются неравенства uk -uk -1, Q(uk)- Q(uk -1) / Q(uk -1), Q(uk )/ u, где,, – заданные числа.

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

3.4.3 Метод наискорейшего спуска При применении метода градиента на каждом шаге вычисляются значения всех частных производных оптимизируемой функции Q по всем независимым переменным U, что при большом числе этих переменных приводит к весьма большому времени поиска оптимума. Сократить время поиска позволяет метод наискорейшего спуска, блок-схема которого отображена на рис. 3.4, где – точность вычисления, H – величина шага, n – размерность вектора u, Q – алгоритм вычисления целевой функции Q (u), L – количество шагов по конкретному направлению градиента функции Q.

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

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

3.4.4 Метод квантования симплексов Симплексный метод относится к группе безградиентных методов детерминированного поиска. Основная идея метода заключается в том, что по известным значениям функции в вершинах выпуклого многогранника, называемого симплексом, находится направление, в котором требуется сделать следующий шаг, чтобы получить наибольшее уменьшение (увеличение) критерия оптимальности. Примером симплекса на плоскости является треугольник, в трехмерном пространстве – четырехгранная пирамида, в nмерном пространстве – многогранник с n + 1 вершиной. Основным свойством симплекса является то, что против любой из вершин симплекса расположена только одна грань, на которой можно построить новый симплекс, отличающийся от прежнего расположением новой вершины, остальные вершины обоих симплексов – совпадают.

Начало задание u0, H,, n, Q вычисление Qвычисление Q/ui L = L = L + u1 = u0 – HQ/u Q0 = Q1; u0 = uQ1 = Q(u1) да Q0

1 Определяются значения целевой функции в трех точках S10, S20, S30, соответствующих вершинам симплекса. Из найденных значений выбирается наибольшее. В рассматриваемом примере – это S10 (рис. 3.12).

2 Строится новый симплекс, для этого вершина S10 исходного симплекса заменяется вершиной S11, расположенной симметрично вершине S10 относительно центра грани, расположенной против вершины S10. Построение нового симплекса S20 S30 S11 осуществляется определением центра А стороны S20 S30 треугольника S10 S20 S30, после чего проводится прямая S10A, на продолжении которой откладывается отрезок АS11 равный S10А.

3 Вычисляется значение целевой функции в вершине S11, которое сравнивается с известными значениями в вершинах S20 и S30. В результате определяется вершина S30 с наибольшем значением целевой функции, подлежащая исключению при построении следующего симплекса S11 S20 S31, и т.д.

S31 S S S S11 S А S10 SРис. 3.12 Поиск оптимума симплексным методом Исключение из рассмотренных вершин симплексов с наибольшим значением целевой функции приводит к сходимости процесса к минимальному значению.





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

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

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

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

2 Выбирается начальная точка u0, из которой производится поиск, будем считать для определенности, минимума любым методом локального поиска. Этот поиск закончится на дне "оврага", в результате чего будет найдена некоторая критическая точка u1 (рис. 3.13).

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

4 Из состояния u1 производится поиск минимума, в результате которого определяется еще одна критическая точка u2, расположенная на дне "оврага" (рис. 3.13).

uuu u Форма "дна оврага" uu u uРис. 3.13 Метод "оврагов" 5 Две найденные критические точки u1 и u2 соединяются прямой и выполняется "шаг по оврагу" в направлении убывания целевой функции. Это дает новое исходное состояние u1.

6 Из состояния u1 производится спуск на "дно оврага" и находится критическая точка u3. Далее определяется состояние u1 и т.д. (рис. 3.13).

Процесс поиска продолжается до тех пор, пока значение целевой функции во вновь найденной критической точке uk+1 Q (uk+1) не окажется больше, чем в предыдущей точке uk – Q (uk). Минимум в этом случае находится между точками uk–1 и uk+1. Далее процесс поиска можно повторить, но уже с меньшими "шагами по оврагу", пока не будет достигнута требуемая точность.

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

3.5 ПОИСК УСЛОВНОГО ЭКСТРЕМУМА При рассмотрении реальных задач оптимизации на переменные состояния накладываются условия типа равенств или неравенств, которые задают область изменения независимых переменных.

Задача нелинейного программирования в этом случае формулируется следующим образом: требуется найти оптимум (минимум) функции Q(u1,..., un) при u U и условия, что (u1,..., un ) 0, = 1, k.

Число условий типа неравенств может быть любым, т.е. меньше или больше числа независимых переменных. Если при решении такой задачи экстремум целевой функции будет находится внутри допустимой области изменения независимых переменных u, = 1, n, ограниченной неравенствами (u1,..., un ) > 0, то в некоторых случаях эту задачу можно решить рассмотренными выше методами поиска без учета ограничений. Вести поиск подобным образом при наличии условий типа равенств обычно невозможно. Если же экстремум целевой функции будет расположен на границе допустимой области, то для его отыскания применяют специальные методы.

3.5.1 Метод проектирования вектора-градиента При решении задач поиска максимума функции Q (u1,..., un) с ограничениями типа неравенств вида (u1,..., un ) > 0, = 1, k часто используется метод проектирования вектора-градиента.

Согласно этому методу движение к оптимуму происходит вдоль границы допустимой области. Стеk (u), при (u) > пень нарушения ограничений определяется функцией H (u) = (u), где =, т.е.

=0, при внутри допустимой области U функция H (u) тождественно равна нулю. При таком подходе к решению задачи положение точки при выполнении очередного шага должны оставаться за пределами области U, где градиент функции H (u) отличен от нуля. Если в результате выполнения очередного шага произойдет слишком большое нарушение ограничений, то коррекция этого нарушения должна осуществляться до того положения, пока функция H (u) еще отлична от нуля.

Движение вдоль границы ограничений будет продолжаться до тех пор, пока не будет выполняться условие (Q, ) < 0, т.е. пока искомый оптимум находится за пределами касательной плоскости, проведенной через рассматриваемую точку, расположенную на границе. Иллюстрация метода представлена на рис. 3.14.

Если условие (Q, ) < 0 оказывается нарушенным, то происходит "отрыв" от границы области U и дальнейший подъем будет происходить уже без влияния ограничений (рис. 3.14, точка u3).

Pages:     | 1 |   ...   | 3 | 4 || 6 | 7 |   ...   | 11 |










© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.