Суррогатный алгоритм оптимизации
Последовательный surrogateopt Алгоритм
Последовательный surrogateopt Обзор алгоритма
Суррогатный алгоритм оптимизации чередуется между двумя фазами.
Создайте суррогат — создают
options.MinSurrogatePointsслучайные точки в границах. Выполните (дорогую) целевую функцию в этих точках. Создайте суррогат целевой функции путем интерполяции радиальной основной функции через эти точки.Поиск Минимума — Поиск минимума целевой функции путем выборки нескольких тысяч случайных точек в границах. Оцените оценочную функцию на основе суррогатного значения в этих точках и на расстояниях между ними и точками, где (дорогая) целевая функция была выполнена. Выберите лучшую точку в качестве кандидата, как измерено оценочной функцией. Выполните целевую функцию в лучшей точке кандидата. Эта точка называется adaptive point. Обновите суррогат с помощью этого значения и ищите снова.
Во время фазы Construct Surrogate алгоритм создает точки выборки из квазислучайной последовательности. Построение интерполирующей радиальной основной функции берет, по крайней мере, nvars + 1 точка выборки, где nvars количество переменных задачи. Значение по умолчанию options.MinSurrogatePoints 2*nvars или 20, какой бы ни больше.
Алгоритм останавливает Поиск фазы Minimum, когда все поисковые точки слишком близки (меньше, чем опция MinSampleDistance) к точкам, где целевая функция была ранее выполнена. Смотрите Поиск Минимальных Деталей. Этот переключатель от Поиска фазы Minimum называется surrogate reset.
Определения для суррогатной оптимизации
Суррогатное описание алгоритма оптимизации использует следующие определения.
Текущий — точка, где целевая функция была выполнена последний раз.
Действующий — точка с наименьшим значением целевой функции среди всех оцененных начиная с нового суррогатного сброса.
Лучше всего — точка с наименьшим значением целевой функции среди всех оцененных до сих пор.
Начальная буква — точки, если таковые имеются, что вы передаете решателю в
InitialPointsопция.Случайные точки — Точки в фазе Construct Surrogate, где решатель выполняет целевую функцию. Обычно решатель берет эти точки из квазислучайной последовательности, масштабируемой и переключенной, чтобы остаться в границах. Квазислучайная последовательность похожа на псевдослучайную последовательность такой как
randвозвращается, но более равномерно расположен с интервалами. См. https://en.wikipedia.org/wiki/Low-discrepancy_sequence. Однако, когда количество переменных выше 500, решатель берет точки из латинской последовательности гиперкуба. См. https://en.wikipedia.org/wiki/Latin_hypercube_sampling.Адаптивные точки — Точки в Поиске фазы Minimum, где решатель выполняет целевую функцию.
Оценочная функция — Видит Определение Оценочной функции.
Оцененные точки — Все точки, в которых известно значение целевой функции. Эти точки включают начальные точки, точки Суррогата Построения и Поиск Минимальных точек, в которых решатель выполняет целевую функцию.
'SamplePoints' . Псевдослучайные точки, где решатель оценивает оценочную функцию во время Поиска фазы Minimum. Эти точки не являются точками, в которых решатель выполняет целевую функцию, за исключением описанного в поисках Минимальных Деталей.
Создайте суррогатные детали
Чтобы создать суррогат, алгоритм выбирает квазислучайные точки в границах. Если вы передаете начальный набор точек в InitialPoints опция, алгоритм использует те точки и новые квазислучайные точки (при необходимости), чтобы достигнуть в общей сложности options.MinSurrogatePoints.
Когда BatchUpdateInterval > 1, минимальное количество точек случайной выборки, используемых, чтобы создать суррогат, является большим из MinSurrogatePoints и BatchUpdateInterval.
Примечание
Если некоторые верхние границы и нижние границы равны, surrogateopt удаляет те "фиксированные" переменные из проблемы прежде, чем создать суррогат. surrogateopt управляет переменными беспрепятственно. Так, например, если вы передаете начальные точки, передаете полный набор, включая какие-либо фиксированные переменные.
На последующих фазах Construct Surrogate алгоритм использует options.MinSurrogatePoints квазислучайные точки. Алгоритм выполняет целевую функцию в этих точках.
Алгоритм создает суррогат как интерполяцию целевой функции при помощи интерполятора радиальной основной функции (RBF). Интерполяция RBF имеет несколько удобных свойств, которые делают ее подходящей для построения суррогата:
Интерполятор RBF задан с помощью той же формулы в любом количестве размерностей и с любым числом точек.
Интерполятор RBF берет заданные значения в оцененных точках.
Оценка интерполятора RBF занимает время.
Добавление точки к существующей интерполяции занимает относительно мало времени.
Построение интерполятора RBF включает решение N на n линейной системы уравнений, где N является количеством суррогатных точек. Когда Пауэлл [1] показал, эта система имеет уникальное решение для многих RBFs.
surrogateoptиспользует кубический RBF с линейным хвостом. Этот RBF минимизирует меру тряски. Смотрите Гутманна [4].
Алгоритм использует только начальные точки и случайные точки в первой фазе Construct Surrogate, и использует только случайные точки в последующих фазах Construct Surrogate. В частности, алгоритм не использует адаптивных точек от Поиска фазы Minimum в этом суррогате.
Ищите минимальные детали
Решатель ищет минимум целевой функции путем выполнения процедуры, которая связана с локальным поиском. Решатель инициализирует scale для поиска со значением 0.2. Шкала похожа на поисковый радиус области или размер mesh в поиске шаблона. Решатель начинает с действующей точки, которая является точкой с наименьшим значением целевой функции начиная с последнего суррогатного сброса. Решатель ищет минимум merit function, который относится и к суррогату и к расстоянию от существующих поисковых точек, чтобы попытаться сбалансировать минимизацию суррогата и поиск пробела. См. Определение Оценочной функции.
Решатель добавляет сотни или тысячи псевдослучайных векторов с масштабированной длиной к действующей точке, чтобы получить sample points. Эти векторы имеют нормальные распределения, переключенные и масштабированные границами в каждой размерности и умноженные на шкалу. При необходимости решатель изменяет точки выборки так, чтобы они остались в границах. Решатель оценивает оценочную функцию при точках выборки, но не в любой точке в options.MinSampleDistance из ранее оцененной точки. Точка с самым низким значением оценочной функции называется адаптивной точкой. Решатель оценивает значение целевой функции в адаптивной точке и обновляет суррогат с этим значением. Если значение целевой функции в адаптивной точке достаточно ниже, чем действующее значение, то решатель считает поиск успешным и устанавливает адаптивную точку как должностное лицо. В противном случае решатель считает поиск неудачным и не изменяет должностное лицо.
Решатель изменяет шкалу, когда первое из этих условий соблюдают:
Три успешных поисковых запросов происходят начиная с последнего изменения шкалы. В этом случае шкала удвоена до максимальной длины шкалы
0.8времена размер поля заданы границами.max(5,nvar)неудачные поисковые запросы происходят начиная с последнего изменения шкалы, гдеnvarколичество переменных задачи. В этом случае шкала разделена на два, вниз к минимальной длине шкалы1e-5времена размер поля заданы границами.
Таким образом случайный поиск в конечном счете концентрируется около действующей точки, которая имеет маленькое значение целевой функции. Затем решатель геометрически уменьшает шкалу к минимальной длине шкалы.
Решатель не оценивает оценочную функцию при точках в options.MinSampleDistance из оцененной точки (см. Определения для Суррогатной Оптимизации). Переключатели решателя от Поиска фазы Minimum к фазе Construct Surrogate (другими словами, выполняет суррогатный сброс), когда все точки выборки в MinSampleDistance из оцененных точек. Обычно этот сброс происходит после того, как решатель уменьшает шкалу так, чтобы все точки выборки плотно кластеризировались вокруг должностного лица.
Когда BatchUpdateInterval опция больше, чем 1, решатель генерирует BatchUpdateInterval адаптивные точки прежде, чем обновить суррогатную модель или изменить должностное лицо. Обновление включает все адаптивные точки. Эффективно, алгоритм не использует новой информации, пока это не генерирует BatchUpdateInterval адаптивные точки, и затем алгоритм используют всю информацию, чтобы обновить суррогат.
Определение оценочной функции
Оценочная функция заслуга f (x) является взвешенной комбинацией двух условий:
Масштабированный суррогат. Задайте min s как минимальное суррогатное значение среди точек выборки, s макс. как максимум и s (x) как суррогатное значение в точке x. Затем масштабированный суррогатный S (x)
s (x) является неотрицательным и является нулем в точках x, которые имеют минимальное суррогатное значение среди точек выборки.
Масштабированное расстояние. Задайте xj, j = 1, …, k, когда k оценил точки. Задайте dij как расстояние от точки выборки i к оцененной точке k. Установите min d = min (dij) и d макс. = макс. (dij), где минимум и максимум взяты по всему i и j. Масштабированное расстояние D (x)
где d (x) является минимальным расстоянием точки x к оцененной точке. D (x) является неотрицательным и является нулем в точках x, которые максимально далеки от оцененных точек. Так, минимизация D (x) приводит алгоритм к точкам, которые далеки от оцененных точек.
Оценочная функция является выпуклой комбинацией масштабированного суррогата и масштабируемого расстояния. Для веса w с 0 <w <1, оценочная функция
Большое значение w дает важность для суррогатных значений, заставляя поиск минимизировать суррогат. Маленькое значение w дает важность для точек, которые далеки от оцененных точек, ведя поиск в новые области. Во время Поиска фазы Minimum, вес циклы w через эти четыре значения, как предложил Режис и Сапожник [2]: 0.3, 0.5, 0.8, и 0.95.
Смешано-целочисленный surrogateopt Алгоритм
Смешанное целое число surrogateopt Обзор
Когда некоторые или все переменные - целое число, как задано в intcon аргумент, surrogateopt изменения некоторые аспекты Последовательного surrogateopt Алгоритма. Это описание в основном об изменениях, а не целом алгоритме.
Алгоритм запускается
При необходимости, surrogateopt перемещает заданные границы для intcon точки так, чтобы они были целыми числами. Кроме того, surrogateopt гарантирует, что предоставленная начальная точка является целым числом, выполнимым и выполнимым относительно границ. Алгоритм затем генерирует квазислучайные точки как в алгоритме нецелого числа, округляя целочисленные точки к целочисленным значениям. Алгоритм генерирует суррогат точно так же, как в алгоритме нецелого числа.
Целочисленный поиск минимума
Поиск минимума продолжает с помощью той же оценочной функции и последовательности весов как прежде. Различие - это surrogateopt использование три различных метода выборки случайных точек, чтобы определить местоположение минимума оценочной функции. surrogateopt выбирает сэмплер в цикле, сопоставленном с весами согласно следующей таблице.
Цикл сэмплера
| Вес | 0.3 | 0.5 | 0.8 | 0.95 |
| Сэмплер | Случайный | Случайный | OrthoMADS | GPS |
Шкала — Каждый сэмплер выборки указывает в масштабированной области вокруг должностного лица. Целочисленные точки имеют шкалу, которая запускается в ½ раза ширине границ и настраивает точно так же, как нецелое число указывает, за исключением того, что ширина увеличена до 1, если это когда-либо падало бы ниже 1. Шкала непрерывных точек разрабатывает точно так же, как в алгоритме нецелого числа.
Случайный — сэмплер генерирует целочисленные точки однородно наугад в шкале, сосредоточенной в должностном лице. Сэмплер генерирует непрерывные точки согласно Гауссову со средним нулем от должностного лица. Ширина выборок целочисленных точек умножается на шкалу, как стандартное отклонение непрерывных точек.
OrthoMADS — Сэмплер выбирает систему прямоугольной координаты однородно наугад. Алгоритм затем создает точки выборки вокруг должностного лица, добавляя и вычитая текущие времена шкалы каждый единичный вектор в системе координат. Алгоритм округляет целочисленные точки. Это создает выборки на 2 Н (если некоторые целочисленные точки не округлены должностному лицу), где N является количеством проблемных размерностей. OrthoMADS также использует еще две точки, чем 2 Н зафиксировали направления, один в [+1, +1, …, +1], и другой в [–1, –1, …, –1], для в общей сложности 2N+2 точки. Затем сэмплер неоднократно половины 2 Н + 2 шага, создавая более прекрасный и более прекрасный набор точек вокруг должностного лица, при округлении целочисленных точек. Этот процесс заканчивается, когда или существует достаточно выборок или округления причин никакие новые выборки.
GPS — сэмплер похож на OrthoMADS, кроме вместо того, чтобы выбрать случайный набор направлений, GPS использует невращаемую систему координат.
Поиск по дереву
После выборки сотен или тысяч значений оценочной функции, surrogateopt обычно выбирает минимальную точку и выполняет целевую функцию. Однако при двух обстоятельствах, surrogateopt выполняет другой поиск, названный Поиском по дереву прежде, чем оценить цель:
Были шаги на 2 Н начиная с последнего Поиска по дереву, названного Случаем A.
surrogateoptсобирается выполнить суррогатный сброс, названный Случаем B.
Поиск по дереву продолжает можно следующим образом, похожий на процедуру в intlinprog, как описано в Ветви и Связанный. Алгоритм делает дерево путем нахождения целочисленного значения и создания новой проблемы, которая имеет привязанный это значение или один выше или один ниже, и решение подпроблемы с этим новым связанный. После решения подпроблемы алгоритм выбирает различное целое число, которое будет ограничено любой выше или ниже одним.
Случай A: Используйте масштабированный радиус выборки в качестве полных границ и запуска максимум для 1 000 шагов поиска.
Случай B: Используйте исходные проблемные границы в качестве полных границ и запуска максимум для 5 000 шагов поиска.
В этом случае решение подпроблемы означает запускаться fmincon
'sqp' алгоритм на непрерывных переменных, запускающихся от должностного лица с заданными целочисленными значениями, так ищут локальный минимум оценочной функции.
Поиск по дереву может быть длительным. Так surrogateopt имеет внутреннее ограничение по времени, чтобы избежать чрезмерного времени на этом шаге, ограничивая и количество Случая A и Случай B шаги.
В конце Поиска по дереву алгоритм берет лучше точки, найденной Поиском по дереву и точкой, найденной предыдущим поиском минимума, как измерено оценочной функцией. Алгоритм выполняет целевую функцию в этой точке. Остаток от целочисленного алгоритма является точно тем же самым как непрерывным алгоритмом.
Линейная ограничительная обработка
Когда проблема имеет линейные ограничения, алгоритм изменяет свою поисковую процедуру способом, которая сохраняет все точки выполнимыми относительно этих ограничений и относительно границ в каждой итерации. Во время конструкции и поисковых фаз, алгоритм создает только линейно допустимые точки процедурой, похожей на patternsearch
'GSSPositiveBasis2N' опросите алгоритм.
Когда проблема имеет целочисленные ограничения и линейные ограничения, алгоритм сначала создает линейно допустимые точки. Затем алгоритм пытается удовлетворить целочисленным ограничениям процессом округления линейно допустимых точек до целых чисел с помощью эвристики, которая пытается, сохраняет точки линейно выполнимыми. Когда этот процесс неудачен в получении достаточного количества допустимых точек для построения суррогата, вызовов алгоритма intlinprog попытаться найти больше точек, которые выполнимы относительно границ, линейных ограничений и целочисленных ограничений.
surrogateopt Алгоритм с нелинейными ограничениями
Когда проблема имеет нелинейные ограничения, surrogateopt изменяет ранее описанный алгоритм несколькими способами.
Первоначально и после каждого суррогатного сброса, алгоритм создает суррогаты объективных и нелинейных ограничительных функций. Впоследствии, алгоритм отличается в зависимости от того, нашла ли фаза Construct Surrogate какие-либо допустимые точки; нахождение допустимой точки эквивалентно действующей точке, являющейся выполнимым, когда суррогат создается.
Действующий неосуществимо — Этот случай, названный Фазой 1, включает поиск допустимой точки. В Поиске фазы Minimum прежде, чем столкнуться с допустимой точкой,
surrogateoptизменяет определение оценочной функции. Алгоритм считает количество ограничений, которые нарушены в каждой точке, и рассматривает только те вопросы с наименьшим количеством количества нарушенных ограничений. Среди тех точек алгоритм выбирает точку, которая минимизирует максимальное нарушение ограничений как лучшее (самая низкая оценочная функция) точка. Эта лучшая точка является должностным лицом. Впоследствии, пока алгоритм не сталкивается с допустимой точкой, он использует эту модификацию оценочной функции. Когдаsurrogateoptоценивает точку и находит, что это выполнимо, допустимая точка становится должностным лицом, и алгоритм находится в Фазе 2.Действующий выполнимо — Этот случай, названный Фазой 2, продолжает таким же образом как стандартный алгоритм. Алгоритм игнорирует неосуществимые точки в целях вычисления оценочной функции.
Алгоритм продолжает согласно Смешанному Целому числу surrogateopt Алгоритм со следующими изменениями. После каждого 2*nvars точки, где алгоритм выполняет объективные и нелинейные ограничительные функции, surrogateopt вызывает fmincon функция, чтобы минимизировать суррогат согласно суррогатным нелинейным ограничениям и границам, где границы масштабируются текущим масштабным коэффициентом. (Если должностное лицо неосуществимо, fmincon игнорирует цель и пытается найти точку, удовлетворяющую ограничениям.), Если проблема имеет и целочисленные и нелинейные ограничения, то surrogateopt Поиск по дереву вызовов вместо fmincon.
Если проблемой является проблема выполнимости, означая, что она не имеет никакой целевой функции, то surrogateopt сразу выполняет суррогатный сброс после того, как он найдет допустимую точку.
Параллельный surrogateopt Алгоритм
Параллельный surrogateopt алгоритм отличается от последовательного алгоритма можно следующим образом:
Параллельный алгоритм обеспечивает очередь точек, на которых можно выполнить целевую функцию. Эта очередь является на 30% более многочисленной, чем количество параллельных рабочих, окруженных. Очередь является более многочисленной, чем количество рабочих, чтобы свести к минимуму вероятность, что рабочий неактивен, потому что никакой смысл не доступен, чтобы оценить.
Планировщик берет точки из очереди способом FIFO и присваивает их рабочим, когда они становятся неактивными, асинхронно.
Когда переключатели алгоритма между фазами (Поиск Суррогата Минимума и Построения), существующие оцениваемые точки остаются в обслуживании, и любые другие точки в очереди сбрасываются (отброшенный от очереди). Так, обычно, количество случайных точек, которые алгоритм создает для фазы Construct Surrogate, в большей части
options.MinSurrogatePoints + PoolSize, гдеPoolSizeколичество параллельных рабочих. Точно так же после суррогатного сброса, алгоритм все еще имеетPoolSize - 1адаптивные точки, что его рабочие оценивают.
Примечание
В настоящее время найдите что-либо подобное суррогатной оптимизации, не обязательно дает восстанавливаемые результаты, из-за невоспроизводимости параллельной синхронизации, которая может привести к различным путям к выполнению.
Найдите что-либо подобное Смешанному Целому числу surrogateopt Алгоритм
Когда запущено параллельно на смешанной целочисленной задаче, surrogateopt выполняет процедуру Поиска по дереву на хосте, не на параллельных рабочих. Используя последний суррогат, surrogateopt поиски меньшего значения суррогата после каждого рабочего возвращаются с адаптивной точкой.
Если целевая функция не дорога (длительный), то эта процедура Поиска по дереву может быть узким местом на хосте. В отличие от этого, если целевая функция является дорогой, то процедура Поиска по дереву берет небольшую часть полного вычислительного времени и не является узким местом.
Ссылки
[1] Пауэлл, M. J. D. Теория Радиального Приближения Основной функции в 1 990. В Свете, W. A. (редактор), Усовершенствования в Числовом Анализе, Объем 2: Вейвлеты, Алгоритмы Подразделения и Радиальные Основные функции. Нажатие Clarendon, 1992, стр 105–210.
[2] Режис, R. G. и К. А. Шоемэкер. Стохастический Радиальный Метод Основной функции для Глобальной Оптимизации Дорогих Функций. INFORMS J. Вычисляя 19, 2007, стр 497–509.
[3] Ван, Y. и К. А. Шоемэкер. Общая Стохастическая Среда Алгоритма для Минимизации Дорогих Целевых функций Черного квадрата На основе Суррогатных Моделей и Анализа чувствительности. arXiv:1410.6271v1 (2014). Доступный в https://arxiv.org/pdf/1410.6271.
[4] Гутманн, H.-M. Радиальный Метод Основной функции для Глобальной Оптимизации. Журнал Глобальной Оптимизации 19, март 2001, стр 201–227.