Глобальный минимум функций, методы поиска

МЕТОДЫ ПОИСКА ГЛОБАЛЬНОГО МИНИМУМА ФУНКЦИЙ [c.185]

В работе [133] предложен детерминированный алгоритм определения глобального минимума функции многих переменных в допустимой области Q, который заключается в следующем. Вначале находится стационарная точка 0 функции S любым локальным методом поиска. Затем выбирается одна из m проходящих через 0о кривых, описываемых системой уравнений [c.186]

При наличии в исходном уравнении двух констант их оптимальные значения соответствуют глобальному минимуму, равному Б(Сд—Сд) , что изображено на рис. 13,6 в виде линий равной суммы квадратов отклонений как функции 01 и 02. По методу Гаусса — Зейделя поиск констант ведут следующим образом. Приблизительно оценивают одну из констант, например 0ь и описанным выше способом находят вторую константу 02. Затем фиксируют последнюю величину и отыскивают тем же способом другую константу 0ь дающую минимальную остаточную сумму квадратов. Эти операции повторяют до тех пор, пока не будут найдены оптимальные значения констант, дающие глобальный минимум 2(Сд—Сд)2, что изображено на рис. 13,6 в виде ступенчатой линии. При усложнении уравнений и наличии большого числа констант описанный метод требует большой вычислительной работы. Поэтому вместо него используют другие, более ускоренные методы поиска оптимальных значений констант (методы градиентов, нелинейных оценок и др.). [c.87]

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

Несмотря на то, что нелокальные методы поиска минимума получили широкое развитие за последнее время [114—116], определение глобального минимума функций, имеющих 15— 20 и более существенных переменных, задача вряд ли разрешимая. Действительно, с увеличением числа переменных машинное время, необходимое для. отыскания глобального минимума, растет экспоненциально вместе с тем увеличивается и время вычисления потенциальной функции. Поэтому представляется более перспективным отбор наиболее выгодных конформаций совсем малых участков (дипептидов и трипептидов) по заданной первичной структуре (подробнее мы это рассмотрим в последнем разделе). Тогда из нескольких вариантов структуры поиском локальных минимумов может быть выбран оптимальный вариант. [c.138]

Процедура поиска глобального минимума плохо организованной функции Ф(а) методом оврагов может быть следующей. [c.228]

Д.И. Батищев [19] рассматривает подобные методы поиска глобального экстремума функции от одной переменной с предварительным выявлением подынтервалов, содержащих по единственной точке локального минимума. Из этих минимумов выбирается наименьщий, который и считается абсолютным для исследуемой функции. Для определения подынтервалов используется процедура построения кусочно-линейной функции, которая имеет такое же число локальных минимумов, что и исходная затем для поиска точек локальных минимумов применяются, например, методы золотого сечения и ДСК-Паузлла [253]. [c.185]

В целом отыскание решения, соответствуюш его глобальному экстремуму, является весьма трудной задачей. В настоящее время все методы отыскания минимума функции S суммы квадратов разностей для многомерных функций без ограничений на переменные Ui, и2,. . ., Ul практически сводится к поиску локального экстремума, который при условии удовлетворительной сходимости опытных и расчетных данных принимается априори за глобальный экстремум. Имеющиеся попытки разработки методов, которые позволили бы находить для многомерных функций условия, определяющие получение единственного решения, соответствующего глобальному экстремуму, не дали положительных результатов. [c.118]

На самом деле деформации валентных углов в молекулах могут быть достаточно большими, и это обстоятельство в полной мере было понято лишь в последние годы [26—31]. Чтобы учесть деформации валентных углов, необходимо пойти дальше конформационных карт и использовать автоматические методы поиска экстремума функций большого числа переменных. Применительно к макромолекулам наиболее эффективным является метод оврагов, описанный в разделе 5 гл. 2. Метод оврагов позволяет прощупать всю потенциальную поверхность и выделить среди множества минимумов глобальный. [c.327]

Эффективность этих методов поиска зависит от формы целевой функции. Читатель, возможно, знает, что типичная форма, встречающаяся в химической кинетике, — так называемая долина. Особенно сложная ситуация имеет место, когда долина оказывается длинной и узкой, т. е. когда глобальный минимум лежит на слабо наклоненной линии, образуемой локальными минимумами (рис. 7.2). Простой градиентный метод (например, скорейшего спуска) имеет тенденцию к возникновению осцилляций вокруг линии локальных минимумов, имеющих характер складчатого стежка (рис. 7.3), что приводит к плохой сходимости. Если в этой ситуации преждевременно прекратить поиск, то можно не достичь глобального минимума и прийти к неверным выводам. В то время как визуальный контроль качества подгонки при движении вдоль линии локальных минимумов мо- [c.383]

