Применение алгоритма сплайновой экстраполяции при решении задач полубесконечной оптимизации

Размещено на http://www.allbest.ru/

Применение алгоритма сплайновой экстраполяции при решении задач полубесконечной оптимизации

Введение

Задачи полубесконечной оптимизации часто возникают при исследовании и оптимизации различных реальных систем, процессов, объектов.

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

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

,

(1)

Величина в (1) является максимально достижимой точностью минимизируемого поля при управлении .

В работе [3] был предложен и обоснован алгоритм численного решения задач полубесконечной оптимизации с использованием экстраполирования минимизируемого поля на каждой итерации, ориентированный на уменьшение числа обращений к вычислению минимизируемого поля. В качестве экстраполянта минимизируемого поля на каждой итерации предложено использовать интерполяционные D^m-сплайны и псевдополиномиальные, например, псевдокубические сплайны на хаотических сетках [4-8 и др.].

Применение численных методов моделирования предполагает получение только значений оптимизируемого (минимизируемого) поля при конкретных заданных значениях управляющих параметров и, как правило, полное отсутствие какой-либо другой информации, например, о поведении этого поля в зависимости от управляющих параметров, значениях и направлении градиента. Между тем для построения экстраполянта и проведения успешной оптимизации при минимальном числе обращений к вычислению минимизируемого поля подобная информация крайне важна. В процессе проводимых итераций она должна появляться и накапливаться. На накопление информации о поведении минимизируемого поля и ориентирован алгоритм, предложенный в [3]. По мере появления такой информации и её конкретизации может меняться ход вычислений и поведение алгоритма. Поэтому весь процесс вычислений можно условно разбить на отдельные стадии. При проведении конкретных расчётов в зависимости от особенностей поля и выбранного начального приближения отдельные стадии могут как удлиняться, так и сокращаться и исчезать.

Разработанный алгоритм был реализован в виде программы для оптимизации полей. Её интерфейс и особенности использования изложены в [9].

1.Стадии итерационного процесса

Первая начальная стадия оптимизационного процесса соответствует начальному этапу алгоритма и заключается в накоплении начальной информации о поведении оптимизируемого поля. Это может быть, например, расчёт оптимизируемого поля в точке -мерного пространства управляющих параметров, не лежащих в одной гиперплоскости этого пространства. Нахождение значений поля на симплексе в пространстве управления уже позволяет построить линейную экстраполяцию оптимизируемого поля от параметров управления. Выбор положения точек и их числа на этой стадии (этапе) может определяться из каких-либо соображений и имеющихся сведений. Это может быть, например, представление о расположении области, содержащей искомый оптимум, или требование глобальной проверки всей области определения пространства управляющих параметров. Представления о примерном расположении оптимума и точности этой информации возникают, в частности, при многократном решении оптимизационной задачи со сравнительно небольшими вариациями каких-либо других, не оптимизируемых параметров. Дополнение начального этапа методами глобальной оптимизации [10-12] в случае многоэкстремальных задач должно позволить при большей детализации оптимизируемого поля и, соответственно, большем числе просчитываемых точек локализовать на начальной стадии положение глобального экстремума и при проведении итераций на последующих стадиях осуществлять поиск именно глобального экстремума.

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

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

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

Если базовые точки, использованные на первой начальной стадии, оказываются далеки от оптимального решения, а полученные в них поля по структуре локальных экстремумов не соответствуют структуре локальных экстремумов в окрестности решения оптимизационной задачи, то вычисления на второй стадии могут сопровождаться значительными по величине шагами. Это может приводить к «метанию» алгоритма по всей области определения параметров управления. В процессе такого «метания» происходит уточнение экстраполянта, процесс достаточно быстро стабилизируется, и в ходе последующих итераций начинает происходить выявление особых точек минимизируемого поля. Такое поведение может наблюдаться лишь на первых итерациях этой стадии, когда отсутствует какая-либо локализация области, содержащей решение, а построенное приближение недостаточно точно. Для уменьшения подобного «метания» алгоритма возможно введение разумного ограничения на величину шага. С целью повышения точности и уменьшения числа итераций на данной стадии для построения экстраполянта следует использовать все ранее найденные опорные точки.

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

Общая схема уточняющих приближений этой стадии, достаточно эффективно работающая на практике, заключается в следующем.

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

, (2)

, .

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

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

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

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

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

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

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

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

2.Пример использования алгоритма для решения задачи оптимального нагрева

В качестве первого примера рассмотрена задача оптимального нагрева в проходной двухзонной индукционной печи. Температурное поле рассчитывалось по численной модели, разработанной в [13].

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

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

<F:\BIG_WD_old\!

На рис. 1 показана структура поля отклонений температуры от заданной в координатах «ток первого индуктора» - «ток второго индуктора». Это поле имеет достаточно протяжённые и искривлённые истинные овраги, которые сходятся в точке оптимума (5141.38А; 1678.47А).

По предложенному алгоритму были многократно проведены расчёты, отличающиеся начальными приближениями. Ход расчётов для трёх достаточно характерных случаев начальных приближений представлен на рис. 2-4.

