Дипломная работа: Использование алгоритмов искусственного интеллекта в процессе построения UFO-моделей
Таким образом, актуальной является проблема автоматического построения модели системы из заданных компонентов.
Целью данной магистерской аттестационной работы является исследование возможности использования алгоритмов искусственного интеллекта в процессе построения UFO-моделей.
Полученные результаты можно использовать в процессе UFO-анализа, а также для внедрения в CASE-инструментарии, используемые в процессе моделирования систем.
1. Обзор современного состояния проблемы
1.1 Современные технологии построения систем
Рассмотрим стандартные методы системного структурного анализа.
Стандарт IDEF0 предназначен для создания функциональной модели, отображающей структуру и функции системы, а также потоки информации и материальных объектов, связывающих эти функции [1-4].
Диаграммы потоков данных (DFD) являются основным средством моделирования функциональных требований к проектируемой системе. С их помощью эти требования разбиваются на функциональные компоненты (процессы) и представляются в виде сети, связанной потоками данных. Главная цель таких средств – продемонстрировать, как каждый процесс преобразует свои входные данные в выходные, а также выявить отношения между этими процессами [5-6].
Стандарт IDEF3 предназначен для документирования технологических процессов, происходящих на предприятии, и предоставляет инструментарий для наглядного исследования и моделирования их сценариев [7-8].
Все вышеперечисленные стандарты поддерживаются CASE-средством моделирования и документирования бизнес-процессов BPwin. Однако весь процесс построения моделей приходится осуществлять проектировщику вручную, основываясь на своем опыте и интуиции [9-10].
Более перспективной является так называемая УФО-технология анализа и моделирования систем, в которой решается задача автоматического построения многоуровневой конфигурации из заданных компонентов. Однако если конфигурацию не удается представить в виде нескольких уровней, то автоматически не получится построить конфигурацию, не привлекая опытного проектировщика. УФО-технология поддерживается CASE-средством UFO-toolkit, использующим базу знаний специальной конфигурации, включающей в себя библиотеку УФО-элементов и классификацию связей [11-14].
1.2 Прикладные методы и технологии искусственного интеллекта
Ранние разработки искусственного интеллекта были ориентированы на создание умных машин, которые копировали поведение человека, однако в настоящее время большинство исследователей и разработчиков искусственного интеллекта преследуют более практичные цели. В число прикладных алгоритмов входят [15]:
– нейронные сети;
– генетические алгоритмы;
– системы, основанные на продукционных правилах;
– нечеткая логика;
– умные агенты;
– алгоритмы муравья.
1.2.1 Нейронные сети
В отношении систем искусственного интеллекта иногда можно услышать следующие критические замечания:
– такие системы слишком "хрупкие" в том смысле, что, встретившись с ситуацией, не предусмотренной разработчиком, они либо формируют сообщения об ошибках, либо дают неправильные результаты (другими словами, эти программы довольно просто можно "поставить в тупик");
– они не способны непрерывно самообучаться, как это делает человек в процессе решения возникающих проблем.
Еще в середине 1980-х годов многие исследователи рекомендовали использовать для преодоления этих и других недостатков нейронные сети.
В самом упрощенном виде нейронную сеть можно рассматривать как способ моделирования в технических системах принципов организации и механизмов функционирования головного мозга человека. Согласно современным представлениям, кора головного мозга человека представляет собой множество взаимосвязанных простейших ячеек – нейронов, количество которых оценивается числом порядка 1010 [16]. Технические системы, в которых предпринимается попытка воспроизвести, пусть и в ограниченных масштабах, подобную структуру (аппаратно или программно), получили наименование нейронные сети.
Нейрон головного мозга получает входные сигналы от множества других нейронов, причем сигналы имеют вид электрических импульсов. Входы нейрона делятся на две категории: возбуждающие и тормозящие. Сигнал, поступивший на возбуждающий вход, повышает возбудимость нейрона, которая при достижении определенного порога приводит к формированию импульса на выходе. Сигнал, поступающий на тормозящий вход, наоборот, снижает возбудимость нейрона. Каждый нейрон характеризуется внутренним состоянием и порогом возбудимости. Если сумма сигналов на возбуждающих и тормозящих входах нейрона превышает этот порог, нейрон формирует выходной сигнал, который поступает на входы связанных с ним других нейронов, т.е. происходит распространение возбуждения по нейронной сети. Типичный нейрон может иметь до 103 связей с другими нейронами [17].
Было обнаружено, что время переключения отдельного нейрона головного мозга составляет порядка нескольких миллисекунд, т.е. процесс переключения идет достаточно медленно. Поэтому исследователи пришли к заключению, что высокую производительность обработки информации в мозге человека можно объяснить только параллельной работой множества относительно медленных нейронов и большим количеством взаимных связей между ними. Именно этим объясняется широкое распространение термина "массовый параллелизм" в литературе, касающейся нейронных сетей.
Независимо от способа реализации, нейронную сеть можно рассматривать как взвешенный ориентированный граф. Узлы в этом графе соответствуют нейронам, а ребра – связям между нейронами. С каждой связью ассоциирован вес (рациональное число) который отображает оценку возбуждающего или тормозящего сигнала, передаваемого по этой связи на вход нейрона-реципиента, когда нейрон-передатчик возбуждается [18].
Поскольку нейронная сеть носит явно выраженный динамический характер, время является одним из основных факторов ее функционирования. При моделировании сети время изменяется дискретно, и состояние сети можно рассматривать как последовательность мгновенных снимков, причем каждое новое состояние зависит только от предыдущего цикла возбуждения нейронов [19].
Для выполнения обработки информации с помощью такой сети необходимо соблюдение определенных соглашений. Для того, чтобы сеть стала активной, она должна получить некоторый входной сигнал. Поэтому некоторые узлы сети играют роль "сенсоров" и их активность зависит от внешних источников информации. Затем возбуждение передается от этих входных узлов к внутренним и таким образом распространяется по сети. Это обычно выполняется посредством установки высокого уровня активности входных узлов, которая поддерживается в течение нескольких циклов возбуждения, а затем уровень активности сбрасывается.
Часть узлов сети используется в качестве выходных, и их состояние активности считывается в конце процесса вычислений. Но часто интерес представляет и состояние всей сети после того, как вычисления закончатся, либо состояние узлов с высоким уровнем активности. В некоторых случаях интерес может представлять наблюдение за процессом установки сети в стабильное состояние, а в других – запись уровня активизации определенных узлов перед тем, как процесс распространения активности завершится [20-24].
В контексте нейронных сетей изучается искусственная жизнь. Например, рассматривается развитие простых организмов в синтетической среде. Только избегая хищников и находя пищу, организмы выживают в среде. Воспроизводство агентов допускается только в том случае, если они выживают и достигают определенного уровня внутренней энергии. Это позволяет получать более здоровое и совершенное потомство. В качестве нейроконтроллеров для агентов выступают многослойные нейронные сети. Простые пищевые цепочки создаются с помощью двух различных типов организмов (хищника и травоядного) [25].
1.2.2 Генетические алгоритмы
Генетические алгоритмы предлагают модель оптимизации, которую можно применять при решении как числовых, так и символических задач. Генетическое программирование используется, например, при создании последовательности инструкций. Подобные последовательности применяются при решении математических задач [26].
Генетические алгоритмы отражают принципы естественного отбора и генетики: выживание наиболее перспективные особей, наследование и мутации. При этом человек не вмешивается в процесс поиска, но может опосредственно влиять на него заданием определенных параметров.
Как и все методы случайного поиска, генетические алгоритмы ориентированы на нахождение не оптимального решения, а на поиск лучшего, чем существующие на данный момент решения. Такой подход эффективен для сложных систем, где зачастую необходимо каким-то образом улучшить текущее решение, а задача поиска оптимального решения не ставится из-за сложности системы и, как следствие, невозможности применения традиционных методов, которые направлены на нахождение оптимальных решений.
Основные отличия генетических алгоритмов от традиционных методов заключаются в следующем [27].
Генетические алгоритмы оперируют с решениями, представленными в виде кодовой строки. И преобразования кодов производятся вне какой-либо связи с их семантикой.
Процесс поиска основан на использовании нескольких точек пространства решений одновременно. Это устраняет возможность нежелательного попадания в локальный экстремум целевой функции, не являющейся унимодальной.
В процессе поиска генетическим алгоритмом используется только информация о допустимых значениях параметров и целевой функции, что приводит к значительному повышению быстродействия.
Для синтеза новых точек генетический алгоритм использует вероятностные правила, а для перехода от одних точек к другим – детерминированные. Такое объединение правил значительно эффективнее, чем их раздельное использование.
При этом в теории генетических алгоритмов используется ряд биологических терминов [28].
Кодовая строка, описывающая возможное решение, и ее структура называются генотипом. Интерпретация кода с позиции решаемой задачи – фенотипом. Например, для предметной области САПР фенотипом будет некоторое проектное решение в виде структурной схемы вычислительного устройства [29-31]. Код также называют хромосомой.
Совокупность хромосом, одновременно используемых генетическим алгоритмом на каждом этапе поиска, называется популяцией. Размер популяции (число хромосом) обычно фиксируется и является одной из характеристик генетического алгоритма. Популяция обновляется созданием новых хромосом и уничтожением старых. Таким образом происходит смена поколений популяций.
Генерация новых хромосом основана на моделировании процесса размножения: пара родителей порождает пару потомков. За генерацию отвечает оператор скрещивания, который в общем случае применяется к каждой родительской паре с некоторой вероятностью. Значение этой вероятности наряду с размером популяции является одной из характеристик генетического алгоритма.
К хромосомам новой популяции применяется оператор мутации. Вероятность применения этого оператора к хромосоме также является параметром генетического алгоритма.
Оператор отбора осуществляет выбор родительских хромосом для порождения потомков, а оператор редукции – выбор хромосом, подлежащих уничтожению. В обоих случаях выбор делается на основании качества хромосомы, которое определяется значением целевой функции на этой хромосоме.
Генетический алгоритм прекращает свою работу в следующих случаях:
– он обработал число поколений, заданных пользователем перед началом работы алгоритма;
– качество всех хромосом превысило значение, заданное пользователем до начала работы алгоритма;
– хромосомы стали однородными до такой степени, что их улучшение от поколения к поколению происходит очень медленно.
В генетических алгоритмах часто используется стратегия элитизма, заключающаяся в переходе лучших хромосом текущей популяции в следующее поколение без изменений. Такой подход обеспечивает поддержание высокого уровня качества популяции.
Оператор мутации вносит случайные изменения в хромосомы, расширяя область пространства поиска.
Многократное применение операторов редукции, отбора, скрещивания и мутации способствует улучшению качества каждой отдельной хромосомы и, как следствие, популяции в целом, отражая основную цель генетического алгоритма – повышение качества начальной популяции. Основным результатом работы генетического алгоритма является хромосома конечной популяции, на которой целевая функция принимает экстремальное значение.
Генетические алгоритмы являются стратегическим подходом к решению проблемы, который необходимо адаптировать к конкретной предметной области путем задания параметров и определения операторов генетического алгоритма. При этом генетический алгоритм становиться сильно привязанным к рассматриваемой предметной области и может быть совершенно бесполезен для решения задач в другой предметной области [32].
От удачного выбора параметров, операторов и вида хромосом зависят устойчивость и скорость поиска – основных показателей эффективности генетического алгоритма. Скорость определяется временем, необходимым для достижения алгоритмом одного из указанных выше критериев останова. Устойчивость – это способность генетического алгоритма увеличивать качество популяции и выходить из локальных экстремумов.
Для увеличения скорости генетические алгоритмы могут подвергаться распараллеливанию как на уровне организации работы алгоритма, так и на уровне его реализации на ЭВМ.
На уровне организации работы распараллеливание осуществляется за счет структурирования популяции, которое может осуществляться двумя способами.
Первый способ называется "концепция островов" и заключается в разбиении популяции на классы (демосы), члены которых скрещиваются только между собой в пределах класса, лишь изредка обмениваясь хромосомами на основе случайной выборки. Второй способ называется "концепция скрещивания в локальной области" и заключается в задании метрического пространства на популяции, хромосомы которой подвергаются скрещиванию только с ближайшими соседями.
Что касается распараллеливания на уровне реализации, то как указанные выше процессы скрещивания пар родителей, так и процессы вычисления значений целевой функции и применения оператора мутации к хромосомам можно реализовать одновременно на нескольких параллельно работающих процессорах или системах.
Устойчивость поиска зависит от параметров операторов генетического алгоритма [33].
Для оператора скрещивания таким параметром служит степень отличия потомков от родительских хромосом: чем больше это отличие, тем устойчивей поиск, но скорость поиска меньше (лучший результат достигается за большее время).
Для оператора мутации параметром, влияющим на устойчивость поиска, служит вероятность его применения: малая вероятность обеспечивает устойчивый поиск и не приводит к ухудшению качества хромосом.
Оператор отбора связан с устойчивостью поиска следующим образом: постоянный выбор сильнейших хромосом обычно приводит к сходимости к локальному экстремуму, а выбор слабых хромосом – к ухудшению качества популяции. Аналогичное утверждение справедливо и для оператора редукции.
Что касается влияния размера популяции на устойчивость генетического алгоритма, то увеличение числа хромосом в популяции расширяет область поиска, но при этом время от времени полезно редуцировать популяцию до первоначального размера, иначе скорость генетического алгоритма резко упадет. Подобные алгоритмы называются поколенческими [34].
Развитие поколенческих алгоритмов привело к появлению адаптивных генетических алгоритмов, изменяющих свои параметры в процессе работы. Возникла концепция nGA, представляющая многоуровневые генетические алгоритмы, в которых нижний уровень улучшает популяцию, а верхний – оптимизирует параметры нижнего уровня, ориентируясь при этом на его скорость и устойчивость.
1.2.3 Системы, основанные на продукционных правилах
В системах продукций знания представляются с помощью наборов правил вида: "если А, то В". Здесь А и В могут пониматься как "ситуация-действие", "причина-следствие", "условие-заключение" и т.п. Часто правило-продукцию записывают с использованием знака логического следования: А Þ В.
В общем случае продукционная система включает следующие компоненты:
– базу продукционных правил;
– базу данных (рабочую память);
– интерпретатор.
