Алгоритм MCS - MCS algorithm
 | эта статья не цитировать Любые источники. (Июль 2012 г.) (Узнайте, как и когда удалить этот шаблон сообщения) |
 | эта статья предоставляет недостаточный контекст для тех, кто не знаком с предметом. (Октябрь 2009 г.) (Узнайте, как и когда удалить этот шаблон сообщения) |
Многоуровневый поиск по координатам (MCS) является эффективным алгоритм для связанных ограничений глобальная оптимизация с помощью функция ценности только.
Для этого n-мерный пространство поиска представлен набором непересекающихся гиперкубов (ящиков). Затем блоки итеративно разделяются вдоль оси в соответствии со значением функции в репрезентативной точке блока (и его соседей) и размером блока. Эти два критерия разделения объединяются для формирования глобального поиска путем разделения больших блоков и локального поиска путем разделения областей, для которых значение функции подходит.
Кроме того, локальный поиск, сочетающий (многомерный) квадратичный интерполянт функции и линейный поиск можно использовать для увеличения производительности алгоритма (MCS с локальным поиском); в этом случае простой MCS используется для определения начальных (начальных) точек. Информация, предоставленная локальным поиском (а именно, локальные минимумы целевой функции), затем возвращается оптимизатору и влияет на критерии разделения, что приводит к уменьшению кластеризации выборки вокруг локальных минимумов и более быстрой сходимости.
Упрощенный рабочий процесс
Основной рабочий процесс представлен на рисунке 1. Как правило, каждый шаг можно охарактеризовать как три этапа:
- Определите потенциального кандидата на расщепление (пурпурный, толстый).
- Определите оптимальное направление разделения и ожидаемое оптимальное положение точек разделения (зеленый).
- Оцените целевую функцию в точках разделения, которые ранее не рассматривались. Создайте новые прямоугольники (пурпурный, тонкий) на основе значений целевой функции в точках разделения (зеленые).
На каждом шаге по крайней мере одна точка разделения (желтая) представляет собой образец известной функции (красный), поэтому цель никогда не оценивается снова.
Чтобы определить, будет ли коробка разделена, используются два отдельных критерия разделения. Первый, разделение по рангу, гарантирует, что большие блоки, которые не разделялись слишком часто, в конечном итоге будут разделены. Если это применимо, то точку разделения можно определить априори. Второй, разделение на ожидаемую прибыль, использует локальную одномерную квадратичную модель (суррогат) по одной координате. В этом случае точка разделения определяется как минимум суррогата, и блок разделяется только в том случае, если значение интерполянта ниже, чем текущее значение наилучшей выборки функции.
Конвергенция
Алгоритм гарантированно сходится к глобальному минимуму в долгосрочной перспективе (т.е. когда количество вычислений функции и глубина поиска произвольно велики), если целевая функция непрерывна в окрестности глобального минимизатора. Это следует из того факта, что любой блок в конечном итоге станет сколь угодно маленьким, следовательно, интервал между выборками стремится к нулю, поскольку количество вычислений функции стремится к бесконечности.
Рекурсивная реализация
MCS была разработана для эффективной рекурсивный путь с помощью деревья. При таком подходе требуемый объем памяти не зависит от размерности проблемы, поскольку точки выборки не сохраняются явно. Вместо этого сохраняется только одна координата каждого образца, а оставшиеся координаты могут быть восстановлены путем отслеживания истории блока до корня (начального блока). Этот метод был предложен авторами и использован в их первоначальной реализации.
При тщательной реализации это также позволяет избежать повторных вычислений функций. Точнее, если точка выборки размещается вдоль границы двух соседних блоков, то эту информацию часто можно извлечь путем обратного отслеживания истории точки для небольшого количества шагов. Следовательно, новые суббоксы могут быть созданы без оценки (потенциально дорогостоящей) целевой функции. Этот сценарий визуализирован на рисунке 1, когда зеленая (но не желтая) и красная точки совпадают, например. когда коробка с углами вокруг и разделен.
