WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

загрузка...
   Добро пожаловать!

Pages:     | 1 | 2 ||

Аналогичные тесты проводились для задачи коммивояжера. Для сравнения использовалась тестовые задачи с городами, расположенными на круге в случайном порядке. Среда имеет два состояния: матрица расстояний для исходной нумерации городов и матрица расстояний при взаимном изменении порядковых номеров двух городов. Кроме того, проводилось сравнение использования двух видов кодирования генотипа: порядкового и перестановочного.

Таблица 2 Задача коммивояжера, перестановочное представление с адаптацией; 2 матрицы.

среднее число средняя стабильность вычислений точность Подход с базой опыта 96.0.000757 0.Диплоидный алгоритм 536.38 0.001174 0.Структурный алгоритм 573.50 0.014067 0.Гипермутация вероятность 0.5 676.97 0.0.Гипермутация вероятность 0.1 650.72 0.0.Гаплоидный алгоритм 663.53 0.018557 0.Методы показали результаты, аналогичные тесту на задаче о ранце.

Точность решения для всех подходов выше, чем в задаче о ранце, что объясняется использованием процедур адаптации (локальной оптимизации) особей. Точность решений для перестановочного кодирования выше, чем у порядкового (для диплоидного алгоритма на 10%, гаплоидного на 5%, с базой опыта на 2%).

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

В работе было проведено сравнение классических методов оптимизации и популяционно-генетического для адаптации оптимального решения на примере нестационарной задачи о ранце по точности и количеству вычислений. В качестве тестовых рассматривались задачи с четырьмя весовыми ограничениями, размерности 30, 100 и 1000 предметов. Тесты проводились для разных отрезков постоянства.

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

Таблица 3. Сравнение средней точности решения стационарной задачи о ранце, размерность 1000.

Метод Метод ветвей Генетический Оценка динамического и границ алгоритм программирования 0.25 средняя точность 0.9986 N/A 0.кол-во вычислений 1253 1126877 0.5 средняя точность 0.9995 N/A 0.кол-во вычислений 3103 3235522 0.75 средняя точность 0.9998 N/A 0.кол-во вычислений 121963 6074444 0.9 средняя точность 0.9997 N/A 0.кол-во вычислений 83676 8132412 Вторая серия экспериментов (Таблица 4,Таблица 5) была проведена на нестационарной задаче о ранце, в качестве меры отрезка постоянства рассматривалось количество оценок решения. В этой серии сравнивались метод с использованием базы опыта и метод ветвей и границ. Для метода ветвей и границ справедливо: чем больше отрезок постоянства, тем меньше вероятность найти оптимальное решение для больших ограничений, поскольку эти ветви будут исключены из рассмотрения при работе алгоритма на меньших ограничениях.

Точность классического алгоритма падает при увеличении отрезка постоянства, и если весовые ограничения Wmax (t) последовательно не увеличиваются. В то время Ограничение как точность генетического алгоритма не зависит от отрезка постоянства и порядка следования задач и остается достаточно высокой (в среднем 0.96).

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

Таблица 4. Сравнение средней точности решения нестационарной задачи о ранце в зависимости от отрезка постоянства.

30 50 70 100 150 Отрезок постоянства Метод ветвей и границ 0.8407 0.8187 0.7717 0.6966 0.4924 0.Генетический алгоритм 0.9511 0.9539 0.9559 0.9557 0.9624 0.Таблица 5. Сравнение средней точности решения нестационарной задачи в зависимости от порядка следования ограничений Возрастание весовых Убывание весовых ограничений ограничений Метод ветвей и границ 0.7295 0.Генетический алгоритм 0.9504 0.Для каждого запуска вычислялось отношение лучшего найденного решения к верхней (Пbest Upper ) и к нижней оценке (Пbest Low ) средние значения по всем запускам приведены в таблице (см. Таблица 6). В таблицу также занесено «Максимальное число ожидающих ОТК», которое соответствует максимальной размерности матрицы переналадок в ходе поиска решения. Верхняя оценка (Upper ) получена построением гамильтонова пути методом самого дешевого включения, нижняя ( Low ) как сумма констант приведения по строкам и столбцам матрицы переналадок.

Таблица 6. Оценки полученного решения для задачи определения оптимальной последовательности выполнения ОТК.

Число ОТК 70 150 Пbest Среднее отношение 0.51 0.61 0.Upper Пbest Среднее отношение 1.04 1.00 1.Low Максимальное число ожидающих ОТК 54 113 Из таблицы (Таблица 6) видно, что алгоритм дает решения близкие к нижней оценке, которая в общем случае является недостижимой, что говорит о хорошем качестве получаемых решений.

На основе предложенной модели и с использованием программного комплекса была решена задача оптимальной загрузки уникального оборудования.

Задача загрузки уникального оборудования сводится к нестационарной задаче о ранце.

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

Таблица 7. Оценки полученного решения для задачи планирования загрузки уникального оборудования на рабочую неделю.

Пbest Пbest Среднее отношение Среднее отношение Upper Low 1.02 0.Таблица 8. Оценки полученного решения для задачи оперативного управления.

Среднее отношение Среднее отношение Количество Пbest Пbest дополнительных заявок Low Upper 10 1.03 0.5 1.03 0.Задача оперативного управления сводится к составлению плана загрузки уникального оборудования на рабочую смену с учетом поступления дополнительных заявок (до десяти за смену).

