Chmyr_I_A_Sistemy_II_4_razdela_2012

41

Бухаресту является город Фэгэраш. Расширение узла Fagaras порождает узел Bucharest, который является целевым. Применение в процессе решения данной конкретной задачи алгоритма жадного поиска по первому наилучшему совпадению с использованием функции hSLD позволяет найти решение без расширения какого-либо узла, не находящегося на пути к решению. Однако, само найденное решение не является наилучшим. Путь до Бухареста через города Сибиу и Фэгэраш на 32 километра длиннее, чем путь через города Рымнику-Вылча и Питешти (см. рис. 2.2). Это замечание показывает, почему изучаемый алгоритм называется «жадным». На каждом этапе он пытается подойти к цели как можно ближе (фигурально выражаясь, «захватить как можно больше»).

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

Алгоритм обладает теми же недостатками, что и алгоритм поиска в глубину: он не является оптимальным, к тому же он – не полный, поскольку способен отправиться по бесконечному пути и не вернуться, чтобы опробовать другие возможности.

3.1.2 Поиск А*: минимизация суммарной оценки стоимости решения

Наиболее широко известная разновидность поиска по первому наилучшему совпадению называется поиском А*, читается как «поиск А звѐздочка». В этой стратегии применяется функция оценки, объединяющая в себе функцию g(n) – стоимость достижения данного узла, и функцию h(n) – оценку стоимости прохождения от данного узла до цели:

f(n) = g(n) + h(n)

Поскольку функция g(n) позволяет определить стоимость пути от начального узла до узла n, а функция h(n) определяет оценку стоимости наименее дорогостоящего пути от узла n до цели, то справедлива следующая интерпретация функции f(n):

f(n) = <оценка стоимости наименее дорогостоящего пути решения, проходящего через узел n>

Таким образом, при осуществлении попытки найти наименее дорогостоящее решение, по-видимому, разумнее всего вначале попытаться проверить узел с наименьшим значением g(n) + h(n).

Как оказалось такая стратегия является более чем просто разумной. Если эвристическая функция h(n) удовлетворяет некоторым условиям, то поиск А* становится и полным и оптимальным. Анализ оптимальности поиска А* является несложным, если этот метод используется в сочетании с обобщѐнным алгоритмом поиска (см. рис. 2.7 и 2.9). В таком случае поиск А* является оптимальным, при условии, что h(n) представляет собой допустимую эвристику, т.е. при условии, что h(n) никогда не переоценивает стоимость достижения цели. Допустимые эвристические функции являются, по сути, оптимистическими функциями, поскольку возвращают значения стоимости решения проблемы, меньшее по сравнению с фактическим значением стоимости. А поскольку g(n) – точная стоимость достижения узла n, из этого непосредственно следует, что функция f(n) никогда не переоценит истинную стоимость достижения решения через узел n.

Очевидным примером допустимой эвристической функции является функция определения расстояния по прямой hSLD, которая уже использовалась для поиска пути из Арада в Бухарест. Расстояние по прямой является допустимой эвристикой, поскольку кратчайший путь между любыми двумя точками лежит на прямой, соединяющей эти точки. Это означает, что длина прямого пути по определению не может представлять собой переоценку длины пути. На рис. 3.3 показано развитие дерева поиска для процесса поиска пути в Бухарест при помощи А* поиска. Значение g(n) определяется при помощи рис.2.2, а значения hSLD приведены в таблице на рис. 3.1.

Отметим, что узел Bucharest впервые появляется в пограничном наборе узлов, показанном на этапе д) на рис. 3.3, но не выбирается для расширения, поскольку его f- стоимость (450) выше, чем стоимость узла Pitesti (417). Поэтому может существовать

42

решение, при котором путь проходит через город Питешти со стоимость, равной 417, поэтому алгоритм не останавливается на решении со стоимостью, равной 450.

а) Начальное состояние

б) После расширения узла Arad

в) После расширения узла Sibiu

г) После расширения узла Rimnicu Vilcea

д) После расширения узла Fagaras

е) После расширения узла Pitesti

