Одномерные методы поиска экстремума

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

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

Наиболее простыми методами являются - дихотомии, «золотого сечения» и Фибоначчи. Идея этих методов заключается в том, что по двум значениям Х₁, Х₂, симметрично расположенных в области исследования Х_min< X₁< X₂< X_max, можно указать интервал меньше первоначального, в котором находится точка экстремума.

Метод дихотомии

Его идея заключается в следующем: на первом этапе экспериментирования относительно центра области исследования размещают две новые точки и проводят эксперимент, затем процедура повторяется на новом отрезке (рис 4.1). Координаты выбирают следующим образом:

где δ -точность измерения.

Координаты экспериментальных точек на последующих этапах исследования определяются по вышеуказанным формулам с учетом новых границ. Длина интервала неопределенности после проведения к-й пары опытов: , где l_N интервал неопределенности, в котором находится точка экстремума. Задаваясь допустимой относительной погрешностью ε локализации точки экстремума, можно найти число наблюдений N, необходимых для обеспечения желаемой точности:

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

Рис. 4.1. Схема поиска экстремума методом дихотомии

Рис. 4.2. Схема поиска экстремума методами Фибоначчи и «золотого сечения»

Метод Фибоначчи

Он более эффективен, чем дихотомии, так как позволяет сократить число опытов при одинаковой области исследования. Реализация метода связана с последовательностью целых чисел, открытых итальянским математиком Леонардом Фибоначчи (1202г.). В этом методе две новые точки Х₁, Х₂, берут на равном расстоянии от концов области исследования. Исходя из чисел Фибоначчи F_N = 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …, которые определяются рекуррентными соотношениями определяются значения

Планирование эксперимента производится следующим образом: вначале определяется необходимое число опытов N, т.к. оно используется при расчете Х₁, Х₂. Для определения N задаются относительной погрешностью ε и абсолютной погрешностью δ. Тогда N находят из соотношения

 

где l_N - интервал неопределенности,

В каждой очередной интервал неопределенности попадает один предыдущий эксперимент (рис 4.2). Для продолжения поиска новую точку следует располагать симметрично оставшейся.

Метод «золотого сечения»

Он занимает промежуточное положение между методами дихотомии и Фибоначчи. Координаты точек берут из следующих соотношений:

Где,

Деление отрезка подобным образом восходит к Евклиду и называется золотым сечением. Далее процедура планирования эксперимента аналогична методу Фибоначчи (см.рис 4.2):

Количество опытов может быть найдено из условия

Из сопоставления 3 методов следует, что самый эффективный - метод Фибоначчи, далее- метод «золотого сечения» (он более прост в расчетах) и метод дихотомии.

 

Многомерные методы поиска

К экспериментальным методам многомерного поиска относятся методы: Гаусса-Зайделя, метод крутого восхождения и симплекс-метод.

 

Метод Гаусса-Зайделя

В основе метода лежит идея координатного поиска, например, для двухфакторной модели вначале выбирают направление поиска по фактору Х₁. Значение Х₂ - фиксировано. Для поиска экстремума используются одномерные методы. Далее движение начинают вдоль новой координатной оси (рис. 4.3). Когда ни по одной из осей невозможно увеличение Y, поиск прекращается и полученная точка принимается за экстремальную.

Недостаток: при большом числе факторов (k) путь к вершине получается извилистым, что требует большого числа опытов.

Рис. 4.3. Схема поиска экстремума методами Гаусса-Зайделя и кругового восхождения

Метод крутого восхождения

(Бокс и Уилсон, 1953г)

Для поиска оптимальных условий достаточно построения линейной модели:

Необходимо найти точку х₁*, х₂*, …, х_k*, в которой целевая функция Y достигает экстремума. Один из кратчайших путей - это движение от данной точки к вершине, в направлении наиболее крутого склона, совпадающего с направлением градиента (см. рис. 4.3). Градиент - это вектор, указывающий наискорейшее изменение функции при переходе из одной точки пространства в другую:

где - частное произведение по j-му фактору, (i, j, k)-орты, совпадающие с направлением осей.

Для линейной модели частные производные равны b₁, b₂, …, b_k, тогда . Из формулы следует, что для осуществления движения по градиенту вес значения факторов по каждой из осей (i, j, k) необходимо изменять пропорционально величинам коэффициентов b₁, b₂, …, b_k. Рассмотрим технологию движения по grad для линейной однофакторной модели:

