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

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

ЕРЕМЕЕВ Антон Валентинович

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

05.13.17 — теоретические основы информатики

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

5 дек гт

005542001

Москва - 2013

005542001

Работа выполнена в Омском филиале Федерального государственного бюджетного учреждения науки Института математики им. С.Л. Соболева Сибирского отделения Российской академии наук

Научный консультант:

доктор физико-математических наук, профессор Александр Александрович Колоколов

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

Эдуард Хайрутдинович Гимади

доктор физико-математических наук, профессор Владимир Константинович Леонтьев

Ведущая организация:

доктор физико-математических наук, доцент Михаил Юрьевич Хачай

Федеральное государственное бюджетное учреждение науки Институт вычислительной математики и математической геофизики Сибирского отделения Российской академии наук

Защита состоится 19 декабря 2013 г. в 13 часов на заседании диссертационного совета Д002.017.02 в Федеральном государственном бюджетном учреждении науки Вычислительном центре им. A.A. Дородницына РАН по адресу: 119333, г. Москва, ул. Вавилова, д. 40.

С диссертацией можно ознакомиться в библиотеке ВЦ РАН

Автореферат разослан " 1$ " jtö^^Jj 2013 г. Ученый секретарь

диссертационного совета Д002.017.02 д.ф.-м.н., профессор B.B. Рязанов

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Задачи комбинаторной оптимизации находят широкое применение в информатике, технике, экономике, планировании и других областях. В настоящее время в комбинаторной оптимизации интенсивно развивается подход, основанный на бионическом принципе моделирования эволюционных процессов адаптации в живой природе. Эволюционные методы успешно применяются в информационных технологиях проектирования, планирования, управления, распознавания образов и т.д. Этим методам посвящено большое число работ как отечественных авторов (Д.И.Батищев, И.Л.Букатова, Н.Г.Загоруйко, А.Г.Ивахнснко, Ю.А.Кочетов, В.М.Курейчик, Ю.И.Неймарк, И.П.Норенков, Л.А.Растригин, В.Г.Редько, Е.С.Семенкин и др.), так и зарубежных (E.Balas, D.Goldberg, J.Holland, I.Rechenberg, M.Schoenauer, P.Vitanyi, M.Vose, I.Wegener, и др.).

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

Важное место в комбинаторной оптимизации занимает проблематика целочисленного программирования, которая включает вопросы, связанные с теорией двойственности, полиэдральным подходом, методами отсечения, ветвей и границ, декомпозиции, множителей Лагранжа, выпуклым и нсвы-пуклым программированием, устойчивостью решений и т.д. Исследованию данной проблематики посвящены работы В.Л.Берсенева, В.П.Булатова, В.Т.Дементьева, Ю.Г.Евтушенко, В.А.Емеличева, И.И.Еремина, М.М.Ковалева, А.А.Колоколова, В.К.Леонтьева, Вл.Д.Мазурова, И.В.Сергиенко, А.С.Стрекаловского, В.Н.Шевченко, G.Dantzig, J.Edmonds, D.Fulkcrson, R.Gomory, G.Nemhauser и многих других авторов как в России, так и за рубежом. В ряде известных методов решения задач целочисленного иро-

граммировалия используется сведение исходной задачи к последовательности задач непрерывной оптимизации. На этом подходе основаны методы отсечения, декомпозиции, ветвей и границ, алгоритмы перебора L-классов и др. Актуальной проблемой при исследовании таких методов является построение нижних и верхних оценок числа итераций, в том числе оценок в среднем. Важные результаты в этом направлении получены В.П.Гришухиным, О.А.Заблоцкой, Л.А.Заозерской, А.А.Колоколовым, Н.Н.Кузюрипым, Ю.Ю.Финкельштейном, R.Jeroslow, H.Lenstra, Е.Venta.

При решении задач комбинаторной оптимизации широко используется метод динамического программирования, предложенный Р.Беллмапом, и его обобщения. Актуальные вопросы распараллеливания, преодоления больших затрат памяти, разработки гибридных алгоритмов, анализа графовых интерпретаций динамического программирования и решения многокритериальных задач в рамках данного подхода рассматриваются в работах В.В.Быковой, Г.Г.Забудского, А.В.Кельманова, Д.И.Когана, Н.Н.Моисеева, В.В.Серваха, Н.З.Шора, О.А.Щербины, U.Bertele, F.Brioschi, Z.Galil и других авторов.

Среди первых методов решения задач комбинаторной оптимизации наряду с методами отсечений, динамического программирования и ветвей и границ возникли методы локального поиска и локальные алгоритмы. В пашей стране основоположниками этого направления стали Ю.И.Журавлев, который ввел в рассмотрение класс локальных алгоритмов и провел анализ их сложности, Л.А.Растригин, предложивший и исследовавший рандомизированные алгоритмы локального поиска, а также И.В.Сергиенко, развивший метод вектора спада и обосновавший его работоспособность. Значительные результаты в исследовании возможностей методов локального поиска получены А.Н.Аптамошкипым, Ю.А.Кочетовым, О.Э.Семенкиной, В.Kernighan, S.Lin, C.Papadimitriou, C.Tovey, M.Yannakakis и другими.

Приближенные алгоритмы решения задач комбинаторной оптимизации оказываются незаменимыми в ситуациях, когда получение точного решения требует чрезмерных временных затрат. Значительный вклад в область разработки и анализа приближенных алгоритмов внесли А.А.Агеев, Э.Х.Гимади, Н.И.Глебов, А.А.Корбут, В.А. Перепелица, В.К.Попков, И.Х.Сигал, М.Ю.Хачай, S.Arora, G.Cornuéjols, В.Körte, L.Lovász, D.Hochbaum, P.Raghavan, C.Thompson и ряд других авторов. В настоящее время интенсивно исследуются вопросы существования

полиномиальных аппроксимациониых схем и их трудоемкости. Существенные результаты в этом направлении полумили Г.В.Генс, М.Я.Ковалев, Е.В.Левнер, С.В.Севастьянов, Я.М.Шафраиский, O.Ibarra, C.Kim, W.Kubiak, G.Woeginger и другие.

Эволюционные алгоритмы (ЭА) берут начало в работах L.Fogel и J.Holland, где было предложено моделировать процесс биологической эволюции с целью синтеза эффективных в некотором смысле структур и создания систем искусственного интеллекта. В нашей стране А.Г.Ивахненко и Л.А.Растригиным независимо были предложены методы случайного поиска, где также использовались идеи эволюции. Характерной особенностью ЭА является имитация процесса эволюционной адаптации биологической популяции к условиям окружающей среды, при этом особи соответствуют пробным точкам в пространстве решений задачи оптимизации, а приспособленность особей определяется значениями целевой функции и штрафами за нарушение ограничений задачи, если такие имеются. В рамках данного подхода предложены эволюционные стратегии (I.Rechenberg), генетические алгоритмы (J.Holland), алгоритмы случайного поиска с адаптацией (Г.С.Лбов), эволюционного моделирования (И.Л.Букатова, L.Fogel), генетического программирования (J.Koza), многокритериальные ЭА (M.Peschel, C.Riedel). К классу ЭА также могут быть отнесены алгоритмы Метрополиса, имитации отжига, поиска с запретами и др. Указанные алгоритмы различаются способами моделирования эволюционного процесса и отражаемыми его аспектами, однако имеют много общих элементов. Области применения этих алгоритмов также несколько различаются.

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

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

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

Теоретически наиболее детально исследованы эволюционные алгоритмы с достаточно простыми (как правило, линейными по трудоемкости) операторами мутации и кроссинговера. Как выяснилось, базовые схемы ЭА при подходящем способе представления решений и настройках параметров могут воспроизводить основные этапы работы известных алгоритмов дискретной оптимизации. Значимые результаты в данном направлении получены при анализе ЭА для таких классических задач дискретной оптимизации, как задача о кратчайшем пути в графе (J.Scharnow, K.Tinricfeld, I.Wegener), задача об остовпом дереве минимального веса (F.Neuinann, ¡.Wegener) и задача о разрезе минимального веса (F.Neumann, J.Reichel, M.Skutella). Оптимальные решения этих задач могут быть получены в среднем за полиномиальное время при помощи многокритериальных эволюционных алгоритмов, воспроизводящих работу алгоритмов Дейкстры и Краскала, или неявно учитывающих двойственность задач о минимальном разрезе и максимальном потоке. ЭА с аналогичными свойствами найдены и для некоторых других задач. Вместо с тем недостает обобщающих результатов об эффективности ЭА на крупных классах задач, а также теоретически обоснованных выводов о преимуществе одного ЭА над другим па некотором классе задач.

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

тодами позволили разработать конкурентоспособные гибридные алгоритмы. В таких алгоритмах отдельные операторы представляют собой уже известные алгоритмы, такие как локальный поиск, жадный алгоритм, метод ветвей и границ или перебор ¿-классов. Для некоторых гибридных ЭА удается и теоретически гарантировать качество получаемого решения благодаря свойствам используемых в них классических методов. К сожалению, в большинстве случаев обоснование работоспособности гибридных ЭА ограничивается применением теоремы E.Aarts, A.Eiben и К.van Нее о сходимости к оптимуму «почти наверное», предъявляющей достаточно слабые требования к операторам ЭА, но не дающей оценок сверху на время достижения оптимума. Для выхода из создавшейся ситуации необходимы новые методы получения оценок времеии отыскания решений требуемой точности и вероятности порождения достаточно точных решений на заданной итерации ЭА.