Рис. 3.3. Этапы А* поиска пути в Бухарест. Узлы отмечены значением f = g + h.

Рассмотренный пример может служить общим свидетельством того, что поиск А* с

использованием обобщѐнного алгоритма поиска (см. рис. 2.7 и 2.9) является оптимальным, если функция h(n) допустима.

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

43

f(G2) = g(G2) + h(G2) > C*

Теперь рассмотрим узел n из пограничного набора узлов, который находится на оптимальном пути решения, например узел Pitesti в примере, приведенном выше. Если решение существует, то всегда должен быть такой узел. Если функция h(n) не переоценивает стоимость завершения этого пути решения, то справедливо следующее выражение:

f(n) = g(n) + h(n) ≤ C*

Таким образом, доказано, что f(n)≤C*<f(G2), поэтому узел G2 не расширяется и поиск А* должен вернуть оптимальное решение.

Одним из главных недостатков алгоритма поиска А* является большая потребность в ресурсе память. Это связано с тем, что этот алгоритм предполагает хранение в памяти всех сгенерированных узлов.

3.2.Эвристические функции

Внастоящем параграфе рассматриваются эвристические функции для головоломки с восемью фишками. На примере этой игрушечной проблемы демонстрируются характерные особенности всех эвристических функций в целом.

Как было отмечено в 2.2.1, в ходе решения головоломки требуется передвигать фишки по горизонтали или по вертикали на пустой участок до тех пор, пока полученная конфигурации фишек не будет соответствовать целевой конфигурации. Рис. 3.4 приведен вариант начальной и целевой конфигурации фишек головоломки с восемью фишками.

Рис.3.4. Начальное и целое состояния головоломки с восемью фишками.

В 2.2.1 приведена формальная формулировка этой проблемы. Представим теперь, что мы хотим найти еѐ решение при помощи алгоритма А*. Для этого нам необходима эвристическая функция, которая никогда не переоценивает количество перемещений, необходимых для достижения цели. Ниже описаны два широко используемых кандидата на эту роль.

h1 = <количество фишек, стоящих не на своѐм месте>. В левой части рис. 3.4 все восемь фишек стоят не на своѐм месте, поэтому показанное слева начальное со-

стояние имеет эвристическую оценку h1 = 8. Эвристическая функция h1 является допустимой, поскольку очевидно, что каждую фишку, находящуюся не на своѐм месте, необходимо переместить, по меньшей мере, один раз.

h2 = <сумма расстояний всех фишек от их целевых позиций>. Поскольку фишки не могут передвигаться по диагонали, то рассчитываемое расстояние представляет собой сумму горизонтальных и вертикальных расстояний. Такое расстояние иногда называют расстоянием городских кварталов, или манхэттенским расстоянием.

Эвристическая функция h2 также является допустимой, поскольку всѐ, что может быть сделано в одном ходе, состоит лишь в перемещении одной фишки на один шаг ближе к цели. Для расположения фишек в левой части рис. 3.4 манхэттенское расстояние равно: h2 = 3+1+2+2+2+3+3+2=18.

Как и можно было предположить, ни одна из этих функций не переоценивает истинную стоимость решения, которая равна 26.

44

3.3. Алгоритмы локального поиска и задачи оптимизации

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

Если путь к цели не представляет интереса, то могут рассматриваться алгоритмы другого класса, в которых вообще не требуются сохранения каких-либо данных о путях. Алгоритмы локального поиска действуют с учѐтом единственного текущего состояния, а не многочисленных путей, и обычно предусматривают только переход в состояние, соседнее по отношению к текущему состоянию. Как правило, информация о путях, пройденных в процессе такого поиска, не сохраняется. Алгоритмы локального поиска обладают двумя важными достоинствами. Во-первых, они используют очень небольшой и, как правило, постоянный объѐм памяти, и, во-вторых, они часто позволяют находить приемлемые решения в больших или бесконечных (непрерывных) пространствах состояний, для которых алгоритмы поиска пути не применимы.

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

Для понимания локального поиска полезно оперировать понятием ландшафт пространства состояний, пример которого изображѐн на рис. 3.6.