Т.к. , то он равен тангенсу угла наклона между линией регрессии и осью фактора. Тогда катет АВ=∆ х₁ b₁.

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

Серия " мысленных опытов" рассчитывается последовательным прибавлением к основным уровням факторов величин, пропорциональных произведению соответствующего коэффициента на интервал варьирования. Потом находит базовый фактор, для которого произведение b_j∆ x_j было максимальным пo абсолютной величине, и для него вычисляют базовый шаг: , где ∆ х - интервал варьирования.

После этого рассчитывают единичные шаги всех остальных факторов по формуле

и полученное значение округляют.

Все шаги рассчитывают в натуральном масштабе. Полученные таким образом шаги последовательно прибавляют к основным уровням факторов или вычитают из них (в зависимости от знака b_j, и от того, что ищут - максимум или минимум). Для качественных факторов фиксируют лучший уровень, для незначимых факторов стабилизируют на любом уровне в интервале (+1; -1). Обычно рассчитывают до 10 мысленных опытов. Реализацию мысленных опытов начинают с опыта, условия которого выходят из области эксперимента хотя бы по одному из факторов. Обычно проводят 3 - 4 опыта и по их результатам принимают решение о прекращении поиска или дальнейшем проведении эксперимента. Если одного линейного приближения недостаточно, то ставится новая серия мысленных опытов до достижения экстремумов.

Симплекс-метод

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

Симплекс-это простейший выпуклый многогранник, образованный k+1 вершиной общего положения в k-мерном пространстве. На плоскости симплекс образуется тремя точками, не лежащими на одной прямой (любой треугольник). В трехмерном пространстве симплекс образуется любыми 4 точками, не лежащими в одной плоскости, то есть это любая треугольная пирамида. Симплекс называется правильным или регулярным, если все расстояния между образующими его вершинами равны. Регулярными симплексами являются правильный треугольник, тетраэдр и т.д. Таким образом, точка - это нуль-мерный симплекс, а отрезок прямой - одномерный симплекс.

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

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

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

Рис.4.4. Схема поиска экстремума симплекс-методов

Правильный к-мерный симплекс с центром в начале координат может быть задан следующей матрицей:

где R_i, r_i – соответственно радиусы сфер, описанных и вписанных около i-мерного симплекса. При длине ребра симплекса, равного единицы, радиусы гиперсфер равны

где i=1, 2, 3, …, k.

Координаты экспериментальных точек, соответствующих вершинам симплекса, можно представить в виде таблицы:

№ опыта	X1	X2	X3	X4	X5	…	Xk	y
	-0, 5	-0, 289	-0, 204	-0, 158	-0, 129	...	r=	Y1
	0, 5	-0, 289	-0, 204	-0, 158	-0, 129	...	Y2
		0, 578	-0, 204	-0, 158	-0, 129	...	Y3
			0, 612	-0, 158	-0, 129	...	Y4
				0, 623	-0, 129	...	Y5
					0, 645	...	Y6
....	...	...	...	...	...	...	…
k+1						...		Yk+1

 

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

Для двух факторов имеем:

;

 

 

Тогда вершины симплекса запишем в таблице следующем образом:

N	X1	X2
	-r1	-r2
	R1	-r1
		R2

N	X1	X2
	-0, 5	-0, 289
	0, 5	-0, 289
		0, 578

 

Рис. 4.5. Двухмерный симплекс

 

 

Возможны и другие исходные положения начального симплекса, например, приведенные на рис. 4.6.

Рис. 4.6. Некоторые виды начального симплекса

Координаты вершин симплексов, представлены на рис. 4.6, записываются следующей таблицей:

N	X1	X2
	0, 5	0, 86

N	X1	X2
	p	q
	q	p

 

Пример

Задача: Используя симплексное планирование, оптимизировать процесс резания по критерию стойкости в зависимости от скорости резания ƒ и подачи при сверлении s:

Основные уровни и интервалы варьирования управляющих факторов приведены в таблице:

Факторы или параметры	Обозначение	Основной уровень	Интервал варьирования
Частота вращения ƒ (об/мин)	X1
Подача s (мм/об)	X2	0, 003	0, 0012

 

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

где х_ik+2 – координата новой вершины, являющейся зеркальным отображением отбрасываемой вершины; х_i* - координата отбрасываемой вершины; - среднее значение координат вершин симплекса, кроме отбрасываемой.

