Разработка и исследование распределенных алгоритмов аппроксимации и оптимизации в условиях многоагентных систем

• Автор: Глухов, Алексей Олегович
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 1999
• Место защиты: Новополоцк
• Количество страниц: 191 с.

Содержание
ВВЕДЕНИЕ
ГЛАВА 1. ПРОБЛЕМА РАСПРЕДЕЛЕННОГО ПОИСКА РЕШЕНИЯ ЗАДАЧ ОПТИМИЗАЦИИ И АППРОКСИМАЦИИ В СОВРЕМЕННЫХ ПРОГРАММНЫХ СИСТЕМАХ
1.1. Составляющие проблемы распределенного поиска
1.2. Объектно-ориентированный подход
1.3. Обзор объектно-ориентированных языков программирования
1.4. Обзор объектно-ориентированных технологий разработки программных
систем
1.5. Архитектура открытых систем
1.6. Принципы построения распределенных объектно-ориентированных
программных систем
Особенности организации распределенных вычислений
Сетевые вычисления сегодня
1.7. Анализ существующих подходов к решению задач оптимизации в
условиях многоагентных систем
1.8. Анализ возможностей адаптации существующих методов решения
задач оптимизации к условиям многоагентных систем
Использование метода динамического программирования
Использование традиционных методов для решения потоковых задач
Использование традиционных методов для решения задачи коммивояжера

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

ГЛАВА 2. РАЗРАБОТКА ОБЪЕКТНО-РАСПРЕДЕЛЕННЫХ АЛГОРИТМОВ
АППРОКСИМАЦИИ И ОПТИМИЗАЦИИ
2.1. Формализация описания многоагентной системы
2.2. Постановка задачи оптимизации с использованием программных
агентов
Общая постановка задачи оптимизации с использованием программных
агентов
Рассмотрение различных вариантов задачи оптимизации
Пример 1. Транспортная задача
Пример 2. Задача составления расписания
Пример 3. Задача календарного планирования
Пример 4. Задача коммивояжера
Пример 5. Задача о наилучшем размещении объектов
2.3. Выработка общего подхода к решению задач оптимизации с
использованием АГЕНТОВ..:
Система локальных эвристик
Критерий оптимальности
Система оповестительных сообщений
Объектно-распределенный алгоритм поиска
Оптимизирующая объектная модель
2.4. Построение оптимизирующих объектных моделей
Конкретизация диаграммы классов оптимизирующей объектной модели
Диаграмма объектов оптимизируюгцей объектной модели
Семантика сообщений оптимизирующей объектной модели
2.5. Кластеризация объектной системы
2.6. Аппроксимация на саморазвивающихся агентных структурах
Введение
Постановка задачи
Объектно-распределенный алгоритм решения задачи
2.7. ВЫВОДЫ
ГЛАВА 3. ИССЛЕДОВАНИЕ ОБЪЕКТНО-РАСПРЕДЕЛЕННЫХ АЛГОРИТМОВ АППРОКСИМАЦИИ И ОПТИМИЗАЦИИ
3.1. Программная реализация

Структура программы исследования объектно-распределенных алгоритмов
оптимизации
3.2. Язык 01ІИСАНИЯ ТЕСТОВЫХ ЗАДАЧ
3.3. Объектно-распределенный алгоритм поиска решения транспортной
ЗАДАЧИ
3.4. Объектно-распределенный алгоритм поиска решения задачи
коммивояжера
3.5. Объектно-распределенный алгоритм поиска решения задачи о
наилучшем размещении
3.6. Объектно-распределенный алгоритм аппроксимации
3.7. Оценка эффективности объектно-распределенных алгоритмов
оптимизации
3.8. Оценка эффективности алгоритма объетно-распределен ной
аппроксимации
3.9. Практические результаты использования алгоритмов
3.10. Выводы
ЗАКЛЮЧЕНИЕ
СПИСОК ЛИТЕРАТУРЫ
ПРИЛОЖЕНИЯ
Приложение 1. Примеры файлов данных и результаты исследования алгоритма объектно-распределенного поиска решения задачи коммивояжера Приложение 2. Листинг модуля решения задачи коммивояжера с использованием объектно-распределенного поиска
Приложение 3. Листинг модуля решения задачи о наилучшем размещении с использованием объектно-распределенного поиска
Приложение 4. Результат работы подсистемы формирования кадров в режиме отображения А) и в режиме редактирования Б) информации в программе ИНСАИТ
Приложение 5. Спецификация объектов для решения транспортной задачи, задачи коммивояжера, задачи о наилучшем размещении
Приложение 6. Листинг процедуры обучения объектной системы при решении задачи аппроксимации, спецификации объектов БОБ.Н и листинг модуля БОБ.СРР

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

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