Управление стратегией выбора с помощью эвристик

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

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

Эвристика - это эмпирическое правило, с помощью которого человек эксперт в отсутствие формулы или алгоритма пытается осуществить свои намерения. Если есть алгоритм, то человек-эксперт воспользуется им. Но чаще алгоритма нет.

Для того, чтобы понять, как разрабатывается эвристика, проведем несложный эксперимент. Возьмём два отличающихся по размеру листа бумаги. Разрежем меньший из них на прямоугольники различных размеров. Затем расположим их на стороне большого листа как можно экономнее. При этом будут видны все варианты стратегий компоновки. Найдём опытным путем лучший вариант стратегии. Эта стратегия и будет являться нашей эвристикой. Следует отметить, что данная проблема слишком сложна, чтобы ее можно было решить математическими методами, даже для прямоугольников.

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

Существует два типичных способа включения эвристической информациии о конкретной задаче в поисковую структуру:

- с помощью эвристической оценочной функции, которая "взвешивает" утверждения конкретной задачи и определяет их относительную значимость;

- непосредственно поместив эвристическую информацию в правила.

Рассмотрим оба варианта.

5.4.1.Поиск с применением эвристической оценочной функции.

Для иллюстрации выберем детскую игру "Восьмерка". Зрительно можно её представить в виде квадрата с девятью возможными позициями и восемью маленькими подвижными квадратиками, расположенными внутри большого. Одна позиция пустая. Цель задачи - найти последовательность перемещений, чтобы перейти из начального положения в определенное конечное. Любую фишку можно передвинуть по горизонтали

или по вертикали, если рядом есть свободное место, но двигаться по диагонали запрещено.

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

Например, имеем:

НАЧАЛЬНОЕ СОСТОЯНИЕ

[4, 0, 5, 7, 2, 1, 3, 8, 6]

КОНЕЧНОЕ СОСТОЯНИЕ

[3, 4, 8, 7, 1, 5, 0, 2, 6]

Таким образом, задача может включать 9! > 350 000 возможных состояний. Вероятный вариант перемещения из начальной позиции:

[4,0, 5, 7, 2, 1, 3, 8, 6] -> [4, 2, 5, 7, 0, 1, 3, 8, 6].

Существует два способа систематического исследования состояния задачи без использования эвристик.

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

[4,0, 5, 7, 2, 1, 3, 8, 6] -> [4, 2, 5, 7, 0, 1, 3, 8, 6];

[4,0, 5, 7, 2, 1, 3, 8, 6] -> [0, 4, 5, 7, 2, 1, 3, 8, 6];

[4,0, 5, 7, 2, 1, 3, 8, 6] -> [4, 5, 0, 7, 2, 1, 3, 8, 6].

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

[4, 2, 5, 7, 0, 1, 3, 8, 6] ->[4, 2, 5, 0, 7, 1, 3, 8, 6];

[4, 2, 5, 7, 0, 1, 3, 8, 6] ->[4, 2, 5, 7, 1, 0, 3, 8, 6];

[4, 2, 5, 7, 0, 1, 3, 8, 6] ->[4, 2, 5, 7, 8, 1, 3, 0, 6].

Допустим, что опять выбран первый вариант. Теперь возможны два перемещения и т.д.

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

Поиск в ширину заключается в проверке всех альтернатив на расстоянии n шагов от начала до того, как начнется просмотр n+1 шага. Поэтому программа поиска в ширину, чтобы выяснить, не достигла ли она нужного решения, прежде разберёт все указанные ниже трансформации:

[4,0, 5, 7, 2, 1, 3, 8, 6] -> [4, 2, 5, 7, 0, 1, 3, 8, 6];

[4,0, 5, 7, 2, 1, 3, 8, 6] -> [0, 4, 5, 7, 2, 1, 3, 8, 6];

[4,0, 5, 7, 2, 1, 3, 8, 6] -> [4, 5, 0, 7, 2, 1, 3, 8, 6].

Далее она просмотрит с той же целью все пути на расстоянии двух трансформаций от начала и т.д. Если исключить повторения, то нужно просмотреть пять таких путей.

[4,2, 5, 7, 0, 1, 3, 8, 6] -> [4, 2, 5, 0, 7, 1, 3, 8, 6];

[4,2, 5, 7, 0, 1, 3, 8, 6] -> [4, 2, 5, 7, 8, 1, 3, 0, 6];

[4,2, 5, 7, 0, 1, 3, 8, 6] -> [4, 2, 5, 7, 1, 0, 3, 8, 6].

[0,4, 5, 7, 2, 1, 3, 8, 6] -> [7, 4, 5, 0, 2, 1, 3, 8, 6];

[4,5, 0, 7, 2, 1, 3, 8, 6] -> [4, 5, 1, 7, 2, 0, 3, 8, 6].

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

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

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

Например, в следующей ситуации:

[4, 0, 5, 7, 2, 1, 3, 8, 6] положение в задаче;

[3, 4, 8, 7, 1, 5, 0, 2, 6] положение цели

расстояние Хемминга равно 7.

Если процедура поиска сможет найти положение, где расстояние Хемминга равно 0, задача будет решена.