Расчёты показали, что вторая стадия проведения итераций, в ходе которой происходит локализация точки оптимума, заканчивается к седьмому шагу (рис. 2) и начинается стадия уточнения положения искомой точки оптимума. В ходе этой третьей стадии наблюдается геометрическая сходимость (рис. 3, 4).

Из проведённых расчетов видно, что итерации сходятся, и максимум за десять обращений к модели нагрева гарантированно достигается точность определения оптимальных токов - не менее 1А, при этом точность нагрева отличается от максимально достижимой (7.67 °C) менее чем на 0.2 °C.

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

В качестве примера использования алгоритма [3] в сложном многомерном случае рассмотрим задачу из [14]. Ищется минимум функции пяти переменных . Здесь евклидова норма, a¹=(0; 0; 0; 0; 0), a²=(2; 1; 1; 1; 3), a³=(1; 2; 1; 1; 2), a⁴=(1; 4; 1; 2; 2), a⁵=(3; 2; 1; 0; 1), a⁶=(0; 2; 1; 0; 1), a⁷=(1; 1; 1; 1; 1), a⁸=(1; 0; 1; 2; 1), a⁹=(0; 0; 2; 1; 0), a¹⁰=(1; 1; 2; 0; 0), b=(1; 5; 10; 2; 4; 3; 1.7; 2.5; 6; 3.5).

Задача является вырожденной, множество активных индексов (2; 4; 5; 9).

В работе [14] эта задача решалась одним из вариантов метода растяжения пространства (при этом на каждом шаге требуется вычислять производные функций). Результаты проведения итераций частично приведены табл. 1.

Т а б л и ц а 1

К данной задаче применён предлагаемый подход.

В качестве начального приближения взято: x¹=(0; 0; 0; 0; 1), x²=(0.5; 0; 0; 0; 1), x³=(0; 0.5; 0; 0; 1), x⁴=(0; 0; 0.5; 0; 1), x⁵=(0; 0; 0; 0.5; 1), x¹=(0; 0; 0; 0; 1.5).

Ход итераций приведён в табл. 2.

Видно, что предлагаемый алгоритм демонстрирует более быструю сходимость по сравнению с результатами [14] (и при этом не требует вычисления производных исследуемой функции).

Приводимые рисунки (рис. 5-8) демонстрируют примерно геометрическую (линейную) сходимость итерационного процесса. Выбор других начальных приближений может приводить к некоторому удлинению стадий итерационного процесса. При этом сохраняется примерно геометрическая сходимость на третьей стадии итерационного процесса.

алгоритм полубесконечный оптимизация сплайн

Таблица 2

<F:\BIG_WD_old\!\SPLINE\Старое\SPL__NEW_3\Work\S 0\ MOD_6.xls>

Видно, что поведение критерия в общих чертах может служить для описания сходимости итерационного процесса.

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

Библиографический список

1. Рапопорт Э.Я. Оптимизация процессов индукционного нагрева металла. - М.: Металлургия, 1993. - 279 с.

2. Рапопорт Э.Я. Альтернансный метод в прикладных задачах оптимизации. - М.: Наука, 2000. - 336 с.

3. Ефимов А.П. Алгоритм сплайновой экстраполяции при решении задач полубесконечной оптимизации. // Вестник СамГТУ. Сер. Технические науки. Вып. 2 (24). - Самара, 2009. - С. 25-32.

4. Duchon J. Splines minimizing rotation-invariant semi-norms in Sobolev spaces // Constructive theory of functions of several variables. Berlin, 1977. - P. 85-100.

5. Meinguet J. Multivariate Interpolation at Arbitrary Points Made Simple // ZAMP. - 1979. - V. 30. - N 2. - P. 292-304.

6. Василенко В.А. Сплайн-функции: теория, алгоритмы, программы. - Новосибирск: Наука, 1983. -215 c.

7. Ашкеназы В.О. Сплайн-поверхности: основы теории и вычислительные алгоритмы. - Тверь: Тверской гос. ун-т, 2003. - 82 с.

8. Arcangйli R., Lуpez de Silanes M.C., Torrens J.J. Multidimensional Minimizing Splines: Theory and Applications. - Boston: Kluwer Academic Publishers, 2004. - 280 p.

9. Ефимов А.П. Численные методы многопараметрической оптимизации процессов взаимодействия тепловых и электромагнитных полей // Проблемы управления и моделирования в сложных системах: Тр. VIII междунар. конф. - Самара: Самар. НЦ РАН, 2006. - С. 195-199.

10. Жиглявский А.А., Жилинскас А.Г. Методы поиска глобального экстремума. - М.: Наука, 1991. - 248 с.

11. Сухарев А.Г. Глобальный экстремум и методы его отыскания. - М.: Изд-во МГУ, 1981. - С. 4-37.

12. Андрамонов М.Ю. Методы глобальной минимизации для некоторых классов обобщенно выпуклых функций. - Казань: Изд-во Казанского математического общества, 2001. - 190 с.

13. Boergerding R. Optimierung des Betriebs induktiver Schmiedeblockerwaermer: Dissertation von Dipl.-Ing. Institut fuer Elektrowaerme der Universiaet Hannover - Hannover, 1997. - 122 S.

14. Шор Н.З. Методы минимизации недифференцируемых функций и их приложения. - Киев: Наук. думка, 1979. - 200 с.

Размещено на Allbest.ru