Дипломная работа: Использование алгоритмов искусственного интеллекта в процессе построения UFO-моделей

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

Устойчивость поиска зависит от параметров операторов генетического алгоритма [33].

Для оператора скрещивания таким параметром служит степень отличия потомков от родительских хромосом: чем больше это отличие, тем устойчивей поиск, но скорость поиска меньше (лучший результат достигается за большее время).

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

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

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

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

1.2.3 Системы, основанные на продукционных правилах

В системах продукций знания представляются с помощью наборов правил вида: "если А, то В". Здесь А и В могут пониматься как "ситуация-действие", "причина-следствие", "условие-заключение" и т.п. Часто правило-продукцию записывают с использованием знака логического следования: А Þ В.

В общем случае продукционная система включает следующие компоненты:

– базу продукционных правил;

– базу данных (рабочую память);

– интерпретатор.

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

Предпосылка правила часто рассматривается как образец. Образец – это некоторая информационная структура, определяющая обобщенную ситуацию окружающей действительности, при которой активизируется правило. Рабочая память отражает конкретные ситуации, возникающие во внешней среде. Информационная структура, представляющая конкретную ситуацию внешней среды в рабочей памяти, называется образом [35].

Интерпретатор реализует логический вывод. Процесс вывода является циклическим и называется поиском по образцу. Рассмотрим его в упрощенной форме. Текущее состояние моделируемой предметной области отражается в рабочей памяти в виде совокупности образов, каждый из которых представляется посредством фактов. Рабочая память инициализируется фактами, описывающими задачу. Затем выбираются те правила, для которых образцы, представляемые предпосылками правил, сопоставимы с образами в рабочей памяти. Данные правила образуют конфликтное множество. Все правила, входящие в конфликтное множество могут быть активизированы. В соответствии с выбранным механизмом разрешения конфликта активизируется одно из правил. Выполнение действия, содержащегося в заключении правила, приводит к изменению состояния рабочей памяти. В дальнейшем цикл управления выводом повторяется. Указанный процесс завершается, когда не окажется правил, предпосылки которых сопоставимы с образами рабочей памяти [36].

Таким образом, процесс вывода, основанный на поиске по образцу, состоит из четырех шагов:

– выбор образа;

– сопоставление образа с образцом и формирование конфликтного набора правил;

– разрешение конфликтов;

– выполнение правила.

Широкое применение продукционных моделей определяется следующими основными достоинствами:

– универсальностью (практически любая область знаний может быть представлена в продукционной форме);

– модульностью (каждая продукция представляет собой элемент знаний о предметной области, удаление одних и добавление других продукций выполняется независимо);

– декларативностью (продукции определяют ситуации предметной области, а не механизм управления);

– естественностью процесса вывода заключений, который во многом аналогичен процессу рассуждений эксперта;

– асинхронностью и естественным параллелизмом, который делает их весьма перспективным для реализации на параллельных ЭВМ.

Однако продукционные системы не свободны от недостатков:

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