Связь с оптимизацией

Этот подход к минимизации энергии в действительности базируется на нескольких основных положениях: физическая система может находиться в одном из многочисленных состояний; ее энергия является функцией текущего состояния; небольшое возмущение в заданном состоянии приводит к «соседнему» состоянию.

Структура связи этих соседних состояний вместе со структурой энергетической функции определяет энергетическую поверхность.

Под этим углом мы снова взглянем на задачу вычислительной минимизации. В типичной задаче такого рода имеется большое (как правило, имеющее экспоненциальный размер) множество C возможных решений.

Также понадобится функция стоимости c(·), оценивающая качество каждого решения; для решения S Ѯ C его стоимость записывается в виде c(S). Целью является поиск решения S* Ѯ C с наименьшим возможным значением (S*).

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

Запись S Ң S’ означает, что S’ является соседним решением S, а множество соседей S, то есть {S’: S Ң S’}, будет обозначаться N(S). Нас в первую очередь интересуют симметричные соседские отношения, хотя основные рассматриваемые принципы также распространяются и на асимметричные соседские отношения.

Здесь принципиально то, что хотя множество C возможных решений и функция стоимости c(·) предоставляются в спецификации задачи, мы свободны выбирать соседские отношения по своему усмотрению.

Алгоритм локального поиска получает эту конфигурацию, включая соседские отношения, и работает по следующей высокоуровневой схеме. Он постоянно поддерживает текущее решение S Ѯ C. На каждом шаге он выбирает соседа S’ решения S, объявляет S’ новым текущим решением и повторяет процесс.

На протяжении всего выполнения алгоритма запоминается решение с наименьшей стоимостью из всех встречавшихся; итак, по мере выполнения постепенно находятся все лучшие и лучшие решения.

Суть алгоритма локального поиска заключается в выборе соседских отношений и в формулировке правила выбора соседнего решения на каждом шаге.

Итак, соседские отношения можно рассматривать как определяющий (обычно ненаправленный) граф множества всех возможных решений, в котором ребра соединяют соседние пары решений. В этом случае алгоритм локального поиска может рассматриваться как обход графа с попыткой перемещения в направлении хорошего решения.