Содержание к диссертации
Введение
1. Распределительные задачи теории расписаний и методы их решения 15
1.1. Параллельное упорядочивание как важнейший этап составления расписаний 15
1.2. Математическое описание задачи параллельного упорядочивания 18
1.2.1. Работы и операции при составлении расписаний 18
1.2.2. Критерии составления расписаний 20
1.2.3. Характеристика и функциональная классификация задач теории расписаний 21
1.2.4. Математическая модель классической распределительной задачи 24
1.3. Основные аспекты выбора методов решения задач теории расписаний 27
1.4. Детерминированные методы решения распределительных задач 28
1.4.1. Целочисленное линейное программирование 28
1.4.2. Методы ветвей и границ. Заполнение работ по устройствам 30
1.4.3. Методы ветвей и границ. Заполнение устройств по работам 31
1.4.4. Приближенные методы списочного составления расписаний. Алгоритм критического пути 33
1.4.5. Возможности и сферы применения детерминированных методов 37
1.5. Эвристические и вероятностные методы решения распределительных задач 38
1.5.1. Предпосылки появления приближенных вероятностных и эвристических методов.. 38
1.5.2. Комбинаторно-эвристический поиск. 40
1.5.3. Методы отжига 40
1.5.4. Метод роящихся частиц (particle swarm) 41
1.5.5. Табуированный поиск (Tabu Search) 42
1.5.6. Эволюционно-генетический подход 43
1.6. Эволюционно-генетические методы решения распределительных задач 44
1.6.1. Общая характеристика эволюционно генетического подхода 44
1.6.2. Представление данных в генах 46
1.6.3. Стратегии отбора 46
1.6.4. Стратегии формирования нового поколения 48
1.6.5. Генетические операторы 49
1.6.6. Модели ЭГА 51
1.6.7. Некоторые обобщения 52
1.7. Выводы по первой главе 55
/. 7.1. Причины использования приближенных алгоритмов в распределительных задачах.. 55
1.7.2. Основания для исследования возможностей эволюционно-генетических аігоритмов в
теории расписаний 55
1.7.3. Основные направления исследований по использованию эволюционно-генетических алгоритмов в теории расписаний 56
1.7.4. Проблемы инструментальной поддержки исследований эволюционно-генетических алгоритмов в теории расписаний 56
2. Эволюционно-генетическая модель распределительной задачи и ее основные свойства 57
2.1. Побитовая генетическая модель распределительной задачи 57
2.1.1. Влияние сущностных свойств распределительных задач теории расписаний на генетические модели 57
2.1.2. Модель гена распределительной задачи теории расписаний 59
2.1.3. Примеры построения и использования побитового гена распределительной задачи. 64
2.2. Эволюционная модель распределительной задачи и ее основные составляющие 67
2.2.1. Оператор кроссовера в распределительной задаче 67
2.2.2. Оператор мутации в распределительной задаче 72
2.2.3. Оператор инверсии распределительной задаче 74
2.2.4. Оператор выбора в распределительной задаче 77
2.3. Эволюционная модель распределительной задачи 78
2.3.1. Итерационный процесс поиска ЭТА 78
2.3.2. Пример организации итерационного поиска в ЭГА 81
2.3.3. Особенности системы поиска эволюционного алгоритма 83
2.4. Сравнительный анализ примеров решений 85
распределительной задачи эвристическими алгоритмами 85
2.4.1. Задачи и алгоритмы для сравнения 85
2.4.2. Решение задачи эволюционно-генетическим алгоритмом 86
2.4.3. Решение задачи методом отжига 88
2.4.4. Решение задачи методом роящихся частиц 89
2.4.5. Сравнительная оценка результатов применения к РЗ различных методов и алгоритмов решения 91
2.5. Выводы по ВТОРОЙ ГЛАВЕ 95
2.5.1. Состоятельность эволюционно-генетических алгоритмов при решении распределительных задач 95
2.5.2. Основные направления исследования и оптимизации свойств эволюционно-генетических алгоритмов в теории расписаний. 95
3. Исследование эволюционной генетической модели распределительной задачи 96
3.1. Система «РЗ-ЭГА», задачи и методы её исследования 96
3.2. Исследование свойств «РЗ-ЭГА» для 2-х устройств 973
3.2.1. Исследование точностных показателей 97
3.2.2. Исследование показателей быстродействия 100
3.2.3. О перспективных направлениях дальнейших исследований системы «РЗ-ЭГА» 102
3.3. Некоторые результаты исследования свойств системы «рз-эга» для 3-х устройств 103
3.3.1. Исследование нестабильности ЭГА для 3-х устройств 103
3.3.2. Предварительные выводы о нестабильности ЭГА 105
3.4. Исследование влияния параметров эга на вероятностную точность решения РЗ 106
3.4.1. Постановка задачи исследования 106
3.4.2. Широкодиапазонное исследование 4-х факторного пространства ЭГА 108
3.4.3. Исследование найденного перспективного диапазона факторного пространства.. 111
3.4.4. Реализация стратегии крутого восхождения для отыскания области экстремума ИЗ
3.4.5. Исследование подозрительного на экстремум диапазона. 114
3.4.6. Градиентный поиск в экстремальной области по факторам X j иХ ^ U7
3.4.7. Детальное исследование предполагаемой экстремальной области 118
3.4.8. Эксперимент по проверке экстремальной области 119
3.5. Влияние весов работ в распределении на степень точности эга 122
3.6. Выводы по ТРЕТЬЕ ГЛАВЕ 128
3.6.1. Исследование показателей системы «РЗ-ЭГА» для двух устройств 128
3.6.2. Исследование показателей системы «РЗ-ЭГА» для трех устройств 128
3.6.3. Исследование показателей системы «РЗ-ЭГА» в зависимости от распределения весов работ 129
4. Исследование феномена вероятностной точности решения распределительной задачи при использовании эга 130
4.1. Теоретико-экспериментальное обоснование оценки эффективности эга вероятностной точностью 130
4.1.1. Теоретические предпосылки оценки эффективности ЭГА вероятностной точностью 130
4.1.2. Экспериментальное исследование влияния кол-ва заданий на эффективность ЭГА 131
4.1.3. Исследование стабильности работы ЭГА 134
4.1.4. Поиск наихудших распределений для ЭГА 137
4.2. Имитационно-статистический подход к оценке оптимальности решения эга... 141
4.2.1. Исследование распределительной задачи «РЗ-ЭГА» на наличие закономерностей формирования вероятностной точности 141
4.2.2. Теоретические основы оценки заданных вероятностно точностных условий решения РЗ 144
4.2.3. Предельная ресурсная оценка решения РЗ параллельными ЭГА 146
4.3. Исследование быстродействия применения пакетной обработки 149
4.3.1. Предпосылки нестабильности времени выполнения операций ЭГА 149
4.3.2. Экспериментальное исследование временных характеристик при фиксированном порядке выполнения ЭГА 151
4.3.3. Экспериментальное исследование временных характеристик при свободном порядке выполнения ЭГА 152
4.3.4. Методика оценки верхней границы по времени выполнения ЭГА 154
4.4.. Исследование алгоритма адаптации уровня мутации в процессе решения 156
4.5. Выводы по четвертой главе 161
5. Программный комплекс «projectsheduler» имитационного моделирования решения распределительной задачи 162
5.1. Функциональная структура пк 162
5.2. Объектно-ориентированное конструирование функциональных блоков 165
5.3. Структура баз данных пк projectsheduler 168
5.4. Интерфейс пк projectsheduler и работа с ним 173
Заключение 187
Список использованных источников 189
Приложения 199
- Параллельное упорядочивание как важнейший этап составления расписаний
- Побитовая генетическая модель распределительной задачи
- Система «РЗ-ЭГА», задачи и методы её исследования
- Теоретико-экспериментальное обоснование оценки эффективности эга вероятностной точностью
Введение к работе
Задачи теории расписаний имеют не только важное теоретическое значение, как относящееся в основном к классу NP-полных задач, но и получили широкое практическое распространение во множестве инженерных и управленческих задач [41,46,46,67]. Везде, где требуется упорядочить и распределить какие либо ресурсы между агентами (исполнителями), возникает вопрос эффективного планирования. Оптимальность планирования в значительной степени определяет технико-экономические показатели производственных и бизнес процессов. Построение оптимального плана распределения может занять даже на современных многопроцессорных системах многие месяцы и годы, при использовании точных методов решения, например, ветвей и границ (МВГ). С другой стороны, сейчас применяемые для таких задач быстрые, но приближенные списочные методы, такие, как метод критического пути (МКП), могут давать большую погрешность, приближающуюся к 30%[46]. Такое отклонение от оптимума в большинстве случаев является неприемлемым. Возникает необходимость в методах, характеризующихся сочетанием противоречивых свойств: полиноминальной зависимостью времени счета от размерности задачи и точностью близкой к оптимальной (по крайне мере значительно лучшей, чем у МКП). К такому классу методов относятся эволюционно-генетические алгоритмы (ЭГА), которые являются на сегодняшний момент наиболее гибкими и эффективными из всех известных приближенных алгоритмов[26].
Таким образом, исследование возможности решения распределительных задач теории расписаний с помощью приближенных методов класса ГА является актуальной задачей.
Цель и основные задачи диссертационной работы.
Основной целью диссертации является исследование возможностей решения задач теории расписаний на основе генетических алгоритмов. В связи с этим возникла необходимость решения следующих научных задач:
разработка, обоснование и исследование эволюционно-генетической модели (ЭГМ) распределительной задачи (РЗ) теории расписаний;
нахождение оценок, определяющих влияние параметров ЭГА и параметров самой РЗ во взаимосвязи на качество решения, т.к. из-за вероятностной природы генетических алгоритмов получаемые решения всегда имеют некоторый разброс относительно оптимума;
исследование возможности применения ЭГА в качестве метода оценки фактического значения оптимума для РЗ большой размерности;
разработка программного средства, реализующего как исследуемую модель решения распределительных задач, так и библиотеку моделей других наиболее известных методов, а также дающего возможность гибкого автоматизированного проведения сравнительных численных экспериментов.
Существенные научные результаты, полученные в диссертации:
1. эффективная побитовая генетическая модель распределения заданий и основанная на ней эволюционно-генетическая модель распределительной задачи теории расписаний, учитывающие специфику работы ЭГА при решении такого рода задач, а также влияние на этот процесс особенностей современного аппаратно-программного обеспечения;
методика имитационно-поискового исследования, описания и выделения эффективных значений параметров системы «РЗ-ЭГА», обеспечивающих максимальную доверительную вероятность получения оптимального решения РЗ;
найденная по этой методике область эффективных значений параметров системы «РЗ-ЭГА», обеспечивающих максимальную доверительную вероятность получения оптимального решения в диапазоне параметров РЗ: п = Ъ (число исполнителей) и
/я = 17 -25 (число работ), (я = 4 и т = \1 -19), а также я = 5и
т = \1 ;
имитационно-статистический подход к параметрической оценке доверительной вероятности определения оптимального решения РЗ и методика его реализации;
найденные по этой методике доверительные значения количества параллельных опытов по оценке с помощью ЭГА величины оптимума решения РЗ, обеспечивающих заданную
if if.
вероятность достоверности результата в диапазоне параметров РЗ: п = Ъ (число исполнителей) и т = \1-25 (число работ), (я = 4и
т = 17-19), а также я = 5и т = \1.
Так, для параметров РЗ п = 3 и т = 17получена оценка нижней границы точности р = 0,76 при следующих параметрах модели ЭГА: Pmut = 0,4\,Pmutbjt =0,07,
Passover =lNVm =1050,Nchr =50
Иными словами, для заданных параметров РЗ п и т может быть получено необходимое количество параллельных опытов z, результат применения которых к данной РЗ даст оценку значения ее оптимального решения Q"pl с заданной вероятностью Р (например, 0,99 или 0,99999).
Научная новизна существенных результатов диссертации
определяется следующими отличительными признаками:
побитовая структура эволюционно генетической модели обеспечивает эффективную реализацию этапов эволюционно генетического алгоритма (ЭГА) при решении задач теории расписаний с предъявлением разумных требований к вычислительным ресурсам;
параметры области настроечных значений ЭГА, обеспечивающих максимальную доверительную вероятность нахождения оптимального решения РЗ, значительно отличаются от рекомендованных в литературе теории и практике применения ГА, так вероятность мутации особи составила Pmut = 0,4l вместо рекомендуемых РтШ = 0,1, вероятность мутации бита в генеРтшЬи = 0,07 вместо рекомендуемых Pmutbit = 0,1, вероятность участии особи в кроссовере Pcrossover=\ вместо рекомендуемых Р^,,^^ 0,9 (при этом для параметров РЗ и = 3 ит = 17 выигрыш по нижней оценке точности составил p^lPxyt = 13)1
предложенный имитационно-статистический подход к параметрической оценке доверительной вероятности определения оптимального решения РЗ привносит в результаты такой оценки вероятностный характер, но позволяет назначать сколь угодно большую вероятность правильной оценки;
разработанная методика оценки оптимального решения с наперед заданной доверительной вероятностью обеспечивает возможность применении ЭГА в качестве эталонного метода при работе с задачами большой размерности, что дает большой выигрыш по ресурсам решения сравнительных задач, так исследования показали, что для получения оптимального решения, с доверительной
вероятностью Рдое= 0,9999 (при числе исполнителейи = з, числе работт = 17) необходим запуск всего z = 7 параллельных ЭГА.
Методы исследования. В диссертации применялись методы исследования операций, в частности, методы теории расписаний и методы статического анализа. При реализации имитационных исследований и построения программного средства «Система для проведения исследований в области задач построения расписаний» («ProjectSheduler») использовались методы объектно-ориентированного программирования и нормализации баз данных.
Практическая значимость диссертационной работы определяется несколькими составляющими:
разработанная побитовая эволюционно-генетическая модель позволяет значительно улучшить точностные и временные характеристики при решении практических задач теории расписаний, со свойственной им большой размерностью, что дает значительный эффект, т. к. повышает производительность, уменьшает затраты различных ресурсов и улучшает технико-экономические показатели промышленных и бизнес процессов;
разработанный и апробированный метод параметрической оптимизации позволяет определить близкую к оптимальным область параметров модели ЭГА, гарантирующую эффективное решение РЗ в диапазоне ее важнейших параметров (в работе исследовались области: п = Ъ (число исполнителей) и т = 17-25 (число работ),
(т? = 4и т = 17 -19), а также я = 5и т = 17);
3. разработанная и апробированная методика параллельного
запуска ГА с доверительным количеством запусков z дает
исследователю возможность получать оценки оптимумов и близкие к
оптимальным решения в тех областях параметров РЗ, где невозможно использование точных методов;
предложенные и опробованные алгоритмы и методики параметрической оптимизации и эталонного использования ГА носят достаточно общий характер и легко могут быть перенесены на оценку параметров решений других оптимизационных задач;
разработанное программное средство «ProjectSheduler» показало себя эффективным инструментом решения и исследования РЗ и подтвердило возможность эффективной реализации предложенной ЭГМ на современном аппаратно-программном комплексе;
«ProjectSheduler» позволяет производить оценку ЭГМ при различных параметрах системы «РЗ-ЭГА», обеспечивает легкую расширяемость функциональных возможностей, позволяет добавление новых модификаций моделей ЭГА или других методов.
Кроме того, работа дала хорошее практическое приложение в учебном процессе, т.к. предложенные решения позволяют изучать на практике задачи комбинаторики, теории расписаний, а также применения ЭГА. Автором опубликованы методические указания по теме «Теория расписаний» (см. список публикаций) для дисциплин «Алгоритмические языки и программирование», «Вычислительная техника и программирование».
ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ
Первая глава диссертации посвящена обзору существующих методов решения РЗ теории расписаний. Методы классифицированы по свойственным им точностным и временным характеристикам. Показано, что для решения задач реальной размерности необходимо применение приближенных методов, наиболее гибкими из которых являются методы класса ЭГА. Для диссертационного исследования из всех задач теории расписаний выделен класс однородных задач (в англоязычных изданиях -
«open shop»), в которых нет ограничений на порядок выполнения работ, и каждая работа состоит только из одной операции.
Вероятностная природа моделей изучаемых систем и явлений требует множества сравнительных численных экспериментов для исследования ее характеристик, автоматизированного характера проведения такого рода экспериментов, что позволит значительно упростить исследования, внесет возможность проверки на множестве исходных данных и т.п. Поэтому по результатам обзора существующих методов решения РЗ сформированы следующие направления исследования:
на основе ГА разработать эффективную эволюционно-генетическую модель (ЭГМ) решения задачи теории расписаний;
исследовать взаимосвязь точностных и временных эксплуатационных характеристик ЭГМ в зависимости от параметров системы «РЗ-ЭГА»;
разработать механизм статистического анализа точностных и временных характеристик модели и с помощью него провести параметрическую оптимизацию модели;
разработать программное средство, реализующие гибкое автоматизированное проведение численных экспериментов, включающие в себя программную реализацию полученной эволюционно-генетической модели, а также других методов решения задач теории расписаний.
Последующие главы диссертации посвящены решению указанных задач.
Вторая глава включает в себя изложение результатов анализа возможных построений эволюционно-генетической модели согласно схеме ЭГА. Показано, что наиболее эффективной моделью является побитовое представление хромосомы
X = {GX ={pn{},G2 ={pn2},G3 ={pn3},...,Gm ={pnm}}, (3)
где G - ген, рп -порядковый номер исполнителя, на который назначена
работа, номер исполнителя кодирован числом размером к>бит.
Побитовое представление операторов ЭГА позволяет исполнять их без последующих проверок на корректность получаемого решения. Кроме того, побитовые операторы преобразования и анализа генетических характеристик легко реализуются на любом современном аппаратно-программном комплексе.
Третья глава посвящена статистическому анализу и параметрической оптимизации характеристик системы «РЗ-ЭГА».
При решении РЗ с фиксированными параметрами ЭГА дает довольно большой разброс значений оценок оптимума. Поэтому для анализа его
точностных характеристик введена величина p3=vonm/v, где vonm - число
опытов с полученным точным решением, v - общее число опытов, которая представляет собой частоту наступления положительных событий -нахождений оптимума. Она является экспериментальной оценкой вероятности правильной оценки оптимума р для исследуемой системы «РЗ-ЭГА». При этом в пределах ограниченной по размерам выборки испытуемых РЗ, для каждой из этих выборок может быть получено различное значение оценки рэ. Для повышения надежности количественной оценки свойств «РЗ-ЭГА» в работе принято решение об оценке вероятности р по нижней границе значений рэ - pmin.
С помощью поэтапной оптимизации исследуемой системы «РЗ-ЭГА» значение нижней границы было существенно улучшено и составило р = 0,78
(вместо pmin = 0,06 до оптимизации) при значениях параметров ЭГА значительно отличающегося от рекомендуемых в литературе (например уровень мутации особи составила PWM, = 0,41 вместо рекомендуемых
РтШ = 0,1, а вероятность мутации бита в гене осталась близкой к
рекомендуемому Pmutbit = 0,l и составила Pmutbit = 0,07, несколько сместилась также вероятность кроссовера Pcrossover =1 вместо Pcrossover = 0,9).
Четвертая глава посвящена исследованиям по обоснованию и реализации предложенной в работе схемы получения точного решения РЗ с заданной доверительной вероятностью использованием некоторого числа параллельных запусков ЭГА. На основании проведенного исследования сделан вывод, что пакетное (параллельное) использование ЭГА можно рекомендовать в качестве метода эталонного для оценки, хотя и только с доверительной вероятностью, оптимальных решений РЗ в областях, где применение точных методов принципиально невозможно.
Пятая глава диссертации посвящена алгоритмической разработке модели и реализации программного средства автоматизированного проведения имитационного моделирования. Программное средство (ПС) выполнено по объектно-ориентированной парадигме на языке Object Pascal в среде Turbo Delphi. Система «ProjectSheduler» обладает разделенной структурой методов и объектов представления РЗ теории расписаний, что обеспечивают простую модификацию параметров ЭГМ или добавления новых методов решения. Система не требовательна к ресурсам, может быть запущена на любом ПК с установленной ОС Windows 2000 и выше. Конкретные показатели потребления аппаратных ресурсов напрямую зависят от размерности РЗ и количества введенных экспериментов. Пользователю предлагается удобная система управления созданным им же набором экспериментов, с возможностью модификации параметров алгоритмов и просмотром результатов вычислений в реальном времени. Предусмотрен также гибкий механизм экспорта-импорта данных в другое ПО.
Параллельное упорядочивание как важнейший этап составления расписаний
Теория расписаний (ТР) является одним из наиболее востребованных разделов исследования операций[41,66,68]. В ней исследуются задачи, в которых необходимо разбить совокупность назначенных к выполнению работ на группы. При этом каждая группа представляет собой обособленную совокупность работ (ОСР), выполняемых конкретным техническим средством из нескольких, назначенных для обеспечения всей исходной совокупности работ (ИСР). Работы, выделенные в ОСР, выполняются представленным им техническим средством последовательно и независимо от хода выполнения работ других ОСР. Работы каждой ОСР также выполняются в определенной последовательности. Таким образом, процесс выполнения ИСР превращается параллельно-последовательный, ход его выполнения определяется составленным для этого «расписанием», упорядочивающим решение задачи.
Задачи упорядочения носят самый общий характер. Они возникают там, где существует возможность выбора того или иного порядка выполнения работ: ? планирование производственных процессов на конвейерных линиях; ? производство и сборка сложных индустриальных объектов (всевозможные машины, самолеты, корабли); ? строительство зданий и других архитектурных объектов; 1 организация больших информационных систем - создание аппаратно-программных комплексов параллельной обработки данных (массово-параллельных систем МРР); ? усовершенствование микроархитектуры процессоров (одна из особенностей современных процессоров персональных PC -наличие выделенного диспетчера, который планирует расписание обработки микроопераций с учетом их взаимозависимости по данным и наличным ресурсам); ? разработка ПО планирования коллективной работы (управления проектами); ? планирование массового обслуживания потребителей (турникеты в местах массового скопления людей, управляемые полосы движения на мостах и туннелях и т.п.).
Результаты, к которым приводит то или иное упорядочение, существенно отличаются. В ряде практических случаев эти различия принимают стоимостной характер или определяются какой-либо другой величиной.
Таким образом, составление расписания на данном уровне обобщения представляет собой сочетание процессов упорядочивания двух видов: распределение работ на параллельно выполняемые ОС и распределение их в последовательности по исполнителям.
Зачастую проблему упорядочивания можно сформулировать так, чтобы выделить параллельное упорядочивание работ как отдельную задачу.
Задачи параллельного упорядочивания в теории расписаний рассматриваются при условии, что решены все вопросы, относящиеся к тому, что и каким образом должно быть выполнено. При этом задачи формализуются на основе ряда предположений: 1) не существует зависимости между характером этих решений и устанавливаемым порядком, т.е. характер работ не зависит от последовательности их выполнения; 2) подлежащие выполнению работы определены и заранее известны их ресурсные потребности (разбиение совокупности работ на классы выполняемых и невыполняемых не входит в задачу параллельного упорядочивания); 3) однозначно определены устройства, выделяемые для выполнения заданных работ; 4) задана совокупность всех элементарных действий, связанных с выполнением каждой из работ, и всех ограничений, налагаемых на порядок их выполнения; 5) известно, каким образом осуществляются эти действия, и что существует, по крайней мере, по одному устройству, способному выполнить каждое из них.
Есть определенное различие между терминами "упорядочение" и "составление" расписания. Упорядочение подразумевает формирование очередности операций, выполняемых одним устройством, в то время как составление расписания означает задание последовательности действий нескольким устройствам. Теория расписаний, выделяет вопросы, общие для большинства задач упорядочения. Получающиеся при этом идеализированные модели не могут в точности соответствовать конкретным ситуациям, однако в силу их общности позволяют получать оценки для широкого круга задач в различных областях производства.
Побитовая генетическая модель распределительной задачи
Структура ЭГА обозначена его парадигмой в довольно общем виде и при его применении к определенной задаче необходимо определить конкретную реализацию составляющих: выбрать механизм кодирования параметров задачи (фенотипа) в гены особи (генотипа), определить оптимизационную функцию F (fitness function), определить набор и вероятности операторов ЭГА, а также выбрать условия останова. Основу всей схемы предметно-ориентированного ЭГА задает метод кодирования, т.к. при некорректном преобразовании «генотип - фенотип» в задаче теории расписаний могут возникнуть следующие проблемы[3,5,12,26]: 1. в результате преобразования генотипа в фенотип может получиться решение, которое не является корректным по условиям задачи, например работа, должна быть назначена на не существующие устройство или назначена одновременно на несколько устройств; 2. в случае неоднородности матрицы загрузки, даже если получено корректное назначение работы на устройство, данное назначение может быть запрещено матрицей загрузки; 3. применение операторов ЭГА в связи с их вероятностной основой может также приводить к некорректному решению; 4. сложная структура гена при малом количестве генов приводит к усложнению операторов ЭГА, усложнению декодирования в фенотип и в целом увеличению времени счета[35,42]; 5. представление фенотипа в генотипе избыточным числом байт приводит к замедлению работы операторов ЭГА.
Общий подход к кодированию в гены можно рассматривать со следующей точки зрения. Хромосома это определенный набор информации, представляющий некоторое существующее решение задачи. Хромосому надо разделить на гены так, чтобы информация в одном гене была максимально независима от информации в другом гене, а сам ген имел минимальную длину. Минимальная длина гена обеспечивает максимальное быстродействие (без учета фактора кратности машинному слову). А полная независимость гена дает возможность без дополнительных условий применять операторы ЭГА. Операторы некоторым образом меняют информацию в генах, и способ этого изменения должен быть максимально простым. То есть самое эффективное кодирование формируется при условии, что гены можно переставлять между особями без проверок (оператор кроссовер). Любые биты гена, при этом, можно менять произвольно (мутация), а в результате получать всегда корректное решение.
В общем виде итеративный процесс поиска, который предполагается осуществлять с помощью ЭГА, можно представить как задачу оптимизации некоторой функции F(x],x2,..., хп) - optimum . Функция задает оценку качества хромосомы как совокупности генов, а ее аргументы х1,х2,...,хп есть значения, кодируемые генами.
Рассматривая сформулированную выше проблему ТР как задачу оптимизации функции F{ ) по ее аргументам, можно придти к выводу, что для корректного задания каждого конкретного решения необходимо и достаточно определить соответствие «работа»-«устройство» (связь «один к одному»). Полная /w-совокупность таких связей однозначно определит соответствия «каждое устройство»-«набор его работ» (связи «один ко многим»), В результате определится и многомерное соответствие «все приборы»-«все работы». В категориях генетического подхода данные соответствия задаются структурой гена и структурой образованной ими хромосомы (особи). Структура гена подразумевает некоторую абстрактную (информационную) кодировку состояния какой либо составляющей распределительной задачи. В связи с этим кодирующую функцию гена в РЗ, способы ее задания следует рассмотреть особо.
Можно показать, что для обеспечения возможности задания функции оптимизации достаточно рассмотреть только два варианта построения генной модели распределительной задачи 1. В генах кодируется порядковый номер работы, и номер гена определяет номер устройства. 2. В генах кодируется порядковый номер устройства, и номер гена определяет номер работы.
Система «РЗ-ЭГА», задачи и методы её исследования
Приступая к исследованию эволюционной генетической модели распределительной задачи, стоит отметить, что неверно оценивать метод получения решения в отрыве от самой задачи. Характеристики ЭГА значительно отличаются, если рассматривать их при различных параметрах РЗ. Изменения касаются не только временных показателей, но и такого важного параметра, как точность получаемого решения. Таким образом, распределительная задача и метод ее решения образуют систему, которую необходимо рассматривать в совокупности ее элементов. Название системы «РЗ-ЭГА» было выбрано на основе двух ее главных составляющих: распределительной задачи и эволюционно генетического алгоритма. Абстрактная схема системы представлена нарис. 3.1.
Исследовать всю область параметров РЗ не представляется возможным, поэтому стоит ограничиться наиболее востребованной областью параметров РЗ для числа устройств п є [2..4]. Такие параметры РЗ часто встречаются в современной области многопроцессорной обработки данных [43]. По литературным источникам известно, что чем уже диапазон весов работ для
такого количества устройств, тем труднее точным методам найти решение. Так для диапазона весов работ [29..30] практически всегда требуется полный перебор вариантов для получения решения с помощью метода Романовского [22,23,25]. Более легким является диапазон [25..30], он позволяет получать точные решения за разумное время для определенной размерности РЗ ТР. Таким образом, целесообразным является выбрать для проведения исследований именно этот диапазон [25..30], как наиболее сложный из доступных для проверки диапазонов.
По совершено естественным причинам первым объектом предварительного исследования является система «РЗ-ЭГА» для 2-х устройств, как наиболее простая, изученная точными методами и легко проверяемая на фактическое значение оптимума точными методами решения РЗ.
В случае 2-х приборной системы предварительные исследования показали, что ЭГА практически всегда дает точное решение. При этом при четном числе работ точность сохраняется для всего исследованного диапазона параметров РЗ, а для нечетного значения обнаружена область отклонений от оптимума. Особенности системы «РЗ-ЭГА» при условии кратности числа работ числу устройств подробнее рассмотрены в 3.5.
Для более детального исследования точности решения ЭГА для системы с 2-мя устройствами п = 2 был поставлен эксперимент с числом работ we{17,117,217,317,417} с диапазоном весов работ [25..30]. Параметры ЭГА при этом имели следующие значения: число особей популяции N chr = 50 , число элитных особей N еШ = 1, длительность эволюции - iVlim =500 поколений. При этом вероятности генетических операторов были приняты, как совокупность следующих значений:
Выбор числа работ в соответствии с формулой mi =17 + / 100,/= 0..4 обусловлен предварительными данными, полученными в результате имитационного моделирования [10]. Было найдено, что алгоритм Романовского для такого т, не смотря на довольно большую размерность, может получить точное решение за приемлемое время. В ходе эксперимента генерировалось Nсоп = 50 задач с различными распределениями весов работ.
Теоретико-экспериментальное обоснование оценки эффективности эга вероятностной точностью
Вероятностная природа ЭГА приводит к тому, что результаты, получаемые при его многократном использовании для одной и той же задачи отличаются. Они в ходе его работы определяются псевдослучайными последовательностями, передаваемыми в схему алгоритма. Однако точность алгоритма зависит не только от входной последовательности случайных чисел, но и от условий задачи таких, как ее размерность, конкретное распределение весов работ.
В связи с указанными факторами возникает вопрос о возможности отыскания такой структуры ЭГА, и таких его параметров, при которых эффективность его работы будет наивысшей. В качестве меры эффективности любого приближенного алгоритма естественно принять вероятность рТ получения оптимального решения РЗ при однократном его применении. Экспериментальной оценкой этой вероятности будет относительная частота появления оптимального решения, как случайного события, в ходе многократного применения алгоритма к одной и той же задаче.
Для оценки точности ЭГА введем величину p3=vonm/v, (4.1) где vonm - число опытов с полученным точным решением, v - общее число опытов. Чем ближе величина рэ к 1, тем больше точных решений получает ЭГА, т.е. выше его точность. Точность ГА 10 20 N распределения Рис. 4.1. Точность ЭГА в зависимости от распределения загрузок
Рассмотренный в предыдущем пункте подход к оценке эффективности ЭГА открывает возможности для массовых исследований, как самого феномена вероятностной точности, так и влияния на него параметров решаемой задачи. Поскольку предварительные исследования показали, что эффективность работы ЭГА зависит и от параметров самого алгоритма, и от структуры матрицы загрузки, которая характеризуется и размерностью и диапазоном весов работы, и даже законом распределения весов. Было принято решение стабилизировать ряд основных влияющих факторов. Тогда появляется возможность наглядно оценить и проанализировать влияние других. Одной из возможных постановок задач в рамках сформулированного подхода является исследование разброса вероятностной точности с помощью генерирования и решения серий различных распределений.
Рассмотрим исследованную ранее задачу размерности п - 3 , т - 17 при диапазоне работ [25..30]. В процессе исследования генерировалось 30 разных наборов работ, каждый из которых подвергался обработке по v = 100 раз ЭГА с целью получения наилучшего решения. По формуле 4.1 рассчитывалась вероятностная точность рэ для каждого из распределений.
Параметры ЭГА были выбраны в следующем виде: число особей Nchr - 50 , NеШ =1, Nlim =500 , вероятности генетических операторов: Pcross=0,9,
Полученные значения /?э представлены на рис. 4.1, в естественной последовательности их получения. Хорошо заметно, что степень точности алгоритма очень сильно меняется от шага к шагу, а это значит, что она сильно зависит от исходного распределения весов работ предназначенных для построения расписания.
Чтобы глубже оценить выявленный феномен и обнаружить скрывающуюся за ним закономерность, было решено расширить диапазон исследование в рамках вычислительных возможностей как по количеству обрабатывающих устройств, так и по количеству распределяемых работ.
Результатом этого явился план эксперимента, содержание которого характеризуется следующими параметрами: 1-ая группа опытов п = 2, т-16,17,18; 2-ая группа п = 3, т = 15,16,17,18, 3-я группа и = 4, т = 16,17,18,19,20. Все опыты проводились так же как и в предыдущем эксперименте. Сводные результаты представлены на рис.4.2, рис. 4.3, рис. 4.4.
