Содержание к диссертации
Введение
1. Анализ проблем и принципов построения гибридных систем имитационного моделирования 11
1.1. Задачи обработки информации и поиска решений с использованием имитационных моделей сложных систем 11
1.2. Подходы к построению имитационных моделей и интеллектуальное имитационное моделирование 15
1.3. Гибридные системы: классификация и принципы создания 22
1.4. Обзор вариантов построения гибридных интеллектуальных систем 28
1.5. Особенности построения гибридных систем на основе имитационного моделирования 35
1.6. Обзор методов эволюционного моделирования и подходов искусственной жизни 41
1.7. Анализ подходов теории агентов и многоагентных систем 51
1.8. Выводы по главе 1 60
2. Система поиска решений на базе интеллектуального имитационного моделирования 62
2.1. Построение гибридной системы на основе бионических эволюционных методов и имитационных моделей различной точности 62
2.2. Разработка алгоритма построения имитационных моделей различной точности 65
2.3. Разработка схем выбора активной имитационной модели 70
2.4. Построение макроструктур генетического поиска 71
2.5. Разработка схем миграции агентов 85
2.6. Выводы по главе 2 89
3. Система эвристического поиска с корректировкой на основе временных продукций 91
3.1. Построение гибридной системы с использованием временных продукционных правил и многоагентых моделей 91
3.2. Разработка алгоритмов поиска на графе на основе временных продукционных правил 98
3.3. Построение динамической многоагентнои системы для корректировки стратегии однонаправленного поиска 108
3.4. Построение многоагентнои системы из двух взаимодействующих популяций для корректировки стратегии двунаправленного поиска 121
3.5. Выводы по главе 3 123
4. Исследование разработанных алгоритмов и оценка их эффективности при решении практических задач 124
4.1. Цели и методы проводимых исследований 124
4.2. Исследование процессов миграции и макроструктур генетического поиска 125
4.3. Исследование многоагентных систем в задачах однонаправленного и двунаправленного поиска 137
4.4. Исследование эффективности разработанных алгоритмов на практических производственных задачах 142
4.5. Выводы по главе 4 153
Заключение 154
Список литературы 156
Указатель сокращений 172
Приложение 1 173
Приложение 2 186
- Подходы к построению имитационных моделей и интеллектуальное имитационное моделирование
- Разработка алгоритма построения имитационных моделей различной точности
- Разработка алгоритмов поиска на графе на основе временных продукционных правил
- Исследование многоагентных систем в задачах однонаправленного и двунаправленного поиска
Введение к работе
Одной из наиболее важных тенденций развития информатики и разработки информационных технологий в последние десятилетия стало создание гибридных систем. В частности, еще в 80-е годы ХХ-го века экспертные системы стали объединяться с традиционными информационными технологиями (базами данных, расчетными и графическими пакетами), в результате чего появились гибридные экспертные системы. В последние годы активно разрабатываются нейроэкспертные системы, гибридные системы на базе мягких вычислений, гибридные системы интеллектуального имитационного моделирования. Подобные системы включают разнородные информационные технологии, функционирующие совместно в интересах решения сложных задач (которые трудно или даже невозможно решить с помощью одной-единственной технологии) и достижения большей эффективности обработки информации. Соответственно, возникает проблема исследования и разработки как эмпирических, так и теоретических подходов к гибридизации, обеспечивающих, например, объединение таких разнородных технологий как: имитационные модели и базы знаний, генетические алгоритмы и многоагентные системы. Так включение интеллектуального модуля в системы имитационного моделирования позволяет учитывать эвристические знания и опыт разработчика при определении параметров модели, а применение генетических алгоритмов обеспечивает эффективный поиск решений. В то же время, интеллектуализация систем имитационного моделирования требует развития баз знаний, опирающихся на продукционные системы с модифицированными, зависящими от времени продукционными правилами, которые требуют построения комбинированных стратегий поиска.
В связи с вышеизложенным, проблемы разработки теоретических и прикладных аспектов построения гибридных, динамических систем в информатике, включающих неоднородные подсистемы, изменяющиеся во времени, являются чрезвычайно актуальными. В диссертационной работе дается новое решение задачи разработки гибридных систем, сочетающих имитационное и эволюционное моделирование, динамические базы знаний и многоагентные модели, а также предлагаются варианты реализации бионических методов и моделей в информационных технологиях, что имеет существенное значение для развития теоретических основ информатики.
Целью диссертационной работы является повышение эффективности обработки информации и поиска решений за счет построения гибридных систем, использующих имитационные модели, бионические принципы и многоагентные подходы.
Для достижения поставленной цели в диссертации решаются следующие основные задачи:
1. Исследование существующих гибридных систем. Построение архитектур гибридных интеллектуальных систем, объединяющих методы и средства имитационного и эволюционного моделирования, базы знаний на основе динамических продукционных правил и агентно-ориентированные подходы.
2. Разработка искусственных агентов и многоагентных систем на основе бионических методов.
3. Исследование механизмов взаимодействия популяций искусственных агентов.
4. Разработка алгоритмов модифицированного генетического поиска на основе принципов макроэволюции, методов миграции агентов и теории формирования элитных групп.
5. Разработка алгоритмов эвристического поиска в пространстве состояний с корректировкой на основе многоагентных моделей.
6. Создание программного обеспечения, реализующего разработанные алгоритмы.
7. Применение разработанного программного обеспечения для решения прикладных оптимизационных задач.
В диссертационной работе для решения поставленных задач используются методы теории множеств и теории алгоритмов, теории графов и теории вероятностей, теории планирования эксперимента и эвристического поиска, имитационного и эволюционного моделирования, теории агентов и многоагентных систем.
Научная новизна диссертации определяется, в первую очередь, разработкой гибридных систем, сочетающих средства интеллектуального имитационного моделирования, базы знаний на основе динамических продукционных правил, алгоритмы, реализующие бионические принципы и многоагентные технологии. Новыми являются:
1. Модель эволюции популяции как многоагентной системы, определяемая принципами миграции агентов и формированием элитной популяции, которая использует в процессе поиска решения имитационные модели различной точности;
2. Метод эвристического поиска на основе динамических продукционных правил;
3. Метод корректировки весов эвристических функций с помощью многоагентой системы при реализации однонаправленного и двунаправленного поиска в пространстве состояний.
Практическая ценность результатов диссертации определяется созданием комплекса алгоритмов поиска решений, реализующих разработанные бионические методы и модели, которые обеспечивают повышение эффективности обработки информации. Предложенные методы и алгоритмы реализованы в виде программ на ЭВМ на языке программирования C++ в среде MS Visual C++. Программное обеспечение имеет возможность интеграции в среду интеллектуального имитационного моделирования РДО.
Теоретические и практические результаты, полученные в диссертационной работе, применялись при выполнении хоздоговорной тематики Отдела «Компьютерные системы автоматизации» НУК РК МГТУ им. Н.Э.Баумана и госбюджетной тематики ГУ РосНИИ информационных технологий и систем автоматизированного проектирования (см. Отчет о НИР «Разработка моделей и методов многоагентных систем», 2004г., шифр БД-01-04). Результаты диссертации также использованы при выполнении работ по грантам Российского фонда фундаментальных исследований (гранты 02-01-00784, 02-07-90240, 03-07-06139, 04-01-00306).
Результаты исследований, проведенных в диссертационной работе, были внедрены на «ОАО Коломенский завод РТИ». Использование результатов диссертации позволило повысить эффективность составления сменно-суточных заданий участка по выпуску резиновых технических изделий (время выполнения текущего портфеля заказов удалось сократить на 4-5%). Кроме того, результаты работы нашли применение в учебном процессе кафедры «Компьютерные системы автоматизации производства» МГТУ им. Н.Э.Баумана и кафедры САПР ТРТУ.
Достоверность научных положений и выводов диссертации подтверждается результатами вычислительных экспериментов на тестовых и практических задачах, а также актами о внедрении.
Основные результаты диссертационной работы докладывались на: Третьей Международной летней школе-семинаре по искусственному интеллекту для студентов и аспирантов (Браславская школа-99, Беларусь, Браславские озера, 1999г.), Четвертой Международной летней школе-семинаре по искусственному интеллекту для студентов и аспирантов (Браславская школа-2000, Беларусь, Браславские озера, 2000г.), Научной сессии МИФИ-2001 (Москва, 2001г.), Международной научно-технической конференции студентов и аспирантов «Радиоэлектроника, электротехника и энергетика» (Москва, 2001г.), Международном научно-практическом семинаре «Интегрированные модели и мягкие вычисления в искусственном интеллекте» (Коломна, 2001г.), Научной сессии МИФИ-2002 (Москва, 2002г.), Восьмой Национальной конференции по искусственному интеллекту (КИИ-2002, Коломна, 2002г.), И-м Международном научно-практическом семинаре «Интегрированные модели и мягкие вычисления в искусственном интеллекте» (Коломна, 2003г.), Международных научно-технических конференциях ШЕЕ AIS 03 и CAD-2003 (Дивноморское, 2003г.), Девятой Национальной конференции по искусственному интеллекту (КИИ-2004, Тверь, 2004г.), Международных научно-технических конференциях IEEE AIS 04 и CAD-2004 (Дивноморское, 2004г.), Ш-м Международном научно-практическом семинаре «Интегрированные модели и мягкие вычисления в искусственном интеллекте» (Коломна, 2005г.), а также научно-техническом семинаре «Экобионика» МГТУ им. Н.Э. Баумана в 2005г.
По теме диссертации автором опубликовано 16 работ, включая одну коллективную монографию.
На защиту выносятся:
1. Архитектуры гибридных систем интеллектуального имитационного моделирования, использующие бионические принципы и многоагентные методы.
2. Метод представления программных агентов как искусственных организмов во взаимодействующих и эволюционирующих популяциях.
3. Новая схема генетического поиска на базе механизмов миграции агентов.
4. Алгоритмы эвристического поиска на основе динамических продукционных правил и многоагентных систем.
В первой главе диссертации приводится постановка задач исследования и обзор методов решения данных задач. Рассматриваются две актуальные задачи поиска решения на основе имитационного моделирования. Обосновано, что для их решения необходимо создание гибридных систем, объединяющих методы искусственного интеллекта и средства имитационного моделирования. Показано, что построение гибридных интеллектуальных систем стало ведущей тенденцией современной информатики. Выполнен обзор принципов создания и различных подходов к разработке гибридных интеллектуальных систем, а также предложена их классификация. Установлено, что проблемы гибридизации в области интеллектуального имитационного моделирования являются недостаточно исследованными. Предложены возможные пути их решения, которые заключаются в построение новых структур гибридных систем имитационного моделирования, а также разработке перспективных поисковых методов основанных на бионических принципах моделирования эволюции и построения многоагентных систем. Проведен обзор методов эволюционного моделирования и подходов искусственной жизни, моделей теории агентов и многоагентных систем.
Во второй главе описывается выбор и построение архитектуры гибридной системы поиска решений на основе имитационного моделирования, а также разработка основных компонентов системы в виде методов и алгоритмов. В гибридной системе предложено использовать блок выбора активной имитационной модели, который реализует выбор менее точных моделей для прогона на начальном этапе работы блока оптимизации и последующее повышение точности модели в процессе поиска. Данный механизм позволяет значительно сократить время поиска решения. Описан алгоритм построения имитационных моделей различной точности, который основан на принципе попарного сравнения разрабатываемых имитационных моделей. Предложено несколько схем определения конкретной имитационной модели для прогона на каждом шаге работы алгоритма. В качестве блока оптимизации в гибридной системе предложено использовать макросхему генетического поиска, которая основана на моделировании макроэволюции и методах миграции агентов. Разработан и описан алгоритм модифицированного генетического поиска. Предложены основные типы межпопуляционных связей и схемы выбора мигрантов, которые основаны на принципах создания элитной популяции агентов.
В третьей главе рассматривается построение архитектуры гибридной системы эвристического поиска с корректировкой на основе временных продукций, а также разработка основных компонентов системы в виде методов и алгоритмов. Система состоит из базы знаний на основе временных продукционных правил, блока эвристического поиска на графе состояний и блока корректировки поиска на основе эволюционирующей многоагентной системы. В качестве базового алгоритма эвристического поиска используется алгоритм Харта - Нильсона - Рафаэла. Разработана модификация данного алгоритма для реализации стратегий поиска на основе продукционных правил, зависящих от времени. Описана многоагентная система, моделирующая одну популяцию агентов, которая предназначена для корректировки весов эвристических функций при реализации однонаправленного поиска. Для корректировки весов эвристических функций в процессе двунаправленного поиска рассматривается многоагентная система, охватывающая две популяции агентов. В данной системе предлагается использовать оператор миграции, который реализуется на базе одной из схем миграции, описанных во второй главе.
В четвертой главе приведены результаты исследований разработанных алгоритмов на тестовых и практических производственных задачах. Определены рациональные параметры миграции агентов. Исследованы методы эвристического поиска на основе многоагентных систем и показана их эффективность для корректировки весов эвристических функций в процессе поиска на графе состояний. Показана эффективность разработанных алгоритмов, как на тестовых, так и на рассматриваемых в работе практических производственных задачах.
В заключении содержатся основные выводы и результаты диссертации.
В приложении 1 приведен текст программы, реализующей алгоритмы модифицированного генетического поиска. В приложении 2 приведен текст программы, которая реализует алгоритмы эвристического поиска с корректировкой на основе многоагентной системы.
Подходы к построению имитационных моделей и интеллектуальное имитационное моделирование
При событийном подходе исследователь описывает события, которые могут изменять состояние системы, и определяет логические взаимосвязи между ними. Имитация происходит путем выбора из списка будущих событий ближайшего по времени и его выполнения. Выполнение события приводит к изменению состояния системы и генерации будущих событий, логически связанных с выполняемым. Эти события заносятся в список будущих событий и упорядочиваются в нем по времени наступления. В событийных системах модельное время фиксируется только в моменты изменения состояний.
При использовании подхода сканирования активностей разработчик описывает все действия, в которых принимают участие элементы системы, и задает условия, определяющие начало и завершение действий. После каждого продвижения имитационного времени условия всех возможных действий проверяются и если условие выполняется, то происходит имитация соответствующего действия. Выполнение действия приводит к изменению состояния системы и возможности выполнения новых действий.
В процессно-ориентированном подходе исследователь описывает последовательность компонентов модели, которые возникают по определенной схеме. Логика возникновения определенных компонентов задается одним оператором языка. Имитатор моделирует процесс продвижения активных элементов через систему и представляет собой некоторую последовательность событий. Процессно-ориентированный подход сочетает элементы событийного подхода и подхода сканирования активностей.
Поскольку имитационная модель - это программа, реализуемая на ЭВМ, то при ее создании этап программирования является одним из основных этапов. Он может быть выполнен тремя путями:
1. Использованием универсальных алгоритмических языков программирования, таких как Паскаль, C++, Фортран, PL/1, Ада и др. Программист имеет здесь практически неограниченные возможности по созданию эффективной ИМ, наилучшим образом использующей ресурсы ЭВМ, особенности операционной системы, обладающей высоким быстродействием и т.д. Однако создание ИМ таким способом требует больших трудозатрат, работы программистов высокой квалификации, взаимодействия специалистов различного профиля (системных программистов, экспертов проблемной области, исследователей и др.). Имитационная модель получается узко направленной на решение конкретной задачи и, как правило, не может быть использована для других приложений.
2. Созданием и использованием специализированных языков моделирования. Примерами языков, реализующих событийный подход служат SLAM II, GASP IV, SIMASCRIPTII, ІІСИМПАК, СИМКОМ и др. Языки CSL, DRAFT, HOCUS, HEADLANDS реализуют подход сканирования активностей. Среди процессно-ориентированных языков, наиболее часто употребляются GPSS, SLAM II, СИМУЛА, SOL, Q-GERT, SIMAN, PAWS, QNAR.
Языки имитационного моделирования за счет снижения гибкости и универсальности позволяют создавать ИМ на несколько порядков быстрее и не требуют работы системных программистов. Они обладают двумя наиболее важными достоинствами: удобством программирования и концептуальной выразительностью. Последнее достоинство позволяет четко и ясно описывать различные понятия, что наиболее важно на стадии моделирования и для определения общего подхода к изучению исследуемой системы.
Основным недостатком языков моделирования является их относительно ограниченная гибкость с точки зрения многообразия исследуемых систем и возможного разнообразия задач их анализа и синтеза. Это приводит к необходимости разработки новых моделей для альтернативных вариантов не только структуры моделируемой системы, но и управляющих элементов сложной системы. При использовании специализированных языков моделирования для подготовки ИМ требуется описывать структуру и физические процессы объекта абстрактными понятиями в терминах используемого языка, как правило, далекими от понятий предметной области.
3. Созданием и использованием проблемно-ориентированных систем моделирования, например ПОДСИМ (МГТУ, Москва), ДСИМ (ЭНИМС, Москва), АСИМПТОТА (Санкт-Петербург), DOSIMIS-3 (Магдебург, ФРГ), Process Charter (Менло-Парк, шт. Калифорния), Powersim (Берген, Норвегия), Ithink (Ганновер, шт. Нью-Хэмпшир), Extend+BPR (Сан-Хосе, шт. Калифорния), ARENA (фирмы Systems Modeling); ProModel (фирмы ProModel); ReThink (фирмы Gensym) и ряда других.
В этих системах исследователь не пишет модель на языке моделирования. Она генерируется автоматически в процессе диалога с исследователем, который происходит в понятиях языка предметной области. Системы обеспечивают моделирование с помощью графических средств, библиотек специализированных программ и языков.
Проблемно-ориентированные системы имитационного моделирования позволяют быстро и эффективно создавать имитационные модели и проводить исследования вообще без программирования. Однако данное преимущество накладывает большие ограничения на класс моделируемых систем и снижает гибкость процесса имитации. Эти системы имеют большую стоимость и, как правило, ориентированы на выполнение крупных проектов в больших фирмах и организациях.
Рассмотрим один из языков имитационного моделирования — язык РДО [48], появление которого тесно связано с таким перспективным направлением развития инструментальных средств, как использование интеллектуальных технологий. Известно, что интеллектуальные системы, обладая большой гибкостью и универсальностью, могут имитировать деятельность человека [55]. Язык РДО служит для решения указанных выше проблем языков имитационного моделирования и обеспечения исследователя и проектировщика сложных систем новыми возможностями.
Язык РДО использует модифицированные правила продукций для описания дискретных систем и процессов. Обычно в работах по искусственному интеллекту (см., например, [70, 75]) продукционные системы рассматривают без учета временного фактора (статический мир), т.е. время исключается из рассмотрения и описывается только логическая взаимосвязь действий системы. При этом изменение состояния системы происходит один раз за одно действие. В таком представлении теряется возможность моделирования нерегулярных событий и определения моментов окончания действий, а также становится невозможным управление в реальном масштабе времени и имитационное моделирование.
Введенная в методе РДО модификация позволяет устранить эти недостатки, сохраняя в то же время известные преимущества продукционных систем: универсальность (возможность описания широкого класса систем применительно к различным задачам исследования); гибкость (простота настройки на конкретную систему); независимость формата продукционного правила и механизма поиска решений от физического смысла представляемых знаний; модульность (продукционные правила независимы друг от друга, что позволяет вводить или удалять правило из базы знаний, не затрагивая остальные); соответствие процедурного характера описания знаний в продукционных системах дискретным процессам.
Разработка алгоритма построения имитационных моделей различной точности
В блоке 1 задаются начальные параметры: Р — значения вероятности, которая необходима для определения доверительного интервала с заданной степенью достоверности; cnt — число имитационных моделей различной точности, которые будут использоваться в процессе поиска решений; п -число прогонов для каждой ИМ, от которого зависит достоверность выходных параметров ИМ.
В блоке 2 реализуется построение адекватной ИМ которая является наиболее точной. Для адекватной ИМ определяется доверительный интервал Lm значений ожидаемого отклика (Блок 3). В блоке 4 производится задание зависимости относительного доверительного интервала L от номера поколения работы ГА, с целью определения моментов переключения с одной имитационной модели на другую в процессе поиска решения. Различные типы данных зависимостей описаны далее в разделе 2.3. Значение относительного доверительного интервала для некоторой ИМ рассчитывается с помощью использования процедуры сравнения двух ИМ (данная процедура описана ниже) и последующего сопоставления данного значения с Lm. Т.е. чем больше это значение, тем разработанная ИМ ближе к адекватной ИМ.
Блоки 5-13 алгоритма реализуют построение необходимого числа имитационных моделей. Основой для построения моделей является определение уровня детализации ИМ. Приведем основные рекомендации по определению уровня детализации имитационных моделей [69, 87]: Разработчику необходимо тщательно определять проблемы, которые будут исследованы при анализе системы и рабочие показатели, которые необходимо оценить. Модели не бывают универсальными, они разрабатываются для конкретных целей. Даже очень удачно разработанную модель можно применять для решения определенного круга задач. Необходимо принимать во внимание, что объект, который рассматривается при прогоне ИМ, не всегда полностью соответствует объекту моделируемой системы. Более того, зачастую нет необходимости моделировать каждый компонент системы. Чтобы определить уровень детализации модели, надо обратиться к специалистам по исследуемым вопросам, с целью выяснения, какие компоненты моделируемой системы имеют наибольшее значение и, следовательно, должны быть тщательно смоделированы. Кроме того, необходимо определить, какие факторы системы оказывают наибольшее влияние на искомые рабочие показатели. Не надо вводить в модель больше деталей, чем требуется для интересуемых проблем, однако нужно вносить дополнительные условия, чтобы модель была достаточно детальной и считалась правдоподобной. Уровень детализации модели должен согласовываться с видом исходных данных. Так, модель, созданная для проектирования новой производственной системы будет не столь детально проработана, как модель, применяемая для регулировки существующей системы, поскольку по новой системе может быть мало данных или не быть вообще. Практически все имитационные исследования связаны с ограничениями во времени и в денежных средствах, которые являются главными факторами при определения уровня детализации модели. Если при исследовании системы необходимо учесть множество факторов, следует воспользоваться «грубой» имитационной моделью или аналитической моделью, чтобы определить, какие факторы из всего множества будут иметь наибольшее влияние на системные показатели. Затем нужно создать «подробную» ИМ, в которой делается ударение на установленные ранее факторы.
В блоке 6 производится сравнение очередной ИМ с адекватной ИМ. Сравнение двух имитационных моделей производится на основании такого показателя работы как ожидаемый отклик. Оно выполняется путем построения доверительного интервала для разности между двумя математическими ожиданиями, а не с помощью проверки гипотезы, призванной установить, будет ли ожидаемая разность существенно отличаться от 0 [69].
Опишем процедуру сравнения двух ИМ. Пусть XiU Xi2, ..., Xin, будет выборкой п( независимых и одинаково распределенных наблюдений, полученных для /-й ИМ при / = 1, 2, и пусть Yt = Е(Ху) будет ожидаемым откликом. Необходимо построить доверительный интервал для С= Y] — Y2. Рассмотрим случай, когда п\ = п2. Попарно объединим Ху и X2j, чтобы определить разность Zj = Хц—Ху, при J = 1,2, ...,«. В этом случае Zj являются независимыми и одинаково распределенными случайными величинами и E(Zj) = С где С величина, для которой необходимо построить доверительный интервал.
На основании данных формул можно построить доверительный интервал для случайной величины Z. При этом доверительный интервал обеспечивает покрытие С с заданной доверительной вероятностью 1-а.
На основании построенного доверительного интервала рассчитывается относительный доверительный интервал для заданной ИМ - Lt. В блоке 7 определяется, попадает ли значение Z,, в соответствующий для заданной ИМ интервал, исходя из ранее определенной зависимости L(N). Если попадает, то данная ИМ заносится в список используемых имитационных моделей.
Таким образом, результатом работы данного алгоритма является построение определенного числа имитационных моделей различной точности, которые используются в соответствующем блоке описанной ГС, а также задание схем выбора данных имитационных моделей в процессе поиска решения.
Рассмотрим способы выбора имитационных моделей различной точности. В работе предлагаются три схемы выбора активной ИМ в процессе поиска решения: линейная (рис.2.3), степенная (рис.2.4) и обратно-степенная (рис.2.5). Как видно из графиков, линейная зависимость является компромиссом для разработчика между скоростью работы алгоритма и качеством получаемого решения. Степенная зависимость отдает предпочтение качеству получаемого решения, а обратно-степенная - времени работы алгоритма. Значение степени определяются разработчиком на основании принципа усиления или уменьшения эффекта, которого позволяют добиться соответствующие зависимости.
Разработка алгоритмов поиска на графе на основе временных продукционных правил
Стратегии поиска в пространстве состояний рассматривают различные допустимые состояния системы в процессе поиска решения. В случае использования имитационного моделирования состояние моделируемой системы определяется набором значений параметров всех ее объектов. Этот набор образует базу данных системы. Чтобы некоторое правило из базы знаний могло исполниться (применяться к БД), должно выполняться его условие (предусловие правила). Исполняемое продукционное правило изменяет содержание БД. Если при некотором состоянии БД могут быть применены несколько продукционных правил, то возникает вопрос о выборе дальнейшего пути имитации, т.е. о выборе необходимого правила из БЗ которое войдет в последовательность правил, переводящих систему в требуемое состояние. Стратегию поиска решения можно представить как нахождение пути на графе состояний от вершины, представляющей исходную базу данных, к вершине, которая представляет базу данных, удовлетворяющую терминальному условию. Выбор такой стратегии объясняется тем, что она обладает большой гибкостью и универсальностью, а также содержит в себе большое число реализаций [37, 75].
Граф поиска G = (S,F) задается двумя множествами: S = {SJ - множество вершин; FaSxS- множество дуг. Каждой вершине St ставится в соответствие состояние системы (база данных), а каждой дуге из F— правило преобразования (продукционное правило). Изначально можно определить две вершины: So-начальная вершина, представляющая собой исходную базу данных; Sn - целевая вершина, представляющая собой базу данных, удовлетворяющую терминальному условию поиска. Таким образом, задачей поиска на графе является нахождение пути на графе от начальной вершины So к целевой вершине Sn.
Различают слепые и направленные методы поиска на графе. Слепой метод имеет два варианта: поиск в глубину и поиск в ширину. При поиске в глубину каждая альтернатива исследуется до конца, без учета остальных альтернатив. Метод плох для «высоких» деревьев, так как легко можно пройти мимо нужной ветви и затратить много времени на исследование «пустых» альтернатив. При поиске в ширину на фиксированном уровне исследуются все альтернативы, и только после этого осуществляется переход на следующий уровень. Метод может оказаться хуже метода поиска в глубину, если в графе все пути, ведущие к целевой вершине, расположены примерно на одной и той же глубине. Оба слепых метода требуют большой затраты вычислительных ресурсов и поэтому необходимы направленные методы поиска.
Существует много методов и алгоритмов направленного поиска: метод ветвей и границ, алгоритм кратчайших путей Мура, алгоритм Дейкстры, алгоритм Дорана и Мичи и др. Однако большинство таких алгоритмов либо находят решение за недопустимо большое время, либо не являются универсальными, т.е. дают хорошие результаты только при решении определенного класса задач.
Хорошей альтернативой описанным выше методам и одним из наиболее перспективных на сегодняшний день методов поиска на графе является алгоритм Харта-Нильсона-Рафаэла [75], который в своей классической реализации представляет поиск на графе состояний на основе обыкновенных продукционных правил вида: ЕСЛИ (Условие) ТО (Действие). Поэтому для разработки стратегий поиска на графе состояний с использованием временных продукций опишем и проанализируем общую процедуру поиска на графе по алгоритму Харта-Нильсона-Рафаэла с целью ее дальнейшей модификации. Процедура GRAPHSEARCH (А ): 1. Создать граф G, состоящий лишь из начальной вершины S0. Создать пустой список OPEN и занести в него S0. 2. Создать пустой список CLOSED. 3. LOOP: если OPEN пуст, то неудача, окончание работы. 4. Выбрать первую вершину в OPEN, убрать ее из OPEN и поместить в CLOSED. Обозначить эту вершину через Sn. 5. Если Sn- целевая вершина - успех, окончание работы с решением, полученным в результате прослеживания пути в G вдоль указателей от Sn к So (указатели определены на шаге 7). 6. Раскрыть вершину Sn, порождая множество М ее преемников, не являющихся предками S„. Поместить в G элементы множества М как преемники S„. 1. Ввести указатель к Sn от тех элементов из М, которые еще не были в G (т.е. ни в OPEN ни в CLOSED). Добавить эти элементы в OPEN. Для каждого элемента из М, который уже был в OPEN или CLOSED, решить, нужно ли переориентировать указатель на Sn. Для каждого элемента из М, уже находящегося в CLOSED, принять решение относительно каждого его потомка в G — нужно ли переориентировать его указатель.
Исследование многоагентных систем в задачах однонаправленного и двунаправленного поиска
Рассмотрим описание и постановку задачи по раскрою материала. На мебельном производстве необходимо оклеивать деревянные блоки дорогостоящей пленкой. Поверхность блоков, на которые наклеивается пленка, имеет форму прямоугольников. Пленка наклеивается на мембранно-вакуумном прессе, поверхность которого также является прямоугольником. Процесс оклейки происходит следующим образом: на поверхность пресса кладется цельная пленка; на нее кладутся блоки, которые сверху также покрываются пленкой; затем происходит запрессовка. Стоит отметить, что блоки необходимо укладывать на поверхность пресса с учетом направленности рисунка пленки.
На вход производственной системы поступают заказы на кухонные гарнитуры. Каждый блок является составляющей одного кухонного гарнитура. Размеры блоков и их количество заданы и определяются портфелем заказов. Заказы могут быть двух типов: срочные и обычные. Очевидно, что срочные должны выполняться в первую очередь.
На выходе системы получаются карты раскроя. Каждая карта раскроя представляет собой вариант укладки блоков на поверхность пресса. Гарнитур считается изготовленным, если все его блоки вошли в карты раскроя. При составлении очередной карты приоритет должны иметь блоки наиболее близкого к завершению гарнитура. Эта особенность вытекает из необходимости исключения простоев и чрезмерной загрузки оборудования.
Задачу по раскрою материала можно сформулировать так: при составлении очередной карты раскроя необходимо выбрать из портфеля заказов некоторое количество блоков и с учетом направленности рисунка пленки уложить их на поверхность пресса; при этом необходимо добиться уменьшения потерь пленки с учетом срочности и приоритета заказов. Таким образом, в данной задаче в качестве основного критерия (как и во многих задачах по раскрою материала) выступает коэффициент использования материала (КИМ): на поверхность пресса; S„p — площадь поверхности пресса.
Для решения данной задачи предложено использовать генетический алгоритм, как алгоритм оптимизации, в сочетании с имитационной моделью [8]. С этой целью была разработана и реализована в среде Borland C++ Builder имитационная модель описанной производственной системы [9].
Для реализации процесса укладки блоков на поверхность пресса, необходимо определить номера блоков, которые нужно выбрать из портфеля заказов, а также их очередность при укладке на пресс. Поэтому каждому блоку в портфеле заказов, помимо идентификационного номера, присваивается порядковый номер, который определяет очередность его укладки. Задачей ГА является определение комбинации значений порядковых номеров блоков, при которых достигается максимум заданного критерия.
Для представления генотипов агентов необходимо кодирование значений порядковых номеров блоков в двоичную форму. Рассмотрим случай кодирования генотипа агента, когда в портфеле заказов 15 блоков. Агент представляет собой битовую строку-хромосому длиной 60 бит. Гены в строке имеют длину по 4 бита и содержат закодированные значения порядковых номеров блоков. Количество бит в каждом гене определяется из условия возможности кодирования максимального номера блока (в данном случае 4 бита обеспечивают кодирование в двоичной форме числа 15). Число генов равно числу блоков, т.е. 15, при этом номер гена определяет номер блока в портфеле заказов.
Оптимизируемой величиной для ГА является функция пригодности. При этом необходимо выбрать такую ФП, которая растет с увеличением значения критерия. Такая функция была найдена ранее, в результате проведенных экспериментов с моделью системы [9]: где: „-параметр, определяющий срочность заказов; Хр - параметр, определяющий приоритет заказов; а7, я2 — весовые коэффициенты, определяющие значимость производственных факторов. Значения весовых коэффициентов были определены исходя из учета производственных условий, а также исследований и экспериментов с моделью системы [10]. Они составляют: ai = В определенный момент времени работу генетического алгоритма следует остановить. В данной схеме этот момент можно определить из условия: где: ФПмах - максимальное значение ФП по популяции; ФПср - среднее значение ФП по популяции. Основу ИМ составляет алгоритм, реализующий укладку блоков. Исходными данными для него является набор порядковых номеров блоков, которые выдает ГА. Здесь декодированный генотип каждого агента — это вариант одной карты раскроя, которую реализует данный алгоритм. Выходной величиной алгоритма является ФП агента. Рассмотрим блок-схему данного алгоритма (рис.4.22). В блоке 1 осуществляется расшифровка строки-хромосомы агента, т.е. определение порядковых номеров блоков. Здесь также устанавливается значение текущего порядкового номера -j, равным 0. В блоке 2 проверяется, имеются ли блоки с порядковым номером равным j. Если такие блоки существуют, то идем дальше; если не существуют, то происходит увеличение,/ на 1 (блок 3).
Похожие диссертации на Гибридные системы интеллектуального имитационного моделирования на основе бионических подходов и многоагентных моделей
