Разработка и исследование распределенных алгоритмов аппроксимации и оптимизации в условиях многоагентных систем тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат технических наук Глухов, Алексей Олегович

• Глухов, Алексей Олегович
• кандидат технических наук
• 1999

Оглавление диссертации кандидат технических наук Глухов, Алексей Олегович

ВВЕДЕНИЕ.5

ГЛАВА 1. ПРОБЛЕМА РАСПРЕДЕЛЕННОГО ПОИСКА РЕШЕНИЯ ЗАДАЧ ОПТИМИЗАЦИИ И АППРОКСИМАЦИИ В СОВРЕМЕННЫХ ПРОГРАММНЫХ СИСТЕМАХ.14

1.1. Составляющие проблемы распределенного поиска.

1.2. Объектно-ориентированный подход.

1.3. Обзор объектно-ориентированных языков программирования.

1.4. Обзор объектно-ориентированных технологий разработки программных систем

1.5. Архитектура открытых систем.

1.6. Принципы построения распределенных объектно-ориентированных программных систем.

Особенности организации распределенных вычислений.

Сетевые вычисления сегодня.

1.7. Анализ существующих подходов к решению задач оптимизации в условиях многоагентных систем.

1.8. Анализ возможностей адаптации существующих методов решения задач оптимизации к условиям многоагентных систем.

Использование метода динамического программирования.

Использование традиционных методов для решения потоковых задач.

Использование традиционных методов для решения задачи коммивояжера.

Использование приближенных методов при решении задачи о наилучшем размещении элементов.

Использование эвристического метода при решении задачи календарного планирования.

1.9. Анализ резервов повышения эффективности традиционных методов решения задач оптимизации в условиях объектной системы.

Использование распределенных сетевых сред.

Распараллеливание вычислений.

Объектно-распределенные алгоритмы.

1.10. Выводы.

ГЛАВА 2. РАЗРАБОТКА ОБЪЕКТНО-РАСПРЕДЕЛЕННЫХ АЛГОРИТМОВ

АППРОКСИМАЦИИ И ОПТИМИЗАЦИИ.57

2.1. Формализация описания многоагентной системы.

2.2. Постановка задачи оптимизации с использованием программных агентов

Общая постановка задачи оптимизации с использованием программных агентов.

Рассмотрение различных вариантов задачи оптимизации.

Пример 1. Транспортная задача.

Пример 2. Задача составления расписания.

Пример 3. Задача календарного планирования.

Пример 4. Задача коммивояжера.

Пример 5. Задача о наилучшем размещении объектов.

2.3. Выработка общего подхода к решению задач оптимизации с использованием агентов.:.

Система локальных эвристик.

Критерий оптимальности.

Система оповестительных сообщений.

Объектно-распределенный алгоритм поиска.

Оптимизирующая объектная модель.

2.4. Построение оптимизирующих объектных моделей.

Конкретизация диаграммы классов оптимизирующей объектной модели.

Диаграмма объектов оптимизирующей объектной модели.

Семантика сообщений оптимизирующей объектной модели.

2.5. Кластеризация объектной системы.

2.6. Аппроксимация на саморазвивающихся агентных структурах.

Введение диссертации (часть автореферата) на тему «Разработка и исследование распределенных алгоритмов аппроксимации и оптимизации в условиях многоагентных систем»

Постановка задачи.91

Объектно-распределенный алгоритм решения задачи.94

2.7. Выводы.100

ГЛАВА 3. ИССЛЕДОВАНИЕ ОБЪЕКТНО-РАСПРЕДЕЛЕННЫХ АЛГОРИТМОВ АППРОКСИМАЦИИ И ОПТИМИЗАЦИИ.102-133

3.1. Программная реализация.102

Структура программы исследования объектно-распределенных алгоритмов оптимизации.105

3.2. Язык описания тестовых задач.108

3.3. Объектно-распределенный алгоритм поиска решения транспортной задачи .109

3.4. Объектно-распределенный алгоритм поиска решения задачи коммивояжера.110

3.5. Объектно-распределенный алгоритм поиска решения задачи о наилучшем размещении.111

