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

Размещено на http://www.allbest.ru/

На правах рукописи

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

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

Специальность 05.13.18 - Математическое моделирование, численные методы и комплексы программ

КАЙНОВ АНДРЕЙ СЕРГЕЕВИЧ

Казань - 2009

Работа выполнена в Казанском государственном техническом университете им. А.Н.Туполева.

Научный руководитель: доктор технических наук, профессор

Емалетдинова Лилия Юнеровна

Официальные оппоненты: доктор физико-математических наук, профессор

Елизаров Александр Михайлович

кандидат технических наук, доцент

Катасёв Алексей Сергеевич

Ведущая организация: Марийский государственный технический университет

Защита состоится 27 марта 2009 года в 14.00 часов на заседании диссертационного совета Д 212.079.01 в Казанском государственном техническом университете им. А.Н. Туполева по адресу: 420111, г. Казань, ул. К. Маркса, 10.

С диссертацией можно ознакомиться в библиотеке Казанского государственного технического университета им. А.Н.Туполева.

С авторефератом можно ознакомиться на сайте Казанского государственного технического университета им. А.Н.Туполева www.kai.ru.

Автореферат разослан 14 февраля 2009 г.

Ученый секретарь диссертационного совета

доктор физ.-мат. наук, профессор П. Г. Данилаев

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

Постановка задачи распределения и упорядочения заданий в мультипроцессорной системе является известной в теории расписаний и рассматривается в работах Конвея Р.В., Максвелла В.Л., Миллера Л.В., Танаева В.С., Шкурбы В.В., Левина В.И. и других. NP-полнота этой задачи не позволяет эффективно ее решать точными методами, поэтому необходимо разрабатывать алгоритмы на основе приближенных методов. Появление искусственных нейронных сетей как математического инструментария распараллеливания вычислений делают актуальной задачу разработки нейросетевых математических моделей, методов и алгоритмов оптимального распределения заданий в мультипроцессорной системе.

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

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

1. Исследовать вычислительную сложность задачи распределения заданий в мультипроцессорной системе с разными критериями оптимизации;

2. Разработать нейросетевые дискретную и непрерывную математические модели распределения заданий в мультипроцессорной системе;

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

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

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

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

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

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

2. Построена двухкритериальная модель булевой оптимизации распределения заданий в мультипроцессорной системе, и на ее основе разработаны однокритериальные дискретная, непрерывная и нейросетевые модели;

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

4. Разработаны алгоритм определения начальной температуры для методов имитации отжига, выражения для вычисления временного шага и оценки временной константы нейронов алгоритма непрерывной нейронной сети Хопфилда.

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

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

Апробация работы. Основные результаты работы докладывались и обсуждались на следующих международных, всероссийских конференциях и семинарах: XII Международная молодежная научная конференция «Туполевские чтения» (Казань, 2004), XVI Международная научно-техническая конференция: «Математические методы и информационные технологии в экономике, социологии и образовании» (Пенза, 2005), VIII Международная научно-практическая конференция «Фундаментальные и прикладные проблемы приборостроения, информатики и экономики» (Москва, 2005), IV Общероссийская конференция с международным участием «Новейшие технологические решения и оборудование» (Москва, 2006), Всероссийская научная конференция студентов и аспирантов (Вологда, 2007), XV Международная молодежная научная конференция «Туполевские чтения» (Казань, 2007), заочная электронная конференция «Фундаментальные и прикладные проблемы математики» (Рос. акад. естествознан., декабрь 2008).

Публикации. По теме диссертации опубликовано 10 научных работ, включая 2 статьи и 8 тезисов докладов.

Структура и объем диссертации. Диссертационная работа состоит из введения, четырех глав, заключения, библиографического списка, двух приложений. Работа содержит 142 страницы машинописного текста, 36 рисунков и 24 таблицы. Список литературы включает 87 наименований.

мультипроцессорный распределение задание нейронный

Содержание работы

Во введении содержится обоснование актуальности проблемы, основные научные положения и результаты.

Первая глава посвящена постановке задачи, анализу критериев оптимизации распределения заданий в мультипроцессорной системе, построению математической модели задачи многокритериальной оптимизации и обзору методов ее решения.

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

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

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

