Работа с нечеткостью

Методы поиска в глубину и в ширину

В системах, база знаний которых насчитывает сотни правил, желательным является использование стратегии управления выводом, позволяющей ми­нимизировать время поиска решения и тем самым повысить эффективность вывода. К числу таких стратегий относятся: поиск в глубину, поиск в ши­рину, разбиение на подзадачи и альфа-бета-алгоритм [Таунсенд, Фохт, 1991; Уэно, Исидзука, 1989; Справочник по ИИ, 1990].

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

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

Разбиение на подзадачи подразумевает выделение подзадач, решение которых рассматривается как достижение промежуточных целей на пути к конечной цели. Примером, подтверждающим эффективность разбиения на подзадачи, является поиск неисправностей в компьютере — сначала выявляется отка­завшая подсистема (питание, память и т. д.), что значительно сужает про­странство поиска. Если удается правильно понять сущность задачи и опти­мально разбить ее на систему иерархически связанных целей-подцелей, то можно добиться того, что путь к ее решению в пространстве поиска будет минимален.

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

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

Кроме того, в задачах, решаемых интеллектуальными системами, часто при­ходится пользоваться неточными знаниями, которые не могут быть интер­претированы как полностью истинные или ложные (логические true/false или 0/1). Существуют знания, достоверность которых выражается некоторой промежуточной цифрой, например 0,7.

Как, не разрушая свойства размытости и неточности, представлять подоб­ные знания формально? Для разрешения таких проблем в начале 70-х годов XX века американский математик Лотфи Заде предложил формальный аппарат нечеткой (fuzzy) алгебры и нечеткой логики [Заде, 1972]. Позднее это направление получило широкое распространение [Орловский, 1981; Аверкин и др., 1986; Яшин, 1990] и положило начало одной из ветвей ИИ под названием мягкие вычисления (soft computing).

Л. Заде ввел одно из главных понятий в нечеткой логике — понятие лингвистической переменной.

Лингвистическая переменная (ЛП) — это переменная, значение которой определяется набором вербальных (т. е. словесных) характеристик некото­рого свойства.

Например, ЛП "рост" определяется через набор {карликовый, низкий, средний, высокий, очень высокий}.

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