Лекция
Привет, мой друг, тебе интересно узнать все про алгоритмы локального поиска, тогда с вдохновением прочти до конца. Для того чтобы лучше понимать что такое алгоритмы локального поиска , настоятельно рекомендую прочитать все из категории Логика.
До сих пор в данной книге было представлено несколько алгоритмов локального поиска, включая алгоритмы 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, являются наиболее полезными, когда можно действительно рассчитывать на то, что решение существует; например, задачи, обычно имеют решения. С другой стороны, локальный поиск не всегда может обнаружить невыполнимость, а именно это требуется, когда задача состоит в том, чтобы определить, следует ли какое-то высказывание из базы знаний. Например, агент не может надежно использовать локальный поиск для доказательства того, что некоторый квадрат в мире вампуса безопасен. Вместо этого он может лишь утверждать: "Я размышлял об этом в течение часа, но так и не мог найти хотя бы один из возможных миров, в котором данный квадрат не является безопасным".
А поскольку данный алгоритм локального поиска обычно позволяет действительно быстро найти модель, если она существует, то агент, использующий этот алгоритм, должен учитывать, что неудача в попытке найти модель высказывания с помощью данного алгоритма скорее всего свидетельствует о невыполнимости данного высказывания. Безусловно, такой результат — нечто иное, чем доказательство, и агент должен трижды подумать, прежде чем рискнуть своей жизнью, основываясь на подобных результатах.Если я не полностью рассказал про алгоритмы локального поиска? Напиши в комментариях Надеюсь, что теперь ты понял что такое алгоритмы локального поиска и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Логика
Из статьи мы узнали кратко, но содержательно про алгоритмы локального поиска
Комментарии