«Применение ит при оценке времени работы алгоритмов»

Скачать 208.64 Kb.

Название	«Применение ит при оценке времени работы алгоритмов»
страница	3/5
Дата публикации	26.04.2015
Размер	208.64 Kb.
Тип	Реферат

100-bal.ru > Информатика > Реферат

1 2 3 4 5

Глава 3. Оценка времени работы генетического алгоритма

В данной главе предлагается оценить время решения задачи построения оптимального расписания в системе обслуживания с блокировками генетическим алгоритмом. Генетический алгоритм является параметризированным, поэтому процесс оценки времени работы был проведён в два этапа. На первом этапе ставилась цель произвести пробные пробеги с относительно ограниченным количеством итераций для определения значений параметров алгоритма. Второй этап являлся результативным, объединившим все наиболее подходящие значения параметров. Были заданы времена обработки для задачи с 5 приборами и 49 требованиями. Проведено 100 итераций и получен период обслуживания 3555. Последовательностью, на которой это было достигнуто, явилась 6, 5, 29, 4, 2, 35, 20, 23, 44, 42, 14, 1, 10, 17, 41, 40, 37, 36, 38, 48, 45, 18, 33, 31, 7, 24, 15, 8, 30, 49, 9, 3, 21, 34, 43, 16, 12, 46, 26, 13, 19, 27, 32, 28, 39, 11, 22, 47, 25. Несколько других хороших последовательностей было получено попутно. Для сравнения, эвристика Abadi произвела в этом случае расписание с периодом обслуживания 3761.

Естественно задаться вопросом, произведёт ли сравнимые результаты простой рандомизированный поиск. Такой поиск с размером выборки в 22000 случайно сгенерированных последовательностей требований произвёл периоды обслуживания с мат. ожиданием 4000 и стандартным отклонением 80. Для наилучшей последовательности в этом случае период обслуживания был равен 3710.

Типичное время вычисления для 100 поколений с единым случайным стартом достигало порядка 50 минут на компьютере 486 (66 MHz), выполняющем программный код на интерпретируемом языке QBASIC (версии 5). Это требование является умеренным для методов эвристического поиска со сравнимой производительностью, если принять во внимание размер пространства решений, который равен 49! Из-за перестановочного характера расписаний. Тем не менее, эффективность использования оптимально параметризованного генетического алгоритма для получения хороших расписаний очевидна.

Для того чтобы сравнить эффективность генетического алгоритма с эвристикой Abadi, программный код алгоритма был переписан на языке C и были рассмотрены сравнительные задачи. Последовательные тесты были проведены на машине SUN SPARC station 20 model 50. Количество требований в тестах достигало 250, а количество приборов не превосходило 20. Оказалось, что генетическому алгоритму в среднем требовалось не более 15 поколений для достижения результата, полученного алгоритмом Abadi, и времени на это он затрачивал меньше, чем алгоритм Abadi (разность времён – порядка 1 секунды в среднем). После генерации 100 поколений результаты были значительно улучшены, но и времени требовалось больше. Однако в отдельных случаях решения, полученные генетическим алгоритмом даже после 100 итераций, не смогли показать лучшие результаты, чем полученные алгоритмом Abadi (3 случая из 80).

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

Глава 4. Оценка времени работы алгоритма табуированного поиска

Здесь пойдёт речь об оценке времени построения расписания алгоритмом табуированного поиска. Табуированным поиск называется так из-за того, что некоторые элементы пространства решений отсекаются как бесперспективные или с той целью, чтобы, натыкаясь на них снова, алгоритм не зацикливался, то есть такие элементы получают статус табу. Было рассмотрено два алгоритма TS (Tabu Search) и TS+M (Tabu Search + Multimoves), второй предполагается более перспективным, чем первый. Результаты их работы сравнивались с генетическим алгоритмом, рассмотренным в главе 2.

Все три алгоритма были закодированы на языке C++ и были запущены на компьютере с процессором Pentium IV 1000 MHz, использовались сравнительные тесты, которые предлагаются для классической задачи составления расписаний (без блокировок). Тесты содержат 120 особенно трудных задач 12 различных размеров, выбранных из огромного числа случайно сгенерированных задач. Выборка из 10 задач была предоставлена для каждой группы размеров n x m: 20 x 5, 20 x 10, 20 x 20, 50 x 5, 50 x 10, 50 x 20, 100 x 5, 100 x 10, 100 x 20, 200 x 10, 200 x 20, 500 x 20.

Алгоритмам TS и TS+M требуется первоначальная перестановка, которая может быть найдена любым методом. В данных тестах используется алгоритм NEH (к слову, предназначенный для классической задачи (без блокировок)) для построения первоначальной последовательности. Этот алгоритм считается одним из лучших для поставленной цели.

