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

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

НЕЙМЛРК ЕЛЕНЛ АЛЕКСАНДРОВЫ,

АДАПТАЦИЯ ОПТИМАЛЬНЫХ РЕШЕНИЙ НЕСТАЦИОНАРНЫХ КОМБИНАТОРНЫХ ЗАДАЧ С ПОМОЩЬЮ ПОПУЛЯЦИОННО-ГЕНЕТИЧЕСКИХ МЕТОДОВ

Специальность 05 13 18 — Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Н Новгород 2008

003445648

Работа выполнена на кафедре информатики и автоматизации научных исследований Федерального Агентства по Образованию «Нижегородский Государственный Университет им Н И Лобачевского»

Научный руководитель доктор технических наук,

профессор Батищев Дмитрий Иванович

Официальные оппоненты кандидат технических наук,

доцент

Клочков Дмитрий Павлович,

член-корр РАН, доктор физико-математических наук, профессор Флеров Юрий Арсениевич

Ведущая организация Институт динамики систем и теории управле-

ния Сибирского Отделения Российской Академии Наук

Защита состоится <о?5» 0£-ЛаЯ 2008 г в _ часов на заседании

Диссертационного Совета Д 212 166 13 при Нижегородском Государственном Университете им Н И Лобачевского по адресу 603950, Н Новгород, пр Гагарина, д 23

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

Автореферат разослан

2008 г

Ученый секретарь диссертационного совета кандидат физико-математических наук, ^/ //)

доцент -Н} Савельев Владимир Петрович

Актуальность

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Материалы диссертационной работы были внедрены в учебный процесс факультета вычислительной математики и кибернетики ННГУ в 2007/2008 учебном году при преподавании курса «Генетические алгоритмы» (лектор Е А Ней-марк), нашли свое отражение в учебном пособии «Применение генетических алгоритмов к решению задач дискретной оптимизации» [12], изданному в рамках Инновационной образовательной программы ННГУ

В 2008 году программная система, составляющая прикладную часть диссертационной работы, прошла апробацию в ФГУ «ОКБМ им И И Африкантова» при решении задачи оптимальной загрузки станка ANCA RX7 для изготовления и заточки режущего инструмента и в «ФНПЦ НИИИС им Ю Е Седакова» при решении задачи определения оптимальной последовательности выполнения проверок технологических операций при производстве изделий микроэлектроники с микронными топологическими нормами

Результаты работы докладывались и обсуждались на Всероссийской научно-практической конференции "Компьютерная геометрия и графика" (Н Новгород, 1998г), VI-ом Интернациональном Конгрессе по математическому

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

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

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

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