Работоспособность генетического алгоритма (ГА) существенно зависит от выбора оператора кроссинговера, где комбинируются элементы родительских решений. Новым направлением исследований является анализ сложности и разработка эффективных алгоритмов решения задачи оптимальной рекомбинации (ЗОР), состоящей в отыскании наилучшего возможного результата кроссинговера при заданных родительских генотипах. Результаты C.Aggarwal, E.Balas, W.Cook, J.Orlin, P.Seymour и др. дают экспериментальное подтверждение целесообразности решения ЗОР (точного или приближенного) в операторах кроссинговера. Тем не менее до сих пор не было проведено систематического анализа вычислительной сложности ЗОР и эффекта от ее решения в процессе работы ЭА.

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

1) разработка эволюционных алгоритмов и их гибридных вариантов с использованием классических методов комбинаторной оптимизации;

2) оценка точности решений, получаемых эволюционными алгоритмами, построение оценок трудоемкости этих алгоритмов и их основных операторов, сопоставление полученных оценок с известными аналогами;

3) анализ сложности задач комбинаторной оптимизации, и в частности, задач оптимальной рекомбинации, оценивание параметров задач, влияющих

па работоспособность ЭА.

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

Научная новизна. Введена в рассмотрение общая постановка задачи оптимальной рекомбинации в терминах задач комбинаторной оптимизации; предложен метод построения сводимостей ЗОР, подобных известным своди-мостям задач комбинаторной оптимизации, позволивший доказать полиномиальную разрешимость или ^-трудность ЗОР для различных задач. Разработана методика использования в ГА операторов кроссинговера, основанных на решении ЗОР, что дало возможность улучшить известные ранее экспериментальные результаты для ряда задач.

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

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

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

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

На защиту выносятся следующие основные результаты.

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

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

2. Исследована сложность задач оптимальной рекомбинации: установлена полиномиальная разрешимость задач оптимальной рекомбинации в генетических алгоритмах для ряда задач булевого линейного программирования, в частности задач упаковки и разбиения множества и простейшей задачи размещения производства; установлена КР-трудность оптимальной рекомбинации для задачи коммивояжера, задал о рюкзаке, кратчайшем гамильтоповом пути, упаковке в контейнеры и некоторых других классических задач комбинаторной оптимизации.

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

4. Разработан подход к построению гибридных генетических алгоритмов, использующих оптимальную рекомбинацию и жадные алгоритмы для решения NP-тpyдныx задач комбинаторной оптимизации: предложены новые генетические алгоритмы для задач покрытия множества, управления поставками продукции и балансировки производственной линии, экспериментально установлены классы задач, на которых такие алгоритмы имеют преимущество по сравнению с известными алгоритмами; выполнен теоретический анализ сложности приближенного решения задачи управления поставками продукции.

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

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

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

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

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

Всероссийской конференции «Проблемы оптимизации и экономические приложения» (Омск, 1997, 2003, 2006, 2009, 2012);

Всероссийской конференции «Математическое программирование и приложения» (Екатеринбург, 1997, 1999, 2007, 2011);

Российской конференции «Дискретный анализ и исследование операций» (Новосибирск, 1998, 2000, 2002);

Российской конференции «Дискретная оптимизация и исследование операций» (Владивосток, 2007; Алтай, 2010; Новосибирск, 2013);

International Conference on Operations Research (Цюрих, Швейцария, 1998);

Байкальской международной школе-семинаре «Методы оптимизации и их приложения» (Иркутск, 1998, 2001; Северобайкальск, 2008);

Conference Evolution Artificielle (Дункерк, Франция, 1999);

International Workshop «Discrete Optimization Methods» (Минск, 2000; Омск - Иркутск, 2004);

European Workshop on Evolutionary Computation in Combinatorial Optimization (Милан, Италия, 2001; Турин, Италия, 2011);

International Seminar «Theory of Evolutionary Algorithms» (Дагштул, Германия, 2002, 2004, 2006, 2008, 2010, 2013);

Workshop on the Foundations of Genetic Algorithms (Торремолинос, Испания, 2003);

Conference of the European Chapter on Combinatorial Optimization (Минск, 2005);

Азиатской школе-семинаре «Оптимизация сложных систем» (Новосибирск, 2006; Усть-Каменогорск, 2010);

Международной научной конференции «Дискретная математика, алгебра и их приложения» (Минск, 2009);

Международной конференции «Интеллектуализация обработки информации» (Будва, Черногория, 2012);

Euro Mini Conference on Variable Neighbourhood Search (Херцег Нови, Черногория, 2012);

а также на семинарах в Институте математики им. С.Л. Соболева СО РАН, его Омском филиале и Вычислительном центре им. A.A. Дородницына РАН. Материалы диссертации легли в основу курса «Эволюционные алгоритмы», читаемого магистрантам Института математики и информационных технологий Омского государственного университета им. Ф.М. Достоевского.

Публикации. По теме диссертации автором опубликовано 38 статей и глав монографий, в том числе 20 статей в журналах из списка ВАК.

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

Объем и структура диссертации. Диссертация состоит из введения, пяти глав, заключения и списка литературы (296 наименований). Объем диссертации 300 страниц.

Содержание работы

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

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

соответственно; {0,1}* - множество всевозможных строк из нулей и единиц. Для строки S € {0,1}* символом |5| обозначается ее длина.

Определение 1.1 Задача комбинаторной оптимизации - это тройка П = (Inst, Sol,//), где

1) Inst С {0,1}* - множество индивидуальных задач из П;

2) Sol(/) С {0,1}"^ - множество допустимых решений индивидуальной задачи I € Inst, где п(1) - размерность пространства решений;

3) для каждой I € Inst определена функция fj : Sol (I) —> Ж, которую требуется максимизировать (если П - задача максимизации) или минимизировать (если П - задача минимизации).

Далее через jj обозначается оптимальное значение целевой функции в индивидуальной задаче I. По умолчанию под полиномиально ограниченной величиной подразумевается величина, ограниченная сверху полиномом с положительными коэффициентами относительно |/|. Задача комбинаторной оптимизации называется полиномиально ограниченной, если значения//(х) полиномиально ограничены.

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

Определение 1.2 Задача комбинаторной оптимизации принадлежит классу NPO, если отношения I € Inst и х 6 Sol(7) могут быть проверены за полиномиально ограниченное время, размерность п(1) полиномиально ограничена, а функция fj : Sol(7) —► N вычислима за полиномиально ограниченное время для любой I (Е Inst.

Из контекста, как правило, ясно, о какой индивидуальной задаче I идет речь. Для краткости символ I в таких случаях будет опускаться.

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

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

Пусть для всякого у е Sol(/) определена окрестность _Л/}(у) С Sol(7). Совокупность {Л/}(у) : у € Sol(/)} называется системой окрестностей. Если для х S Sol(/) при всяком у € Л/}(х) выполняется неравенство //(у) < /г(х) в случае задачи максимизации, или //(у) > //(х) в случае задачи минимизации, то х называется локальным оптимумом. Система окрестностей {yV(x) | х G Sol(/)} называется к-ограниченной, если для любых х Е Sol и у € Л/"(х) выполнено 5(х, у) < А:, где <5(-, •) - метрика Хэмминга.

В разделе 1.2 описываются класс эволюционных алгоритмов и наиболее известные его представители.

Первым излагается классический генетический алгоритм (КГА), предложенный Дж. Холландом, как алгоритм, имитирующий процесс адаптации популяции к окружающей среде, взаимодействие с которой задастся функцией приспособленности особей. На каждой итерации КГА с помощью рандомизированных операторов мутации и кроссинговера строится новая популяция (поколение). Численность популяции N фиксирована от начала работы алгоритма до конца. В КГА каждая особь текущей популяции выбирается в качестве родительской для построения новой особи-потомка с вероятностью, пропорциональной приспособленности родительской особи с помощью так называемого оператора пропорциональной селекции

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

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

Генотип £ представляет собой строку (£ь £2, ■ • •, 6) фиксированной длины I. Элементы этой строки - символы некоторого конечного алфавита, их принято называть генами по аналогии с генами живых организмов, которые представляют собой участки молекулы ДНК.

Обозначим через В множество всевозможных генотипов длины I с сим-

волами из заданного набора алфавитов A\,...,Ai, т.е. В = А\ х • • • х Л/. Для применения ГА к задаче комбинаторной оптимизации необходимо определить функцию представления решений Ф : В —> {0,1}", задающую способ кодирования элементов пространства решений с помощью генотипов.

Образ х = Ф(£) принято называть фенотипом, соответствующим генотипу Во многих случаях в ГА используется тот же способ кодировки решений, что и в постановке задачи комбинаторной оптимизации. В таком случае термины «генотип», «фенотип» и «пробное решение» оказываются эквивалентными, а отображение Ф(-) становится тождественным.

Популяция представляет собой вектор X = (f \ £2,..., £N) G BN, элементами которого являются генотипы. Способ нумерации особей в популяции не имеет значения. Популяция поколения t, t = 0,1,..., обозначается через X1 = (£u,£2í, ... Итерацией ГА является переход от текущей популя-

ции Хь к следующей популяции Xt+l.

В соответствии с общепринятым подходом будем предполагать, что при Ф(£) € Sol функция приспособленности имеет вид Ф(£) = фй t(f №{€)))> фы :R - некоторая строго возрастающая функция, если решается задача па максимум, или строго убывающая функция в случае задачи минимизации. Если же Ф(£) 0 Sol, то функция приспособленности принимает меньшее значение, чем в любом допустимом решении, что соответствует штрафу за нарушение ограничений задачи. Кроме того, будем предполагать, что в ГА Ф(£) > 0 для любого £ е В.

