Ненаправленный случайный поиск

 

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

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

Направленный случайный поиск

 

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

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

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

1) неприемлемостью или отсутствием соответствующих аналитических и численных методов исследования модели;

2) возможностью создания модели функционирования системы (процесса), получением необходимого количества информации о моделируемой системе (процессе);

3) наличием большого числа случайных факторов в исследуемой системе (процессе);

4) наличием современной вычислительной техники и соответствующего программного обеспечения.

Вариационное исчисление

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

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

Аналогично тому, как в обычном анализе характеризуется функция одной переменной

                                                                                (52.6)

В вариационном исчислении дается определении понятие функционала как правила, по которому сопоставляются функция х(t) и некоторая скалярная величина

                                    (53.6)

Решением задачи отыскания экстремума функции х(t) являются одно или несколько значений независимой переменной t,  при которой функция х(t) имеет экстремальное значение.

Решением же задачи отыскания экстремума функционала I служат одна или несколько функций ,при подстановке которых в выражение (53.6) функционала его величина принимает экстремальное значение.

Функции  в этом случае называются экстремалями функционала. Причем, в зависимости от того, придает функция функционалу максимальное или минимальное значение, она называется максималью или минималью.

Понятие функционала обобщается также и на случай нескольких функций, т.е.

Ĩ = Ĩ [ x₁(t), x₂(t), …, x_m(t)]                      (54.6)

или с использованием векторной формы записи

Ĩ = Ĩ [ x(t)]                                          (55.6)

где

 x = x [ x₁(t), x₂(t), …, x_m(t)]                      (56.6)

Кроме того, сами функции , от которых зависит значение фукнционала I, в свою очередь могут является функциями нескольких независимых переменных t_i (i = 1,…, p).

 

      а)                                                б)

Рисунок 4.6. а) - Траектория процесса в фазовом пространстве; б) - Задание в фазовом пространстве областей начальных и конечных состояний

 

Функционалу I⁽³⁾ может быть придан наглядный геометрический смысл. Так, например, если представить совокупность функций

x_i(t)     i = 1,…m                                   (57.6)

как параметрическое задание некоторой кривой в m-мерном пространстве переменных x_i, то величину функционала I можно рассматривать как определенную оценку непрерывной кривой (57.6), соединяющей две точки этого пространства с координатами x⁽⁰⁾ и x^(k). Поскольку величины могут являться переменными состояния некоторого процесса, кривая (57.6) может интерпретироваться как траектория в фазовом пространстве переменных x_i, определяющая промежуточные состояния процесса при его переходе из начального состояния x⁽⁰⁾ в конечное x^(k).

В общем случае начальное состояние может описываться не точкой n-мерного пространства, а некоторой областью Х⁽⁰⁾, ограниченной заданной поверхностью F⁽⁰⁾ в указанном пространстве. Это относится и к конечному состоянию, которое может также определяться заданной областью Х^(k), ограниченной поверхностью F^(k).

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

Обычным выражением функционала служит интегральная зависимость, которую для одной функции x(t) можно, например, представить как

                                                               (58.6)

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

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

Несложно записать выражение для функционала типа (58.6), когда функция x зависит от нескольких переменных. Например, для функции x(t₁,t₂) можно привести следующий функционал:

                   (59.6)

Также обобщается запись функционала на случай нескольких функций. Например, для двух функций x₁(t), x₂(t) имеем:

                            (60.6)

Очевидно, что возможны и другие формы аналитического выражения функционала, например когда функционал I представляется некоторой известной функцией от соотношений типа (58.6 –60.6).

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

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

                                     (61.6)

с учетом которого выражение для функционала (60.6) можно представить как

                           (62.6)

где значение производной обозначено через xˊ.

Для функционала от нескольких функций вида (54.6)

                   (63.6)

при наличии ограничений в форме системы дифференциальных уравнений

                  (64.6)

выражение для функционала может быть также записано в виде (62.6)

           (65.6)

В простейшем случае, когда начальное и конечное состояния траектории процесса фиксированы, задание граничных условий сводится к заданию значений всех неизвестных функций при значениях независимой переменной t⁽⁰⁾ и t^(k), соответствующих началу и концу траектории, т.е. задается совокупность значений:

                         (66.6)

                         (67.6)

В более общем случае, когда задаются лишь области F⁽⁰⁾ и F^(k) возможных начальных и конечных значений искомых функций, граничные условия задаются в виде уравнений поверхности, ограничивающих эти области:

                                (68.6)

                                (69.6)

Если начальное и конечное значения независимой переменной t не заданы, то вид ограничивающих поверхностей F⁽⁰⁾ и F^(k) определяемых уравнениями (68.6) и (69.6), может зависеть и от значения независимой переменной, т.е.

                                (70.6)

                           (71.6)                                

