Симплексный метод оптимизации.

Симплексом называется правильный многогранник, имею­щий п+1 вершину, где п—число факторов, влияющих на про­цесс. Так, например, если факторов два, то симплексом явля­ется правильный треугольник.

 

Рис.. Оптимизация по симплексному методу

Сущность симплексного метода оптимизации иллюстрирует рис. 6.

Начальная серия опытов соответствует вершинам исход­ного симплекса (точки 1, 2 и 3). Условия этих первых опытов берутся из области значений факторов, соответствующих наи­более благоприятным из известных режимов оптимизируемого процесса.Сравнивая между собой результаты опытов в точках 1, 2 и 3, находят среди них самый «плохой», с точки зрения выбран­ного критерия оптимальности. Пусть, например, самым «не­удачным» оказался опыт в точке 1. Этот опыт исключают из рассмотрения, а вместо него в состав симплекса вводят опыт в точке 4, которая симметрична точке 1 относительно проти­воположной стороны треугольника, соединяющей точки 2 и 3.

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

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

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

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

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

Матрица опытов исходного симплекса в кодированных пе­ременных приведена в табл.11.

Величины, входящие в эту таблицу, рассчитываются по сле­дующим формулам:

                                    (*)

 

Здесь i—номер фактора в матрице планирования. Символом 0 обозначены координаты центра плана, т. е. основной уровень.

Таблица 11

Матрица исходного симплекса

 

 

Опыты, представленные в табл. 11, соответствуют верши­нам симплекса, сторона которого равна единице, а центр сов­падает с началом координат (в кодированных переменных).

Результаты расчетов, выполненных на основании табл. 11 и формул (*) .приведены в табл. 12.

Таблица 12 Условия начальной серии опытов

 

 

Аналогично можно рассчитать условия исходной серии опытов для большего количества факторов.

Очевидно, наибольшее количество опытов приходится ста­вить в начале эксперимента. Затем на каждом шаге оптимиза­ции выполняется только один опыт.

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

В дальнейшем все операции производятся только с физиче­скими¹. переменными.

.Условия каждого нового опыта рассчитываются по фор­муле:

 

   (**)

где п—число факторов в матрице планирования;

j — номер опыта;

i—номер фактора;

—значение i-го фактора в самом «неудачном» опыте предыдущего симплекса.

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

 

 

При этом значения всех ранее рассматриваемых факторов рас­считываются по формуле:

 

где 1= 1, 2,..., п, то есть являются средними арифметическими значениями соответствующих координат предыдущего симп­лекса.

Значение вновь вводимого фактора определяется по фор­муле:

.где x_0(n+1)—основной уровень этого фактора;

Δx_n+1—выбранный шаг варьирования для данного фак­тора;

R_n+1, k_n+1—величины, рассчитываемые по формулам (*).

Отметим, что добавление нового фактора в состав полного «факторного эксперимента сопровождается увеличением коли­чества опытов вдвое. В этом смысле симплексный метод имеет очевидное преимущество.

В практику научных исследований симплексный метод был введен Химсвортом в 1962 г.

 Пример 3.2. Пусть требуется с помощью симплексного ме­тода оптимизировать выход целевого продукта у (%), кото­рый получается при взаимодействии двух реагентов с кон­центрациями x₁ и  x₂ ()   при температуре x₃ (°С).

Выберем основные уровни и шаги варьирования факторов и сведем их в табл. 13.

Таблица 13

Значения уровней факторов и шагов варьирования

 

Пользуясь формулой (3.5) и табл. 12, рассчитаем условия проведения первых четырех опытов и полученные результаты сведем в табл. 14. Так, например, для третьего опыта

x₃₁=1+0,1*0==1;  x₃₂== 1,50 +0,2 (—0,578) ==1,38; x₃₃=60+5*0,204==61.

Таблица 14 Оптимизация симплексным методом

 

 

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

Заменим его опытом 5, условия проведения которого рас­считаем по формуле (**):

 

В новом симплексе, образованном опытами 1, 2, 4 и 5, са­мым «неудачным» является опыт 4. Его заменим опытом 6, ус­ловия которого найдем, пользуясь той же формулой (**).

Далее процедура оптимизации может быть продолжена аналогично.

Рассмотрим теперь вопрос о том, как включить в програм­му исследований еще один фактор, например скорость враще­ния мешалки. Пусть до этих пор она была постоянной и рав­ной 500 об/мин. Теперь будем считать эту величину фактором x₄ и примем для нее шаг варьирования Δx₄==100 об/мин.

