Ветвь и граница ( BB , B&B или BnB ) - это парадигма разработки алгоритмов для задач дискретной и комбинаторной оптимизации , а также математической оптимизации . Алгоритм ветвей и границ состоит из систематического перечисления возможных решений посредством поиска в пространстве состояний : набор возможных решений рассматривается как образующий корневое дерево с полным набором в корне. Алгоритм исследует веткиэтого дерева, которые представляют собой подмножества множества решений. Прежде чем перечислять кандидатских решения филиала, филиал сверяется верхней и нижней сметные оценки по оптимальному решению, и отбрасывается , если он не может производить лучшее решение , чем лучшие из найденных до сих пор по алгоритму.
Алгоритм зависит от эффективной оценки нижней и верхней границ областей / ветвей пространства поиска. Если границы недоступны, алгоритм переходит к исчерпывающему поиску.
Этот метод был впервые предложен Айлз землей и Alison Doig в то время как проведение исследований в Лондонской школе экономики при поддержке British Petroleum в 1960 году для дискретного программирования , [1] [2] и стал наиболее часто используемым инструментом для решения NP-трудным проблемы оптимизации. [3] Название «ветвь и граница» впервые появилось в работе Литтла и др. по задаче коммивояжера . [4] [5]
Обзор
Цель алгоритма ветвей и границ - найти значение x, которое максимизирует или минимизирует значение действительной функции f ( x ) , называемой целевой функцией, среди некоторого множества S допустимых или возможных решений . Множество S называется пространством поиска или допустимой областью . В остальной части этого раздела предполагается, что желательна минимизация f ( x ) ; это предположение делается без ограничения общности , так как максимальное значение f ( x ) можно найти, найдя минимум g ( x ) = - f ( x ) . Алгоритм B&B работает по двум принципам:
- Он рекурсивно разбивает пространство поиска на меньшие пространства, а затем минимизирует f ( x ) на этих меньших пространствах; расщепление называется ветвлением .
- Само по себе ветвление означало бы перебор всех возможных решений методом перебора и их всех. Чтобы повысить производительность поиска методом перебора, алгоритм B&B отслеживает границы минимума, который он пытается найти, и использует эти границы для « сокращения » пространства поиска, исключая возможные решения, которые, как он может доказать, не будут содержать оптимальное решение.
Превращение этих принципов в конкретный алгоритм для конкретной задачи оптимизации требует некоторой структуры данных , представляющей наборы возможных решений. Такое представление называется экземпляром проблемы. Обозначим множество вариантов решения экземпляра I по S I . Экземплярное представление должно сопровождаться тремя операциями:
- ветвь ( я ) производит два или более экземпляров , что каждый представляет собой подмножество S I . (Обычно подмножества не пересекаются, чтобы алгоритм не мог дважды посетить одно и то же решение-кандидат, но это не требуется. Однако оптимальное решение среди S I должно содержаться по крайней мере в одном из подмножеств. [6] )
- связанным ( я ) вычисляет нижнюю границу стоимости любого кандидата раствора в пространстве , представленном I , то есть, связанного ( я ) ≤ F ( х ) для всех х в S I .
- Решение ( I ) определяет, представляю ли я единственное возможное решение. (Необязательно, если это не так, то операция может выбрать , чтобы вернуть некоторое допустимое решение из числа S I . [6] ) Если решение ( я ) возвращает решение , то F (раствор ( I )) обеспечивает верхнюю границу для целей оптимального значение по всему пространству возможных решений.
Используя эти операции, алгоритм B&B выполняет рекурсивный поиск сверху вниз по дереву экземпляров, сформированному операцией ветвления. При посещении экземпляра I он проверяет, больше ли граница ( I ), чем найденная на данный момент верхняя граница; в таком случае меня можно безопасно исключить из поиска, и рекурсия прекратится. Этот шаг сокращения обычно реализуется путем поддержания глобальной переменной, которая записывает минимальную верхнюю границу, наблюдаемую среди всех экземпляров, исследованных до сих пор.
Общая версия
Ниже приведен скелет общего алгоритма ветвей и границ для минимизации произвольной целевой функции f . [3] Чтобы получить из этого фактический алгоритм, требуется граница функции , которая вычисляет нижние границы f на узлах дерева поиска, а также правило ветвления для конкретной задачи. Таким образом, общий алгоритм, представленный здесь, является функцией более высокого порядка .
- Используя эвристику , найдите решение x h задачи оптимизации. Сохраните его значение, B = f ( x h ) . (Если эвристика недоступна, установите B на бесконечность.) B будет обозначать лучшее решение, найденное на данный момент, и будет использоваться в качестве верхней границы для возможных решений.
- Инициализируйте очередь, чтобы сохранить частичное решение без присвоения ни одной из переменных задачи.
- Цикл, пока очередь не станет пустой:
- Убрать узел N из очереди.
- Если N представляет собой единственное возможное решение x и f ( x ) < B , то x - лучшее решение на данный момент. Запишите его и положите B ← f ( x ) .
- В противном случае, филиал на N для создания новых узлов N I . Для каждого из них:
- Если bound ( N i )> B , ничего не делать; поскольку нижняя граница этого узла больше верхней границы проблемы, она никогда не приведет к оптимальному решению и может быть отброшена.
- В противном случае сохраните N i в очереди.
Можно использовать несколько различных структур данных очереди . Эта реализация на основе очереди FIFO дает поиск в ширину . Стека (очереди LIFO) даст глубину первого алгоритма. Лучше всего первые ветви и границ могут быть получены с использованием очереди приоритета , который сортирует узлы на их нижней границе. [3] Примерами алгоритмов поиска лучшего первого с этой предпосылкой являются алгоритм Дейкстры и его потомок A * search . Вариант в глубину рекомендуется, когда нет хорошей эвристики для получения начального решения, потому что он быстро дает полные решения и, следовательно, верхние границы. [7]
Псевдокод
A C ++ -как реализации псевдокода вышеперечисленного:
// C ++ - подобная реализация ветвления и привязки, // предполагая, что целевая функция f должна быть минимизированаКомбинаторное решение branch_and_bound_solve ( Комбинаторная проблема , ObjectiveFunction objective_function / * f * / , BoundingFunction lower_bound_function / * граница * / ) { // Шаг 1 выше double problem_upper_bound = std :: numeric_limits < двойной > :: бесконечность ; // = B CombinatorialSolution heuristic_solution = heuristic_solve ( проблема ); // x_h problem_upper_bound = objective_function ( heuristic_solution ); // B = f (x_h) CombinatorialSolution current_optimum = эвристическое_решение ; // Шаг 2 выше queue < CandidateSolutionTree > кандидат_queue ; // инициализация очереди для конкретной проблемы Очередь кандидата = populate_candidates ( проблема ); while ( ! scheme_queue . empty ()) { // Шаг 3 выше // Шаг 3.1 Узел CandidateSolutionTree = очередь- кандидата . pop (); // "узел" представляет N выше если ( узел . represents_single_candidate ()) { // Шаг 3.2 if ( objective_function ( node . кандидата ()) < проблема_upper_bound ) { current_optimum = узел . кандидат (); problem_upper_bound = objective_function ( current_optimum ); } // иначе узел - единственный кандидат, который не является оптимальным } else { // Шаг 3.3: узел представляет собой ветвь возможных решений // "child_branch" представляет N_i выше для ( авто && child_branch : узел . candidate_nodes ) { if ( lower_bound_function ( child_branch ) <= проблема_upper_bound ) { кандидат_очередь . enqueue ( child_branch ); // Шаг 3.3.2 } // в противном случае, bound (N_i)> B, поэтому мы обрезаем ветку; шаг 3.3.1 } } } вернуть current_optimum ;}
В приведенном выше псевдокоде функции heuristic_solve
и populate_candidates
вызываемые как подпрограммы должны быть предоставлены в соответствии с проблемой. Функции f ( objective_function
) и bound ( lower_bound_function
) рассматриваются как записанные объекты функций и могут соответствовать лямбда-выражениям , указателям на функции или функторам на языке программирования C ++, среди других типов вызываемых объектов .
Улучшения
Когда вектор , алгоритмы ветвей и границ могут быть объединены с интервальным анализом [8] и методами подрядчика , чтобы обеспечить гарантированные вложения глобального минимума. [9] [10]
Приложения
Этот подход используется для ряда NP-сложных задач:
- Целочисленное программирование
- Нелинейное программирование
- Задача коммивояжера (TSP) [4] [11]
- Квадратичная задача о назначении (QAP)
- Задача максимальной выполнимости (MAX-SAT)
- Поиск ближайшего соседа [12] ( Кейносуке Фукунага )
- Планирование поточного цеха
- Проблема раскроя материала
- Вычислительная филогенетика
- Установить инверсию
- Оценка параметров
- 0/1 задача о ранце
- Установить проблему с обложкой
- Выбор функций в машинном обучении [13] [14]
- Структурированное предсказание в компьютерном зрении [15] : 267–276.
Branch-and-bound также может быть базой для различных эвристик . Например, кто-то может пожелать прекратить ветвление, когда разрыв между верхней и нижней границами становится меньше определенного порога. Это используется, когда решение «достаточно хорошо для практических целей» и может значительно сократить требуемые вычисления. Этот тип решения особенно применим, когда используемая функция стоимости является зашумленной или является результатом статистических оценок и поэтому не известна точно, а скорее всего лишь известно, что она находится в диапазоне значений с определенной вероятностью . [ необходима цитата ]
Отношение к другим алгоритмам
Nau et al. представляют собой обобщение ветвей и границ, которое также включает алгоритмы поиска A * , B * и альфа-бета . [16]
Смотрите также
- Возврат
- Branch-and-cut , гибрид между методами ветвей и границ и секущей плоскостью, который широко используется для решения целочисленных линейных программ .
Рекомендации
- Перейти ↑ AH Land и AG Doig (1960). «Автоматический метод решения задач дискретного программирования». Econometrica . 28 (3). С. 497–520. DOI : 10.2307 / 1910129 .
- ^ «Кадровые новости» . www.lse.ac.uk . Проверено 8 октября 2018 .
- ^ а б в Клаузен, Йенс (1999). Алгоритмы ветвей и границ - принципы и примеры (PDF) (Технический отчет). Копенгагенский университет . Архивировано из оригинального (PDF) 23 сентября 2015 года . Проверено 13 августа 2014 .
- ^ а б Литтл, Джон округ Колумбия; Murty, Katta G .; Суини, Дура У .; Карел, Кэролайн (1963). «Алгоритм задачи коммивояжера» (PDF) . Исследование операций . 11 (6): 972–989. DOI : 10.1287 / opre.11.6.972 . ЛВП : 1721,1 / 46828 .
- ^ Балас, Эгон; Тот, Паоло (1983). Методы ветвей и границ для задачи коммивояжера (PDF) (Отчет). Высшая школа промышленного администрирования Университета Карнеги-Меллона . Архивировано из оригинального (PDF) 20 октября 2012 года.
- ^ а б Бадер, Дэвид А .; Харт, Уильям Э .; Филлипс, Синтия А. (2004). «Разработка параллельных алгоритмов для ветвей и границ» (PDF) . В Гринберге, HJ (ред.). Учебники по новым методологиям и приложениям в исследовании операций . Kluwer Academic Press. Архивировано из оригинального (PDF) 13 августа 2017 года . Проверено 16 сентября 2015 .
- ^ Мельхорн, Курт ; Сандерс, Питер (2008). Алгоритмы и структуры данных: Basic Toolbox (PDF) . Springer. п. 249.
- ^ Мур, Р. Э. (1966). Интервальный анализ . Энглвуд Клифф, Нью-Джерси: Прентис-Холл. ISBN 0-13-476853-1.
- ^ Jaulin, L .; Kieffer, M .; Didrit, O .; Уолтер, Э. (2001). Прикладной интервальный анализ . Берлин: Springer. ISBN 1-85233-219-0.
- ^ Хансен, ER (1992). Глобальная оптимизация с использованием интервального анализа . Нью-Йорк: Марсель Деккер.
- ^ Конвей, Ричард Уолтер; Максвелл, Уильям Л .; Миллер, Луи В. (2003). Теория планирования . Courier Dover Publications. С. 56–61 .
- ^ Фукунага, Кейносуке; Нарендра, Патренахалли М. (1975). «Алгоритм ветвей и границ для вычисления k ближайших соседей». Транзакции IEEE на компьютерах : 750–753. DOI : 10.1109 / tc.1975.224297 .
- ^ Narendra, Patrenahalli M .; Фукунага, К. (1977). «Алгоритм ветвей и границ для выбора подмножества признаков» (PDF) . Транзакции IEEE на компьютерах . С-26 (9): 917–922. DOI : 10.1109 / TC.1977.1674939 .
- ^ Хазиме, Хусейн; Мазумдер, Рахул; Сааб, Али (2020). «Разреженная регрессия в масштабе: ветвление и граница, основанная на оптимизации первого порядка». arXiv : 2004.06152 .
- ^ Новозин, Себастьян; Ламперт, Кристоф Х. (2011). «Структурированное обучение и прогнозирование в компьютерном зрении». Основы и тенденции компьютерной графики и зрения . 6 (3–4): 185–365. CiteSeerX 10.1.1.636.2651 . DOI : 10.1561 / 0600000033 . ISBN 978-1-60198-457-9.
- ^ Nau, Dana S .; Кумар, Випин; Канал, Лавин (1984). «Общая ветвь и граница и ее связь с A ∗ и AO ∗» (PDF) . Искусственный интеллект . 23 (1): 29–58. DOI : 10.1016 / 0004-3702 (84) 90004-3 .
Внешние ссылки
- LiPS - Бесплатная простая в использовании программа с графическим интерфейсом, предназначенная для решения задач линейного, целочисленного и целевого программирования.
- Cbc - (Coin-or branch and cut) - решатель смешанного целочисленного программирования с открытым исходным кодом, написанный на C ++.