автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Модели и методы решения задачи распределения заданий в мультипроцессорной системе

На правах рукописи 0034В2563

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

МОДЕЛИ И МЕТОДЫ РЕШЕНИЯ ЗАДАЧИ РАСПРЕДЕЛЕНИЯ ЗАДАНИЙ В МУЛЬТИПРОЦЕССОРНОЙ СИСТЕМЕ

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

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

гзоиз^

Казань - 2009

003462563

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

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

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

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

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

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

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

университет

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

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

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

Автореферат разослан фв^^аМг 2009 г.

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

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

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

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

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

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

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

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

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

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

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

4. Разработать программный комплекс, реализующий разработанные

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

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

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

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

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

равномерной загрузкой компьютеров;

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

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

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

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

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

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

технологические решения и оборудование» (Москва, 2006), Всероссийская научная конференция студентов и аспирантов (Вологда, 2007), XV Международная молодежная научная конференция «Туполевские чтения» (Казань, 2007), заочная электронная конференция «Фундаментальные и прикладные проблемы математики» (Рос. акад. естествознан., декабрь 2008).

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

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

СОДЕРЖАНИЕ РАБОТЫ

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

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

Рассматривается мультипроцессорная система, состоящая из t компьютеров различной производительности. Необходимо распределить п (п » i) заданий по компьютерам. Время х-а выполнения z-ro задания на /"-м

компьютере (/ = 1,f, z = 1,л) известно. В результате распределения заданий для каждого компьютера формируется очередь задач, время выполнения которых на /'-м компьютере равно T¡ (/ =

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

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

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

max{T1,...,T¿}=>mín (1)

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

системе, то более подходящим является критерий минимизации среднего времени завершения выполнения заданий: 1 "

-1>2 => гтип, (2)

«ги

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

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

^Гв-Т^тт (3)

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

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

ЕГ/^пш (4)

/=1

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

Таблица 1

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

шшв ЖШЁШШШ!

(1) ЫР -полная

(2) Р

(3) ЫР -полная

(4) Р

(3) и (4) Л/Р-полная

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

сложность которого равна о(/\/3), где N - размерность задачи.

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

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

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

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

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

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

1, если г - я задача выполняется на /' - м компьютере /. — — \ О, в противном случае

Требуется определить план распределения заданий Х = (х/г)1х;.п, обеспечивающий

=411(ГДХ)-Г/.(Х))2 =>гтнп (5)

и

^г(Х) = X £ тих{г => т'ш, (6)

/и м

где Тр{Х) = (р = V) при следующих ограничениях:

г=1

*йе{0,1} {¡ = й,г = Хп) (7)

¿хй=1(г = Тп) (8)

/=1

Поскольку задача распределения заданий в мультипроцессорной системе (5)-(8) относится к классу задач нелинейной булевой многокритериальной оптимизации, имеет место противоречивость критериев

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

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

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

+ ЛгЦткх1г=>гПп (9)

^ Ы/=1и=1 г=1 ) Мг=1

где /Ц, Дг - положительные весовые коэффициенты целевых функций (5) и (6),

которые являются нормирующими множителями, поскольку частные критерии

имеют различный масштаб измерения.

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

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

условной задачи (9), (7)-<8) к безусловной задаче оптимизации:

/ ч 1 1 1 (" " ' "

ФО^И +Л2Пг*Хй +

А"-1;'=1\,г=1 2=1 У 1=17=1

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

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

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

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

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

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

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

некоторого начального состояния Х° = {^1г\х1.п при начальной температуре Ттах. Начальное состояние Х° = (х^^.л генерируется с помощью датчика случайных чисел следующим образом: для каждой переменной {¡-\i\z-\,п) в соответствии, с равномерным законом распределения случайных величин генерируется число из диапазона (0,1). Тогда

0 0 \\ если Я12 > 0.5

переменные принимают значения х¡, = {

[0, в противном случае.

В процессе работы алгоритма температура Т понижается с

коэффициентом охлаждения а е (0,1). При каждой температуре

предпринимается т попыток изменения состояния X - (Ха)1х(.л системы,

которые могут привести к увеличению или уменьшению целевой функции (10).

Если новое состояние X' системы обеспечивает уменьшение значения

целевой функции, то такой переход системы из состояния X в состояние X'

принимается, в противном случае определяется вероятность этого перехода

АР

р = е г , где ДР = Р(Х')-Р(Х). В соответствии с равномерным законом распределения генерируется случайное число Я из диапазона (0,1). Тогда переход из состояния X в состояние X' принимается, если Я < р. Процесс

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

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

• начальная температура Гтах,

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

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

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

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

В работе были предложены способы выбора нового состояния X'. Определение 1. Под окрестностью некоторого состояния X = (x,z)1xin будем понимать множество состояний, отличных от состояния X значениями

одной переменной xi2 i e(l,...,£} z e (1.....л).

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

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

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

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

Ill способ. Генерируется случайным образом вектор A = ({i,zj)b(n номеров переменных такой, что: каждый номер (¡,z) встречается в ней ровно 1 раз; вектор содержит номера всех переменных. Состояние X' получается из X путем последовательного изменения значений переменных xiz с номерами (i,z) из вектора А.

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

Для решения исходной задачи (10) методом, основанным на детерминированной асинхронной .дискретной сети Хопфилда, построена нейросетевая модель. Пусть хй е{0,1} (/ = \t, 2 = 1,n) - состояния нейронов,

где индекс / - кодирует номер компьютера, а г - номер задания. Х(1)= (х,2{())ы.п - вектор состояний нейронов в момент времени /. Время I дискретная величина. В начальный момент времени сеть характеризуется некоторым вектором Х(0) = (хй(0))1х/п начальных состояний. Элементы

вектора нейронов X соответствуют плану распределения заданий.

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

£(*('))=—£ I í Х>* лхй(*)хл(0+£ (11)

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

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

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

г. п

Хй(* + 1) =

= ('*'**) (,• = ; = (12)

где активный нейрон (/а,га) выбирается из условия: тах |/7/г(ф, . где М0= I 4г.

С.^'о /=1(/=1

/0 = - множество нейронов, которые могут изменить свое

состояние в момент времени t.

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

Е(Х)=~Ш£[*,(- 2)К - + ¿з(- ^+

^ /=1 у'=12=1<7=1

+ £ + Л2Га - ЯзК + Я3П , (13)

/=1г=1

1, если /' = у

где 6ц - символ Кронекера: 6Л =

[0, в противном случае

Из формул (11) и (13) следует, что веса синапсов примут вид: «>й Л = Ы- 2){Щ ~ + А3(- 2)5«, ](1 - 8Н8Щ), (14)

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

^^(¿-•О^ + ^-Дз (15)

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

Е(Х)=~1 2Е1Х>ЙЛ*Й*Л + 06)

2;=1;=1г=1(7=1 /=1г=1

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

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

1 + е 12

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

Ьи = I £ о ш - (' = V; г = \п).

/=1<И

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

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

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

дополнение к нему, из промежуточных состояний X' (/ = 1,2,...) запускается детерминированная асинхронная дискретная сеть Хопфилда (АДСХ), которая обеспечивает быстрое нахождение локальных оптимумов X" (/ = 1,2,...). Затем из решений X'1 (/' = 1,2,...) выбирается наилучшее.

и

Рис. 1. Комбинированный метод

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

Таблица 2

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

Алгоритм Трудоемкость: . Г .

Алгоритм решения задачи сетью Хопфилда (АДСХ) о{к(( х л)2), где к - число начальных состояний

Алгоритм имитации отжига О 'т1ода^п (£хп)2 ] ч ' тах /

Алгоритм имитации отжига на основе стохастической сети Хопфилда (САДСХ) о(т 1ода (£хп)2] Ч ' тах /

Комбинированный алгоритм О ( Т \ \ ' тах ^

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

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

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

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

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

+ (17)

¿/=1/=1^г»1 2=1 ) ¡=1;=1

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

0Дх)=£х&-1 = О = (18)

1=1

9*(Х)=х,Л1-хь)=о{1 = Гьг = *п). (19)

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

1 ( ( ( п п \2 I п п ( I \2

¿ы 1 /=1\г=1 г=1 ) 1=12=1 2=1/=1 )

+ А2Ц х1(1-х,г)2=*тп. (20)

|=1г=1

Для интерпретации некоторого решения X = (х¡г \х1.п непрерывной модели (20) как плана распределения заданий оно подвергается процедуре

(% если х/г г 0.5 округления в соответствии со следующим правилом: х.> = <

[0, если ха < 0.5

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

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

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

Метод Флетчера-Ривса состоит в построении последовательности точек

{х*}, где Хк к = 0,1,..., обеспечивающей убывание целевой

функции я(х*), т.е. я(х*+1)<р(х*).

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

Хк+1> = Хк +1кйк, к = ОД...

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

р(хк тю. (21)

к

Направление убывания О* =(с/£\хг.л определяется по формуле:

ок_(-ур(хк}к = о

ур(хк)+/Зк_^Ок'\ /с > о'

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

1 I Л*, Мх*Т

(22)

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

Решение задачи (21) одномерной минимизации по выбору оптимального

С1р{хк Ок)

шага ¡к находится, исходя из необходимых —'--—' = 0 и достаточных

<Хк

-1-г-5—' > 0 условии экстремума, и сводится к нахождению корней

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

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

ЦуЯ^Ми^ или (23)

¡х*+1-х"|<*2

(24)

\Хк-Хк-Ч<е2

\р(хк)-р{х^\<Е2

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

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

В диссертации исследовался метод решения на основе непрерывной синхронной сети Хопфилда. В отличие от дискретной сети Хопфилда, рассмотренной во второй главе, время ¿2:0 и состояния нейронов сети являются непрерывными величинами, Х;г(/)е(0,1) (< = 1,г = 1,п). За Х(/) = (х,г({))Ы п обозначается вектор состояний нейронов в момент времени (. В начальный момент времени сеть характеризуется некоторым вектором Х(0)=(х/г(0))М л начальных состояний.

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

^-¿¿«ЬА/М= = (25)

где и,г(1) - напряжение на нейроне (потенциал нейрона) (¡,г) в момент

времени (,

а ¡я

- вес связи между нейронами (/, г) и (/, д) - пороговое

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

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

1

Пе-"**

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

а Х)2

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

Мг)

Г1(х,>)

Рис. 2. Функция активации: а. График логистической функции активации,

б. Гра'фик обратной функции активации

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

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

2ыуии=1 2=1 ) /=1г=1

+ =>™п (26)

)

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

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

1=1г=1/=1с)Е1 /=1г=1

+ Г\у^у (27)

1=1 г=Щг 0.5

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

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

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

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

(/=гЪ=Й- (28)

;=1q=1 ; iz

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

/=1 z=1 /=1д=-!17Х,гС'ХJt? х/г=с,г

Х/Ч'С/Я

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

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

Теорема 5. Существует такой г>0, что, если точка С = (cjz)Wn является решением системы дифференциальных уравнений (25), и выполняется условие |c/zj<e илиjciz -1|<£, то С является точкой локального

минимума функции энергии (27).

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

Коши для систем дифференциальных уравнений. Производная в

выражении (25) заменяется ее разностной аппроксимацией, и получается итерационная процедура:

Uiz{t + At) = Ufe(f)+ Aifl I^MOM, . (29)

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

» , J<e. (30)

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

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

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

Начальные точки Х° = (х ° )ие,п предлагается выбирать из окрестности центра единичного гиперкуба в соответствии с формулой:

х? = 0.5 + Дх(2Я-1), (г = V?; / = Л* е(0;0.5], где случайное число Я? е (0,1) генерируется датчиком псевдослучайных чисел в соответствии с равномерным законом распределения.

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

0.4

Д? =-

а• тах

/=1.....е

г=1.....л

У=1(?=1

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

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

0.4

0„ >

I

I п

I

/=1<М

г

>17=1

гд .«¡АЯКвСПИ^<0

И <Оа л =

_ 1в&А1еслиФЙЛ>0

[0, в противном случае [0, в противном случае

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

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

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

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

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

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

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

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

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

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

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

|х*+1-х*|<г2

выводы:

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

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

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

является план распределения заданий.

В работе рассматривается технология интерактивного взаимодействия

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4. Емалетдинова Л.Ю., Кайнов A.C. Нейросетевые модели оптимизации распределения заданий по нескольким компьютерам II Науч. тр. VIII Междунар. науч.-практ. конф. «Фундаментальные и прикладные проблемы

приборостроения, информатики и экономики», Московск. гос. академ. приборостроен. и информат, Москва, 2005. С. 71-75.

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

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

7. Зайнуллина Э.Ш., Кайнов A.C. Выбор активного нейрона при асинхронном функционировании сети Хопфилда II Тез. докл. Междунар. науч. конф.

. «XV Туполевские чтения», Т. Ill, Казань, 2007. С. 18-20.

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

9. Кайнов A.C. Нейросетевой метод решения задач дискретной оптимизации II Заочная электронная конференция «Фундаментальные и прикладные проблемы математики». Рос. акад. естествознан., 15-20 декабря 2008 г. httD://www.rae.ru/zk/?section=rubricator&op=article&id=4303.

10. Кайнов A.C. Решение задачи распределения заданий в мультипроцессорной системе методом Флетчера-Ривса II Заочная электронная конференция «Фундаментальные и прикладные проблемы математики». Рос. акад. естествознан., 15-20 декабря 2008 г. http://www.rae.ru/zk/?section=rubricator&op=article&id=4302.

Формат 60x84 1/16. Бумага офсетная. Печать офсетная. Печ.л. 1,25. Усл.печ.л. 1,16. Усл.кр.-отт. 1,16. Уч.-изд.л. 1,0. Тираж 100. Заказ М22.

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

ВВЕДЕНИЕ.

ГЛАВА 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. Руководство пользователя.

Выводы.

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

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

Постановка задачи распределения и упорядочения заданий в мультипроцессорной системе является хорошо известной в теории расписаний и рассматривается в работах Конвея Р.В., Максвелла B.JL, Миллера JI.B., Танаева B.C., Шкурбы В.В., Левина В.И. и других [26, 46, 52, 74, 78]. Многие задачи распределения являются NP-полными, что не позволяет эффективно решать их точными методами, поэтому необходимо разрабатывать алгоритмы на основе приближенных методов [51]. Появление искусственных нейронных сетей как математического инструментария распараллеливания вычислений делают актуальной задачу разработки нейросетевых математических моделей, методов и алгоритмов оптимального распределения заданий в мультипроцессорной системе.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Выход

Открыть и

Сохранить

Генерация

Решить задачу

Параметры задачи Начальное состояние ]

1 .и Ь И |5 |б |7 |з ¡9 |10 |п 112 |13 |14 115 \ 16 19 |ДО [

1 ¡1 о 1 |г о .1 1 1 1 о о о 1 о о [11 1 о кЛ»

1 о I о 1 !о

11 0 1 0

1 1 а о 0 1 о — 0

1 1 о

1 1

1 О о о а ¡1

И |1 [о

Рис. 4.9. Начальное состояние, заданное пользователем

Кроме того, имеется возможность использования начальных состояний, предварительно сохраненных в файле с расширением «*.р1ап». Для генерирования множества начальных состояний нужно нажать кнопку «Сгенерировать планы в файл» на вкладке «Начальные состояния» (рис. 4.8) в появившихся диалоговых окнах ввести число начальных состояний и имя файла (рис. 4.10). г- Введите имя файла

Имя файла:

Планы 420.р1ап|

ОК \ Сапсе!

Рис. 4.10. Ввод параметров генерации начальных состояний.

На вкладке «Алгоритмы решения» (рис. 4.11) задается алгоритм, который будет использоваться для решения задачи, а также вводятся параметры алгоритма.

Настройки

Коэффициенты задачи | Начальные состояния Алгоритмы решения |

Алгорктм решения задачи

Имитация отжига

Параметры алгоритма

Параметры имитации отжига

Козф. охлаждения 0,95

Коточество итераций при постоянной температуре

Пришил выбора следующего состояния (последовательно по 1 переменной

ОК

Отмена

Рис. 4.11. Форма «Настройки» - вкладка «Алгоритмы решения»

После настройки программы переходим к этапу решения задачи. Запуск алгоритма решения осуществляется из главной формы (рис. 4.2) нажатием на кнопки «Решить задачу» на панели инструментов или вызове пункта меню «Операции/Решить задачу». После завершения работы алгоритма открывается форма с результатами решения (рис. 4.12).

ДЙ Реэл/т >тзт решения: Имитация отжига

Информация о решении л-поеные характеристики Начальное значение цф 36303510 Конечное значение цф 2519975 Оценка решения ДОПУСТИМОЕ Число итераций 61600 Время решения, с. 1.997 1 1 дополнительная информация

Начальная температура = 2094669.59 Коневая тетература = 42472.67 Доля принятых переходов при начальной температуре = 55,88%

План раслреде мления к/р з 4 5 6 8 з ! 10 11 12 13 14 15; 1в 17 18 19 20 1

1 1 X 1 1

2 I 1 1 1 1 1 1 1 1

3 1 1 1

4 1 1 1 1

Рис. 4.12. Форма «Результат решения»

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

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

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

1. Berg J., Bioch J. Constrained Optimization with a Continuous Hopfield-Lagrange Model. 1993 September 6, Department of Computer Science Erasmus University Rotterdam.

2. Cerny V. Thermodynamical approach to the traveling Salesman Problem: an efficient simulation algorithm, J. Opt. Theory Appl., 45, 1985, P.41-51.

3. Gandhi Ritesh. Implementation of traveling salesman's problem using neural network / Final Project Report (Fall 2001) // ECE 559 Neural Networks, December 3, 2001. 9 p.

4. Hopfield J.J. Neural networks and physical systems with emergent collective computational abilities // Proc. Natl. Acad. Sci. USA. 1982. Vol. 79. №8. P.2554-2558.

5. Hopfield J.J. Neurons with graded responses have collective computational properties like those of two-state neurons, Proceedings of the National Academy of Sciences, USA, 1984. Vol. 81. № 10. P. 3088-3092.

6. Hopfield J. J. and Tank D. W. «Neural computation of decisions in optimization problems», Biol. Cybern., vol. 52, pp. 141—152, 1985.

7. Huang J., Chen J., Chen S., Wang J. A simple linear time approximation algorithm for multi-processor job scheduling on four processors // J Comb Optim 13:33-45 DOI 10.1007/sl0878-006-9011-y, 2007.

8. Kirkpatrick S., Gellat Jr C.D. and Vecchi P.M. Optimization by simulated annealing, Science 220, 1983, P. 671-680.

9. Krose Ben, Patrick van der Smagt. An introduction to neural networks. Eighth edition, November 1996. The University of Amsterdam.

10. Laarhoven P.J.M van. and Aarts E.H.L. Simulated Annealing: Theory and Applications, 2nd edition, D. Reidel, Boston, 1988, 187 pp.

11. Locatelli, M. Simulated annealing algorithms for continuous global optimization: convergence conditions // Journal of Optimization Theory and Applications, 104(1), 2000, P. 121-133.

12. Metropolis M., Rosenbluth A., Rosenblath M., Teller A. and Teller E. Equation of state calculations by fast computing machines, J. of Chem. Physics 21, 1953, P. 1087-1092.

13. Tank D. W. and Hopfield J. J. «Simple neural optimization networks: An A/D converter, signal decision circuit, and a linear programming circuit», IEEE Trans. Circuits Syst., vol. CAS-33, pp. 533-541, 1986.

14. Zhang Xiang Sun, Neural Networks in Optimization, Nonconvex optimization and its applications, Kluwer Academic Publishers, Norwell, 2000.

15. Zhu W.X. Penalty parameter for linearly constrained 0-1 (quadratic programming // Journal of optimization theory and applications: Vol. 116, No. 1, January 2003, P. 229-239.

16. Архангельский А.Я. Программирование в Delphi для Windows. Версии 2006, 2007, Turbo Delphi. M.: ООО «Бином-Пресс», 2007 г. -1248 c.: ил.

17. Васин А.А. Исследование операций: Учеб. пособ. для студ. вузов / А.А. Васин, П.С. Краснощеков, В.В. Морозов. М.: Изд. центр «Академия», 2008. - 464 с.

18. Введение в математическое моделирование: Учеб. пособ. /,В.Н. Ашихмин и др. Под ред. П.В. Трусова. М.: «Интермет Инжиниринг», 2000. - 336 с.

19. Вентцель Е.С. Исследование операций. Задачи, принципы, методология: Учеб. пособ. для вузов. 3-е изд., стереотип. — М.: Дрофа, 2004. - 208 е.: ил.

20. Вержбицкий В. М. Основы численных методов: Учебник для вузов. -2-е изд., перераб. -М.: Высш. шк., 2005. 840 е.: ил.

21. Винокуров А.В., Костенко В.А. Использование сетей Хопфилда для построения расписаний // Труды международной конференции «Параллельные вычисления и задачи управления» (РАСО'2001). Москва, 2-4 октября 2001 г. Институт проблем управления им. В. А.

22. Трапезникова РАН. М. Институт проблем управления им. В. А. Трапезникова РАН, 2001, с. 107-114.

23. Галкина В.А. Дискретная математика: комбинаторная оптимизация на графах. М.: Гелиос АРВ, 2003. - 232 е., ил.

24. Галушкин А.И. Нейрокомпьютеры и их применение на рубеже тысячелетий в Китае. В 2-х томах. Том 1. М.: Горячая линия -Телеком, 2004. - 367 е.: ил.

25. Гилл Ф., Мюррей У., Райт М. Практическая оптимизация: Пер. с англ. М.: Мир, 1985. - 509 е., ил.

26. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи: Пер. с англ. -М.: Мир, 1982.-416 е., ил.

27. Дегтярев Ю.И. Исследование операций: Учеб. для вузов по спец. АСУ. М.: Высш. шк., 1986. - 320 е.: ил.

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

29. Ефимов В.В. Нейроподобные сети в бортовых информационно-управляющих комплексах летательных аппаратов. Решение оптимизационных задач. СПб.: ВИКА им. А.Ф. Можайского, 1996. -113 с.

30. Зайдуллин С.С., Моисеев B.C. Элементы теории принятия решений: Учебное пособие. Для самостоятельной работы студентов по дисциплине «Теория принятия решений». Казань: Изд-во Казан, гос. техн. ун-та, 2002. 114 с.

31. Зайнуллина Э. Ш. Модели и методы решения задачи оптимальной маршрутизации данных в корпоративных сетях: дис. канд. физ.-мат. наук 05.13.18: защищена 29.02.08 / Зайнуллина Эльмира Шаукатовна; Казанск. гос. техн. ун-т. Казань, 2008. - 121 с.

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

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

34. Ильин В. А., Позняк Э. Г. Линейная алгебра: Учеб.: Для вузов. 6-е изд., стер. - М.: ФИЗМАТЛИТ, 2005. - 280 с. - (Курс высшей математики и математической физики). - ISBN 5-9221-0481-0.

35. Ильин В. А., Позняк Э. Г. Основы математического анализа: В 2-х ч. Часть I: Учеб.: Для вузов. 6-е изд. - М.: ФИЗМАТЛИТ, 2002. - 648 с. - (Курс высшей математики и математической физики). — ISBN 59221-0130-7 (Вып. 1).

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

37. Кайнов A.C. Непрерывная нейросетевая модель оптимизации распределения заданий по нескольким компьютерам // Тез. докл.

38. Междунар. науч. конф. «XV Туполевские чтения», Т. III, Казань, 2007. С. 24-26.

39. Каллан Р. Основные концепции нейронных сетей: Пер. с англ. М.: Изд. дом «Вильяме», 2003. - 288 е.: ил.

40. Карп Р. М. Сводимость комбинаторных проблем. — В кн.: Кибернетический сборник. Новая серия. Вып. 12. Сборник переводов. М.: Мир, 1975, с. 16-38.

41. Кластерные системы. PC Magazine/RE. www.pcmag.ru. (Главная / Архив / Upgrade2005 / Upgrade4/2005 / Кластерные системы), 01.09.2007.

42. Кнут Д. Искусство программирования, т.1. Основные алгоритмы. 3-е изд. - М.: Изд. дом «Вильяме», 2006. - 720 с.

43. Комашинский В.И., Смирнов Д.А. Нейронные сети и их применение в системах управления и связи. М.: Горячая линия — Телеком, 2003. — 94 с.

44. Конвей Р.В., Максвелл B.JL, Миллер JI.B. Теория расписаний. М.: Наука, 1975.

45. Корбут А. А., Финкельштейн Ю.Ю. Дискретное программирование / под ред. Д. Б. Юдина. М.: Наука, 1969. - 368 е.: ил.

46. Кормен Т.Х., Лейзерсон Ч.И., Ривест P.JI., Штайп К. Алгоритмы: построение и анализ, 2-е издание. Пер. с англ. М.: Изд. дом «Вильяме», 2007. - 1296 е.: ил. - Парал. Тит. англ.

47. Круглов В.В., Борисов В.В. Искусственные нейронные сети. Теория и практика. — 2-е изд., стереотип. — М.: Горячая линия-Телеком, 2002— 382с.: ил.

48. Левин В.И. Современное состояние исследований в области теории расписаний // Сб. ст. XVI Междунар. науч.-техн. конф. «Математические методы и информационные технологии в экономике, социологии и образовании: сборник статей». Пенза, 2005. С. 303-317.

49. Левин В.И. Бесконечнозначная логика в задачах кибернетики. — М.: Радио и связь, 1982. 176 е., ил.

50. Леоненков A.B. Решение задач оптимизации в среде MS Excel. — СПб.: БХВ-Петербург, 2005. 704 е.: ил.

51. Летова Т.А., Пантелеев A.B. Экстремум функций в примерах и задачах: Учебное пособие. -М.: Изд-во МАИ, 1998.-376 е.: ил.

52. Лесин В.В., Лисовец Ю.П. Основы методов оптимизации. — М.: Изд-во МАИ, 1995. -344 е.: ил.

53. Макконелл Дж. Основы современных алгоритмов. 2-ое дополнен, изд. -М.: Техносфера, 2004.-368 с.

54. Максютин С.А., Кайнов A.C. Olap-технологии в жилищно коммунальной отрасли региона // IV общерос. конф. с междунар. участ. «Новейшие технологические решения и оборудование», Рос.

55. Академ. Естеетвознан., Успехи современного естествознания, №6, 2006. С. 38-39.

56. Математические методы в исследовании операций: Сборник / Под ред. H.H. Моисеева, П.С. Краснощекова. М.: Изд-во Моск. ун-та,1981.- 192 с.

57. Математические модели и методы исследования операций: учебник для студентов вузов, обучающихся по специальности 080116 «Математические методы в экономике» и другим экономическим специальностям / под ред. В.А. Колемаева. -М.: ЮНИТИ-ДАНА, 2008. 592 с.

58. Меламед И.И. Нейронные сети и комбинаторная оптимизация. //АиТ. 1994 г, С. 3-40.

59. Михалевич B.C., Кукса А.И. Методы последовательной оптимизации в дискретных сетевых задачах оптимального распределения ресурсов. -М.: Наука. Гл. ред. физ.-мат. лит., 1983. 208 с.

60. Мэтыоз Дж.Г., Финк К.Д. Численные методы. Использование MATLAB, 3-е изд.: Пер. с англ. М.: Изд. дом. «Вильяме», 2001. -720 е.: ил.

61. Назаров A.B., Лоскутов А.И. Нейросетевые алгоритмы прогнозирования и оптимизации систем — СПб.: Наука и Техника, 2003.-384 е.: ил.

62. Нейрокомпьютеры. Кн. 3: Учеб. пособ. для вузов / Общ. ред. А.И. Галушкина. М.: ИПРЖР, 2000. - 528 е.: ил. (Нейрокомпьютеры и их применение).

63. Нейрокомпьютеры и их применение. Кн.6. Нейроматематика. / Под ред. А.И. Галушкина .-Москва:ИПРЖР, 2002. 448 с.

64. Пападимитриу X., Стайглиц К. Комбинаторная оптимизация: алгоритмы и сложность. М.: Мир, 1982. - 512 с.

65. Подиновский В.В. Многокритериальные задачи с упорядоченными по важности однородными критериями // АиТ, 1976 г., №11, С. 118-127.

66. Редько В.Г. Эволюция, нейронные сети, интеллект: Модели и концепции эволюционной кибернетики. Изд. 3-е. М.: КомКнига, 2005.-224 с.

67. Романенко В.К. Курс дифференциальных уравнений и вариационного исчисления -М.: Лаборатория Базовых Знаний, 2000 344 е.: ил.

68. Савяк В. iXBT: Эффективные кластерные решения. Апрель 2002. http://www.ixbt.com/cpu/clustenng.shtml.

69. Сигал И.Х., Иванова А.П. Введение в прикладное дискретное программирование: модели и вычислительные алгоритмы: Учеб. пособие. М.: ФИЗМАТЛИТ, 2002. - 240 с.

70. Струченков В.И. Методы оптимизации. Основы теории, задачи, обучающие компьютерные программы: Учебное пособие / В.И. Струченков. М.: Издательство «Экзамен», 2005. - 256 с. (Серия «Учебное пособие для вузов»)

71. Талызин В.А. Вычислительные алгоритмы решения задач нелинейной оптимизации. Учебное пособие. — Казань: Изд-во Казан, авиац. инст. им. А.Н. Туполева, 1978. 79 с.

72. Танаев B.C., Шкурба В.В. Введение в теорию расписаний. М.: Наука, 1975.

73. Taxa, Хемди А. Введение в исследование операций, 7-е издание.: Пер. с англ. М.: Издательский дом «Вильяме», 2005. - 912 е.: ил. - Парал. тит. англ.

74. Ten В.В., Герасимов Б.И. Экономические основы стабильности банковской системы России: Учеб. пособ. Тамбов: Изд-во Тамб. гос. техн. ун-та, 2001.-308 с.

75. Теория нейронных сетей. Кн. 1: Учеб. пособ. для вузов / Общ. ред. А.И. Галушкина. -М.: ИПРЖР, 2000.-416 е.: ил.

76. Теория расписаний и вычислительные машины / под ред. Э.Г. Коффмана. М.: Наука, 1984. - 334 с.

77. Турчак Л.И. Основы численных методов: Учеб. пособие. М.: Наука, Гл. ред. физ.-мат. лит., 1987. - 320 с.

78. Уоссермен Ф. «Нейрокомпьютерная техника» М.: Мир, 1992. - 240 с.

79. Фаронов В.В. Delphi 6. Учебный курс. М.: Издатель Молгачева C.B., 2001.-672 е., ил.

80. Хайкин С. Нейронные сети: полный курс, 2-е изд., испр.: Пер. с англ. М.: ООО «И. Д. Вильяме», 2006. - 1104 е.: ил. - Парал. Тит. англ.

81. Хопкрофт Дж., Мотовани Р., Ульман Дж. Введение в теорию автоматов, языков и вычислений, 2-ое изд.: Пер. с англ. — М.: Издательский дом «Вильяме»; 2002. 528 с.

82. Хохлюк В.И. Параллельные алгоритмы целочисленной оптимизации. -М.: Радио и связь, 1987. 224 е.: ил.

83. Осовский С. Нейронные сети для обработки информации / Пер. с польского И.Д. Рудинского. М.: Финансы и статистика, 2004. - 344 е.: ил.

84. Шкурба В. В. Задача трех станков М., Наука, 1976. - 96 е.: ил.

85. Шоломов JI.A. Логические методы исследования дискретных моделей выбора. -М.: Наука. Гл. ред. физ.-мат. лит., 1989. 288 с.