бесплано рефераты

Разделы

рефераты   Главная
рефераты   Искусство и культура
рефераты   Кибернетика
рефераты   Метрология
рефераты   Микроэкономика
рефераты   Мировая экономика МЭО
рефераты   РЦБ ценные бумаги
рефераты   САПР
рефераты   ТГП
рефераты   Теория вероятностей
рефераты   ТММ
рефераты   Автомобиль и дорога
рефераты   Компьютерные сети
рефераты   Конституционное право
      зарубежныйх стран
рефераты   Конституционное право
      России
рефераты   Краткое содержание
      произведений
рефераты   Криминалистика и
      криминология
рефераты   Военное дело и
      гражданская оборона
рефераты   География и экономическая
      география
рефераты   Геология гидрология и
      геодезия
рефераты   Спорт и туризм
рефераты   Рефераты Физика
рефераты   Физкультура и спорт
рефераты   Философия
рефераты   Финансы
рефераты   Фотография
рефераты   Музыка
рефераты   Авиация и космонавтика
рефераты   Наука и техника
рефераты   Кулинария
рефераты   Культурология
рефераты   Краеведение и этнография
рефераты   Религия и мифология
рефераты   Медицина
рефераты   Сексология
рефераты   Информатика
      программирование
 
 
 

Сравнительный анализ методов оптимизации

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.

Шаг 5. Уменьшить симплекс, полагая xi=( xi+ x0)/2, i=1,...,n перейти к шагу 1.

На практике хорошо зарекомендовал себя следующий набор параметров a=1/2, b=1, g=2, поэтому он и был использован в программе.

Таблица 5 – Метод деформированного симплекса

№ шага Z(x0,y0) Z(x1,y1) Z(x2,y2)
1 5,25127562399313 5,35273629457997 4,72465845389651
2 4,47048359472409 5,52371793491734 4,32427361628427
3 4,26941489330181 4,56183485018145 2,53610076197985
4 2,53610076197985 4,26941489330181 2,54614140634749
5 2,60406550474582 2,62414679348111 0,650136727095332
6 0,873172338270091 4,78102989357106 -0,460995375774572
7 -0,460995375774572 -0,183165198484471 -0,647802169588968
8 -0,647802169588968 -0,460995375774572 -0,752046189909185
9 -0,752046189909185 -0,647802169588968 -0,743774186218157
10 -0,824978188986428 -0,820842187140914 -0,807869388437316
11 -0,848148148136976 -0,848148148106495 -0,848148148103467
12 -0,848148148146818 -0,848148148131578 -0,848148148135116
13 -0,848148148146818 -0,848148148135116 -0,848148148139001
14 -0,848148148136976 -0,848148148106495 -0,848148148103467
15 -0,848148148148147 -0,848148148148145 -0,848148148148146
16 -0,848148148148148 -0,848148148148147 -0,848148148148147

T.к.

Страницы: 1, 2, 3, 4


© 2010 САЙТ РЕФЕРАТОВ