Міністерствоосвіти і науки України
Харківськийнаціональний університет радіоелектроніки
Факультетприкладної математики та менеджменту
Кафедрасоціальної інформатики
Магістерська атестаційна робота
Пояснювальна записка
2071197.ПЗ
Використанняалгоритмів штучного інтелекту у процесі побудови UFO-моделей
Магістрант гр. КСмаг-05-1
Сергієнко І.М.
Науковий керівник
доц. Єльчанінов Д.Б.
Допускається до захисту
Зав. Кафедри
Соловйова К.О.
2009
Харківськийнаціональний університет радіоелектроніки
ФакультетПММ
КафедраСІ
Спеціальність8.000012 – «Консолідована інформація»
Завдання
на магістерську атестаційну роботу
магістрантовіСергієнко Івану Миколайовичу
1. Тема роботиВикористання алгоритмів штучного інтелекту у процесі побудови UFO-моделей затвердженанаказом по університету від " 12 «квітня2006 р. №556 Ст
2. Термін здачі магістрантом закінченоїроботи12.06.2006
3. Вихідні дані до роботи основні алгоритми штучного інтелекту, основні поняття UFO-аналізу
4. Зміст пояснювальної записки (перелік питань, що їх потрібнорозробити) перелік умовних позначень,символів, одиниць, скорочень і термінів; вступ; огляд сучасного стану проблеми;адаптація алгоритму мурахи до процесу UFO-моделювання; використання Microsoft Excel упроцесі UFO-моделювання на основі алгоритму мурахи; UFO-моделі шахтної транспортноїсистеми;
Висновки
5. Перелік графічного матеріалу (з точним зазначенням обов’язковихкреслень, плакатів)
тема роботи;актуальність дослідження; мета дослідження; постановка задачі;
адаптаціяалгоритму мурахи до процесу UFO-моделювання;
використанняMicrosoft Excel у процесі UFO-моделювання на основі алгоритму мурахи;
UFO-моделішахтної транспортної системи; висновки; апробація результатів
6. Консультанти з роботи із зазначеннямрозділів роботи, що їх стосуються (п.6 заповнюється в разі необхідності)Найменування розділу Консультант (посада, прізвище, ім’я, по батькові)
Позначка консультанта
про виконання розділу (підпис) (дата)
7. Дата видачізавдання13.03.06
Науковий керівник доц. Єльчанінов Дмитро Борисович
Завдання прийнявдо виконання Сергієнко Іван Миколайович
Календарний план№ Назва етапів магістерської атестаційної роботи Термін виконання етапів роботи Примітка 1 Аналіз проблемної області та постановка задачі 03.04.06 2 Адаптація алгоритму мурахи до процесу UFO-моделювання 17.04.06 3 Використання Microsoft Excel у процесі моделювання на основі алгоритму мурахи 01.05.06 4 Розробка UFO-моделей шахтної транспортної системи 15.05.06 5 Підготовка пояснювальної записки. 29.05.06 6 Підготовка презентації та доповіді 05.06.06 7 Попередній захист 12.06.06 8 Нормоконтроль, рецензування 14.06.06 9 Занесення диплома в електронний архів 15.06.06 10 Допуск до захисту у зав. кафедрою 16.06.06
Магістрант Сергієнко Іван Миколайович
Науковий керівникЄльчанінов Д.Б.
Реферат
Пояснювальназаписка: 44 рис., 1 додаток, 46 джерел.
Об’єктдослідження – процес побудови UFO-моделей.
Мета роботи – дослідження можливості використанняалгоритмів штучного інтелекту у процесі побудови UFO-моделей.
Методидослідження – методи штучного інтелекту тасучасні комп’ютерні технології обробки табличних даних.
Результати роботи– адаптація алгоритму мурахи до процесу UFO-моделювання; використання Microsoft Excel у процесі UFO-моделювання на основіалгоритму мурахи; UFO-моделі шахтної транспортної системи.
штучний інтелект, алгоритм мурахи, UFO-аналіз, моделювання,табличний процесор
Реферат
Пояснительная записка: 44рис., 1 приложение, 46 источников.
Объект исследования – процесс построения UFO-моделей.
Цель работы –исследование возможности использованияалгоритмов искусственного интеллекта в процессе построения UFO-моделей.
Методы исследования –методы искусственногоинтеллекта и современныекомпьютерные технологии обработки табличных данных.
Результаты работы –адаптация алгоритма муравья к процессу UFO-моделирования; использование Microsoft Excel в процессе UFO-моделирования на основе алгоритма муравья; UFO-модели шахтной транспортной системы.
искусственныйинтеллект, Алгоритм муравья, UFO-анализ,МОДЕЛИРОВАНИЕ, табличный процессор
ABSTRACT
Explanatorynote: 44 fig., 1 appendix, 46 references.
Researchobject – process of UFO-models construction.
Work purpose –researching of possibility of artificial intelligence methods using in processof UFO-models construction.
Research methods – artificial intelligencemethods and modern computer technologies of tabular data processing.
Work results –ant algorithm adaptation to UFO-modeling process; Microsoft Excel using inUFO-modeling process based on ant algorithm; UFO-models of mining transportsystem.
artificial intelligence, ant algorithm, UFO-analysis, modeling,tabular processor
Содержание
Перечень условных обозначений, символов, единиц, сокращений итерминов
Введение
1. Обзор современного состояния проблемы
1.1 Современные технологии построения систем
1.2 Прикладныеметоды и технологии искусственного интеллекта
1.2.1 Нейронные сети
1.2.2 Генетические алгоритмы
1.2.3 Системы, основанные на продукционных правилах
1.2.4 Нечеткая логика
1.2.5 Умные агенты
1.2.6 Алгоритммуравья
1.3 Постановка задачи
2. Адаптация алгоритма муравья к задаче построения UFO-модели из заданных компонентов
2.1 Начальное размещение муравья
2.2 Правила соединения UFO-компонентов
2.3 Элементарное перемещение муравья
2.3.1 Перемещение из входа контекстной диаграммы
2.3.2 Перемещение из выхода контекстной диаграммы
2.3.3 Перемещение из входа UFO-компонента
2.3.4 Перемещение из выхода UFO-компонента
2.3.5 Пример перемещений муравья
2.4. Перемещение нескольких муравьев
2.4.1 Разрешение конфликтов
2.4.2 Пример перемещений нескольких муравьев
3. Пример использования Microsoft Excel в процессе построения UFO-модели из заданных компонентов на основе алгоритма муравья
4. Использование алгоритма муравья в процессеUFO-моделирования шахтнойтранспортной системы
4.1 Общие сведения о подразделении „Шахта “Комсомольская»"
4.2 Подготовка и вскрытие шахтного поля
4.3 UFO-модельшахтной транспортной системы
Выводы
Перечень ссылок
искусственный интеллект компьютерный муравейшахтный
Переченьусловных обозначений, символов, единиц, сокращенийи терминов
CASE – computer-aidedsystem engineering;
DFD – диаграммы потоков данных;
IDEF0 – стандарт функционального моделирования;
IDEF3– стандарт документирования технологических процессов;
Муравей – программныйагент, который является членом большой колонии и используется для решениякакой-либо проблемы;
УФО –Узел-Функция-Объект.
Введение
В современных технологияханализа и моделирования систем процесс построения моделей приходитсяосуществлять проектировщику вручную, основываясь на своем опыте и интуиции спомощью CASE-средств.
Современные прикладныеметоды и технологии искусственного интеллекта (нейронные сети, генетическиеалгоритмы, нечеткая логика, умные агенты, алгоритмы муравья и т.п.)ориентированы не столько на копирование поведения человека, сколько надостижение результатов, аналогичных человеческим результатам.
Для автоматического построенияконфигурации системы целесообразно применить алгоритм муравья, который внастоящее время широко используется для поиска оптимальных путей по графу.
Таким образом, актуальнойявляется проблема автоматического построения модели системы из заданных компонентов.
Целью данной магистерскойаттестационной работы является исследование возможности использования алгоритмов искусственного интеллекта в процессе построения 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 Системы, основанныена продукционных правилах
В системах продукцийзнания представляются с помощью наборов правил вида: «если А, то В».Здесь А и В могут пониматься как «ситуация-действие», «причина-следствие»,«условие-заключение» и т.п. Часто правило-продукцию записывают сиспользованием знака логического следования: А Þ В.
В общем случаепродукционная система включает следующие компоненты:
– базу продукционных правил;
– базу данных (рабочую память);
– интерпретатор.
Множество продукционныхправил образует базу правил, каждое из которых представляет обособленныйфрагмент знаний о решаемой проблеме. Психологи называют такие фрагменты чанками(от англ. chunk). Считается, что чанк – этообъективно существующая единица знаний, выделяемая человеком в процессепознания окружающего мира.
Предпосылка правила часторассматривается как образец. Образец – это некоторая информационная структура,определяющая обобщенную ситуацию окружающей действительности, при которойактивизируется правило. Рабочая память отражает конкретные ситуации,возникающие во внешней среде. Информационная структура, представляющаяконкретную ситуацию внешней среды в рабочей памяти, называется образом [35].
Интерпретатор реализуетлогический вывод. Процесс вывода является циклическим и называется поиском пообразцу. Рассмотрим его в упрощенной форме. Текущее состояние моделируемойпредметной области отражается в рабочей памяти в виде совокупности образов,каждый из которых представляется посредством фактов. Рабочая памятьинициализируется фактами, описывающими задачу. Затем выбираются те правила, длякоторых образцы, представляемые предпосылками правил, сопоставимы с образами врабочей памяти. Данные правила образуют конфликтное множество. Все правила,входящие в конфликтное множество могут быть активизированы. В соответствии свыбранным механизмом разрешения конфликта активизируется одно из правил.Выполнение действия, содержащегося в заключении правила, приводит к изменениюсостояния рабочей памяти. В дальнейшем цикл управления выводом повторяется.Указанный процесс завершается, когда не окажется правил, предпосылки которыхсопоставимы с образами рабочей памяти [36].
Таким образом, процессвывода, основанный на поиске по образцу, состоит из четырех шагов:
– выбор образа;
– сопоставление образа с образцом иформирование конфликтного набора правил;
– разрешение конфликтов;
– выполнение правила.
Широкое применениепродукционных моделей определяется следующими основными достоинствами:
– универсальностью (практически любаяобласть знаний может быть представлена в продукционной форме);
– модульностью (каждая продукцияпредставляет собой элемент знаний о предметной области, удаление одних идобавление других продукций выполняется независимо);
– декларативностью (продукцииопределяют ситуации предметной области, а не механизм управления);
– естественностью процесса выводазаключений, который во многом аналогичен процессу рассуждений эксперта;
– асинхронностью и естественнымпараллелизмом, который делает их весьма перспективным для реализации напараллельных ЭВМ.
Однако продукционныесистемы не свободны от недостатков:
– процесс вывода имеет низкуюэффективность, так как при большом числе продукций значительная часть временизатрачивается на непроизводительную проверку условия применения правил;
– проверка непротиворечивости системыпродукций становится весьма сложной из-за недетерминированности выборавыполняемой продукции из конфликтного множества.
В системах, основанных направилах, часто акцент делается на системах прямого логического вывода.Например, в качестве правил и начальных фактов используется ряд примеров, чтопозволяет встроить систему с правилами в более крупную систему и задействоватьее для создания системы управления сенсорами, устойчивой к ошибкам [37].
1.2.4 Нечеткая логика
Ту роль, которую вклассической теории множеств играет двузначная булева логика, в теории нечеткихмножеств играет многозначная нечеткая логика, в которой предположения опринадлежности объекта множеству, например Быстрый(«Порш»), могутпринимать действительные значения в интервале от 0 до 1. Возникает вопрос, акак, используя концепцию неопределенности, вычислить значение истинностисложного выражения, такого как Не(Быстрый(«Шевроле»)).
По аналогии с теориейвероятности, если F представляетсобой нечеткий предикат, операция отрицания реализуется по формуле Не(F)=1–F.
Но аналоги операцийконъюнкции и дизъюнкции в нечеткой логике не имеют никакой связи с теориейвероятностей [38]. Рассмотрим следующее выражение: "«Порш»является быстрым, представительским автомобилем".
В классической логикепредположение (Быстрый(«Порш»)) И (Представительский («Порш»))является истинным в том и только в том случае, если истинны оба членаконъюнкции. В нечеткой логике существует соглашение: если F и G являются нечеткими предикатами, то f(FÙG)(X)=min(fF(X), fG(X)).
Таким образом, еслиБыстрый(«Порш»)=0,9 и Представительский(«Порш»)=0,7, то(Быстрый(«Порш»))И(Представительский («Порш»)) = 0,7.
А теперь рассмотримвыражение (Быстрый(«Порш»)) И Не(Быстрый(«Порш»)).Вероятность истинности этого утверждения равна 0, но в нечеткой логике значениеэтого выражения будет равно 0,1. Какой смысл имеет это значение? Его можносчитать показателем принадлежности автомобиля к нечеткому множествусреднескоростных автомобилей, которые в чем-то близки к быстрым, а в чем-то – кмедленным.
Смысл выражения Быстрый(«Порш»)=0,9заключается в том, что мы только на 90% уверены в принадлежности этогоавтомобиля к быстрым именно из-за неопределенности самого понятия «быстрыйавтомобиль». Вполне резонно предположить, что существует некоторая уверенностьв том, что «Порш» не принадлежит к быстрым. Например, он медленнееавтомобиля, принимающего участие в гонках «Формула-1».
Аналог операциидизъюнкции в нечеткой логике определяется следующим образом: f(FÚG)(X)=max(fF(X), fG(X)).
Операторы обладаютсвойствами коммутативности, ассоциативности и взаимной дистрибутивности. Как коператорам в стандартной логике, к ним применим принцип композитивности, т.е.значения составных выражений вычисляются только по значениям выражений-компонентов.В этом операторы нечеткой логики составляют полную противоположность законамтеории вероятностей, согласно которым при вычислении вероятностей конъюнкции идизъюнкции величин нужно принимать во внимание условные вероятности [39].
Нечеткая логика имеетдело с ситуациями, когда и сформулированный вопрос, и знания, которыми мырасполагаем, содержат нечетко очерченные понятия. Однако нечеткостьформулировки понятий является не единственным источником неопределенности.Иногда мы просто не уверены в самих фактах. Если утверждается: «Возможно,Иван сейчас в Киеве», то говорить о нечеткости понятий Иван и Киев неприходится. Неопределенность заложена в самом факте, действительно ли Иваннаходится в Киеве.
Теория возможностейявляется одним из направлений в нечеткой логике, в котором рассматриваютсяточно сформулированные вопросы, базирующиеся на неточных знаниях.
На основе нечеткой логикичасто строятся системы управления. Например, в модели зарядного устройства длябатарей функции содержат не только стандартные операторы нечеткой логики, но ивспомогательные функции, которые поддерживают создание функций нечеткой логики[40].
1.2.5 Умные агенты
Агент – это аппаратнаяили программная сущность, способная действовать в интересах достижения целей,поставленных перед ним владельцем и/или пользователем [41].
Проблематикаинтеллектуальных агентов и мультиагентных систем имеет уже почти 40-летнююисторию и сформировалась на основе результатов, полученных в рамках работ пораспределенному искусственному интеллекту, распределенному решению задач ипараллельному искусственному интеллекту. Но, пожалуй, лишь в последнеедесятилетие она выделилась в самостоятельную область исследований и приложенийи все больше претендует на одну из ведущих ролей в рамках интеллектуальныхинформационных технологий. Спектр работ по данной тематике весьма широк,интегрирует достижения в области компьютерных сетей и открытых систем,искусственного интеллекта и информационных технологий и ряда другихисследований, а результаты уже сегодня позволяют говорить о новом качествеполучаемых решений.
В настоящее времямножество исследовательских лабораторий, университетов, фирм и промышленныхорганизаций работают в этой области, и список их постоянно расширяется. Онвключает мало известные имена и небольшие коллективы, уже признанныеисследовательские центры и организации, а также огромные транснациональныекомпании. Областями практического использования агентных технологий являются:
– управление информационными потоками исетями;
– управление воздушным движением;
– информационный поиск;
– электронная коммерция;
– обучение;
– электронные библиотеки.
К построениюагентно-ориентированных систем можно указать два подхода: реализацияединственного автономного агента или разработка мультиагентной системы.Автономный агент взаимодействует только с пользователем и реализует весь спектрфункциональных возможностей, необходимых в рамках агентно-ориентированнойпрограммы. В противовес этому мультиагентные системы являютсяпрограммно-вычислительными комплексами, где взаимодействуют различные агентыдля решения задач, которые трудны или недоступны в силу своей сложности дляодного агента. Часто такие мультиагентные системы называют агентствами, врамках которых агенты общаются, кооперируются и договариваются между собой дляпоиска решения поставленной перед ними задачи.
Агентные технологииобычно предполагают использование определенных типологий агентов и их моделей,архитектур мультиагентных систем и опираются на соответствующие агентныебиблиотеки и средства поддержки разработки разных типов мультиагентных систем.
Умные агенты применяютсяразличными способами. Например, существует агент-фильтр, использующийся дляфильтрации информации из сети Интернет. Параметры поиска Web-агента задаются в простом файле конфигурации.Затем агент автономно собирает новости через протокол NNTP и предоставляет их пользователю с помощью HTTP-протокола, действуя аналогично Web-серверу [42].
1.2.6 Алгоритм муравья
Алгоритмы муравья – этосравнительно новый метод, который может использоваться для поиска оптимальныхпутей по графу. Данные алгоритмы симулируют движение муравьев в окружающейсреде и используют модель ферментов для коммуникации с другими агентами [43].
Хотя муравьи и слепы, ониумеют перемещаться по сложной местности, находить пищу на большом расстоянии отмуравейника и успешно возвращаться домой. Выделяя ферменты во времяперемещения, муравьи изменяют окружающую среду, обеспечивают коммуникацию, атакже отыскивают обратный путь в муравейник.
Самое удивительное вданном процессе – это то, что муравьи умеют находить самый оптимальный путьмежду муравейником и внешними точками. Чем больше муравьев используют один итот же путь, тем выше концентрация ферментов на этом пути. Чем ближе внешняяточка к муравейнику, тем больше раз к ней перемещались муравьи. Что касаетсяболее удаленной точки, то ее муравьи достигают реже, поэтому по дороге к нейони применяют более сильные ферменты. Чем выше концентрация ферментов на пути,тем предпочтительнее он для муравьев по сравнению с другими доступными. Такмуравьиная «логика» позволяет выбирать более короткий путь междуконечными точками.
Алгоритмы муравьяинтересны, поскольку отражают ряд специфических свойств, присущих самиммуравьям. Муравьи легко вступают в сотрудничество и работают вместе длядостижения общей цели. Алгоритмы муравья работают так же, как муравьи. Этовыражается в том, что смоделированные муравьи совместно решают проблему ипомогают другим муравьям в дальнейшей оптимизации решения.
Рассмотрим пример [15].Два муравья из муравейника должны добраться до пищи, которая находится запрепятствием. Во время перемещения каждый муравей выделяет немного фермента,используя его в качестве маркера.
При прочих равных каждыймуравей выберет свой путь. Пусть первый муравей выбирает путь, который в двараза длиннее, чем путь, выбранный вторым муравьем. Так как путь второго муравьяв два раза короче пути первого муравья, то, когда второй муравей достигнетцели, первый муравей в этот момент пройдет только половину пути.
Когда муравей достигаетпищи, он берет один из объектов и возвращается к муравейнику по тому же пути.Когда второй муравей вернется в муравейник с пищей, первый муравей еще толькодостиг пищи.
При перемещении каждогомуравья на пути остается немного фермента. Для первого муравья за это времяпуть был покрыт ферментом только один раз. В то же самое время второй муравейпокрыл путь ферментом дважды. Когда первый муравей вернется в муравейник,второй муравей уже успеет еще раз сходить к еде и вернуться. При этомконцентрация фермента на пути второго муравья будет в два раза выше, чем напути первого. Поэтому первый муравей в следующий раз выберет путь второгомуравья, поскольку там концентрация фермента выше.
В этом и состоит базоваяидея алгоритма муравья – оптимизация путем непрямой связи между автономнымиагентами.
1.3 Постановка задачи
Проведенный анализсовременного состояния проблемы показывает, что:
– в современных технологиях построениясистем процесс построения моделей приходится осуществлять проектировщикувручную, основываясь на своем опыте и интуиции с помощью CASE-средств;
– современные прикладные методы итехнологии искусственного интеллекта ориентированы не столько на копированиеповедения человека, сколько на достижение результатов, аналогичных человеческимрезультатам;
– для автоматического построениямоделей систем целесообразно применить алгоритм муравья.
Целью данной магистерскойаттестационной работы является исследование возможности использования алгоритмов искусственного интеллекта в процессе построения UFO-моделей.
Достижениесформулированной цели связано с решением следующих задач:
– адаптация алгоритма муравья кпроцессу построения UFO-модели иззаданных компонентов;
– использование Microsoft Excel в процессе построения UFO-модели из заданных компонентов;
– применение полученных результатов впроцессе UFO-моделирования.
2.Адаптация алгоритма муравья к задаче построения UFO-модели иззаданных компонентов
2.1 Начальное размещениемуравья
Пусть задана контекстнаядиаграмма системы, определяющая ее множество входов и выходов (рис. 2.1).
/>
Рисунок 2.1 – Контекстнаядиаграмма системы
Изначально муравей можетнаходиться в одной из двух видов точек [44]:
– в конце любой входной стрелки In (n) (n = 1,2, …, N);
– в начале любой выходной стрелки Out (m) (m = 1,2, …, M).
Например, контекстнаядиаграмма системы может иметь два входа (In (1), In(2)) и три выхода (Out (1), Out (2), Out (3)), а муравей – находиться в конце входной стрелки In (1). Данная ситуация иллюстрируетсярис. 2.2, на котором муравей условно изображен жирной точкой.
/>
Рисунок 2.2 – Пример начальногоразмещения муравья
2.2 Правила соединения UFO-компонентов
Пусть задана библиотекакомпонентов />, из которых необходимособрать систему, заданную контекстной диаграммой, изображенной на рис. 2.1.Каждый компонент /> библиотеки тожехарактеризуется своим множеством входов />,а также – своим множеством выходов /> (рис.2.3).
/>
Рисунок 2.3 – Контекстнаядиаграмма компонента />
Входы и выходыконтекстной диаграммы системы и компонентов имеют такую характеристику как тип.Существуют следующие правила соединения входов и выходов [11]. Вход In (n)контекстной диаграммы системы может быть присоединен к входу /> компонента />, если тип In (n) совпадаетс типом />. Это условие совпадениетипов можно записать в виде равенства /> (рис.2.4).
/>
Рисунок 2.4 – Соединениевхода с входом
Выход Out (m) контекстной диаграммы системы может быть присоединен квыходу /> компонента />, если тип Out (m) совпадает с типом />.Это условие можно записать в виде равенства /> (рис.2.5).
/>
Рисунок 2.5 – Соединениевыхода с выходом
Выход /> компонента /> может быть присоединен квходу /> компонента />, если тип /> совпадает с типом/>. Это условие можнозаписать в виде равенства /> (рис.2.6).
/>
Рисунок 2.6 – Соединениевыхода с входом
Пусть контекстнаядиаграмма системы имеет вход a ивыход b (рис. 2.7).
/>
Рисунок 2.7 – Примерконтекстной диаграммы системы
Пусть в библиотекукомпонентов входит компонент С1 с входом a и выходом c икомпонент С2 с входом c ивыходом b (рис. 2.8).
/>
Рисунок 2.8 – Примерыконтекстных диаграмм компонентов
Тогда вход a и выход b системы могут быть соединены с помощью компонентов С1и С2 так, как показано на рис. 2.9.
/>
Рисунок 2.9 – Примерысоединений компонентов
2.3 Элементарноеперемещение муравья
2.3.1 Перемещение извхода контекстной диаграммы
Пусть изначально муравейнаходится в конце входной стрелки In (n). Он может случайным образом выбратьиз библиотеки компонентов любой компонент />,у которого есть вход />, который можноприсоединить к входу In (n). После присоединения входа /> компонента /> к входу In (n) контекстной диаграммы, муравей «переползает» повходу /> на компонент /> и пытается присоединять «висящие»входы компонента /> либо к ещесвободным входам контекстной диаграммы системы, либо к еще свободным выходамдругих компонентов. Аналогично муравей пытается присоединять «висящие»выходы компонента /> либо к ещесвободным выходам контекстной диаграммы системы, либо к еще свободным входамдругих компонентов (рис. 2.10).
/>
Рисунок 2.10 –Присоединение компонента к входу системы
Если послевышеперечисленных действий муравья у компонента /> неосталось «висящих» входов и выходов, то муравей «выползает»из компонента /> по входу />, через который он попал вэтот компонент. На этом перемещения муравья прекращаются.
Если же у компонента /> остались «висящие»входы и выходы, то муравей случайным образом размещается на любом из них. Еслимуравей оказался в конце «висящего» входа компонента />, то далее он должендействовать так, как описано ниже в пункте 2.3.3. Если муравей оказался вначале «висящего» выхода компонента />,то далее он должен действовать так, как описано ниже в пункте 2.3.4.
2.3.2 Перемещение извыхода контекстной диаграммы
Пусть изначально муравейнаходится в начале выходной стрелки Out (m). Он может случайным образом выбратьиз библиотеки компонентов любой компонент />,у которого есть выход />, который можноприсоединить к выходу Out (m). После присоединения выхода /> компонента /> к выходу Out (m) контекстной диаграммы, муравей «переползает» повыходу /> на компонент /> и пытается присоединять «висящие»входы компонента /> либо к ещесвободным входам контекстной диаграммы системы, либо к еще свободным выходамдругих компонентов. Аналогично муравей пытается присоединять «висящие»выходы компонента /> либо к ещесвободным выходам контекстной диаграммы системы, либо к еще свободным входамдругих компонентов (рис. 2.11).
/>
Рисунок 2.11 –Присоединение компонента к выходу системы
Если послевышеперечисленных действий муравья у компонента /> неосталось «висящих» входов и выходов, то муравей «выползает»из компонента /> по выходу />, через который он попал вэтот компонент. На этом перемещения муравья прекращаются.
Если же у компонента /> остались «висящие»входы и выходы, то муравей случайным образом размещается на любом из них. Еслимуравей оказался в конце «висящего» входа компонента />, то далее он должендействовать так, как описано ниже в пункте 2.3.3. Если муравей оказался вначале «висящего» выхода компонента />,то далее он должен действовать так, как описано ниже в пункте 2.3.4.
2.3.3 Перемещение извхода UFO-компонента
Пусть изначально муравейнаходится в начале входной стрелки /> компонента/>. Он может случайнымобразом выбрать из библиотеки компонентов любой компонент />, у которого есть выход />, который можноприсоединить к входу />. Послеприсоединения выхода /> компонента /> к входу /> компонента />, муравей «переползает»по выходу /> на компонент /> и пытается присоединять «висящие»входы компонента /> либо к ещесвободным входам контекстной диаграммы системы, либо к еще свободным выходамдругих компонентов. Аналогично муравей пытается присоединять «висящие»выходы компонента /> либо к ещесвободным выходам контекстной диаграммы системы, либо к еще свободным входамдругих компонентов (рис. 2.12).
/>
Рисунок 2.12 –Присоединение компонента /> к входукомпонента />
Если послевышеперечисленных действий муравья у компонента /> неосталось «висящих» входов и выходов, то муравей «переползает»из компонента /> по выходу /> назад через вход /> в компонент />. Если у компонента /> еще остались «висящие»входы и выходы, то муравей случайным образом размещается на любом из них. Иначе– покидает компонент /> по тому пути, покоторому он на него попал.
Если же у компонента /> остались «висящие»входы и выходы, то муравей случайным образом размещается на любом из них.
2.3.4 Перемещение извыхода UFO-компонента
Пусть изначально муравейнаходится в конце выходной стрелки /> компонента/>. Он может случайнымобразом выбрать из библиотеки компонентов любой компонент />, у которого есть вход />, который можноприсоединить к выходу />. Послеприсоединения входа /> компонента /> к выходу /> компонента />, муравей «переползает»по входу /> на компонент /> и пытается присоединять «висящие»входы компонента /> либо к ещесвободным входам контекстной диаграммы системы, либо к еще свободным выходамдругих компонентов. Аналогично муравей пытается присоединять «висящие»выходы компонента /> либо к ещесвободным выходам контекстной диаграммы системы, либо к еще свободным входамдругих компонентов (рис. 2.13).
/>
Рисунок 2.13 –Присоединение компонента /> квыходу компонента />
Если послевышеперечисленных действий муравья у компонента /> неосталось «висящих» входов и выходов, то муравей «переползает»из компонента /> по входу /> назад через выход /> в компонент />. Если у компонента /> еще остались «висящие»входы и выходы, то муравей случайным образом размещается на любом из них. Иначе– покидает компонент /> по тому пути, покоторому он на него попал.
Если же у компонента /> остались «висящие»входы и выходы, то муравей случайным образом размещается на любом из них.
2.3.5 Пример перемещениймуравья
Пусть контекстнаядиаграмма системы имеет два входа (a и b) и два выхода (c и d), а муравей находится в конце входа b (рис. 2.14).
/>
Рисунок 2.14 –Контекстная диаграмма с двумя входами и двумя выходами
Пусть в библиотекекомпонентов находятся (рис. 2.15):
– компонент С1 с входами b, e и выходом d;
– компонент С2 с входом a и выходами e, f;
– компонент С3 с входом f и выходом c.
/>
Рисунок 2.15 – Примербиблиотеки компонентов
Первое перемещениемуравей делает следующим образом.
Вначале он выбирает избиблиотеки компонент С1, у которого есть вход b, который можно присоединить к входу b контекстной диаграммы.
После присоединения входаb компонента С1 к входу b контекстной диаграммы, муравей «переползает»по входу b на компонент С1 иприсоединяет «висящий» выход d компонента С1 к еще свободному выходу d контекстной диаграммы системы.
У компонента С1остался «висящий» вход e, вначале которого и размещается муравей (рис. 2.16).
/>
Рисунок 2.16 – Первый ходмуравья
Второе перемещениемуравей делает следующим образом.
Вначале он выбирает избиблиотеки компонент С2, у которого есть выход e, который можно присоединить к входу e компонента С1.
После присоединениявыхода e компонента С2 к входу e компонента С1, муравей «переползает»по входу e на компонент С2 иприсоединяет «висящий» вход a компонента С2 к еще свободному входу a контекстной диаграммы системы.
У компонента С2остался «висящий» выход f, в конце которого и размещается муравей (рис. 2.17).
/>
Рисунок 2.17 – Второй ходмуравья
Третье перемещениемуравей делает следующим образом.
Вначале он выбирает избиблиотеки компонент С3, у которого есть вход f, который можно присоединить к выходуf компонента С2. Послеприсоединения входа f компонента С3к выходу f компонента С2, муравей «переползает»по выходу f на компонент С3 иприсоединяет «висящий» выход c компонента С3 к еще свободному выходу c контекстной диаграммы системы (рис.2.18).
/>
Рисунок 2.18 – Третий ходмуравья
У компонента С3не осталось «висящих» входов и выходов. Поэтому муравей «переползает»обратно по связи f на компонент С2.У компонента С2 тоже не осталось «висящих» входов ивыходов. Поэтому муравей «переползает» обратно по связи e на компонент С1. Укомпонента С1 тоже не осталось «висящих» входов и выходов.Поэтому муравей «переползает» обратно по связи b на вход b контекстной диаграммы системы.
Муравей вернулся вначальное положение, поэтому его перемещения на этом прекращаются.
Присоединяя «висящие»входы или выходы компонента, муравей в первую очередь должен пытаться ихприсоединять к еще свободным входам или выходам контекстной диаграммы системы,а уже потом – к «висящим» входам или выходам других компонентов.
Наконец, из библиотекикомпонентов муравью, вероятно, следует выбирать для присоединения тоткомпонент, у которого в результате окажется меньше «висящих» входов ивыходов. Хотя такая локальная оптимальность вовсе не гарантирует того, чтопроцесс построения системы из заданных компонентов закончится быстрее.
2.4 Перемещениенескольких муравьев
Естественно, что сборкасистемы из заданных компонентов будет производиться гораздо быстрее, если еебудет осуществлять не один муравей, но несколько. Количество муравьев можетзадаваться произвольным образом. Например, их можно разместить по одному вконце каждого входа и в начале каждого выхода контекстной диаграммы системы.Однако при этом возникает проблема разрешения конфликтов при попытке разныхмуравьев присоединить, например, к одному свободному выходу контекстнойдиаграммы, «висящие» выходы своих компонентов (рис. 2.19).
/>
Рисунок 2.19 – Конфликтдвух муравьев
2.4.1 Разрешениеконфликтов
Можно предложитьнесколько способов разрешения конфликтов муравьев при доступе к одним ресурсам.
Например, можно назначитьмуравьям приоритеты – целые числа от 1 до V, где V –количество муравьев. Чем меньше число, тем выше приоритет. Таким образом, самыйвысокий приоритет имеет муравей, которому сопоставлено число 1, а самый низкий– муравей, которому сопоставлено число V. Если два муравья конфликтуют, то предпочтение отдаетсятому, у которого выше приоритет. Например, если у муравьев, изображенных вышена рис. 2.19, приоритеты назначены так, что муравей, находящийся на выходе c компонента C1, имеет приоритет 7, а муравей, находящийся на выходе c компонента C2, имеет приоритет 9, то их конфликт за выход c контекстной диаграммы системыразрешиться в пользу муравья, находящегося на выходе c компонента C1, который имеет более высокийприоритет по сравнению с муравьем, находящимся на выходе c компонента C2. Результат разрешения конфликта этих двух муравьев показанна рис. 2.20.
/>
Рисунок 2.20 – Разрешениеконфликта двух муравьев
Другим способом можетбыть разрешение конфликта, основанное на присоединении к свободной связи любойслучайным образом выбранной «висящей» связи.
Наконец, предпочтениеможно отдавать муравью, у которого больше «висящих» связей.
2.4.2 Пример перемещенийнескольких муравьев
Пусть контекстнаядиаграмма системы имеет два входа (a и b) и два выхода (c и d), а муравей 1 находится в конце входа b, и муравей 2 – в начале выхода c, рис. 2.21).
/>
Рисунок 2.21 – Размещениемуравьев на контекстной диаграмме
Пусть в библиотекекомпонентов находятся (рис. 2.22):
– компонент С1 с входами b, e и выходом g;
– компонент С2 с входом a и выходами e, f;
– компонент С3 с входами f, h и выходом c;
– компонент С4 с входом g и выходами h, d.
/>
Рисунок 2.22 – Библиотекаиз четырех компонентов
Первое перемещениемуравей 1 делает следующим образом.
Вначале он выбирает избиблиотеки компонент С1, у которого есть вход b, который можно присоединить к входу b контекстной диаграммы.
После присоединения входаb компонента С1 к входу b контекстной диаграммы, муравей «переползает»по входу b на компонент С1. Укомпонента С1 остался «висящий» вход e и «висящий» выход g, в конце которого и размещаетсямуравей 1 (рис. 2.23).
/>
Рисунок 2.23 – Первый ходмуравья 1
Первое перемещениемуравей 2 делает следующим образом. Вначале он выбирает из библиотеки компонентС3, у которого есть выход c, который можно присоединить к выходу c контекстной диаграммы. После присоединения выхода c компонента С3 к выходу c контекстной диаграммы, муравей «переползает»по выходу c на компонент С3. Укомпонента С3 остались «висящие» входы h и f, в начале которого и размещается муравей 2 (рис. 2.24).
/>
Рисунок 2.24 – Первый ходмуравья 2
Второе перемещениемуравей 1 делает следующим образом.
Вначале он выбирает избиблиотеки компонент С4, у которого есть вход g, который можно присоединить к выходуg компонента С1.
После присоединения входаg компонента С4 к выходу g компонента С1, муравей «переползает»по входу g на компонент С4, выход h которого он соединяет с входом h компонента С3, а выход d – c выходом dконтекстной диаграммы системы (рис. 2.25).
/>
Рисунок 2.25 – Второй ходмуравья 1
Второе перемещениемуравей 2 делает следующим образом. Вначале он выбирает из библиотеки компонентС2, у которого есть выход f, который можно присоединить к входу f компонента С3. После присоединения выхода f компонента С2 к входу f компонента С3, муравей «переползает»по входу f на компонент С2, выход e которого он соединяет с входом e компонента С1, а вход a – c входом a контекстнойдиаграммы системы (рис. 2.26).
/>
Рисунок 2.26 – Второй ходмуравья 2
3.Пример использования Microsoft Excel в процессе построенияUFO-модели из заданных компонентов на основе алгоритма муравья
Пусть контекстнаядиаграмма системы имеет такой вид, как на рис. 3.1, и все муравьи расположены увходов в диаграмму.
/>
Рисунок 3.1 – Начальноеразмещение трех муравьев
Пусть библиотекакомпонентов содержит шесть подсистем, таких, как показано на рис. 3.2.
/>
Рисунок 3.2 – Библиотекаиз шести компонентов
В Microsoft Excel данную библиотеку компонентов можно представить так,как показано на рис. 3.3, на листе «Библиотека компонентов».
/>
Рисунок 3.3 –Представление библиотеки в Microsoft Excel
Текущее положениемуравьев в Microsoft Excel можно представить так, как показано на рис. 3.4, налисте «Муравьи».
/>
Рисунок 3.4 –Представление текущего положения муравьев в Microsoft Excel
Для поиска в библиотекекомпонентов того компонента, который может быть подключен муравьем к той «висящей»стрелке, на которой он сейчас находится, можно воспользоваться функциейПРОСМОТР [45].
Функция ПРОСМОТР имеетдве синтаксические формы: вектор и массив. Вектор – это диапазон, которыйсодержит только одну строку или один столбец. Векторная форма функции ПРОСМОТРпросматривает диапазон, в который входят значения только одной строки илиодного столбца (так называемый вектор) в поисках определенного значения ивозвращает значение из другого столбца или строки. Эта форма функции ПРОСМОТРиспользуется, когда требуется указать интервал, в котором находятся искомыезначения. Другая форма функции ПРОСМОТР автоматически использует для этой целипервую строку или первый столбец.
Синтаксис векторной формыфункции ПРОСМОТР имеет следующий вид: ПРОСМОТР (Иск_знач; Просматриваемый_вектор;Вектор_результатов).
Иск_знач – это искомоезначение, которое ПРОСМОТР ищет в первом векторе. Искомое значение может бытьчислом, текстом, логическим значением, именем или ссылкой, ссылающимися назначение. Просматриваемый_вектор – это интервал, содержащий только одну строкуили один столбец. Значения в аргументе просматриваемый вектор могут бытьтекстами, числами или логическими значениями. Следует отметить, что значения варгументе просматриваемый вектор должны быть расположены в порядке возрастания,в противном случае функция ПРОСМОТР может вернуть неверный результат. Тексты внижнем и верхнем регистре считаются эквивалентными. Вектор_результатов – этоинтервал, содержащий только одну строку или один столбец. Он должен быть тогоже размера, что и просматриваемый вектор. Для поиска в библиотеке компонентовтого компонента, который может быть подключен муравьем 1 к «висящей»стрелке a, на которой он сейчас находится, вячейку Е3 введем формулу
=ПРОСМОТР(C3;'Библиотекакомпонентов'!$A$2:$A$7;
'Библиотекакомпонентов'!$B$2:$B$7),
которую затемраспространим с помощью маркера заполнения в ячейки Е4 и Е5. Результат показанна рис. 3.5.
/>
Рисунок 3.5 – Поисккомпонентов в Microsoft Excel
Заметим, что для муравья3 результат поиска оказался неверным. Это связано с тем, что компоненты вбиблиотеке (рис. 3.3) упорядочены по возрастанию по системам, но не по входам,как это требует функция ПРОСМОТР. Поэтому функция ПРОСМОТР вернула неверныйрезультат. Чтобы в дальнейшем получать правильные результаты, необходимоизменить представление библиотеки компонентов так, как показано на рис. 3.6.
/>
Рисунок 3.6 – Измененнаябиблиотека компонентов
Теперь Microsoft Excel дает правильный результат (рис. 3.7).
/>
Рисунок 3.7 – Верныйрезультат поиска компонентов в Microsoft Excel
Итак, Microsoft Excel рекомендует (рис. 3.7):
– муравью 1 подключить к выходу aкомпонент С1;
– муравью 2 подключить к выходу b компонент С2;
– муравью 3 подключить к выходу c компонент С4.
Сделаем это (рис. 3.8):
/>
Рисунок 3.8 – Первыеперемещения муравьев
Заметим, что муравей 1закончил свои перемещения, а муравей 2 перешел на стрелку g, и муравей 3 – на стрелку h.
Посмотрим, что теперьпредложит Microsoft Excel муравьям 2 и 3 (рис. 3.9).
/>
Рисунок 3.9 – Втораяитерация поиска компонентов в Microsoft Excel
Итак, Microsoft Excel рекомендует (рис. 3.9):
– муравью 2 подключить к выходу g компонент С3;
– муравью 3 подключить к выходу h компонент С5.
Сделаем это (рис. 3.10):
/>
Рисунок 3.10 – Вторыеперемещения муравьев
Заметим, что муравей 2также закончил свои перемещения, а муравей 3 перешел на стрелку i.
Посмотрим, что теперьпредложит Microsoft Excel муравь. 3 (рис. 3.11).
/>
Рисунок 3.11 – Третьяитерация поиска компонентов в Microsoft Excel
Сделаем это и посмотримна окончательный результат (рис. 3.12):
/>
Рисунок 3.12 –Окончательный результат
4.Использование алгоритма муравья в процессе UFO-моделирования шахтнойтранспортной системы
Все результаты,представленные в этом разделе, получены в ходе исследовательской практики вотдельном подразделении «Шахта „Комсомольская“»государственного предприятия «Антрацит» Министерства угольнойпромышленности Украины (г. Антрацит, Луганская область).
4.1 Общие сведения оподразделении «Шахта „Комсомольская“»
Подразделение создано дляосуществления производственной, хозяйственной, коммерческой и других видовдеятельности с целью содействия всестороннему развитию государственногопредприятия «Антрацит», повышению его инвестиционнойпривлекательности, получения прибыли.
Подразделение работает поединой производственно-технологической программе с государственным предприятием«Антрацит» и отчитывается перед ним о результатахфинансово-хозяйственной деятельности.
Основными видами деятельности,которые осуществляет подразделение, являются, в частности:
– добыча угольной продукции;
– переработка (обогащение) угольногосырья;
– переработка, использование иреализация отходов производства, вторичного сырья;
– разработка и внедрение проектов поприменению новой техники, передовой технологии, современных методов организациипроизводства, а также использование прогрессивных материалов, изделий иконструкций;
– развитиепроизводственно-хозяйственного комплекса подразделения, повышение производительноститруда и эффективности добычи угля, максимальное использование внутреннихрезервов, интенсификация производственных процессов;
– обеспечение экономического анализапроизводственной и финансово-хозяйственной деятельности с целью выявлениярезервов повышения эффективности производства, улучшения использованияматериальных, трудовых и финансовых ресурсов;
– научно-техническая деятельность.
Для достижения целисоздания подразделения и учитывая необходимость обеспечения подразделениемвыполнения планов добычи угля, эффективного освоения производственных мощностейи наибольшего использования внутренних резервов при соблюдении безопасныхусловий труда и наименьших затратах трудовых, материальных и денежных ресурсов,а также повышения социально-экономического уровня трудового коллектива иудовлетворения социальных потребностей работников, подразделение осуществляет,в частности, следующие производственно-хозяйственные функции:
– самостоятельно планирует своюдеятельность, исходя из основных показателей, которое доводит государственноепредприятие «Антрацит»;
– на основе перспективной программыразвития и задания, которое устанавливается государственным предприятием «Антрацит»на добычу угля, разрабатывает планы производства, доводит их до участков ицехов;
– разрабатывает проекты отработкиочистных забоев и анализирует эффективность использования используемогооборудования при обеспечении соблюдения безопасных условий труда;
– осуществляет выбор системы разработкиугольных месторождений и его элементов, способов подготовки участков для выема,способов механизации основных процессов очистных и подготовительных работ,способов управления горным давлением в очистных и подготовительных выработках;
– принимает участие в рассмотрениипроектов отработки шахтных полей и технологических процессов;
– внедряет в производство достиженияотечественной и зарубежной науки и техники.
4.2 Подготовка и вскрытиешахтного поля
Подземный транспорт шахти рудников горнодобывающей промышленности является составным звеном общешахтнойтранспортной системы. Он представляет собой многозвенную систему, состоящую изразнотипных транспортных установок цикличного и непрерывного действия, свзаимосвязанными параметрами, функционирующую в сложных горно-геологическихусловиях [46].
Характерные чертыподземного транспорта:
– сравнительно небольшие расстояниятранспортирования в подземных условиях при значительных объёмах перевозки;
– неравномерность грузопотоков;
– широкая разветвлённость транспортныхмагистралей;
– наличие в одной магистрали несколькихвидов транспорта и необходимость перегрузок в местах сопряжения;
– многозвенность транспорта,работающего в горизонтальных и наклонных выработках в стеснённых условиях призначительной запылённости, влажности и загазованности окружающей среды.
Основные виды подземноготранспорта: конвейерный и локомотивный.
Конвейерный транспортхарактеризуется:
– высокой производительностью,связанной с поточностью;
– низкой трудоёмкостью обслуживания;
– высокой надёжностью;
– низким уровнем травматизма обслуживающегоперсонала;
– способностью транспортировать груз,как по горизонтальным, так и по наклонным выработкам;
– удобством сопряжения с очистнымизабоями.
Недостатки конвейерноготранспорта:
– относительно высокие капитальные иэксплуатационные затраты;
– неприспособленность ктранспортированию крупнокусковых и абразивных грузов;
– низкая технологическая гибкость.
Локомотивный транспортхарактеризуется
– многофункциональностью;
– практически неограниченнойпроизводительностью;
– высокой экономичностью;
– маневренностью;
– высоким коэффициентом готовности.
Недостатки локомотивноготранспорта:
– цикличность
– зависимость производительности отуровня организации
– ограниченность применения по угламнаклона
– наличие сложного аккумуляторногохозяйства при использовании аккумуляторных электровозов.
Существуют различныесистемы подготовки и вскрытия шахтного поля. Одной из них является панельная система подготовки сотработкой длинными столбами по простиранию.
При панельной системеподготовки применяется следующая схема транспорта. Отбитый уголь попризабойному скребковому конвейеру через перегружатель доставляется на ярусныйштрек. В зависимости от мощности забоя, могут быть применены 2 последовательносоединённые конвейера 2ЛТ80 и 2Л80 или один 1ЛТ100 на всю длину ярусногоштрека. Далее уголь подаётся на панельный конвейерный уклон, где, в зависимостиот нагрузки, могут быть применены уклонные ленточные конвейеры 1ЛУ100, 2ЛУ100или 2ЛУ120В. В месте сопряжения уклона и главного полевого транспортного штрекаоборудуется горный бункер ёмкостью 100-150 т. По главному штреку транспортированиеосуществляется локомотивной откаткой. Для доставки материалов и оборудования кочистному забою по ярусным штрекам предусматривается установка грузо-людскоймонорельсовой дороги ДМКМ. Для обслуживания конвейера на конвейерном уклонеустанавливается монорельсовая дорога.
4.3 UFO-модель шахтной транспортнойсистемы
Контекстная модельшахтной транспортной системы показана на рис. 4.1.
/>
Рисунок 4.1 – Контекстнаямодель шахтной транспортной системы
В процессе построениядекомпозиции контекстной модели шахтной транспортной системы муравей можетпользоваться библиотекой компонентов, основные элементы которой представлены нарис. 4.2.
/>
Рисунок 4.2 – Основныеэлементы библиотеки компонентов
Первоначально муравейнаходится в добывающем забое. Если муравей выбрал для транспортировки отбитогоугля компонент «Конвейер 1ЛТ100», то диаграмма декомпозиции контекстной модели шахтной транспортной системы приметследующий вид (рис. 4.3).
/>
Рисунок 4.3 – Первый шагмуравья
Далее муравей можетвыбрать уклонныйленточный конвейер 1ЛУ100. В этом случае диаграмма декомпозиции контекстной модели шахтнойтранспортной системы примет такой вид, как показано на рис. 4.4.
/>
Рисунок 4.4 – Второй шагмуравья
На последнем шаге муравейвыбирает локомотивнуюоткатку. В результате получается такая диаграмма декомпозиции контекстной модели шахтной транспортнойсистемы, как показано на рис. 4.5.
/>
Рисунок 4.5 – Третий шагмуравья
Если бы на первом шагемуравей выбрал вместо конвейера 1ЛТ100 конвейер 2ЛТ80, а вместо конвейера 1ЛУ100 конвейер2ЛУ120В, то в результате получилась бы диаграмма декомпозиции контекстной модели шахтной транспортнойсистемы, показанная на рис. 4.6.
/>
Рисунок 4.6 – Диаграмма декомпозиции контекстной модели
Выводы
В процессе выполнениямагистерской аттестационной работы получены следующие результаты:
– проанализированы современные технологии построениясистем;
– проанализированы прикладные методы итехнологии искусственного интеллекта:
1) нейронные сети;
2) генетическиеалгоритмы;
3) системы,основанные на продукционных правилах;
4) нечеткая логика;
5) умные агенты;
6) алгоритм муравья.
– осуществлена адаптация алгоритмамуравья к задаче построения UFO-моделииз заданных компонентов:
1) начальноеразмещение муравья;
2) правиласоединения муравьем UFO-компонентов;
3) перемещениемуравья из входа и выхода контекстной диаграммы;
4) перемещение муравьяиз входа и выхода UFO-компонента;
5) разрешениеконфликтов при перемещении нескольких муравьев.
– разработан пример использования Microsoft Excel в процессе построения UFO-моделииз заданных компонентов на основе алгоритма муравья;
– полученные результаты применены впроцессе UFO-моделирования шахтной транспортной системы.
Полученные результатыможно использовать в процессе UFO-анализа.
Среди возможныхнаправлений развития следует отметить перспективность исследования возможностиприменения других алгоритмов искусственного интеллекта в процессе UFO-анализа. Также направлением развитияможет быть внедрение полученных результатов в CASE-инструментарии, используемые в процессе моделированиясистем.
Результаты работыапробированы на IV-м Международномнаучно-практическом форуме «Информационные технологии и кибернетика 2006»,который проходил в Днепропетровске 27-28 апреля 2006 г., и опубликованы в сборнике докладов и тезисов этого форума [44].
Переченьссылок
1. Лямец В.И., Тевяшев А.Д. Системный анализ. Вводный курс. –Харьков: ХТУРЭ, 1998. – 252 с.
2. Давыдов А.Н., Судов Е.В., Якунина О.В. Применениерасширенной идеологии IDEFдля анализа и реинжиниринга бизнес-процессов в производственных иорганизационных системах // Проблемы продвижения продукций и технологий навнешний рынок. Специальный выпуск, 1997. – С. 23-27.
3. Информационные технологии организационного управлениясложными социотехническими системами / О.Е. Федорович, Н.В. Нечипорук, Е.А.Дружинин, А.В. Прохоров. – Харьков: Нац. аэрокосм. ун-т «Харьк. авиац.ин-т», 2004. – 295 с.
4. Емельянов В.В., Урусов А.В. IDEF-RDO:имитационный анализ функциональной структуры сложных систем // Программныепродукты и системы. – 1997. – № 3. – С. 13-18.
5. Калянов Г.Н. Консалтинг при автоматизации предприятий. –М.: Синтег, 1997. – 316 с.
6. Вендров А.М. CASE-технологии. Современные методы исредства проектирования информационных систем. – М.: Финансы и статистика,1998. – 176 с.
7. Бондаренко М.Ф., Маторин С.И., Ельчанинов Д.Б. Системная технологиямоделирования информационных и организационных систем: Учебное пособие. –Харьков: ХНУРЭ, 2005. – 116 с.
8. Емельянов В.В., Попов Э.В. Интеллектуальное имитационноемоделирование в реинжиниринге бизнес-процессов // Программные продукты и системы.– 1998. – № 3. – С. 3-10.
9. Маклаков С.В. Моделирование бизнес процессов с BPwin 4.0. – М.: Диалог-МИФИ, 2002. – 224с.
10. Маклаков С.В. BPwin, ERwin. CASE-средства разработки информационных систем. – М.:Диалог-Мифи, 1999. – 295 с.
11. Маторин С.И. Анализ и моделирование бизнес-систем:системологическая объектно-ориентированная технология. – Харьков: ХНУРЭ, 2002.– 322 с.
12. Бондаренко М.Ф., Соловьева Е.А., Маторин С.И., ЕльчаниновД.Б. Системологическая технология моделирования информационных иорганизационных систем: Учебное пособие. – Харьков: ХНУРЭ, 2005. – 136 с.
13. Маторин В.С., Маторин С.И., Полунин Р.А., Попов А.С.Знаниеориентированный CASE-инструментарийавтоматизации UFO-анализа // Проблемы программирования.– 2002. – №1-2. – С. 469-476.
14. Маторин С.И., Ельчанинов Д.Б. Применение теории паттерновдля формализации системологического УФО-анализа // Научно-техническаяинформация. Серия 2. – 2002. – №11. – С. 1-8.
15. Джонс М.Т. Программирование искусственного интеллекта вприложениях. – М.: ДМК Пресс, 2004. – 312 с.
16. Хьюбел Д. Глаз, мозг, зрение. – М.: Мир, 1990. – 239 с.
17. Pulsed neural networks / by W. Maas and C.M.Bishop eds. – MIT Press. – 1999. – 408 p.
18. Lin C.T. Neural fuzzy systems: a neuro-fuzzysynergism to intelligent systems. – Upper Saddle Rever, New Jersey: PrenticeHall PTR, 1997. – 786 p.
19. Цыпкин Я.З. Основы теории обучающихся систем. – М.:Наука, 1970. – 252 с.
20. Hertz J. Introduction to the theory of neuralcomputation. – Redwood City: Addison-Wesley Publishing Company, 1996. – 327 p.
21. Kohonen T. Self-organizing Maps. – Berlin:Springer-Verlag, 1995. –363 p.
22. Приобретение знаний / Под ред. С. Осуги, Ю. Саэки; Пер. сяпон. – М.: Мир, 1990. – 304 с.
23. Огнев И.В. Интеллектуальные системы ассоциативной памяти.– М.: Радио и связь, 1996. – 176 с.
24. Kung S.Y. Digital Neural Networks. – EngewoodCliffs, New Jersey: PTR Prentice Hall, 1994. – 418 p.
25. Корнеев В.В., Гареев А.Ф., Васютин С.В., Райх В.В. Базыданных. Интеллектуальная обработка информации. – М.: «Нолидж». 2000.– 352 с.
26. Люгер Д.Ф. Искусственный интеллект: стратегии и методырешения сложных проблем. – М.: «Вильямс», 2003. – 864 с.
27. Goldberg D.E. Genetic algorithms in search,optimization and machine learning. – Adison Wesley, Reading, MA, 1989. – 308 p.
28. Эволюционные вычисления и генетические алгоритмы.Обозрение прикладной и промышленной математики. Выпуск 5.– М.:«ТВП».– Т.3.– 1996.– 204 с.
29. Ельчанинов Д.Б., Кривуля Г.Ф., Лобода В.Г., Механа СамиПрименение генетических алгоритмов и многоуровневых сетей Петри припроектировании компьютерной техники // Радиоэлектроника и информатика, 2002. –№ 1. – С. 89-97.
30. Петросов Д.А. Лобода В.Г., Ельчанинов Д.Б. Представлениегенетических алгоритмов сетями Петри в задачах проектирования компьютернойтехники // Материалы научно-практической конференции «Информационныетехнологии – в науку и образование». Харьков: ХНУРЭ, 2005. – С. 48-51.
31. Ельчанинов Д.Б., Петросов Д.А., Механа Сами Применениегенетических алгоритмов при проектировании компьютерной техники // ВестникХерсонского государственного университета. № 2 (18). 2003. – С. 35-38.
32. Григорьев А.В. Представление генетических алгоритмовсетями Петри в задаче размещения. Автореф. дис. канд. техн. наук. – Казань,2002. – 20 c.
33. Генетические алгоритмы, искусственные нейронные сети ипроблемы виртуальной реальности / Г.К. Вороновский, К.В. Махотило, С.Н.Петрашев, С.А. Сергеев. – Х.: ОСНОВА, 1997. – 112 с.
34. De Jong K.A. Genetic Algorithms: A 10 YearPerspective // In: Procs of the First Int. Conf. on Genetic Algorithms, 1985. – P. 167-177.
35. Искусственный интеллект [В 3-х кн.]. – Кн. 2. Модели иметоды: Справочник / Под. ред. Д.А. Поспелова. – М.: Радио и связь, 1990. – 304с.
36. Бакаев А.А., Гриценко В.И., Козлов Д.Н. Экспертные системыи логическое программирование. – Киев: Наук. думка, 1992. – 220 с.
37. Бондарев В.Н., Аде Ф.Г. Искусственный интеллект. – Севастополь:Изд-во СевНТУ, 2002. – 615 с.
38. Обработка нечеткой информации в системах принятия решений/ А.Н. Борисов, А.В. Алексеев, Г.В. Меркурьев. – М.: Радио и связь, 1989. – 304с.
39. Поспелов Д.А. Ситуационное управление: теория и практика.– М.: Наука, 1986. – 288 с.
40. Джексон П. Введение в экспертные системы. – М.:«Вильямс», 2001. – 624 с.
41. Sycara P.K. Multiagent Systems // AI MAGAZINE. –1998. – V. 19. – № 2. – P. 79-93.
42. Гаврилова Т.А., Хорошевский В.Ф. Базы знанийинтеллектуальных систем. – СПб: Питер, 2000. – 384 с.
43. Marco Dorigo, Vittorio Maniezzo, Alberto Colorni.The Ant System: Optimization by a colony of cooperating agents. // IEEETransactions on Systems, Man and Cybernetics – Part B, Vol. 26, No.1, 1996. –P. 1-13.
44. Сергиенко И.Н. Алгоритмы искусственного интеллекта впроцессе организационного моделирования // Информационные технологии икибернетика 2006: Сборник докладов и тезисов IV-го Международного научно-практического форума(Днепропетровск, 27-28 апреля 2006 г.). – Днепропетровск: ИТМ, 2006. – С.62-63.
45. Петров В.Н. Информационные системы. – СПб.: Питер, 2002.– 688 с.
46. Подземный транспорт шахт и рудников: Справочник / Подобщей редакцией Г.Я. Пейсаховича, И.П. Ремизова. – М.: Недра, 1985. – 304 с.