Предыдущий симплекс для трех факторов (см. табл. 14) состоит из опытов 1, 2, 5 и 6. Чтобы из него получить новый симплекс для четырех факторов, введем опыт 7 (табл. 15).

 

Таблица 15 Добавление нового фактора в программу оптимизации

 

Номер опыта	x1	x2	x3	x4	Функция отклика
1	1,05	1,56	61	500	72,3
2	0,95	1,56	61	500	70,1
5	1,00	1,70	58	500	73,9
6	1,00	1,72	63	500	76,5
7	1,00	1,64	61	580	78,1

 

Условия проведения 7-го опыта найдем по формулам     (3.7) и (3.8):

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

 

                                                                                                     

                                                                                  

 

 

 

 

 

 

 

 

 

 

 

ПОИСК ПО ДЕФОРМИРУЕМОМУ МНОГОГРАННИКУ

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

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

 

Рнс. 12. Иллюстрация идеи симплексного метода

Симплексами называют регулярные многогранники. Например, для случая двух переменных это будет равносторонний треугольник, для трех переменных - тетраэдр и т. д. Точки испыта-. ний (рис. 12) совпадают с вершинами симплекса (точки 1, 2,3). Из вершины, в которой целевая функция максимальна (точка 1), проводится проектирующая прямая через цент тяжести   симплекса.   Затем строится новый симплекс, называемый отраженным, из точек 2, 3 и новой точки 4, расположенной на проектирующей прямой на надлежащем расстоянии от центра тяжести. Такая процедура в которой каждый раз вычеркивается вершина с максимально целевой функцией, повторяется. Треугольник (в случае двух переменных) как бы переворачивается через сторону с наименьшим значениями целевой функции. Существуют правила постепенного уменьшения размера симплекса и предотвращения циклического движения в окрестности минимума.

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

Обозначим координаты вершин многогранника на /с-м шаг через

Х_i,k    i = 1, . . ., п + 1;   k = 0, 1, ...

Выделим вершины, в которых целевая функция максимальная и минимальная, и обозначим их соответственно через Хплохое (Xмакс)и Xхорошее(X min).

(для упрощения формул индекс шага  к в дальнейшем будем опускать) Через

Xцентр обозначим центр тяжести всех вершин, исключая Хплохое:

 

X_n+2,j=

Работа метода состоит из сле­дующих операций: отражения, растяжения, сжатия и редукции (рис. 13).

 

 

 

Рис. 13. Операции метода деформируе­мого многогранника

 

 

Рис. 14. Траектория метода деформиру­емого многогранника

 

 

 

 

 

Отражение (рис. 13, а) — это проектирование точки       Хплохое через центр тяжести с получением новой точки:

Хn+з = X(n+2)+a*((Хn+2 — Xплохое)

где а > 0 — коэффициент отражения.

Растяжение. Если отражение прошло успешно, т. е.

/ (Х„7з) < / (х^),

то продолжаем дальше растягивать симплекс (рис. 13, б) в соответствии с соотношением

Хn+4 ⁼ Х.(n+2)+С (Хn+з — Хn+2)

где с представляет собой коэффициент растяжения. Если растяже­ние успешно, т. е. если

f(Хn+4) < f (Xхорошее), то Хплохое заменяется на Х(т+4). В противном случае Хплохое заменяется на  Xn+3

Сжатие. Если отражение не успешно в том смысле, что f(Хn+з) > f (Xi) для всех i≠плохая, то симплекс сжимается (рис. 13, в) в сторону от центра тяжести Хn+2

Хn+5 = Х(n+2) + b* (Xплохая — Хn+2),

где 0 < b <1 — коэффициент сжатия. Хплохая заменяется на Хn+5.

Редукция. Если сжатие не успешно в том смысле, что f (Хn+з) > f (Хплохое), то симплекс уменьшается. Уменьшение происходит и сто­рону вершины с наименьшей целевой функцией Xхорошее (из рис., г). Координаты вершин пересчитываются:

Хi=Ххорошее+d*(Хi-Ххорошее), i=1,...,n+1.

Здесь  d< 1 — коэффициент редукции.

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

 

 

где ε— произвольно малое число, от которого зависит точности и время оптимизации.

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

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

а = 1; b = 0,5; с = 2; d= 0,5.