Файл: Дашевский, В. Г. Конформации органических молекул.pdf

Описанный метод поиска минимума на прямой, с квадратич­ ной интерполяцией, является весьма эффективным, но не опти­ мальным. Оптимальные стратегии сложнее (они основаны на последовательности чисел Фибоначчи); их описание можно найти в [173]. Но дихотомия (удвоение приращения или деление его пополам) почти не уступает по своей эффективности оптимальной стратегии, и потому ее можно рекомендовать как самую простую и вместе с тем достаточно эффективную стратегию. Заметим, что вместо малого т можно было выбрать и достаточно большое зна­ чение, такое, что при дг<*+|>= х (*> -j- х х г функция возрастает. Затем т половинится до тех пор, пока функция не станет убывать. Очевидно, эти два способа действий равносильны, если прене­ бречь тем обстоятельством, что при большом т точка д:<*+1) иногда может выйти из области притяжения искомого локального ми­ нимума.

Итак, квадратичные методы более эффективны для нахожде­ ния точного положения минимума, чем линейные. Но в рассмот­ ренном выше методе Ньютона — Рафсона каждая итерация стоит слишком дорого, поскольку приходится вычислять матри­ цу вторых производных btj [выражение (2.110)]. Поэтому немало усилий математиков было направлено на то, чтобы получить эквиваленты этого метода, но без расчета вторых производных. В работах [182—190] предложено несколько эффективных алго­ ритмов минимизации; сравнение некоторых из них на различных функциях проведено в [186, 191,. 192].

Из упомянутых алгоритмов следует остановиться на методе параллельных касательных [182], применявшемся в конформационном анализе [193]. Идея его состоит в следующем. Возьмем точку (рис. 2.18а) и найдем в этой точке касательную к ли­ нии уровня (пока мы ограничиваемся двумерной функцией).

Рис. 2.18. Двумерная иллюстрация метода параллельных касательных.

Затем выберем произвольную точку лгО) и найдем минимум в на­ правлении, параллельном этой касательной. Применяя, напри­ мер, параболическую интерполяцию, получим точку лг(2>. Соеди­ ним теперь точки лг(°) и х№ и на этой прямой вновь найдем ми­ нимум. Можно строго доказать, что для квадратичных функций точка х ), полученная минимизацией функции на прямой

133

статочно сложны, и мы не будем на них останавливаться. Метод Давидона характеризуется квадратичной сходимостью и, повидимому, является наиболее универсальным из всех современ­ ных локальных методов; универсальность его заключается в том, что он хорошо работает на самых разнообразных классах функций. В частности, машинные эксперименты Леона [192, р. 23J показа­ ли, что метод Давидона быстро сходится на некоторых «очень пло­ хих» функциях, где градиентные методы и даже метод параллель­ ных касательных оказываются мало эффективными. Что же ка­ сается конформационных задач, то потенциальные функции еще «не так плохи», чтобы для их минимизации следовало рекомен­ довать метод Давидона.

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

Преимущества и недостатки каждого из четырех методов — скорейшего спуска (СС), сопряженных градиентов (СГ), Ньюто­

*min — (0; 0; 0; 0)

Р (*min) = 0

135

Функция (1) была предложена автору В. Г. Туманяном; функ­ ции (2) и (3) ранее неоднократно использовались в качестве те­ стовых. В (2.123) — (2.125) указаны не только аналитические вы­ ражения, но и начальные точки х(0>с соответствующими значе­ ниями функции, а также положения минимума, xmin, и значения функции в минимуме.

В табл. 2.8 приведены результаты испытаний различных мето­ дов минимизации на этих функциях*. Во всех случаях при поиске минимумов на прямых для начального шага т (который в дальней­ шем удваивался) было принято значение 0,00005; приращения аргументов при вычислении производных принимались равными 0,0001. Одномерный поиск проводился с параболической интер­

Цифры в таблице означают число обращений к процедурефункции. Понятно, что сравнение по числу обращений к функ­ ции более объективно, чем сравнение по числу итераций (напом­ ним, что каждая итерация в методе Ньютона — Рафсона (HP) значительно «дороже», чем в других методах). Следует еще за-

* У автора имеется комплекс программ минимизации, написанный на языке АЛГОЛ-60.

136

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

Данные табл. 2.8 показывают, что наименее эффективным вблизи минимума является метод скорейшего спуска (СС); осталь­ ные методы «в среднем» равноценны, хотя некоторое предпочте­ ние все же следует отдать методу Ньютона — Рафсона. Правда, на функции (3) этот метод испытывает некоторые трудности в самом начале поиска, и в конце концов ему только лишь удается «догнать» метод скорейшего спуска. Но подобные ситуации редки в конформационных задачах.

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

можно написать

где п = 0, 1, 2, а потенциалы невалентных взаимодействий раз­ ложим в ряд Тэйлора, ограничиваясь квадратичными членами. Найдя точный минимум квадратичной формы (для чего требуется решить систему квадратных уравнений), примем его за нулевое приближение и вновь проведем разложение в ряд. Такая проце­ дура применялась в работе [ 153J; восьми итераций оказывалось достаточно, чтобы, исходя из априорного знания положения ми­ нимума, уточнить его координаты. Надо полагать, что этот спо­ соб действий не уступает по скорости методу Ньютона — Рафсо­ на, однако он не является универсальным: если нулевое прибли­ жение выбрано далеко от минимума, сходимость процесса должна быть медленной. Кроме того, предположение малости разности Ф — Фо. где ф0 — угол вращения, соответствующий скрещенной

велики даже в равновесных конформациях и минимум упрощен­ ной потенциальной функции может не соответствовать истинному минимуму.

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

137

использующие опыт предыдущих испытаний, ко второй — стра­ тегии, не использующие этого опыта.

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

найдено в процессе накопления опыта по проведенным испыта­ ниям: около точек, имеющих низкие значения энергии, случай­ ные точки выбрасываются чаще, в других областях — реже. Такая процедура, сочетающая в себе черты недетерминирован­ ных и детерминированных методов, применялась в работе [194] . при поиске глобального минимума открытой пептидной системы, состоящей из 10 аланиновых остатков (поиск велся в простран­ стве 20 переменных — углов вращения). При достаточно боль­ шом числе испытаний точки, соответствующие низким значениям энергии, могут быть найдены, но никогда нет уверенности в том, что точка с минимальной энергией соответствует истинному ми­

нимуму.

Из детерминированных методов наиболее сильным, вероятно, является метод оврагов И. М. Гельфанда и М. Л. Цетлина [195, 196]. Для того, чтобы он работал эффективно, функция должна быть «хорошо организована», что означает наличие двух групп переменных: переменных существенных и несущественных. Су­ щественные переменные слабо влияют на функцию, т. е. при их изменении функция мало меняется; изменения несущественных переменных приводят к резким изменениям значений функции. В конформационных задачах существенными переменными обыч­ но являются углы вращения, несущественными — валентные углы и связи. Но в некоторых точках потенциальной поверх­ ности это может быть и неверно; кроме того, некоторые из углов вращения в ряде точек могут быть существенными, а другие углы вращения — несущественными. Опыты показывают, что потен­ циальные функции конформационных задач являются в этом смысле «хорошо организованными», и эффективность метода овра­ гов при нелокальном поиске весьма высока.

Метод оврагов заключается в построении последовательности точек поиска А 0, Аъ ..., Ап. Предположим, что точки А 0, ...,А п найдены. Для нахождения точки Лп+1 производится «шаг по оврагу» — через точки Ап_! и Ап проводится прямая, на которой находится точка хп+1 (рис. 2.19), отстоящая от Ап на величину h.

138