WWW.DISSERS.RU

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

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

Pages:     | 1 || 3 |

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

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

Генетические алгоритмы находят широкое применение как в практических, так и теоретических областях компьютерных наук. Генетический подход успешно применялся при конструировании самолетов [7], маршрутизации водопроводов [53], составлении расписаний [28]. В то же время на основе генетического подхода разрабатываются эффективные эвристические алгоритмы для решения NP-трудных комбинаторных задач Выполнимость [6], Задача Коммивояжера [24] и других.

Различные варианты генетических алгоритмов применялись для решения задачи Выполнимость (см., например, [16,18,25,36,55]). В статье [40] Лардо и др. предложили гибридный алгоритм GASAT, использующий Локальный Поиск при образовании новых индивидов в ходе эволюции.

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

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

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

Цель работы, таким образом, состоит в решении следующих задач:

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

• установить, каков наиболее вероятный результат применения алгоритма Локальный Поиск к случайной задаче Выполнимость, поступающей в соответствии с распределением (n, n);

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

Методы исследования. В диссертации используются методы теории клонов, теории вероятностей, а также экспериментальные данные по эффективности алгоритмов Локальный Поиск, GASAT и VEGAS.

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

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

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

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

Апробация работы. Результаты диссертации представлены на Всероссийской конференции Дискретный анализ и исследование операций (Новосибирск, 2002), на Мальцевских чтениях (Новосибирск, 2002), Объединенной конференции по искусственному интеллекту (Акапулько, Мексика 2003), Объединенной конференции по логике (Сиэтл, США, 2006), международной конференции Компьютерные науки в России (Екатеринбург, 2007). Отметим, что отбор работ на последние три из перечисленных конференции осуществлялся в соответствии с принятой в компьютерных науках практикой, т. е. на конкурсной основе на базе отзывов трех анонимных рецензентов отбиралась в среднем одна работа из трех представленных. Результаты диссертации докладывались также на алгебраических и алгоритмических семинарах Уральского государственного университета и университета Саймона Фрэйзера (Ванкувер, Канада).

Публикации по теме диссертации. Основные результаты диссертации отражены в семи публикациях автора [57–63]. В трех совместных работах c А. А. Булатовым последнему принадлежит постановка задачи и общая методика исследований; доказательства всех основных утверждений принадлежат диссертанту. Совместная работа с Е. Амири выполнена в неразрывном соавторстве. Работа [58] опубликована в издании, входившем в перечень ВАК на момент публикации.

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

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

Во введении обсуждается история проблем, решаемых в диссертации, даются общие определения.

В главе 1 решается вопрос о полиномиальности амальгамы множеств отношений. Для решения поставленной задачи мы используем предложенную в [34, 35] методику, опирающуюся на достижения теории клонов. Напомним, что клоном функций на множестве A называется семейство функций, замкнутое относительно суперпозиции и содержащее все проекции, т. е. функции вида ei (x1,..., xn) = xi. Далее, каждому n-местному отноn шению на A естественным образом соответствует n-местный предикат P. Это позволяет ввести следующее понятие. Множество отношений называется клоном отношений, если оно содержит отношение равенства и для любых 1,..., k содержит отношение определяемое предикатом P(x1,..., xn) = y1,..., ym(x1,..., xn, y1,..., ym), где формула в правой части диофантова и ее атомарные формулы суть P,..., P. Говорят, что n-местная функция f сохраняет m-местное отно1 k шение, если результат построчного применения f к любой матрице mn, столбцами которой являются элементы, принадлежит. Множество всех функций, сохраняющих все отношения из, обозначается через Pol();

множество всех отношений, сохраняемых всеми функциями из C, обозначается через Inv(C). Как хорошо известно [47], множества вида Pol() – это в точности клоны функций, а вида Inv(C) – клоны отношений, причем операции Inv и Pol задают соответствие Галуа между решетками клонов функций и отношений.

Говорят, что конечное множество отношений полиномиально, если полиномиален класс задач CSP(), а бесконечное множество отношений полиномиально, если полиномиальны все его конечные подмножества. Клоны отношений играют важную роль в изучении задачи CSP ввиду того, что, как было установлено в [34], если множество отношений полиномиально, то полиномиален и клон отношений, порожденный этим множеством. В то же время полиномиальность клона отношений R может быть проверена по наличию определенных функций в клоне Pol(R).

Основным рабочими понятием в изучении клона функций, соответствующего амальгаме, является понятие схемы, собранной из функций клонов F1,..., Fn. Для краткости мы приведем здесь определение схемы в случае n = 2. (В диссертации схема определяется для произвольного n.) Пусть клоны функций FA, FB определены на множествах A и B соответственно. Через Z мы будем обозначать множество {A, B}, через C – множество AB, а через D – множество AB. Вектор (X1,..., Xk) Zk мы будем называть шаблоном вектора = (x1,..., xk) Dk, если xi Xi. Множество x векторов, являющихся шаблонами мы будем обозначать через ( x, x).

Если – шаблон и X – элемент Z, то через мы будем обозначать x, xX вектор, полученный из опусканием координат, на местах которых в x стоит не X. Через X мы обозначаем количество вхождений X в.

Функция f : Cn C арности n называется схемой, собранной из функций клонов FA, FB, если существуют функция f : Zn Z и семейство функций D = {f | Zn ar(f) = f()()}, содержащееся в FA FB, таких, что для всех и всех ( выполняx x) ется равенство f( = f( x) xf()). Функция f называется метафункцией функции f, а функции из множества D – ее деталями.