Критерий 1. Если необходимо завершить выполнение всех заданий как можно раньше и при этом не имеет значения порядок выполнения заданий, то применяется критерий минимизации «длины» расписания:

(1)

Критерий 2. Если необходимо уменьшить время пребывания задания в системе, то более подходящим является критерий минимизации среднего времени завершения выполнения заданий:

,(2)

где - время, прошедшее с момента начала обработки первого задания до момента окончания обработки -го задания, т.е. это время нахождения задания в системе.

Критерий 3. Если важно, чтобы все компьютеры эксплуатировались одинаково, то необходимо минимизировать разность между загруженностью компьютеров:

(3)

Для случая идентичных компьютеров данный критерий также сокращает «длину» расписания, в противном случае минимизация «длины» расписания не обеспечивается. Эта ограниченность является недостатком критерия (3).

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

(4)

В данной работе был проведен анализ критериев (1)-(4) с точки зрения вычислительной сложности рассматриваемой задачи. В таблице 1 показаны классы сложности задачи составления расписаний с критериями (1)-(4).

Таблица 1

Классы сложности задачи составления расписаний

Критерий	Класс задачи
(1)	-полная
(2)
(3)	-полная
(4)
(3) и (4)	-полная

В литературе доказана -полнота задачи с критерием (1) и показано, что задача с критерием (2) сводится к задаче нахождения потока минимальной стоимости, для которой существует эффективный алгоритм решения, сложность которого равна , где - размерность задачи.

Для критерия (3) в диссертации сформулирована и доказана следующая теорема.

Теорема 1. Задача распределения заданий по компьютерам в соответствии с критерием (3) является -полной.

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

Указанные недостатки критериев (3) и (4) частично компенсируются за счет их совместного использования, поэтому при составлении расписаний целесообразно использовать оба критерия одновременно. Таким образом, мы получаем -полную задачу многокритериальной оптимизации.

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

Математическая модель задачи составления расписаний на основе критериев (3)-(4) формулируется следующим образом. Пусть - план распределения заданий (расписание), где - число компьютеров в мультипроцессорной системе, - число заданий:

.

Требуется определить план распределения заданий , обеспечивающий

(5)

и

,(6)

где при следующих ограничениях:

(7)

(8)

Поскольку задача распределения заданий в мультипроцессорной системе (5)-(8) относится к классу задач нелинейной булевой многокритериальной оптимизации, имеет место противоречивость критериев (5) и (6), связанная с невозможностью найти оптимальное допустимое решение задачи (5)-(8) сразу по двум целевым функциям. Поэтому для таких задач необходимо искать компромиссное эффективное решение, учитывающее «важность» каждой целевой функции.

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

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

(9)

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

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

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

(10)

где - весовые коэффициенты целевых и штрафной функций.

Среди множества приближенных дискретных методов оптимизации для решения исходной задачи (10) были выбраны следующие известные методы:

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

2. Нейросетевой метод на основе детерминированной асинхронной дискретной сети Хопфилда (АДСХ);

3. Метод имитации отжига на основе стохастической асинхронной дискретной нейронной сети Хопфилда (САДСХ).

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

Алгоритм метода имитации отжига представляет собой алгоритмический аналог физического процесса управляемого охлаждения металлов. Суть алгоритма заключается в следующем. Процесс охлаждения начинается с некоторого начального состояния при начальной температуре . Начальное состояние генерируется с помощью датчика случайных чисел следующим образом: для каждой переменной в соответствии с равномерным законом распределения случайных величин генерируется число из диапазона . Тогда переменные принимают значения

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

Для улучшения сходимости алгоритма метода имитации отжига были исследованы следующие его параметры:

· начальная температура ,

· способ выбора нового состояния из окрестности текущего состояния ,

· коэффициент охлаждения ,

· число итераций при постоянной температуре .

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

В работе были предложены способы выбора нового состояния .

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

Определение 2. Под размером окрестности будем понимать мощность множества состояний, входящих в окрестность.

Окрестность любого состояния имеет размер, равный состояний. Будем выбирать состояние из окрестности состояния одним из следующих трех способов:

I способ. Состояние получается из путем изменения значения переменной ; следующее состояние получается из путем изменения значения переменной и т.д. Таким образом, переменные изменяются в порядке их нумерации.

