paretosearch Алгоритм
paretosearch Обзор алгоритма
The paretosearch алгоритм использует поиск шаблона для набора точек, чтобы итерационно искать недоминированные точки. См. «Мультиобъективная терминология». Поиск шаблона удовлетворяет всем границам и линейным ограничениям при каждой итерации.
Теоретически алгоритм сходится к точкам около истинного фронта Парето. Для обсуждения и доказательства сходимости смотрите Cust, dio et al. [1], чье доказательство относится к проблемам с непрерывными целями и ограничениями Липшица.
Определения для paretosearch Алгоритм
paretosearch использует в своем алгоритме ряд промежуточных величин и допусков.
| Количество | Определение |
|---|---|
| Ранг | Ранг точки имеет итеративное определение.
|
| Объем | Гипертом набора точек p в пространстве целевой функции, которые удовлетворяют неравенству, для каждого j индекса, fi (j) < p i < M i, где fi (j) является i-м компонентом значения j-й целевой функции в наборе Парето, а M i является верхней границей для i-го компонента для всех точек в наборе Парето. На этом рисунке M называется контрольной точкой. Оттенки серого на рисунке обозначают фрагменты объема, которые некоторые алгоритмы вычисления используют как часть вычисления включения-исключения.
Для получения дополнительной информации см. Fleischer [3].
Изменение объема является одним из факторов остановки алгоритма. Для получения дополнительной информации смотрите Условия остановки. |
| Расстояние | Расстояние является мерой близости индивидуума к ближайшим соседям. Алгоритм устанавливает расстояние индивидуумов в крайних положениях на
Алгоритм сортирует каждую размерность отдельно, поэтому термин neighbors означает соседей в каждой размерности. Индивидуумы того же ранга с более высоким расстоянием имеют более высокие шансы на отбор (более высокое расстояние лучше). Расстояние является одним из факторов при вычислении спреда, который является частью критерия остановки. Для получения дополнительной информации смотрите Условия остановки. |
| Распространение | Спред является мерой движения набора Парето. Чтобы вычислить спред,
Разброс невелик, когда значения экстремальной целевой функции не сильно изменяются между итерациями (то есть μ мала) и когда точки на фронте Парето распределены равномерно (то есть σ мала).
|
ParetoSetChangeTolerance | Условие остановки поиска. paretosearch останавливается, когда объем, разброс или расстояние не изменяются более чем на ParetoSetChangeTolerance в окне итераций. Для получения дополнительной информации смотрите Условия остановки. |
MinPollFraction | Минимальная доля местоположений для опроса во время итерации. Эта опция не применяется, когда |
Эскиз paretosearch Алгоритм
Инициализация поиска
Чтобы создать начальный набор точек, paretosearch генерирует options.ParetoSetSize точки из квазирандомной выборки, основанные на границах задачи, по умолчанию. Для получения дополнительной информации смотрите Bratley и Fox [2]. Когда задача имеет более 500 размерности, paretosearch использует латинскую выборку гиперкуба, чтобы сгенерировать начальные точки.
Если у компонента нет границ, paretosearch использует искусственную нижнюю границу -10 и искусственная верхняя граница 10.
Если компонент имеет только одну границу, paretosearch использует привязку в качестве конечной точки интервала ширины 20 + 2*abs(bound). Например, если нет верхней границы для компонента и существует нижняя граница 15, paretosearch использует ширину интервала 20 + 2 * 15 = 55, поэтому использует искусственную верхнюю границу 15 + 55 = 70.
Если вы передаете некоторые начальные точки в options.InitialPoints, затем paretosearch использует эти точки в качестве начальных точек. paretosearch генерирует больше точек, если необходимо, чтобы получить, по крайней мере options.ParetoSetSize начальные точки.
paretosearch затем проверяет начальные точки, чтобы убедиться, что они допустимы относительно границ и линейных ограничений. При необходимости, paretosearch проецирует начальные точки на линейный подпространство линейно допустимых точек путем решения задачи линейного программирования. Этот процесс может привести к совпадению некоторых точек, в этом случае paretosearch удаляет все повторяющиеся точки. paretosearch не изменяет начальные точки для искусственных границ, только для заданных границ и линейных ограничений.
После перемещения точек, чтобы удовлетворить линейным ограничениям, при необходимости, paretosearch проверяет, удовлетворяют ли точки нелинейным ограничениям. paretosearch дает значение штрафа Inf в любую точку, которая не удовлетворяет всем нелинейным ограничениям. Тогда paretosearch вычисляет все отсутствующие значения целевой функции для остальных допустимых точек.
Примечание
В настоящее время, paretosearch не поддерживает нелинейные ограничения равенства ceq(x) = 0.
Создание архива и заполнения
paretosearch поддерживает два набора точек:
archive- структура, содержащая недоминированные точки, сопоставленные с размером сетки нижеoptions.MeshToleranceи удовлетворение всех ограничений внутриoptions.ConstraintTolerance. Thearchiveструктура содержит не более2*options.ParetoSetSizeТочки и первоначально пуста. Каждая точка вarchiveсодержит связанный размер сетки, который является размером сетки, при котором была сгенерирована точка.iterates- структура, содержащая недоминированные точки и, возможно, некоторые доминирующие точки, связанные с большими размерами сетки или недопустимостью. Каждая точка вiteratesсодержит связанный размер сетки.iteratesсодержит не болееoptions.ParetoSetSizeточки.
Опрос, чтобы найти лучшие точки
paretosearch опрашивает точки из iterates, с опрашиваемыми точками, наследующими связанный размер сетки от точки в iterates. paretosearch алгоритм использует опрос, который поддерживает допустимость относительно границ и всех линейных ограничений.
Если задача имеет нелинейные ограничения, paretosearch вычисляет допустимость каждой точки опроса. paretosearch сохраняет счет недопустимых точек отдельно от счета допустимых точек. Счет допустимой точки является вектором значений целевой функции этой точки. Счет недопустимой точки является суммой нелинейных infeasibilities.
paretosearch опросы по крайней мере MinPollFraction* (число точек в шаблоне) местоположения для каждой точки в iterates. Если опрашиваемые точки дают хотя бы одну недоминированную точку относительно действующей (исходной) точки, опрос считается успешным. В противном случае, paretosearch продолжает опрашивать, пока либо не найдет недоминированную точку, либо не иссякнет точки в шаблоне. Если paretosearch истекает количество точек и не дает недоминированной точки, paretosearch объявляет опрос неудачным и уменьшает размер сетки вдвое.
Если опрос находит недоминированные точки, paretosearch неоднократно расширяет опрос в успешных направлениях, удваивая размер сетки каждый раз, пока расширение не создает доминирующую точку. Во время этого расширения, если размер сетки превышает options.MaxMeshSize (значение по умолчанию: Inf), опрос останавливается. Если значения целевой функции уменьшаются до -Inf, paretosearch объявляет задачу неограниченной и останавливается.
Обновление archive и iterates Структуры
После опроса всех точек в iteratesалгоритм исследует новые точки вместе с точками в iterates и archive структуры. paretosearch вычисляет ранг, или передний номер Парето, каждой точки и затем делает следующее.
Отметьте для удаления все точки, которые не имеют ранга 1 в
archive.Отметьте новый ранг
1точки для вставки вiterates.Отметьте допустимые точки в
iteratesразмер сопоставленной сетки меньшеoptions.MeshToleranceдля перевода вarchive.Отметьте доминирующие точки в
iteratesдля удаления, только если они препятствуют добавлению новых недоминированных точек кiterates.
paretosearch затем вычисляет измерения объема и расстояния для каждой точки. Если archive переполнение в результате включения отмеченных точек, затем точки с наибольшим объемом занимают archiveа остальные уходят. Точно так же новые точки отмечены для сложения к iterates введите iterates в порядке их объёмов.
Если iterates полно и не имеет доминирующих точек, тогда paretosearch не добавляет никаких точек к iterates и объявляет итерацию неудачной. paretosearch умножает размеры сетки в iterates по 1/2.
Условия остановки
Для трех или менее целевых функций, paretosearch использует объем и спред как меры остановки. Для четырех или более целей, paretosearch использует расстояние и разброс как меры остановки. В оставшейся части этого обсуждения эти две меры paretosearch использование обозначают applicable меры.
Алгоритм поддерживает векторы последних восьми значений применимых мер. После восьми итераций алгоритм проверяет значения двух применимых мер в начале каждой итерации, где tol = options.ParetoSetChangeTolerance:
spreadConverged = abs(spread(end - 1) - spread(end)) <= tol*max(1,spread(end - 1));volumeConverged = abs(volume(end - 1) - volume(end)) <= tol*max(1,volume(end - 1));distanceConverged = abs(distance(end - 1) - distance(end)) <= tol*max(1,distance(end - 1));
Если любой из применимых тестов trueалгоритм останавливается. В противном случае алгоритм вычисляет макс квадратов членов преобразований Фурье применимых мер минус первый член. Затем алгоритм сравнивает максимумы с их удаленными терминами (DC- компонентов преобразований). Если любой удаленный термин больше 100*tol*(max of all other terms), затем алгоритм останавливается. Этот тест по существу определяет, что последовательность измерений не колеблется, и, следовательно, сходится.
Кроме того, функция построения графика или выходная функция могут остановить алгоритм, или алгоритм может остановиться, потому что он превышает предел времени или вычисления функции.
Возвращенные значения
Алгоритм возвращает точки на фронте Парето следующим образом.
paretosearchобъединяет точки вarchiveиiteratesв один набор.Когда существует три или меньше целевых функций,
paretosearchвозвращает точки от наибольшего объема до наименьшего, максимумParetoSetSizeточки.Когда существует четыре или более целевых функций,
paretosearchвозвращает точки с самого большого расстояния на самое маленькое, максимум доParetoSetSizeточки.
Изменения для параллельных Расчетов и векторизированных Вычислений функции
Когда paretosearch вычисляет значения целевой функции параллельно или векторизированно (UseParallel является true или UseVectorized является true), существуют некоторые изменения в алгоритме.
Когда
UseVectorizedявляетсяtrue,paretosearchигнорируетMinPollFractionОпция и оценивает все точки опроса в шаблоне.При параллельных вычислениях,
paretosearchпоследовательно исследует каждую точку вiteratesи выполняет параллельный опрос из каждой точки. После возвращенияMinPollFractionдоля точек опроса,paretosearchопределяет, доминируют ли какие-либо точки опроса в базовой точке. Если это так, опрос считается успешным, и любые другие параллельные оценки прекращаются. Если нет, опрос продолжается до тех пор, пока не появится доминирующая точка или не будет выполнен опрос.paretosearchвыполняет объективные вычисления функции либо на рабочих, либо векторизованным образом, но не на обоих. Если вы оба задаетеUseParallelиUseVectorizedнаtrue,paretosearchвычисляет значения целевой функции параллельно для рабочих, но не векторизованным образом. В этом случае,paretosearchигнорируетMinPollFractionОпция и оценивает все точки опроса в шаблоне.
Выполняйте paretosearch Быстро
Самый быстрый способ запустить paretosearch зависит от нескольких факторов.
Если вычисления целевой функции выполняются медленно, то обычно быстрее всего использовать параллельные вычисления. Накладные расходы в параллельных вычислениях могут быть значительными, когда вычисления целевой функции быстрые, но когда они медленные, обычно лучше всего использовать больше вычислительную степень.
Примечание
Для параллельных вычислений требуется лицензия Parallel Computing Toolbox™.
Если вычисления целевой функции не очень длительны, то обычно быстрее всего использовать векторизованную оценку. Однако это не всегда так, потому что векторизованные расчеты оценивают весь шаблон, в то время как последовательные вычисления могут взять лишь небольшую часть шаблона. В высоких размерностях, особенно, это сокращение оценок может привести к тому, что последовательная оценка будет быстрее для некоторых проблем.
Чтобы использовать векторизованные вычисления, ваша целевая функция должна принять матрицу с произвольным количеством строк. Каждая строка представляет одну точку для вычисления. Целевая функция должна вернуть матрицу значений целевой функции с одинаковым числом строк, как она принимает, с одним столбцом для каждой целевой функции. Для одноцелевого обсуждения см. «Векторизация функции соответствия» (
ga) или векторизованная целевая функция (patternsearch).
Ссылки
[1] Кустидио, А. Л., Ж. Ф. А. Мадейра, А. И. Ф. Ваз, и Л. Н. Висенте. Прямая мультисемя для мультибъективной оптимизации. SIAM J. Optim., 21 (3), 2011, pp. 1109-1140. Препринт, доступный в https://estudogeral.sib.uc.pt/bitstream/10316/13698/1/Direct%20multisearch%20for%20multiobjective%20optimization.pdf.
[2] Брэтли, П. и Б. Л. Фокс. Алгоритм 659: Реализация генератора квазирандомной последовательности Соболь. ACM Trans. Math. Software 14, 1988, pp. 88-100.
[3] Fleischer, M. Measure of Pareto Optima: Applications to Multi-Objective Metaheuristics. В «Трудах второй Международной конференции по эволюционной мульти-критерий оптимизации - EMO» апрель 2003 года в Фару, Португалия. Опубликовано Springer-Verlag в серии Lecture Notes in Computer Science, Vol. 2632, pp. 519-533. Препринт, доступный в https://apps.dtic.mil/dtic/tr/fulltext/u2/a441037.pdf.