Целевая функция

Глобальный максимум

Уступ

Локальный максимум

«Плоский» локальный максимум

Рис.3.6. Ландшафт одномерного пространства состояний, в котором возвышение соответствует целевой функции. Задача состоит в поиске глобального максимума.

Различные топографические элементы ландшафта рассмотрены в тексте.

Ландшафт пространства состояний можно рассматривать с точки зрения: (1) эвристической функции стоимости (тогда задача заключается в поиске самой глубокой «долины», или глобального минимума), или (2) целевой функции (тогда задача заключается в поиске высочайшего «пика», или глобального максимума).

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

45

3.3.1. Поиск с восхождением к вершине

Алгоритм поиска с восхождением к вершине приведен на рис. 3.7.

function HillClimbingSearch(problem) returns состояние, которое соответствует локальному максимуму

inputs: problem, проблема

local variables: current, текущий узел дерева поиска neighbor, ближайший узел дерева поиска

current MakeNode(InitialState(problem)) loop do

neighbor преемник узла current с наибольшим значением целевой функции ObjectiveFunc

if ObjectiveFunc(neighbor) ≤ ObjectiveFunc(current) then return State(current)

current neighbor

Рис. 3.7. Алгоритм поиска с восхождением к вершине. На каждом шаге текущий узел заменяется наилучшим соседним узлом с наибольшим значением

функции ObjectiveFunc.

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

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

Однако, поиск с восхождением к вершине часто попадает в тупиковую ситуацию по причине достижения локального максимума или плато.

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

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

Попав в тупиковую ситуацию, алгоритм поиска с восхождением к вершине не может осуществляться дальнейшее успешное продвижение по пространству состояний.

Начиная со случайно сформированного начального состояния для задачи с восемью ферзями, алгоритм поиска с восхождением к вершине заходит в тупик в 86% случаях, решая только 14% экземпляров этой задачи. Но работает очень быстро, выполняя в среднем 4 цикла в случае успешного завершения и 3 цикла в случае попадания в тупиковую ситуацию.

Разработано несколько вариантов поиска с восхождением к вершине. Поиск с вос-

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

вестной рекомендацией: «Если первая попытка оказалась неудачной, пробуй снова и снова». В этом алгоритме предусмотрено проведение ряда поисков из сформированных слу-

46

чайным образом начальных состояний и остановка после достижения цели. Он является полным с вероятностью, достигающей единицы, хотя бы по той тривиальной причине, что в конечном итоге в качестве начального состояния может сформироваться одно из целевых состояний. Алгоритм поиска с восхождением к вершине и перезапуском случайным образом является эффективным применительно к задаче с восемью ферзями. Успех этого алгоритма в значительной степени зависит от ландшафта пространства состояний. Если в нѐм есть лишь несколько локальных максимумов и плато, то поиск с восхождением к вершине и перезапуском случайным образом позволяет быстро найти хорошее решение.

3.3.2. Локальный лучевой поиск

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

Валгоритме локального лучевого поиска предусмотрено отслеживание k состояний,

ане одного состояния. Вначале формируются k состояний случайным образом. Затем формируются преемники всех k состояний. Если какой-либо из этих преемников соответствует целевому состоянию, то алгоритм останавливается. В противном случае алго-

ритм выбирает k наилучших преемников и повторяет цикл. Выбор наилучшего преемника осуществляется таким же образом, как и в алгоритме с восхождением к вершине.

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

чевом поиске параллельные потоки поиска обмениваются информацией. Если в некото-

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

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

3.3.3. Генетические алгоритмы

Генетический алгоритм представляет собой вариант стохастического лучевого поиска, в котором состояния-преемники формируются путѐм использования двух родительских состояний, а не путѐм модификации единственного состояния. В нѐм просматривается такая же аналогия с естественным отбором, как и в стохастическом лучевом поиске, за исключением того, что теперь моделируется не бесполое, а половое воспроизводство.

