WWW.DISSERS.RU

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

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

Pages:     || 2 | 3 |

На правах рукописи

НЕЙМАРК ЕЛЕНА АЛЕКСАНДРОВНА АДАПТАЦИЯ ОПТИМАЛЬНЫХ РЕШЕНИЙ НЕСТАЦИОНАРНЫХ КОМБИНАТОРНЫХ ЗАДАЧ С ПОМОЩЬЮ ПОПУЛЯЦИОННО-ГЕНЕТИЧЕСКИХ МЕТОДОВ Специальность 05.13.18 — Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

Н.Новгород 2008

Работа выполнена на кафедре информатики и автоматизации научных исследований Федерального Агентства по Образованию «Нижегородский Государственный Университет им. Н.И.Лобачевского» Научный руководитель доктор технических наук, профессор Батищев Дмитрий Иванович Официальные оппоненты кандидат технических наук, доцент Клочков Дмитрий Павлович, член-корр. РАН, доктор физико-математических наук, профессор Флеров Юрий Арсениевич Ведущая организация Институт динамики систем и теории управления Сибирского Отделения Российской Академии Наук

Защита состоится «_» _ 2008 г. в _ часов на заседании Диссертационного Совета Д 212.166.13 при Нижегородском Государственном Университете им. Н.И.Лобачевского по адресу: 603950, Н.Новгород, пр.Гагарина, д.

23.

С диссертацией можно ознакомиться в библиотеке Нижегородского Государственного Университета им. Н.И.Лобачевского.

Автореферат разослан «_»_2008 г.

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

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

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

Пионерами построения адаптивных систем в нашей стране являются И.Л.Букатова, Л.А.Расстригин, Я.З.Цыпкин. Они предлагали алгоритмы, способные работать при отсутствии достаточной априорной информации об объекте оптимизации (управления). Важной особенностью такого подхода является возможность адаптации и самоадаптации алгоритма при накапливании информации в процессе поиска.

Введение в алгоритмы аналогов биологических и социальных процессов привело к созданию новых методов: эволюционного моделирования (Л.Фогель, А.Оуенс, М.Уолш, И.Л.Букатова), эволюционных стратегий (I.Rechenberg, H.P.Schwefel), социальных эвристик (М.Л.Цетлин), эволюционной адаптации коллективом вероятностных автоматов (Ю.И.Неймарк, Л.А.Расстригин), генетических алгоритмов (J.H. Holland, D.E. Goldberg, E. Goodman, K. A. De Jong, Z.Michalewicz, Д.И.Батищев, В.В.Емельянов, Л.А.Зинченко, В.М.Курейчик).

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

Задачи оптимизации охватывают широкий класс задач: задачи непрерывной оптимизации, дискретной оптимизации. Классические алгоритмы решения задач оптимизации ориентированы на решение статических задач (не меняющихся в процессе решения), однако задачи, возникающие на крупных производствах, в экономике и логистике, зачастую не являются стационарными. Их параметры изменяются во времени, таким образом, алгоритм, для их успешного решения, должен постоянно подстраиваться под изменяющиеся условия задачи – обладать адаптивными свойствами.

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

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

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

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

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

В соответствии с описанной целью, в диссертационной работе поставлены и решены следующие задачи.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Для тестирования и сравнения предложенных алгоритмов разработана программная система, имеющая диалоговый интерфейс.

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

Апробация результатов Материалы диссертационной работы были внедрены в учебный процесс факультета вычислительной математики и кибернетики ННГУ в 2007/учебном году при преподавании курса «Генетические алгоритмы» (лектор Е.А.

Неймарк), нашли свое отражение в учебном пособии «Применение генетических алгоритмов к решению задач дискретной оптимизации» [12], изданному в рамках Инновационной образовательной программы ННГУ.

В 2008 году программная система, составляющая прикладную часть диссертационной работы, прошла апробацию в ФГУ «ОКБМ им.

И.И.Африкантова» при решении задачи оптимальной загрузки станка ANCA RXдля изготовления и заточки режущего инструмента и в «ФНПЦ НИИИС им Ю.Е.Седакова» при решении задачи определения оптимальной последовательности выполнения проверок технологических операций при производстве изделий микроэлектроники с микронными топологическими нормами.