3.6. Объектно-распределенный алгоритм аппроксимации.112

3.7. Оценка эффективности объектно-распределенных алгоритмов оптимизации.115

3.8. Оценка эффективности алгоритма объетно-распределенной I аппроксимации.124

3.9. Практические результаты использования алгоритмов.128

3.10. Выводы.130

ЗАКЛЮЧЕНИЕ. 134-136

СПИСОК ЛИТЕРАТУРЫ.137-145

ПРИЛОЖЕНИЯ.146

Приложение 1. Примеры файлов данных и результаты исследования алгоритма объектно-распределенного поиска решения задачи коммивояжера

Приложение 2. Листинг модуля решения задачи коммивояжера с использованием объектно-распределенного поиска

Приложение 3. Листинг модуля решения задачи о наилучшем размещении с использованием объектно-распределенного поиска

Приложение 4. Результат работы подсистемы формирования кадров в режиме отображения А) ив режиме редактирования Б) информации в программе ИНСАИТ

Приложение 5. Спецификация объектов для решения транспортной задачи, задачи коммивояжера, задачи о наилучшем размещении

Приложение 6. Листинг процедуры обучения объектной системы при решении задачи аппроксимации, спецификации объектов SOS.Ни листинг модуля SOS. CP Р

Введение

АКТУАЛЬНОСТЬ

Современные вычислительные системы строятся с учетом таких возможностей повышения их эффективности, как распределенность структуры, использование коммуникационных механизмов сетевых сред, многопроцессорная обработка. Результатом развития технологий разработки программных систем на сегодня является целый ряд стандартов, которые регламентируют их архитектуру, средства управления процессами, механизмы взаимодействия систем, и т.д. В рамках этих стандартов уже прочно закрепилось применение объектно-ориентированной технологии при разработке (проектировании и программировании) программных систем.

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

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

Если характеризовать оптимизацию, осуществляемую на агентах, то можно выделить такие ее свойства: а) иерархия сущностей в системе требует перехода от разнообразных методов глобальной оптимизации и локальной оптимизации к методам многоуровневой оптимизации; б) декомпозиция агентных систем, осуществляемая на основании тех или иных способах классификации сущностей, приводит к неизбежной интерпретации их структур в понятиях решаемых этими системами задач - отсюда, широкое распространение эвристической оптимизации; в) необходимость оптимизации в условиях многоагентных систем и практически полная неприспособленность традиционных методов оптимизации к данным условиям приводит к возврату к старым техникам программирования, хранения и обработки данных (деревья, I массивы, структуры) в рамках этих систем, что нарушает их целостность, лишает гибкости, модифицируемости и других положительных качеств, присущих объектно-ориентированной технологии; по этой же причине проблематичным становится использовать коммуникационные возможности многоагентных систем, приспособленность к функционированию в распределенной (сетевой) среде. Вот почему очень важно рассмотреть специфику и подходы к оптимизации в условиях многоагентных систем и определить возможные пути решения возникающих проблем.

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

ЦЕЛЬ РАБОТЫ

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

ИДЕЯ РАБОТЫ

Идея работы состоит в возможности повышения эффективности эвристического поиска решения в задачах оптимизации и аппроксимации за счет превращения объектов в активные элементы поиска. Тогда уже речь идет не об одном поисковом процессе, основанном на том или ином принципе, а о множестве взаимосвязанных поисковых процессов.

Для достижения поставленной цели были выделены следующие задачи:

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

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

3. Разработка формализма описания объектных структур и происходящих в них процессов с целью получения возможности описания алгоритмов объектно-распределенного поиска;

4. Формулировка задачи объектно-распределенного поиска, с использованием разработанного формализма;

5. Формулировка частных задач объектно-распределенного поиска (задача управления транспортными потоками, задача составления оптимального расписания, задача календарного планирования, задача коммивояжера и задача о наилучшем размещении);

6. Выработка общего подхода к решению задачи объектно-распределенного поиска, основанного на построении оптимизирующей объектной модели;

7. Построение объектной модели для решения задачи аппроксимации на агентных структурах;

8. Разработка и исследование отдельных алгоритмов объектно-распределенного поиска. Получение оценок эффективности алгоритмов по временным характеристикам, точности и надежности.