Построение новой особи (потомка) начинается с выбора пары родительских особей из X1 при помощи вероятностного оператора селекции Sel : BN —+ {1,..., N}, в котором номера родительских особей выбираются с учетом их приспособленности. К генотипам выбранных особей применяется оператор кроссинговера Cross : S х S -> В х В (в некоторых генетических алгоритмах Cross : В х В —> В), заменяющий часть генов одного генотипа генами другого. Полученный генотип подвергается действию оператора мутации Mut: В —> В, при этом часть его генов изменяется случайным образом. Здесь и далее под вероятностным оператором понимаем рандомизированную процедуру, такую что при заданном входном аргументе распределение вероятностей па ее выходе не зависит от предшествующей работы алгоритма.

В качестве критерия остановки ГА может использоваться, например, огра-

ничеиие на число итераций или условие достижения оптимума, когда это возможно установить. Результатом ГА является лучшее построенное решение.

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

Операторы Cross и Mut с некоторым упрощением моделируют процессы кроссинговера и мутации в живой природе, где они сводятся к случайным изменениям в молекуле ДНК. Степень воздействия кроссинговера и мутации в КГА регулируется вероятностью кроссинговера Рс и вероятностью мутации Рт. Известно множество вариантов генетического алгоритма, имеющих разные операторы селекции, мутации, кроссинговера и несколько различающихся в своих схемах.

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

Далее приводится описание операторов ЭА и его общая схема. Определения фенотипа, функции представления решений и популяции, введенные выше для ГА, сохраняются без изменений. Функция приспособленности в случае ЭА может иметь более общий вид, чем в случае ГА. Известны эволюционные алгоритмы как для задач с одним критерием оптимизации, так и для многокритериальных задач, поэтому допускается и многокритериальная вектор-функция приспособленности. В качестве примеров известных ЭА в главе 1 описываются эволюционные стратегии и многокритериальные ЭА.

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

операторах кроссинговера и при построении начальной популяции.

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

В разделе 2.1 найдены достаточные условия, при которых генетический алгоритм с полной заменой популяции при турнирной селекции достигает локального оптимума в среднем за полиномиально ограниченное время, и доказано выполнение этих условий на классе задач комбинаторной оптимизации с гарантированными локальными оптимумами (GLO). Предполагается, что двоичное представление решений совпадает с кодировкой решений задачи комбинаторной оптимизации, а при выполнении условия остановки происходит новая инициализация счетчика итераций и популяции Xo, и вычислительный процесс продолжается. Данный вариант ГА обозначается далее через GA.

Пусть в результате кроссинговера с вероятностью не менее некоторой константы е, 0 < е < 1, образуется пара генотипов (х',у') = Cross(x,y), хотя бы один из которых не уступает но приспособленности родительским особям X, у € В при любых X, у £ В, причем константа £ не зависит от I. Для одноточечного кроссинговера последнее неравенство выполняется се = 1 — Рс, если Рс < 1 - константа, не зависящая от I. Указанное условие также выполняется с £ = 1, если один из двух потомков - решение задачи оптимальной рекомбинации, рассматриваемой далее в главе 3.