Для нашего примера координаты точки А` будут:

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

где х_i - кодированное значение фактора; - натуральные значения фактора; - интервал варьирования фактора; - основной уровень фактора.

Подставляя вместо х_i кодированные значения х₁=x₁₄ и х₂=х₂₄, получаем

откуда находим: =5050 об/мин, =0, 004 об/мин. Аналогично находятся значения и для других точек.

 

 

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

N	Симплекс	Вершина	Частота вращения X1	Подача X2	Стойкость (мин)
Код.	Об/мин	Код.	мм/об
	ABC ABC ABC A’BC A’B’C A’B’C’ A’B’’C’ A’’B’’C’ A’’B’’C’’ A’’’B’’C’’ A’’’B’’C’’’	A B C A’ B’ C’ B’’ A’’ C’’ A’’’ C’’’	0, 5 1, 5 2, 5 2, 5 2, 5		0, 86 0, 86 0, 86 1, 72 1, 72 2, 58 2, 58 1, 72	0, 003   0, 005	9, 0 13, 2 14, 6 18, 0 17, 0 21, 2 24, 8 21, 6 22, 1 22, 8 23, 7

 

Движение симплекса прекращается его вращением вокруг точки В``. Таким образом, наибольшая стойкость достигается в точке В``. Оптимальным режимом при этом является следующий - скорость резания ƒ =6050 об/мин и подача s=0, 005 об/мин.

Вопросы для самопроверки

1. Для чего и в каких случаях применяются методы поиска экстремума?

2. В чем особенность одномерных методов поиска?

3. Перечислите достоинства и недостатки метода дихотомии.

4. Какой из рассмотренных одномерных методов: дихотомии, Фибоначчи или «золотого сечения» наиболее эффективен и почему?

5. Что такое интервал неопределенности?

6. Перечислите основные шаги при поиске экстремума методом Фибоначчи.

7. Для чего необходимо рассчитывать количество экспериментальных точек при использовании одномерных методов?

8. В чес сходство и в чем различие методов дихотомии, Фибоначчи и «золотого сечения»?

9. Зачем требуется определять минимальную длину интервала неопределенности?

10. Чем определяется эффективность метода поиска экстремума?

11. От чего зависит длина интервала неопределенности?

12. Почему один из методов назван именем Фибоначчи?

13. Когда прекращается поиск в одномерных методах?

14. В чем особенность многомерных методов поиска экстремума?

15. Что такое единичные шаги фактора?

16. Что общего и в чем различие межу методами Гаусса-Зайделя, МКВ и симплекса?

17. Какой из методов: Гаусса-Зайделя, MKB или симплекса наиболее эффективен и почему?

18. Когда целесообразно применять метод Гаусса-Зайделя и почему?

19. Какие из многомерных методов наиболее доступны программированию? Обоснуйте свой ответ.

20. Когда заканчивается поиск в методах Гаусса-Зайделя, MKB и симплекса?

21. Какие параметры управляют точностью поиска в симплекс-методе?

22. Какие требования к объекту исследования должны выполняться при использовании многомерных методов поиска?

23. Что такое симплекс? В чем сущность симплекс-метода?

24. Чем руководствуются при выборе шага фактора при поиске экстремума?

25. Можно ли менять величину шага фактора при поиске экстремума методами Гаусса-Зайделя и МКВ?

26. В чем сущность метода крутого восхождения?

27. Для каких типов математических моделей применим МКВ?

28. Дайте определение градиента функции.

29. Как выбрать базовый фактор?

30. Как рассчитать единичные шаги факторов?

31. Как спланировать серию мысленных опытов при поиске максимума?

32. Как реализовать серию мысленных опытов?

33. Когда применение метода MKB эффективно?

34. Перечислите достоинства МКВ.

35. В чем заключается идея метода Гаусса-Зайделя?

1234567Следующая ⇒

Поделиться:

Популярное:

1. Алгоритм дихотомического поиска
2. В ПОИСКАХ «БАЛАНСА» НА БЛИЖНЕМ ВОСТОКЕ
3. В поисках своего подлинного Я
4. В поисках социальной солидарности: основные исследования Дюркгейма
5. В поисках Центра Души с тестом Розенцвейга
6. В поисках Эрика. Гипотеза вторая : против Церкви
7. Глава 1. В поисках тайной силы
8. Глава 4. В поисках новых подходов к праву
9. Дедуктивные методы поиска решений.
10. Дике и номос: в поисках начал справедливости
11. Достаточные условия существование экстремума
12. Живопись в СССР: в поисках прекрасного