Д. Лесэнт: Проблемы локального поиска в задачах теории операций

[mns2012]

1. ЛП -- это аппроксимация без каких-либо незыблемых теоретических оснований. Никаких гарантий сходимости процесса к оптимуму нет. Пространство поиска неструктурировано. Отсюда вытекает важность выбора "правильного", с точки зр. эффективности, оператора соседства: гладкого, регулярного (близкие точки должны давать близкие значения функции цели), структурирующего пространство и определяющего ландшафт.

2. ЛП неудобен для формулирования задач в терминах программирования в ограничениях. Ограничения задачи "убивают" поиск. Три подхода преодоления этой трудности:

(1) Формулировать задачу так, чтобы решение выбиралось из множества, заранее удовлетворяющего органичениям задачи. Например, в задаче странствующего коммивояжера, где по условию посещать любой город можно только единожды, можно вручную составить первое допустимое решение и дальше осуществлять поиск только на множесте перестановок. Этот путь неудобен, если ограничения сложные и их много.
(2) Представлять ограничения мягкими и запихивать их в функцию цели (max satisfiability problem). Это неудобно потому, что "замыливается" реальная функция цели, да и на практике часто нужно удовлетворять всем ограничениям, а не как можно большему числу.
(3) Подход наиболее чистый, с т.зр. knowledge representation. Сочетание (coupling) поиска с технологией программирования в ограничениях: проверка на удовлетворение органичениям задачи производится на каждом шаге поиска. В результате этого локальные модификации решения, не удовлетворяющие всем ограничениям, отбрасываются. Это тянет за собой проблемы теоретического и практического плана. Теоретические касаются условия эргодичности, связанного с парадоксом Пуанкаре возвращения, согласно которому траектория закрытой системы, совершающей финитные движения, рано или поздно пройдет сколь угодно близко к начальной точке. Условие эргодичности применительно к локальному поиску требует наличия пути между любыми двумя точками в пространстве поиска. Это условие устанавливает некоторую форму полноты ЛП (локальный поиск, будучи несистематическим поиском без отката, как известно, не является полным, поэтому, в частности, ЛП не может использоваться в общем случае для доказательства отсутствия решений задачи). К сожалению, удаление точек, не совместных с органичениями задачи, нарушает условие эргодичности! Могут быть наложены такие ограничения, которые исключают возможность построения совместного соседства (все соседи решения могут оказаться несовместными). Отсюда следует возможность недостижения оптимума. При рассмотрении практических задач большого размера вероятность "выпадения" всего соседства как несовместного низка, однако эффективность ЛП всё же страдает, поскольку показатель эффективности ЛП -- это отношение числа совместных решений по соседству с данным решением к размеру множества соседей. При малой величине отношения, поиск будет тратить много времени на отбраковку несовместных соседей.

Итак, сочетание ЛП с программированием в ограничениях, с формальной т.зр., является наилучшим выходом из положения: представление решения не страдает, функция цели отделена от ограничений. С практической т.зр., проверка совместности (constraint checks) может сильно ухудшать производительность ЛП. Это может случиться вследствие неудачных выбора и имплементации операторов соседства и методов распространения ограничений.

Парадокс возвращения мне уже как-то приходилось обсуждать (здесь, здесь и здесь).

Comments

[mns2012]

"Условие эргодичности применительно к локальному поиску требует наличия пути между любыми двумя точками в пространстве поиска."

Неясно вот что. Это условие связности пространства. Понятно, что оно должно быть удовлетворено. Но это не всё, что предъявляется к эргодической системе.
Согласно определению эргодичности, средние по времени должны совпадать или, по кр. мере, быть близкими к средним по пространству. Это не выполняется в общем случае ландшафта ЛП: в зависимости от начальных условий динамика поиска может быть совершенно различной. Даже при условии связности пространства...