В литературе описано большое число методов поиска глобального минимума функций многих переменных. Подавляющая часть этих методов относится к поискам случайного тина. Отметим один из них [135], так называемы гиперко-нический поиск, который, по мнению его создателей, в наибольшей степени приспособлен к решению задач, где многоэкстремальность сочетается с наличием оврагов высокой размерности. Алгоритм гиперконического поиска объединяет чисто случайный поиск при равномерном распределении проб во всей допустимой области значений подбираемых параметров (глобальный поиск) с направленным локальным поиском. Вначале используется глобальный поиск, сменяемый локальным всякий раз, когда достигается удачная точка 0 +, в которой значение функции отклонений меньше, чем в предыдущей точке 04 С другой стороны, локальный поиск сменяется глобальным, когда число неудачных проб превышает некоторое предельное значение. [c.185]

В нашей практике широко используется метод поиска [13], основанный на уже упоминавшихся свойствах линий уровня функции S, которые проявляются при двумерном табулировании в координатах 1пЛ , /. Вдоль овражного направления значение функции S изменяется очень медленно. Это приводит к тому, что вид сечения, перпендикулярного к прямым (VII,1), почти не зависит от того, через какую точку дна оврага оно проведено (см. рис. 20). Поэтому достаточно сделать одно сечение, чтобы получить представление о характере ноля. В сечении обычно оказывается несколько минимумов. Причем каждому из них отвечает свой овраг . Для поиска глобального минимума функций с такими свойствами применяются программы Разрез и Поиск . Поиск представляет собой программу минимизации одноэкстремальных функций. Эта программа позволяет уточнить значения функции в локальном минимуме, найденном Разрезом , а также может работать самостоятельно. Разрез использует Поиск в качестве подпрограммы. [c.186]

Здесь разбираются только локальные методы, позвляющие найти ближайший локальный минимум, в зоне притяжения которого-находится начальная точка поиска. Отсюда мы будем предполагать, что либо функция f в области В одноэкстремальна, либо что известнодостаточно хорошее приближение к глобальному минимуму. Рассмотрим здесь только методы, которые задачу (1,1), (1,2), (1,3) на условный экстремум сводят к задаче на безусловный экстремум. В основе такого подхода лежит следующее соображение. Для решения задач на безусловный экстремум разработан ряд эффективных, быстросходящихся методов [7]. Поэтому, если задача на условный экстремум будет сведена к задаче на безусловный экстремум, можно-воспользоваться упомянутыми методами для решения первоначальной задачи. Отметим, что сведение одной задачи к другой можег оказаться полезным как в прямых, так и в непрямых методах. [c.89]

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

Важно отметить, что два независимых валентных угла в этой молекуле не должны быть одинаковыми. Действительно, отталкивание атомов хлора сильнее отталкивания атомов водорода и следует ожидать, что угол ССС будет близок к тетраэдрическому в группе СХг и будет значительно превышать тетраэдрический в группе СНг (в этом случае увеличиваются расстояния X.. .X). Поиск глобального минимума нашей потенциальной функции методом оврагов привел к следующим значениям независимых параметров Z ССС (СНг) = 125°, Z ( X2) = H3°, ф1=44°, фг=17Г, ZH H=106°, Z 1 1 = = 109°, аг=113°. На рис. 16а, 166 приведены построенные нами потенциальные карты этого полимера для валентных углов [c.43]

Простейшим недетерминированным методом является построение сетки в пространстве переменных и локальный спуск из каждой точки сетки. Если сетка достаточно густа, то таким способом могут быть найдены все локальные минимумы, после чего остается лишь сравнить их по величине. Разумеется, это слишком дорогой метод, поскольку при его реализации функция должна быть вычислена слишком много раз. Более эффективен метод случайных испытаний. Вместо построения сетки случайным образом выбрасывают точки в пространстве переменных и из них производят локальные спуски. Если о структуре функции заранее что-нибудь известно, то задается распределение выбрасываемых точек. Наконец, распределение может быть найдено в процессе накопления опыта по проведенным испытаниям около точек, имеющих низкие значения энергии, случайные точки выбрасываются чаще, в других областях — реже. Такая процедура, сочетающая в себе черты недетерминированных и детерминированных методов, применялась в работе [194] при поиске глобального минимума бТкрытой пептидной системы, состоящей из 10 аланиновых остатков (поиск велся в пространстве 20 переменных — углов вращения). При достаточно большом числе испытаний точки, соответствующие низким значениям энергии, могут быть найдены, но никогда нет уверенности в том, что точка с минимальной энергией соответствует истинному минимуму. [c.138]

Методы направленного поиска способны привести в точку одного из экстремумов, но не позволяют установить, единственный ли это экстремум, а если известно, что не единственный, то в какой экстремум мы попали глобальный (экстремальный для всей области) или локальный (другие точки могут оказаться выше в случае максимума или ниже для минимума). Если при решении задачи оптимизации появится подозрение, что мы встретились с неунимодальностью, следует грубо исследовать функцию сканированием и выделить область глобального экстремума. [c.264]

Справочник химика 21

Химия и химическая технология