Поиск методом прямого спуска (Direct Descent Search)

Поиск методом прямого спуска — один из многих очень быстрых методов направленного поиска. Главное отличие направленного поиска от поиска на решетке — это то, что может быть названо «информированной избирательностью» («enlighten selectivity»). Поиск на решетке последовательно рассматривает каждого кандидата в тестовой группе. Направленный поиск отыскивает путь к наивысшей эффективности в тестовой группе и доводит его до логического завершения.

В течение этого он отбрасывает эффективность, которая меньше уже найденной, отдает предпочтение лучшей эффективности и двигается в этом «направлении» в рамках набора тестов или модельного пространства, как его иногда называют. Графически эта идея представлена на Рисунке 5-2. Достоинство «информированной избирательности», встроенной в методы направленного поиска, в том, что обычно она делает эти методы очень быстрыми. Метод направленного поиска может потребовать расчета всего 5-10% всех возможных моделей, в то время как метод поиска на решетке рассчитывает число всех комбинаций.

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

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

Многоточечный направленный поиск отбирает группу различных стартовых точек. Они могут выбираться несколькими способами, например, случайным выбором из пространства переменных или путем деления пространства переменных на равные по величине сегменты и выбора в качестве точки входа «центра» каждого сегмента. (См. Рисунок 5-3). Затем данный поиск входит в пространство переменных в своей первой точке входа и ищет лучшую модель в этой области. Если данный поиск после выполнения определенного заранее заданного числа шагов не дает кандидата, удовлетворяющего критерию эффективности, поиск на решетке в локальной области прекращается и перемещается на следующую стартовую точку. Если же данный кандидат действительно удовлетворяет минимальному критерию эффективности, то далее выполняется поиск на решетке в этой локальной области модельного пространства. Мы находим топ-модель и запоминаем ее. Затем поиск переходит к следующей стартовой точке, и этот процесс повторяется. Если модель, удовлетворяющая критерию эффективности, найдена, то в этой области выполняется поиск на решетке, и топ-модель, обнаруженная здесь, сравнивается с топ-моделью, найденной в предыдущих поисках. Если она лучше, то становится новой топ-моделью. Если же она не столь хороша, то мы ее отвергаем. Многоточечный направленный поиск продолжается таким образом до тех пор, пока не будут исследованы все точки входа.

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