В этом случае переменную целесообразно включить в число переменных фазового пространства, в результате чего траектория процесса будет изображаться уже в расширенном пространстве, имеющем размерность m+1

Рисунок 5.6. Задание начальных и конечных состояний на фазовой плоскости.

 

Для процесса, состояние которого определяется, например, значением только одной переменной состояния x(t), расширенное фазовое пространство представляется в виде фазовой плоскости переменных x и t.

Пусть области начальных и конечных значений переменной x характеризуются уравнениями

                                                                              (70.6)

 ,                                      (71.6)

 которые на фазовой плоскости x – t изображаются линиями. Тогда решение оптимальной задачи с функционалом (62.6) сводится к выбору такой траектории, соединяющей на фазовой плоскости линии, определяемые уравнениями (70.6) и (71.6), вдоль которой функционал (62.6) имеет экстремальное значение. При этом определяют точки начального и конечного состояний процесса.

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

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

Пример. Математическое описание нестационарного режима периодически действующего реактора идеального смешения представляется системой уравнений с граничными условиями

                                  (72.6)

                                       

                              

 

где    - концентрация исходного реагента;    - концентрация продукта реакции.

Предполагается, что между концентрациями реагентов А и Р в любой момент времени выполняется соотношение

 ,                                            (73.6)

означающее, что, кроме продукта Р, никаких других продуктов в ходе реакции не образуется. Требуется записать функционал, значение которого определяет выход продукта реакции Р для заданных времени пребывания реагентов f^(k) и программы изменения температуры в реакторе T(f) (0≤ f ≤ f^(k)).

Решение.

Из уравнения (73.6) можно получить функционал

,                        (74.6)

который необходимо анализировать с учетом ограничивающих условий (72.6)и (75.6). Эти условия позволяют найти зависимости

.                                     (75.6)

подставляя которые в выражение функционала (74.6), можно записать его в виде

             (76.6)

Если ввести обозначения

                  (77.6)

                              ,

то функционал (74.6) можно представить в форме:

,                                        (78.6)

отличающейся от формы записи функционала лишь тем, что в подынтегральном выражении (78.6) отсутствует в явном виде независимая переменная τ.

Таким образом, задача максимизации выхода продукта реакции Р в периодическом реакторе идеального смешения может быть сведена к задаче максимизации функционала (78.6). В результате ее решения можно найти оптимальную программу изменения температуры в реакторе T(f), максимизирующую выход продукта Р для заданного времени пребывания реагентов в аппарате.

 

Итак, решение любой оптимизационной задачи состоит из трех следующих этапов:

1) определение множества допустимых решений;

2) обоснование критерия оптимальности;

3) выбор наилучшего решения.

В практических задачах оптимизации существуют два вида их поста­новки. В первом случае точками допустимого пространства Х_g являются наборы вещественных чисел(х₁,х₂,...,х_n), а целевой функцией будет К(х)=К(х₁,х₂,...,х_n) - обычная вещественная функция от n веществен­ных аргументов (n - размерность пространства). Такая задача называ­ется задачей оптимизации функции.

Во втором случае в качестве допустимого множества выступает не­которое множество функций вещественных переменных y(x₁,x₂,...,x_n), а целевая функция есть некоторый функционал К, сопоставляющий каждой функции y(x₁,x₂,..,x_n) некоторое вещественное число К(y). Такую за­дачу называют задачей оптимизации функционалов или вариационной за­дачей.

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

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

Критерий оптимальности детерминированного процесса в общем виде может быть представлен как функция входных, выходных и управляющих                  (оптимизируюемых) параметров

R= R (x₁, x₂ …x_n; y_1, y_{2, …,} y_m; u₁, u_{2, …} u_k).

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

- аналитические методы;

- методы математического программирования.

Группа аналитических методов оптимизации объединяет аналитический поиск экстремума функции, метод множителей Лагранжа, вариационные методы и принцип максимума. Аналитический поиск экстремума функции, заданных без ограничений на независимые переменные является наиболее простым, но применяется к задачам, у которых оптимизируемая функция имеет аналитическое выражение, дифференцируемое во всем диапазоне исследования, а число переменных невелико.

Группа методов математического программирования включает: динамическое программирование, линейное программирование и нелинейное программирование.

Динамическое программирование – эффективный метод решения задач оптимизации многостадийных процессов. Метод предполагает разбивку анализируемого процесса на стадии (во времени или в пространстве). Рассмотрение задачи начинается с последней стадии процесса и оптимальный режим определяется постадийно.

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

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

 

Вопросы самоконтроля

 

1. Что представляет собою оптимизация?

2. Постановка задачи оптимизации.

3. Что представляют собою цели оптимизации?

4. Что представляют собою ресурсы оптимизации?

5. Что представляет собой критерий оптимизации?