В качестве верхней оценки (Upper ) выступает решение линейной задачи о ранце, нижней ( Low ) – решение дискретной задачи по методу Данцига.

Полученные результаты приведены в таблицах (Таблица 7, Таблица 8).

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

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

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

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

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

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

Проведено сравнение работы классических оптимизационных алгоритмов и популяционно-генетического алгоритма на нестационарной задаче о ранце.

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

На основании построенной модели, были решены прикладные задачи:

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

Публикации по теме диссертационной работы Статьи, опубликованные в сборниках, рекомендованных ВАК:

1. Булгаков, И.В. Решение задачи коммивояжера с использованием генетических алгоритмов/ И.В. Булгаков, Е.А. Неймарк //Вестник ННГУ. -1998 - Вып.2(19) - с.186-192.

2. Батищев, Д.И. Решение задачи оптимизации нестационарной функции при помощи генетического алгоритма с использованием базы опыта / Д.И Батищев, Е.А.Неймарк // Известия СПбГЭТУ «ЛЭТИ». Серия Информатика, управление и компьютерные технологии. – Санкт-Петербург, изд-во СПбГЭТУ «ЛЭТИ». – 2006 - Вып. 1/2006.- сс.29-3. Неймарк, Е.А. Решение нестационарной задачи о ранце при помощи генетического алгоритма. / Е.А. Неймарк //Вестник ННГУ. – 2006 - Вып.3(32).

с.133-137.

Другие публикации:

4. Батищев, Д.И. Решение задачи коммивояжера с использованием генетических алгоритмов и эвристических методов./ Д.И. Батищев, И.В.Булгаков, Е.А.

Неймарк //Тезисы докладов международной конференции «Новые информационные технологии в науке, образовании и бизнесе».-1997- с. 171 5. Батищев, Д.И. Вопросы визуализации при решении экстремальных задач с помощью ГА./ Д.И.Батищев, С.А. Исаев, Н.В.Старостин, Е.А.Неймарк, Е.К.

Ремер //Тезисы докладов. Всероссийская научно-практической конференции “Компьютерная геометрия и графика”.- Н.Новгород, НГТУ.- 1998г., стр. 1016. Батищев, Д.И. Декомпозиционный подход к нахождению минимального гамильтонова цикла./ Д.И Батищев, Е.А.Неймарк // Оптимизация и моделирование в автоматизированных системах. Межвузовский сборник научных трудов.-Воронеж:ВГТУ-1998-с12-19.

7. Батищев, Д.И. Диплоидное представление в оптимизации нестационарной функции. / Д.И Батищев., Е.А.Неймарк //Труды НГТУ системы обработки информации и управления. -2005 - Том 54. Выпуск 12 - сс.17-22.

8. Неймарк, Е.А. Оптимизация нестационарной функции с использованием генетического алгоритма / Е.А. Неймарк // Вестник ВГАВТ. Межвузовская серия Моделирование и оптимизация сложных систем. - Н.Новгород: Изд-во ФГОУ ВПО ВГАВТ – 2005 – Вып.14-с.85-90.

9. Neumark, E.A. The application of GA for the decomposition of the TSP./ E.A.

Neumark, A.M. Perelubsky //VI International Congress of Mathematical modeling.

N.Novgorod- 2004- p.370.

10. Батищев, Д.И. Оптимизация нестационарных задач комбинаторного типа с помощью генетических алгоритмов. / Д.И.Батищев, Е.А.Неймарк, Н.В.Старостин // Десятая национальная конференция по искусственному интеллекту с международным участием КИИ-2006 (25-28 сентября 2006г., Обнинск): Труды конференции. В 3-т. - М.: Физматлит – 2006- Т.3. - С. 976983.

11. Неймарк, Е.А. Использование структурного генетического алгоритма для оптимизации нестационарной функции. / Е.А. Неймарк //Тезисы докладов международной научно-технической конференции ИСТ-2006.– Н.Новгород, изд-во НГТУ - 2006 - с.176-177.

12. Батищев, Д.И. Применение генетических алгоритмов к решению задач дискретной оптимизации: Учебное пособие. / Д.И.Батищев, Е.А.Неймарк, Н.В.Старостин - Н.Новгород, изд-во ННГУ им. Н.И.Лобачевского, 2006. – 136с.

13. Неймарк, Е.А. Применение генетического алгоритма для решения нестационарной задачи коммивояжера. / Неймарк Е.А. // Системы обработки информации и управления: труды НГТУ.-Н.Новгород:НГТУ - 2007- Т.65.Вып.

14- С.152-155.

14. Батищев, Д.И. Оптимизация нестационарной функции с помощью генетического алгоритма, использующего представление-перестановку./ Батищев Д.И., Неймарк Е.А. //Материалы международной научно-технической конференции "Информационные системы и технологии (ИСТ-2007)".- Н.Новгород:НГТУ.- 2007, с.205-207.

Подписано в печать 3.07.2008. Формат 6084 1/16.

Бумага офсетная. Печать офсетная. Гарнитура «Таймс».

Усл. п. л. 1. Заказ № 513. Тираж 100 экз.

Отпечатано с готового оригинал-макета в типографии Нижегородского госуниверситета им. Н.И. Лобачевского.

603000, г. Н. Новгород, ул. Б. Покровская,

Pages:     | 1 | 2 ||






© 2011 www.dissers.ru - «Бесплатная электронная библиотека»