II способ. Состояние получается из путем изменения значения одной переменной , выбираемой случайным образом.

III способ. Генерируется случайным образом вектор номеров переменных такой, что: каждый номер встречается в ней ровно 1 раз; вектор содержит номера всех переменных. Состояние получается из путем последовательного изменения значений переменных с номерами из вектора .

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

Для решения исходной задачи (10) методом, основанным на детерминированной асинхронной дискретной сети Хопфилда, построена нейросетевая модель. Пусть - состояния нейронов, где индекс - кодирует номер компьютера, а - номер задания. - вектор состояний нейронов в момент времени . Время дискретная величина. В начальный момент времени сеть характеризуется некоторым вектором начальных состояний. Элементы вектора нейронов соответствуют плану распределения заданий.

Традиционно энергия дискретной сети Хопфилда представляется в виде функции Ляпунова:

,(11)

где - число компьютеров, - число заданий, - вес связи между нейронами и , - порог активизации нейрона .

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

.

Асинхронная динамика функционирования сети задается следующим законом:

,(12)

где активный нейрон выбирается из условия:

,

где , - множество нейронов, которые могут изменить свое состояние в момент времени .

Для решения задачи (10) с помощью дискретной сети Хопфилда необходимо преобразовать выражение (10) к виду функции Ляпунова (11). В результате преобразований энергия сети для задачи распределения заданий в мультипроцессорной системе примет вид:

,(13)

где - символ Кронекера: .

Из формул (11) и (13) следует, что веса синапсов примут вид:

,(14)

пороги нейронов равны:

(15)

С учетом выражений (14) и (15) целевую функцию (13) можно записать в краткой форме:

.(16)

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

В диссертации для решения исходной задачи рассматривается алгоритм метода имитации отжига на основе стохастической асинхронной дискретной сети Хопфилда. В отличие от детерминированной сети Хопфилда, где состояния нейрона однозначно определяются детерминированной процедурой, реализующей динамику (12), нейронные стохастические сети принимают состояния 0 или 1 в соответствии с процедурой, включающей элемент случайности. Для каждого нейрона в сети определяется вероятность нахождения этого нейрона в состоянии 1 по следующей формуле:

,

где взвешенная сумма входов нейрона определяется по формуле:

 .

Затем, путем генерации случайного числа и сравнения его с вероятностью , определяется реальное состояние нейрона .

В работе был предложен комбинированный метод, суть которого иллюстрирует рис. 1.

Этот метод реализует алгоритм имитации отжига на основе стохастической асинхронной дискретной сети Хопфилда (САДСХ), но, в дополнение к нему, из промежуточных состояний запускается детерминированная асинхронная дискретная сеть Хопфилда (АДСХ), которая обеспечивает быстрое нахождение локальных оптимумов . Затем из решений выбирается наилучшее.

Размещено на http://www.allbest.ru/

Для каждого разработанного алгоритма была проведена оценка трудоемкости, представленная в таблице 2.

Таблица 2

Трудоемкость разработанных алгоритмов

Алгоритм	Трудоемкость
Алгоритм решения задачи сетью Хопфилда (АДСХ)	, где - число начальных состояний
Алгоритм имитации отжига
Алгоритм имитации отжига на основе стохастической сети Хопфилда (САДСХ)
Комбинированный алгоритм

Таким образом, все рассмотренные алгоритмы имеют полиномиальную сложность, но минимальную сложность имеет алгоритм поиска решения на основе сети Хопфилда (АДСХ).

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

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

По аналогии с дискретной моделью (9), (7)-(8) формулируется непрерывная модель задачи распределения заданий в мультипроцессорной системе, при этом переменные плана распределения рассматриваются как непрерывные величины. Необходимо определить план, обеспечивающий минимум целевой функции:

(17)

при следующих ограничениях:

,(18)

.(19)

Далее осуществляется переход от задачи условной оптимизации (17)-(19) к задаче безусловной оптимизации:

.(20)

Для интерпретации некоторого решения непрерывной модели (20) как плана распределения заданий оно подвергается процедуре округления в соответствии со следующим правилом:

.

