Содержание к диссертации
Введение
1 Общее описание проблематики 4
2 Проблемы, решаемые в диссертации 6
2.1 Используемые подходы 6
2.2 Амальгамы подклассов CSP 7
2.3 Эффективность алгоритма Локальный Поиск . 9
2.4 Алгоритм VEGAS 12
1 Амальгамы подклассов CSP 15
1.1 Основные определения теории клонов и теории задачи CSP 15
1.1.1 Задача CSP 15
1.1.2 Клоны 17
1.1.3 Амальгамы клонов 20
1.2 Строение клона функций, сохраняющих амальгаму 21
1.2.1 Случай дизъюнктных множеств 21
1.2.2 Общий случай 24
1.3 Склеивание двух клонов 28
1.4 Критерий полиномиальности амальгамы 33
1.4.1 О мощности множества С 34
1.4.2 Случай монолитности одного из клонов 36
1.4.3 Канонический вид задачи 38
2 Эффективность Локального Поиска 52
2.1 Основные определения 52
2.1.1 Задача Выполнимость и Локальный Поиск 52
2.1.2 Теорема Вормальда 55
2.2 Локальный Поиск за Один Просмотр 56
2.2.1 Модель 56
2.3 Локальный Поиск 66
2.3.1 Модель 66
2.3.2 Эксперименты 72
Оглавление
Алгоритм VEGAS 78
3.1 Основные определения 78
3.1.1 Взвешенная Максимальная Выполнимость 78
3.1.2 Генетические алгоритмы 80
3.2 Описание алгоритма VEGAS 81
3.2.1 Эволюция среды обитания 82
3.2.2 Моделирование социальной структуры популяции . 83
3.2.3 Алгоритм TabuSearch 83
3.3 Результаты экспериментов 87
3.3.1 Сравнение эффективности VEGAS и GASAT . 87
3.3.2 Исследование влияния социальной структуры популяции на эффективность вычисления Литература
- Эффективность алгоритма Локальный Поиск
- Строение клона функций, сохраняющих амальгаму
- Задача Выполнимость и Локальный Поиск
- Взвешенная Максимальная Выполнимость
Введение к работе
1 Общее описание проблематики
С расширением области применения компьютерных технологий появля
ется потребность в решении все большего количества комбинаторных
задач. В связи с этим возникает естественное стремление разработать
универсальные алгоритмы, способные решать как можно более широкие
классы задач. При этом желательно, .чтобы универсальный алгоритм при
решении конкретных задач был бы сравним по затратам ресурсов с наи
лучшим возможным алгоритмом. , _ „
Мы будем использовать стандартные определения комбинаторной задачи, класса задач NP, сведения, полиномиальности и NP-полноты задачи, см. например [1, 56]. Данная работа относится к исследованию комбинаторной задачи CSP (От английского 'Constraint Satisfaction Problem', в немногочисленной русскоязычной литературе встречается также название 'Обобщенная выполнимость'). Цель данного направления — разработать эффективные универсальные алгоритмы для задач из класса NP. Задача CSP является лишь одной из многих известных NP-полных задач, однако в последнее десятилетие стало ясно, что она занимает особое место. Сведение задачи к NP-полной очень часто оказывается громоздким и искусственным. Преимущество задачи CSP состоит в том, что большинство комбинаторных задач может быть представлено в виде CSP просто и естественно. Многие комбинаторные задачи могут быть естественным образом охарактеризованы как подклассы задачи CSP. Теория задачи CSP находит свое применение в таких областях как теория реляционных баз данных [43, 65], временная и пространственная логика [62], распознавание зрительных образов [52], автоматическое доказательство теорем [16], техническое проектирование [55], анализ языков программирования [54] и естественных языков [4], биоинформатика [45] и многих
ВВЕДЕНИЕ
других.
Формулируется задача CSP следующим образом. Пусть даны множество переменных V и множество их возможных значений D. Ограничением называется пара, состоящая из вектора переменных (vi,..., г^) и отношения р С Dk. Говорят, что функция ф : V —> D, ставящая в соответствие переменным их значения, удовлетворяет ограничению ({vi,..., v/-), р), если вектор (Ф(уі), ..., ф(ьк)) содержится в отношении р. В конкретной задаче CSP даны множества V и D, а также некоторое множество ограничений С Требуется указать значения переменных (т. е. выбрать функцию ф : V —* D) так, чтобы удовлетворялись все ограничения из С.
Впервые общая задача CSP была введена Монтанари в 1974 г. [52] при решении одной из задач машинного зрения — распознавания формы многогранников по их двумерному изображению. В последующие годы этот формализм был активно использован для моделирования прикладных задач, а затем и разработки универсальных алгоритмов для их решения. В настоящее время существуют специальные декларативные языки программирования: ECLiPSc[5j, Oz[59], 2LP[50], СНІР[30] и Newton[31], в которых для решения задачи достаточно записать ее в виде CSP, существуют библиотеки с подобной функциональностью для C++ (например ILOG[58]), расширениями, позволяющими решать задачу CSP, снабжено большинство современных версий Prolog[53].
Частным случаем задачи CSP, в котором множество значений переменных двухэлементно, а разрешенные ограничения — дизъюнкции ли-тералов(клозы), является задача ВЫПОЛНИМОСТЬ, одна из первых задач, NP-полнота которых была доказана. Задача ВЫПОЛНИМОСТЬ представляет самостоятельный интерес, так как формулируется она проще, чем CSP, и в то же время сведение задачи CSP к задаче ВЫПОЛНИМОСТЬ не составляет труда.
Сама задача ВЫПОЛНИМОСТЬ является в настоящее время объектом активного исследования. Ей посвящена ежегодная конференция SAT (это название является сокращением от SATISFIABILITY — английского названия задачи ВЫПОЛНИМОСТЬ), проводящаяся с 1996-го года. С 2005-го года выпускается журнал JSAT. Важное место в исследовании задачи ВЫПОЛНИМОСТЬ занимает разработка реально работающих программ-решателей. При конференции SAT регулярно проходит соревнование таких программ, в котором принимают участие десятки программных продуктов, созданных учеными со всего мира. Прогресс, достигнутый в разработке алгоритмов для практических задач, огромен:
ВВЕДЕНИЕ
многие задачи, еще 10 лет назад считавшиеся практически неразрешимыми, современными программами могут быть решены за доли секунды.
Возможный путь решения задачи CSP — это сведение ее к задаче ВЫПОЛНИМОСТЬ и использование эффективных эвристических алгоритмов. Однако, богатый язык общей задачи CSP позволяет сохранить при моделировании структуру исходной задачи, что дает ряд преимуществ. Во-первых, как было отмечено выше, многие задачи могут быть естественным образом охарактеризованы как ограниченные задачи CSP. Например, /с-раскраска графа — это в точности задача CSP на fc-элементном множестве, в которой в качестве отношения ограничения используется только неравенство. Во-вторых, большая структурированность задачи позволяет перенести в теорию CSP и обобщить алгоритмы, разработанные для других комбинаторных задач. Кроме того, язык задачи CSP оказывается проще для понимания, поэтому запись задачи в виде CSP на практике оказывается предпочтительнее кодирования в виде задачи ВЫПОЛНИМОСТЬ с точки зрения взаимодействия с заказчиком при моделировании предметной области.
Литература, появившаяся за десятилетия изучения задачи CSP, весьма обширна и рассматривает широчайший круг вопросов. Не пытаясь охватить всю литературу, посвященную задаче CSP, в следующем разделе мы осуществляем обзор только тех работ, которые непосредственно касаются проблем, решаемых в данной диссертации.
2 Проблемы, решаемые в диссертации
2.1 Используемые подходы
Для CSP, как и любой NP-полной задачи, не известно алгоритмов эффективных в худшем случае, однако, существует несколько подходов, использование которых позволяет решить многие классы задачи CSP, возникающие в практических приложениях, за приемлемое время. Результаты данной работы относятся к трем из таких подходов.
Во-первых, на языке CSP могут быть сформулированы все задачи из класса NP, а значит и полиномиальные, поэтому важным направлением в исследовании задачи CSP является идентификация полиномиальных подклассов и разработка для них эффективных алгоритмов. В первой главе мы рассматриваем операцию амальгамирования классов задач CSP и устанавливаем критерий полиномиальности амальгамы.
ВВЕДЕНИЕ
Во-вторых, вероятностное распределение интересующей задачи может быть таковым, что существует алгоритм, получающий решение (или хорошее приближение решения) за приемлемое время с большой вероятностью. Во второй главе мы выясняем каково качество решения, которое с большой вероятностью находит базовый алгоритм Локального Поиска в применении к задаче ВЫПОЛНИМОСТЬ.
В-третьих, критерием эффективности алгоритма может быть его способность решить за приемлемое время конкретный набор задач. Классы задач, возникающие на практике, зачастую не представляется возможным описать как полиномиальное множество или задать для них адекватное вероятностное распределение. Поэтому тестирование является основным методом оценки практических алгоритмов. В третьей главе мы предлагаем эвристический алгоритм для задачи ВЫПОЛНИМОСТЬ, основанный на генетическом подходе, и устанавливаем его эффективность на наборе тестовых задач.
2.2 Амальгамы подклассов CSP
Естественный способ выделения подзадач CSP состоит в задании множества отношений, разрешенных для использования в ограничениях. Для каждого такого множества Г через СБР(Г) обозначается множество задач CSP, в которых множество отношений, заданное в условии, содержится в Г.
В 1978 году Шефер [61], изучая ограниченные классы задачи CSP на двухэлементном множестве, показал, что каждый такой класс либо NP-полон, либо имеет полиномиальный алгоритм, решающий его. Кроме того, он нашел критерий, разделяющий легкие и трудные задачи. В этой же работе Шефер поставил проблему поиска аналогичного критерия для общей задачи CSP: для каждого множества отношений Г определить сложность задачи СЭР(Г) и найти для нее полиномиальный алгоритм, если таковой существует. Множество отношений Г, для которого задача CSP(r) полиномиальна, называется полиномиальным.
Полиномиальные множества отношений могут быть заданы многими разными способами. Например, в [19], используя технику логического программирования и методы теории групп, удалось выявить два больших класса задач CSP, решаемых за полиномиальное время. В частности, в эти классы попадают все 'легкие' задачи CSP, найденные Шефе-ром. Иной подход был предложен в [38, 41], где полиномиальные мно-
ВВЕДЕНИЕ
жества задавались с помощью некоторых инвариантов. Этот подход был развит в [10, 11].
Предпринимались также попытки выделить классы задач CSP, которые могут быть сконструированы из более простых задач так, чтобы решение каждой конкретной задачи сводилось к решению составляющих ее компонент. Такому разложению могут быть подвергнуты как ди-офантовы формулы из задачи.CSP [14, 17, 21, 23, 24], так и множества отношений [12, 13].
В данной работе мы, следуя [12, 13], строим новые множества отношений с помощью операции амальгамирования. Амальгамой множеств отношений Ra, Rb на множествах Аи В соответственно, называется множество отношений R на множестве A U В, где
R = {ра^Рв | Ра Є Ra, Рв Є Rb-, причем, рл,рв — одинаковой арности}.
Как мы докажем ниже, задача CSP, соответствующая амальгаме двух множеств, не менее сложна чем ее составляющие, что, впрочем, интуитивно представляется истинным. Кроме того, амальгама двух полиномиальных множеств не всегда полиномиальна. Даже тогда, когда она полиномиальна, алгоритм, сводящий ее к составляющим, может быть весьма нетривиальным.
В [12] был рассмотрен случай, когда А и В дизъюнктны. В этом случае, при некоторых необременительных ограничениях амальгама полиномиальна тогда и только тогда, когда исходные множества полиномиальны, а алгоритм декомпозиции тривиален. В работе [13], в предположении равенства множеств, на которых заданы отношения, указано несколько частных типов полиномиальных амальгам, важных с прикладной точки зрения. В данной работе мы исследуем вопрос полиномиаль-ности амальгамы множеств отношений, области определения которых пересекаются, но не совпадают. Для полиномиальных случаев мы приводим соответствующие алгоритмы.
Для решения поставленной задачи мы используем методику, предложенную в [38, 41], опирающуюся на достижения теории клогюв.
Клоном функций называется множество функций, замкнутое относительно суперпозиции и содержащее все проекции, т.е. функции вида e'n(xi,... ,хп) = %і. Далее, каждому (n-местному) отношению р на А соответствует естественным образом (n-местный) предикат Рр. Это позволяет ввести следующее понятие. Множество отношений Г называется клоном отношений, если содержит отношение равенства, и для любых
ВВЕДЕНИЕ
рі,...,рк Є Г отношение р определяемое предикатом
Рр(хи ...,хп) = Зуі,..., утФ(хи ...,хп,у1,...,ут), (1)
где формула в правой части диофантова и ее атомарные формулы суть Рп,...,РРк, также содержится в Г. Говорят, что n-местная функция / сохраняет m-местное отношение р, если результат построчного применения / к любой матрице тхп, столбцами которой являются элементы р, принадлежит р. Множество всех функций, сохраняющих все отношения из Г, обозначается через Pol (Г); множество всех отношений, сохраняемых всеми функциями из С, обозначается через Inv(C). Как хорошо известно [57], множества вида Pol (Г) — это в точности, клоны функций, а вида Inv(C) — клоны отношений, причем операции Inv и Pol задают соответствие Галуа между решетками клонов функций и отношений.
Говорят, что конечное множество отношений Г полиномиально, если полиномиален класс задач CSP(r), а бесконечное множество отношений Г полиномиально, если полиномиальны все его конечные подмножества. Клоны отношений играют важную роль в изучении задачи CSP ввиду того, что, как было установлено в [38], если множество отношений Г полиномиально, то полиномиален и (Г) — клон отношений порожденный Г. В то же время полиномиальность клона отношений R может быть проверена по наличию определенных функций в клоне Pol (Л). В частности, благодаря такому подходу, для того, чтобы установить является ли класс задач СБР(Г) полиномиальным, достаточно проверить, сохраняют ли отношения из Г некоторые функции.
Мы начинаем исследование амальгамы клонов отношений с описания устройства соответствующего ей клона функций и выяснения в каких случаях клон отношений, порожденный амальгамой A(Ra,Rb), будучи суженным на А, В оказывается равным Ra,Rb соответственно. Далее, опираясь на полученные результаты, мы устанавливаем критерий по-линомиальности амальгамы и для полиномиальных случаев приводим алгоритмы, сводящие амальгаму к задачам из исходных классов.
2.3 Эффективность алгоритма Локальный Поиск
Оценка эффективности алгоритма с позиции анализа худшего случая зачастую не отражает ни результаты экспериментов, ни его практическую полезность. Классическим примером является алгоритм решения задач
ВВЕДЕНИЕ
линейного программирования: симплекс метод, являющийся экспоненциальным алгоритмом с точки зрения анализа худшего случая, используется на практике вместо известного полиномиального алгоритма.
Вероятностный анализ способен дать более адекватную оценку эффективности алгоритма. В этот анализ могут быть вовлечены два вероятностных пространства, во-первых, сам алгоритм может быть стохастическим и выдавать различные результаты в применении к одной и той же задаче, во-вторых, в анализе может быть учтено вероятностное рас-' пределение поступающих задач. Распространенным подходом является комбинирование этих пространств и вычисление вероятности того или иного результата при поступлении на вход стохастического алгоритма случайной задачи. Именно таким образом мы анализируем простейший вариант локального поиска в применении к задаче З-ВЫПОЛНИМОСТЬ.
Локальный поиск относятся к числу стандартных приемов, используемых для решения NP-полных. задач, в частности задачи ВЫПОЛНИМОСТЬ. В отличие от систематического поиска, в котором происходит выбор значений- переменных с откатом при появлении противоречия, в локальном поиске идет работа с векторами — наборами значений всех переменных. Начальный набор значений выбирается случайно, или следуя некоторой эвристике. Затем на каждом шаге новый набор значений выбирается случайным образом из окрестности текущего в соответствии с некоторым вероятностным распределением.
Локальный поиск — один из первых алгоритмов, использованных для решения задач Выполнимость и Максимальная Выполнимость. С конца восьмидесятых годов внимание исследователей привлекали разные версии алгоритма ЛП см., например [25, 60]. Алгоритм Unit Walk [33], построенный на принципах локального поиска, в 2003 году занял первое место в одной из номинаций соревнования SAT, являющегося самым крупным соревнованием программ-решателей задачи Выполнимость. Доказано [34], что некоторые варианты локального поиска даже в худшем случае находят решение задачи Выполнимость за время, ограниченное экспонентой от количества переменных, с основанием строго меньшим, чем 2. Алгоритмы GASAT и VEGAS (см. главу 3) используют для улучшения индивидов разновидность локального поиска алгоритм TabuSearch.
В данной работе мы исследуем эффективность одной из простейших версий локального поиска, известной также под названием Iterative
ВВЕДЕНИЕ
Improvement1 [37], при решении задачи Максимальная Выполнимость. В этом алгоритме мы начинаем со случайного набора значений переменных и затем на каждом шаге изменяем значение одной из переменных, для которых это приводит к увеличению количества выполненных клозов. Если таких переменных больше нет, то работа прекращается и возвращается найденный вектор. Таким образом, работа алгоритма заканчивается, когда текущий набор значений переменных оказывается локальным максимумом количества выполненных клозов для данной формулы. Этот алгоритм в дальнейшем мы называем просто Локальный Поиск(ЛП).
Оценки ЛП в худшем случае довольно пессимистичны: наилучшая нижняя оценка локального максимума количества выполненных ограничений задачи /г-Выполнимость — это ^г^яі, где та — общее количество ограничений [27]. Известны [7] многие алгоритмы, имеющие лучшую оценку с точки зрения анализа худшего случая. Однако, эмпирически установлено, что в среднем результат Локального Поиска намного лучше, чем щ^тп. Также это наблюдение поддерживается результатами работы [44], в которой установлено, что большинство выполнимых формул задачи З-ВЫПОЛНИМОСТЬ решается алгоритмом Локального Поиска.
В данной работе исследуется эффективность алгоритма ЛП в среднем на задачах З-ВЫПОЛНИМОСТЬ, распределенных по закону Ф(тг, рп): для заданного количества переменных п и константы р равновероятна любая задача, содержащая п переменных и [рп\ клозов. Это распределение привлекает особое внимание, поскольку известно(см. например [51]), что в зависимости от параметра р оно позволяет генерировать задачи различной сложности, как с точки зрения доказательства невыполнимости, так и нахождения решения.
Мы также рассматриваем ослабленную версию алгоритма ЛП — Локальный Поиск за Один Просмотр (ЛПОП). В ЛПОП все переменные просматриваются в случайном порядке, при этом каждая переменная рассматривается только один раз, и если изменение ее значения приводит к увеличению количества выполненных клозов, то ее значение меняется, в противном случае — нет. Для ЛПОП мы строим модель аналогичную 'карточной игре' из [3] и затем применяем теорему Вормальда [67], показывая, что ЛП почти наверняка возвращает вектор, удовлетворяющий с(р)п + о(п) клозов, где с(р) > |р. Используя подобные методы и основываясь на некотором естественном предположении, мы получаем
Итеративное Улучшение (англ.)
ВВЕДЕНИЕ
аналогичный результат для ЛП.
2.4 Алгоритм VEGAS
В третьей главе мы представляем генетический алгоритм приближенного решения задачи Максимальная Выполнимость.
Генетические алгоритмы — это стохастический метод решения сложных оптимизационных задач. Впервые они рассматривались в [35] и позже стали широко известными благодаря работе [22]. В генетических алгоритмах моделируются два основных механизма эволюции — наследование и естественный отбор, или выживание наилучших, которое приводит к исчезновению из популяции неприспособленных к среде индивидов. В роли индивидов, как правило, выступают элементы области определения целевой функции, а их приспособленность к окружающей среде задается значением целевой функции.
Генетические алгоритмы находят широкое применение как в практических, так и теоретических областях компьютерных наук. Генетический подход успешно применялся при конструировании самолетов [9], маршрутизации водопроводов [63], составлении расписаний [32]. В то же время на основе генетического подхода разрабатываются эффективные эвристические алгоритмы для решения NP-трудных комбинаторных задач Выполнимость [8], Задача Коммивояжера [26] и других. В своем простейшем варианте генетические алгоритмы могут быть применены к любым задачам оптимизации функции нескольких переменных.
Как и алгоритм Локального Поиска (см. главу 2), генетические алгоритмы являются неполными. Различные варианты генетических алгоритмов были испытаны для задачи Выполнимость (см. например [42, 28, 20, 18, 66]). В статье [46] Лардо и др. предложили гибридный алгоритм GASAT, использующий Локальный Поиск при образовании новых индивидов в ходе эволюции. Сравнение, проведенное Лардо и др. на задачах библиотеки SATLIB, показало, что такое совмещение оказывается более эффективным, чем каждый из подходов по отдельности.
Работа генетического алгоритма, решающего оптимизационную задачу, строится по следующей схеме. Прежде всего, некоторым образом (в простейшем варианте — случайным) генерируется начальная популяция. Каждый индивид в ней — это строка, представляющая из себя код элемента множества, в котором ищется решение. Затем популяция итеративно обновляется за счет того, что в нее добавляются потомки
ВВЕДЕНИЕ
присутствующих в ней индивидов и удаляются "погибшие" особи. Вероятность гибели индивида тем больше, чем меньше индивид приспособлен к среде, что соответствует худшему значению оптимизируемой функции.
Отличительной чертой предлагаемого нами алгоритма является влияние индивидов на окружающую среду. В то время как в классическом варианте популяция обитает и развивается в неизменном окружении, в предлагаемом нами алгоритме популяция и окружающая среда активно влияют друг на друга, эволюционируя вместе. Сравнение нашего алгоритма с существующими показывает, что такое взаимное влияние существенно повышает эффективность работы алгоритма, позволяя популяции не останавливаться на локальных максимумах целевой функции.
Разработанный нами алгоритм мы назвали VEGAS (сокращенно от Valuation Enhanced Genetic Algorithm for Satisfability2). Алгоритм VEGAS является модификацией алгоритма GASAT[46].
Для того, чтобы оценить насколько включение воздействия индивидов на окружаюшую среду влияет на эффективность вычислений, мы сравниваем эффективность VEGAS с эффективностью GASAT на ряде известных тестовых задач [36].
Проведенные тесты показывают, что VEGAS может решить больший класс задач, чем GASAT, а задачи, посильные GASAT, алгоритм'VEGAS решает за меньшее время, оказываясь таким образом сильнее своего предшественника. В результате мы видим, что предложенная нами модификация генетической модели заслуживает внимания и исследования в случае решения и других задач.
Попутно мы исследуем влияние социальной структуры популяции на эффективность работы алгоритма. Социальная структура отражается на операторе выбора родителей нового индивида. В нашем подходе мы повышаем вероятность наилучшего индивида участвовать в размножении в роли первого родителя и при этом нарушаем равенство вероятностей получения ребенком гена от первого и от второго родителей. Такая модель предоставляет параметры, правильная настройка которых может повысить эффективность алгоритма при решении конкретного класса задач.
2Усиленный взвешиванием генетический алгоритм для задачи Выполнимость
ВВЕДЕНИЕ
Результаты данной работы представлены на Всероссийской конференции Дискретный Анализ и Исследование Операций (Новосибирск 2002), на Мальцевских чтениях(Новосибирск 2002), Международной объединенной конференции по искусственному интеллекту (Акапулько, 2003), Объединенной конференции по логике (Сиэтл, 2006), конференции Компьютерные науки в России (Екатеринбург 2007), докладывались на алгебраических и алгоритмических семинарах Уральского Государственного Университета, Университета Саймона Фрайзера. Основные результаты диссертации отражены в семи публикациях автора.
Результаты работы представлены в статьях [68, 69, 70, 71, 72, 73, 74]. В совместных работах с А. А. Булатовым последнему принадлежит постановка задачи и общая методика исследований; доказательства всех основных утверждений принадлежат диссертанту. Совместная работа с Е. Амири выполнена в неразрывном соавторстве.
Эффективность алгоритма Локальный Поиск
Генетические алгоритмы — это стохастический метод решения сложных оптимизационных задач. Впервые они рассматривались в [35] и позже стали широко известными благодаря работе [22]. В генетических алгоритмах моделируются два основных механизма эволюции — наследование и естественный отбор, или выживание наилучших, которое приводит к исчезновению из популяции неприспособленных к среде индивидов. В роли индивидов, как правило, выступают элементы области определения целевой функции, а их приспособленность к окружающей среде задается значением целевой функции.
Генетические алгоритмы находят широкое применение как в практических, так и теоретических областях компьютерных наук. Генетический подход успешно применялся при конструировании самолетов [9], маршрутизации водопроводов [63], составлении расписаний [32]. В то же время на основе генетического подхода разрабатываются эффективные эвристические алгоритмы для решения NP-трудных комбинаторных задач Выполнимость [8], ЗАДАЧА КОММИВОЯЖЕРА [26] и других. В своем простейшем варианте генетические алгоритмы могут быть применены к любым задачам оптимизации функции нескольких переменных.
Как и алгоритм Локального Поиска (см. главу 2), генетические алгоритмы являются неполными. Различные варианты генетических алгоритмов были испытаны для задачи Выполнимость (см. например [42, 28, 20, 18, 66]). В статье [46] Лардо и др. предложили гибридный алгоритм GASAT, использующий Локальный Поиск при образовании новых индивидов в ходе эволюции. Сравнение, проведенное Лардо и др. на задачах библиотеки SATLIB, показало, что такое совмещение оказывается более эффективным, чем каждый из подходов по отдельности.
Работа генетического алгоритма, решающего оптимизационную задачу, строится по следующей схеме. Прежде всего, некоторым образом (в простейшем варианте — случайным) генерируется начальная популяция. Каждый индивид в ней — это строка, представляющая из себя код элемента множества, в котором ищется решение. Затем популяция итеративно обновляется за счет того, что в нее добавляются потомки присутствующих в ней индивидов и удаляются "погибшие" особи. Вероятность гибели индивида тем больше, чем меньше индивид приспособлен к среде, что соответствует худшему значению оптимизируемой функции.
Отличительной чертой предлагаемого нами алгоритма является влияние индивидов на окружающую среду. В то время как в классическом варианте популяция обитает и развивается в неизменном окружении, в предлагаемом нами алгоритме популяция и окружающая среда активно влияют друг на друга, эволюционируя вместе. Сравнение нашего алгоритма с существующими показывает, что такое взаимное влияние существенно повышает эффективность работы алгоритма, позволяя популяции не останавливаться на локальных максимумах целевой функции.
Разработанный нами алгоритм мы назвали VEGAS (сокращенно от Valuation Enhanced Genetic Algorithm for Satisfability2). Алгоритм VEGAS является модификацией алгоритма GASAT[46].
Для того, чтобы оценить насколько включение воздействия индивидов на окружаюшую среду влияет на эффективность вычислений, мы сравниваем эффективность VEGAS с эффективностью GASAT на ряде известных тестовых задач [36].
Проведенные тесты показывают, что VEGAS может решить больший класс задач, чем GASAT, а задачи, посильные GASAT, алгоритм VEGAS решает за меньшее время, оказываясь таким образом сильнее своего предшественника. В результате мы видим, что предложенная нами модификация генетической модели заслуживает внимания и исследования в случае решения и других задач.
Попутно мы исследуем влияние социальной структуры популяции на эффективность работы алгоритма. Социальная структура отражается на операторе выбора родителей нового индивида. В нашем подходе мы повышаем вероятность наилучшего индивида участвовать в размножении в роли первого родителя и при этом нарушаем равенство вероятностей получения ребенком гена от первого и от второго родителей. Такая модель предоставляет параметры, правильная настройка которых может повысить эффективность алгоритма при решении конкретного класса задач.
Усиленный взвешиванием генетический алгоритм для задачи Выполнимость Результаты данной работы представлены на Всероссийской конференции Дискретный Анализ и Исследование Операций (Новосибирск 2002), на Мальцевских чтениях(Новосибирск 2002), Международной объединенной конференции по искусственному интеллекту (Акапулько, 2003), Объединенной конференции по логике (Сиэтл, 2006), конференции Компьютерные науки в России (Екатеринбург 2007), докладывались на алгебраических и алгоритмических семинарах Уральского Государственного Университета, Университета Саймона Фрайзера. Основные результаты диссертации отражены в семи публикациях автора.
Результаты работы представлены в статьях [68, 69, 70, 71, 72, 73, 74]. В совместных работах с А. А. Булатовым последнему принадлежит постановка задачи и общая методика исследований; доказательства всех основных утверждений принадлежат диссертанту. Совместная работа с Е. Амири выполнена в неразрывном соавторстве.
Строение клона функций, сохраняющих амальгаму
Для клона отношений R обозначим через R\x клон отношений {рП Х\р Е R}. Аналогично для клона функций F, введем обозначение F\x = {/х/ Є- F)f сохраняет X}. Очевидно, что для клонов отношений RA, RB, определенных на множествах Л, В соответственно справедливы включения: (A(RA,RB)) \А Э RA, {A(RA, RB)) \в 2 RB- МЫ говорим, что клоны отношений RA и RB склеиваются, если выполняются равенства {A(RA, RB)) \А = RA, (HRA, RB)) \В = RB В терминах задачи CSP склеивание означает, что любая задача Р Є CSP((A(J?A, RB)) \А) принадлежит CSP(RA) и любая задача Р Є CSP((A(RA,RB)) \В) принадлежит CSP(RB).
Основной результат данного раздела — это теорема 4, в которой приводится критерий склеиваемости клонов.
Следующая лемма указывает на то, что интерес представляет проблема склеивания клонов отношений, определенных на пересекающихся множествах.
Лемма 1.3 Пусть А и В некоторые конечные множества. Тогда если АГ\В = 0, то любые клоны отношений RA и RB, определенные на А и В соответственно, склеиваются. Если АПВ ф 0, то существуют такие клоны отношений RA, RB, что выполняются оба или одно из строгих
включений (A(RA,RB))\ACR% (1.3) (A(RA,RB))\BcRB. (1.4) Доказательство. Действительно, если А П В = 0, то любая функция g Є РоІ(і?д) является проекцией некоторой схемы ,,_,. _ Г g(ж), если все координаты х принадлежат А, \ х\ в противном случае, что означает РоІ(Дл) Q S(Po\(RA), Po\(RB)). По теореме 1.2, в силу соотношения (1.2) имеем (A(RA,RB)) \RA = RA. Рассмотрим случай А П В ф 0. Поскольку А Є lnv(FA), В Є lnv(FB), 0 є lnv(Fx) П Inv ) имеем A = A U 0 Є А(ЯЛ, ЯВ), В = В U 0 Є А(ЯЛ, RB). Следовательно, А Г) В = С Є (A(RA,RB)}, для любых RA,RB. Таким образом, если С RA, С 0 R%, то включения (1.3) и (1.4) истинны.
В третьем и четвертом разделах мы ограничиваемся рассмотрением амальгамы двух клонов. Автору ясно, как обобщить определение скле-иваемости, а также формулировку и доказательство критерия склеива-емости клонов. Однако, поскольку мы доказываем критерий полиноми-альности только для бинарной амальгамы, то и в этом параграфе мы ограничиваемся лишь этим случаем.
Вплоть до конца этой главы мы считаем D — АиВ, Z = {A,B}, С = АпВф0. Мы будем говорить, что клоны функций FA и FB склеиваются, если выполняются равенства S(FAyFB)\A = FA,S(FA,FB)\B = FB.
Эквивалентность склеиваемости клонов функций и соответствующих им клонов отношений устанавливают терема 1.3 и следующая
Лемма 1.4 Для любого клона функций F, определенного на множестве А и сохраняющего множество С С. А, клон отношений R = \nv(F), удовлетворяет равенству Po\c(R\c) = F\c.
Доказательство. Включение F\c Q Ро1с(Яс) очевидно. Действительно, функции из F\c сохраняют Я и С, а значит сохраняют и R\c Докажем обратное включение, т. е. Po\c(R\c) Q F\c. Для каждого п е. N мы построим такое отношение р, что все n-арные функции из клона Ро1с(Яс) будут его сохранять, в то время как каждая п-арная функция, сохраняющая р, будет принадлежать F\c- Это отношение строится следующим образом. Рассмотрим Хп— n-ый график клона F. Вычеркнем из Хп все строчки, в которых в абсциссе графика Хп встречаются компоненты, не принадлежащие С. Полученное отношение обозначим через р. Поскольку клон отношений замкнут относительно вычеркивания строк имеем р Є R, и так как F сохраняет С, отношение р принадлежит С""" , то есть р Є Дс- Значит, все функции из Polc-Rc сохраняют р.
Докажем, что всякая п-арная функция /, сохраняющая р, принад лежит F\c- Заметим, что все столбцы Ас принадлежат р. Применим / к абсциссе Ас- Мы получим некоторый столбец, принадлежащий р.
Этот столбец является результатом вычеркивания некоторых элементов из столбца, принадлежащего Хп, который является результатом примене ния некоторой функции JGFK абсциссе графика \ п. Ясно, что / = д\с Лемма доказана.
Нам пригодятся следующие обозначения. Если X — вектор, то через Ха Р мы обозначим вектор, получающийся из X заменой компонент, равных а, на /?. Если Л = {ai,..., а } — множество, то мы определим ХЛ=?/? следующим образом
Если Ф Є Zn, то через Фд обозначим вектор фв—с ) а через Фв — вектор А с. Напомним, что если /(х) — произвольная функция, то через f l{z) обозначается множество {х \f(x) = z}. Критерий склеиваемости клонов будет основываться на следующей лемме.
Лемма 1.5 Если функция f принадлежит S(FA, FB), то функции /л = I\A IB = 1\в удовлетворяют следующим трем условиям. 1) Выполняется равенство JA\C — /вс 2) Справедливы включения fA Є S(FA,FB\C), /В Є S(FB,FA\C) 3) Для /А и /в можно выбрать метафункции так, чтобы, для любого Ф Zar(-M было истинным равенство Ы л))С В = ЫЪв))С А. Справедливо таксисе обратное, т. е., если /А, /В — функции одинаковой арности, удовлетворяющие условиям 1) - 3), то существует функция f Є S{FA, FB) такая, что fA = /д, /в = /в
Доказательство. Пусть / Є S(FA,FB). Условие 1) истинно в силу равенств /лс = Ш\с = f\c = Ш\с = /вс Функция /д является схемой, собранной из функций клонов FA) FB\C, так как мы можем указать для нее метафункцию ґд : {А, С}аг —» {А, С} и набор деталей D С FA U FB\C- Пусть
г (ъ \-г(ъ\в с f -Jf если fW = І /фІс, если ґ(Ф) = В.
Проверим, что fд и D = {/ЛФЛ}, действительно, — метафункция и детали функции /д. Убедимся, что детали выбираются из подходящих клонов. В самом деле, если f (Ф) = А, то /ф є FA, а если f (Ф) = В, то /Ф Є - в, и, следовательно, /Фс Є -Рвс Посмотрим, как /д действует на произвольном векторе х Є А, если Фд — шаблон для х: IA{S) = /(f) = /ф(х щф)) = /лФА(ЯфлгА(фл)).
Установлено, что /д удовлетворяет определению схемы. Доказательство для /в аналогично, и условие 2) доказано.
Истинность третьего условия проверяется следующим образом: (ІЛ(ФА))С В = (f (Ф)) с с-в = f(Ф) = (f (Ф))д с С-А = (ґв(Фв))с л. Пусть теперь функции /А,/в удовлетворяют условиям 1) - 3). Построим схему /, ограничениями которой ЯВЛЯЮТСЯ /д И /д. положи f( ) - «.(ад) -» /, = ( " если W = {/в в, если і(Ф) = J5. Отметим, что в силу условия 3) имеет место равенство f (Ф) = (їв(Фв))С- л-Для любого вектора х и любого шаблона Ф Є Ф(х) положим f(x) равным /Ф(ЖФҐ(Ф)). Докажем корректность данного определения функции /, то есть покажем, что значение /() не зависит от выбора Ф. Пусть с — произвольный элемент из С. Возьмем произвольные Ф1, Ф2 Є Ф{х) и установим равенство /Ф1(ЖФ1Г(Ф1)) = /Ф2(Ф2Г(Ф2))
Задача Выполнимость и Локальный Поиск
В этом разделе мы даем формальное определение задачи ВЫПОЛНИМОСТЬ, описываем алгоритмы Локальный Поиск и Локальный Поиск за Один Просмотр.
Литералом называется булева формула, являющаяся переменной или отрицанием переменной. Дизъюнкция литералов называется клозом. Булева формула Ф называется конъюнктивной нормальной формой (КНФ), если Ф — конъюнкция клозов. Булева формула Ф называется fc-КНФ, если Ф — конъюнкция клозов, и каждый клоз содержит ровно к литералов.
Определение 2.1 Задача Выполнимость— это комбинаторная задача распознавания, каждая конкретная задача S которой формулируется следующим образом: УСЛОВИЕ: Дана КНФ Ф. ВОПРОС: Существует ли набор значений переменных, обращающий Ф в истинное выражение?
Мы будем полагать, что переменные, входящие в Ф, имеют вид х , где г Є {І,.--,п]. Нам будет удобно говорить о наборе значений, как о булевом векторе, г-я компонента которого соответствует значению г-й переменной. Количество клозов, содержащих определенную переменную, называется степенью данной переменной.
В задаче /с-ВыполНИМОСТЬ в качестве Ф разрешено брать только /с-КНФ.
Условием задачи МАКСИМАЛЬНАЯ Выполнимость также является булева формула Ф в КНФ, вопрос в этой задаче: Какой набор значений переменных удовлетворяет наибольшему числу ограничений?
В качестве вероятностного распределения задач мы используем задачи З-ВЫПОЛНИМОСТЬ фиксированной плотности. Через Ф(п, т) обозначается случайная КНФ с т клозами и п переменными, где клозы выбираются равномерно и независимо из всех 8(g) клозов без повторений переменных.
Мы рассматриваем следующую версию Локального Поиска. Изначально выбирается х — случай набор значений переменных и повторяются, следующие шаги, пока это возможно: найти множество W, состоящее из всех переменных Ж{ таких, что при изменении значения xi количество невыполненных клозов уменьшается; выбрать переменную Xi из W случайно (считая, что все переменные из W равновероятны); изменить значение xi. Прежде чем давать формальное описание алгоритма ЛП мы представим его в виде, более простом для анализа, и введем необходимые обозначения.
Локальный Поиск, в рассматриваемой нами формулировке, начинает работу со случайной задачи и случайного набора значений. Нетрудно заметить, что при анализе эффективности алгоритма, набор значений может быть устранен из рассмотрения. Действительно, зафиксируем набор значений х = (1,..., 1) и в ходе алгоритма будем изменять формулу. Вместо того, чтобы изменять значение xt будем заменять все вхождения ХІ на -я:j и наоборот. Ясно, что такая модификация не повлияет на количество выполненных клозов в ходе работы алгоритма, в то время как упрощает моделирование, используемыми нами методами.
Через АФ(ХІ), Вф(хі) обозначается количество невыполненных клозов из Ф, содержащих - ХІ (В таких клозах все литералы отрицательны), и количество клозов из Ф, содержащих ХІ, в которых два других литерала отрицательны, соответственно. Благодаря переменной ХІ клозы из ВФ(ХІ) выполнены, но при ее изменении они становятся невыполненными. Поскольку из контекста всегда будет ясно о какой формуле Ф идет речь, индекс Ф мы будем опускать. Формальное описание алгоритма Локального Поиска приводится на рис. 2.1.
ВХОД: Случайная булева формула в 3-КНФ Ф ВЫХОД: количество невыполненных клозов по окончании поиска Шаг 1 Вычислить множество W переменных xt со свойством A(xt) B(xt) Шаг 2 Пока W Ф 0 делать: Шаг 2.1 Выбрать переменную xt из W равномерно случайно Шаг 2.2 Для каждого клоза С Є Ф содержащего xt или xt Заменить xt на Xt и -іж4 на xt Шаг 2.3 Вычислить множество W переменных xt таких, что A(xt) B(xt) Шаг З Вернуть количество невыполненных клозов в Ф ВХОД: случайная булева формула в 3-КНФ Ф с п переменными ВЫХОД: количество невыполненных клозов по окончании работы Шаг 1 Для t = 1 до п делать: Шаг 1.1 вычислить A(xt) и B(xt) Шаг 1.2 Если A(xt) B(xt) то Шаг 1.2.1 Для каждого клоза С Є Ф содержащего xt или - xt Заменить xt на - xt и - xt на xt Шаг 2 Вернуть количество невыполненных клозов в Ф
На ряду с обычным ЛП мы исследуем его ослабленную версию, которую мы называем Локальный Поиск за Один Просмотр (ЛПОП), см рис. 2.2. Отметим, что более естественно было бы выбирать очередную переменную для рассмотрения случайно, так как это делается в ЛП. Однако очевидно, что при запуске алгоритма на случайной задаче, нет никакой разницы, будет ли очередная переменная в ЛПОП выбираться на каждом шаге случайно из тех, что еще не были просмотрены, или порядок просмотра переменных выбран в начале работы. Мы считаем, что порядок просмотра выбирается вначале, поскольку в таком виде ЛПОП более естественным образом укладывается в используемую нами модель.
Ключевым приемом нашего анализа является применение теоремы, доказанной Вормальдом [67], которая позволяет заменить вероятностный анализ комбинаторного алгоритма анализом детерминированной системы дифференциальных уравнений.
Мы будем говорить, что функция д является 0(/), если limn_,oo( 7//) = const, и является о(/), если предел этот равен 0. Причем предел в данном случае равномерный по всем остальным переменным.
Пусть дана последовательность Г2„, п = 1,2,..., вероятностных пространств. Пусть " набор случайных величин, причем " определена на пространстве Г2„. Мы будем говорить, что равенство = о(/(п)) выполняется всегда, если тах{жР (" = х) ф 0} = o(f(n)). Для семейства событий {п} (где " событие в Пп) мы будем говорить, что Еп происходит почти наверняка, если вероятность события п равна 1 — о(1).
Дискретным случайным процессом мы называем последовательность векторных случайных величин . Историей случайного процесса к мо-_ менту to называется матрица Hto, строчками которой являются значения вектора , для t t0.
Взвешенная Максимальная Выполнимость
Как уже было сказано, в рамках генетического подхода функция V(x) рассматривается как мера приспособленности индивида х к среде. Таким образом, решение задачи ВМВ S представляется нам как поиск наиболее приспособленного к среде S индивида.
Решение этой задачи осуществляется посредством моделирования эволюционного процесса. Прежде всего генерируется начальная популяция V С {0,1}" . Затем популяция обновляется, с целью получить в ней индивидов с более высокой приспособленностью. Для этого индивиды, присутствующие в популяции, скрещиваются между собой, их потомки добавляются в популяцию, а некоторые индивиды из популяции удаляются. При разработке генетического алгоритма для того или иного класса задач необходимо указать способ генерации начальной популяции, выбора родителей для нового индивида, получения генетического кода нового индивида из кода родителей, и, наконец, правила выбора удаляемых индивидов.
Формальное описание генетического алгоритма в общем виде дано на рис. 3.1. Действия, требующие доопределения, выделены курсивом. В самом простом случае эти действия могут быть, определены следующим образом: вектора в начальную популяцию V выбираются случайно, на шаге 2.1 все индивиды из популяции V имеют равные шансы быть выбранными в качестве родителей, на шаге 2.2 каждая координата Z{ определяется по правилу: 1, с вероятностью 0.5 /л, 0, с вероятностью 0.5 -и, .,,,,. Zl = \ А К (Л \ (ЗЛ) Х{, с вероятностью 0.5 (1 — /л), ЧУІ, с вероятностью 0.5 (1 — /л).
Отметим, что в теории генетических алгоритмов параметр fi называется вероятностью мутации, а функция осуществляющая скрещивание кроссинговером. удаляется наименее приспособленный индивид. Bxofl:iV — размер популяции, Т — максимальное количество итераций, V(-) — функция приспособленности. ВЫХОД: х наилучший найденный индивид. Шаг 1 Сгенерировать начальную популяцию V Шаг 2 Повторять Г раз: Шаг 2.1 Выбрать ж и у из популяции Шаг 2.2 Скрестить х и у, получив потомка z Шаг 2.3 Удалить одного из индивидов из V Шаг 3 Вернуть наиболее приспособленного индивида из рассмотренных GASAT — один из известных генетических алгоритмов, разработанных для задачи МАКСИМАЛЬНАЯ Выполнимость [46], его специфика заключается в следующем: при создании индивида для начальной популяции V сначала его генотип генерируется случайным образом, а затем передается для улучшения алгоритму TabuSearch, представляющему из себя модификацию алгоритма Локальный Поиск, мы приводим его описание в следующем разделе; при скрещивании индивидов делается попытка создать ребенка, удовлетворяющего как ограничениям выполненным первым родителем, так и вторым (см. детали в [46]), после этого генотип передается для улучшения алгоритму TabuSearch.
Данный раздел состоит из трех подразделов, соответствующих трем эвристикам входящим в VEGAS. Сначала мы описываем эволюцию среды обитания популяции, затем способ моделирования социальной структуры, осуществляемый в VEGAS, и, наконец, приводим описание алгоритма TabuSearch, используемого для улучшения новых индивидов перед добавлением в популяцию. Эволюция среды обитания и моделирование социальной структуры являются новыми элементами генетического ал ВХОД: Формула в КНФ Ф, набор весов v(-) = {v(C)\C Є Ф}, индивид х, параметр 5. ВЫХОД: Новый набор весов v (-). Шаг 1 Для С є Ф: Шаг 1.1 Если - (С()) то Шаг 1.1.1 пусть v {C) = v{G) + 8 Шаг 1.2 иначе Шаг 1.2.1 пусть v (C) = v{C) горитма, предлагаемыми в данной работе. Алгоритм TabuSearch уже использовался в [29]. Раздел завершается псевдокодом алгоритма VEGAS.
Эволюция среды обитания, происходящая из-за влияния индивидов, позволяет популяции покидать найденные локальные максимумы и не возвращаться в них.
Набор значений переменных х по прежнему считается генетическим кодом некоторого организма. В то время как каждый клоз С мы считаем формой хищника и интерпретируем удовлетворение вектором х клоза С как способность существа х защититься от хищника С.
Эволюция Среды (см рис. 3.2) в алгоритме VEGAS реализована следующим образом. Когда в результате размножения появляется существо с генотипом х, хищники, от которых это существо не защищено, размножаются, что в терминах задачи выражается в увеличении веса клозов, которые нарушаются вектором х. Увеличения весов невыполненых клозов производится на величину 5, которая является настроечным параметром алгоритма.
В начале работы мы запоминаем исходные веса v в г»о, полагая VQ(C) = v(C), для каждого С (если решается задача МАКСИМАЛЬНАЯ ВЫПОЛНИМОСТЬ, то изначально v(C) = 1). В ходе вычисления мы запоминаем индивида Ь, максимизирующего значение Vo(b) = 2 vo(C), как наи СЄФ,С(Ь) лучшего из встреченных.
Регулируя вероятность участия наиболее приспособленного индивида в очередном размножении и степень похожести потомства на него, мы можем регулировать, будет ли алгоритм склонен к исследованию более широкого или более узкого участка пространства решений. Моделирование социальной структуры предоставляет нам эту возможность.
Социальная структура популяции учитывается в алгоритме VEGAS следующим образом: индивид с наибольшим значением целевой функции считается "вожаком". С вероятностью q вожак выбирается в качестве первого родителя новой особи и случайным образом выбирается второй родитель. В противном случае родители выбираются случайно. Таким образом, изменяя параметр q, мы влияем на привилегированность генов вожака по отношению к генам остальных особей популяции.
Скрещивание производится по следующей схеме. После того, как из популяции выбраны родители будущего индивида — вектора х, у Є V, строится их потомок z. Схема построения потомка имеет два параметра — это вероятность мутации [і и вероятность получения очередного гена от первого родителя р. Очередной ген потомка с вероятностью \і выбирается случайно, и с вероятностью 1 — \i наследуется от одного из родителей. Если гену выпало наследоваться от родителей, то с вероятностью р он будет унаследован от первого родителя и с вероятностью 1 — р от второго. Более формально, zi = C{x,y,p,ii)i= 1, с вероятностью 0,5 //, О, с вероятностью 0,5 ц, ХІ, с вероятностью р (1 — ц), КУІ,с вероятностью (1 — р) (1 — fj,). Очевидно, формула (3.2) обращается в (3.1) при р = 0.5.
