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

9

ю-4 ; 1 ^ у":;"

3904 ~ ■"'.; ~ ( о1

р"

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

Сись

Ш"

/( ' ' ' / и /) I

^ /

с

ТИТОВ ДМИТРИЙ ВЯЧЕСЛАВОВИЧ

МЕТОДЫ ПОВЫШЕНИЯ ЭФФЕКТИВНОСТИ АЛГОРИТМОВ РЕШЕНИЯ РАСПРЕДЕЛИТЕЛЬНЫХ МИНИМАКСНЫХ ЗАДАЧ В ОДНОРОДНЫХ СИСТЕМАХ

Специальность 05.13.01 - Системный анализ, управление и обработка информации

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

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

Ростов-на-Дону 2010 г.

Работа выполнена на кафедре «Программное обеспечение вычислительной техники и автоматизированных систем» ГОУ ВПО «Донской государственный технический университет».

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

Ведущая организация:

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

доктор технических наук, доцент Кобак Валерий Григорьевич

доктор технических наук, профессор Фатхи Владимир Ахатович

доктор технических наук, профессор Жак Сергей Вениаминович

ФГУ «Информационно-методический центр анализа»

Защита состоится «8» июня 2010 года в «10:00» на заседании диссертационного совета Д 212.058.04 Донского государственного технического университета по адресу:

344000, г. Ростов-на-Дону, пл. Гагарина, 1. ДГТУ, ауд. № 252.

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

Автореферат разослан «7» мая 2010 года.

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

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

кандидат технических наук, ///¿¿¿исгЛ^

доцент -^Г'-/ г Могилевская Н.С.

ГОСБтаИОТЕКА I 2010____1

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

Актуальность темы

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

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

Для получения оптимального решения однородной РЗ могут быть использованы точные методы решения. Однако, в силу её ИР-полноты, как с увеличением размерности распределительной задачи, так и при неблагоприятных распределениях ресурсных оценок заданий, получение оптимального решения за доступное время может стать недостижимым. В этой ситуации приходится ориентироваться на быстрые, но приближенные методы. Однако они не обеспечивают оптимальность результатов, и могут давать большую погрешность, достигающую 30%. Для практических задач такая потеря точности не всегда является приемлемой. Возникает необходимость & МёТОдаК, характеризующихся сочетанием противоречивых свойств: точностью решения, близкой к оптимальной, и быстродействием, т.е. полиномииальной зависимостью времени счета от размерности задачи. К таким методам относятся эво-люционно-генетические алгоритмы (ЭГА), которые являются на сегодняшний момент наиболее гибкими и эффективными из всех известных

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

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

Цели и основные задачи диссертационной работы

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

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

2. разработка и исследование методов повышения возможностей приближенных алгоритмов, в частности, ЭГА, при решении однородных РЗ теории расписаний, в том числе:

• методов повышения точностной эффективности ЭГА при ре-

шении РЗ высокой размерности,

• методов использования приближенных алгоритмов, в частно-

сти, ЭГА, для повышения ресурсной эффективности точного алгоритма Романовского (АР) при решении однородных РЗ теории расписаний;

3. разработка программного обеспечения (ПО) разработанных методов, способов и алгоритмов решения однородных РЗ, позволяющего проводить сравнительные вычислительные эксперименты и предварительную обработку накопленных статистических данных.

Существенные научные результаты диссертации и степень их новизны

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

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

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

3. метод бинарной декомпозиции решения РЗ высокой размерности с чётным количеством устройств обработки заданий, существенно повышающий точность решения приближёнными методами (в частности, методом ЭГА, при использовании которого среднее отклонение решения от минимальной оценки сокращается практически до 0), и сокращающий время решения для некоторых алгоритмов до 1,5 раз;

4. модифицированная стратегия формирования нового поколения ЭГА путём реализации бинарного турнирного отбора^между особями «родителей» и «потомков», которая отсутствует в классических прототипах, и позволяет, по данным статистически представительных исследований (около 9000 опытов), повысить точность находимого решения в 5-60 раз, в зависимости от размерности и структуры задачи;

5. структурная модификация алгоритма Романовского путём формирования первого приближения решения РЗ быстрыми приближенными методами, которая позволяет увеличить быстродействие в 3-4 раза (для двух устройств получено увеличение в несколько тысяч раз) в сравнении с классическим вариантом алгоритма.

Методы исследования

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

Для реализации экспериментальных исследований разработано ПО для ЭВМ «Система вычислительных исследований однородных распределительных задач «Optimal», проведено большое количество имитационных экспериментов, результаты которых использованы для получения статистически достоверных оценок результатов исследований. Для реализации ПО применялись концепции объектно-ориентированного программирования.

Достоверность результатов исследования

В основу подхода, обеспечивающего достоверность исследований, решений и выводов, положены корректное применение методов системного и математического анализа, статистическая представительность имитационного моделирования и автоматизированная обработка результатов экспериментов. Общий объем имитационно-численных экспериментов, проведенных при решении различных задач и вариациях параметров модели, составил около 106 опытов. Статистическая представительность данных и воспроизводимость свойств обеспечивалась не менее чем 100 параллельными опытами. Программный комплекс «Система вычислительных исследований однородных распределительных задач «Optimal», с помощью которого осуществлялось автоматизированное проведение имитационных экспериментов, прошёл официальную регистрацию в Федеральной службе по интеллектуальной собственности, патентам и товарным знакам (ФГУ ФИПС свидетельство № 2009616118 от 06.11.2009).

Практическая значимость диссертационной работы

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

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

1. существенное повышение точности решения для РЗ высокой размерности с чётным количеством устройств, в частности, при

б

использовании ЭГА (среднее отклонение решения от минимальной оценки сокращается для ЭГА практически .до 0);

2. повышение для ЭГА точности (до 60-кратного) решения однородных РЗ, в зависимости от. размерности и структуры задачи;

3. существенное улучшение быстродействия точных алгоритмов решения однородных РЗ (в основном, в 2-3 раза, а для некоторых частных задач - в несколько тысяч раз).

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

В рамках диссертационной работы разработано ПО «Система вычислительных исследований однородных распределительных задач «Optimal» (ФГУ ФЙПС свидетельство № 2009616П8 от 06.11.2009), с помощью которого осуществляется автоматизированное проведение имитационных экспериментов при выполнении лабораторных, курсовых и дипломных работ.

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

Тема диссертационной работы сформулирована в соответствии с тематическим планом ДГТУ, а также лежит в русле задач из списка «Приоритетные направления развития науки, технологий и техники и перечень критических технологий Российской Федерации», утвержденного Президентом Российской Федерации (№ Пр-842 и № Пр-843 от 21 мая 2006 г).

Апробация основных теоретических и практических

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

Материалы диссертационной работы докладывались и обсуждались на следующих международных научно-технических конференциях (МИК): «Математические методы в технике и .технологиях - ММТТ-20» (ЯГТУ, Ярославль, 28-31 мая 2007 г.), «Математические методы в технике и технологиях - ММТТ-21» (СГТУ, Саратов, 27-30 мая 2008 г.), «Математические методы в технике и технологиях - ММТТ-22» (ППИ, Псков, 25-30 мая 2009 г.); на VIII всероссийской научно-технической конференции «Проблемы информатики в образовании, „управлении, экономике и технике» (Пенза, 19-20 ноября 2008 г.); в рамках Конгрес-

са по интеллектуальным системам и информационным технологиям «АК-ГГ'ОЭ» на молодежной научно-технической конференции «Интеллектуальные системы - 2009» (Дивноморское, 3-10 сентября 2009 г.), в рамках международной научно-технической конференции «Математические методы в технике и технологиях - ММТТ-22» на международном научно-методическом симпозиуме «Современные проблемы многоуровневого образования» (ДГТУ, Ростов-на-Дону, 28 сентября - 4 октября 2009 г.). Кроме того, они приняты в программу МНК ММТТ-23 в г. Саратове и приняты к публикации в сборнике её трудов.

Промежуточные материалы диссертационных исследований докладывались на ежегодных научно-технических конференциях «Донского государственного технического университета» в 2007-2010 гг.

Публикации по теме диссертационной работы

Основные результаты диссертационной работы опубликованы в 14 работах, из которых 3 - самостоятельные публикации, а 11 опубликовано в соавторстве. При этом 3 статьи опубликованы в ведущих рецензируемых изданиях, входящих в список ВАК РФ, из которых 1 - самостоятельная публикация. Получено также свидетельство о государственной регистрации программы для ЭВМ.

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

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

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

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

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

Рассматривается математическая модель исследуемой задачи, согласно которой исследуемая однородная система обслуживания состоит из п несвязанных идентичных устройств р = {pj | / = 1, п}. На обслуживание этими устройствами поступает набор из т независимых параллельных работ Q = {c/j | j = 1, т), которым сопоставляется множество ресурсных оценок Т-{/, | j = im}. Для выполнения отдельной работы q/ на каком-либо из устройств р, системы обслуживания требуется одинаковое количество необходимого ресурса В каждый момент времени отдельное устройство обслуживает не более одной работы, и отсутствует передача работ на другое устройство.

Задача составления расписания сводится к разбиению исходного множества работ £> = {</,! у = 1,/"} на п непересекающихся подмно-

и

жеств, т.е. Q,: Vi, к е [1, и] --> 0/ П Qk = 0 и U Q, = Q, где п - число усг-

ы

ройств, m - число работ.

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

Для исследования возможностей такого совершенствования выделены наиболее перспективные методы решений однородных РЗ, В ка* чесгве Приближенного метода выбран ЭГА, показавший хорошие точностные результаты в предыдущих исследованиях/ проводимых в ДГТУ учениками школы проф. Нейдорфа P.A. в области теории расписаний. Результаты проведенного анализа показали необходимость исследования и доработки ЭГА, а также путей повышения их точностной эффективности при решении РЗ высокой размерности.

В качестве точного метода исследуется алгоритм Романовского. В связи с этим, традиционно ставится вопрос о повышении ресурсо-временных характеристик точных алгоритмов.

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

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

Схема предложена для увеличения эффективности решения РЗ высокой размерности. Согласно схеме исходное (чётное) множество устройств разбивается на два блока, которые условно считаются некоторыми «псевдоустройствами 1 очереди» (ПУ1) обработки заданий. Тогда начальному распределению на 2 ПУХ, состоящих из к{ = п / 2 реальных устройств каждое, подлежит множество 0 из т заданий. Результатом является 2 непересекающихся «подмножества 1 очереди» (ПМ1) заданий.. Далее каждое ПМ1 заданий и Й распределяются

на два ПУ2 (псевдоустройства 2 очереди, включающие по к2 = А, / 2 = и / 4 реальных устройств каждое). В результате получается

4 непересекающихся подмножества заданий , £>3, где

£?12и£?2 -Ол и Яъ и 04 =£?2/ образующих расписание для системы из 4 псевдоустройств 2 очереди. Подобные акты деления исходного и промежуточных множеств, рассматриваемых как псевдоустройства, с распределением на них результатов предыдущего разбиения заданий, • продолжается до получения на очередном Ам этапе деления нечётного значения к1. Тогда конечным этапом декомпозиционного решения РЗ

будет распределение / + 1 подмножеств где уе[1,и/2'], на к1 реальных устройств каждое.

Случай, когда к1 = 1 назван алгоритмом абсолютной бинарной декомпозиции, который применяется для задач, у которых количество " устройств п = 2'.

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

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

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

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

f = F -F■

°Hi * оп 1 min /

которая наиболее информативна и устойчива как оценка свойств приближённых алгоритмов решения РЗ.

Поскольку все РЗ решаются, в основном, на основе оптимизационного подхода, ТО можно называть также «оптимизационной».

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

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

Эффективность предложенного метода и построенных на его основе алгоритмов показана в работе на многочисленных примерах, в

которых проводились статистически представительные имитационные

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

_,__I Таблица 1

п т Усредненная точностная оценка Ресурсная оценка (95%), мс

ЭГА МВД ЭГА ЭГА МВД ЭГА

4 25 4,27 0,01 8,92 14,6

111 5,77 0,02 28,77 52,21

217 8 0,01 49,84 88,47

6 25 2,96 0Д1 9,58 14,88

111 5 0,05 37,29 48,59

217 7,17 0,03 .75,31 87,74

8 25 3,13 0,01 12,99 23,72

111 4,26 0,15 43,38 70,11

217 9,73 0 91,97 . 127,05

10 25 0,98 0,48 13,82 17,19

111 . 4,22 0,34 61,64 54,5

217 5,25 0,01 120,34 - 107,26

В таблице обобщены данные решения РЗ для следующих её базовых параметров: «е {4,6,8,10}, те {25,111,217} при диапазоне работ tj е [25,30]. В данном примере исследовалось решение РЗ методом ЭГА

с заданными параметрами вероятности оператора кроссовера Л:»«» =0'9 и мутации Ртш =0,1. При этом решалось по 100 задач с реализацией двух схем распределения: традиционной (ЭГА) и бинарно-декомпозиционной (МВД ЭГА). Проанализировав приведенные данные можно отметить, что во всех случаях МВД ЭГА является по сравнению с ЭГА более эффективным по оптимизационным показателям, хотя незначительно уступает ему по времени нахождения решения.

В третьей главе диссертации исследуется влияние на решение однородной РЗ структуры ЭГА. В качестве базового варианта ЭГА для исследования выбрана модель, предложенная аспирантом проф. Ней-дорфа P.A. Будиловским Д.М., защитившим кандидатскую диссертацию в 2007 году. Согласно модели выбранной базовой схемы ЭГА используется побитовое представление особи (хромосомы), в которой каждый ген представляет собой закодированный порядковый, номер устройства, на которое назначена работа, причем номер гена определяет номер выполняемой работы.

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

тельская особь. Модификация получила название «турнир с родителем». Для сравнения эффективности базового модифицированного ЭГА проведен вычислительный эксперимент, в ходе которого исследовалось влияние на эффективность рассмотренных алгоритмов количества особей, используемых в турнирном отборе для выбора особей, используемых в операторе кроссовера. Базовые параметры всех ЭГА приняты следующими: РСГ05Х- 1, Рт„= 0.41. При этом решалось по 100 задач

для и=2..4, при диапазоне работ е [25,30] (таблицы 2 и 3).

Таблица 2

л т Усредненная точностная оценка

ЭГА №1 ЭГА №2 ЭГА №3 ЭГА №4 ЭГА №5 ЭГА №6

25 2,73 2,34 0,02 0,25 0,81

2 27 2,43 2/77 2,19 0,01 0,16 0,51

29 2,57 2,21 2,41 0,01 0,07 0,17

25 5,93 6,17 5,6 0,49 1,92 2,72

3 27 0,86 0,83 0,73 0 0 0,04

29 3,86 3,76 3,65 0,61 0,87 1,44

25 4,58 4,69 4,33 0,49 1,51 2^08

4 27 1,95 1,87 1,9 0,3 0,61 0,81

29 5,67 5,4 5,34 0,9 1,99 . 2,34

Таблица 3

п /77 Ресурсная оценка (95%^ мс --------- —1

ЭГА №1 ЭГА №2 ЭГА №3 ЭГА №4 ЭГА №5 ЭГА №6

25 29,51 30,59 32,96 32,86 32,64 34,13

2 27 32,27 33,44 34,29 36,13 33,95 34,90

29 34,81 33,49 34,28 36,23 37,20 36,45

25 30,46 29,56 32,26 42,11 38,15 41,35

3 27 11 31,84 33,41 33,06 34,06 34,02

29 32,94 34,21 35,45 62,92 52,01 51,92

25 32,55 31,41 32,79 40,72 41,07 48,24

4 27 38,83 37,96 46,53 52,28 46,45

29 36,50 38,26 37,54 58,98 52,84 49,66

В таблице приняты следующие обозначения: ЭГА №1 - базовый ЭГА, ЭГА №2 - базовый ЭГА с бинарным турнирным отбором, ЭГА №3 -базовый ЭГА с турнирным отбором с 4 особями, ЭГА №4 - ЭГА с использованием турнира с родителем, ЭГА №5 - ЭГА с использованием турнира с родителем и бинарным турнирным отбором, ЭГА №б - ЭГА с использованием турнира с родителем и турнирным отбором с 4 особями.

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

В том же диапазоне работ и параметров ЭГА исследована зависимость точностной эффективности от количества устройств, показанная в таблице 4, где использованы обозначения: МКП - метод критического пути, ЭГА №1 - базовый ЭГА, ЭГА №2 - ЭГА, использующий турнир с родителем.

Таблица 4

п /77 Усредненная точностная оценка Ресурсная оценка (95%), мс

МКП ЭГА №1 ЭГА №2 МКП ЭГА №1 ЭГА №2

2 25 11,86 2,90 0,01 0,01 33,76 36,15

111 12,00 0,58 0,00 0,06 107,68 109,22

217 12,00 0,25 0,00 0,19 190,70 204,81

4 25 8,80 4,39 0,06 0,01 32,68 50,00

111 3,53 4,65 0,00 0,06 111,13 271,85

217 15,74 5,85 0,00 0,19 226,59 623,45

6 25 5,94 2,01 0,15 0,01 44,64 52,25

111 4,50 2,48 0,08 0,06 196,08 290,93

217 13,81 4,99 0,01 0,22 290,31 610,09

8 25 4,95 1,19 0,22 0,01 55,04 53,64

111 0,00 4,03 2,15 0,06 238,43 309,39

217 13,09 2,64 0,60 0,22 389,76 729,70

10 25 0,46. 0,27 0,32 0,01 66,66 55,03

111 10,64 2,81 0,39 0,06 210,17 320,15

217 0,23 2,00 МР . 0,20 487,99 727.42

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

Во-вторых, анализ её данных показывает, что при количестве устройств 8 и 10 в некоторых случаях наблюдается улучшение точностных показателей МКП даже по отношению к ЭГА. Поскольку ресурсная оценка МКП по сравнению с ЭГА очень мала, в диссертационной работе предложено использовать в ЭГА одну элитную особь, полученную с

помощью МКП. Это повышает её эффективность за счёт гарантированного получения точностной оценки ЭГА не хуже МКП.

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

Для выделения очередной ¿-задачи в классическом АР используется полусумма нижней и верхней границ. В работе показано, что можно использовать другие способы, которые дают повышение скорости нахождения решения: использовать линейный спуск с шагом Ъ, который равняется 1 или 2, т.е. когда от верхней границы отнимается Л. Показано, что для П-7..А, при диапазоне работ tJ е [25,30], использование линейного спуска с шагом 1 уменьшает время нахождения решения (таблица 5).

_____Таблица 5

п Ресурсная оценка (95%), мс

СМАР №1 СМАР №2 СМАР №3

2 15491 5005 11482

3 4523 3945 4763

4 697047 190591 388781

В таблице 5 введены обозначения: СМАР №1 - СМАР, использующий полусумму верхней и нижней границ, СМАР №2 - СМАР, использующий линейный спуск с шагом 1, СМАР №3 - СМАР, использующий линейный спуск с шагом 2 (СМАР - списочная модификация АР).

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

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

Для получения первого приближения в АР можно, например, использовать МКП (в соответствие со СМАР). Так, для п-2.А, при диапазоне работ €[25,30], который является наиболее трудным для АР,

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

Таблица 6

п т Ресу рсная оценка (95%) мс

АР СМАР Выигрыш в %

2 17 17225 14896 13,5

3 17 4814 4523 6,0

4 17 714013 697047 2,4

Для получения первого приближения в АР можно использовать и ЭГА (эволюционно-генетическая модификация АР - ЭГМАР). Так, например для /1=2..4/ при диапазоне работ /уе[25,30] для двух устройств выигрыш ресурсной оценки составил несколько тысяч раз, но, с ростом количества устройств, практически сравнялся с АР, использующим метод критического пути (таблица 7).

Таблица 7

п т Ресу эсная оценка (95%), мс

. СМАР ЭГМАР Выигрыш в %

2 41 115886 46 99,96

43 203931 48 99,98

3 41 657421 334037 49,19

4 19 26512 26453 0,22

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

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

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

В рамках диссертационной работы разработано ПО «Система вычислительных исследований однородных распределительных задач «Optimal», удовлетворяющее предъявленным требованиям. Данное ПО прошло регистрацию в ФГУ ФИПС. Получено свидетельство о государственной регистрации программы для ЭВМ № 2009616118 от 06.11.2009 г.

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

Заключение

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

2. Метод бинарной декомпозиции существенно повышает точность решения приближёнными методами РЗ высокой размерности с чётным количеством устройств обработки заданий, а в сочетании с методом ЭГА даёт очень большое улучшение точностной оценки при незначительном проигрыше в оценке ресурсной.

3. Модификация стратегии формирования нового поколения ЭГА путём реализации между особями «родителей» и «потомков» бинарного турнирного отбора, который отсутствует в классических прототипах, позволяет существенно повысить точность находимого алгоритмом решения, а в сочетании с методом бинарной декомпозиции эффективнее классического ЭГА.

4. Структурная модификация АР путём формирования начального распределения быстрыми приближенными методами и использования для выделения z-задач линейного спуска с шагом один позволяет улучшить ресурсную оценку алгоритма.

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

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

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

Публикации в ведущих рецензируемых изданиях, рекомендованных ВАК РФ

1. Титов Д.В. Сравнительный анализ эффективности вариантов турнирного отбора генетического алгоритма решения однородных распределительных задач / P.A. Нейдорф, В.Г. Кобак, Д.В. Титов // Вестник Дон. гос. тех. унив-та. - 2009. -Т.9. - №3(42). - С. 410-418.

2. Титов Д.В. Алгоритмический подход к уменьшению времени работы точного метода в однородных системах / В.Г. Кобак, Д.В. Титов // Вестник Дон. гос. тех. унив-та. - 2009. -Т.9. - Спец. выпуск. - С. 24-29.

3. Титов Д.В. Модификация генетического алгоритма распределения для четного количества однородных приборов / Д.В. Титов // Известия вузов. Сев.-Кавк. регион. Техн. науки. - 2010. - №1. - С. 3-6.

Публикации в других изданиях

4. • Титов Д.В. Анализ работы алгоритма Романовского с использованием разных подходов к формированию верхней и нижней границ / В.Г. Кобак, Д.В. Титов // Математические методы в технике и технологиях -ММТТ-20: сб., тр. XX Междунар. науч. конф., 28-31 мая / ЯГТУ. - Ярославль, 2007. - Т.2, секц. 2, 6. - С. 57-59.

5. Титов Д.В. Исследование работы алгоритма Романовского с использованием списочных алгоритмов при формировании верхней границы / В.Г. Кобак, Д.В. Титов // Системный анализ, управление и обработка информации: 1-й межвуз. сб. науч. сг. / ДГГУ; ТТИ ЮФУ. - Ростов н/Д, 2007. -С. 115-119.

6. Титов Д.В. Исследование принципа турнирного отбора генетического алгоритма для решения однородной минимаксной задачи / В.Г. Кобак, Д.В. Титов // Математические методы в технике и технологиях -

ММТТ-21: сб. тр. XXI Междунар. науч. конф., 27-30 мая / СГТУ. - Саратов, 2008. - Т.2, секц. 2, 6. - С. 12-13.

7. Методы получения расписаний для однородных систем обработки информации с использованием модификаций генетического алгоритма / Сост. В.Г. Кобак, Д.В. Титов // Методические указания и контрольные задания к практическим, лабораторным занятиям, курсовому проектированию / ДГТУ. - Ростов н/Д, 2008. - 11 с.

8. Титов Д.В. Анализ подходов к улучшению результатов работы генетического алгоритма при решении однородной минимаксной задачи / Д.В. Титов, В.Г. Кобак // Проблемы информатики в образовании, управлении, экономике и технике: сб. сг. VIII Всерос. науч.-техн. конф., 19-20 но-яб. - Пенза, 2008. - С. 76-78.

9. Титов Д.В. Использование генетического алгоритма для задания верхней границы алгоритма Романовского / Д.В. Титов // Математические методы в технике и технологиях - ММТТ-22: сб. тр. XXII Междунар. науч. конф., 25-30 мая / ППИ. - Псков, 2009. - Т. 10, секц. 11. - С. 123-124.

10. Титов Д.В. Анализ работы списочных и генетических алгоритмов в однородных системах обработки информации / Д.В. Титов, В.Г. Кобак // Математические методы в технике и технологиях - ММТТ-22: сб. тр. XXII Междунар. науч. конф., 25-30 мая / ППИ. - Псков, 2009. - Т.10, секц. И. -С. 124-126.

11. Титов Д.В. Алгоритмическое улучшение работы генетического алгоритма для четного количества процессоров / В.Г. Кобак, Д.В. Титов // Сб. науч.-метод. ст. вузов связи МО РФ по математическим и общим естественно-научным дисциплинам / НВВКУС. - Новочеркасск, 2009. - Вып. 11.

- С. 31-35.

12. Система вычислительных исследований однородных распределительных задач «Optimal»: свидетельство о государственной регистрации программы для ЭВМ № 2009616118 / Д.В. Титов, В.Г. Кобак, P.A. Нейдорф.

- № 2009614987; заявл. 15.09.2009; зарег. 06.11.2009.

13. Титов Д.В. Повышение эффективности генетического алгоритма для систем обработки заданий высокой размерности / Д.В. Титов // Труды Конгресса по интеллектуальным системам и информационным технологиям «AIS-IT'09». - M.: Физматлит, 2009. - Т.З. - С. 346-350.

14. Титов Д.В. Исследование способа формирования элитной особи генетического алгоритма для однородных систем / В.Г. Кобак, Д.В. Титов, В.В. Кобак // Математические методы в технике и технологиях - ММТТ-22: сб. тр. XXII Междунар. науч. конф. Междунар. науч. метод, симпоз. «Современные проблемы многоуровневого образования», 28 сент. - 4 oicr. / ДГТУ. - Ростов н/Д, 2009. - С. 160-162.

В работах [1,2,4-8,10-12,14] автору принадлежат наиболее существенные результаты, связанные с разработкой и экспериментальным подтверждением основных положений диссертационной работы.

В набор 04.05.2010 г. В печать 05.05.2010 г. Объем 1,0 усл.пл., 1,0 уч.-изд.л. Офсет. Формат 60x84/16. Бумага тип №3. Заказ № «2 /т. Тираж 90.

Издательский центр ДГТУ Адрес университета и полиграфического предприятия: 344000, г.Ростов-на-Дону, пл.Гагарина, 1.

{ ■

1°mH6 5 2

/ /Л

/' / / / / )

/ ' / /

^uuyu62037

2009062037