Среди множества численных методов поиска приближенного экстремума были выбраны два метода:

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

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

Метод Флетчера-Ривса состоит в построении последовательности точек , где , , обеспечивающей убывание целевой функции , т.е. .

Точки последовательности вычисляются по правилу:

,

где величина шага определяется для каждого значения из условия:

.(21)

Направление убывания определяется по формуле:

,

где вектор-градиент и коэффициент определяются как:

и

(22)

В формуле (22) и далее используется Евклидова норма вектора, вычисляемая следующим образом:

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

В качестве критериев останова принимается выполнение хотя бы одного из следующих условий:

или(23)

(24)

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

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

Нейродинамическая модель непрерывной сети Хопфилда описывается системой дифференциальных уравнений:

, (25)

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

В работе в качестве функции активации используется логистическая функция:

,

где - коэффициент передачи нейрона. Функция активации имеет обратную функцию:

.

Графики этих функций изображены на рис.2.

Размещено на http://www.allbest.ru/

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

Итак, из исходной непрерывной модели (17)-(19) формируется нейросетевая модель безусловной оптимизации следующего вида:

(26)

Заметим, что при нейросетевом подходе состояния нейронов благодаря использованию логистической функции активации находятся в интервале (0,1), а конечный результат работы сети округляется. Поэтому штраф, соответствующий ограничению (19), не включается в целевую функцию (26).

В качестве энергии непрерывной сети с непрерывными состояниями используют функцию Ляпунова, которая имеет следующий вид:

(27)

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

Теорема 2. Энергия нейронной сети, динамика которой описывается уравнением (25), со временем не возрастает, а скорость изменения энергии не изменяется тогда и только тогда, когда состояние системы сосредотачивается в одной точке.

Для функции (27) необходимые и достаточные условия локального минимума имеют вид.

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

, .(28)

Теорема 4 (Достаточные условия локального минимума). Если в некоторой точке выполняются необходимые условия минимума (28), и квадратичная форма

является положительно определенной, то в этой точке энергия нейронной сети (27) имеет локальный минимум.

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

Теорема 5. Существует такой , что, если точка является решением системы дифференциальных уравнений (25), и выполняется условие или, то является точкой локального минимума функции энергии (27).

Непрерывная сеть Хопфилда реализует метод Эйлера решения задачи Коши для систем дифференциальных уравнений. Производная в выражении (25) заменяется ее разностной аппроксимацией, и получается итерационная процедура:

,(29)

При этом предлагается следующий критерий останова:

.(30)

Левая часть неравенства (30) выражает относительную величину изменения напряжений на нейронах.

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

На скорость сходимости сети и качество получаемых решений оказывают влияние следующие параметры: начальная точка , величина шага , критерий останова , временная константа нейрона .

Начальные точки предлагается выбирать из окрестности центра единичного гиперкуба в соответствии с формулой:

, , ,

где случайное число генерируется датчиком псевдослучайных чисел в соответствии с равномерным законом распределения.

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

.

В качестве критерия останова в условии (30) используется относительное изменение напряжений на нейронах, поэтому величина должна быть малым положительным числом, близким к нулю.

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

,

где и .

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

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

1. Численные эксперименты показали, что наилучшие результаты для типовых примеров были получены, когда начальная точка не отклонялась от центра единичного гиперкуба более чем на 40%.

2. Исследование критериев останова (23), (24) и параметров и алгоритма Флетчера-Ривса позволило выявить их недостатки, связанные с трудностью подбора параметров и . В работе обоснована целесообразность применения для рассматриваемой задачи модифицированного критерия при :

3. Наилучшие результаты использования непрерывной сети Хопфилда с критерием останова (30) были получены при значениях параметра . Кроме того, было отмечено, что при одном и том же значении количество итераций функционирования синхронной сети Хопфилда практически не зависит от размерности задачи.

Экспериментальные исследования позволили сделать следующие выводы:

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

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

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

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

Для разработки программного комплекса использовалась среда Delph 6, язык разработки - Object Pascal. В работе приведены требования к программному и аппаратному обеспечению.

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

В работе рассматривается технология интерактивного взаимодействия пользователя с программой, которая включает три основных этапа:

1. Ввод исходных данных задачи;