НАУЧНАЯ НОВИЗНА.

Научная новизна состоит в следующем:

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

2. Сформулирована задача объектно-распределенного поиска решения на основе предложенного формализма;

3. Предложен способ построения распределенных алгоритмов оптимизации и аппроксимации в условиях многоагентных систем, который является развитием эвристического метода, доказаны утверждения о сходимости алгоритмов;

4. Разработаны алгоритмы объектно-распределенного поиска решения конкретных прикладных задач и исследована их сравнительная эффективность;

5. Выработаны рекомендации по программной реализации алгоритмов объектно-распределенного поиска решения задач оптимизации и аппроксимации.

НАУЧНЫЕ ПОЛОЖЕНИЯ, ВЫДВИГАЕМЫЕ НА ЗАЩИТУ

Основным результатом работы является метод построения объектно-распределенных алгоритмов эвристического поиска решения задач оптимизации и аппроксимации.

Конкретные результаты:

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

2. Формализованная постановка задачи объектно-распределенного поиска решения задач оптимизации и аппроксимации;

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

4. Условие сходимости обобщенного алгоритма объектно-распределенного поиска решения задач оптимизации и аппроксимации;

5. Распределенные алгоритмы решения различных классов задач: а) задача коммивояжера; б) транспортная задача; в) задача о наилучшем размещении; с) аппроксимация на самоорганизующихся агент-ных структурах выполняемая по объектно-распределенному принципу.

6. Рекомендации по реализации и использованию алгоритмов объектно-распределенного поиска.

ОБОСНОВАННОСТЬ И ДОСТОВЕРНОСТЬ

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

ПРАКТИЧЕСКАЯ ЗНАЧИМОСТЬ проведенных исследований заключается в следующем:

1. Разработан формализм описания процесса реализации запроса в усI ловиях MAC. На основе которого формализован процесс эвристической многоуровневой оптимизации, который позволяет не только конструировать новые алгоритмы, но также позволяет рассматривать вопрос распараллеливания вычислений и кластеризации системы, что очень важно для распределенных систем;

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

3. Разработаны три программы для ЭВМ: 1) Пакет обучающих мультимедийных курсов для ЭВМ «ИНСАИТ» по курсам «Практикум по MS ProjectManager'98», «Управление проектами» и другие по учебным курсам академика МАИ, д.т.н., профессора Трофимова В.В.; 2) Учебная программа для ЭВМ "Исследование алгоритмов решения потоковых задач", с использованием распределенных алгоритмов оптимизации; 3) Программа моделирования самоорганизующихся агентных структур, используемых при решение задач аппроксимации с предварительным обучением.

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

РЕАЛИЗАЦИЯ И ВНЕДРЕНИЕ РЕЗУЛЬТАТОВ

Автором разработаны следующие программные продукты, испольI зующие результаты диссертационного исследования:

Инструментальная Система Автоматизации Интеллектуальных Тестов (ИНСАИТ), который внедрен в образовательный процесс следующих предприятий: Санкт-Петербургская государственная академия физической культуры имени П.Ф.Лесгафта; Санкт-Петербургский Центр информационной культуры. В ИНСАИТ используется алгоритм ОРП решения задачи о наилучшем размещении. Использование данного алгоритма позволило автоматизировать процесс динамического построения информационных кадров в системе отображения информации, сократить трудоемкость процесса создания мультимедийных приложений обучения и контроля знаний, о чем имеются соответствующие акты.

Подсистема многомерной аппроксимации на самоорганизующихся агентных структурах была внедрена в производственный процесс следующих предприятий: производственно-коммерческое многопрофильное предприятие «Модуль НП», г.Новополоцк; научно-производственная фирма «Строитель», г.Новополоцк; малое предприятие «Реконструкция», г.Новополоцк; Центр научно-технических услуг по строительству Министерства архитектуры и строительства Республики Беларусь, г.Минск; Белгосстрой, г.Минск; о чем прилагаются соответствующие акты. Данная подсистема разрабатывалась как часть программного пакета «EXTREME», предназначенного для выполнения расчета напряженно-деформированного состояния железобетонной конструкции и определение несущей способности по деформации на изгиб, сжатие, растяжение.

