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

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

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

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

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

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

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

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

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

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

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

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

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

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

  • Используйте MultiStart к:

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

    • RunInParallel.

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

    • Поиск полностью глобального минимума.

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

Алгоритм GlobalSearch

Для описания алгоритма смотрите Ugray и др. [1].

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

Запустите fmincon от x0

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

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

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

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

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

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

Инициализируйте области, счетчики, порог

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

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 предполагаемый радиус, который обновляется в Радиусе Области с Обновлением и Пороге, и Реагируйте на Большие Встречные Значения.

  • счет (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. GlobalSearch алгоритм изменяет GlobalOptimSolution из xq путем добавления p к массиву ячеек X0 'points'.

      Существует одна незначительная тонкая настройка, которая может произойти с этим обновлением. Если выходной флаг для 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 MultiStart объект, алгоритм выполняет следующие шаги:

Проверка вводов

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

Сгенерируйте стартовые точки

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

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

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

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] Ugray, Zsolt, Леон Лэсдон, Джон К. Пламмер, Фред Гловер, Джеймс Келли и Рафаэль Марти. Рассейте Поиск и Локальные Решатели NLP: A Мультизапускают Среду для Глобальной Оптимизации. Журнал INFORMS на Вычислении, Издании 19, № 3, 2007, стр 328–340.

[2] Перчаточник, F. “Шаблон для поля точек поиска и пересоединения пути”. Искусственная Эволюция (J.-K. Хао, E.Lutton, E.Ronald, M.Schoenauer, D.Snyers, редакторы). Читайте лекции Примечаниям в Информатике, 1363, Спрингер, Берлине/Гейдельберге, 1998, стр 13–54.

[3] Диксон, L. и Г. П. Сзеге. “Глобальная Задача оптимизации: Введение”. К Глобальной Оптимизации 2 (Диксон, L. C. W. и Г. П. Сзеге, редакторы). Амстердам, Нидерланды: Северная Голландия, 1978.

Похожие темы

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

Поддержка

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