![]() |
||
Главная Рефераты по сексологии Рефераты по информатике программированию Рефераты по биологии Рефераты по экономике Рефераты по москвоведению Рефераты по экологии Краткое содержание произведений Рефераты по физкультуре и спорту Топики по английскому языку Рефераты по математике Рефераты по музыке Остальные рефераты Рефераты по авиации и космонавтике Рефераты по административному праву Рефераты по безопасности жизнедеятельности Рефераты по арбитражному процессу Рефераты по архитектуре Рефераты по астрономии Рефераты по банковскому делу Рефераты по биржевому делу Рефераты по ботанике и сельскому хозяйству Рефераты по бухгалтерскому учету и аудиту Рефераты по валютным отношениям Рефераты по ветеринарии Рефераты для военной кафедры Рефераты по географии Рефераты по геодезии Рефераты по геологии Рефераты по геополитике Рефераты по государству и праву Рефераты по гражданскому праву и процессу Рефераты по делопроизводству Рефераты по кредитованию Рефераты по естествознанию Рефераты по истории техники Рефераты по журналистике Рефераты по зоологии Рефераты по инвестициям Рефераты по информатике Исторические личности Рефераты по кибернетике Рефераты по коммуникации и связи |
Реферат: Нелинейное программированиеРеферат: Нелинейное программированиеЮжно-Уральский Государственный Университет Кафедра АиУ реферат на тему: Нелинейное программирование Выполнил: Пушников А. А., ПС-263. Проверил: Разнополов О.А. Челябинск – 2003. Оглавление 1. Постановка задачи нелинейного программирования 2. Критерии оптимальности в задачах с ограничениями 2.1. Задачи с ограничением в виде равенств 2.2. Множители Лагранжа 3. Условия Куна-Таккера 3.1. Условия Куна-Таккера и задача Куна-Таккера 3.2. Интерпретация условий Куна-Таккера 3.3. Теоремы Куна-Таккера 4. Функции нескольких переменных 4.1. Методы прямого поиска 4.1.1. Метод поиска по симплексу (S2 - метод) 4.1.2. Метод поиска Хука-Дживса 1. Постановка задачи нелинейного программирования. В
задаче нелинейного программирования (НЛП) требуется найти значение многомерной
переменной х=(
а
переменные
Иногда
в формулировке задачи ограничения (1) имеют противоположные знаки неравенств.
Учитывая, однако, что если 2. Критерии оптимальности в задачах с ограничениями. Ряд
инженерных задач связан с оптимизацией при наличии некоторого количества ограничений
на управляемые переменные. Такие ограничения существенно уменьшают размеры области,
в которой проводится поиск оптимума. На первый взгляд может показаться, что
уменьшение размеров допустимой области должно упростить процедуру поиска
оптимума. Между тем, напротив, процесс оптимизации становится более сложным,
поскольку установленные выше критерии оптимальности нельзя использовать при
наличии ограничений. При этом может нарушаться даже основное условие, в
соответствии с которым оптимум должен достигаться в стационарной точке,
характеризующейся нулевым градиентом. Например, безусловный минимум функции 2.1. Задачи с ограничениями в виде равенствРассмотрим общую задачу оптимизации, содержащую несколько ограничений в виде равенств: Минимизировать
при
ограничениях Эта задача в принципе может быть решена как задача безусловной оптимизации, полученная путем исключения из целевой функции k независимых переменных с помощью заданных равенств. Наличие ограничений в виде равенств фактически позволяет уменьшить размерность исходной задачи с n до n-k.. В качестве иллюстрации рассмотрим следующий пример. Пример 1 Минимизировать
при
ограничении Исключив
переменную оптимизационную задачу с двумя переменными без ограничений min Метод
исключения переменных применим лишь в тех
случаях, когда уравнения, представляющие ограничения, можно разрешить
относительно некоторого конкретного набора независимых переменных. При наличии
большого числа ограничений в виде равенств, процесс исключения переменных
становится весьма трудоемкой процедурой. Кроме того, возможны ситуации, когда
уравнение не удается разрешить относительно переменной. В частности, если в
примере 1 ограничение то получить аналитическое выражение какой-либо из переменных через другие не представляется возможным. Таким образом, при решении задач, содержащих сложные ограничения в виде равенств, целесообразно использовать метод множителей Лагранжа, описание которого дается в следующем разделе. 2.2. Множители ЛагранжаС помощью метода множителей Лагранжа по существу устанавливаются необходимые условия, позволяющие идентифицировать точки оптимума в задачах оптимизации с ограничениями в виде равенств. При этом задача с ограничениями преобразуется в эквивалентную задачу безусловной оптимизации, в которой фигурируют некоторые неизвестные параметры, называемые множителями Лагранжа. Рассмотрим задачу минимизации функции n переменных с учетом одного ограничения в виде равенства: Минимизировать
при
ограничениях В соответствии с методом множителей Лагранжа эта задача преобразуется в следующую задачу безусловной оптимизации: минимизировать L(x,u)=f(x)-u*h(x) (5) Функция L(х;u) называется функцией Лагранжа, u — неизвестная постоянная, которая носит название множителя Лагранжа. На знак u никаких требований не накладывается. Пусть
при заданном значении u=u0
безусловный минимум функции L(x,u) по х достигается в точке Разумеется, необходимо подобрать значение u=u° таким образом, чтобы координата точки безусловного минимума х° удовлетворяла равенству (4). Это можно сделать, если, рассматривая u как переменную, найти безусловный минимум функции (5) в виде функции u, а затем выбрать значение u, при котором выполняется равенство (4). Проиллюстрируем это на конкретном примере. Пример 2 Минимизировать
при
ограничении Соответствующая задача безусловной оптимизации записывается в следующем виде: минимизировать
L(x,u)= Решение. Приравняв две компоненты градиента L к нулю, получим Для того чтобы проверить, соответствует ли стационарная точка х° минимуму, вычислим элементы матрицы Гессе функции L(х;u), рассматриваемой как функция х,
которая
оказывается положительно определенной. Это означает, что L(х,,u) — выпуклая
функция х. Следовательно, координаты При
решении задачи из примера 2 мы рассматривали L(х;u) как функцию
двух переменных
в виде явных функций u получить нельзя, то значения х и u находятся путем решения следующей системы, состоящей из n+1 уравнений с n+1 неизвестными:
Для
нахождения всех возможных решений данной системы можно использовать численные
методы поиска (например, метод Ньютона). Для каждого из решений ( Метод множителей Лагранжа можно распространить на случай, когда задача имеет несколько ограничений в виде равенств. Рассмотрим общую задачу, в которой требуется Минимизировать f(x) при
ограничениях Функция Лагранжа принимает следующий вид: L(x,u)=f(x)- Здесь
……….. Если найти решение приведенной выше системы в виде функций вектора u оказывается затруднительным, то можно расширить систему путем включения в нее ограничений в виде равенств Решение расширенной системы, состоящей из n+К уравнений с n+К неизвестными, определяет стационарную точку функции L. Затем реализуется процедура проверки на минимум или максимум, которая проводится на основе вычисления элементов матрицы Гессе функции L, рассматриваемой как функция х, подобно тому, как это было проделано в случае задачи с одним ограничением. Для некоторых задач расширенная система n+К уравнений с n+K неизвестными может не иметь решений, и метод множителей Лагранжа оказывается неприменимым. Следует, однако, отметить, что такие задачи на практике встречаются достаточно редко. 3. Условия Куна-Таккера В предыдущем разделе было установлено, что множители Лагранжа можно использовать при построении критериев оптимальности для задач оптимизации с ограничениями в виде равенств. Кун и Таккер обобщили этот подход на случай общей задачи нелинейного программирования с ограничениями, как в виде равенств, так и в виде неравенств. Рассмотрим следующую общую задачу нелинейного программирования: минимизировать
при
ограничениях
Определение: Ограничение
в виде неравенства Если существует возможность обнаружить ограничения, которые неактивны в точке оптимума, до непосредственного решения задачи, то эти ограничения можно исключить из модели и тем самым уменьшить ее размеры. Основная трудность заключается при этом в идентификации неактивных ограничений, предшествующей решению задачи. Кун
и Таккер построили необходимые и достаточные условия оптимальности для задач
нелинейного программирования, исходя из предположения о дифференцируемости
функций 3.1. Условия Куна—Таккера и задача Куна—ТаккераНайти
векторы
Прежде всего проиллюстрируем условия Куна — Таккера на примере. Пример 3 Минимизировать
при
ограничениях Решение. Записав данную задачу в виде задачи нелинейного программирования (0)-(2), получим Уравнение (3), входящее в состав условий Куна—Таккера, принимает следующий вид: откуда Неравенства (4) и уравнения (5) задачи Куна — Таккера в данном случае записываются в виде
Уравнения (5.16), известные как условие дополняющей нежесткости, принимают вид
Заметим,
что на переменные Таким образом, этой задачи условия Куна—Танкера записываются в следующем виде: 3.2. Интерпретация условий Куна — ТаккераДля того чтобы интерпретировать условия Куна — Таккера, рассмотрим задачу нелинейного программирования с ограничениями в виде равенств: минимизировать
при
ограничениях Запишем условия Куна—Таккера
Далее рассмотрим функцию Лагранжа для задачи нелинейного программирования с ограничениями в виде равенств Для этой функции условия оптимальности первого порядка записываются в виде Нетрудно видеть, что условия Куна-Таккера (8) и (9) совпадают с условиями оптимальности первого порядка для задачи Лагранжа. Рассмотрим задачу нелинейного программирования с ограничениями в виде неравенств: минимизировать
при
ограничениях Запишем условия Куна—Таккера Соответствующая функция Лагранжа имеет вид Условия оптимальности первого порядка записываются как Заметим,
что Если
предположить, что Для
того чтобы определить знак 3.3. Теоремы Куна—ТаккераВ предыдущем разделе построены условия Куна—Таккера для задач условной оптимизации. С помощью метода множителей Лагранжа получено интуитивное представление о том, что условия Куна — Танкера тесно связаны с необходимыми условиями оптимальности. В данном разделе рассматриваются строгие формулировки необходимых и достаточных условий оптимальности решения задачи нелинейного программирования. Теорема 1. Необходимость условий Куна—Таккера Рассмотрим
задачу нелинейного программирования (0)-(2). Пусть Условие,
согласно которому 1. Все ограничения в виде равенств и неравенств содержат линейные функции. 2. Все ограничения в виде неравенств содержат вогнутые функции, все ограничения-равенства — линейные функции, а также существует, по крайней мере, одна допустимая точка х, которая расположена во внутренней части области, определяемой ограничениями-неравенствами. Другими словами, существует такая точка х, что Если условие линейной независимости в точке оптимума не выполняется, то задача Куна—Таккера может не иметь решения. Пример 4 Минимизировать
при
ограничениях Решение. На
рис.1 изображена область допустимых решений сформулированной выше нелинейной
задачи. Ясно, что оптимальное решение этой задачи есть
Рис.1 Допустимая область в задаче 4 Так как
Запишем условия Куна—Таккера и проверим, выполняются ли они в точке (1, 0). Условия (3), (6) и (7) принимают следующий вид;
При
Заметим,
что нарушение условия линейной независимости не обязательно означает, что точка
Куна—Таккера не существует. Для того чтобы подтвердить это, заменим целевую
функцию из этого примера функцией Нетрудно
проверить, что точка Теорема о необходимости условий Куна—Таккера позволяет идентифицировать неоптимальные точки. Другими словами, теорему 1 можно использовать для доказательства того, что заданная допустимая точка, удовлетворяющая условию линейной независимости, не является оптимальной, если она не удовлетворяет условиям Куна—Таккера. С другой стороны, если в этой точке условия Куна—Таккера выполняются, то нет гарантии, что найдено оптимальное решение нелинейной задачи. В качестве примера рассмотрим следующую задачу нелинейного программирования. Следующая теорема устанавливает условия, при выполнении которых точка Куна—Таккера автоматически соответствует оптимальному решению задачи нелинейного программирования. Теорема.2 Достаточность условий Куна—Таккера Рассмотрим
задачу нелинейного программирования (0) — (2). Пусть целевая функция Если условия теоремы 2 выполняются, то нахождение точки Куна—Таккера обеспечивает получение оптимального решения задачи нелинейного программирования. Теорему 2 можно также использовать для доказательства оптимальности данного решения задачи нелинейного программирования. В качестве иллюстрации опять рассмотрим пример: Минимизировать
при
ограничениях С
помощью теоремы 2 докажем, что решение Так
как матрица чтобы
показать, что функция Поскольку
матрица
Точка
Положив
Замечания 1.Для встречающихся на практике задач условие линейной независимости, как правило, выполняется. Если в задаче все функции дифференцируемы, то точку Куна—Таккера следует рассматривать как возможную точку оптимума. Таким образом, многие из методов нелинейного программирования сходятся к точке Куна—Таккера. (Здесь уместно провести аналогию со случаем безусловной оптимизации, когда соответствующие алгоритмы позволяют определить стационарную точку.) 2. Если условия теоремы 2 выполнены, точка Куна—Таккера в то же время оказывается точкой глобального минимума. К сожалению, проверка достаточных условий весьма затруднительна, и, кроме того, прикладные задачи часто не обладают требуемыми свойствами. Следует отметить, что наличие хотя бы одного нелинейного ограничения в виде равенства приводит к нарушению предположений теоремы 2. 3.Достаточные условия, установленные теоремой 2, можно обобщить на случай задач с невыпуклыми функциями, входящими в ограничения в виде неравенств, невыпуклыми целевыми функциями и нелинейными ограничениями-равенствами. При этом используются такие обобщения выпуклых функций, как квазивыпуклые и псевдовыпуклые функции. 4. Функции нескольких переменных Ограниченные возможности симплексного метода, заключенные в задачах со сложными видами ограничений и произвольным видом целевой функции, привели к широкому использованию итеративных методов поиска оптимального решения. Сначала
рассмотрим вопрос анализа «в статике» с использованием положений линейной
алгебры и дифференциального исчисления, а также условия, которые (в достаточно
общих возможных ситуациях) позволяют идентифицировать точки оптимума. Такие
условия используются для проверки выбранных точек и дают возможность выяснить,
являются ли эти точки точками минимума или максимума. При этом задача выбора
указанных точек остается вне рамок проводимого анализа; основное внимание
уделяется решению вопроса о том, соответствуют ли исследуемые точки решениям
многомерной задачи безусловной оптимизации, в которой требуется минимизировать f(x)
x Градиентом функции f(х) называют вектор, величина которого определяет скорость изменения функции f(x), а направление совпадает с направлением наибольшего возрастания этой функции. Следует
помнить, что функция f может принимать минимальное значение в точке x, в которой f или 4.1. Методы прямого поискаНиже рассматривается вопрос анализа «в динамике» для функций нескольких переменных, т. е. исследуются методы и алгоритмы, позволяющие на итерационной основе получать оценки х*— вектора управляемых переменных, которому соответствует минимальное значение функции f(x). Указанные методы применимы также к задачам максимизации, в которых целевую функцию следует заменить на -f(х). Методы, ориентированные на решение задач безусловной оптимизации, можно разделить на три широких класса в соответствии с типом используемой при реализации того или иного метода информации. 1. Методы прямого поиска, основанные на вычислении только значений целевой функции. 2. Градиентные методы, в которых используются точные значения первых производных f(x). 3. Методы второго порядка, в которых наряду с первыми производными используются также вторые производные функции f(x). Ниже рассматриваются методы, относящиеся к каждому из перечисленных классов, поскольку ни один метод или класс методов не отличается высокой эффективностью при решении оптимизационных задач различных типов. В частности, возможны случаи, когда происходит переполнение памяти ЭВМ; в других ситуациях вычисление значений целевой функции требует чрезмерных затрат времени; в некоторых задачах требуется получить решение с очень высокой степенью точности. В ряде приложений либо невозможно, либо весьма затруднительно найти аналитические выражения для производных целевой функции. Поэтому если предполагается использовать градиентные методы, следует применить процедуру разностной аппроксимации производных. В свою очередь это приводит к необходимости экспериментального определения длины шагов, позволяющего установить надлежащее соответствие между ошибкой округления и ошибкой аппроксимации. Таким образом, инженер вынужден приспосабливать применяемый метод к конкретным характеристикам решаемой задачи. Методы
решения задач безусловной оптимизации отличаются относительно высоким уровнем
развития по сравнению с другими методами нелинейного программирования. Ниже
речь идет о методах прямого поиска, для реализации которых требуются только
значения целевой функции; в следующем разделе рассматриваются градиентные
методы и методы второго порядка. Здесь предполагается, что f(x) непрерывна,
а Многомерные методы, реализующие процедуру поиска оптимума на основе вычисления значений функции, с общих позиций можно разделить на эвристические и теоретические. Эвристические методы, как это следует из названия, реализуют процедуры поиска с помощью интуитивных геометрических представлений и обеспечивают получение частных эмпирических результатов. С другой стороны, теоретические методы основаны на фундаментальных математических теоремах и обладают такими операционными свойствами, как сходимость (по крайней мере при выполнении некоторых определенных условий). Ниже подробно рассматриваются три метода прямого поиска: 1) поиск по симплексу, или S2-метод; 2) метод поиска Хука—Дживса; 3) метод сопряженных направлений Пауэлла. Первые два из перечисленных методов относятся к категории эвристических и реализуют принципиально различающиеся стратегии поиска. В процессе поиска по S2-методу последовательно оперируют регулярными симплексами в пространстве управляемых переменных, тогда как при реализации метода Хука-Дживса используется фиксированное множество (координатных) направлений, выбираемых рекурсивным способом. Метод Пауэлла основан на теоретических результатах и ориентирован на решение задач с квадратичными целевыми функциями; для таких задач метод сходится за конечное число итераций. К числу общих особенностей всех трех методов следует отнести относительную простоту соответствующих вычислительных процедур, которые легко реализуются и быстро корректируются. С другой стороны, реализация указанных методов может требовать (и часто требует) более значительных затрат времени по сравнению с методами с использованием производных. 4.1.1. Метод поиска по симплексу(S2 -метод)Первые попытки решения оптимизационных задач без ограничений на основе прямого поиска связаны с использованием одномерных методов оптимизации. Как правило, при реализации таких методов допустимая область определения показателя качества функционирования системы (целевой функции) заменяется дискретным множеством (решеткой) точек пространства управляемых переменных, а затем используются различные стратегии уменьшения области, которая содержит решение задачи. Часто эта процедура оказывается эквивалентной равномерному поиску в узлах решетки и, следовательно, непригодной для решения задач с числом переменных, превышающим 2. Более полезная идея заключается в выборе базовой точки и оценивании значений целевой функции в точках, окружающих базовую точку. Например, при решении задачи с двумя переменными можно воспользоваться квадратным образцом, изображенным на рис.2
Рис 2. Квадратный образец (частный случай кубического образца) Затем «наилучшая» из пяти исследуемых точек выбирается в качестве следующей базовой точки, вокруг которой строится аналогичный образец. Если ни одна из угловых точек не имеет преимущества перед базовой, размеры образца следует уменьшить, после чего продолжить поиск. Этот
тип эволюционной оптимизации был использован Боксом и другими
исследователями для анализа функционирования промышленных предприятий, когда
эффект варьирования значений переменных, описывающих производственные процессы,
измеряется с ошибкой. В задачах большой размерности вычисление значений целевой
функции проводится во всех вершинах, а также в центре тяжести гиперкуба (гиперкуб
куб в n-мерном евклидовом пространстве, т.е. множество S=x=( Одна из вызывающих особый интерес стратегий поиска положена в основу метода поиска по симплексу, предложенного Спендли, Хекстом и Химсвортом. Следует отметить, что указанный метод и другие подобные методы не имеют отношения к симплекс-методу линейного программирования, а сходство названий носит случайный характер. Процедура симплексного поиска Спендли, Хекста и Химсворта базируется на том, что экспериментальным образцом, содержащим наименьшее количество точек, является регулярный симплекс. Регулярный симплекс в n-мерном пространстве представляет собой многогранник, образованный n+1 равностоящими друг от друга точками-вершинами. Например, в случае двух переменных симплексом является равносторонний треугольник; в трехмерном пространстве симплекс представляет собой тетраэдр. В алгоритме симплексного поиска используется важное свойство симплексов, согласно которому новый симплекс можно построить на любой грани начального симплекса путем переноса выбранной вершины на надлежащее расстояние вдоль прямой, проведенной через центр тяжести остальных вершин начального симплекса. Полученная таким образом точка является вершиной нового симплекса, а выбранная при построении вершина начального симплекса исключается. Нетрудно видеть, что при переходе к новому симплексу требуется одно вычисление значения целевой функции. Рис 3 иллюстрирует процесс построения нового симплекса на плоскости.
Рис.3.Построение нового симплекса. а
начальный симплекс б
новый симплекс
Работа алгоритма симплексного поиска начинается с построения регулярного симплекса в пространстве независимых переменных и оценивания значений целевой функции в каждой из вершин симплекса. При этом определяется вершина, которой соответствует наибольшее значение целевой функции. Затем найденная вершина проецируется через центр тяжести остальных вершин симплекса в новую точку, которая используется в качестве вершины нового симплекса. Если функция убывает достаточно плавно, итерации продолжаются до тех пор, пока либо не будет накрыта точка минимума, либо не начнется циклическое движение по двум или более симплексам. В таких ситуациях можно воспользоваться следующими тремя правилами. Правило 1. «Накрытие» точки минимума Если вершина, которой соответствует наибольшее значение целевой функции, построена на предыдущей итерации, то вместо нее берется вершина, которой соответствует следующее по величине значение целевой функции. Правило 2. Циклическое движение Если некоторая вершина симплекса не исключается на протяжении более чем М итераций, то необходимо уменьшить размеры симплекса с помощью коэффициента редукции и построить новый симплекс, выбрав в качестве базовой точку, которой соответствует минимальное значение целевой функции. Спендли, Хекст и Химс-ворт предложили вычислять М по формуле M=1,65n+0,05 где n — размерность задачи, а М округляется до ближайшего целого числа. Для применения данного правила требуется установить величину коэффициента редукции. Правило 3. Критерий окончания поиска Поиск завершается, когда или размеры симплекса, или разности между значениями функции в вершинах становятся достаточно малыми. Чтобы можно было применять эти правила, необходимо задать величину параметра окончания поиска. Реализация
изучаемого алгоритма основана на вычислениях двух типов: (1) построении
регулярного симплекса при заданных базовой точке и масштабном множителе и (2)
расчете координат отраженной точки. Построение симплекса является достаточно
простой процедурой, так как из элементарной геометрии известно, что при
заданных начальной (базовой) точке
для i и j=1,2,3,…,n Приращения
Заметим,
что величина масштабного множителя
Все
точки прямой, проходящей через
При
Проиллюстрируем вычислительную схему метода следующим примером. Пример 5. Вычисления в соответствии с методом поиска по симплексу Минимизировать
f(x)= Решение. Для
построения исходного симплекса требуется задать начальную точку и масштабный
множитель. Пусть x Используя эти два параметра, вычислим координаты двух остальных вершин симплекса: которым
соответствуют значения целевой функции, равные Используя формулу (12), получаем В
полученной точке Изложенный
выше алгоритм 1. Расчеты и логическая структура метода отличаются сравнительной простотой, и, следовательно, соответствующая программа для ЭВМ оказывается относительно короткой. 2. Уровень требований к объему памяти ЭВМ невысокий, массив имеет размерность (n+1, n+2). 3.
Используется сравнительно небольшое число заранее установленных параметров: масштабный
множитель 4. Алгоритм оказывается эффективным даже в тех случаях, когда ошибка вычисления значений целевой функции велика, поскольку при его реализации оперируют наибольшими значениями функции в вершинах, а не наименьшими. Перечисленные факторы характеризуют метод поиска по симплексу как весьма полезный при проведении вычислений в реальном времени. Алгоритм обладает также рядом существенных недостатков. 1.
Не исключено возникновение трудностей, связанных с масштабированием, поскольку
все координаты вершин симплекса зависят от одного и того же масштабного множителя
2. Алгоритм работает слишком медленно, так как полученная на предыдущих итерациях информация не используется для ускорения поиска. 3.
Не существует простого способа расширения симплекса, не требующего пересчета
значений целевой функции во всех точках образца. Таким образом, если 4.1.2. Метод поиска Хука-Дживса.Метод, разработанный Хуком и Дживсом, является одним из первых алгоритмов, в которых при определении нового направления поиска учитывается информация, полученная на предыдущих итерациях. По существу процедура Хука—Дживса представляет собой комбинацию «исследующего» поиска с циклическим изменением переменных и ускоряющегося поиска по образцу с использованием определенных эвристических правил. Исследующий поиск ориентирован на выявление характера локального поведения целевой функции и определение направлений вдоль «оврагов». Полученная в результате исследующего поиска информация затем используется в процессе поиска по образцу при движении по «оврагам». Исследующий поиск. Для проведения исследующего поиска необходимо задать величину шага, которая может быть различной для разных координатных направлений и изменяться в процессе поиска. Исследующий поиск начинается в некоторой исходной точке. Если значение целевой функции в пробной точке не превышает значения функции в исходной точке, то шаг поиска рассматривается как успешный. В противном случае необходимо вернуться в предыдущую точку и сделать шаг в противоположном направлении с последующей проверкой значения целевой функции. После перебора всех N координат исследующий поиск завершается. Полученную в результате точку называют базовой точкой. Поиск по образцу. Поиск по образцу заключается в реализации единственного шага из полученной базовой точки вдоль-прямой, соединяющей эту точку с предыдущей базовой точкой. Новая точка образца определяется в соответствии с формулой Как
только движение по образцу не приводит к уменьшению целевой функция, точка
Приведенная последовательность характеризует логическую структуру поиска по методу Хука Дживса. Структура метода поиска Хука — Дживса Шаг 1 . Определить: начальную точку приращения коэффициент уменьшения шага параметр окончания поиска Ш а г 2. ровести исследующий поиск. Ш а г 3. Был ли исследующий поиск удачным (найдена ли точка с меньшим значением целевой функции)? Да: перейти к шагу 5. Нет: продолжать. Ш а г 4. Проверка на окончание поиска. Выполняется
ли неравенство Да: прекратить поиск; текущая точка аппроксимирует точку
оптимума Нет: уменьшить приращения по формуле Перейти к шагу 2. Ш а г 5. Провести поиск по образцу: Шаг
6. Провести исследующий поиск, используя пусть
Ш
а г 7. Выполняется ли неравенство Да: положить Нет: перейти к шагу 4. Пример 6 Поиск по методу Хука — Дживса Найти
точку минимума функции Решение. Для того чтобы применить метод прямого поиска .Хука — Дживса, необходимо задать следующие величины:
Итерации
начинаются с исследующего поиска вокруг точки
Следовательно,
необходимо зафиксировать
Таким образом, в результате исследующего поиска найдена точка Поскольку исследующий поиск был удачным, переходим к поиску по образцу: Далее
проводится исследующий поиск вокруг точки Поскольку
Из примера следует, что метод Хука — Дживса характеризуется несложной стратегией поиска, относительной простотой вычислений и невысоким уровнем требований к объему памяти ЭВМ, который оказывается даже ниже, чем в случае использования метода поиска по симплексу.
Итерации поиска по методу Хука-Дживса на примере |
|