Пусть имеется задача П = (Inst, Sol, //) и указана некоторая система окрестностей {Л/}(у) : у £ Sol(/)}. Обозначим через h(I) число различных неоптимальпых значений целевой функции //, т. е.

h(I) = \{ф G M : ф = fi(х), X € Sol(7)}| - 1.

Начиная с любого решения, локальный поиск достигает локального оптимума не более чем за h(I) итераций, улучшающих значение целевой функции. Пусть L(I) обозначает минимальную вероятность достижения любого заданного решения в пределах окрестности:

L(I) = min P{Mut(x) = х'}.

v ' xeSoi(Z), х'еЛ/Нх)

Чем выше величина L{I), тем больше согласованность оператора мутации Mut с системой окрестностей Л/*/. Показано, что если начальная популяция Xo

содержит допустимое решение, s > rN, г > О, h(I) > 1, L(I) > 0 и

2(1+In МЛ)

- eL(I)(\ — е~2гУ

то GA с условием остановки t = h + 1 имеет свойства: 1) локальный оптимум посещается к итерации h(I) с вероятностью не менее 1/е; 2) локальный оптимум достигается не более, чем за eh(I) итераций в среднем.

С использованием свойства 2) найдены полиномиальные верхние оценки на среднее время получения оптимума в семействе задач с целевой функцией из класса ONEMAX**, введенного S.Droste, T.Jansen и ¡.Wegener, и семействе задач вершинного покрытия графаС(А;), предложенном Л.А.Заозерской. Кроме того, из свойства 2) вытекает

Теорема 2.1 Если задача П = (Inst, Sol, fj) е NPO полиномиально ограничена, функция \/L{I) полиномиально ограничена, а популяция Xo содержит допустимое решение, то при соответствующих параметрах GA локальный оптимум впервые достигается в среднем за полиномиально ограниченное время.

Согласно G.Ausiello и M.Protasi, задача П из NPO принадлежит классу задач с гарантированными локальными оитимумами (GLO), если выполняются следующие два условия:

1) по крайней мере одно допустимое решение может быть вычислено за полиномиально ограниченное время для любого входа I 6 Inst;

2) существует натуральное число к такое, что все локальные оптимумы задачи П относительно некоторой /г-ограпичеиной системы окрестностей имеют константную оценку точности.

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

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

Следствие 2.1 Пусть П G GLO, п > к и популяция Xa содержит допустимое решение. Тогда при операторе мутации Mut и соответствующем,

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

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

Трудности применения известных моделей ГА (G.Rudolph, M.Vose) к анализу задач комбинаторной оптимизации связаны с большой размерностью матрицы перехода цепи Маркова. Предложенная в данном разделе модель включает в себя меньшее число состояний и позволяет найти нижние и верхние оценки числа особей с приспособленностью не ниже заданного уровня.

Пусть Фо = пип£бвФ(£) и заданы линии уровня функции приспособленности Фь • • •. такие что Ф0 < ф1 < ф2 • • • < Число линий уровня, а также их значения могут зависеть от индивидуальной задачи I. С выбранными линиями уровня сопоставляются лебеговы множества = {£ : Ф(£) > i = 0,..., <± Кроме того, полагаем Щ+\ = 0.

Пусть для всех г = 0,..., d и j = 1,... ,d априори известны нижние ац и верхние ßij оценки вероятности перехода из ЯДЯг+i в Hj при действии оператора мутации, а именно для любого £ £ Hi\Hi+i

otij < P{Mut(0 е Hj} < ßij.

Обозначим матрицу с элементами ощ, где i — 0,...,d и j = 1.,d через А; аналогичную матрицу верхних оценок обозначим через В. Представим

m г (О (О (<h

популяцию на uiarei при помощи вектора популяции zw = , z2 ,..., zd J, где zj^ € К - доля генотипов из Н{ в популяции ХК

Будем называть (d х с/)-матрицу с элементами 7у монотонной, если 7t-ij < 7i,j Для всех iyJ от 1 Д° Пусть Е - символ математического ожидания; W - (d х (¿)-матрица с элементами Wij = с*у — Qi-ij; I ~ единичная матрица; а = («0ъ • • •, £*<и)- Если матрица А монотонна и ||W|| < 1 в некоторой матричной норме, то для любого натурального t имеет место нижняя оценка числа приближенных решений достаточно высокого качества

E[zW] > E[z(0)]W( + a(I - W)"1^ - W*).

При условии монотонности матрицы В имеет место оценка сверху

E[*jt+1)] < pdj ~ J2(Ptj - Pi-i,i)(l - j = l,...,d.

i=l

Итеративным применением последнего неравенства каждая компонента вектора E[z^] может быть оценена сверху при любом t.

Если при всех i = 0,..., d, j = 1,..., d, вероятность P{Mut(£) G Hj} не зависит от выбора Ç S Hi\Hi+1, то существуют матрицы оценок А и В, А = В. В таком случае оператор мутации будем называть ступенчатым относительно набора линий уровня Ф1,..., Ф^ и обозначать матрицу А через М.

Ступенчатый оператор мутации будем называть монотонным, если матрица M монотонна. Для таких операторов мутации проведено исследование свойств вектора популяции, связанных с изменением размера турнира при N —^ оо. С использованием полученных асимптотических свойств доказана

Теорема 2.2 Пусть z^ и z^ - векторы популяции ГА с турнирами величины sus соответственно, причем s < s. Тогда, если ГА имеет монотонный оператор мутации и особи начальных популяций одинаково распределены, то для любых t = 0,1,... и г = 1,..., d при достаточно большом размере популяции имеет место неравенство E[z^] < Е

Выделенный здесь случай монотонного оператора мутации характеризует ситуацию, в которой при N = 1 становятся точными нижние оценки, а при Л'' —> оо - верхние оценки на математическое ожидание вектора популяции. Установлено, что для оператора мутации классического ГА условие монотонности во многих случаях эквивалентно условию принадлежности функции Ф к классу строго монотонных псевдобулевых функций.

В разделе 2.3 исследуются условия, при которых эволюционная стратегия (1+1)-ES (рандомизированный алгоритм локального поиска) оказывается «наилучшим» методом в классе эволюционных алгоритмов.

Будем называть эволюционным алгоритмом с неограниченной памятью следующий рандомизированный алгоритм: начальная популяция 6 BN строится некоторым случайным или детерминированным способом. Последовательность генотипов, построенных в ЭА с неограниченной памятью к началу итерации t, обозначим через <ri-1, а множество всех входящих в аь~1 элементов - через На каждой итерации t, t = 1,2,..., вычисляется

промежуточная популяция Хь из N" генотипов потомков с помощью оператора воспроизведения Rep(??1,... ,T]N'), где 771,... ,T)N' - некоторые из ранее построенных особей. Родительские особи t]1,...,t]N' на итерации t выбираются с помощью рандомизированного оператора селекции с неограниченной памятью Seloo, так что Seloo(t7i_1) Ç Работа ЭА с неограниченной памятью представляет собой итерации следующей композиции случайных отображений: X1 = Rep(Seloo(^"°, • ■ •, Х*~1)), i = 1,2,----Алгоритм указанного

вида обозначим через ЕА.

Эволюционная стратегия (1+1)-ES является рандомизированным алгоритмом локального поиска и начинает работу с начального генотипа, построенного случайно или детерминированно с помощью некоторой процедуры инициализации. На каждой итерации t, i = 0,1,..., по текущему генотипу строится новый генотип посредством оператора мутации Mut. В случае, если Ф(С') > Ф(С'), полагаем := В противном случае := С,1.

Обозначим максимум функции приспособленности на последовательности

генотипов а = (£\...,£fc) через Ф(а), т.е. Ф(<т) = maxj=1.....k Ф(£г)- Будем

говорить, что оператор воспроизведения Rep доминируете» оператором мутации Mut, если для любой ./V'-элементной последовательности генотипов X' и любого 7] е В, таких что Ф(77) > Ф(Х'), при всех ф > Ф(г]):

Р ^(Mut(i?)) > ф} > Р {4>(Rep(X')) > ф] ■

Основным результатом данного раздела является следующая теорема о сравнении эволюционных алгоритмов с эволюционной стратегией (1+1)-ES. Здесь, как и ранее, предполагается, что в эволюционном алгоритме ЕА используется оператор воспроизведения Rep, а в алгоритме (1+1)-ES - оператор мутации Mut.

Теорема 2.3 Для любого эволюционного алгоритма ЕА с неограниченной памятью при Ф(£°) > Ф(Х°) выполняются неравенства

Р{Ф(С4) > ф] > Р{ФИ > Ф}, te z+, феш,

в том и только в том случае, когда оператор Mut доминирует оператор Rep.

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

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

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

В даном разделе построены нижние границы параметра и, обеспечивающие заданную доверительную вероятность. Кроме того, в предположении равновероятного попадания локального поиска во все локальные оптимумы построены консервативные двусторонние доверительные интервалы для и. Предлагаемые методы предназначены для исследования индивидуальных задач комбинаторной оптимизации, в которых большая размерность пространства решений не позволяет осуществить полный перебор всех его элементов за приемлемое время. Вместе с тем S.Sahoo и A.Albrecht показана перспективность использования этих методов в биоинформатике при анализе стабильных состояний молекул РНК.

Результаты второй главы опубликованы в [1,5,12,20,25,26,32,34,38).

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

Определение 3.1 Задачей оптимальной рекомбинации для задачи комбинаторной оптимизации П = (Inst,Sol,/) является задача комбинаторной оптимизации П = (Inst,Sol, f), такая что всякая индивидуальная задача I £ Inst имеет вид I = (/, р\р2), где I € Inst, р1 = (р\,... £ Sol(7),

Р2 = (Pi, ■ • • >Pn(/)) £ Sol(/), и

SoI(7) = {х G SoI(7)| Xj = р) или Xj = р), j = 1,..., п{1)}. (1)

Критерий оптимизации в I тот же, что и в I, т. е. fj= fj.

Допустимые решения р1, р2 задачи I называются родительскими решениями для задачи 7 = (/,р\р2)- Обозначим D(p\p2) = {j \ р) ф р2}.

Определение 3.1 может интерпретироваться как «фиксация» в ЗОР тех значений генов, в которых оба родительских генотипа совпадают. В литературе, однако, известны и другие постановки задач рекомбинации. Например, в работах W.Cook, C.Cotta, P.Seymour, J.Troya обнадеживающие экспериментальные результаты показали ГА, в которых решается задача рекомбинации с «фиксацией» только тех значений генов, в которых оба родительских генотипа имеют значение, равное 0. Такая постановка задачи далее будет называться ослабленной задачей оптимальной рекомбинации, и для ее формулировки достаточно заменить условие (1) в определении 3.1 на

551(7) = {х € Sol(/)| Xj < р) или Xj < р2, j = 1.....п(1)}. (2)

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

п

max Дх) = ^cjxj, (3)

j=i

n

QijXj <bu i = 1,..., m, (4)

j=i

Xj e {0,1}, j = l,...,n. (5)

Здесь x G {0, l}n - вектор булевых переменных, а исходные данные Cj, bi, qij, г = 1,..., m, j = 1,..., n - рациональные числа.

В разделе 3.2 с использованием полиномиальных сводимостсй между задачами оптимальной рекомбинации доказывается, что ЗОР полиномиально разрешима для задач упаковки множества наибольшего веса, разбиения множества минимального веса и простейшей задачи размещения предприятий в постановке булевого линейного программирования. Для задачи булевого линейного программирования (3)-(5) введем обозначение C/¿ = {j \ qij ^ 0, j = 1 ,...,n}, i = l,...,m.

Теорема 3.2 ЗОР для задачи булевого линейного программирования (3)-(5) сводится к задаче о независимом множестве в 2-раскрашиваемом

гиперграфе, где 2-раскраска является частью входных данных. Каждое ребро в получаемом гиперграфе содержит не более чем U¡пах вершин, где í/max = max¡=i m \Ui\, и трудоемкость данной сводимости есть 0(т(2и,иах +п)).

Из теоремы 3.2 следует существование полиномиально вычислимого оператора оптимальной рекомбинации для задач булевого линейного программирования, где в каждое ограничение входят не более двух неременных. Таким образом, получено обобщение результата Е.Balas и W.Nichaus об эффективной разрешимости ЗОР для задачи о клике наибольшего веса.

В разделе 3.3 показана сложность ряда задач оптимальной рекомбинации. Доказана NP-трудность оптимальной рекомбинации для задач булевого линейного программирования с тремя переменными в каждом ограничении. Далее рассмотрена ЗОР для задач об одномерном булевом рюкзаке и одномерной упаковке в контейнеры в постановке булевого линейного программирования. Задача об одномерном булевом рюкзаке имеет формулировку

где о^ > О, С7 > 0,] = 1,..., п, и А > 0 целочислены.

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

Пусть булева переменная yj является индикатором использования контейнера с номером у, _7 = 1,..., к, а булева переменная хц - индикатором упаковки предмета i в контейнер 3 при г, ^ = 1.. ,к. Требуется найти

п

п

шах

I ^^ CLjXj < A, Xj £ {0,1}, j = 1,... ,п 3=1 j=l

к

inin Y^Vj

j=1

к

к

г=1

Уз ^ ^ — 2 — 1,..., ку

хц, % € {0,1}, г = 1,...,к, 2 = 1,2,...,к.

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

Теорема 3.3 ЗОР и ослабленная ЗОР для одномерных задач о булевом рюкзаке и об упаковке в контейнеры являются NР-трудными.

Рассмотрим задачу коммивояжера (ЗК): дай ориентированный граф С без нетель и кратных дуг с множеством вершин V и множеством дуг А, где длина дуги (г,2) € Apa.mia.Cij > 0. Найти гамильтонов контур минимальной длины.

Если для любой дуги (г, 2) € А существует обратная, и Су = с^,, то ЗК называется симметрической и граф (? можно считать неориентированным. Если же такое свойство не предполагается, то имеет место общий случай ЗК.

Допустимое решение задачи коммивояжера в ЭА может кодироваться как строка, в которой последовательно записаны все компоненты матрицы перестановки, отвечающей маршруту коммивояжера. В таком случае ЗОР состоит в поиске кратчайшего маршрута коммивояжера, совпадающего с двумя родительскими допустимыми решениями по тем дугам (или ребрам), по которым проходят оба контура родительских решений, и не проходящего по дугам (или ребрам), отсутствующим в обоих из них. КР-трудность ЗОР в симметрическом случае ЗК доказана с использованием результата А.Ка1, С.Рарас^гшЫои и Л.Зг\¥агс{Нег об №-полноте задачи проверки свойства гамильтоновости решеточных графов.

Теорема 3.4 ЗОР для задачи коммивояжера в симметрическом случае МР-трудна в сильном смысле.

Аналогично доказывается теорема 3.5 об ^-трудности ЗОР для задачи отыскания кратчайшей гамильтоновой цели в графе.

В общем случае ЗК задача оптимальной рекомбинации не является обобщением рассмотренной в теореме 3.4. Даже при симметрической матрице расстояний (су) пара родительских «маршрутов», понимаемых как контуры, обусловливает иное множество допустимых решений ЗОР, чем та же пара

«маршрутов», понимаемых как циклы. Таким образом, общий случай требует специального анализа сложности.

Теорема 3.6 ЗОР для задачи коммивояжера в общем случае NP-тпрудна в сильном смысле.

Рассмотренные выше задачи оптимальной рекомбинации сводятся к ЗК с предписанными ребрами на графах, где степень вершин равна не более 4 в симметрическом и не более 3 - в общем случае. Решение таких задач может быть получено алгоритмами, предложенными D.Eppstein. В частности, трудоемкость решения ЗОР для общего случая ЗК составляет0(|V| • 1.421^1).

В работе [8] рассмотрен иной подход к кодировке решений для задач на перестановках и соответствующая ему ЗОР. Как показано в [9], в случае задачи о кратчайшем гамильтоновом пути этот способ представления решений также приводит к NP-трудной ЗОР, однако для «почти всех» нар родительских решений ЗОР полиномиально разрешима.

Результаты третьей главы опубликованы в [4,18,21,33].

В главе 4 предложены эволюционные алгоритмы с возможностями методов динамического программирования (ДП).

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

Пусть имеется d! критериев оптимизации. Индивидуальная задача Г из многокритериальной задачи П' определяется четверкой (d\ g, S, D). Здесь S -пространство поиска, g: S —»(R U {oo})d' - векторпо-значпая целевая функция, и Т> С S - множество допустимых решений. Введем частичный порядок >z для обозначения доминирования по Парсто: (у[,..., y'd,) >z (у\,..., уд) тогда и только тогда, когда уJ < % для всех j, таких что gj - критерий минимизации, и y'j > yj для всех j, таких что gj - критерий максимизации (у' У> если у' У У и у ^ у'). Решение задачи I' состоит в отыскании полного множества альтернатив (ПМА).

Далее предполагается, что ПМА задачи Г с помощью некоторой эффективной процедуры (например, метода обратного хода) может быть преобразовано в оптимальное решение х* € Sol(7) индивидуальной задачи I из П.

Алгоритм ДП для задачи П' выполняется за п итераций, называемых стадиями. На каждой стадии г вычисляется и записывается в память некоторое множество состояний С Будем говорить, что алгоритм решает индивидуальную задачу I', если множество состояний, вычисленных на последней стадии ДП, представляет собой ПМА для /'.

Пусть имеются п конечных множеств отображений ъ — 1, со-

стоящих из переходных функций вида 5 —+ Здесь 5' содержит пространство ¿> или совпадает с ним. С целью исключения элементов, принадлежащих 5'\<5, на каждой стадии г используется семейство функционалов Нр, Ну: 5' —> М, таких что при любом ^ е ^ выполнено ^(5) е Я тогда и только тогда, когда Ну(8) < 0.

Сначала рассматривается упрощенный алгоритм ДП, в котором на этапе инициализации формируется множество ¿>0, являющееся конечным подмножеством 5. На г-той стадии вычисляется множество состояний по формуле

$ = {^(5) I 5 е F е Ти НР{Б) < 0}.

Результатом работы упрощенного алгоритма ДП является минимальное по включению подмножество <5^ С такое что <7(5^) = <?(<5>я).

Для снижения трудоемкости в приложениях ДП, как правило, используется принцип оптимальности Р.Беллмана или его обобщения, что позволяет удалить из рассмотрения неперспективные состояния, не нарушая оптимальности результата. Во многокритериальном случае классический принцип Р.Беллмана, как правило, неприменим, однако неперспективные состояния могут быть удалены с помощью соответствующего отношения доминирования на множестве состояний ДП (см., например, в алгоритмы, предложенные В.С.Михалевичем и Н.З.Шором, 11.ККИ;г1ег, С.\Уое§ш§ег и др.).

Рассмотрим предпорядок ^аот "а <5', такой что 5 ^аот 51' тогда и только тогда, когда д(Б) < д(Б') или 5 ^ 5, 5' € 5. Установлено, что два следующих условия позволяют корректно использовать отношение ^¿от Для исключения неперспективных состояний в ДП.

С.1. При л гобых 5,5" € 5, г = 1,..., п, если 5 ^от 5', то F(S) ^аот .Р(5') для всех F € таких, что F(£") 6 5.

С.2. Для любых г = 1,... ,п и Р € Ти если 5 ^от 5", то

Я/г(5') < ЯИ5).

При выполненных условиях С.1 и С.2 в алгоритме ДП достаточно хранить не все множество ¿>г, а лишь минимальное по включению его подмножество,

доминирующее и общая схема ДП представима в следующем виде.

Алгоритм 4.1 Динамическое программирование для задачи II'

1. Т0 := 50.

2. Цикл для всех г — 1,... ,п .

3. % := 0.

4. Цикл для всех 5 6 ^ £ ■

5. Если < 0 и € %, такой что F(5) Хаот 5', то

6. Тц={%\ {5" е 711 5" ВД}) и {^(5)}.

7. Конец цикла.

8. Конец цикла.

9. Результат: Тл.

Если упрощенный алгоритм ДП вычисляет множество состоянийпредставляющее собой ПМА для /', и условия С.1 и С.2 выполнены, то алгоритм 4.1 также находит ПМА для /'.

В разделе 4.2 при условии применимости к задаче П' алгоритма ДП предлагается многокритериальный ЭА с аналогичными свойствами. Для выявления эффектов, связанных со спецификой ЭА, необходимо ввести дополнительные ограничения на трудоемкость каждого из операторов многокритериального ЭА. Такой подход к сравнению ЭА и ДП реализован в следующей теореме 4.1. Обозначим через Тор трудоемкость алгоритма ДП, а через - наибольшую из мощностей множеств состояний, вычисленных за все время работы ДП. Под обработкой состояния в ДП будем ионимать итерацию внутреннего цикла, т.е. строки 5 и 6 алгоритма 4.1.

Теорема 4.1 Пусть задача П' разрешима алгоритмом ДП, условия С.1, С.2 выполнены, а обработка состояния в ДП имеет трудоемкость 0(1). Тогда существует многокритериальный ЭА, где трудоемкость каждого оператора есть 0(1), и ПМА задачи П' вычисляется в среднем за время 0(7ЪРпк^И/тах).

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

В разделе 4.3 установлено (теорема 4.2), что для класса задач, удовлетворяющих условиям G.Woeginger существования вполне полиномиальной ап-проксимациопной схемы (РРТАБ), на основе многокритериального ЭА может быть построено семейство алгоритмов, являющееся вполне полиномиальной рандомизированной аппроксимационной схемой (РРИАБ).

Результаты четвертой главы опубликованы в [3,14,22,23,29].

Глава 5 посвящена применению оптимальной рекомбинации в ГА.

В разделе 5.1 разработаны и исследованы генетический алгоритм и точный гибридный алгоритм для решения задачи наименьшего покрытия множества (ЗНП). Задача имеет следующую постановку. Пусть даны множество М = {1,..., т} и набор его подмножеств М) С М, где ] & и = {1,..., п}. Подмножество 3 С [/ называется покрытием М, если \Jjzj М) = М. Каждому М] приписан вес с^ > 0. Требуется найти покрытие минимального суммарного веса. ЗНП ОТ-трудна в сильном смысле. Кроме того, существование алгоритма полиномиальной трудоемкости, который гарантированно находит решение, не более чем в константу раз превышающее оптимум, влечет P—NP.

Для ЗНП предлагается новый вариант ГА (вА№) с недвоичным представлением решений и оператором ЛП-кроссинговера, при действии которого ослабленная ЗОР решается с использованием методов линейного программирования. Кроме того, в данном разделе описывается гибридный алгоритм решения ЗНП, который представляет собой комбинацию метода перебора ¿-классов с СА№ и эвристикой лагранжевой релаксации. ГА используется для нахождения начального решения, а с помощью метода лагранжевой релаксации строятся нижние и верхние оценки целевой функции на начальном этапе и на подзадачах, возникающих в процессе перебора ¿-классов.

При решении задач библиотеки СШ-ЫЬгагу предложенный ГА показал результаты, пе уступающие результатам ГА с двоичным представлением Л.Веавку и Р.СДш. В частности, для всех 50 тестовых задач со случайно сгенерированными данными при размерности до 5000 переменных данным ГА найдены оптимальные решения. Кроме того, для двух индивидуальных задач, связанных с вопросом Р.Егёбв о раскраске гиперграфа, получены решения, улучшающие известные из литературы.

Эксперимент показал, что применение ЛП-кроссипговсра в целесо-

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

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

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

т п

min ^ ' ^ ^ Zijdij -Ь СуЖу, »=1 j=i

m

'У ] Xij > Aj, j = 1,..., n,

¿=1

n

"SPXjj < Mi, i = l,...,m,

j=i

Zij e {0,1}, % = l,...,m, j = l,...,n,

rriijZij < Xij < Miz^, i = 1,..., m, j = 1,..., n,

где тп - число поставщиков; n - число потребителей; неременные Zy являются индикаторами наличия поставки от поставщика г потребителю j, а переменные х^ обозначают размер соответствующей поставки. Aj - минимальное количество продукта, требуемое потребителю j; m,j - минимальное количество продукта, которое поставщик г готов доставить потребителю j; Mi - максимальное общее количество продукта, которое поставщик г может доставить. В целевую функцию входят фиксированные доплаты а^, связанные с открытием поставки (i,j) и стоимости транспортировки единицы продукции Су. Параметры aij,Cij,rriij, Mi, Aj целочислснпы и неотрицательны при всех г, j.

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

Для случая п = 1 в данном разделе предложен жадный алгоритм трудоемкости 0(т2) и доказано, что он является 2-приближенным алгоритмом,

если стоимость поставки от каждого поставщика г является вогнутой неубывающей функцией на отрезке [О, МЦ (теорема 5.2). В [7] нами предложена РРТАЭ для случая п = 1 в более общей постановке, где предполагается, что объем поставки от каждого поставщика принадлежит объединению конечного числа отрезков, функции стоимости поставок являются вогнутыми и неубывающими в пределах каждого интервала. В [13] построена РРТАБ для более широкого класса непрерывных целевых функций.

Для рассматриваемой задачи предлагаются два гибридных генетических алгоритма и проводится их исследование и сравнение. Первый из предложенных ГА, обозначаемый через GAgrd, основывается на декодировании генотипов с использованием жадного 2-приближенного алгоритма.

Во втором предложенном ГА, обозначаемом через САгшрг, генотип представляет собой (т х п)-матрицу Ъ = (г^). Если при заданной Z допустимое решение существует, то объемы поставок х^ вычисляются посредством решения транспортной задачи с нижними и верхними ограничениями на объем каждой перевозки. Если же такого решения не существует, то для оценки приспособленности используется штрафная функция.

В САппрг разработан новый оператор ЦЛП-кроссинговера, в котором перед решением ЗОР в родительские генотипы вносятся случайные изменения. После этого решается (ослабленная) ЗОР для задачи управления поставками продукции в приведенной выше постановке частично целочисленного линейного программирования (ЧЦЛП). Из теоремы 3.3 вытекает, что ЗОР и ослабленная ЗОР для задачи управления поставками продукции являются ОТ-трудными даже в случае одного потребителя. Оператор ЦЛП-кроссинговера реализован с использованием метода ветвей и границ из пакета СРЬЕХ.

Вычислительный эксперимент показал, что при заданном ограничении на время вычислений САгшрг имеет преимущество по качеству получаемых решений в сравнении с GAgrd и пакетом СРЬЕХ.

В разделе 5.3 рассматривается NP-тpyднaя задача балансировки автоматизированной производственной линии и предлагается ГА с оператором ЦЛП-кроссинговера для ее решения. Исследуемая задача имеет ряд отличий от известной задачи балансировки автоматической сборочной линии, таких как параметризованное время выполнения операции, нестрогие отношения предшествования и параллельное выполнение операций.

В предлагаемом ГА применяется стационарная стратегия управления по-

иуляцией и турнирная селекция. В качестве генотипа используется совокупность булевых переменных в терминах модели А.Б.Долгого и соавт., кодирующая назначение операций на блоки и станции. Генотипы начальной популяции формируются случайным образом посредством TV-кратного применения эвристики GRASP, также реализованной с использованием модели ЧЦЛП.

Действие ЦЛП-кроссинговера состоит в решении ЗОР, получаемой фиксацией значений части булевых переменных в исходной задаче. Как следует из теоремы 3.3, данная ЗОР является NP-трудпой задачей.

В вычислительном эксперименте с предложенным ГА сравнивались эвристические и точные алгоритмы, разработанные О.Н.Гущипской, Н.Н.Гущинским и А.Б.Долгим, а также эвристика GRASP и метод ветвей и границ с отсечениями из пакета CPLEX.

Эксперименты [19,30J показали перспективность использования ЗОР в ГА для рассматриваемой задачи и позволили выявить классы задач, на которых ГА с ЦЛП-кроссинговером имеет преимущество перед другими известными алгоритмами. Важной отличительной особенностью данного подхода является возможность его применения к широкому классу задач за счет использования гибких средств построения моделей ЧЦЛП и универсальных пакетов программ для решения такого рода задач.

Результаты пятой главы дают экспериментальное подтверждение целесообразности решения ЗОР в операторах кроссинговера генетических алгоритмов даже в тех случаях, когда ЗОР является NP-трудной задачей. Результаты этой главы опубликованы в [2,6,10,11,24,27,28,30,31,36].

В заключении приведены основные результаты диссертации.

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

[1[ Борисовский П. А., Еремеев А. В. О сравнении некоторых эволюционных алгоритмов // Автомат, и тслемех. - 2004. - № 3. - С. 3-9.

[2] Еремеев А. В. Генетический алгоритм для задачи о покрытии // Дискрет, анализ и исслед. операций. Сер. 2. - 2000. - Т. 7. - X'- 1. - С. 47-60.

[3J Еремеев А. В. Вполне полиномиальная рандомизированная анпроксима-ционная схема на основе эволюционного алгоритма // Дискрет, анализ и исслед. операций. - 2010. - Т. 17. - № 4. - С. 3-17.

[4] Еремеев А. В. О сложности оптимальной рекомбинации для задачи коммивояжера // Дискрет, анализ и исслед. операций. - 2011. - Т. 18. - № 1. - С. 27-40.

Еремеев А. В. Генетический алгоритм с турнирной селекцией как метод локального поиска // Дискрет, анализ и исслед. операций. - 2012. - Т. 19.

- № 2. - С. 41-53.

Еремеев А. В., Заозсрская Л. А., Колоколов А. А. Задача о покрытии множества: сложность, алгоритмы, экспериментальные исследования // Дискрет. анализ и исслед. операций. Сер. 2. - 2000. - Т. 7. - № 2. - С. 22-46.

Еремеев А. В., Ковалев М. Я., Кузнецов П. М. Приближенное решение задачи управления поставками со многими интервалами и вогнутыми функциями стоимости // Автомат, и телемех. - 2008. - № 7. - С. 90-97.

Еремеев А. В., Коваленко Ю. В. О задаче составления расписаний с группировкой машин по технологиям // Дискрет, анализ и исслед. операций.

- 2011. - Т. 18. - № 5. - С. 54-79.

Еремеев А. В., Коваленко Ю. В. О сложности оптимальной рекомбинации для одной задачи составления расписаний с переналадками // Дискрет, анализ и исслед. операций. - 2012. - Т. 19. - № 3. - С. 13-26.

Еремеев А. В., Романова А. А., Сервах В. В., Чаухан С. С. Приближенное решение одной задачи управления поставками // Дискрет, анализ и исслед. операций. Сер. 2. - 2006. - Т. 13. - № 1. - С. 27-39.

Borisovsky P., Dolgui A., Eremeev A. Genetic algorithms for a supply management problem: MIP-recombination vs greedy decoder // Europ. Journ. of Operational Research - 2009. - Vol. 195. - N 3. - P. 770-779.

Borisovsky P. A., Eremeev A. V. Comparing evolutionary algorithms to the (1 I 1)-EA // Thcorct. Computer Scicncc - 2008. - Vol. 403. - N 1. - P. 33-41.

Chauhan S. S., Eremeev A. V., Romanova A. A., Servakh V. V., Woeginger G. J. Approximation of the supply scheduling problem // Operations Research Letters - 2005. - Vol. 33. - N 3. - P. 249-254.

Doerr В., Eremeev A., Neumann F., Theile M., Thyssen C. Evolutionary algorithms and dynamic programming // Theorct. Computer Science - 2011.

- Vol. 412. - N 43. - P. 6020-6035.

Dolgui A., Eremeev A., Kolokolov A., Sigaev V. A Genetic Algorithm for the Allocation of Buffer Storage Capacities in a Production Line with Unreliable Machines // Journ. of Mathematical Modelling and Algorithms. - 2002. - Vol. 1.

- N 2. - P. 89-104.

Dolgui A., Eremeev A. V., Kovalyov M. Y., Kuznetsov P. M. Multi-product lot sizing and scheduling on unrelated parallel machines // IIE Transactions.

- 2010. - Vol. 42. - N 7. - P. 514-524.

Dolgui A., Eremeev A. V., Sigaev V. S. HBBA: hybrid algorithm for buffer allocation in tandem production lines // Journ. of Intelligent Manufacturing.

- 2007. - Vol. 18. - N 3. - P. 411-420.

Eremeev A. V. On complexity of optimal recombination for binary representations of solutions // Evolutionary Computation. - 2008. - Vol. 16.

- N 1. - P. 127-147.

Guschinskaya O., Gurevsky E., Dolgui A., Eremeev A. Metaheuristic approaches for the design of machining lines // The Intern. Journ. of Advanced Manufacturing Technology. - 2011. - Vol. 55. - N 1-4. - P. 11-22.

[20] Reeves С. R., Eremeev A. V. Statistical analysis of local search landscapes // Journ. of the Operational Research Soc. - 2004. - Vol. 55. - N 7. - P. 687-693.

Главы монографий, статьи в трудах конференций и препринты

[21] Долгий А., Еремеев А. В. О сложности оптимальной рекомбинации для задачи об одномерной упаковке в контейнеры // Материалы VIII международной научно-технической конференции «Динамика систем, механизмов и машин». - Омск: Изд-во ОмГТУ, 2012. - Кн. 3. - С. 25-27.

[22] Еремеев А. В. О связи динамического программирования и многокритериальных эволюционных алгоритмов: препринт. - Омск: Изд-во ОмГУ, 2008. - 20 с.

[23] Еремеев А. В. Эволюционные алгоритмы с возможностями динамического программирования // IV Всероссийская конференция «Проблемы оптимизации и экономические приложения»: материалы конференции. - Омск: Полигр. центр КАН, 2009. - С. 35-39.

[24] Borisovsky P., Dolgui A., Eremeev A. Genetic algorithms for supply management problem with lower-bounded demands // Information Control Problems in Manufact.: Proc. of 12th IFAC Intern. Syinp. / Ed. by Dolgui A. [et al.]. - St Etienne: Elsevier Science, 2006. - Vol. 3. - P. 521-526.

[25] Borisovsky P. A., Eremeev A. V. On performance estimates for two evolutionary algorithms // Applications of Evolutionary Computing: Proc. of EvoWorkshops 2001 / Ed. by Boers E. J. W. [et al.]. - Berlin: Springer-Verlag, 2001. - P. 161171. - (Lect. Notes Comput. Sci.; Vol. 2037).

[26] Borisovsky P. A., Eremeev A. V. A study on performance of the (l+l)-evolu-tionary algorithm // Foundations of Genetic Algorithms 7 / Ed. by De Jong K., Poli R., Rowe J. - San Francisco: Morgan Kaufmann, 2003. - P. 271-287.

[27] Chauhan S. S., Eremeev A. V., Kolokolov A. A., Servakh V. V. Concave cost supply management for single manufacturing unit // Supply chain optimisation. Product/process design, factory location and flow control. - N. Y.: SpringerVerlag, 2005. - P. 167-174. - (Applied Optim.; Vol. 94).

[28] Chauhan S. S., Eremeev A. V., Romanova A.A., Servakh V. V. Approximation of linear cost supply management problem with lower-bounded demands // Proc. of Discrete Optimization Methods in Production and Logistics (DOM'2004). - Omsk: Nasledie Dialog-Sibir, 2004. - P. 16-21.

[29] Doerr В., Eremeev A., Horoba C., Neumann F., Theile M. Evolutionary algorithms and dynamic programming // Proc. of Genetic and Evolutionary Comput. Conf. (GECCO). - New York: ACM Press, 2009. - P. 771-777.

[30] Dolgui A., Eremeev A., Guschinskaya O. MlP-based GRASP and genetic algorithm for balancing transfer lines // Matheuristies. Hybridizing Metaheuristics and Mathematical Programming / Ed. by Maniezzo V., Stutzle Т., Voss S. - Berlin: Springer-Verlag, 2010. - P. 189-208.

[31] Eremeev A. V. A Genetic algorithm with a non-binary representation for the set covering problem // Proc. of Operations Research (OR'98). - Berlin: SpringerVerlag, 1999. - P. 175-181.

[32] Eremccv A. V. Modeling and analysis of genetic algorithm with tournament selection // Proc. of Artificial Evolution Conference (AE'99) / Ed. by Fonlupt C. [et al.J - Berlin: Springer Verlag, 2000. - P. 84-95. - (Lect. Notes Comput. Sei.; Vol. 1829).

[33] Eremcev A. V. On complexity of optimal recombination for the travelling salesman problem // Proc. of Evolutionary Computation in Combinatorial Optimization (EvoCOP 2011) / Ed. by Merz P., Hao J.-K. - Berlin: Springer Verlag, 2011. - P. 215-225. - (Lect. Notes Comput. Sei.; Vol. 6622).

[34] Ercmecv A. V. Non-elitist gcnctic algorithm as a local search method: Preprint (arXiv:1307.3463v2 [cs.NE]). - Cornell: Cornell University, 2013. - 9 p. URL: http://arxiv.org/abs/1307.3463.

[35] Eremccv A. V., Kolokolov A. A. On some genetic and L-class enumeration algorithms in integer programming // Proc. of the First International Conference on Evolutionary Computation and its Applications. -Moscow: Russian Acadcmy of Sciences, 1996. - P. 297-303.

[36] Eremccv A. V., Kolokolov A. A., Zaozerskaya L. A. A hybrid algorithm for set covering problem // Proc. of International Workshop on Discrete Optimization Methods in Scheduling and Computer-Aided Design. - Minsk: National Academy of Sciences Belarus, 2000. - P. 123-129.

[37] Eremccv A. V., Reeves C. R. Evolutionary algorithms in discrete optimisation // Book of abstracts of Discrete Analysis and Opcr. Res. Conf. - Novosibirsk: Institute of Mathematics, 2002. - P. 40-45.

[38] Eremccv A. V., Reeves C. R. On confidence intervals for the number of local optima // Applications of Evolutionary Computing: Proc. of EvoWorkshop 2003 / Ed. by Raidl G. R. [et al.] - Heidelberg: Springer-Verlag, 2003. - P. 224-235. - (Lcct. Notes Comput. Sci.; Vol. 2611).

Подписано в печать 24.10.2013. Формат 60x84/16. Бумага офсетная. Оперативный способ печати. Усл. печ. л. 2,0. Тираж 100 экз. Заказ № 646.

Отпечатано в «Полиграфическом центре КАН» тел. (3812) 24-70-79, 8-904-585-98-84.

E-mail: pc_kan@mail.ru 644050, г. Омск, ул. Красный Путь, 30 Лицензия ПЛД № 58-47 от 21.04.97

РОССИЙСКАЯ АКАДЕМИЯ НАУК СИБИРСКОЕ ОТДЕЛЕНИЕ

Омский филиал Федерального государственного бюджетного учреждения науки Института математики им. С.Л. Соболева Сибирского отделения

Российской академии наук

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

05201 450^1

ЕРЕМЕЕВ Антон Валентинович

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

05.13.17 — теоретические основы информатики

Диссертация на соискание ученой степени доктора физико-математических наук

Научный консультант д.ф.-м.н., профессор Колоколов А. А.

Омск 2013

Оглавление

Введение 4

1 Постановки задач и схемы эволюционных алгоритмов 40

1.1 Задачи комбинаторной оптимизации.............. 40

1.2 Эволюционные алгоритмы.................... 47

2 Исследование эволюционных алгоритмов с позиций локальной оптимизации 65

2.1 Генетический алгоритм как метод локального поиска .... 65

2.2 Динамика численности особей с высокой приспособленностью в популяции генетического алгоритма.......... 74

2.3 Сравнение эволюционных алгоритмов с эволюционной стратегией (1+1)-ES.......................... 95

2.4 Статистические оценки числа локальных оптимумов..... 104

3 Исследование сложности задачи оптимальной рекомбинации 114

3.1 Постановка задачи........................ 114

3.2 Полиномиально разрешимые случаи.............. 118

3.3 NP-трудные случаи........................ 132

4 Построение эволюционных алгоритмов со свойствами динамического программирования 156

4.1 Формализация метода динамического программирования . . 157

4.2 Эволюционные алгоритмы на основе динамического программирования .......................... 169

4.3 Вполне полиномиальная рандомизированная аппроксимаци-

онная схема............................ 176

5 Применение оптимальной рекомбинации в генетических алгоритмах 188

5.1 Задача о наименьшем покрытии................ 188

5.2 Задача управления поставками продукции ..........216

5.3 Задача балансировки автоматизированной производственной линии ...............................244

Заключение 265

Литература 267

Введение

Актуальность темы. Задачи комбинаторной оптимизации находят широкое применение в информатике, технике, экономике, планировании и других областях. В настоящее время в комбинаторной оптимизации интенсивно развивается подход, основанный на бионическом принципе моделирования эволюционных процессов адаптации в живой природе. Эволюционные методы успешно применяются в информационных технологиях проектирования, планирования, управления, распознавания образов и т.д. Этим методам посвящено большое число работ как отечественных авторов (Д.И. Батищев, И.Л. Букатова, Н.Г. Загоруйко, А.Г. Ивахненко, Ю.А. Кочетов, Г.С. Лбов, В.М. Курейчик, И.П. Норенков, Ю.И. Неймарк, Л.А. Рас-тригин, В.Г. Редько, Е.С. Семенкин и др.) [7,8,18,55,74,76,81,84,88,89,95], так и зарубежных (Э. Балаш, Д. Голдберг, Дж. Холланд, И. Реченберг, М. Шоно, П. Витани, М. Воз, И. Вегенер) [122,132,197,213,266,288,289].

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

Важное место в комбинаторной оптимизации занимает проблема™-

ка целочисленного программирования, которая включает вопросы, связанные с теорией двойственности, полиэдральным подходом, методами отсечения, ветвей и границ, декомпозиции, множителей Лагранжа, выпуклым и невыпуклым программированием, устойчивостью решений и т.д. Исследованию данной проблематики посвящены работы Дж. Бендер-са, B.JI. Береснева, В.П. Булатова, Р. Гомори, Дж. Данцига, В.Т. Дементьева, Ю.Г. Евтушенко, В.А. Емеличева, И.И. Еремина, М.М. Ковалева, A.A. Колоколова, В.К. Леонтьева, Вл.Д. Мазурова, Дж. Немхаузе-ра, И.В. Сергиенко, A.C. Стрекаловского, Д. Фалкерсона, В.Н. Шевченко, Дж. Эдмондса и многих других авторов как в России, так и за рубежом [11,12,19,32,33,45,78,97,103,106,187]. В ряде известных методов решения задач целочисленного программирования используется сведение исходной задачи к последовательности задач непрерывной оптимизации. На этом подходе основаны методы отсечения, декомпозиции, ветвей и границ, алгоритмы перебора L-классов и др. [49,63-66,93]. Актуальной проблемой при исследовании таких методов является построение нижних и верхних оценок числа итераций, в том числе оценок в среднем. Важные результаты в этом направлении получены Е. Вентой, В.П. Гришухиным, Р. Джерослоу, O.A. Заблоцкой, Л.А. Заозерской, A.A. Колоколовым, H.H. Кузюриным, X. Ленстрой, Ю.Ю. Финкелынтейном [26,28,48,53,67,69,75,221,235,252].

При решении задач комбинаторной оптимизации широко используется метод динамического программирования, предложенный Р. Беллма-ном [130], и его обобщения. Актуалные вопросы распараллеливания, преодоления больших затрат памяти, разработки гибридных алгоритмов, анализа графовых интерпретаций динамического программирования и решения многокритериальных задач в рамках данного подхода рассматриваются в работах У. Бертеле, Ф. Бриоши, В.В. Быковой, 3. Галил, Г.Г. За-будского, A.B. Кельманова, Д.И. Когана, H.H. Моисеева, В.В. Серваха, Н.З. Шора, O.A. Щербины [20,49,57,61,79,80,104,131,142,188] и других

авторов.

Среди первых методов решения задач комбинаторной оптимизации наряду с методами отсечений, динамического программирования и ветвей и границ возникли методы локального поиска и локальные алгоритмы [47, 87, 204, 236]. В нашей стране основоположниками этого направления стали Ю.И. Журавлев, который ввел в рассмотрение класс локальных алгоритмов и провел анализ их сложности [46], и Л.А. Растри-гин, предложивший и исследовавший рандомизированные алгоритмы локального поиска [87], а также И.В. Сергиенко, развивший метод вектора спада и обосновавший его работоспособность [93]. Значительные результаты в исследовании возможностей методов локального поиска получены А.Н. Антамошкиным, Б. Керниганом, Ю.А. Кочетовым, С. Лином, X. Пападимитриу, О.Э. Семенкиной, С. Товеем, М. Яннакакисом и другими [72,86,96,113,275,296].

Приближенные алгоритмы решения задач комбинаторной оптимизации оказываются незаменимыми в ситуациях, когда получение точного решения требует чрезмерных временных затрат. Значительный вклад в область разработки и анализа приближенных алгоритмов внесли A.A. Агеев, С. Apopa, Э.Х. Гимади, Н.И. Глебов, Д. Джонсон, A.A. Корбут, Г. Кор-нужолс, Б. Корте, Л. Ловас, В.А. Перепелица, В.К. Попков, П. Рагхаван, И.Х. Сигал, К. Томпсон, М.Ю. Хачай, Д. Хочбаум [2,23,27,31,82,92,102,115, 212,216,230] и ряд других авторов. В настоящее время интенсивно исследуются вопросы существования полиномиальных аппроксимационных схем и их трудоемкости. Существенные результаты в этом направлении получили Г. Воегингер, Г.В. Гене, О. Ибарра, М.Я. Ковалев, В. Кубик, Е.В. Левнер, C.B. Севастьянов, Я.М. Шафранский [21,22,60,215,233,293] и др.

Эволюционные алгоритмы (ЭА) берут начало в работах Л. Фогеля, А. Оуэнса и М. Уолша [101] и Дж. Холланда [213], где было предложено моделировать процесс биологической эволюции с целью синтеза эффектив-

ных в некотором смысле структур и создания систем искусственного интеллекта. В нашей стране А.Г. Ивахненко и Л.А. Растригиным независимо были предложены методы случайного поиска, где также использовались идеи эволюции [55,265]. Характерной особенностью ЭА является имитация процесса эволюционной адаптации биологической популяции к условиям окружающей среды, при этом особи соответствуют пробным точкам в пространстве решений задачи оптимизации, а приспособленность особей определяется значениями целевой функции и штрафами за нарушение ограничений задачи, если такие имеются. В рамках данного подхода предложены эволюционные стратегии [266], генетические алгоритмы [213], алгоритмы случайного поиска с адаптацией [76], эволюционного моделирования [18,101]), генетического программирования [231], многокритериальные ЭА [257]. К классу ЭА также могут быть отнесены алгоритмы Метрополи-са [248], имитации отжига [227], поиска с запретами [194] и др. Указанные алгоритмы различаются способами моделирования эволюционного процесса и отражаемыми аспектами, однако имеют много общих элементов. Области применения этих алгоритмов также несколько различаются.

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

комбинаторной оптимизации, возникающих в управлении, планировании, проектировании, распознавании образов и других областях (см., например, [84,90,161,163]).

О применимости ЭА к индивидуальной задаче комбинаторной оптимизации естественно судить по математическому ожиданию времени первого достижения оптимального решения или достаточно точного приближенного решения. Эти средние значения могут быть оценены снизу и сверху функциями от длины записи исходных данных задачи, что позволяет делать вывод об эффективности ЭА на задаче комбинаторной оптимизации в целом. Необходимо отметить, что существование ЭА, обнаруживающего оптимальное решение какой-либо ИР-трудной задачи в среднем за время, полиномиально ограниченное сверху, представляется маловероятным (это противоречило бы предположению о неравенстве классов NP ф ЯР, которое длительное время принимается в теории сложности в качестве рабочей гипотезы [229]).

Теоретически наиболее детально исследованы эволюционные алгоритмы с достаточно простыми (как правило, линейными по трудоемкости) операторами мутации и кроссинговера [248]. Как выяснилось, базовые схемы эволюционных алгоритмов при подходящем способе представления решений и настройках параметров могут воспроизводить основные этапы работы известных алгоритмов дискретной оптимизации. Значимые результаты в данном направлении получены при анализе ЭА для таких классических задач дискретной оптимизации, как задача о кратчайшем пути в графе [279], задача об остовном дереве минимального веса [249] и задача о разрезе минимального веса [247]. Оптимальные решения этих задач могут быть получены в среднем за полиномиальное время при помощи многокритериальных эволюционных алгоритмов, воспроизводящих работу алгоритмов Дейкстры и Краскала, или неявно учитывающих двойственность задач о минимальном разрезе и максимальном потоке. ЭА с аналогичны-

ми свойствами найдены и для некоторых других задач [157,186,193,248]. Вместе с тем недостает обобщающих результатов об эффективности ЭА на крупных классах задач, а также теоретически обоснованных выводов о преимуществе одного ЭА над другим на некотором классе задач.

На практике попытки применения стандартных ЭА без учета специфики решаемых задач достаточно быстро показали их низкую эффективность в сравнении со специализированными алгоритмами. Тем не менее гибкость вычислительных схем ЭА и возможности их комбинирования с другими методами позволили разработать конкурентоспособные гибридные алгоритмы. В таких алгоритмах отдельные операторы представляют собой уже известные алгоритмы, такие как локальный поиск, жадный алгоритм, метод ветвей и границ или перебор ¿-классов (см., например, [74,84,163,177]). Для некоторых гибридных ЭА удается и теоретически гарантировать качество получаемого решения благодаря свойствам используемых в них классических методов [163,177]. К сожалению, в большинстве случаев обоснование работоспособности гибридных ЭА ограничивается применением теоремы Е. Аартс, А. Айбен и К. ван Хи о сходимости к оптимуму «почти наверное» [277], предъявляющей достаточно слабые требования к операторам ЭА, но не дающей оценок сверху на время достижения оптимума. Для выхода из создавшейся ситуации требуется получение оценок времени отыскания решений требуемой точности и вероятности порождения достаточно точных решений на заданной итерации ЭА.

Работоспособность генетического алгоритма (ГА) существенно зависит от выбора оператора кроссинговера, где комбинируются элементы родительских решений. Новым направлением исследований является анализ сложности и разработка эффективных алгоритмов решения задачи оптимальной рекомбинации (ЗОР), состоящей в отыскании наилучшего возможного результата кроссинговера при заданных родительских генотипах. Результаты Ч. Аггарвала, Э. Балатла, В. Кука, Дж. Орлина, П. Сеймура

и др. [42,108,122,147,160,195] дают экспериментальное подтверждение целесообразности решения ЗОР (точного или приближенного) в операторах кроссинговера. Тем не менее до сих пор не было проведено систематического анализа вычислительной сложности ЗОР и эффекта от ее решения в процессе работы ЭА.

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

1) разработка эволюционных алгоритмов и их гибридных вариантов с использованием классических методов комбинаторной оптимизации;

2) оценка точности решений, получаемых эволюционными алгоритмами, построение оценок трудоемкости этих алгоритмов и их основных операторов, сопоставление полученных оценок с известными аналогами;

3) анализ сложности задач комбинаторной оптимизации, и в частности, задач оптимальной рекомбинации, оценивание параметров задач, влияющих на работоспособность ЭА.

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

Научная новизна. Введена в рассмотрение общая постановка задачи оптимальной рекомбинации в терминах задач комбинаторной оптимизации; предложен метод построения сводимостей ЗОР, подобных известным сводимостям задач комбинаторной оптимизации, позволивший доказать полиномиальную разрешимость или КР-трудность ЗОР для различных задач. Разработана методика использования в ГА операторов кроссинговера, основанных на решении ЗОР, что дало возможность улучшить известные ранее экспериментальные результаты для ряда задач.

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

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

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

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

На защиту выносятся следующие основные результаты.

1. Проведено комплексное исследование эволюционных методов с позиций локальной оптимизации: найдены необходимые и достаточные условия, при которых рандомизированный вариант локального поиска является наилучшим методом по вероятности отыскания оптимума в классе эволюционных алгоритмов с заданным оператором мутации; найдены достаточные условия, при которых генетический алгоритм с турнирной селекцией достигает локальный оптимум в среднем за полиномиально ограниченное время, и показано выполнение этих условий на классе задач СЬО; предложены статистические методы нахождения нижних оценок числа локальных оптимумов задачи.

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