Сравнительный анализ методов оптимизации (стр. 3 из 6)
Шаг 1. Вычилить lymj - оптимальное решение задачи минимизации f(yj+lym * dj) при условии lym принадлежит E1. Положить y[j+1]= yj+lymj*dj. Если j < n, то заменить j на j+1 и вернуться к шагу 1. Если j=n, то положить x[k+1] = y[n+1]. Если ||x[k+1] - xk|| < eps , то остановиться; в противном случае перейти к шагу 2.
Шаг 2. Положить d = x[k+1] - xk и найти lym - оптимальное решение задачи минимизации f(x[k+1]+lym*d) при условии lym принадлежит E1. Положить y1= x[k+1]+lym*d, j=1, заменить k на k+1 и перейти к шагу 1. Для решения поставленной задачи выбрано приближение ε=0,02, α=0,15
Таблица 4 - Метод Хука-Дживса
| № шага | x1 | x2 | Z(x1,x2) |
| 1 | 1,147 | 1,257 | 5,0057324 |
| 2 | 1,127 | 1,237 | 4,7420444 |
| 3 | 1,107 | 1,217 | 4,4844364 |
| 4 | 1,087 | 1,197 | 4,2329084 |
| 5 | 1,067 | 1,177 | 3,9874604 |
| 6 | 1,047 | 1,157 | 3,7480924 |
| 7 | 1,027 | 1,137 | 3,5148044 |
| 8 | 1,007 | 1,117 | 3,2875964 |
| 9 | 0,987 | 1,097 | 3,0664684 |
| 10 | 0,967 | 1,077 | 2,8514204 |
| 11 | 0,947 | 1,057 | 2,6424524 |
| 12 | 0,927 | 1,037 | 2,4395644 |
| 13 | 0,907 | 1,017 | 2,2427564 |
| 14 | 0,887 | 0,997 | 2,0520284 |
| 15 | 0,867 | 0,977 | 1,8673804 |
| 16 | 0,847 | 0,957 | 1,6888124 |
| 17 | 0,827 | 0,937 | 1,5163244 |
| 18 | 0,807 | 0,917 | 1,3499164 |
| 19 | 0,787 | 0,897 | 1,1895884 |
| 20 | 0,767 | 0,877 | 1,0353404 |
| 21 | 0,747 | 0,857 | 0,887172399999997 |
| 22 | 0,727 | 0,837 | 0,745084399999997 |
| 23 | 0,707 | 0,817 | 0,609076399999996 |
| 24 | 0,687 | 0,796999999999999 | 0,479148399999997 |
| 25 | 0,667 | 0,776999999999999 | 0,355300399999997 |
| 26 | 0,647 | 0,756999999999999 | 0,237532399999997 |
| 27 | 0,627 | 0,736999999999999 | 0,125844399999997 |
| 28 | 0,607 | 0,716999999999999 | 0,0202363999999973 |
| 29 | 0,587 | 0,696999999999999 | -0,0792916000000026 |
| 30 | 0,567 | 0,676999999999999 | -0,172739600000002 |
| 31 | 0,546999999999999 | 0,656999999999999 | -0,260107600000002 |
| 32 | 0,526999999999999 | 0,636999999999999 | -0,341395600000002 |
| 33 | 0,506999999999999 | 0,616999999999999 | -0,416603600000002 |
| 34 | 0,486999999999999 | 0,596999999999999 | -0,485731600000002 |
| 35 | 0,466999999999999 | 0,576999999999999 | -0,548779600000002 |
| 36 | 0,446999999999999 | 0,556999999999999 | -0,605747600000002 |
| 37 | 0,426999999999999 | 0,536999999999999 | -0,656635600000002 |
| 38 | 0,406999999999999 | 0,516999999999999 | -0,701443600000001 |
| 38 | 0,426999999999999 | 0,496999999999999 | -0,699011600000001 |
Т.к в ε окрестности полученной на 38 шаге точке мы не получаем улучшения (уменьшения значения) функции, то примем x1=0,426999999999999 x2=0,496999999999999,
Z(x1,x2)= -0,699011600000001.
2.3 Метод правильного симплекса
Правильный симплекс в пространстве En называется множество из n+1 равноудаленных друг от друга точек (вершин симплекса). В пространстве Е2 правильным симплексом является совокупность вершин равностороннего треугольника, Е3 – правильного тетраэдра.
Поиск точки минимума функции f(x) с помощью правильных симплексов производят следующим образом. На каждой итерации сравниваются значения f(x) в вершинах симплекса. Затем проводят описанную выше процедуру отражения для этой вершины, в которой f(x) принимает наибольшее значение. Если в отраженной вершине получается меньшее значение функции, то переходят к новому симплексу. В противном случае выполняют еще одну попытку отражения для вершины со следующим по величине значением f(x). Если и она не приводит к уменьшению функции, то сокращают длину ребра симплекса и строят новый симплекс с новым ребром. В качестве базовой выбирают ту вершину х0 старого симплекса, которой функция принимает наименьшее значение. Поиск минимума f(x) заканчивают, когда либо ребро симплекса, либо разность между значениями функции в вершинах симплекса становятся достаточно малыми.
Начальный этап. Выбрать параметр точности eps, базовую точку x0, ребро a и построить начальный симплекс. Вычислить f(x0).
Основной этап.
Шаг 1. Вычислить значения f(x) в вершинах симплекса x1,..., xn.
Шаг 2. Упорядочить вершины симплекса x0,..., xn так, чтобы f(x0)<=f(x1)<=...<=f(x[n-1])<=f(xn).
Шаг 3. Проверим на окончание поиска
,где
Это одно из возможных условий останова. Его выполнении соответствует либо малому ребру a симплекса, либо попаданию точки минимума x* внутрь симплекса, либо тому и другому одновременно.
Если это условие выполнено, то вычисления прекратить, полагая x*= x0. В противном случае перейти к шагу 4.
Шаг 4. Найти xс и выполнить отражение вершины xn : y=2*xс- xn. Если f(y)<f(xn), то положить xn=y и перейти к шагу 2. Иначе - перейти к шагу 5.
Шаг 5. Перейти к новому правильному симплексу с вдвое меньшим ребром, считая базовой вершиной x0. Остальные n вершин симплекса найти по формуле xi=( xi+ x0)/2, i=1,...,n. Перейти к шагу 1.
Для решения поставленной задачи выбрано приближение ε=0,01, α=0,3
Таблица 5 - Метод симплекса
| № шага | Z(x0,y0) | Z(x1,y1) | Z(x2,y2) | α |
| 1 | 5,2755004 | 7,4172004 | 5,62549807735416 | 0,3 |
| 2 | 5,2755004 | 5,62549807735416 | 3,76366398915256 | 0,3 |
| 3 | 3,76366398915256 | 5,2755004 | 3,5838004 | 0,3 |
| 4 | 3,5838004 | 3,76366398915256 | 2,35182990095096 | 0,3 |
| 5 | 2,35182990095096 | 3,5838004 | 2,3421004 | 0,3 |
| 6 | 2,3421004 | 2,35182990095096 | 1,38999581274936 | 0,3 |
| 7 | 1,38999581274936 | 2,3421004 | 1,5504004 | 0,3 |
| 8 | 1,38999581274936 | 1,5504004 | 0,878161724547756 | 0,3 |
| 9 | 0,878161724547756 | 1,38999581274936 | 0,657100646520204 | 0,3 |
| 10 | 0,657100646520204 | 0,878161724547756 | 0,425132470117002 | 0,3 |
| 11 | 0,425132470117002 | 0,657100646520204 | 0,143414901312537 | 0,3 |
| 12 | 0,143414901312537 | 0,425132470117002 | 0,191312636707734 | 0,3 |
| 13 | 0,143414901312537 | 0,191312636707734 | -0,15106142287364 | 0,3 |
| 14 | -0,15106142287364 | 0,143414901312537 | -0,0288250700672363 | 0,3 |
| 15 | -0,15106142287364 | -0,0288250700672363 | -0,383957885030324 | 0,3 |
| 16 | -0,383957885030324 | -0,15106142287364 | -0,226328326038328 | 0,3 |
| 17 | -0,383957885030324 | -0,226328326038328 | -0,519881278971922 | 0,3 |
| 18 | -0,519881278971922 | -0,383957885030324 | -0,507376749762318 | 0,3 |
| 19 | -0,519881278971922 | -0,507376749762318 | -0,703956634480828 | 0,3 |
| 20 | -0,703956634480828 | -0,521318017069623 | -0,507376749762318 | 0,3 |
| 21 | -0,703956634480828 | -0,521318017069623 | -0,778554392565042 | 0,3 |
| 22 | -0,778554392565042 | -0,703956634480828 | -0,681327098177849 | 0,3 |
| 23 | -0,778554392565042 | -0,816581347038974 | -0,681327098177849 | 0,3 |
| 24 | -0,816581347038974 | -0,778554392565042 | -0,743674553224567 | 0,3 |
| 25 | -0,816581347038974 | -0,842357998475409 | -0,743674553224567 | 0,3 |
| 26 | -0,845848412956476 | -0,846177360374865 | -0,838238020383463 | 0,075 |
| 27 | -0,846177360374865 | -0,845848412956476 | -0,843154372435278 | 0,075 |
| 28 | -0,846616455690446 | -0,845848412956476 | -0,843154372435278 | 0,075 |
| 29 | -0,848017017695877 | -0,847087728053341 | -0,846597987664592 | 0,0375 |
| 30 | -0,848017017695877 | -0,847980516275042 | -0,847811621576176 | 0,01875 |
| 31 | -0,848017017695877 | -0,848085062414109 | -0,847811621576176 | 0,01875 |
Т.к дальнейшее уменьшение α невозможно(α/2< ε) и в ε окрестности полученной на 31 шаге точке мы не получаем улучшения (уменьшения значения) функции, то примем x=0,248249999999998 и y=0,408289729858682 Z(x,y)= -0,847811621576176.
2.4 Метод деформированного симплекса
Алгоритм минимизации по правильному симплексу можно модифицировать, добавив к процедуре отражения при построении нового симплекса процедуры сжатия и растяжения. А именно, положение новой вершины y вместо вершины xn , соответствующей наибольшему значению функции, находится сравнением и выбором наименьшего среди значений целевой функции в точках:
z1= xc - a( xc - xn), 0<a<1;
z2 = xc + a( xc - xn), 0<a<1;
z3 = xc + b( xc - xn), b приближенно равно 1;
z4 = xc + g( xc - xn), g<1.
Геометрическая иллюстрация этих процедур для двумерного пространства приведена на рисунке 7.
Новые симплексы полученные в результате процедуры сжатия (a,b); отражения (c); растяжения (d)
Так как величина a принадлежит интервалу (0;1), то выбор точек z1 и z2 соответствует сжатию симплекса; b приближенно равно 1, поэтому выбор точки z3 соответствует отражению, а g>1 и выбор точки z4 приводит к растяжению симплекса.
Отметим, что при деформациях утрачивается свойство правильности исходного симплекса.
Алгоритм метода поиска точки минимума функции по деформируемому симплексу
Начальный этап. Выбрать параметр точности eps, параметры a, b и g, базовую точку x0 , параметр a и построить начальный симплекс. Вычислить значение функции f(x0).
Основной этап. Шаг 1. Вычислить значения функции в вершинах симплекса x1,..., xn.
Шаг 2. Упорядочить вершины симплекса x0,..., xn так, чтобы f(x0)<=f(x1)<=...<=f(x[n-1])<=f(xn).
Шаг 3. Проверить условие (1/n)Sum[f(xi)-f(x0)]^2 < e^2, i=[1,n].
Это одно из возможных условий останова. При его выполнении "дисперсия" значений f(x) в вершинах симплекса становится меньше e2, что, как правило, соответствует либо малому ребру a симплекса, либо попаданию точки минимума x* внутрь симплекса, либо тому и другому одновременно.Если это условие выполнено, то вычисления прекратить, полагая x*= x0. В противном случае перейти к шагу 4.
Шаг 4. Найти xс и пробные точки zk , k=1,...,4 по формулам (2). Найти f(z*)=minf(zk). Если f(z*)<f(xn), то положить xn = z* и перейти к шагу 2. Иначе - перейти к шагу 5.