Как работают GlobalSearch и MultiStart

Несколько запуски локального решателя

GlobalSearch и MultiStart имеют аналогичные подходы к нахождению глобальных или нескольких минимумов. Оба алгоритма запускают локальный решатель (такой как fmincon) из нескольких начальных точек. Алгоритмы используют несколько начальных точек, чтобы дискретизировать несколько областей притяжения. Для получения дополнительной информации смотрите Области притяжения.

Различия между Решателем Объектов

Обзор алгоритмов GlobalSearch и MultiStart содержит эскиз GlobalSearch и MultiStart алгоритмы.

Обзор алгоритмов GlobalSearch и MultiStart

Основные различия между GlobalSearch и MultiStart являются:

  • GlobalSearch использует механизм поиска рассеяния для генерации начальных точек. MultiStart использует равномерно распределенные начальные точки в границах или предоставленные пользователем стартовые точки.

  • GlobalSearch анализирует стартовые точки и отвергает те точки, которые вряд ли улучшат лучший локальный минимум, найденный до сих пор. MultiStart запуски всех начальных точек (или, опционально, всех начальных точек, которые допустимы относительно границ или ограничений неравенства).

  • MultiStart дает выбор локального решателя: fmincon, fminunc, lsqcurvefit, или lsqnonlin. The GlobalSearch алгоритм использует fmincon.

  • MultiStart может работать параллельно, распределяя стартовые точки на несколько процессоров для локального решения. Чтобы запустить MultiStart параллельно см. раздел «Как использовать параллельную обработку в Global Optimization Toolbox».

Решение, какой решатель использовать

Различия между этими объектами решателя сводятся к следующему решению, на котором использовать:

  • Использование GlobalSearch наиболее эффективно найти один глобальный минимум на одном процессоре.

  • Использование MultiStart кому:

    • Найдите несколько локальных минимумов.

    • Прокрутка параллельно.

    • Используйте решатель кроме fmincon.

    • Тщательно ищите глобальный минимум.

    • Исследуйте свои собственные стартовые точки.

Алгоритм GlobalSearch

Описание алгоритма см. в Ugrey et al. [1].

Когда вы run a GlobalSearch объект, алгоритм выполняет следующие шаги:

Запуск fmincon из x0

GlobalSearch запуски fmincon от начальной точки вы даете в problem структура. Если этот запуск сходится, GlobalSearch записывает начальную и конечную точки для начальной оценки по радиусу области притяжения. Кроме того, GlobalSearch записывает окончательное значение целевой функции для использования в функции score (см. «Получение начальной точки этапа 1», «Запуск»).

Функция счета является суммой значения целевой функции в точке и кратной сумме нарушений ограничений. Таким образом, допустимая точка имеет счет, равную ее значению целевой функции. Множественное значение для нарушений ограничений первоначально составляет 1000. GlobalSearch обновляет несколько во время запуска.

Сгенерируйте пробные точки

GlobalSearch использует алгоритм поиска рассеяния, чтобы сгенерировать набор NumTrialPoints пробные точки. Пробные точки являются потенциальными стартовыми точками. Описание алгоритма поиска рассеяния смотрите в Glover [2]. GlobalSearch генерирует пробные точки в любых конечных границах, которые вы задаете (lb и ub). Неограниченные компоненты имеют искусственные ограничения:   lb = -1e4 + 1,   ub = 1e4 + 1. Эта область значений не симметрична относительно источник, так что источник не находится в поиске рассеяния. Компоненты с односторонними границами имеют искусственные ограничения, накладываемые на неограниченную сторону, смещенные конечными границами, чтобы сохранить   lb < ub.

Получите стартовую точку 1 этапа, выполните

GlobalSearch оценивает функцию счета набора NumStageOnePoints пробные точки. Затем он принимает точку с лучшим счетом и бежит fmincon с этой точки. GlobalSearch удаляет набор NumStageOnePoints пробные точки из его списка пунктов для рассмотрения.

Инициализируйте умывальные раковины, счетчики, порог

The localSolverThreshold первоначально является меньшим из двух значений целевой функции в точках решения. Точками решения являются fmincon решения, начиная с x0 и от начальной точки этапа 1. Если обе эти точки решения не существуют или являются недопустимыми, localSolverThreshold первоначально является значением функции штрафа начальной точки этапа 1.

The GlobalSearch эвристическое предположение, что области притяжения являются сферическими. Начальная оценка областей притяжения для точки решения от x0 и точка решения от Стадии 1 являются сферами с центром в точках решения. Радиус каждой сферы является расстоянием от начальной точки до точки решения. Эти предполагаемые умывальные раковины могут перекрываться.