Как и при лучевом поиске, работа генетического алгоритма начинается с формирования случайным образом k состояний, называемых популяцией. Каждое состояние, или индивидуум, представляется строкой символов. Например, состояние задачи с восемью ферзями должно определять положение всех восьми ферзей, поэтому любое состояние может быть представлено строкой из восьми символов, каждый из которых является числом в диапазоне от 1 до 8. На рис. 3.8а, показана популяция из четырѐх индивидуумов для задачи с восемью ферзями.

Процесс выработки следующего поколения состояний показан на рис. 3.8б-д. На рис. 3.8б каждое состояние оценивается с помощью функции пригодности. Функция при-

47

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

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

Рис. 3.8. Пример работы генетического алгоритма. (а) – начальная популяция; (б) – функция пригодности; (в) – отбор; (г) – скрещивание; (д) – мутация.

Для исходных четырѐх состояний соответствующие значения функции пригодности равны 24, 23, 20 и 11. В данном конкретном варианте генетического алгоритма вероятность выбора для воспроизводства прямо пропорциональна оценке пригодности. Соответствующие вероятности в процентах показаны рядом со значениями функции пригодности.

Как показано на рис. 3.8в, для воспроизводства случайным образом выбираются две пары в соответствии с вероятностями, показанными на рис. 3.8б. Один индивидуум выбирается дважды, а один вообще остаѐтся не выбранным. Для каждой пары, предназначенной для воспроизводства, среди позиций в строке случайным образом выбирается точка скрещивания. На рис. 3.8 точки скрещивания находятся после третьей цифры в первой паре и после пятой цифры во второй паре (отмечено вертикальными пунктирными линиями).

Как показано на рис. 3.8г, сами потомки создаются путѐм перекрѐстного обмена подстроками родительских строк, разорванных в точке скрещивания. Например, первый потомок первой пары получает первые три цифры от первого родителя, а остальные цифры – от второго родителя, тогда как второй потомок получает первые три цифры от второго родителя, а остальные – от первого родителя.

Состояния задачи с восемью ферзями, участвующие в этом этапе воспроизводства, показаны на рис. 3.9.

Рис. 3.9. Состояния задачи с восемью ферзями, соответствующие первым двум родительским состояниям, показанным на рис. 3.8в, и первому потомку, показанному на рис. 3.9г. Затемнѐнные столбцы на этапе скрещивания теряются, а незатемнѐнные сохраняются.

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

48

На рис. 3.10 приведен генетический алгоритм поиска, который реализует описанные этапы.

function GeneticAlgorithm(population, FitnessFn) returns

индивидуум

inputs: population, начальная популяция

FitnessFn, функция пригодности индивидуума

repeat

newPopulation ← пустое множество

loop for i from 1 to Size(population) do

x RandomSelection(population, FitnessFn)

y RandomSelection(population, FitnessFn)

child Reproduce(x, y)

if (небольшое случайно выбранное значение вероятности) then child Mutate(child)

добавить child к newPopulation

population newPopulation

until некоторый индивидуум не станет достаточно пригодным или не истечѐт заданное время

return наилучший индивидуум в population в соответствии с

FitnessFn

function Reproduce(x, y) returns индивидуум inputs: x, y, индивидуумы-родители

n Length(x)

c случайное число от 1 до n // точка скрещивания return Couple(Substring(x, 1, c), Substring(y, c+1, n)

Рис. 3.10 Генетический алгоритм. Каждое скрещивание двух родителей приводит к получению только одного потомка, а не двух.

Как и в алгоритмах стохастического лучевого поиска, в генетических алгоритмах тенденция в стремлении к максимуму сочетается с проводимым случайным образом исследованием и обменом информацией между параллельными поисковыми потоками. Основное преимущество генетических алгоритмов связано с применением операции скрещивания. Тем не менее можно доказать, что если позиции в генетическом коде первоначально устанавливаются в случайном порядке, то скрещивание не даѐт никаких преимуществ. На интуитивном уровне можно предположить, что преимуществом была бы способность комбинировать в результате скрещивания большие блоки символов, которые были независимо сформированы в ходе эволюции для выполнения полезных функций, что позволило бы повысить степень детализации, с которой действует этот алгоритм поиска. Например, преимущество достигалось бы, если в качестве полезного блока была выделена строка символов, предусматривающая размещение первых трѐх ферзей в позициях 2, 4 и 6 (где они не атакуют друг друга), после чего можно было бы объединять этот блок с другими блоками для формирования решения.