АППРОБАЦИЯ РАБОТЫ

Основные положения и результаты работы докладывались и получили одобрение и награды на 4-х международных и 3-х республиканских конфе ренциях. Основные научные результаты опубликованы в 9-ти печатных работах, из них 4 статьи в научных периодических изданиях:

1. Глухов А.О., Глухов Д.О. Объектно-ориентированный подход к рассмотрению виртуальной реальности / тезисы международной научной конференции "Гагаринские чтения". - М.: МГАТУ, 1996. (III место)

2. Y. Trofimov, A. Gloukhov, D. Gloukhov Algorithm of ecological monitoring by fuzzy production rules / 2-nd International Conférence Ecology and Society's Development Abstracts.- St.P.: МАНЭБ, 1997,- p. 166

3. Глухов A.O., Глухов Д.О. Объектно-ориентированная система виртуальной реальности / тезисы научной конференции "НДРС-96" БГУ: Минск, 1996. (1-е место)

4. Глухов А.О., Глухов Д.О. Система построения трехмерного изображения для динамической визуализации/ тезисы Республиканского конкурса студенческих научных работ "Кибернетика и компьютерные технологии XXI века". - Минск: БГУИР, 1996. (диплом I степени)

5. Глухов А.О. Автоматизация компоновочных процессов в системах отображения информации/ тезисы международной конференции по мягким вычислениям и измерениям. - СПб: СПбЭТУ, 1998, 4с

13

6. Глухов Д.О., Глухов А.О. Объектно-ориентированная система виртуальной реальности/Сб. науч. статей "НДРС-96" БГУ-Минск, 1996.-5с.

7. Глухов А.О. Автоматизация компоновочных процессов в системах отображения информации/ Сборник докладов SCM'98. - СПб: СПбЭТУ, 1998-4с.

8. Глухов А.О. Способ повышение эффективности эвристического метода оптимизации в условиях объектно-ориентированных систем / Сборник докладов SCM'99. - СПб: СПбЭТУ, 1999, с.228-232

9. Глухов Д.О., Глухов А.О., Трофимов В.В. Мониторинг по нечетким продукционным правилам в сложных динамических системах с изменяющейся структурой / Вестник факультета менеджмента СПбГУ - СПб: СПбГУ, 1998.-5с.

СТРУКТУРА РАБОТЫ

Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы и приложений с документацией о внедрении и использовании результатов работы. Общий объем работы (без приложений) 145 страницы. Рисунков - 26, таблиц - 7. Список литературы включает 121 наименование.

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Глухов, Алексей Олегович

3.10. Выводы

Получена оценка вычислительной сложности объектно-распределенного алгоритма поиска решения задачи коммивояжера при однопроцессорном исполнении, выраженной в числе итераций и ограниченной асимптотической функцией 2п для первого варианта алгоритма и 2п - для второго, где п - предел длины решения, что подтверждается при осуществлении поиска в сетях из 30, 100 и 200 узлов. Это позволяет использовать данный подход при решении задач большого объема. По степени отклонения стоимости решения от оптимума также получена оценка в виде функций приближения. При исследовании эффективности объектно-распределенных алгоритмов в зависимости от способа реализации параллельности были получены следующие результаты:

1. По способу синхронизации предпочтительнее простая синхронизация, односторонняя при небольшом числе отказов и асинхронная. Синхронная - применима лишь при малом ожидании обработки сообщения и малом числе отказов. Использование синхронизации по времени не рекомендуется.

2. По введению приоритетов для объектов - наиболее эффективна система приоритетов с динамическим критерием.

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

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

Значительно шире набор базовых преобразований;

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

Ниже автор приводит преимущества и недостатки объектно-распределенных алгоритмов оптимизации, которые были выявлены при решении рассмотренных в данной работе задач.

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

