paretosearch Алгоритмparetosearch Обзор алгоритма paretosearch алгоритм использует поиск шаблона по набору точек для итеративного поиска недоминированных точек. См. раздел Многообъективная терминология. Поиск массива удовлетворяет всем границам и линейным ограничениям в каждой итерации.
Теоретически алгоритм сходится к точкам вблизи истинного фронта Парето. Для обсуждения и доказательства сходимости см. Custâdio et al. [1], доказательство которого относится к проблемам с непрерывными целями и ограничениями Липшица.
paretosearch Алгоритмparetosearch использует в своем алгоритме ряд промежуточных величин и допусков.
| Количество | Определение |
|---|---|
| Разряд | Ранг точки имеет итеративное определение.
|
| Объем | Гиперобъём множества точек p в пространстве целевой функции, удовлетворяющих неравенству, для каждого индекса j, fi (j) < pi < Mi, где fi (j) - i-й компонент значения j-й целевой функции в наборе Парето, а Mi - верхняя граница для i-го компонента для всех точек в наборе Парето. На этом рисунке M называется опорной точкой. Оттенки серого на рисунке обозначают части объема, которые некоторые алгоритмы вычисления используют как часть вычисления включения-исключения.
Дополнительные сведения см. в разделе Fleischer [3].
Изменение громкости является одним из факторов остановки алгоритма. Дополнительные сведения см. в разделе Условия остановки. |
| Расстояние | Расстояние - это мера близости человека к ближайшим соседям. Алгоритм устанавливает расстояние отдельных лиц в крайних положениях на
Алгоритм сортирует каждое измерение по отдельности, поэтому термин «соседи» означает соседей в каждом измерении. Особи одного ранга с более высокой дистанцией имеют более высокие шансы на отбор (более высокая дистанция лучше). Расстояние является одним из факторов при расчете разброса, который является частью критерия остановки. Дополнительные сведения см. в разделе Условия остановки. |
| Распространение | Спред - мера движения множества Парето. Чтобы вычислить спред,
Разброс мал, когда значения предельной целевой функции мало меняются между итерациями (то есть λ мал) и когда точки на фронте Парето разбросаны равномерно (то есть λ мал).
|
ParetoSetChangeTolerance | Условие остановки поиска. paretosearch останавливается, когда объем, разброс или расстояние не изменяются более чем на ParetoSetChangeTolerance над окном итераций. Дополнительные сведения см. в разделе Условия остановки. |
MinPollFraction | Минимальная доля расположений для опроса во время итерации. Этот параметр не применяется, когда |
paretosearch Алгоритм
Чтобы создать начальный набор точек, paretosearch производит options.ParetoSetSize точки из квазирандомной выборки, основанной на границах задачи, по умолчанию. Подробнее см. Bratley and 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. archive структура содержит не более 2*options.ParetoSetSize точки и изначально пусты. Каждая точка в archive содержит связанный размер сетки, который представляет собой размер сетки, в котором была создана точка.
iterates - Структура, содержащая недоминированные точки и, возможно, некоторые доминирующие точки, связанные с большими размерами сетки или несходимостью. Каждая точка в iterates содержит связанный размер сетки. iterates содержит не более options.ParetoSetSize точки.
paretosearch опросы очки от iterates, при этом опрошенные точки наследуют связанный размер сетки от точки в iterates. paretosearch алгоритм использует опрос, который поддерживает выполнимость относительно границ и всех линейных ограничений.
Если проблема имеет нелинейные ограничения, paretosearch вычисляет выполнимость каждой точки опроса. paretosearch сохраняет оценку неосуществимых баллов отдельно от оценки возможных баллов. Оценка возможной точки является вектором значений целевой функции этой точки. Оценка неосуществимой точки - это сумма нелинейных несходимостей.
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 виды использования обозначаются применимыми мерами.
Алгоритм поддерживает векторы последних восьми значений применимых мер. После восьми итераций алгоритм проверяет значения двух применимых мер в начале каждой итерации, где 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, стр. 1109-1140. Препринт доступен по адресу https://estudogeral.sib.uc.pt/bitstream/10316/13698/1/Direct%20multisearch%20for%20multiobjective%20optimization.pdf.
[2] Bratley, P. и Б. Л. Фокс. Алгоритм 659: Реализация генератора квазирандомных последовательностей Соболя. ACM Trans. Math. Software 14, 1988, стр. 88-100.
[3] Флейшер, М. Мера Парето Оптима: Применение к многообъектной метаэуристике. В «Трудах второй Международной конференции по эволюционной многомерной оптимизации - EMO» апрель 2003 года в Фару, Португалия. Опубликовано Springer-Verlag в серии «Lecture Notes in Computer Science», т. 2632, стр. 519-533. Препринт доступен по адресу https://apps.dtic.mil/dtic/tr/fulltext/u2/a441037.pdf.