Задача нестационарной комбинаторной оптимизации (1) состоит в нахождении в каждый момент времени из промежутка наблюдения [0,Г*] такого решения х*, из области допустимых решений 0(1) (М -мощность 0(0), которое доставляет максимум критерия ()(х ,/) то есть состоит в отслеживании движения оптимума

0 <10(01< N < 00, ,где

/е[0,Г*],Г*<°о 0)

У = (х',,х'г х^), £>(/) = (х',х\ х") Примем, что изменения среды дискретны и цикличны, тогда критерий можно записать в виде декомпозиции функций, не зависящих от времени (2)

й(4'с[0, г,]

е2(х), *с[г,,г,+г2] <2м(х),1с[Т-гм_{,Т]

Промежуток наблюдения г, < = 1 ,м называется отрезком постоянства задачи, М - число различных стационарных функций, появляющихся за время наблюдения Т (Т<Т*), являющееся периодом задачи Очевидно, что в общем случае Т — Т*

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

0(х, /) = V х, V, (/) -» шах

1=1

(3)

х, =

х, е {о,1}, 1 = 1,11 I е[0,Т*],Т* «я \,если предмет с номером I положен в ранец [О, иначе

у, (0- ценность, ^,(0- вес предмета х1 в момент времени I ¿™,(0> ^ (0, 0 < (0 ^ (О, V, (0 > о,» = ¡Я V/ е [0,7*]

1=1

и) - главное весовое ограничение в момент времени I (7) > 0, V/ е [0,Г*]

__п п

>-1 7=1 ¿>„=1 ,Уу=й

7=1

Хи е {0,1}, I = ¡¡п

и1 -и +пХу <п-1,и1 >0, = 2,л (*) I е [0,Г*],Г* < со 1 ,если из города с номером ¡коммивояжер переходит

в город у 0, иначе

сц (/) - цена перехода из города; в город у, сц (О > о, С0 (0 = (0,1, у = й, V/ е [0, Т*] Условие (*) гарантирует наличие единственного цикла

(4)

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

Приспособленность а 8 8 § § <---►

/ ф * ' V...... . ..........Лучший 1 / " " -Худший _ -Средний

1 - - *

; /

0 30 60

Рис. 1. Адаптация оптимального решении на примере задачи о ранце.

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

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

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

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

Популяционно-генетические алгоритмы в процессе поиска работают не с решениями исходной задачи, а с их кодировками Для того чтобы перейти от задач дискретной оптимизации к задаче генетического поиска, все решения из области допустимых решений D кодируются в виде строк в алфавите В, в результате получаем пространство кодировок S (также называемое пространством поиска) Значения ""ритерия Q переводятся при помощи некоторого отображения, сохраняющего те же отношения предпочтения между кодировками, что и между соответствующими им решениями, в R* - получаем функцию приспособленности p{s) (критерий сравнения кодировок)

От выбора способа кодирования во многом зависит успех поиска решения О вычислительном эксперименте для сравнения эффективности различных методов кодирования для задачи коммивояжера будет рассказано ниже

Рост приспособленности популяции в генетическом алгоритме происходит за счет «построения» генотипа из лучших аллелей (строительных блоков) Holland в фундаментальной теореме1 показал, что количество строительных блоков с высокой приспособленностью в популяции с течением времени будет расти экспоненциально Эта теорема подтверждает теорию Докинза2, в которой предполагается, что при естественном отборе соревнование происходит не на уровне особей, а на уровне генов Таким образом, выживают наиболее приспособленные аллели генов

В генетическом алгоритме при переходе из поколения в поколение происходит вытеснение менее приспособленных признаков Rudolph3 в своей работе показал, что при сохранении лучшей особи при переходе в следующее поколение (элитарная селекция), прог/есс генетического поиска, как последовательность случайных величин, сходится почти наверное к оптимальному решению

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

' Holland, J Н , Adaptation m Natural and Artificial Systems/ J H Holland - Ann Arbor University of Michigan Press, 1975

2 Докипз P Эгоистичный ген / P Докимз- Пер С англ Пер с англ Н О Фоминой - М Мир- 1993 -316с

3 Rudolph, G Convergence Analysis of Canonical Genetic Algorithms / G Rudolph // ICEE Trans on Neural Networks, special issue on Evolutionary Computation, vol 5, no 1, pages 96-101, Jan 1994

гипермутации4 искусственно увеличивает генетическое разнообразие при смене состояния среды, методы с диплоидным5 и структурным6 представлением генотипа относятся к методам с неявным использованием памяти, в то время как метод с использованием базы опыта [2] явно использует внешнюю память

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

Для сравнения эффективности алгоритмов в динамической среде важно знать следующее его точность, его устойчивость (6), скорость реакции на изменения

-.-(О _F{best%)-Mm?

~ МахГ-МтГ {)

stab(,) = тах{0,асс{1-1) -ассю} (6)

Для тестовых задач на максимум точность можно задавать формулой (5), где F(best<_'}) - лучшее найденное решение в поколении р', Maxf,Mmf - максимальное и минимальное значение критерия в текущий момент времени t В реальных задачах Мах)0, Мт^ не известны, в этом случае их можно заменить верхней и нижней оценкой соответственно

Генетические алгоритмы работают с кодировками решений исходной задачи Часто выбор способа кодирования обусловлен особенностями задачи Одно из правил выбора метода кодирования основано на сохранении близости решений при кодировании То есть если для решений х\ л2, .х* е D выполняется d{x\ x*)>d(x', х'), где d(y!, У) - расстояние между решениями У , то и для кодировок s',s!,j!eS, s' = ),г = 1,3 должно выполняться ¿(s1,s2) > S(s',s}), где S(s',sJ)- расстояние между кодировками Введем понятие расстояния для бинарных векторов и перестановок

4 Cobb H An Investigation into the Use of Hypermutation as an adaptive Operator in Genetic Algorithm Having Continuous, Time-Dependent Nonstationary Environments / H Cobb //Naval Research Laboratory Memorandum Report 6760 (1990)

5 Smith R E Diploidy and Dominance in Artificial Genetic Search /RE Smith, D E Goldberg // Complex Systems, V 6, 1992, ph 251—285

6 Dasgupta,D (1992) SGA A Structured Genetic Algorithm / D Dasgupta, D R McGregor //Technical report no IK.BS-8-92, University of Strathclyde

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

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

Для гарантии получения допустимых кодировок (кодировок, которым соответствуют решения из области D) существуют различные методы

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

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

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

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

7 Сигал, И X Введение в прикладное дискретное программирование / И X Смгал, А П Иванова - 2007г - М Физматлит 304с

8 Lin S An effective heuristic algorithm for the traveling salesman problem / S Lin, В W Kermghan //Oper Res, 1973,v 21,#2,p 498-516

шей размерности - непересекающиеся регионы, число регионов 2 <М <. В

каждом регионе при помощи популяционно-генетического метода находится минимальный гамильтонов путь, размерность каждой из этих задач меньше исходной 3 < N, < N,i = 1, А/, где N - размерность исходной задачи, /V, - размерность регионов Гамильтоновы пути, являющиеся решением каждой подзадачи, «сшиваются», образуя решение исходной задачи (гамильтонов цикл) При этом не только поиск решения подзадач, но и само разбиение на подзадачи происходит при помощи генетического алгоритма

Для реализации этого подхода предложено использование ярусного генотипа, в верхнем ярусе находятся регионы, а в нижнем города из этих регионов Для ярусного представления разработаны специальные операторы, гарантирующие допустимое разбиение на регионы и построение гамильтонова цикла Метод был опробован на известных тестовых задачах (в частности 01iver's-30, Eilon's-50, Eilon's-759), на них получены результаты [6], повторяющие лучшие известные

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

В настоящей работе был предложен метод с использованием базы опыта для создания начальной популяции[3] В основе этого метода лежит использование внешней памяти для запоминания и дальнейшего использования решений, найденных при сходных состояниях среды Этот метод хорошо применяется при малом количестве различных состояний и их периодическом повторении Метод с использованием базы опыта позволяет продолжать процесс адаптации решений, используя полученные ранее решения при аналогичных параметрах внешней среды

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

Известные в литературе диплоидные алгоритмы используют бинарный алфавит кодирования В диссертации предлагается оригинальный диплоидный гене-

9 Oliver I A study of permutation crossover operators on the traveling salesman problems / I Oliver, D Smith, J R Holland //Proc of the Second International Conf on Genetic Algorithms, 1987,p 224-230

тический алгоритм, основанный на перестановочном кодировании генотипа [13] Для него описаны варианты операторов кроссовера и мутации Этот алгоритм специально разработан для нестационарной задачи коммивояжера

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

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

Рис 2. Структура программного комплекса.

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

Для сравнения эффективности различных алгоритмов на задаче о ранце рассматривался класс задач (7), в которых от времени зависит только главное весовое ограничение ^„„(0 Рассматривались два случая с двумя и с четырьмя различными состояниями среды Параметрами тестовой задачи является размерность задачи - 30, 100 и 650 предметов, количество различных весовых ограничений - два весовых ограничения, составляющих 50%и 90% от суммарного веса всех предметов, и четыре, составляющих 25%, 50%, 75% и 90% от суммарного веса всех предметов, порядок следования ограничений (для 4х ограничений)

X тах

1=1

^«.о (7)

1=1

х{ е {0,1}, I = Т7Й

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

Таблица 1 Задача о ранце размерности 650; два весовых ограничения.

среднее число вычислений стабильность средняя точность

Подход с памятью 171571 0 001312 0 9562

Структурный подход 1719 29 0 00264 0 8515

С модификацией 1715 71 0 002683 0 8365

Диплоидный подход 171571 0 002395 0 7375

Гипермутация вероятность 0 1 1715 71 0 012458 0 4556

Гипермутация вероятность 0 5 1785 36 0 012124 0 4482

Метод штрафов 171571 0 013798 0 4432

Подходы сравнивались по точности, среднему количеству затраченных на поиск оптимума вычислений и стабильности Результаты эксперимента (Таблица 1) показали, что подход с использованием базы опыта (в таблице обозначен «Подход с памятью») имеет лучшие результаты эффективности, что обуславливается продолжением адаптации при повторении состояния среды Заметим, что этот алгоритм использует в качестве базового гаплоидное представление с применением штрафов для недопустимых решений («Метод штрафов»), но по показателям точности превосходит базовый алгоритм более чем в два раза

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

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

Диплоидный подход занимает четвертое место по показателям эффективности На задаче с двумя ограничениями точность алгоритма 0 7375, с четырьмя ограничениями - 0 5046, Такое поведение алгоритма соответствует его особенностям смена доминантности позволяет из одного генотипа получить два различных решения Остальные подходы на задачах о ранце имеют точность ниже 50%

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

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

среднее число вычислений стабильность средняя точность

Подход с базон опыта 96 50 0 000757 0 9904

Диплоидный алгоритм 536 38 0 001174 0 8993

Структурный алгоритм 573 50 0 014067 0 8868

Гипермутацня вероятность 0 5 676 97 0018017 0 8659

Гмпермутацня вероятность 0 1 650 72 0 018248 0 8551

Гаплоидный алгоритм 663 53 0 018557 0 8531

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

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

ности 30,100 и 1000 предметов Тесты проводились для разных отрезков постоянства

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

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

размерность 1000

Ограничение Оценка Метод ветвей и границ Метод динамического программирования Генетический алгоритм

0 25 средняя точность 0 9986 Л/А 0 8258

коч-во вычислений 1253 1126877 1000

05 средняя точность 0 9995 Л/А 0 9026

кол-во вычислений 3103 3235522 1000

0 75 средняя точность 0 9998 Л/А 0 9661

кол-во вычислений 121963 6074444 1000

09 средняя точность 0 9997 Л/А 0 9942

кол-во вычислений 83676 8132412 1000

Вторая серия экспериментов (Таблица 4,Таблица 5) была проведена на нестационарной задаче о ранце, в качестве меры отрезка постоянства рассматривалось количество оценок решения В этой серии сравнивались метод с использованием базы опыта и метод ветвей и границ Для метода ветвей и границ справедливо чем больше отрезок постоянства, тем меньше вероятность найти оптимальное решение для больших ограничений, поскольку эти ветви будут исключены из рассмотрения при работе алгоритма на меньших ограничениях Точность классического алгоритма падает при увеличении отрезка постоянства, и если весовые ограничения последовательно не увеличиваются В то время как точность генетического алгоритма не зависит от отрезка постоянства и порядка следования задач и остается достаточно высокой (в среднем 0 96)

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

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

зависимости от отрезка постоянства

Отрезок постоянства 30 50 70 100 150 200

Метод ветвей и границ 0 8407 0 8187 0 7717 0 6966 0 4924 0 4843

Генетический алгоритм 0 9511 0 9539 0 9559 0 9557 0 9624 0 9706

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

Возрастание весовых ограничений Убывание весовых ограничений

Метод ветвей и границ 0 7295 0 6400

Генетический алгоритм 0 9504 0 9679

Для каждого запуска вычислялось отношение лучшего найденного решения к верхней 1"'у{/ррег)11 к нижней оценке () средние значения по всем запускам приведены в таблице (см Таблица 6) В таблицу также занесено «Максимальное число ожидающих ОТК», которое соответствует максимальной размерности матрицы переналадок в ходе поиска решения Верхняя оценка {Upper) получена построением гамильтонова пути методом самого дешевого включения, нижняя (Low) как сумма констант приведения по строкам и столбцам матрицы переналадок

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

Число ОТК 70 150 500

Среднее отношение ^ь"^/цррСГ 0 51 0 61 0 61

Среднее отношение 1 04 1 00 1 03

Максимальное число ожидающих ОТК 54 113 239

Из таблицы (Таблица 6) видно, что алгоритм дает решения близкие к нижней оценке, которая в общем случае является недостижимой, что говорит о хорошем качестве получаемых решений

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

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

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

Среднее отношение ^b'"/iow Среднее отношение ^h"^/{jppCr

1 02 0 97

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

Количество дополнительных заявок Среднее отношение Пь,„/ /Low Среднее отношение Пьы/ /Upper

10 1 03 0 96

5 1 03 0 96

Задача оперативного управления сводится к составлению плана загрузки уникального оборудования на рабочую смену с учетом поступления дополнительных заявок (до десяти за смену)

В качестве верхней оценки {Upper) выступает решение линейной задачи о ранце, нижней (Low) - решение дискретной задачи по методу Данцига Полученные результаты приведены в таблицах (Таблица 7, Таблица 8)

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

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

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

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

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

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

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

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

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

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

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

3 Неймарк, Е А Решение нестационарной задачи о ранце при помощи генетического алгоритма / Е А Неймарк //Вестник ННГУ - 2006 - Вып 3(32) с 133137

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

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

5 Батищев, Д И Вопросы визуализации при решении экстремальных задач с помощью ГА / Д И Батищев, С А Исаев, Н В Старостин, Е А Неймарк, Е К Ре-мер //Тезисы докладов Всероссийская научно-практической конференции "Компьютерная геометрия и графика" - Н Новгород, НГТУ- 1998г, стр 101102

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

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

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

9 Neumark, Е 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г, Обнинск) Труды конференции ВЗ-т -М Физматлит- 2006- Т 3 - С 976-983

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

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

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

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

Подписано в печать 3 07 2008 Формат 60x84 1/16 Бумага офсетная Печать офсетная Гарнитура «Тайме» Уел п л 1 Заказ №513 Тираж 100 экз

Отпечатано с готового оригинал-макета в типографии Нижегородского госуниверситета им Н И Лобачевского 603000, г Н Новгород, ул Б Покровская, 37

ВВЕДЕНИЕ.

1 ПОСТАНОВКА ЗАДАЧИ НЕСТАЦИОНАРНОЙ ДИСКРЕТНОЙ ОПТИМИЗАЦИИ.

1.1 Нестационарные задачи комбинаторного типа.

1.2 Трудности решения задач комбинаторного типа.

1.3 Обзор методов оптимизации нестационарных задач.

1.4 Критерии оценки эффективности алгоритмов для решения задач в динамических средах.

2 ГАПЛОИДНЫЙ ГЕНЕТИЧЕСКИЙ АЛГОРИТМ ДЛЯ РЕШЕНИЯ НЕСТАЦИОНАРНЫХ ЗАДАЧ ДИСКРЕТНОЙ ОПТИМИЗАЦИИ.

2.1 Переход от задачи дискретной оптимизации к задаче поиска, генетический поиск.

2.2 Основные определения и структура генетического алгоритма

2.3 Операторы генетического алгоритма.

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

2.5 Применение генетического алгоритма к решению задачи коммивояжера большой размерности.

2.6 Гаплоидный генетический алгоритм с гипермутацией.

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

3 ТЕОРЕТИЧЕСКОЕ ИССЛЕДОВАНИЕ ПОВЕДЕНИЯ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ.

3.1 Шаблоны сходства генотипов.

3.2 Основные теоретические результаты.

3.3 Время сходимости и время захвата.

3.4 Применение цепей Маркова для исследования генетического дрейфа в генетических алгоритмах.

4 ГЕНЕТИЧЕСКИЙ АЛГОРИТМ С ДИПЛОИДНЫМ ПРЕДСТАВЛЕНИЕМ ГЕНОТИПА ДЛЯ РЕШЕНИЯ НЕСТАЦИОНАРНЫХ ЗАДАЧ.

4.1 Диплоидная хромосома. Понятие доминирования.

4.2 Операторы кроссовера и мутации для диплоидного представления.

4.3 Диплоидные алгоритмы с доминированием и без.

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

4.5 Метод, основанный на структурном представлении генотипа

5 ВЫЧИСЛИТЕЛЬНЫЙ ЭКСПЕРИМЕНТ.

5.1 Методы адаптации нестационарных функций.

5.2 Описание программного комплекса.

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

5.4 Сравнение популяционно-генетического алгоритма с классическими алгоритмами на задаче о ранце.

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

5.6 Использование популяционно-генетического алгоритма в задаче загрузки уникального оборудования.

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

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

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

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

Сейчас одним из широко известных подходов являются эволюционные алгоритмы. Термин «эволюционные алгоритмы» был введен Михалевичем (Michalewicz) для обозначения всех алгоритмов, в основе которых лежат принципы популяционной генетики. Наиболее известными и развиваемыми сейчас представителями эволюционных алгоритмов являются эволюционное программирование [57], генетические алгоритмы [95], эволюционные стратегии [117,121] и генетическое программирование [99].

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

• отказ от использования истории и перезапуск алгоритма с нуля может быть очень затратным по времени;

• изменение условий задачи может быть не обнаружено совсем или в течение достаточно долгого периода времени;

• если изменения достаточно малы, то и решения могут отличаться незначительно;

• невозможность перезапуска алгоритма при каждом изменении.

Эволюционные алгоритмы уже достаточно хорошо зарекомендовали себя как в оптимизации сложных стационарных задач [1, 2, 11, 32, 67, 73, 77, 83, 88, 95, 98 и др.], так и для принятия решения или предсказания в условиях недостаточной информации [15,35,36,46,74,79,89,91,112,114,125,129,136]. Широкое использование эволюционных алгоритмов для решения задач оптимизации обусловлено их адаптивными свойствами.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Материалы диссертационной работы были внедрены в учебный процесс факультета вычислительной математики и кибернетики ННГУ в 2007/2008 учебном году при преподавании курса «Генетические алгоритмы» (лектор Е.А. Неймарк), нашли свое отражение в учебном пособии «Применение генетических алгоритмов к решению задач дискретной оптимизации» [11], изданному в рамках Инновационной образовательной программы ННГУ.

В 2008 году программная система, составляющая прикладную часть диссертационной работы, прошла апробацию в ФГУ «ОКБМ им. И.И.Африкантова» при решении задачи оптимальной загрузки станка ANCA RX7 для изготовления и заточки режущего инструмента. А также в «ФНПЦ НИИИС им Ю.Е.Седакова» при решении задачи определения оптимальной последовательности выполнения проверок технологических операций при производстве изделий микроэлектроники с микронными топологическими нормами.

Результаты работы докладывались и обсуждались на Всероссийской научно-практической конференции "Компьютерная геометрия и графика"

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

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

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

По теме диссертации опубликовано 14 работ (в том числе 7 статей, 3 из которых опубликованы в сборниках, рекомендованных ВАК, и одно учебное пособие). Основные результаты диссертации опубликованы в следующих работах: [6,7,9,13,36,38,39]. Краткое содержание работы

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

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

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

разделить на несколько классов:

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

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

В главе 2 даются основные понятия генетического алгоритма на примере генетического алгоритма с гаплоидным представлением генотипа.

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

В §2.2 даны основные определения и понятия генетического алгоритма. В §2.3 приводятся его основные операторы: формирование начальной популяции, кроссовер, мутация, селекция.

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

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

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

Поскольку эволюционный алгоритм в стандартной реализации, не дает хороших результатов, в основном из-за свойства преждевременной сходимости, поэтому для решения нестационарной задачи было рассмотрено несколько подходов на основе эволюционного алгоритма: алгоритм с явным использованием памяти (§2.7), алгоритм с гипермутацией (§2.6), гибридные алгоритмы (§2.4.2, §2.4.4).

В §2.6 описан метод с гипермутацией, этот метод основан на повышении вероятности мутации в популяции при обнаружении изменения состояния внешней среды.

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

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

В §3.1 вводится понятие схемы (Schema). Схема - это шаблон, представленный строкой длины L, состоящей из символов {0,1,*}, который описывает сходство генотипов в определенных позициях. Понятие шаблона является основным в теоретическом исследовании поведения генетических алгоритмов. Вводится понятия средней приспособленности шаблона и средней наблюдаемой приспособленности.

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

В следующих параграфах §3.3, §3.4 приводятся исследования сходимости генетического алгоритма по одному признаку. Рассматривается процесс изменения пропорции аллелей в одном локусе популяции при переходе в следующее поколение. Выводятся рекуррентные соотношения для изменения пропорции аллелей; формулы, отражающие время сходимости и захвата признаком популяции.

В главе 4 приводятся основные понятия, операторы и алгоритмы для диплоидного представления генотипа.

В §4.1 вводится понятия диплоидной хромосомы и понятия доминирования, при помощи которого диплоидный генотип преобразуется в фенотип особи.

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

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

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

В главе 5 приводятся результаты вычислительного эксперимента.

В §5.1 описываются методы, применяемые в ходе вычислительного эксперимента: структурный алгоритм, диплоидный алгоритм, гаплоидный алгоритм с гипермутацией и две модификации гаплоидного генетического алгоритма для задачи о ранце.

В §5.2 приводится описание программного комплекса, использовавшегося для тестирования и решения практических задач.

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

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

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

В §5.6 приводится постановка задачи загрузки уникального оборудования и результаты поиска оптимального решения этой задачи. Основные результаты

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

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

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

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

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

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

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

6 Заключение

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

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

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

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

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

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

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

Разработана и исследована многоуровневая модель хромосомы для решения задачи коммивояжера большой размерности, обладающая адаптивной структурой, позволяющая понизить размерность решаемой задачи. Популяци-онно-генетический алгоритм, использующий ярусную модель хромосомы, был проверен на известных тестовых примерах Oliver's -30, Eilon's-50 и Eilon's-75. С его помощью удалось построить разбиение на регионы и найти решения, которые совпадают с лучшими известными решениями, для каждой задачи.

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

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

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

1. Батищев, Д.И. Генетические алгоритмы решения экстремальных задач: Учебное пособие./ Д.И. Батищев; под ред. Львовича Я.Е.- Воронеж, 1995.64 с.

2. Батищев, Д.И. Методы оптимального проектирования./ Д.И.Батищев М.: Радио и связь, 1984 - 248 с.

3. Батищев, Д.И. Вычислительная сложность экстремальных задач переборного типа: Учебное пособие./ Батищев Д.И., Коган Д.И. Н.Новгород, ННГУ, 1994, 111 с.

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

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

6. Ю.Батищев, Д.И. Оптимизация нестационарных задач комбинаторного типа с помощью генетических алгоритмов. / Д.И.Батищев, Е.А.Неймарк,

7. Н.В.Старостин // Десятая национальная конференция по искусственному интеллекту с международным участием КИИ-2006 (25-28 сентября 2006г., Обнинск): Труды конференции. В 3-т. Т.З. М.: Физматлит, 2006 - С. 976-983.

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

9. Беллман, Р. Динамическое программирование./ Р. Беллман пер. с англ. И. М. Андреевой и др. ; под ред. Н. Н. Воробьева - М.: Издательство иностранной литературы , 1960 - 400 с.

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

11. Букатова, И.Л. Эвоинформатика: теория и практика эволюционного моделирования./ И.Л.Букатова, Ю.И.Михасев, A.M. Шаров М.:Наука- 1991 - 206 с.

12. Букатова, И.Л. Эволюционное моделирование и его приложения./ И.Л. Бука-това М: Наука, 1979 - 232 с.

13. Буш, Р. Стохастические модели обучаемости./ Р.Буш, Ф.Мостеллер ; Перев. с англ.- М.: Физматгиз 1962 .- 481 с.

14. Генетические алгоритмы, искусственные нейронные сети и проблемы виртуальной реальности / Г. К. Вороновский, К. В. Махотило, С. Н. Петрашев, С. А. Сергеев.— X.: ОСНОВА, 1997.— 112 с.

15. Гринченко, С.Н. Системная память живого./ С.Н. Гринченко Москва: ИПИРАН, Мир.- 2004.

16. Гери, М. Вычислительные машины и трудно решаемые задачи ./ М.Гери , Д.Джонсон Пер. С англ.- М: Мир - 1982 - 416 с.

17. Дарвин, Ч. Сочинения: в 3 т./ Ч.Дарвин ; Перев. с англ.- Изд-во АН СССР, Москва-Зт, 1939.

18. Докинз, Р. Эгоистичный ген./ Р.Докинз- Пер. С англ. Пер. с англ. Н.О.Фоминой М: Мир, 1993 - 316 с.

19. Дубинин, Н.П. Избранные труды. В 4х томах. Т.1.: Проблемы гена и эволюции./ Н.П. Дубинин М: Наука - 2000 - 546 с.

20. Дубинин, Н. П. Некоторые проблемы современной генетики: РАН. Ин-т общей генетики им. Н. И. Вавилова./ Н.П. Дубинин М.: Наука - 1994 - 223 с.

21. Дюбин, Г.Н. Жадные алгоритмы для задачи о ранце: поведение в среднем / Г.Н.Дюбин , А.А. Корбут // Сибирский журнал индустриальной математики- 1999- Т. 2, № 2 (4). С. 68-93.

22. Емельянов, В.В. Теория и практика эволюционного моделирования./ В.В.Емельянов, В.М.Курейчик, В.В. Курейчик М.:ФИЗМАИЛИТ- 2003 -432 с.

23. Ивахненко, А.Г. Самообучающиеся системы распознавания и автоматического управления./А.Г. Ивахненко Киев.: Техника -1969 .- 392 с.

24. Корбут, А.А. Дискретное программирование./ А.А.Корбут, Ю.Ю. Финкель-штейн М: Наука, 1969 - 368 с.

25. Кристофидес, Н. Теория графов. Алгоритмический подход. / Н.Кристофидес;

26. Пер. с анг. М.: Мир, 1978. - 432 с.

27. Курейчик, В.М. Эволюционные методы решения оптимизационных задач: Монография./В.М.Курейчик -Таганрог: изд-во ТРТУ 1999 -95с.

28. Меламед, И.И. Задача коммивояжера. Вопросы и теория./И.И.Меламед, О.И. Сергеев, И.Х. Сигал //АиТ 1989 - №9, С.3-33 - №10-С.З-29- №11-С.З-26.

29. Миллер, Б.М. Теория случайных процессов в примерах и задачах./ Б.М.Миллер, А.Р. Панков-М.:ФИЗМАИЛИТ, 2002 -302с.

30. Мухин, В.И. Автоматная оптимизация с эволюционной адаптацией. / В.И.Мухин, Ю.И.Неймарк, Е.И. Ронин //Проблемы случайного поиска. -Рига, вып.2 ,2005 С. 83-98.

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

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

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

34. Неймарк, Е.А. Решение нестационарной задачи о ранце при помощи генетического алгоритма. / Е.А. Неймарк //Вестник ННГУ. Вып.3(32), 2006 -С. 133137

35. Неймарк, Ю.И. Динамические системы и управляемые процессы./ Ю.И.Неймарк М.: Наука, 1978 - 336 с.

36. Неймарк, Ю.И. Динамические модели теории управления. / Ю.И.Неймарк, Н.Я.Коган, В.П.Савельев М.: Наука, Главная ред. Физико-математической литературы , 1985 - 400 с.

37. Неймарк, Ю.И. Новые технологии применения метода наименьших квадратов. ./ Ю.И.Неймарк, Л.Г. Теклина -Н.Новгород :Изд-во ННГУ, 2003 196 с.

38. Пападимитриу, X. Комбинаторная оптимизация: Алгоритмы и сложность./

39. Х.Пападимитриу, К.Стайглиц М.: Мир, 1985 - 510 с.

40. Половинкин, А.И. Алгоритм поиска глобального экстремума при проектировании инженерных конструкций./ А.И. Половинкин // АиТ №1, 1975 С.88-103.

41. Популяционно-генетический подход к решению задач покрытия множества./ Д.И.Батищев, В.Е.Костюков, Н.В.Старостин, А.И.Смирнов Н.Новгород , ННГУ, 2004-152 с.

42. Растригин, JI.A. Адаптация сложных систем./ JI.A. Растригин Рига: Зинатне, 1981 - 376 с.

43. Растригин, JI.A. Адаптивные компьютерные системы./ JI.A. Растригин М: Знание, 1987-60 с.

44. Растригин, JI.A. Адаптация случайного поиска./ JI.A. Растригин, К.К.Рипа, Г.С.Тарасенко Рига: Зинатне , 1978 - 239 с.

45. Рейнгольд, Э. Комбинаторные алгоритмы. Теория и практика./ Э.Рейнгольд, Ю.Нивергельт, Н.Део Пер. с англ. Е.П. Липатова под ред. В.Б. Алексеева,- М.: Мир, 1980 - 476 с.

46. Семевский, Ф.Н. Математическое моделирование экологических процессов. / Ф.Н. Семевский, С.М. Семенов Л: Гидрометеоиздат -1982 - 280 с

47. Семенов, М.А. О подходе к доказательству сходимости эволюционных методов./ М.А.Семенов, Д.А. Теркел // Перспективы развития вычислительных систем. Рига: РПИ, 1985 С.92-102.

48. Сигал, И.Х. Алгоритм приближенного решения задачи коммивояжера большой размерности и его вычислительная реализация. / И.Х. Сигал //ЖВМ и МФ , т.27, №8, 1987 с.1145-1153.

49. Сигал, И.Х. Введение в прикладное дискретное программирование./ И.Х. Сигал, А.П. Иванова, М. Физматлит, 2007 304с.

50. Сигал, И.Х. Декомпозиционный подход к решению задачи коммивояжера большой размерности и некоторые его приложения / И.Х. Сигал // Изв. АН СССР. Техническая кибернетика, №6, 1990 С.143-155.

51. Сигал, И.Х. Задача коммивояжера большой размерности. / И.Х. Сигал -М: ВЦ АН СССР, 1968 -32с.

52. Сигал, И.Х. Задача о рюкзаке: теория и вычислительные алгоритмы. Учебное пособие. / И.Х. Сигал М.: МИИТ , 1999 - 270 с.

53. Турчин, В.Ф. Феномен науки: Кибернетический подход к эволюции./ В.Ф. Турчин -Изд. 2-е М.: ЭТС. 2000 — 368 с.

54. Феллер, В. Введение в теорию вероятностей и ее приложения. Т.1. / В.Феллер М.: Мир- 1984 - 528 с.

55. Феллер, В. Введение в теорию вероятностей и ее приложения. Т.2. / В.Феллер М.: Мир- 1984 - 752 с.

56. Фогель, JI. Искусственный интеллект и эволюционное моделирование./ Л.Фогель, А.Оуэне, М.Уолш ; Пер. с англ. М.:Мир, 1969 -230 с.

57. Ху, Т.Ч. Комбинаторные алгоритмы / Т.Ч.Ху, М.Т. Шинг Пер. с англ. -Нижний Новгород: Изд-во Нижегородского госуниверситета им.Н.И.Лобачевского , 2004 - 330 с.

58. Цетлин, М.Л. Исследования по теории автоматов и моделированию биологических систем./ М.Л. Цетлин М.: Наука, 1969 - 316с.

59. Цыпкин, Я.3. Адаптация и обучение в автоматических системах./ Я.З. Цып-кин М.: Наука. Гл. ред. физ.-мат. лит., 1968 - 400 с.

60. Цыпкин, Я.З. Адаптивные алгоритмы оптимизации при априорной неопределенности./Я.З. Цыпкин //АиТ 1979- №6- С.94-108.

61. Четвериков, С.С. Проблемы общей биологии и генетики. / С.С. Четвериков-Новосибирск, 1983 273 с.бб.Шмальгаузен, И.И. Кибернетические вопросы биологии. / Шмальгаузен И.И. Новосибирск: Наука - 1968 - 223 с.

62. Эволюционные вычисления и генетические алгоритмы. /Составители Гудман Э.Д., Коваленко А.П. //Обозрение прикладной и промышленной математики. -М: Изд-во ТВП- Выпуск 5, 1996 С. 1-11.

63. Adrews, М. Diversity does not necessarily imply adaptability./ M.Adrews , A.Tuson //GECCO Workshop on Evolutionary Algorithms for Dynamic Optimization Problems; J. Branke, editor, 2003- P. 24-28.

64. Bendtsen, C. N. Dynamic Memory Model for Non-Stationary Optimization. / Bendtsen, C. N. and Krink, T. // Proceedings of the Fourth Congress on Evolutionary Computation (CEC-2002), Vol. 1, 2002 P. 145-150.

65. Bertoni, M. Implicit parallelism in Genetic Algorithms./ M.Bertoni, M.Dorigo // In Artificial Intelligence (61) 2, 1993 P.307-314.

66. Blackwell, Т. M. Swarms in dynamic environments. Lecture Notes in Computer

67. Science (LNCS) No. 2723. / Т. M. Blackwell //Proceedings of the Genetic and Evolutionary Computation Conference 2003 (GECCO 2003), Chicago, IL, USA, 2003-P. 1-12.

68. Branke, J. Memory enhanced evolutionary algorithms for changing optimization problems./ J.Branke // In Congress on Evolutionary Computation CEC99, Vol.3, IEEE, 1999 P. 1875-1882.

69. Branke, J. Evolutionary approaches to dynamic environments updated survey./ J.Branke // In GECCO Workshop on Evolutionary Algorithms for Dynamic Optimization Problems, 2001 - P.27-30.

70. Branke, J. Evolutionary Optimization in Dynamic Environments./ J.Branke Klu-wer Academic Publishers, 2003 - 317 p.

71. Branke, J. Multi-Population Approach to Dynamic Optimization Problems./ J.Branke, T.Kausler, C.Schmidt, and H.Schmeck A //In Adaptive Computing in Design and Manufacturing, Springer, 2000.

72. Cobb, H. An Investigation into the Use of Hypermutation as an adaptive Operator in Genetic Algorithm Having Continuous, Time-Dependent Nonstationary Environments. / H.Cobb //Naval Research Laboratory Memorandum Report 6760, 1990.

73. Cobb, H. G. Genetic Algorithms for Tracking Changing Environments./ H. G. Cobb, J. F.Grefenstette // Proceedings of the 5th International Conference on Genetic Algorithms Forrest, editor, 1993 - P.523-530.

74. Collingwood E. Useful Diversity via Multiploidy ./ E.Collingwood, D.Corne, P.Ross // in Proceedings of International Conference on Evolutionary Computing, 1996-P. 810-813.

75. Dasgupta, D. Optimisation in Time-Varying environments using Structured Genetic Algorithms/ D.Dasgupta // Technical Report No IKBS-17-93, Dec. 1993.

76. Dasgupta, D. Nonstationary function optimization using the Structured Genetic Algorithm./ D.Dasgupta, D. R. McGregor // In Proceedings of Parallel Problem Solving From Nature (PPSN-2), Brussels, 28-30 September, 1992 P.145-154.

77. Dasgupta,D. SGA: A Structured Genetic Algorithm./ D.Dasgupta, D. R. McGregor //Technical report no. IKBS-8-92, University of Strathclyde, 1992.

78. Davis, L. Genetic Algorithms and Simulated Annealing, Morgan Kaufmann, 1987 216 p.

79. Davis, L. Handbook of Genetic Algorithms/ L.Davis van Nostrand Reinhold, New York - 1991.

80. Eggermont, J. Non-stationary function optimization using evolutionary algorithms with a case-based memory/ J.Eggermont, T.Lenaerts // Technical Report TR2001, 2001.

81. Ghosh, A. Function optimization in nonstationary environment using steady state genetic algorithms with aging of individuals./ A.Ghosh, S.Tstutsui, and H.Tanaka. // In IEEE Intl. Conf. on Evolutionary Computation—, 1998 P.666-671.

82. Goldberg, D.E. Genetic algorithms in search, optimization, and machine learn-ing./Goldberg D.E. Addison-Wesley, 1989

83. Gordon, V. A note on the performance of genetic algorithms on zero-one knapsack problems./V.Gordon, A.BOhm, D.Whitley// Proceedings of the 1994 ACM symposium on Applied computing , 1994 P. 194-195.

84. Grefenstette, J. J. Genetic Algorithms for changing environments./ J. J. Grefenstette // In Proceedings of Parallel Problem Solving From Nature (PPSN-2), Brussels, 28-30 September, 199 P. 137-144.

85. Grefenstette, J. J. An Approach to Anytime Learning. Proceedings of the Ninth / J. J. Grefenstette, C. L. Ramsey //International Conference on Machine Learning, San Mateo, С A: Morgan Kaufmann , 1992 P. 189-195.

86. Handbook of Evolutionary Computation/ Editors: Back Т., Fogel D.B., Michale-wicz Z.- Oxford University Press, NewYork, 1997.

87. Haupt, R. Practical Genetic Algorithms/ R.Haupt, S.Haupt John Wiley & Sons, 1998-261 p.

88. Holland, J.H., Adaptation in Natural and Artificial Systems/ J.H. Holland Ann Arbor: University of Michigan Press, 1975.

89. Holland, J.H. Genetic algorithms and classifier systems: Foundations and future directions. / J.H. Holland// 2nd International Conference on Genetic Algorithms, 1987-P. 82-89.

90. Hollstien, R. B. Artificial genetic adaptation in computer control systems./ R. B. Hollstien // Dissertation Abstracts International, 32(3):1510B (University Mi-crolmsNo. 7123, 773), 1971.

91. De Jong, K. A. An analysis of the behavior of a class of genetic adaptive systems. / De Jong, К. A. //PhD Dissertation, Univ. of Michigan, 1975.

92. Koza, John R. Genetic Programming: on the programming of computers by means of natural selection. // John R.Koza, -MIT Press. 1992.

93. Larranaga, P./ Tackling the Traveling Salesman Problem with Evolutionary Algorithms: Representations and Operators / P.Larranaga, C.M.H.Kuijpers, R.H. Murga // Technical Report, 1998

94. Louis, S. J. Solving similar problems using genetic algorithms and case-based memory. / S. J.Louis, J Johnson // In Proceedings of the Seventh International Conference on Genetic Algorithms, Morgan Kauffman, San Mateo. P.283-290.

95. Lewis, J. A comparison of dominance mechanisms and simple mutation on non-stationary problems./ J. Lewis, E.Hart, G.Ritchie. // In 5PPSN: Parallel Problem Solving from Nature, Vol. 1498. LNCS, Springer, 1998 P. 139-148.

96. Lin, S. An effective heuristic algorithm for the traveling salesman problem. / S.Lin, B.W. Kernighan //Oper.Res, Vol.21,#2, 1973 P.498-516.

97. Lopez de Mantaras, R. Case-Based Reasoning: An overview. / R.Lopez de Mantaras, E.Plaza //AI Communications Journal 10(1), 1997 P. 21-29.

98. Morrison, R. Performance measurement in dynamic environments./ R.Morrison // In J. Branke, editor, GECCO Workshop on Evolutionary Algorithms for Dynamic Optimization Problems, 2003 P.5-8.

99. Michalewicz, Z. Genetic algorithms + data structures = evolution programs./ Z.Michalewicz Springer Verlag, New York, 3rd edition, 1996.

100. Mitchell, M. An Introduction to Genetic Algorithms / Mitchell M. MIT Press, 1996.

101. 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.

102. Ng, K. P. A new diploid scheme and dominance change mechanism for non-stationary function optimization. / K. P. Ng, K. C.Wong // Proc. 6th Int'l Conference on Genetic Algorithms, Morgan Kaufmann Publishers 1995, P. 159-166.

103. Ohkura, K. Structured string representation and adaptive genetic search. / K.Ohkura, K.Ueda //In Proceedings of the Japan-USA Symposium on Flexible Automation, Vol.2., 1996 P. 1477-1480.

104. Oliver, I. A study of permutation crossover operators on the traveling salesman problems. / I.Oliver, D.Smith, J.R. Holland //Proc. of the Second International Conf. on Genetic Algorithms. 1987 P.224-230.

105. Ramsey, C. Case-based initialization of genetic algorithms./ C.Ramsey, J.Grefenstette // In Proc. Fifth International Conference on Genetic Algorithms. 1993 -P.84—91.

106. Ramsey, C. L. Case-based anytime learning. // C. L.Ramsey, J. J. Grefenstette //In Case-Based Reasoning: Papers from the 1994 Workshop, (D. W. Aha, Ed.). Technical Report WS-94-07, AAAI Press: Menlo Park, CA, Aug., 1994.

107. Rechenberg I. Evolution Strategy./ I.Rechenberg // Computational intelligence imitating life. IEEE Press. 1994.

108. Rudolph, G. Convergence Analysis of Canonical Genetic Algorithms./ G.Rudolph // IEEE Trans, on Neural Networks, special issue on Evolutionary Computation, Vol. 5, no. 1, 1994- P.96-101.

109. Ryan, C. Diploidy without dominance. / C.Ryan //In J. T. Alander, editor, Third Nordic Workshop on Genetic Algorithms, 1997 P.63-70.

110. Ryan, C. The Degree of Oneness. / C.Ryan // 1st Online Workshop on Soft Computing, Nagoya, Japan, 1996 P. 100-105.

111. Schwefel H.-P. Evolution and Optimum Seeking. / H.-P. Schwefel John-Wiley, New York, 1995

112. Smith, R. E. Diploidy and Dominance in Artificial Genetic Search / R. E. Smith, D. E. Goldberg // Complex Systems, Vol.6, 1992 P. 251—285.

113. Suzuki, J. A Markov Chain Analysis on Simple Genetic Algorithms./ J.Suzuki // IEEE Trans, on Systems, Man, and Cybernetics, April, 1995 P.655-659.

114. Suzuki J. A Further Result on the Markov Chain Model of GAs and Their Application to SA-like Strategy./ J.Suzuki // IEEE Trans, on Systems, Man, and Cybernetics. Feb. 1998 P.95-102.

115. Trojanowski, K. Evolutionary algorithms for non-stationary environments./

116. K.Trojanowski, Z.Michalewicz.// In Proc. of 8th Workshop: Intelligent Information systems. ICS PAS Press, 1999 P.229-240.

117. Vavak,F. Leaning the Local search range for genetic optimization in nonsta-tionary environments/ F.Vavak, K.A. Jukes, T.C.Fogarty //In IEEE Intl. Conf. on Evolutionary Computation ICEC'97 IEEE Publishing, 1997 P. 355-360.

118. Van Hemert, J. A futurist approach to dynamic environments./ J.Van Hemert, C. Van Hoyweghen, E. Lukshandl, and K.Verbeeck.// In GECCO Workshop on Evolutionary Algorithms for Dynamic Optimization Problems, 2001 P.35-38.

119. Whitley, D. A Genetic Algorithm Tutorial. / D.Whitley //Statistics and Computing- Vol. 4, 1994 P. 64-85.

120. Whitley, D. An Overview of Evolutionary Algorithms / D.Whitley //Journal of Information and Software Technology, Vol. 43, 2001 P. 817-831.

121. Weicker, K. Performance Measures for Dynamic Environments./ K.Weicker // In: Parallel Problem Solving from Nature PPSN VII, Lecture Notes in Computer Science 2349. Springer-Verlag, 2002 - P. 64-73.