Сеточный поиск

Cтраница 1

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

Сеточный поиск Хука и Дживса - это простой метод прямого поиска, очень полезный на практике. [2]

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

Метод исключения областей ( касательной к линии уровня в случае вогнутых линий уровня. [4]

Одним из методов исключения является метод сеточного поиска, разработанный Мишке [15] и дающий неплохие результаты. В этом случае суженная область неопределенности представляет собой гиперкуб - многомерный аналог квадрата или куба - размеры которого можно определить заранее. Благодаря этому метод Мишке является одним из немногих методов многомерного поиска, эффективность которого поддается измерению. [5]

Выбор направления в методе суммирования градиентов. [6]

Величина пробного шага вдоль направления р выбирается порядка величин пробных шагов сеточного поиска. Пусть при этом нарушается новое ограничение задачи. [7]

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

Для конкретной реализации алгоритма необходимо учитывать, что функция В ( х, г) определена только внутри допустимой области. Так, при сеточном поиске мы предпочитаем запрещать те пробные шаги из точки, которые нарушают ограничения задачи. Если некоторое сеточное перемещение выводит текущую точку в недопустимую область, то для определения допустимой точки с меньшим значением целевой функции можно попытаться применить технику Хука и Дживса так же, как и для безусловной минимизации. При использовании методов линейного поиска Пауэлла и ДСК в случае, когда пробная точка нарушает ограничения задачи, величина шага уменьшается до тех пор, пока не получится допустимая пробная точка. После этого, если возможно, один раз для оценки минимума функции В ( х, г) вдоль исследуемого направления делается ее квадратичная интерполяция. Далее, среди имеющихся допустимых пробных точек выбирается точка с наименьшим значением целевой функции. [11]

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

В сеточное множество входят такие переменные, которые попадают в е-окрестность своего верхнего или нижнего предела. Величина е выбирается по порядку величины больше наименьшего пробного шага в сеточном поиске. Поиск начинается с симплексных итераций, число которых не превышает 2п, при этом итерация определяется как отражение худшей вершины с последующим растяжением или сжатием. Итераций будет менее 2п, если симплексный поиск сходится или появляется новая сеточная переменная. Последнее происходит в том случае, когда отражение или нарушает ограничения, или приводит в е-окрестность границы. В результате соответствующая переменная переходит из симплексного множества в сеточное. Заметим, что растяжения, которые нарушают ограничения или приводят в е-окрестность границы, считаются просто недопустимыми. Если симплексный поиск сошелся и множество сеточных переменных пусто, то задача считается решенной. [13]

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

Страницы: 1 2