Преимуществами объектно-ориентированной, распределенной оптимизации по сравнению с традиционными методами решения являются: высокая производительность (дальнейшее увеличение возможно при распараллеливании вычислений); возможность адаптации к динамически изменяемой структуре системы; использование коммуникационных возможностей объектов при выполнении вычислений (все вычисления выполняются в рамках существующих объектных связей); использование логических правил, вытекающих из анализа поставленной задачи, позволяет сделать объектно-ориентированную, распределенную оптимизацию гибкой, позволяет легко вводить в задачу новые параметры и ограничения; распределенный характер вычислений, который позволяет решать задачи больших размерностей.

133

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

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

Заключение

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

В диссертационной работе получены следующие основные результаты:

1. Построен формализм описания стратегии эвристического поиска оптимального решения в условиях многоагентной системы.

2. Формализована постановка задачи объектно-распределенного поиска оптимального решения, определен круг задач оптимизации, для которых возможна данная постановка.

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

4. Построены объектно-распределенные алгоритмы поиска решения конкретных задач оптимизации: а) задача коммивояжера; б) транспортная задача; в) задача о наилучшем размещении; г) а также задачи аппроксимации, которая может быть поставлена как задача оптимизации.

5. Исследована сравнительная эффективность объектно-распределенного алгоритма поиска решения задачи коммивояжера по отношению к традиционным методам. В нашем случае, вычислительная сложность, полученная на основании статистических оценок и выраженная в числе итераций мониторинга объектов, составила 2п и 2п для двух вариантов алгоритма. Что лучше степенной зависимости 1.26" метода ветвей и границ и его модификаций или п2п для метода динамического программирования. Если же сравнивать с приближенными методами, то качество решения при распределенном поиске значительно превосходит локальную эвристическую оптимизацию при соизмеримом уровне сложности.

6. Исследован вопрос эффективности объектно-распределенного алгоритма решения задачи о наилучшем размещении;

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

8. Создан ряд обучающих мультимедийных программ для ЭВМ «ИНСАИТ» по курсам «Практикум по МБ Рго]ес1Мапа§ег'98», «Управление проектами» и другие по учебным курсам академика МАИ, д.т.н., профессора Трофимова В.В., учебная программа для ЭВМ "Исследование алгоритмов решения потоковых задач", с использованием объектно-распределенных алгоритмов оптимизации.

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

1. Обмен информацией между зависимыми агентами в процессе поиска решения. При этом агент производит сопоставление собственного решения с решениями соседей и принимает решение об эффективности собственного поиска или же переходит к решению, предлагаемому соседними агентами;

2. Распараллеливание вычислений и независимый характер поиска решения агентами. Использование многопоточного программирова

136 ния;

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

4. Использование шаблонов взаимодействий для построения распределенных сетей агентов. Кластеризация сети;

5. Обучение агентов в процессе поиска или настройка.

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

Список литературы диссертационного исследования кандидат технических наук Глухов, Алексей Олегович, 1999 год

1. A critical view of inheritance and reusability in object-oriented programming: Acad. Diss. . Univ. Of Jyraskyla / Antero Taivalsaar. Univ. of Jyraskyla, 1993. - 276p.

2. Adamo J.M. L. P. L.: A Fuzzy Programming Language // Fuzzy Sets a. Sistems. 1980. - Vol.3, N 2. -P. 151-179.

3. Askit M., Bergmans M. Obstacles in Object-Oriented Development, TRESE Project, University of Twente; H. Lieberman, Using Prototypical Objects to implement shared behavior, OOPSLA '86

4. Bailin S. Remarks on Object-Oriented Requirements Specification. Laurel, MD: Computer Technology Associates. 1988.j

5. Batory D.S. Extensible Cost Models and Query Optimization in GENESIS // IEEE Database Eng.-1987,- 10, N4. p. 27-34

6. Bill Gallmeister POSIX 4 USA, Sebastopol: O'Reilly & Associates, Inc., 1995. - 570 p.

7. Blanton J., Wainwright R. Multiple Vehicle Routing wuth Time and Capacity Constraints Using Genetic Algorithms. Proc. Of 5th Int. Conf. On GA, Morgan Kaufmann Publ., San Mateo, 1993.

8. Bodorik P., Riordon J.S. Distributed Query Processing Optimization Objectives // 4th Int. Conf. Data Eng., West Berlin, Sept. 13-15, 1988. New York, 1988,- p. 320-329

