Конференции ИВТ СО РАН

VII Всероссийская конференция молодых ученых по математическому моделированию и информационным технологиям (с участием иностранных ученых)

1-3 ноября 2006 года, Красноярск, Россия

Тезисы докладов

Вычислительная математика

Методы улучшения сходимости алгоритма минимизации функционала, ассоциированного с задачей 3-SAT

Хныкин И.Г., Файзуллин Р.Т.

Омский государственный университет им.Ф.М.Достоевского,
г.Омск

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

Смещение по антиградиенту функционала

Основная процедура состоит из последовательных итераций. Итерация определяется формулой

A(x(t-k),:x(t)) * x(t+1) - B(x(t)), где A и B определены в [1]

При k=0, A(x(t)) * x(t) - B(x(t)) = p. Вектор x(t) является решением, если только p=0. Следовательно, к приближению необходимо добавить поправку.

x(t+1) = x(t) + p/A, где p = A * x(t) - B

Сдвиг по градиенту хорошо сокращает погрешности и ускоряет сходимость алгоритма. Тестирование показало увеличение числа решенных примеров примерно на 20%.

Метод смены траектории

При приближении к решению алгоритм может зацикливаться на некотором плато. Метод смены траектории позволяет сойти с плато и продлить сходимость. Для данного приближения x, рассмотрим множество переменных E0 = {x(i) | существует триплет с: c(x)=0 & литерал x(i) лежит в c}. С вероятностью m_p поменяем значения x(i) на противоположные. Экспериментально установлено, что полученный вектор x(0) обладает хорошими свойствами (количество невыполнимых триплетов до и после операции примерно одинаково). Используя вектор x(0) в качестве нового начального приближения, алгоритм очень быстро (за 5-10 итераций) находит следующее приближение, на котором функционал достигает значения не больше, чем на первоначальном векторе.

Наряду с множеством E0 можно также рассмотреть множество E1 (с триплетами c(x)=1). Компоненты вектора из E1 влияют на качественное изменение вектора, количество невыполнимых триплетов может увеличиться. Чем больше компонент из E1 меняются на противоположные, тем меньшую роль играют рестарты. Результаты тестирования показали существенное увеличение числа решаемых примеров. Особенно хорошо решаются примеры из библиотеки SATLib ~ 99% из 5100 тестов, в том числе тесты BMS, CBS_b90, uf250-1065, flat.

Метод угадываний

Предлагается эвристика для угадывания компонент решения. Если некоторая компонента вектора приближений больше 0.5 и монотонно возрастает, то можно сделать вывод, что в векторе решении она равна 1, и наоборот. Предварительные испытания подтвердили правомерность применения данной эвристики в 70% случаев.

Увеличение разрядности вычислений

Была исследована сходимость алгоритма при увеличении разрядности вычислений. Результаты с типами DOUBLE и FLOAT показывают преимущество вычислений с двойной точностью. Количество решенных примеров увеличивается на 10%. С другой стороны, исследования поведения алгоритма при попадании на плато показывают, что рост числа итераций не дает значимого уменьшения функционала. Сойти с плато без смены траектории очень трудно.

ЛИТЕРАТУРА

1. Файзуллин Р.Т., Cалаев Е.В. Применение метода последовательных приближений с <инерцией> к решению задачи выполнимость, ОМГУ, г.Омск.

2. Gu J.,Purdom P.W.,Franco J.,Wah B.W Algorithms for the Satisfiability Problem: A Survey // DIMACS Series in Discrete Mathematics and Theoretical Computer Science. -1996. -C. 19-151.

Дополнительные материалы: Полный текст доклада
Примечание. Тезисы докладов публикуются в авторской редакции

Ваши комментарии
Обратная связь

[Головная страница]
[Конференции]