Модели и методы решения задачи распределения заданий в мультипроцессорной системе

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

СОДЕРЖАНИЕ
ВВЕДЕНИЕ.
ГЛАВА 1. ПОСТАНОВКА И МНОГОКРИТЕРИАЛЬНАЯ МАТЕМАТИЧЕСКАЯ МОДЕЛЬ ЗАДАЧИ РАСПРЕДЕЛЕНИЯ ЗАДАНИЙ В МУЛЬТИПРОЦЕССОРНОЙ СИСТЕМЕ

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

1.2. Анализ критериев оптимизации распределения выполнения заданий в мультипроцессорной системе

1.2. Математическая модель задачи.

1.3. Обзор методов решения задачи многокритериальной оптимизации

ГЛАВА 2. МЕТОДЫ РЕШЕНИЯ ЗАДАЧИ ПА ОСНОВЕ ДИСКРЕТНОЙ И СООТВЕТСТВУЮЩЕЙ НЕЙРОСЕТЕВОЙ МАТЕМАТИЧЕСКИХ МОДЕЛЕЙ.

2.1. Метод решения на основе детерминированной асинхронной дискретной сети Хопфилда

2.2. Метод имитации отжига

2.3. Метод имитации отжига на основе стохастической асинхронной дискретной сети Хопфилда
2.4. Комбинированный метод
2.5. Оценка трудоемкости алгоритмов.
2.6. Экспериментальное исследование алгоритмов
2.6.1. Исследование параметров метода имитации отжига
2.6.2. Сравнение алгоритмов решения задачи.
ГЛАВА 3. МЕТОДЫ РЕШЕНИЯ ЗАДАЧИ НА ОСНОВЕ НЕПРЕРЫВНОЙ И СООТВЕТСТВУЮЩЕЙ НЕЙРОСЕТЕВОЙ МАТЕМАТИЧЕСКИХ МОДЕЛЕЙ.
3.1. Непрерывная математическая модель
3.2. Методы решения задач непрерывной оптимизации.
3.2.1. Метод ФлетчсраРивса
3.2.2. Нейросстевой метод
3.3. Экспериментальное исследование разработанных алгоритмов.
3.3.1. Исследование параметров алгоритма ФлетчераРивса
3.3.2. Исследование параметров непрерывной сети Хопфилда
3.3.3. Сравнение разработанных алгоритмов решения задачи
ГЛАВА 4. ОПИСАНИЕ ПРОГРАММНОГО КОМПЛЕКСА ОПТИМИЗАЦИЯ РАСПРЕДЕЛЕНИЯ ЗАДАНИЙ В МУЛЬТИПРОЦЕССОРНОЙ СИСТЕМЕ.
4.1. Структура программного комплекса.
4.3. Руководство пользователя.
ЗАКЛЮЧЕНИЕ
СПИСОК ЛИТЕРАТУРЫ


Экспериментально исследованы параметры, влияющие на сходимость методов имитации отжига, предложен алгоритм вычисления начальной температуры, предложены и исследованы способы определения нового состояния из окрестности текущего состояния. Проведена оценка трудоемкости и сравнительный анализ разработанных алгоритмов. Поскольку рассматриваемая задача является ЫР -полной, для се решения используются приближенные методы дискретной оптимизации. Для решения задачи распределения заданий в мультипроцессорной системе приближенными дискретными методами был осуществлен переход от условной задачи к безусловной задаче оптимизации. Среди множества приближенных дискретных методов безусловной оптимизации для решения исходной задачи были выбраны следующие известные методы: метод имитации отжига [8], нейросетевой метод на основе детерминированной асинхронной дискретной сети Хопфилда (АДСХ) [, ], метод имитации отжига на основе стохастической асинхронной дискретной нейронной сети Хопфилда (САДСХ) []. Помимо известных методов предлагается и исследуется комбинированный метод, сочетающий детерминированную и стохастическую асинхронные дискретные сети Хопфилда и метод имитации отжига. Алгоритм метода имитации отжига представляет собой алгоритмический аналог физического процесса управляемого охлаждения металлов. Суть алгоритма заключается в следующем. В процессе работы алгоритма температура Т понижается с коэффициентом охлаждения ае(0,1). При каждой температуре предпринимается т попыток изменения состояния системы, которые могут привести к увеличению или уменьшению целевой функции. Д/у’ - положительное приращение целевой функции. Процесс останавливается, когда не происходит уменьшения целевой функции при 5 последовательных температурах. Для улучшения сходимости алгоритма метода имитации отжига были исследованы следующие его параметры: начальная температура Гтах, способ выбора нового состояния из окрестности текущего состояния, коэффициент охлаждения а, число итераций при постоянной температуре т. Для вычисления начальной температуры в диссертации предложен алгоритм, обеспечивающий принятие около % переходов, увеличивающих значение целевой функции. В работе также были предложены способы выбора нового состояния. Проведенные численные эксперименты показали, что, чем ближе значение коэффициента а к единице и чем выше число итераций т, тем меньше погрешность получаемых решений, но тем больше времени требуется для нахождения решения. Для решения исходной задачи методом, основанным на детерминированной асинхронной дискретной сети Хопфилда, построена нейросетевая модель. Время / дискретная величина. Элементы хг вектора нейронов X соответствуют плану распределения заданий. Традиционно энергия дискретной сети Хопфилда представляется в виде функции Ляпунова. Каждый нейрон преобразует входной сигнал в выходной сигнал с помощью нелинейной функции активации. В качестве функции активации /(/? Сеть функционирует в асинхронном режиме. Для решения задачи с помощью дискретной сети Хопфилда необходимо преобразовать целевую функцию к виду функции Ляпунова. Известно, что динамика функционирования сети Хопфилда обеспечивает схождение сети к локальному экстремуму. Для нахождения глобального или близкого к глобальному решению необходимо запускать сеть из различных начальных состояний и выбирать из полученных решений наилучшее. В диссертации для решения исходной задачи рассматривается алгоритм метода имитации отжига на основе стохастической асинхронной дискретной сети Хопфилда. В отличие от детерминированной сети Хопфилда, где состояния нейрона однозначно определяются детерминированной процедурой, реализующей асинхронную динамику, нейронные стохастические сети принимают состояния 0 или 1 в соответствии с процедурой, включающей элемент случайности. В работе был предложен комбинированный метод, который реализует алгоритм имитации отжига на основе стохастической асинхронной дискретной сети Хопфилда (САДСХ), но, в дополнение к нему, из промежуточных состояний запускается детерминированная асинхронная дискретная сеть Хопфилда (АДСХ), которая обеспечивает быстрое нахождение локальных оптимумов. Затем из полученных решений выбирается наилучшее.