Искусственный интеллект - [158]

4. Нечеткая логика (fuzzy logic) - направление, предложенное в 1965 году профессором Калифорнийского университета Лофти Заде, сочетающее в себе подходы математической логики и теории вероятностей. В нечеткой логике, в отличие от обычной, высказывания бывают не только истинными или ложными, что позволяет учитывать неопределенности при моделировании ИИ. Для решения практических задач в этой области, качественные переменные описываются некоторой функцией распределения, после чего они уже используются как точные (например, с помощью нечеткой логики можно более точно определить понятие величины дохода человека - «маленький», «средний», «большой», «очень большой»). Согласно знаменитой теореме FAT (Fuzzy Approximation Theorem), доказанной Б. Кос-ко (Kosko (1992)), «любая математическая система может быть аппроксимирована системой, основанной на нечеткой логике.

Основные исследования в области нечеткой логики проводятся в США и Японии, а в числе результатов этих исследований - многочисленные микрочипы, используемые как в бытовой технике (стиральные машины, СВЧ-печи), так и в моторных отсеках автомобилей, в поездах метрополитена и т.д. Свое место нечеткие системы управления нашли в военной технике (например, при проектировании «умных» ракет).

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

Изложение основ нечеткой логики заняло бы слишком много места, поэтому для более детального изучения этого направления мы можем порекомендовать бестселлер Барта Коско (Kosko (1992)), в котором приводится фундаментальное изложение теории нечетких множеств.

Среди русскоязычных источников представляют интерес книги (Левнер, Птускин, Фридман (1998)), (Пивкин, Бакулин, Кореньков (1998)), а также научно-популярная статья А. Масаловича (Масалович (1995)). Кроме того, большая подборка материалов в этой области выложена по адресу:

http://dir.vahoo com/Sdence/Comouter Science/Artifidal Intelligence/

Fuzzy Logic

5. Генетические алгоритмы (ГА) это последовательность управляющих действий и операций, моделирующих эволюционные процессы на основе аналогов механизмов генетического наследования и естественного отбора, почерпнутых из биологии (Круглов, Борисов (2002)). Из определения уже ясно, что это направление берет свое начало из теории эволюции, согласно которой каждый биологический вид непрерывно развивается, чтобы наилучшим образом приспособиться к окружающей среде. Путем естественного отбора природа решает задачу оптимизации, в результате чего выживают только более приспособленные особи. Используя биологическую терминологию можно представить задачу поиска экстремума функции многих переменных следующим образом:

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

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

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

Кроссовер (или скрещивание) - операция, при которой две хромосомы обмениваются частями.

Мутация - случайное изменение хромосомы (изменение состояния одного из генов на противоположное).

Инверсия - изменение порядка генов в хромосоме (аргументе функции) путем циклической перестановки.

В ГА чаще используются первые два способа взаимодействия хромосом.

Последовательность действий ГА выглядит следующим образом:

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

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

Шаг 3. преобразование аргументов функции в двоичный формат;

Шаг. 4 применение операций скрещивания и мутации для всего набора хромосом (популяции). На этом шаге количество особей в популяции возрастает;

Шаг 5. селекция популяции - формирование новой популяции из старой, путем отбора новых хромосом и удаления старых, после чего старая популяция вымирает;

Шаг. 6. обратное преобразование аргументов функции в десятеричный формат;

Шаг 7. расчет целевой функции и проверка ее значений со значениями, полученными в предыдущем цикле вычислений. Если оно стало больше (в случае поиска максимума функции), то такой набор хромосом запоминается;