Результаты работы докладывались и обсуждались на Всероссийской научно-практической конференции “Компьютерная геометрия и графика” (Н.Новгород, 1998г.), VI-ом Интернациональном Конгрессе по математическому моделированию (Н.Новгород, 2004г). На научном семинаре Института динамики систем и теории управления СО РАН (Иркутск). На Международной научнотехнической конференции ИСТ-2006 (Н.Новгород), на Десятой национальной конференции по искусственному интеллекту с международным участием КИИ2006 (Обнинск), на Международной научно-технической конференции "Информационные системы и технологии (ИСТ-2006, ИСТ-2007)" (Н.Новгород), на семинарах кафедры информатики и автоматизации научных исследований факультета ВМК ННГУ (Н.Новгород).

Исследования по теме диссертационной работе проводились в рамках бюджетной темы «Математическое моделирование и создание новых методов анализа динамических систем и систем оптимизации».

Структура и объем работы Работа состоит из пяти глав, введения, заключения, списка литературы и приложений. Общий объем работы составляет 136 страниц. Список литературы составляет 149 наименований.

Публикации По теме диссертации опубликовано 14 работ (в том числе 7 статей, 3 из которых опубликованы в научных журналах, рекомендованных ВАК, и одно учебное пособие). Список публикаций приведен в конце автореферата.

Краткое содержание работы Задача нестационарной комбинаторной оптимизации (1) состоит в [0,T*] нахождении в каждый момент времени из промежутка наблюдения такого x* решения, из области допустимых решений D(t) (N –мощность D(t)), которое i доставляет максимум критерия Q(x,t), то есть состоит в отслеживании движения оптимума.

i Q(x*,t) = maxQ(x,t) i x D(t) 0 <| D(t) | N <,, где t [0,T*],T* < (1) 1 2 N xi = (хi, xi... xi ), D(t) = (x, x,... x ) 1 n Примем, что изменения среды дискретны и цикличны, тогда критерий можно записать в виде декомпозиции функций, не зависящих от времени (2).

Q1(x), t [0,1] Q2 (x), t [1,1 + ] Q(x,t) = (2)...

Q (x), t [T -,T ] M M -Промежуток наблюдения i =1, M называется отрезком постоянства i задачи, М – число различных стационарных функций, появляющихся за время наблюдения Т (T T *), являющееся периодом задачи. Очевидно, что в общем случае Т = T *.

Модель нестационарной задачи о ранце приведена в (3) и нестационарной задачи коммивояжера в (4).

n x i Q(x,t) = vi (t) max i= n x wi (t) Wmax (t) i i= (3) xi {0,1}, i = 1, n t [0,T*],T* < 1,если предмет с номеромi положенв ранец xi = 0,иначе vi (t) wi (t) xi - ценность, - вес предмета в момент времени t.

n (t) > Wmax (t), 0 < wi (t) Wmax (t), vi (t) > 0, i = 1, n, t [0,T*] wi i=Wmax(t) Wmax (t) > 0, t [0,T*] - главное весовое ограничение в момент времени t,.

n n (t)xij min cij Q(x,t) = i-1 j= n = 1, j = 1,n xij i= n = 1, i = 1, n xij j= (4) x {0,1}, i = 1,n ij - u + nxij n -1,ui 0, i, j = 2, n (*) ui j t [0,T*],T* < 1,если из городас номеромi коммивояжер переходит xi = в город j 0,иначе cij (t) - цена перехода из города i в город j, cij (t) 0, cij (t) = c (t), i, j = 1, n, t [0,T*].

ji Условие (*) гарантирует наличие единственного цикла.

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

Лучший Худший Средний Поколения Рис. 1. Адаптация оптимального решения на примере задачи о ранце.

На Рис. 1 приведен график адаптации оптимального решения на примере задачи о ранце. В этой задаче отрезок постоянства задачи равен тридцати поколениям популяционно-генетического алгоритма, период задачи T – шестидесяти поколениям. Чем выше приспособленность особи, тем лучше соответствующее ей решение. На графике видно как приспособленность лучшей особи изменяется в зависимости от текущего состояния среды, как происходит рост приспособленности после смены состояния среды и достижение оптимального значения на отрезках постоянства длиной.

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

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

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

Pages:     || 2 | 3 |






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