Автореферат (1091134), страница 3
Текст из файла (страница 3)
некоторого участкарасписания.Пусть D*– размер участка обрабатываемого расписания в ярусах, тогдаС* =показывает число участков в расписании, причем, если∉ , то= H – (C*– 1)*D*, тогда:размер последнего участка равен(21),где С* = с* , еслиNorm(, причём, если==при С* ≠ ⌈ ⌉, то= rmin, где rmin – минимальная оценка времени выполнения rmin≠ 0, rminmin[ω, ὠ] – диапазон допустимых значений rНаоснове[ω, ὠ], где.разработанныхмоделейпредложенамодификациягенетического алгоритма.В общем виде ГА представляет последовательность следующих шагов:1)формирование популяции;2)расчёт оценок для каждой особи (фитнес-функция);3) стохастический отбор наиболее приспособленных особей;4) скрещивание (кроссинговер);5) мутация.15Суть модификации генетического алгоритма состоит в следующем. Пустьмножество расписаний в популяции размером n – S={si: i=}, si = { : j=},i-е расписание, где m – количество задач в комплексе ИЗЗ, xj – ген-слот,кодирующий задачу с идентификатором j .F(si) – фитнес-функция, которая вычисляет время выполнения расписанияsi , f( ) процедура функции F(si), обрабатывающая слот.Пусть Ti время выполнения расписания si ,– время выполненияпроцедуры с идентификатором j расписания s i , а Tmin лучшая оценка для ужеобработанных расписаний, тогда= f( ).Тогда функцию F(si) можно записать, какF()… f () ->F (f ( ) f (а время выполнения расписания si , как Ti = F(f( ) f(Блок-схеманарисунке1представляет)f()… f()) ,) f(алгоритм)).выполнениямодифицированной фитнес - функции.Рис.
1. Блок-схема алгоритма фитнес-функции для обработки коротких расписаний16На начальном этапе фитнес-функция обрабатывает первую особь(расписание-хромосому), полученная оценка считается лучшей на текущиймомент и сохраняется в переменной Тmin .При вычислении Ti для следующихрасписаний популяции после обработки каждого слота производится сравнение сТmin. Если время слота больше Тmin расписанию назначается неточная оценка.Если слот является последним в расписании и Ti < Тmin , то Tmin = Ti.Второй алгоритм предназначен для обработки расписаний большой длины,для чего расписание разбивается на несколько участков.Каждый участок обрабатывается в своём цикле, и операция сравненияпроизводится на последней итерации, за счёт чего происходит сокращениеопераций сравнения.
Блок-схема алгоритма для отдельного участка расписанияпоказана на рисунке 2.Рис 2. Блок-схема алгоритма фитнес-функции для обработки длинных расписаний17Третья глава посвящена оценке работоспособности и эффективностиразработанных алгоритмов и применению разработанного теоретическогоаппарата.Дляпроведенияэкспериментапосравнениюэффективностимодифицированного алгоритма и классического был разработан стенд, которыйсостоит из персонального компьютера (ПК) AMDAthlon(tm) NeoProcessor MV-40,1,60 GHz, 2 Гб RAM, под управлением 32-разрядной Windows 7 и программы«Анализатор генетических алгоритмов».Результаты проведенного эксперимента представлены в таблице 2. Изданной таблицы видно, что при значительном сокращении времени работыфитнес-функции результаты поиска эффективных расписаний не снижаются.Таблица 2.
Результаты экспериментаКолвоитерацийСреднее времяработыфитнес-функцииклассическогоГА, мс101001000100000,352,441423СредняяСредняя оценкаСреднее времяоценкалучшей особиработылучшей особиГА сфитнес-функцииГА смодифицированмодифицированногоклассическойной фитнесГА, мсфитнесфункцией,*функцией, *0,0997880,688857,25848460,58484*оценки измеряются в условных квантах времениВ исследуемых алгоритмах неэффективным расписаниям назначаласьминимальная ненулевая оценка, что увеличивает вероятность отбора данныхрасписаний и сохраняет стохастичность ГА.Проведенный эксперимент доказывает, что при назначении расписаниямнеточных оценок, время работы алгоритма фитнес-функции сокращается на 79 %,что не влияет на результаты поиска эффективных расписаний.Недостаток разработанного алгоритма заключается в большей склонностик ранней конвергенции (рисунок 3).
Данный недостаток может устранятьсяпопеременным включением разработанного и классического алгоритмов. Также18следует отметить, что прирост в скорости алгоритма даёт возможность большевремени выделить для мутации и кроссинговера.Рис. 3. График сходимости алгоритмов при 10 (а), 100(б) и 1000(в) итерацияхВо второй части третьей главы проведена оценка работоспособностиразработанных алгоритмов на примере распараллеливания задачи умноженияматриц большой размерности в гетерогенных РСОД, а также представленаметодика его применения для класса ИЗЗ.Цель эксперимента, описанного во второй части главы, заключалась всравненииэффективностиклассическогоГА,модифицированногоГА,смешанного ГА и алгоритма на основе обыкновенного блочного метода в РСОД соднороднойигетерогеннойконфигурациейнапримерепараллельноговыполнения операции умножения матриц.В процессе проведения эксперимента в программу вводились исходныеданные с различными конфигурациями вычислительной сети комплекса ИЗЗ,представляющего операцию умножения двух квадратных матриц размерностью10000x10000.
За атомарную операцию принималась операция умножения строкии столбца размерностью 10 элементов.В первой части эксперимента, результаты которой представлены в таблице3, проводилось сравнение вышеописанных алгоритмов в однородной РСОД.Из таблицы 3 видно, что алгоритм с блочным методом в однороднойсистеме явно преобладает над алгоритмами, синтезирующими расписания.19Таблица 3. Результаты эксперимента для однородной РСОДНазвание методаВремя поискарасписанияКлассический ГАМодифицированный ГАСмешанный ГАБлочный метод100 мкс100 мкс100 мкс0Классический ГАМодифицированный ГАСмешанный ГАБлочный метод50 мкс50 мкс50 мкс0Среднее время выполнения операцииРазмерность системы100 узлов 1000 узлов 2500 узлов1,4 мc70 мкc59 мкс1,1 мс68 мкс61 мкс0,94 мс64 мкс58 мкс0,78 мс59 мкс46 мкс1,6 мc1,2 мс1,1 мс0,78 мс90 мкc69 мкс67 мкс59 мкс68 мкс63мкс61 мкс46 мксВо второй части эксперимента производилось сравнение в гетерогеннойРСОД (таблица 4).Таблица 4.
Результаты эксперимента для гетерогенной РСОДНазвание методаВремя поискарасписанияКлассический ГАМодифицированный ГАСмешанный ГАБлочный метод100 мкс100 мкс100 мкс0Классический ГАМодифицированный ГАСмешанный ГАБлочный метод50 мкс50 мкс50 мкс0Среднее время выполнения операцииРазмерность системы100 узлов 1000 узлов 2500 узлов1,1 мc92 мкc83 мкс0,94 мс80 мкс73 мкс0,82 мс67 мкс62 мкс2,4 мс354 мкс287 мкс1,2 мc0,98 мс0,87 мс2,4 мс96 мкc87 мкс69 мкс354 мкс85 мкс77 мкс63 мкс287 мксИз второй части эксперимента видно, что несмотря на временные затраты,связанные с поиском оптимального расписания, эффективность алгоритмов,применяющихГА,вышечемублочного,чтосвязаносбольшойнеравномерностью вычислительных ресурсов гетерогенной РСОД. Из чегоследует, что при использовании алгоритмов с построением расписаний вгетерогенных РСОД время вычислительного процесса сокращается.Заключительная часть третьей главы посвящена описанию примененияпредложенных алгоритмов при разработке стенда для отработки программногообеспечения системы аварийной защиты двигателя.20Платформонезависимое программное обеспечение системы аварийнойзащиты (ППОСАЗ) представляет собой набор математических функций, на основекоторых разрабатывается рабочая программа системы аварийной защитыдвигателя.
Применение набора функций данного инструментального средствасокращает сложность и время разработки ПО для систем аварийной защиты (САЗ)двигателей.Аппаратура САЗ состоит из модулей микро-ПК, к которым через аналогоцифровые преобразователи (АЦП) поступают сигналы от датчиков различноготипа. Микро-ПК производит обработку полученных данных и в соответствии салгоритмом управления выдаёт сигналы на исполняющие механизмы (ИМ).Количество датчиков и микро-ПК, а также их технические характеристикимогут изменяться в зависимости от версии САЗ и от типа двигателя.Впроцессеразработкиплатформонезависимогопрограммногообеспечения САЗ необходимо его тестирование на стенде, моделирующем работусистем комплекса бортового оборудования (КБО) в реальном времени. Стендпредставляет РСОД, организованную на базе локальной вычислительной сети.ВсеузлывРСОДработаютподуправлениемОСРВQNX6.5.0.Коммуникационная среда РСОД организована на основе родного протокола QNX –QNET.При работе в режиме моделирования входные параметры поступают всистему от центральных ПК.
Для своевременной выдачи управляющих сигналоввозникает необходимость повышения эффективности вычислительного процессана 10 %. В связи с чем в систему включается планировщик, работающий наоснове разработанных алгоритмов, который равномерно распределяет нагрузкумежду вычислительными узлами.Применение разработанного модифицированного ГА сократило времяреакции системы и увеличило производительность на 13%, что обеспечилонеобходимую скорость вычислительного процесса.На рисунке 5 представлена общая методика применения разработанноготеоретического аппарата.21Рис. 5.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