6. Какие требования предъявляются к критерию оптимизации?

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

8. Условия постановки задачи оптимизации.

9. Методы поиска экстремума (оптимизации).

10. Классические методы. Метод прямого перебора.

11. Классические методы. Классический метод дифференциального исчисления.

12. Классические методы. Метод множителей Лагранжа.

13. Методы поиска экстремума унимодальных функций.

14. Методы поиска экстремума унимодальных функций. Метод половинного деления.

15. Методы поиска экстремума унимодальных функций. Метод чисел Фибоначчи.

16. Методы поиска экстремума унимодальных функций. Метод золотого сечения.

17. Регулярные (детерминированные) методы оптимизации.

18. Достоинства и недостатки градиентных методов.

19. Как организуется вычислительная процедура движения по градиенту?

20. Регулярные (детерминированные) методы оптимизации. Метод покоординатного спуска (подъема).

21. Регулярные (детерминированные) методы оптимизации. Метод градиента.

22. Регулярные (детерминированные) методы оптимизации. Метод наискорейшего спуска.

23. Методы случайного поиска.

24. Методы случайного поиска. Метод Монте-Карло.

25. Методы случайного поиска. Направленный поиск без самообучения.

26. Методы случайного поиска. Направленный случайный поиск с самообучением.

27. Что представляет собою предмет вариационного исчисления?

28. Вариационное исчисление. Понятие функционала.

29. Вариационное исчисление. Экстремаль.

30. Вариационное исчисление. Траектория процесса в заданном пространстве.

31. Вариационное исчисление. Основная задача.

32. Вариационное исчисление. Задание начальных и конечных состояний на фазовой плоскости.

33. Вариационное исчисление. Область применения по классам процессов.

34. Вариационные задачи с ограничениями.

 

Литература

 

1.  Батунер Л.М., Позин М.Е. Математические методы в химической технике./под ред. Позина М.Е., 6-е изд., исправленное - Л.: Химия, 1971. - 824с.  

2. Бахвалов Н.С. Численные методы. – М.: Наука, 1993. 

3. Брановицкая С.В., Медведев Р.Б., Фиалков Ю.Я. Вычислительная математика в химии и химической технологии. - К.: Вища шк., 1986. - 216с. 

4. Бояринов А.И., Кафаров В.В. Методы оптимизации в химической технологии. - М: Химия, 1969. - 564с.

5. Гартман Т.Н. основы компьютерного моделирования химико-технологических процессов: Учеб. пособие для вузов / ТН.Гартман, Д.В.Клушин. - М.: ИКЦ «Академкнига», 2006.- 416с.

6. Гайдадин А.Н., Ефремова С.А., Нистратов А.В. Методы оптимизации в технологической практике. - Волгоград: ВолгГТУ, 2008. - 16с.  

7. Закгейм А.Ю. Введение в моделирование химико-технологических процессов. - М.: Химии, 1982. - 288с.

8. Гайдадин А.Н., Ефремова С.А., Нистратов А.В. Методы оптимизации в технологической практике. - Волгоград:ВолгГТУ, 2008. - 16с.

9. Дворецкий Д.С., Дворецкий С.И., Муратова Е.И., Ермаков А.А. Компьютерное моделирование биотехнологических процессов и систем. Тамбов: ТГТУ, 2005. - 80с.

10. Кафаров В.В., Мешалкин В.П. Анализ и синтез химико-технологических систем. Учебник для вузов. -М.: Химия, 1991. -432с.     

11. Кузнецов А.В., Сакоич В.А., Холод Н.И. Высшая математика. Математическое программирование. - Минск: Вышэйшая школа, 1994. - 288с.  

12. Саулин Д.В. Математическое моделирование химико-технологических систем: Конспект лекций/ Перм.гос.техн.ун-т. Пермь, 2003, 91 с.

13. Математическая энциклопедия.  

http://dic.academic.ru/dic.nsf/enc_mathematics/4128

14. Математический энциклопедический словарь/гл.ред. Прохоров Ю.В. - М.:Советская энциклопедия, 1988. – 847с.

15. Пантелеев А.В., Летова Т.А. Методы оптимизации в примерах и задачах/:Учеб. пособие, - 2-е изд., исправл. -М.: Высш. шк., 2005. - 544с.   

16. Поляк Б.Т. Введение в оптимизацию. -М.: Наука, 1983. - 384с.  

17. Рейлиз В.И. Методы оптимизации/ Электронный ученик по дисциплине «Методы оптимизации».- Томск:нац. исслед. Томс. политех. у-т, -http://109.123.146.125/97/  

18. Федорова С.А. Методические указания по дисциплине «Математическое моделирование и применение ЭВМ в химической технологии для студентов заочной формы обучения» – СИЯЭиП – 2001г.