9. Coad P., Yourdon E. Object-Oriented Analisis, Second Edition. Englewood Cliffs, New Jersey: Yourdon Press. 1991.

10. Conference on object-oriented systems, languages and applications. New York: Assoc. For computing machines, 1990.

11. Conference Proceedings (Portland, Oregon, September 26 October 2) ACM SIGPLAN Notices vol. 21, nr. 11 (Nov), 1986. — P.l-8

12. Dave Curry Using С on UNIX System USA, Sebastopol: O'Reilly & Associates, Inc., 1989. -250p.

13. Donald Lewine POSIX Programmer's Guide USA, Sebastopol: O'Reilly & Associates, Inc., 1991. - 640 p.

14. Duda R.O. and others. Subjectiv Bayesian methods for rule-based system // Proceedings of the AFIPS, 1976, National Computer Conference.- V.45.- P. 1075-1082.

15. Dyer J.S. Remarks on the Analytic Hierarhy Process // Management Science, 1990.— 36, №3. — P.249-258.

16. ECOOP'92: European conference on OOP. Berlin etc.: Springer, 1992. -426p.

17. Finkelstein S., Schkolnick M., Tiberio P. Physical Database Design for Relational Databases // ACM Trans. Database Syst., 1988.- 13, N 1,- p. 91-128

18. Hall P.A.V. Optimization of a Single Relational Expression in a Relational Data Base System // IBM J. of Res. and Dev., 1976,- 20, N 3.- p. 244-257

19. HP 9000 Networking. BSD Sockets Interface Programmer's Guide. USA: Hewlet Packard, 1995. -180 p.

20. Jackson M. System Development. Englewood Cliffs, NJ: Prentice-Hall, 1983

21. Jarke M., Koch J. Query Optimization in Database Systems // ACM Comput. Surv.- 1984.- 16, N 2,-C. 111-152

22. John Bloomer Power Programming with RPC. USA, Sebastopol: O'Reilly & Associates, Inc., -1992.-486 p.

23. John Shirley, Wei Hu & David Magid Guide to Writing DCE Applications USA, Sebastopol: O'Reilly & Associates, Inc., 1994. - 462 p.

24. Keller R/M/ Parallel Program Schemate and Maximal Parallelism / JACM. 1973 - Vol.20, №3 -P.514-537; Vol.20, №4 - P.696 - 710.

25. Kim W. Global Optimization of Relational Queries: A First Step // Query Processing in Database Systems. New York: Springer.- 1985,- P. 206-216

26. Lohman G.M., Daniels D., Haas L.M., Kistler R., Seiinger P.G. Optimization of Nested Queries in a Distributed Relational Database // Proc. 10th Int. Conf. Very Large Data Bases, Singapore, Aug. 2731, 1984. New York, 1984,- P. 403-415

27. Lu H., Carey M. Some Experimental Results on Distributed Join Algorithms in a Local Network // Proc. 11th Int. Conf. Very Large Databases, Stockholm, Sweden, Aug. 1985. Los Altos, Calif., 1985.-P. 425-432

28. Mackert L., Lohman G. R* Optimizer Validation and Performance Evaluation for Distributed Queries // Proc. 12th Int. Conf. Very Large Data Bases, Kyoto, Japan, Aug. 1986. Los Altos, Calif., 1986.-P.149-159

29. Markus Kuhn. Linux 2.2 POSIX.lb овместимость и поддержка функций реального времени. Обзор. / перевод Владимира Черненкова ([e-mail]) http://www.sao.ru/~vch/Publications/Russ/html/linux-posix/linux-posix.html

30. Meyer В. Object-Oriented Software Construction. New York, NY: Prentice-Hall. - 1988

31. Micallef J. Encapsulation, Reusability, and Extensibility in Object-Oriented Programming Languages. // Journal of Object-Oriented Programming vol. 1(1), p.25. 1988

32. Moon D.A., Object-oriented programming with Flavors // Meyrowitz N. (ed.), OOPSLA'86

33. Conference Proceedings (Portland, Oregon, September 26 October 2) ACM SIGPLAN Notices vol.j21, nr. 11 (Nov), 1986.— P. 1-8.