Существует два набора счетчиков, сопоставленных с алгоритмом. Каждый счетчик является количеством последовательных пробных точек, которые:

  • Лежать в области притяжения. Для каждой умывальной раковины имеется по одному счетчику.

  • Иметь функцию счета больше localSolverThreshold. Определение счета см. в разделе Запуск fmincon из x0.

Сначала все счетчики равны 0.

Начальный основной цикл

GlobalSearch неоднократно исследует оставшуюся пробную точку из списка и выполняет следующие шаги. Он постоянно отслеживает время и останавливает поиск, если прошедшее время превышает MaxTime секунд.

Исследуйте пробную точку 2 этапа, чтобы увидеть, работает ли fmincon

Вызовите пробную точку p. Управляемый fmincon от p если соблюдаются следующие условия:

  • p не находится ни в одном существующей умывальной раковине. Критерий для каждой умывальной раковины i является:

    |p - center(i)| > DistanceThresholdFactor * radius(i).

    DistanceThresholdFactor является опцией (значение по умолчанию 0.75).

    radius - предполагаемый радиус, который обновляется в Update Basin Radius и порог и реагирует на большие значения счетчика.

  • счет (p) <localSolverThreshold.

  • (необязательно) p удовлетворяет связанным и/или ограничениям неравенства. Этот тест происходит, если вы устанавливаете StartPointsToRun свойство GlobalSearch объект к 'bounds' или 'bounds-ineqs'.

Когда fmincon запускается

  1. Счетчики сброса

    Установите счетчики для умывальных раковин и порога равными 0.

  2. Обновление набора решений

    Если fmincon выполняется начиная с p, это может привести к положительному выходному флагу, который указывает на сходимость. В этом случае GlobalSearch обновляет вектор GlobalOptimSolution объекты. Вызовите точку решения xp и значение целевой функции fp. Существует два случая:

    • Для каждой другой точки решения xq со значением целевой функции fq,

      |xq - xp| > XTolerance * max(1,|xp|)

      или

      |fq - fp| > FunctionTolerance * max(1,|fp|).

      В этом случае GlobalSearch создает новый элемент в векторе GlobalOptimSolution объекты. Для получения дополнительной информации, содержащейся в каждом объекте, смотрите GlobalOptimSolution.

    • Для некоторых других xq точек решения со значением целевой функции fq,

      |xq - xp| <= XTolerance * max(1,|xp|)

      и

      |fq - fp| <= FunctionTolerance * max(1,|fp|).

      В этом случае GlobalSearch с уважением xp как эквивалентный xq. The GlobalSearch алгоритм изменяет GlobalOptimSolution от xq путем добавления p в массив ячеек X0 точки.

      Существует одна незначительная подстройка, которая может произойти с этим обновлением. Если выходной флаг для xq больше 1, и выходной флаг для xp является 1, затем xp заменяет xq. Эта замена может привести к тому, что некоторые точки в той же умывальной раковине будут больше, чем расстояние XTolerance от xp.

  3. Обновление радиуса умывальной раковины и порога

    Если выходной флаг тока fmincon прогон положительный:

    1. Установите пороговое значение баллов балла в начальной точке p.

    2. Установите радиус умывальной раковины для xp равен максимуму существующего радиуса (если он имеется) и расстоянию между p и xp.

  4. Отчет для итерационного отображения

    Когда GlobalSearch Display свойство 'iter', каждая точка, который fmincon запуски создает одну линию в GlobalSearch итеративное отображение.

Когда fmincon не запускается

  1. Счетчики обновлений

    Увеличьте счетчик для каждой умывальной раковины, содержащей p. Сбросьте счетчик каждой другой умывальной раковины в 0.

    Увеличьте пороговый счетчик, если счет (p) > = localSolverThreshold. В противном случае сбросьте счетчик на 0.

  2. Реакция на большие значения счетчика

    Для каждой умывальной раковины с счетчиком, равным MaxWaitCycle, умножить радиус умывальной раковины на 1 – BasinRadiusFactor. Сбросьте счетчик в 0. (Оба MaxWaitCycle и BasinRadiusFactor являются установившимися свойствами GlobalSearch объект.)

    Если пороговый счетчик равен MaxWaitCycle, увеличить порог:

    новый порог = порог + PenaltyThresholdFactor* (1 + abs (порог)).

    Сбросьте счетчик в 0.

  3. Отчет для итерационного отображения

    Каждая 200-я пробная точка создает одну линию в GlobalSearch итеративное отображение.

Создайте GlobalOptimSolution

После достижения MaxTime секунд или истечения пробных точек, GlobalSearch создает вектор GlobalOptimSolution объекты. GlobalSearch упорядочивает вектор по значению целевой функции от самого низкого (лучший) до самого высокого (худший). На этом алгоритм завершается.

