Алгоритмы локального поиска
До сих пор в данной книге было представлено несколько алгоритмов локального поиска, включая алгоритмы Hill-Climbing (с. 176) и Simulated-Annealing (с. 181). Эти алгоритмы могут непосредственно применяться для решения задач проверки выполнимости, при условии, что будет выбрана правильная функция оценки. Поскольку цель состоит в том, чтобы найти присваивание, обеспечивающее выполнение каждого выражения, для этой цели может использоваться любая функция оценки, которая подсчитывает количество невыполненных выражений. Фактически именно этот критерий и применяется в алгоритме Min-Conf licts для задач CSP (с. 227). Все эти алгоритмы делают шаги в пространстве полных присваиваний, каждый раз меняя на противоположное (инвертируя) истинностное значение одного символа. Это пространство обычно содержит много локальных минимумов, для выхода из которых требуются различные формы рандомизации. В последние годы было проведено множество экспериментов с тем, чтобы можно было найти приемлемый компромисс между стремлением к "жадному" выбору наилучшего преемника и необходимостью выходить из локальных минимумов с помощью случайного выбора очередного преемника.
Одним из простейших и наиболее эффективных алгоритмов, которые были созданы в результате всей этой работы, является алгоритм, получивший название WalkSAT (листинг 7.8). При каждой итерации этот алгоритм выбирает одно невыполненное выражение, а в этом выражении выбирает один символ для инвертирования. В данном алгоритме происходит случайным образом переключение между двумя способами выбора символа для инвертирования его истинностного значения: во-первых, этап с "минимизацией конфликтов", в котором минимизируется количество невыполненных выражений в новом состоянии, и, во-вторых, этап "случайного передвижения", в котором один из символов выбирается случайным образом.
Листинг 7.8. Алгоритм WalkSAT для проверки выполнимости путем инвертирования значений переменных случайным образом. Существует много версий этого алгоритма
function WalkSAT(clauses, р, max_flips) returns выполняющую высказывание
модель model или индикатор отказа failure inputs: clauses, множество выражений в пропозициональной логике р, вероятность выбора решения сделать ход со "случайным
перемещением", которая, как правило, составляет около 0,5 тах_flips, количество инверсий, которые разрешено
выполнить,прежде чем отказаться от дальнейших попыток
model <г- случайно выбранное присваивание значений true/false
символам в выражениях for i = 1 to тах_flips do
if в модели model выполняется множество clauses
then return model clause
случайно выбранного символа из выражения clause else инвертировать значение того символа из выражения clause, который максимизирует количество выполненных выражений в множестве clauses return failure
Действительно ли такой алгоритм, как WalkSAT, способен выполнять производительную работу? Очевидно, что если он возвращает некоторую модель, то входное высказывание в самом деле выполнимо. А что если он возвращает индикатор неудачи failure? К сожалению, в этом случае невозможно определить, верно ли, что высказывание является невыполнимым, или просто этому алгоритму требуется предоставить больше шансов добиться успеха. При этом можно попытаться присвоить параметру с определением максимального количества инверсий тах_flips бесконечно большое значение. В данном случае можно легко показать, что алгоритм Walks AT в конечном итоге вернет какую-то модель (если она существует), при условии, что вероятность этого р>0. Это связано с тем, что всегда существует последовательность инверсий, ведущая к присваиванию, которое обеспечивает выполнение высказывания, и такая последовательность в конечном итоге вырабатывается в результате случайного выбора этапов перемещения. К сожалению, если параметр тах_flips имеет бесконечно большое значение, а высказывание является невыполнимым, данный алгоритм никогда не заканчивает свою работу!
Из этого следует, что алгоритмы локального поиска, подобные WalkSAT, являются наиболее полезными, когда можно действительно рассчитывать на то, что решение существует; например, задачи, которые рассматривались в главах 3 и 5, обычно имеют решения. С другой стороны, локальный поиск не всегда может обнаружить невыполнимость, а именно это требуется, когда задача состоит в том, чтобы определить, следует ли какое-то высказывание из базы знаний. Например, агент не может надежно использовать локальный поиск для доказательства того, что некоторый квадрат в мире вампуса безопасен. Вместо этого он может лишь утверждать: "Я размышлял об этом в течение часа, но так и не мог найти хотя бы один из возможных миров, в котором данный квадрат не является безопасным". А поскольку данный алгоритм локального поиска обычно позволяет действительно быстро найти модель, если она существует, то агент, использующий этот алгоритм, должен учитывать, что неудача в попытке найти модель высказывания с помощью данного алгоритма скорее всего свидетельствует о невыполнимости данного высказывания. Безусловно, такой результат — нечто иное, чем доказательство, и агент должен трижды подумать, прежде чем рискнуть своей жизнью, основываясь на подобных результатах.