Упражнения

3.1.Выполните трассировку работы алгоритма поиска А* применительно к решению задачи проезда в город Бухарест из города Лугож с использованием эвристической функции определения расстояния по прямой. Иными словами, покажите последовательность узлов, которые рассматриваются этим алгоритмом, и приведите оценки f, g и h для каждого узла.

3.2.Докажите каждое из приведенных ниже утверждений.

a.Поиск в ширину представляет собой частный случай поиска по критерию стоимости.

49

b.Поиск в ширину, поиск в глубину и поиск по критерию стоимости – специальные случаи поиска А*.

3.3.Предложите эвристическую функцию для головоломки с восемью фишками, которая иногда допускает переоценку, и покажите, каким образом это может привести к получению неоптимального решения некоторых конкретных экземпляров задачи. Докажите, что если функция h никогда не переоценивает стоимость больше чем на c, то алгоритм А* с использованием функции h возвращает решение, стоимость которого превышает оптимальное решение не больше чем на c.

50

4.ЛОГИЧЕСКИЕ АГЕНТЫ

Настоящий раздел посвящѐн введению в теорию агентов, действующих на основе знаний, или агентов на основе знаний. Рассматриваемые здесь понятия, такие как представление знаний и процессы рассуждений являются базовыми в дисциплине искусственный интеллект.

4.1. Агенты, основанные на знаниях

Центральным компонентом агента, основанного на знаниях, является его база знаний, или сокращѐнно KB (knowledge base). В искусственном интеллекте база знаний рассматривается как множество предложений. Предложения записаны на языке, называемом языком представления знаний, и представляют собой утверждению о среде в которой оперирует агент.

Должна существовать операция добавления новых предложений в базу знаний и операция извлечения знаний из базы знаний. Будем называть эти операции соответственно Tell и Ask. Обе отмеченные операции могут быть связаны с проведением логического вывода, т.е. получением новых предложений из уже имеющихся предложений. В логических агентах, логический вывод подчиняется фундаментальному требованию, заключающемся в том, что ответ на запрос к базе знаний, переданный при помощи операции

Ask, должен логически следовать из того, что было ранее введено в базу знаний при по-

мощи операции Tell. Программа агента, основанного на знаниях, приведена на рис. 4.1.

function KB-Agent(perception) returns action static: KB, база знаний

t, счѐтчик моментов времени, первоначально пустой

Tell(KB, PerceptionToSentence(perception, t))

action Ask(KB, MakeActionQuery(t)) Tell(KB, ActionToSentence(action, t)) return action

Рис. 4.1. Интеллектуальный агент, основанный на знаниях.

Как и все интеллектуальные агенты, этот агент принимает результат акта восприятия perception и возвращает действие action. Агент поддерживает базу знаний, KB, которая может первоначально содержать некоторые фоновые знания. После каждого вызова, программа агента выполняет три этапа. Во-первых, вводит в базу знаний при помощи функции Tell результаты восприятия, во-вторых, передаѐт в базу знаний с помощью функции Ask запрос о том, какое действие следует предпринять. Процесс поиска ответа на этот запрос представляет собой процесс логических рассуждений над знаниями, имеющимися в базе знаний. В-третьих, агент регистрирует свой выбор с помощью функции Tell и выполняет действие. Вторая функции Tell необходима для передачи в базу знаний информации о том, какое действие было выполнено.

Функция PerceptionToSentence формирует предложение, соответствующее восприятию в текущий момент времени, а функция ActionToSentence – предложение, соответствующее выполненному действию. Функция MakeActionQuery формирует запрос, адресованный базе знаний, о том, какое действие должна быть выполнено в текущий момент времени. Механизм логического вывода скрыт внутри функций Tell и Ask.

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

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