Одна из стратегий заключается в следующем: с помощью оценочной функции проверяются все следствия одного выбора на всю возможную глубину, и только потом происходит очередной выбор. Эта стратегия называется методом оврагов. Этот метод имеет недостатки: неизбежно программа будет попадать в локальные минимумы и на "хребты". Ситуации локальных минимумов возникают потому, что программа может войти в состояние, где ни один из доступных ходов не улучшает ситуацию. "Хребет" соответствует ситуации, когда программа должна сделать ход, который временно ухудшает значения эвристической функции и только впоследствии приводит к улучшению. Серьёзный недостаток этой стратегии заключается в её “близорукости” – для совершения выбора используется только локальная информация.

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

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

5.4.2.Поиск с эвристическими правилами.

Теперь откажемся от оценочных функций и перейдем к проблеме построения реальной экспертной системы.

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

- каждый студент должен пройти за семестр четыре курса;

- следует определить обязательные курсы для данной специализации;

- каждому студенту разрешается выбрать факультативные курсы;

- нужно включить в учебный план общеобразовательные дисциплины;

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

Эти предположения станут эвристиками, когда будут включены в правила для составления расписания.

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

Описание:

req ("введения в вычисления"). /* обязательные курсы */

req ("структуры данных").

req ("ассемблер").

и т. д.

elec ("информатика"). /* факультативные курсы */

elec ("трансляторы").

elec ("анализ алгоритмов").

и т. д.

given_now("введения в вычисления"). /* читают в данном */

given_now("мат. анализ2"). /* семестре */

и т. д.

Пройдены конкретным студентом:

waived("введение в вычисления"). /* временно отложить */

waived("мат. анализ1").

passed("структуры данных"). /* изученные курсы */

passed("ассемблер").

и т. д.

impreq("структуры данных","введения в вычисления").

impreq("мат. анализ2","мат. анализ1").

/* Читать это следует так: "Непосредственным предварительным

условием для изучения "мат. анализ2" является знание "мат. анализ1"

*/

Перейдем к описанию правил:

pos_req_course (X) if req (X) /* правило для обязательных курсов */

and not (done_with(X)) and /* не прошёл старых*/

given_now (X) and /* читается в данном семестре*/

have_preq_for (X)./* изучить предварительно курсы*/.

Здесь утверждается, что X будет возможным обязательным курсом в расписании, если он является обязательным курсом, если студент его еще не прошел, если он должен читаться в этом семестре и если студент изучил все предварительные курсы.

Далее определим курсы, пройденные студентом (определяется один пройденныё курс):

done_with (X) if waived (X).

done_with (X) if passed (X).

all_done_with (X) if findall (Y, done_with(Y), X).

/* все пройденные курсы заносятся в список X */

Далее определяются все предварительные курсы в том случае, если все предварительные курсы, необходимые для изучения обязательного:

have_preq_for (X) if all_preq_for (X, Z) and

all_done_with (Q) and

subset (Z, Q).

/* Студент прошел все предварительные курсы в том случае, если все предварительные для X курсы находятся в списке Z, а все курсы, пройденные или пропущенные им, находятся в списке Q, и Z входит в Q. Другими словами, Z есть подмножество Q. */

Опишем список, содержащий все предварительные курсы для данного курса Y (impreq –непосредственно предвариттельный курс;общий предварительный курс):

all_preq_for (Y, Z) if findall (X, preq (Y, X), Z).

preq (X, Y) if impreq (X, Y). /* Данная комбинация */

preq (X, Y) if impreq (X, Z) and preq (Z, Y)./* исключает зацикливание */

/* в программе */

Правило для факультативного курса:

pos_elec_course (X) if elec (X) and

not (done_with (X)) and

given_now (X) and

have_preq_for (X).

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

Набор правил имеет вид:

pos_schedule(A, B, C, "gen.elec") if /*elec-факультативный */

pos_req_course (A), /* курс, который выбрал */

pos_req_course (B), /* студент */

pos_req_course (C),

ordered3 (A, B, C). /* предикат исключает */

/* повторение курсов */

Он выявляет повторение в списке одного и тогоже курса, а также перестановки наборов одинаковых курсов.

pos_schedule (A, B, C, "gen.elec") if

pos_req_course (A),

pos_req_course (B),

pos_elec_course (C),

ordered2 (A, B).

pos_schedule (A, B, C, "gen.elec") if

pos_req_course (A),

pos_elec_course (B),

pos_elec_course (C),

ordered2 (B, C).

pos_schedule (A, B, C, "gen.elec") if

pos_elec_course (A),

pos_elec_course (B),

pos_elec_course (C),

ordered3 (A, B, C).

pos_schedule (A, B, "gen.elec", "gen.elec") if

pos_req_course (A),

pos_req_course (B),

ordered2 (A, B).

pos_schedule (A, B, "gen.elec", "gen.elec") if

pos_req_course (A),

pos_elec_course (B).

pos_schedule (A, B, "gen.elec", "gen.elec") if

pos_elec_course (A),

pos_elec_course (B),

ordered2 (A, B).

pos_schedule (A, "gen.elec", "gen.elec", "gen.elec") if

pos_req_course (A).

pos_schedule (A, "gen.elec", "gen.elec", "gen.elec.") if

pos_elec_course (A).

pos_schedule ("gen.elec", "gen.elec", "gen.elec", "gen.elec").

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

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

Здесь вместо одного сложного правила создаётся набор простых правил по одному для каждого случая.

Дата добавления: 2014-01-07