Алгоритмы локального поиска

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

До сих пор в данной книге было представлено несколько алгоритмов локального поиска, включая алгоритмы Hill-Climbing и Simulated-Annealing. Эти алгоритмы могут непосредственно  применяться для решения задач проверки выполнимости, при условии, что будет выбрана правильная функция оценки. Поскольку цель состоит в том, чтобы найти присваивание, обеспечивающее выполнение каждого выражения, для этой цели может использоваться любая функция оценки, которая подсчитывает количество невыполненных выражений. Фактически именно этот критерий и применяется в алгоритме Min-Conf licts для задач CSP.

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

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

 

Алгоритм WalkSAT для проверки выполнимости путем инвертирования значений переменных случайным образом. Об этом говорит сайт https://intellect.icu . Существует много версий этого алгоритма

function WalkSAT(clauses, р, max_flips) returns выполняющую

  высказывание

  модель model или индикатор отказа failure

  inputs: clauses, множество выражений в пропозициональной логике

  р, вероятность выбора решения сделать ход со "случайным

  перемещением", которая, как правило, составляет около 0,5

  max_flips, количество инверсий, которые разрешено

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

  попыток

  model <— случайно выбранное присваивание значений true/false

  символам в выражениях

  for i = 1 to тах_flips do

  if в модели model выполняется множество clauses

  then return model

  clause <— выбранное случайным образом выражение из множества

  clauses, которое имеет значение false в модели model

  with probability р инвертировать в модели model значение

  случайно выбранного символа из выражения clause

  else инвертировать значение того символа из выражения clause,

  который максимизирует количество выполненных выражений

  в множестве clauses

  return failure

 

Действительно ли такой алгоритм, как WalkSAT, способен выполнять производительную работу? Очевидно, что если он возвращает некоторую модель, то входное высказывание в самом деле выполнимо. А что если он возвращает индикатор неудачи failure? К сожалению, в этом случае невозможно определить, верно ли, что высказывание является невыполнимым, или просто этому алгоритму требуется предоставить больше шансов добиться успеха. При этом можно попытаться присвоить параметру с определением максимального количества инверсий тах_ flips бесконечно большое значение.

В данном случае можно легко показать, что алгоритм Walks AT в конечном итоге вернет какую-то модель (если она существует), при условии, что вероятность этого р>0. Это связано с тем, что всегда существует последовательность инверсий, ведущая к присваиванию, которое обеспечивает выполнение высказывания, и такая последовательность в конечном итоге вырабатывается в результате случайного выбора этапов перемещения. К сожалению, если параметр тах_flips имеет бесконечно большое значение, а высказывание является невыполнимым, данный алгоритм никогда не заканчивает свою работу!

Из этого следует, что алгоритмы локального поиска , подобные Walks AT, являются наиболее полезными, когда можно действительно рассчитывать на то, что решение существует; например, задачи, обычно имеют решения. С другой стороны, локальный поиск не всегда может обнаружить невыполнимость, а именно это требуется, когда задача состоит в том, чтобы определить, следует ли какое-то высказывание из базы знаний. Например, агент не может надежно использовать локальный поиск для доказательства того, что некоторый квадрат в мире вампуса безопасен. Вместо этого он может лишь утверждать: "Я размышлял об этом в течение часа, но так и не мог найти хотя бы один из возможных миров, в котором данный квадрат не является безопасным".

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

Если я не полностью рассказал про алгоритмы локального поиска? Напиши в комментариях Надеюсь, что теперь ты понял что такое алгоритмы локального поиска и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Логика

Из статьи мы узнали кратко, но содержательно про алгоритмы локального поиска