Содержание к диссертации
Введение
1. Минимаксные неоднородные задачи и методы решения 13
1.1. Постановка задачи и математическая модель минимаксной неоднородной задачи 13
1.2. Обзор и анализ существующих критериев решения минимаксных неоднородных задач 21
1.3. Обзор и анализ существующих методов решения минимаксных задач 25
1.4. Алгоритмы балансировки Citrix NetScaler 36
1.5. Выводы к главе 1 39
2. Разработка и исследование алгоритмов опти мизациии минимаксных задач 41
2.1 Разработка и исследование модифицированного алгоритма
Плотникова –Зверева для неоднородных минимаксных задач 41
2.2. Разработка и исследование модифицированного алгоритма Холланда для неоднородных минимаксных задач 54
2.3. Разработка и исследование алгоритма модифицированного Алексеева для неоднородных минимаксных задач 67
2.4. Исследование алгоритма Крона для однородных минимаксных задач 76
2.5. Выводы к главе 2 77
3. Разработка и исследование модификации алгоритма крона для неоднородных мини максных задач
3.1. Разработка модифицированного алгоритма Крона для неоднородных минимаксных задач 70
3.2. Исследование алгоритма Крона модифицированного минимальной матрицей 84
3.3. Исследование алгоритма Крона модифицированного первоначальными матрицами «численный выбор» 87
3.4. Исследование алгоритма Крона модифицированного первоначальными матрицами элементный выбор 96
3.5. Результаты вычислительного эксперимента 100
3.6. Выводы к главе 3 106
4. Экспериментальная проверка и моделирование решения неоднородных распределительных задач
4.1. Функциональная структура программного обеспечения 108
4.2. Концептуальная схема функционирования программного обеспечения 111
4.3. Концептуальная модель системы моделирования и решения неоднородных минимаксных задач 114
4.4. Выводы к главе 4 135
Заключение 136
Библиографический список
- Обзор и анализ существующих методов решения минимаксных задач
- Разработка и исследование модифицированного алгоритма Холланда для неоднородных минимаксных задач
- Исследование алгоритма Крона модифицированного первоначальными матрицами «численный выбор»
- Концептуальная модель системы моделирования и решения неоднородных минимаксных задач
Введение к работе
Актуальность темы исследований. Субоптимизация решения минимаксных неоднородных задач является актуальной задачей и рассматривается во многих работах. Задачи теории расписания – это задача, решение которой обеспечит эффективное функционирование множества процессов в различных сферах деятельности человека.
Задачи такого типа относятся к NP-полным задачам. Для их решения используются алгоритмы точного решения, отличающиеся высокой сложностью и длительностью решения. В связи с NP-полнотой минимаксной неоднородной задачи, точные алгоритмы решения имеют экспоненциальную сложность. В связи с этим практические задачи инициировали разработку алгоритмов вычисления квазиоптимальных решений за полиномиальное время.
Существует много сфер деятельности, для которых необходимо решение минимаксных задач. Примером является распараллеливание задач в электронно-вычислительной сети. Все большие корпоративные решения основываются на кластерах серверов, каждый из которых содержит десятки процессоров. При этом производительность серверов в кластере чаще всего неоднородна. В случае правильного распределения задач можно добиться сбалансированной нагрузки. Развитие облачных технологий ускоряет данный процесс.
Применение приближенных алгоритмов, работающих за известное и гарантированно определённое время, может существенно повысить возможность применения таких алгоритмов в задачах балансировки вычислительной нагрузки. Также необходимо понимать, что задача минимаксного распределения не может занимать время большее или сопоставимое с решением поставленных задач.
Алгоритмы построения квазиоптимальных расписаний распределенных вычислительных систем, обеспечивающих субоптимальное время выполнения параллельных задач при известном числе процессоров или минимальное количество требуемых устройств при заданном времени выполнения параллельных задач, разработаны только для простых функций и моделей.
Как уже отмечалось, наибольшую ценность имеет возможность обрабатывать большое число распределяемых частей, причем за «реальное» время. Мониторинг показывает, что оптимизация выполнения большинства регулярно возникающих задач повысит эффективность во многих сферах жизнедеятельности человека. В век активного роста информатизации, кибернетизации, ускорения и распараллеливания задач оптимизация решения задач будет иметь ключевое значение.
Значительный вклад в область решения минимаксных задач как в России, так и за рубежом, внесли такие исследователи, как Б.А. Головкин, В.В. Липаев, Э.А. Трахтенгерц, А.Б. Барский, О.Г. Алексеев, В.М. Глушков, Г.Е. Цейтлин, Э.В. Евреинов, В.Г. Хорошевский, Ю.Г. Косарев, В.Е. Котов, Ю.Г. Косарев, Н.Н. Миренков, В.М. Курейчик, В.В. Липаев, Я.А. Хетагуров, С.Д. Пашкеев, Д.А. Поспелов, В.С. Танаев, А. Кофман, В. Феллер, Е. Кофман, М. Гери, Д., Джонсон М. Гонсалес, Р. Грэхам и многие другие.
Цель работы заключается, в повышение эффективности решения минимаксных неоднородных задач на основе модифицированных разработанных алгоритмов.
Для достижения поставленной цели в работе решены следующие основные задачи:
-
расширение функциональных возможностей алгоритма Плотникова и Зверева квадратичным критерием, кубическим критерием. Адаптация критериев «по максимальной матрице», «по минимальной матрице» и «средний элемент по строке» для использования с указанным алгоритмом;
-
расширение функциональных возможностей алгоритма Холланда относительно предметной области с применением квадратичного и кубического критериев оценки. Адаптация алгоритмов решения минимаксной задачи для вычисления первоначальных «особей»;
-
модификация алгоритма Крона адаптацией его для неоднородных минимаксных задач с применением квадратичного и кубического критерия;
-
исследование и разработка оценочных критериев и параметров, влияющих на оптимальность построения решения для минимаксной задачи. Оценка времени действия и влияния на исследованные алгоритмы решения неоднородных минимаксных задач;
-
разработка специализированного программного обеспечения для сравнения алгоритмов оптимизации неоднородных минимаксных задач и критериев вычисления оптимальности распределения.
Методы исследования. Для решения поставленных задач автором использовались методы математического моделирования, теории расписаний, исследования операций оптимизации, математической статистики, теории планирования вычислительных экспериментов, методы системного анализа, методы и алгоритмы оценки эффективности и качества. Научная новизна работы состоит в следующем:
1. математическая модель, описывающая несовпадения в ре-
шении по «минимаксному» и «квадратичному» критерию для системы из двух исполнителей при использовании алгоритма Плотникова – Зверева.
Расширение функционала, отличающегося применением квадратичного критерия, позволяющие улучшить результат решения на 5-7% от эталонного алгоритма (стр. 43-44,47-48) (Пункт 3 паспорта специальности 05.13.01);
-
алгоритм оптимизации минимаксных неоднородных задач составления расписаний на основе алгоритма Крона для однородных задач, впервые адаптированный к неоднородным задачам. Отличающийся от известных тем, что модифицирован для решения неоднородных минимаксных задач, позволяющий за меньшее время (10-15%) обеспечить распределение задач в многопроцессорной системе для их решения (стр.74-98) (Пункт 4 паспорта специальности 05.13.01);
-
модификация алгоритма Крона, отличающаяся использованием модифицированного алгоритма Крона, позволяющая улучшить результаты относительно генетических алгоритмов Холланда и Голдберга и первого приближения алгоритма Алексеева в качестве распределения задач по минимаксному и квадратичному критерию на 6-10% (стр. 99-101) (Пункт 4 паспорта специальности 05.13.01);
-
архитектура программного комплекса решения минимаксных неоднородных задач, отличающийся от аналогов использованием разработанных подходов, критериев и алгоритмов, ориентированных на получение субоптимального расписания за полиномиальное время (стр. 106-111) (Пункт 5 паспорта специальности 05.13.01).
Практическая ценность работы определяется применимостью результатов при решении минимаксных неоднородных задач:
– разработан комплекс программных средств, на основе разработанных и исследованных, позволяющих проводить сравнительный анализ предложенных алгоритмов;
– разработан программный модуль, реализующий модифицированный алгоритм Крона для неоднородных минимаксных задач, обеспечивающий улучшение точности решения в сравнении с первым приближением алгоритма Алексеева;
– разработаны библиотеки модулей, позволяющие реализовывать исследованные алгоритмы сторонним программным обеспечением.
Реализация и внедрения результатов работы. Результаты диссертационной работы использовались в НИОКР, выполненных в Институте компьютерных технологий и информационной безопасности Южного Федерального университета, направленных на решения задач оптимизации. Материалы диссертации внедрены в учебный процесс кафедры систем автоматизированного проектирования Южного федерального университета.
Результаты работы внедрены:
– на предприятии ООО «СофтДон»;
– на предприятии ООО «Информационные системы».
Апробация. Основные результаты докладывались и обсуждались на следующих семинарах и конференциях: I международный семинар студентов, аспирантов и ученых «Системный анализ, управление, обработка информации», Ростов-на-Дону, ДГТУ,2010;IV международная научно-практическая конференция «Перспективы развития информационных технологий», Новосибирск, 2011; Межвузовская научно-техническая конференция «Перспективы развития средств и комплексов связи», Новочеркасск, 2011; Международная научная конференция «Математические методы в технике и технологиях ММТТ-24», Саратов, 2011; II международный научный семинар «Системный анализ, управление и обработка информации», Ростов-на-Дону, ДГТУ, 2011; Международный молодежный научный форум «Ломоносов-2012», Москва, 2012; Международная научная конференция «Математические методы в технике и технологиях ММТТ-25», Саратов, 2012; III международный семинар студентов, аспирантов и ученых «Системный анализ, управление, обработка информации», Ростов-на-Дону, ДГТУ, 2012; Международная научная конференция «Математические методы в технике и технологиях ММТТ-26», Саратов, 2013.
Получено свидетельство о государственной регистрации программы для ЭВМ 2012611611 Российская федерация №2011619668; заявление от 14.12.2012; зарегистрировано 13.02.2012.
Публикации. По теме диссертационной работы опубликовано 12 печатных работ, из них три статьи из перечня рекомендуемых ВАК РФ научных журналов и изданий; сделано девять докладов на Всероссийских и Международных научно-технических конференциях. Получено 1 свидетельство о государственной регистрации программы для ЭВМ
Структура и объем работы. Диссертационная работа состоит из введения, четырех разделов, заключения и приложений. Диссертация содержит 147 страниц машинописного текста, включая введение, четыре раздела, заключение, список литературы из 105-ти наименований, 75-рисунков, 23 - таблицы.
Обзор и анализ существующих методов решения минимаксных задач
История возникновения и применения. Термин «исследование операций» (operations research) широко используется в различных сферах деятельности. В Англии наиболее используемым считается термин «операционные исследования» (operational research). Канадцы чаще употребляют выражение «наука об управлении», популярность которого связана с работой известной мировой организации – Института научного управления[1-7].
Можно с высоким уровнем точности установить исследование операций как научный подход для решения вопросов восстановления естественного порядка для систем. Для решения конкретной задачи использования подходов исследования операций предполагает: – разработка экономических, статистических или математических моделей для задач выбора решения и управления в не регламентированных обстоятельствах или в условиях недостаточности входной информации [8-10, 12]; – изучение взаимного влияния, определяющих возможное развитие событий в зависимости от принятых решений, а также определение критериев оценки, позволяющих определить эффективность данного решения относительно того или иного варианта действий.
В некоторых случаях предполагают, что предметом исследования операций являются регулярно появляющиеся задачи управления развитием любого предприятия. Иногда, считают, что рассматриваются управленческие задачи, возникающие в процессе работы над определенными регулярными, повторяемыми операциями [12, 14]. Подходы исследования операций, определенно, являются эффективными при решении ряда задач управления. Задачи, связанные с календарным планированием работы и распределением материальных ценностей, использованием и модернизацией оборудования, а также вопросы набора штатов в организациях коммунального и бытового обслуживания, могут быть отнесены к задачам такого типа[15-19].
В некоторых случаях методы исследования операций применяются для решения другого типа управленческих задач, обладающих только косвенным отношением к регулярным операциям. Задачи такого типа, в большинстве случаев, связаны с построением планов. К таким задачам, относятся вопросы выбора разновидности выпускаемой продукции, внедрению длительных и ресурсоемких проектов модернизации линий производства, планирования размещения базовых станций (шлюзов) в системе интернет и телеком предприятий, а также задачи освоения новых технологий передачи данных или финансовой деятельности путем объединения с другими компаниями или путем поглощения крайних [20].
Термин «Исследование операции» не должен вызывать впечатления «созерцательности», того метода рассмотрения, задачи который выбран для решения задачи. Так же определение «операция» не полностью соответствует, тому кругу задач, которые используют эти методы. В реальности чаще всего происходит обратный эффект.
Использование подходов исследования операций, в последние несколько лет, регулярно подтверждают высокое качество при решении прикладных задач управления и большие возможности этих подходов. Фундаментальные теоретические разработки продолжаются в области исследования операций. Серьезные теоретические и практические достижения в сфере исследования операций достаточно быстро реализуются и используются для практического применения, в отличии от других наук [22]. Задача выбора решения (или принятие плана последовательности действий) является основной для всех операционных исследований. Исследование ключевых решений предопределяет разбиение определенной составной задачи на более мелкие и простые задачи, которые проще поддаются интуитивному и логическому анализу [22-23].
Ключевой проблемой современной теории управления является оптимизация. Анализ данного вопроса показывает необходимость в разработке и практического применения алгоритмов и критериев оптимизации, реализованных для использования на ЭВМ. Задачи дискретного программирования являются ключевыми задачами среди прикладных задач оптимизации [25].
Использование дискретных моделей и методов исследования является отличительной чертой современного этапа развития науки. В физике, химии, биологии и других научных направлениях идеи дискретности позволили наиболее полно описать различные явления и процессы. В последние годы идея дискретности находит широкое применение и в технической кибернетике [25].
Современные устройства компьютеров основаны на дискретных принципах, на реализации простейших логических операций. Применение данных устройств потребовало разработок в новых областях использования математических методов, привело к быстрому развитию дискретных методов оптимизации [26].
Большое теоретическое значение и практическое применение в различных сферах целенаправленной деятельности общества, получили модели, построенные на основе классических минимаксных вопросов теории расписания [26].
С решением минимаксных задач в той или иной степени сталкиваются различные категории лиц, как экономисты-плановики, инженеры производственники, финансисты или руководители проектов и команды разработчиков. Для того, чтобы определенный подход классифицировать как минимаксный, он должен обладать, следующими свойствами: – результат анализа должен иметь полностью определенное и непосредственное отношение к принятию решения. Ориентация на выбор способа или последовательности действия; – анализ отличающихся вариантов действий должен основываться на количественных показателях, позволяющих однозначно идентифицировать полезность ожидаемого результата для изучаемой компании. Количественные показатели для финансовых служб предполагают возможность использование измеримых величин, как доходы, расходы, стоимость оборудования, наличные денежные средства и трудозатраты; – доверие к математической модели. Процедуры обращения с упомянутыми выше параметрами должны быть определены настолько точно, чтобы любой специалист в области системного анализа смог их трактовать однозначно. Другими словами, опираясь на одни и те же данные, различные специалисты-аналитики должны получать одинаковые результаты; – Условие необходимости использования ЭВМ, определяется большими объемами данных, сложностью используемых математических моделей, объемом вычислительных процедур, поддерживающих основные системы контроля и управления [24-35].
Разработка и исследование модифицированного алгоритма Холланда для неоднородных минимаксных задач
Алгоритм Крона впервые был разработан и применен для однородных минимаксных задач, где показал хорошие результаты. В данной работе преобразуем алгоритм для работы с неоднородными минимаксными задачами. Предлагаем адаптированный алгоритм Крона для минимаксных задач: 1) генерируем первоначальное решение; 2) вычисляем ti max = j.p. ; 3) находим столбец mm = штатах), ипах = тах(итах); 4) в максимальном столбце берем произвольный элемент; 5) переносим задание с максимального столбца на минимальный столбец и считаем Ттах для обоих столбцов. ЕслиТтах тах(Шах), где і є {mm, max}, то обновляем решение и повторяем пункты 1-5; 6) если Ттах max (Шах),то выбираем следующий элемент из максимального столбца и переходим к шагу 4; 7) находим столбец min = min(Umax), max = тах-тах); 8) в максимальном столбце берем произвольный элемент; 9) производим замену произвольного элемента максимального столбца на минимальный элемент минимального столбца. Если Tmax max(timax), где / є {min, max}, то обновляем решение и повторяем пункты 7-9; 10) полученное решение - результат алгоритма; Данный алгоритм применяется для неоднородной вычислительной системы, т.е. когда время выполнения одного и того же задания может отличаться на разных вычислительных устройствах. Алгоритм отличается наибольшим по сравнению с точными алгоритмами быстродействием, простотой и позволяет получить приемлемые по точности решения [103,105].
Пример решения. Приведем пример решения данным алгоритмом. Исходная матрица (рис.3.1): – вычислим сумму выбранных элементов столбцов, получаем (7;11;15); – выбираем первый и третий столбец; – меняем выбор для восьмой строки с третьего на первый столбец; – проверяем Tmax для обоих столбцов, 13 и 9. Фиксируем решение (рис. 3.3); 2 [4] 8
Никакие дальнейшие перестановки не дадут улучшения решения. В результате получили следующее распределение: N1 ={1;4},7V2 ={3;7;8},N3 ={2;5;6}. Таким образом, правильное распределение было получено за 10 шагов. Конечно, в представлении работы данного алгоритма случайный выбор элемента был не совсем случаен, но даже если бы взяли элементы последовательно, то получили бы исходный результат. Данный алгоритм был представлен, когда в качестве первоначального решения берется случайным образом выбранный набор [104].
В табл. 3.1 представлено сравнение решения по алгоритму Крона со случайной первоначальной матрицей по квадратичному и минимаксному критерию. Из предыдущего анализа известно, что квадратичный критерий дает очень хороший результат. Кубический критерий не рассматривается, так как его результаты сопоставимы или хуже результатов квадратичного критерия.
Для анализа выбран интервал задач из диапазона [15;25]. Количество экспериментов на каждом наборе параметров – 100 повторений. Результат получаем как среднее арифметическое по всем экспериментам. Из приведенной таблицы хорошо видно, что результат по квадратичному критерию заметно лучше. Только смена критерия дала прирост в качестве ре-83 шения минимум 10%. В дальнейшем будем считать квадратичный критерий для случайно сгенерированной стартовой матрицы эталонным, поскольку он наиболее эффективный.
Минимаксный критерий. Предложено модифицировать первоначально решение так, чтобы исключить элементы, которые могут внести максимальное отклонение от оптимального решения. То есть для первоначального решения выбирать только минимальную нагрузку для каждого задания. Пример такого выбора на рис. 3.10.
Как видно из приведенной матрицы, для нашего алгоритма это не очень удачный пример, так как данная матрица уже отвечает всем требованиям алгоритма и ни один элемент не будет перемещен. Но даже в таком виде получаем сразу близкое к оптимальному решение Л ={1},N2 = {3;4;8},7V3 ={2;5;6;7}, значение минимаксного критерия равно 6.
Квадратичный критерий. Еще одним способом модификации является применение квадратичного критерия. Возьмем матрицу, представленную на рис. 3.11. Посчитаем квадратичный критерий для данной матрицы. При моди фикации квадратичным критерием, считается критерий для всей матрицы. В связи с этим нет необходимости дополнительной проверки по строкам. Критерием улучшения является уменьшение квадратичного критерия.
И так далее, в итоге получим результат, аналогичный минимаксному критерию. В случае применения минимальной матрицы, матрица решения не будет изменена, так как изначально никакое одинарное изменение в столбцах матрицы не приводит к улучшению квадратичного критерия. Для сравнения посчита-85 ем квадратичный критерий для минимальной матрицы и оптимального решения. Toptimai = (2 + 2)2 + (1 + 2 + 2)2 + (1 + 2 + 2)2 = 54; Tmin = (2)2 + (1 + 1 + 2)2 + (1 + 2 + 2 + I)2 = 56.
Как видно из результатов, квадратичный критерий минимальной матрицы также не очень сильно отличается от оптимального решения. В связи с тем, что математически доказать эффективность применения минимальной матрицы невозможно, проведем эксперимент по сравнению данной модификации с эталонным алгоритмом Крона со случайной матрицей по квадратичному критерию. Для минимальной матрицы будем брать и квадратичный, и минимаксный критерий [185].
Результаты эксперимента представлены в табл. 3.2. Диапазон распределения по задачам из интервала [15; 25]. Для статистически точного результата для каждого набора параметров проводилось 100 экспериментов.
В случае применения минимальной матрицы, видим минимум 3% улучшения по сравнению с квадратичным критерием и случайной первоначальной матрицей. При размерности, где количество задач меньше, чем исполнителей, умноженное на 25, при использовании минимальной матрицы для алгоритма Крона, лучший результат дает применение минимаксного критерия. На больших размерностях квадратичный критерий показывает лучшие результаты. Для сравнения в следующих экспериментах оставляем оба варианта критериев.
Максимальная матрица. В качестве модификации был выбран способ «максимальная матрица». Данный алгоритм заключается в следующем: В каждой строке, выбирается элемент с максимальным значением загрузки для этой задачи. Пример распределения по алгоритму «максимальная матрица» показан на рис. 3.13. В качестве исходной была взята матрица, показанная на рис. 3.1/
При таком первоначальном распределении значение характеризующих критериев по минимаксному критерию равно 27, а по квадратичному – 729. Данные значения можно использовать как верхнюю границу в любых алгоритмах. Для сравнения был поставлен вычислительный эксперимент. В эксперименте сравним данный алгоритм с квадратичным и минимаксным критерием с выбранными ранее эталонными алгоритмами.
Исследование алгоритма Крона модифицированного первоначальными матрицами «численный выбор»
Вкладка «алгоритм Крона».На рис. 4.13 и 4.14 представлены две вкладки для алгоритма Крона, так как у данного алгоритма реализовано большое количество модификаций [93-97].
Параметр «Кол-во повторений» влияет на количество повторений решения по алгоритму Крона для случайной первоначальной матрицы и двух критериев (квадратичный и минимаксный). При решении с количеством повторений больше одного выбирается лучший результат.
Число, введённое в этот параметр, характеризует вероятность попадания в минимальную первоначальную матрицу. Чем выше значение данного числа, тем выше точность решения относительно оптимального. Значение данного информационного блока рассчитывается по формуле полной вероятности наступления событий и зависит от размерности матрицы, которая передается на вход, и значений, которые она может принимать.
Данный элемент ввода также проверяется на ввод некорректных данных и имеет ограничение на количество повторений в 9999 999 999. Данное ограни 120 чение введено в связи с тем, что добавление еще одного порядка значительно замедляет работу алгоритма. Пример ошибки показан на рис. 4.15.
Особо стоит заметить, что данное программное средство привязано к операционной системе семейства Windows и требует обязательной установки .NET Framework версии 4.0 и выше, так как внутри алгоритма для улучшения скорости обработки реализована возможность параллельного расчета части не зависимых вычислительных экспериментов.
Использование данного пакета позволяет не контролировать самостоятельно количество потоков и не синхронизировать их выполнение. Данный алгоритм может быть применен в системах другого вендора только после перекомпиляции и переписывания метода, который отвечает за многопоточность в приложении.
Выбор любого элемента единичного выбора задействует указанный в подписи алгоритм, дополнительные ограничения не вводятся. На рис. 4.16 представлена структурная схема алгоритма Крона. Схема показывает принцип работы алгоритма, где используются различные варианты комбинаций первоначальных матриц и критериев. Реализовано последовательное вычисление по нескольким критерием, где результат работы по одному критерию являлся начальной матрицей для решения по другому критерию.
Вкладка «алгоритм Алексеева». Вкладка «алгоритм Алексеева» представлена на рис. 4.17. У данной вкладки есть только два чекбокса. Это однопроходный алгоритм без возврата с упорядочиванием и алгоритм без упорядочивания. Этот алгоритм использовался как целевой и достаточно точный, поэтому для него не исследовались различные модификации.
Данный алгоритм достаточно подробно разобран в предыдущих частях диссертации, поэтому отдельная структурная схема для него не рисовалась. Выбор любого чекбокса добавляет указанный алгоритм к эксперименту[103].
Вкладка «алгоритм Холланда». Эта вкладка (рис. 4.18) требует детального рассмотрения, так как обладает специфическими параметрами, присущими только данному алгоритму.
Начнем рассмотрение с параметра «вероятность мутации». Данный параметр задаётся из диапазона от 0 до 100. Это означает, что при 0 мутация не произойдет никогда, а при 100 мутация произойдет гарантированно. Для данного параметра задано значение по умолчанию, равное 50, которое проставляется при открытии формы или в случае неправильно введённого значения. Пример ошибки, в случае если значение данного параметра вышло за пределы, показан на рис. 4.19.
В ходе работы над данным алгоритмом сделан вывод, что чем выше данный параметр, тем лучше ведет себя алгоритм. Это связано с тем, что мутация позволяет выйти алгоритму из локального минимума (максимума).
Во всем интерфейсе, где допустим ручной ввод данных, обрабатываются значения на корректность ввода и правильность использования параметров. В случае некорректного введения параметров выдаются сообщения ошибки.
Следующим параметром является параметр «вероятность кроссинговера». Как видно из названия, данный параметр отвечает, произойдёт ли кроссинговер или нет. Он также может быть задан из диапазона от 0 до 100 и имеет значение по умолчанию, равное 100.
Следующим параметром является параметр «размер популяции». Данный параметр может принимать значение от 2 до 1000, не может быть меньше двух, так как в случае возникновения кроссинговера нужна хотя бы одна особь, с которой данный процесс может произойти.
Верхняя граница задана вручную и имеет только временное обоснование. К этому параметру нужно относиться очень внимательно, поскольку он может значительно увеличивать время формирования отчета, так как от количества особей в популяции рассчитывается общее число операций, производимых алгоритмом на одном шаге. При малых размерностях задач и больших вероятностях мутации решение становится очень близким к точному.
Имеется также параметр «количество итераций без изменения», который задается границами от 2 до 10000. Он отвечает за улучшение критерия в популяции в течение одного потомства. Особенностью данного параметра является то, что улучшение конкретной особи не учитывается.
Улучшение происходит только в том случае, когда появляется особь с наилучшим критерием по сравнению с наилучшей особью предыдущей популяции.
В связи с большим количеством возможных комбинаций, здесь используется перемножение параметров выбора алгоритма, поскольку, для того чтобы получить один результат, необходимо выбрать по одному чекбоксу в каждой группе (рис. 4.20) [104-105].
Таким образом, мы для своего эксперимента выбрали минимаксный критерий с пропорциональным отбором и без элиты. На рис. 4.21 представлен вариант, когда выбраны сразу несколько решений алгоритма. На рис. 4.22 мы хотим увидеть эти же варианты, но еще и по квадратичному критерию. Так, добавив только один пункт в меню, мы добавим еще три варианта решения.
Подробно операции и способы их проведения были рассмотрены в первой главе диссертации. Элитарная особь может быть получена в результате вычисления по любому алгоритму для решения минимаксных неоднородных задач.
Прогресс выполнения эксперимента. Для облегчения восприятия прогресса прохождения эксперимента введено графическое отображение. Минимальным значением является один опыт. Отображение прогресса представлено на рис. 4.24. Он размещен в нижней части формы. Отображается вне зависимости, на какой вкладке находится пользователь. Исчезает после завершения вычисления всех опытов.
Так как часть экспериментов выполняется в отдельных потоках, приложение может занимать до 100% процессорного времени.
Сохранение допустимо в текстовый файл по комбинации клавиш CTRL+S. Все ключевые столбцы разделены между собой символом табуляции и поэтому легко импортируются в любые программы для оптимальной работы с данными.
Концептуальная модель системы моделирования и решения неоднородных минимаксных задач
Процесс решения неоднородной распределительной задачи с помощью программного обеспечения “Минимакс” состоит из нескольких этапов:
Этап ввода основных параметров. На данном этапе выбирается размерность матрицы, количество процессоров и задач. Выбирается, из какого диапазона будет генерироваться матрица нагрузки. Выбирается количество опытов с этими параметрами. Данный этап может быть пропущен, если имеется набор экспериментов, предоставленный в бинарном файле. Тогда все параметры буду получены из него.
Этап выбора алгоритмов. В зависимости от того, какие режимы поддерживает тот или иной алгоритм, к выбору предоставляются различные возможности. Минимальным является выбор алгоритма с одним единственным критерием.
Для работы некоторых алгоритмов требуется ввод дополнительных данных. Например, для алгоритма Холланда необходимо ввести вероятности мутаций и кроссинговера. В случае если выбран алгоритм с дополнительными параметрами, изначально они заполняются по умолчанию предопределенными значениями.
При вводе параметров алгоритмов и экспериментов выполняется контроль введенных данных, в случае необходимости, выводится сообщение с описанием ошибок исходных данных. После закрытия окна ошибок возможен повторный ввод исходных данных, не корректные данные заменяются на значение по умолчанию.
Генерация исходных данных для экспериментов является основным способом получения входных списков задач. На данном этапе генерируются вари анты экспериментов, в зависимости от параметров, введенных пользователем в графическом интерфейсе или полученных косвенным путем.
Оператор может изменять любые доступные параметры генерации опытов. Возможны различные комбинации следующих параметров: число работ, число приборов, число независимых повторов, число опытов в эксперименте.
К сформированным или загруженным экспериментам будут имплементи-рованы одинаковые алгоритмы, выбранные оператором. В случае если матрица была загружена из файла, данный этап необходимо пропустить.
При необходимости параметры экспериментов и результаты вычислений могут быть экспортированы как в текстовый файл, так и в файл, содержащий структуры данных. Данное свойство позволяет применять исходные параметры для решения в других экспертных системах и сравнить статистический результат. Это действие было проведено со всеми стандартными алгоритмами и критериями, ранее применявшимися для данных алгоритмов.
Позднее исходные данные и введенные параметры отправляются на обработку. В момент процесса выполнения вычислительного эксперимента, задача не может прерываться. Сложные вычисления происходят в отдельном потоке, благодаря чему мы можем увидеть прогресс выполнения. Этот этап самый ресурсоемкий. Он может занимать продолжительное время и зависит от производительности процессора.
При сохранении результата выполнения эксперимента, есть возможность, осуществить запись в текстовый файл, для последующей работы обработки в любой программе. Решение генерировать отчеты в текстовый файл было принято в связи с тем, что разработка графического отображения сравнительных результатов потребовала бы значительных трудозатрат.
В настоящее время существует достаточно много решений, умеющих работать со сводными таблицами и делать графическое отображение исходных данных. В данной работе активно применялась программа из пакета Microsoft Office 2010, продукт Microsoft Excel 2010.
Применение независимого интерфейса для реализации графического отображения дало возможность по мере выполнения экспериментов подстраивать отображения результатов в удобный для человека читаемый вид.
При разработке архитектурного видения было принято решение, каждый алгоритм выделить в отдельный класс, тем самым достигалась возможность использовать любой алгоритм решения задачи без особого изменения интерфейса и большого количества доработок.
Было решено, что генератором экспериментов и при необходимости загрузкой и выгрузкой их должна заниматься программа, реализующая графический интерфейс.
В связи с тем, что использование различных критериев в алгоритме требует специальной модификации алгоритма к критерию, принято решение, что каждый критерий должен реализовываться внутри класса. Образец текущего решения представлен на рис.4.2.
В связи с тем, что классы решают конкретную задачу и получают только необходимую информацию о параметрах конкретного эксперимента, мы можем добиться единообразного интерфейса для любых алгоритмов. Это облегчит понимание программы пользователем и ускорит выполнение экспериментов.
Интерфейс взаимодействия с пользователем является ключевым элементом любого программного средства. Чем удобнее и понятнее будет интерфейс пользователя, тем лучше будет и все приложение. При разработке данного программного обеспечения интерфейс пережил две версии.
В первой версии автор попытался разместить все алгоритмы и параметры на одном экране, что привело к огромному числу элементов на одной странице и сложности понимания, как это все работает.
Уже для первой версии программы было решено использовать модульное построение алгоритмов решения минимаксной задачи, что в последующем дало возможность не переписывать все исходные алгоритмы, а только заменив графический интерфейс, получить работоспособный продукт.
Правильность выбора архитектурного решения на этапе формирования первоначальной версии стало то, что исчезла необходимость проверять корректность расчетов, поскольку они были проверены и отлажены заранее.
Первая версия пользовательского интерфейса не очень удобна для использования и непонятна. Был изменен внешний вид пользовательского интерфейса, с учетом практик компании Microsoft в создании модульной ленты (рис. 4.3).
Использование модульной ленты позволило вынести основные параметры всех алгоритмов на отдельную вкладку. Это дало облегчение восприятия и возможность простой настройки параметров. Использование вкладок делает интерфейс гибким. На вкладке выбираются параметры, необходимые для конкретного алгоритма.
В случае увеличения количества алгоритмов, не нужно придумывать, куда добавить еще элементы, создается новая вкладка с наименованием алгоритма. На рис. 4.4 представлена общая схема функционирования интерфейса пользователя. В связи с тем, что мы хотим управлять количеством экспериментов, их распараллеливанием на потоки, каждый класс должен уметь решать задачу только с одним набором данных. Это позволит вычислять время и контролировать прогресс решения.