34. Object Management Group, " Object Management Architecture Guide", OMG Document Number 92.11.1, September 1, 1992.

35. Robson D. Object-Oriented Software Systems // Byte vol. 6 (8), p.86. 1981.

36. Rumelhart D.E., Hilton G.E., Williams R.J. Learning representations by back-propagating errors // Nature, 1986. V.323. P. 533-536

37. Satoh K., Tsuchida M., Nakamura F., Oomachi K. Local and Global Query Optimization Mechanisms for Relational Databases // Proc. 11th Int. Conf. Very Large Databases, Stockholm, Sweden, Aug. 1985. Los Altos, Calif, 1985,- P. 405-417

38. Sellis T. Global Query Optimization // Proc. ACM SIGMOD Int. Conf. Manag. Data, Washington, D.C, May 28-30, 1986. New York, 1986,- P. 191-205

39. Shan M.C. Optimal Plan Search in a Rule-Base Query Optimizer // Lect. Notes Comput. Sei.- 1988,303, P.92-112

40. Shriver B, Wegner P. (ed.), Reseach directions in object-oriented programming: The MIT Press, 1987 // Wegner P, The object-oriented classification paradigm inheritance. — P.479-560.

41. Shriver В., Wegner P. (ed.), Reseach directions in object-oriented programming: The MIT Press, 1987 \\ Wegner P., The object-oriented classification paradigm inheritance. — P.479-560.

42. Snyder A. Encapsulation and Inheritance in Object-Oriented Programming Languages // SIGPLAN Notices vol. 21(11).- November 1986.

43. Stone M.N. The generalized Weierstrass approximation theorem. Math. Mag., 1948. V.21. PP.167-183,237-254

44. Subieta K., Rzeczkowski W. Query Optimization by Stored Queries // Proc. 13th Int. Conf. Very Large Data Bases, Brington, England, Sept. 1987. Los Altos, Calif., 1987,- P. 369-380

45. Thanglash S., Vinayagamoorty R., Gabbi A. Vehicle Routing and Time Deadlines Using Genetic and Local Algorithms. Proc. Of 5th Int. Conf. On GA, Morgan Kaufmann Publ., San Mateo, 1993.i

46. Trivedi M.M. Analysis of aerial image using fuzzy clustering // In "Analysis of fuzzy Information" ed. By Bezdec J.C. CDC Press, 1987. Vol 3. -P.133-151.

47. Wagner Tom, Towsley Don. Getting Started With POSIX Threads. Department of Computer Science, University of Massachusetts at Amherst. http://centaurus.cs.umass.edu/~wagner/threadshtml/tutorial.html

48. Ward Rosenberry & Jim Teague Distributing Applications Across DCE and Windows NT USA, Sebastopol: O'Reilly & Associates, Inc., 1993. - 302 p.

49. Ward Rosenberry, David Kenney & Gerry Fisber Understanding DCE USA, Sebastopol: O'Reilly & Associates, Inc., 1992. - 266 p.

50. Whang K.-Y. Index Selection in Relational Databases // Found. Data Organ. Proc. Int. Conf., Kyoto, Japan, May 22-24, 1985. New York; London, 1987.- P. 487-500

51. Yu C.T., Gun K.-C., Zhang W., Templeton M., Brill D., Chen A.L.P. Algorithms to Process Distributed Queries in Fast Local Networks // IEEE Trans. Comput.- 1987,- 36, N 10. P. 1153-1164

52. Аверкин A.H., Блишун А.Ф., Гаврилова T.A., Осипов Г.С. Приобретение и формализация знаний // Искусственный интеллект. М.: Радио и связь, 1990. - С. 65-76.

53. Автоматизация проектирования, идентификация и управление в сложных системах / Под. ред. В.П. Тарасенко. Томск: Изд-во HTJI, 1997. - 264с.

54. Автоматизированная система проектирования (АСП-П) капитальной планировки орошаемых земель на ЭВМ "Минск-22М" (основные положения, алгоритмы, программы и инструкции по эксплуотации). Фрунзе, 1974.