Алгоритм MultiStart

Когда вы run a MultiStart объект, алгоритм выполняет следующие шаги:

Валидация входных параметров

MultiStart проверяет входные аргументы для валидности. Проверки включают запуск локального решателя один раз на входах задачи. Даже при параллельном запуске MultiStart выполняет эти проверки последовательно.

Сгенерируйте начальные точки

Если вы звоните MultiStart с синтаксисом

[x,fval] = run(ms,problem,k)

для целого числа k, MultiStart генерирует   k - 1 стартовые точки точно так же, как если бы вы использовали RandomStartPointSet объект. Алгоритм также использует x0 начальная точка от problem структура, на общую сумму k начальные точки.

A RandomStartPointSet объект не имеет точек, сохраненных внутри объекта. Вместо этого MultiStart вызовы list, который генерирует случайные точки в границах, заданных problem структура. Если существует неограниченный компонент, list использует искусственную границу, заданную ArtificialBound свойство RandomStartPointSet объект.

Если вы предоставляете CustomStartPointSet объект, MultiStart не генерирует начальные точки, но использует точки в объекте.

Фильтрация начальных точек (необязательно)

Если вы задаете StartPointsToRun свойство MultiStart объект к 'bounds' или 'bounds-ineqs', MultiStart не запускает локальный решатель из недопустимых начальных точек. В этом контексте «недопустимые» означают стартовые точки, которые не удовлетворяют границам, или стартовые точки, которые не удовлетворяют и границам, и ограничениям неравенства.

Настройка по умолчанию StartPointsToRun является 'all'. В этом случае MultiStart не отбрасывает недопустимые начальные точки.

Запуск локального решателя

MultiStart запускает локальный решатель, указанный в problem.solver, начиная с точек, которые проходят StartPointsToRun фильтр. Если MultiStart работает параллельно, отправляет начальные точки рабочим процессорам по одному, а рабочие процессоры запускают локальный решатель.

Локальный решатель проверяет, MaxTime ли секунды прошли в каждой из его итераций. Если это так, он выходит из этой итерации, не сообщая о решении.

Когда локальный решатель останавливается, MultiStart сохраняет результаты и переходит к следующему шагу.

Отчет по итерационному отображению.  Когда MultiStart Display свойство 'iter'каждая точка, которую запускает локальный решатель, создает одну линию в MultiStart итеративное отображение.

Проверяйте условия остановки

MultiStart останавливается, когда заканчиваются начальные точки. Он также останавливается, когда превышает общее время запуска MaxTime секунд.

Создайте объект GlobalOptimSolution

После MultiStart достигает условия остановки, алгоритм создает вектор GlobalOptimSolution объекты следующим образом:

  1. Сортировка локальных решений по значению целевой функции (Fval) от самого низкого до самого высокого. Для lsqnonlin и lsqcurvefit локальные решатели, целевой функцией является норма невязки.

  2. Закольцовывайте локальные решения j начиная с самого низкого (лучшего) Fval.

  3. Найти все решения k удовлетворяющие обоим:

        |Fval(k) - Fval(j)| <= FunctionTolerance*max(1,|Fval(j)|)

        |x(k) - x(j)| <= XTolerance*max(1,|x(j)|)

  4. Запись j, Fval(j), локальный решатель output структура для j, и массив ячеек начальных точек для j и все k. Удалите эти точки k из списка локальных решений. Эта точка является одной записью в векторе GlobalOptimSolution объекты.

Получившийся вектор GlobalOptimSolution объекты в порядке по Fval, от самого низкого (лучшего) до самого высокого (худшего).

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

Библиография

[1] Угрей, Жолт, Леон Ласдон, Джон К. Пламмер, Фред Гловер, Джеймс Келли и Рафаэль Марти. Рассеяние и локальные решатели NLP: мультистартовая среда для глобальной оптимизации. Журнал ИНФОРМС по вычислению, том 19, № 3, 2007, стр. 328-340.

[2] Glover, F. «A шаблона for scatter search and пути relinking». Искусственная эволюция (Ж.-К. Hao, E.Lutton, E. Ronald, M.Schoenauer, D.Snyers, eds.). Лекции по информатике, 1363, Спрингер, Берлин/Гейдельберг, 1998, стр. 13-54.

[3] Диксон, Л. и Г. П. Сегё. «Глобальная задача оптимизации: введение». К глобальной оптимизации 2 (Dixon, L.C. W. and G.P. Szeg, eds.). Амстердам, Нидерланды: Северная Голландия, 1978.

Похожие темы

Документация Global Optimization Toolbox

Поддержка

Для просмотра документации необходимо авторизоваться на сайте