2. Настройка параметров задачи и алгоритмов решения;

3. Решение задачи с помощью выбранного алгоритма.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

1. Сформулирована и доказана теорема о том, что задача распределения заданий в мультипроцессорной системе с равномерной загрузкой компьютеров является -полной.

2. Построена двухкритериальная модель булевой оптимизации распределения заданий в мультипроцессорной системе, и на ее основе разработаны однокритериальные дискретная, непрерывная и соответствующие нейросетевые модели.

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

4. Доказано, что если непрерывная сеть Хопфилда имеет устойчивые состояния вблизи углов единичного гиперкуба, то эти состояния обеспечивают минимум функции энергии сети.

5. Разработаны формулы, алгоритмы и даны рекомендации по выбору параметров разработанных алгоритмов.

Основное содержание диссертации изложено в следующих публикациях

1. Емалетдинова Л.Ю., Кайнов А.С. Дискретная нейросетевая модель оптимизации распределения заданий по нескольким компьютерам // Вестник Казанского государственного технического университета им. А.Н. Туполева, №1(46), 2007. С. 80-83.

2. Кайнов А.С. Математическая модель распределения заданий по нескольким компьютерам // Тез. докл. Междунар. науч. конф. «XII Туполевские чтения», Т. III, Казань, 2004. С. 22-24.

3. Зайнуллина Э.Ш., Кайнов А.С. Особенности нейросетевого моделирования задачи комбинаторной оптимизации в распределенной среде // Сб. ст. XVI Междунар. науч.-техн. конф. «Математические методы и информационные технологии в экономике, социологии и образовании: сборник статей», Пенза, 2005. С. 451-454.

4. Емалетдинова Л.Ю., Кайнов А.С. Нейросетевые модели оптимизации распределения заданий по нескольким компьютерам // Науч. тр. VIII Междунар. науч.-практ. конф. «Фундаментальные и прикладные проблемы приборостроения, информатики и экономики», Московск. гос. академ. приборостроен. и информат, Москва, 2005. С. 71-75.

5. Максютин С.А., Кайнов А.С. Olap-технологии в жилищно коммунальной отрасли региона // IV общерос. конф. с междунар. участ. «Новейшие технологические решения и оборудование», Рос. Академ. Естествознан., Успехи современного естествознания, №6, 2006. С. 38-39.

6. Зайнуллина Э.Ш., Кайнов А.С. Методика подбора коэффициентов при решении оптимизационной задачи с помощью нейронной сети Хопфилда // Матер. всерос. науч. конф. студ. и асп. «Молодые исследователи - регионам», Т. I, Вологда, 2007. С. 103-104.

7. Зайнуллина Э.Ш., Кайнов А.С. Выбор активного нейрона при асинхронном функционировании сети Хопфилда // Тез. докл. Междунар. науч. конф. «XV Туполевские чтения», Т. III, Казань, 2007. С. 18-20.

8. Кайнов А.С. Непрерывная нейросетевая модель оптимизации распределения заданий по нескольким компьютерам // Тез. докл. Междунар. науч. конф. «XV Туполевские чтения», Т. III, Казань, 2007. С. 24-26.

9. Кайнов А.С. Нейросетевой метод решения задач дискретной оптимизации // Заочная электронная конференция «Фундаментальные и прикладные проблемы математики». Рос. акад. естествознан., 15-20 декабря 2008 г.

http://www.rae.ru/zk/?section=rubricator&op=article&id=4303.

10. Кайнов А.С. Решение задачи распределения заданий в мультипроцессорной системе методом Флетчера-Ривса // Заочная электронная конференция «Фундаментальные и прикладные проблемы математики». Рос. акад. естествознан., 15-20 декабря 2008 г.

http://www.rae.ru/zk/?section=rubricator&op=article&id=4302.

Формат 60х84 1/16. Бумага офсетная. Печать офсетная.

Печ.л. 1,25. Усл.печ.л. 1,16. Усл.кр.-отт. 1,16. Уч.-изд.л. 1,0.

Тираж 100. Заказ М 22.

Типография Издательства Казанского государственного технического университета им. А.Н.Туполева

420111, Казань, К. Маркса, 10.

Размещено на Allbest.ru

...