55. Автоматизированная система проектирования двухсторонних печатных плат печатного монтажа (ППП-АСППП). М.: НИИмаш, 1982. - 60 с.

56. Банахан М., Ратгер Э. Введение в операционную систему UNIX. М.: Радио и связь, 1986. -341с.

57. Барцев С.И., Охонин В.А. Адаптивные сети обработки информации. Красноярск: Препринт ИФ СО АН СССР, 1986, №59Б. - 20с.

58. Беляков М.И., Рабовер Ю.И., Фридман A.JI. Мобильная операционная система. -М.: Радио и связь, 1991 -208 с.1

59. Бондаренко В.П. и др. Отображение информации в АСУ реального времени. — Томск: Изд-во Том. Ун-та, 1993,— 169с.

60. Браун П. Введение в операционную систему UNIX. -М.: Мир, 1987. -287 с.

61. Вальковский В.А. Лекции по параллельному программированию Новосибирск: НГУ, 1982 -88с

62. Вальковский В.А. Распараллеливание алгоритмов и программ. Структурный подход. М.: Радио и Связь, 1989

63. Вальковский В.А. Формальные модели параллельных программ и вычислений. Параллельные операторные схемы. Учебное пособие. Новосибирск., 1984

64. Вальковский В.А., Котов В.Е., Марчук А.Г., Миренков H.H. Элементы параллельного программирования. М.: Радио и Связь, 1983 - 240 с.

65. Глухов А.О. Автоматизация компоновочных процессов в системах отображения информации/ Сборник докладов SCM'98. СПб: СПбЭТУ, 1998 - 4с.

66. Глухов А.О. Способ повышение эффективности эвристического метода оптимизации в условиях объектно-ориентированных систем / Сборник докладов SCM'99. СПб: СПбЭТУ, 1999, с.228-232

67. Глухов Д.О., Глухов А.О., Сурто С.Г. "Методы получения динамического стереоизображения на ПЭВМ по виртуальной модели трехмерного пространства'Удоклад на научной конференции/. Новополоцк: ПГУ, 1995.

68. Глухов Д.О., Глухов А.О., Трофимов В.В. Мониторинг по нечетким продукционным правилам в сложных динамических системах с изменяющейся структурой / Вестник факультета менеджмента СПбГУ СПб: СПбГУ, 1998. - 5с.

69. Готье Р. Руководство по операционной системе UNIX. -М.: Финансы и статистика, 1985. -232с.

70. Гради Буч. Объектно-ориентированный анализ и проектирование с примерами приложений на С++, 2-е изд. М.: "Издательство Бином", СПб.: "Невский диалект", 1998. - 560 с.

71. Громов Ю.Ю.,Татаренко С.И. Программирование на языке СИ: Учебное пособие. -Тамбов, 1995. 169 с.

72. Дунин-Барковский B.JI. Нейрокибернетика, нейроинформатика, нейрокомпьютеры. Ростов-на-Дону: НИИ нейрокибернетики им. А.Б.Когана РГУ, 1996.

73. Дункан Р. Инкапсуляция данных и наследование свойств в СИ++ PC Magazine - 1991. - N3.

74. Дэвид Чеппел Технологии ActiveX и OLE / Пер. с англ. М.: Издательский отдел «Русская редакция» ТОО «Channel Trading Ltd.», 1997. - 320 с.

75. Задачи синтеза оптимальных модульных диалоговых систем / Институт проблем управления. -М., 1989. 44с.

76. Иващенко H.H. Автоматическое регулирование. Теория и элементы систем. М.: «Машиностроение», 1973. - 606с.

77. Казупеев В. М. Разработка и исследования структур нечеткого логического вывода в системах обработки нечеткой информации и знаний: дис. на соиск. учен. степ, к.т.н. Таганрог: Таганрогский государственный радиотехнический университет, 1997. - 132с.

78. Калиниченко Л.А., Когаловский М.Р. Интероперабильность брокеров в стандарте CORBA 2.0. СУБД, N 3, 1996

79. Керниган Б.В., Пайк P. UNIX Универсальная среда программирования. -М.: Финансы и статистика, 1992 -304 с.80