Исследование методов трансформации энергетической поверхности в задачах бинарной минимизации квадратичного функционала

• Автор: Карандашев, Яков Михайлович
• Шифр специальности: 05.13.01
• Научная степень: Кандидатская
• Год защиты: 2013
• Место защиты: Москва
• Количество страниц: 119 с. : ил.

СОДЕРЖАНИЕ
СОДЕРЖАНИЕ
1. ВВЕДЕНИЕ

1.1 Актуальность темы

1.2 Постановка задачи

1.3 Обзор литературы

1.4 Цели и задачи диссертации

1.5 Основные положения выносимые на защиту

1.6 Научная новизна

1.7 Практическая ценность

1.8 Методы исследования

1.9 Апробация работы и публикации
1.10 Структура диссертации
2. ОБЛАСТЬ ПРИТЯЖЕНИЯ МИНИМУМА
2.1 Область притяжения минимума
2.2 Форма минимума
2.3 Ограничение на глубину минимума
2.4 Выводы по главе
2.5 Приложение А. Форма энергетической поверхности в п-окрестности
3. АЛГОРИТМ С ВОЗВЕДЕНИЕМ МАТРИЦЫ В СТЕПЕНЬ (DDK)
3.1 Стандартный алгоритм случайного поиска (SRS)
3.2 Базовые соотношения
3.3 Трансформация поверхности
3.4 Обоснование алгоритма DDK
3.4а) Углубление минимумов
3.46) Сдвиг минимума
3.4в) Выводы и их проверка
3.5 Эффективность алгоритма DDK
3.5а) Результаты для матриц двумерной модели Эдвардса-Андерсона (2D ЕА)
3.56) Результаты для матриц модели Шеррингтона-Киркпатрика (SK)
3.5в) Улучшение динамики. Алгоритм Хоудайера-Мартина (НМ)
3.5г) Результаты для матриц З-.мерноймодели Эдвардса-Андерсона (3D ЕА)
3.6 Применения алгоритма к задаче разбиения графа (graph bipartitioning)
3.7 Выводы по главе
4. АЛГОРИТМ MIX-MATRIX (ММ)
4.1 Углубление минимума
4.2 Сдвиг минимума
4.3 Описание алгоритма ММ
4.4 Результаты для алгоритма ММ
4.5 Сравнение с алгоритмами для задачи MAXCUT
4.6 Выводы по главе
4.7 Приложение А
5. ОГРАНИЧЕНИЯ НА ВЕСА ПАТТЕРНОВ В КВАЗИХЕББОВСКОЙ МАТРИЦЕ (ДОПОЛНИТЕЛЬНАЯ ГЛАВА)
5.1 Квазихеббовская модель
5.2 Основное уравнение
5.3 Простейший случай
5.4 Произвольное распределение весов
5.5 Выводы по главе
6. ЗАКЛЮЧЕНИЕ
СПИСОК ЛИТЕРАТУРЫ

1. ВВЕДЕНИЕ
1.1 Актуальность темы
Дискретная оптимизация играет важную роль как в инженерных системах, так и в фундаментальной науке.
Настоящая работа направлена на повышение эффективности процедуры случайного поиска, применяемой при решении задач минимизации квадратичного функционала с бинарными переменными. Такого рода задачи возникают в системах, состоящих из большого числа взаимодействующих частей, как например нейронные сети, спины в магнитной решётке, элементы электронных плат, фазированные антенные решётки и мн. др.
Несмотря на многочисленные работы по данной тематике, №-сложность задачи в общем случае оставляет её трудно решаемой. Открытой проблемой является природа энергетической поверхности в оптимизационных задачах. Обычно соглашаются с тем, что эта поверхность сильно испещрена минимумами, поэтому эффективные алгоритмы особенно необходимы [1].
Анализ больших технических систем приводит к необходимости решения задач подобного рода, при этом однако линейное увеличение скорости вычислений компьютеров (например, при помощи графических ускорителей) не может превозмочь экспоненциальную от размера входных данных сложность задачи. Поэтому задача остаётся актуальной, и вероятно будет оставаться такой вплоть до эффективной реализации квантовых вычислителей.
1.2 Постановка задачи
Настоящая работа направлена на повышение эффективности процедуры случайного поиска, применяемой при решении задач бинарной минимизации. Это класс задач, решение которых сводится к минимизации квадратичного функционала Е(3):

ч»—лгх£г.,л. о.1)
'У °г '=1 у=
построенного на заданной N х ЛГ -матрице Г в N -мерном
конфигурационном пространстве состояний 5” = ($,, з2 ,...,5^) с дискретными
переменными ^=±1, 1 = 1,И; ат - стандартное отклонение матричных
элементов Т . Матрицу Т без ограничения общности будем полагать
симметричной (Т = 77) с нулевой диагональю (Ти =0). Нормировка на сгг
обеспечивает корректность сравнения результатов для различных матриц.
1.3 Обзор литературы
Функционал вида (1.1) определяет энергию системы взаимодействующих спинов в магнитной решётке. В случае случайных положительных и отрицательных взаимодействий Т1} такая система в физике
называется спиновым стеклом и характеризуется беспорядком и фрустрацией, приводящей к очень сложной энергетической поверхности [2-5]. Эти физические модели также формулируются как задачи оптимизации, которые применимы во многих областях научной деятельности [3,5]. К сожалению, проблема поиска основного состояния является ЫР-сложной [6]. Поэтому разнообразные алгоритмы адаптировались на протяжении многих лет специально для поиска основных состояний и для исследования спиновых стёкол при конечных температурах и при переходе к пределу нулевой температуры [7,8]. Ввиду большой сложности задач разрабатывались специализированные компьютеры для их решения [9].
Задача минимизации в конфигурационном пространстве дискретных переменных кардинально отличается от той же задачи в непрерывном пространстве с вещественными переменными, когда она может быть решена с применением известных вычислительных процедур. Во-первых, в случае бинарных переменных квадратичный функционал является многоэкстремальным, даже если матрица Т является положительно-

случае есть не что иное, как стандартный алгоритм случайного поиска 5115 (£>£>1з £/?$).
Количество операций, выполняемых алгоритмом ББК примерно в два раза больше чем у алгоритма 5Я5, т.е. Оовк & 20$К5, однако мы также должны помнить что некоторое время также приходится тратить на возведение матрицы в степень (порядка ЛС операций для полносвязных матриц).
3.4 Обоснование алгоритма ББК
Обоснование предложенного алгоритма проведем на примере случая к- 2. Покажем, что в результате трансформации поверхности глобальный минимум становится заметно глубже, а его сдвиг в пространстве невелик.
3.4а) Углубление минимумов
Сначала убедимся, что трансформация поверхности приводит к углублению минимума. Рассмотрим энергию Е20 = £2(50) в точке б1,,. Следуя
(3.3) матрицу М = Т2 представим в виде М = Тд +Т2 +(Т0Т} + 7]Г0). Тогда с
учетом соотношений БдТ^д = 0 и сги = у]ИоЕ из (3.5) получим:
Из (3.7) следует, что в пределе N »1 энергию Е1() можно рассматривать как нормально распределенную величину со средним Е20 и относительно малым стандартным отклонением аЕ:
результате произведенной трансформации поверхности минимум станет глубже (Е20 < Ед). Вероятность такого события описывается выражением:
(3.7)
Рт{Е20<Е0} = ^1 + егГт1)
(3.9)