В проводимых тестах TS и TS+M прерываются по достижении количества итераций, равного Maxiter на каждой задаче. В TS+M для того чтобы определить сходимость по сравнению с генетическим алгоритмом и TS, устанавливаем Maxiter=100, 200, 500, 1000, 3000, 10000 и 30000 итераций.

Эффективность алгоритмов была проанализирована с обеих сторон: с точки зрения процессорного времени и качества решения.

Эвристика табуированного поиска TS+M имеет значительно лучшую производительность, чем генетический алгоритм. Для 100 итераций TS+M находил решения значительно более близкие к оптимальным, чем генетический алгоритм (за оптимальные брались решения, полученные алгоритмом RON). В особенности, TS+M превосходит генетический алгоритм в задачах большого размера. Кроме того, процессорное время для 100 итераций у алгоритма TS+M существенно меньше, чем у генетического. Естественно, что с увеличением количества итераций время работы TS+M значительно возрастало, но и точность решения повышалась. Например, для 20 приборов и 500 требований время работы составило 475,0 с. Для получения результата для каждых уникальных исходных данных генетический алгоритм выполнял 10 пробегов и брались усреднённые значения (в силу его недетерминированности). Таким образом, табуированный поиск показал превосходство над генетическим алгоритмом для данной задачи.

1 2 3 4 5

Похожие:

	Применение ит при оценке мультипликативного эффекта экспортно-импортных... Реферат на тему «Применение ит при оценке мультипликативного эффекта экспортно-импортных потоков на основании сетевой модели» 6		Конспект урока определение и свойства алгоритма фио (полностью) Гайфулина... Цель урока: дать учащимся понятие алгоритма, изучить свойства алгоритмов, применение алгоритмов в жизнедеятельности человека
	Конспект по теме «Алгоритмы» Цель урока: дать учащимся понятие алгоритма, изучить свойства алгоритмов, применение алгоритмов в жизнедеятельности человека		Программа по формированию навыков безопасного поведения на дорогах... Тема: Понятие алгоритмов, свойства алгоритма. Исполнители алгоритмов, система команд исполнителя. Способы записей алгоритмов. Формальное...
	Конспект урока на тему "Алгоритм. Свойства алгоритмов. Виды алгоритмов... ...		Фио группа Правильных ответов Тест №2 по «Оценке собственности» Вопрос... Экономика и бухгалтерский учет, 080112. 51 Маркетинг, 080501. 51 Менеджмент, 080108. 51 Банковское дело, 080504. 51 Государственное...
	Конспект урока по теме: "Способы записи алгоритмов". Фио (полностью)... Цель урока: Создание условий для формирования целостного представления и навыка работы по способам записи алгоритмов		На уроках русского языка необходимо вводить следующие этапы работы При этом речь идет не о заучивании простых алгоритмов, а о подлинной фундаментализации школьного образования, при которой акцент...
	Утверждается на заседании методического объединения. В процессе работы... Требования, устанавливаемые настоящим Положением, основаны на Уставе Учреждения и направлены на урегулирование отношений, возникающих...		Свойства степени с натуральным показателем Закрепить знание свойств степени с натуральным показателем, способствовать отработке алгоритмов умножения и деления степеней, возведение...
	Программа по формированию навыков безопасного поведения на дорогах... Иметь представление об алгоритмах, свойствах алгоритмов и записи алгоритмов. Приводить примеры алгоритмов из жизни. Применять готовые...		Реферат Марсианская техника в романе Герберта Уэллса «Война миров» ...
	Урок по информатике по теме «Методика обучения сортировке одномерного массива» Образовательная: формирование у учащихся навыков составления алгоритмов сортировки массива методом прямого выбора и методом пузырька;...		Рефератов по курсу «Математическая логика и теория алгоритмов» Темпоральные логики высказываний линейного времени и вычислительных деревьев: их синтаксис и семантика
	План-конспект урока алгоритм. Свойства алгоритмов. Виды алгоритмов. Формы записи алгоритмов Преподавание алгебры в 7 классе ведётся по умк «Алгебра 7 класс» под редакцией А. Г. Мордковича. Учебное пособие для изучения курса...		ПРИМЕНЕНИЕ КОМПЬЮТЕРНЫХ ТЕХНОЛОГИЙ ПРИ ПОДГОТОВКЕ К Экзаменам ДОКЛАД “ПРИМЕНЕНИЕ КОМПЬЮТЕРНЫХ ТЕХНОЛОГИЙ ПРИ ПОДГОТОВКЕ К ЕГЭ ФИЗИКЕ” Подготовил учитель физики Кюкяйской СОШ

Школьные материалы