Другими словами, схемой называется такая функция, которая на векторах данного шаблона действует как некоторая определяемая по шаблону функция f, принадлежащая одному из клонов FA, FB. Множество всех схем, собранных из функций клонов FA, FB, мы обозначаем через S(FA, FB). Первым основным результатом главы 1 является Теорема 1.3 Имеет место равенство Pol(A(R1,..., Rn)) = S(Pol(R1),..., Pol(Rn)).

+ + Обозначим клоны A(RA, RA|C) и A(RB, RB|C) через RA и RB соответственно. Клон RA называется монолитным, ни одно из его унарных отношений не содержится в A\C. Оказывается, если клон RA монолитен, то + задача CSP(A(RA, RB)) сводится к CSP(RB). Таким образом, наибольший интерес представляет случай, когда существуют такие унарные отношения EA RA, EB RB, что EA C = EB C =. В этом случае мы указываем следующий критерий полиномиальности амальгамы, который является вторым основным результатом главы 2.

Теорема 1.6 Если клоны RA и RB немонолитны, то клон A(RA, RB) + полиномиален тогда и только тогда, когда полиномиальны клоны RA, + RB и RA RB.

В главе 2 исследуются алгоритм Локальный Поиск (ЛП) и его ослабленная версия Локальный Поиск за Один Просмотр (ЛПОП).

На вход им подается булева формула, сгенерированная в соответствии с распределением (n, n): для заданного количества переменных n и константы равновероятна любая 3-КНФ, содержащая n переменных и n клозов. Псевдокод алгоритмов представлен на рис. 1. В нем через W (, x) обозначено множество переменных, изменение значения которых в приx водит к увеличению количества выполненных клозов в ( x).

Алгоритм Локальный Поиск (ЛП) Выборать набор значений равномерно случайно x Пока W (, = x) Выбрать xt W (, равномерно случайно x) Изменить значение xt на противоположное Алгоритм Локальный Поиск за Один Просмотр (ЛПОП) Выборать набор значений равномерно случайно x Для каждой переменной xt от x1 до xn Если xt W (, то x) изменить значение xt на противоположное Рис. 1: Псевдокод алгоритмов ЛП и ЛПОП Мы используем принципиально различные модели для анализа ЛП и ЛПОП, однако и в том и в другом случае ключевым моментом нашего анализа является применение теоремы Вормальда [56], позволяющей доказать близость заданных параметров случайного процесса к решению некоторой системы дифференциальных уравнений.

Мы пользуемся следующими определениями из теории вероятности. Событие A(n) происходит почти наверняка при n, стремящемся к бесконечности, если P(A(n)) - 0. Пусть X(n) – некоторая случайная величина, n а c – некоторая константа. Говорят, что равенство X(n) = cn + o(n) выполняется почти наверняка при n, стремящемся к бесконечности, если существуют бесконечно малые последовательности (n), (n) такие, что выполняется неравенство P |X(n) - cn| > (n) < (n).

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

При работе алгоритма ЛПОП после выполнения шага t переменные {x1,..., xt} были рассмотрены и в дальнейшем изменяться не будут. Литералы, содержащие эти переменные, мы называем обработанными. В модели алгоритма ЛПОП рассматриваются следующие множества:

E – множество клозов, не содержащих обработанных литералов;

E1 – множество клозов, содержащих выполненный обработанный литерал;

E0 – множество клозов, содержащих три невыполненных обработанных литерала;

E++ (E+-, E--) – множества клозов, которые содержат ровно один обработанный невыполненный литерал и два (ровно один, ноль, соответственно) других литерала выполнены;

E+ (E-) – множество клозов, содержащих два невыполненных обработанных литерала, в которых необработанный литерал выполнен (невыполнен), соответственно.

Через e, {, 1, 0, ++, +-, --, +, -} мы обозначаем мощность множества E.

Мы показываем, что параметры e удовлетворяют условиям теоремы Вормальда, а следовательно, близки к решению некоторой явно выписываемой системы дифференциальных уравнений (см. систему (2.8) в диссертации). Поскольку в конце работы алгоритма все литералы обработаны, параметр e0 оказывается равным количеству невыполненных клозов.

Таким образом, мы получаем первый основной результат главы 2:

Теорема 2.2 Для любого положительного существует константа cтакая, что для случайной 3-КНФ, распределенной по закону (n, n), количество клозов, выполненных набором значений, получаемым по окончании работы алгоритма ЛПОП, почти наверняка равно c1n + o(n).

Поскольку во время работы ЛП каждая переменная может изменять значение несколько раз, модель, разработанная для ЛПОП, оказывается неприменимой. В модели, описывающей работу ЛП, мы рассматриваем множества {Eab}, где a, b – неотрицательные целые числа. Множество Eab содержит такие переменные xi, что если значение xi изменится, то ровно a невыполненных клозов станут выполненными и ровно b выполненных клозов перестанут быть выполненными. Через eab мы обозначаем мощность множества Eab и через совокупность значений eab по всем неотрицательe ным целым a, b. Ясно, что изменяется в ходе работы ЛП.

e Наш анализ алгоритма ЛП основан на следующем допущении:

Допущение 1 В предположении истории..., процесса работы e(1), e(t) алгоритма ЛП для произвольного клоза C текущей формулы, произвольных позиций p, r в нем, p = r, любых a1, a2, b1, b2 и любых переменных xi Ea,b1, xj Ea,b2, события “xi занимает позицию p клоза C” и “xj 1 занимает позицию r клоза C” независимы.

Pages:     | 1 || 3 |






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