Применение дискретизации для решения задач бинарной оптимизации с помощью нейронной сети Хопфилда

• Автор: Мальсагов, Магомед Юсупович
• Шифр специальности: 05.13.01
• Научная степень: Кандидатская
• Год защиты: 2012
• Место защиты: Москва
• Количество страниц: 133 с. : ил.

СОДЕРЖАНИЕ
СОДЕРЖАНИЕ
ГЛАВА Ї. ВВЕДЕНИЕ
§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. АЛГОРИТМЫ ПОИСКА МИНИМУМОВ
§3.1. Одноэтапный алгоритм
§3.2. Двухэтапный алгоритм
§3.3. Быстродействие алгоритмов
§3.4. Выводы
ГЛАВА 4. СХЕМЫ АЛГОРИТМОВ ПОИСКА
§4.1. Схема одноэтапного алгоритма
§4.2. Схема двухэтапного алгоритма
§4.3. Нейронная сеть Хопфилда с дискретизированной матрицей
§4.4. Описание программной реализации
§4.5. Выводы
ЗАКЛЮЧЕНИЕ
ПРИЛОЖЕНИЕ
СПИСОК ЛИТЕРАТУРЫ

ГЛАВА 1. ВВЕДЕНИЕ
§1.1. Актуальность темы
Задачи дискретной оптимизации [1-8] широко распространены и встречаются практически во всех сферах человеческой деятельности. Многочисленные проблемы в математике, статистике, технике, науке, медицине и экономике могут рассматриваться как проблемы оптимизации. Задачей оптимизации является нахождение решения, которое удовлетворяет системе ограничений и максимизирует или минимизирует целевую функцию. Наиболее известными задачами дискретной оптимизации являются задача о рюкзаке, задача о коммивояжере, задача планирования вычислений для многопроцессорной системы, выбор оптимальной структуры автоматизированной системы управления и т.д. Решение этих задач связано с рядом трудностей. Например, полный перебор возможных решений, как правило, невозможен из-за большого объема вычислений. Из-за дискретности пространства решений неприменимы многие приемы, разработанные в математическом программировании, например, движение по направлению градиента, переход из одной точки допустимых решений в другую и т.д. Однако для большинства прикладных задач достаточно получить хорошее приближенное решение. За счет отказа от поиска точного решения часто удается построить простые алгоритмы для сложных задач. Поэтому на практике часто используются приближенные методы как альтернатива полному перебору [9-14].
Большое значение имеют вопросы эффективности алгоритмов решения задач дискретной оптимизации [1, 15]. Для дискретных задач не всегда пригодны критерии оценки эффективности алгоритмов оптимизации, используемые для непрерывных задач. Состояние теории в настоящее время не позволяет указать универсальные количественные, и даже качественные оценки эффективности вычислительных алгоритмов. Такие оценки дает лишь вычислительная практика.

При решении задач дискретной оптимизации характерным приемом является разбиение задачи на подзадачи или ветвление. Полученные подзадачи либо решают, либо, в свою очередь, применяют к ним процедуру ветвления. Решение всей задачи получается в результате анализа всех подзадач наиболее низкого уровня ветвления.
Основными методами дискретной оптимизации являются метод ветвей и границ, динамическое программирование, метод отсечений, генетические алгоритмы, нейросетевые алгоритмы.
В методе ветвей и границ [16] из рассматриваемой задачи получаются две подзадачи путем специального разбиения пространства решений и отбрасывания областей, заведомо не содержащих решения исходной задачи. В случае, когда целочисленные переменные являются булевыми, обычно используется аддитивный алгоритм (метод Балаша [17]). Метод ветвей и границ позволяет получать хорошие результаты, но только при малых размерностях задачи (N=50-60) [18-21].
Метод динамического программирования [22-25] применяется для решения динамических, т.е. меняющихся во времени, или многошаговых оптимизационных задачах. Метод строится на основе принципа оптимальности: оптимальное поведение в многошаговом процессе обладает тем свойством, что, какими бы ни были решение, принятое на последнем шаге, и состояние процесса перед последним шагом, предыдущие решения должны составлять оптимальное относительно этого состояния поведение. Таким образом, метод динамического программирования можно представить в виде трех этапов:
1. Исходная задача разбивается на подзадачи меньшего размера.
2. Находится оптимальное решение подзадач, рекурсивно применяя к каждой подзадаче тот же трехэтапный алгоритм, пока решение подзадачи не будет очевидно.
3. Используются решения подзадач для формирования решения исходной задачи.

время работы алгоритмов. Чтобы снизить требования к оперативной памяти и скорости алгоритмов для задач распознавания образов, еще в 60-х годах было предложено заменять матричные элементы их знаками, т.е. ±1. Нули остаются без изменений. Обзор работ по бинаризации приведен во введении. Сравнение приведенных в данной главе результатов исследований будет проводиться с результатами работы [121], в которой подробно исследовалась процедура бинаризации.
В данной главе предлагается подход, основанный на бинаризации. Его отличие заключается в том, что элементы исходно матрицы связей будут заменяться целыми числами. Еще одно отличие в том, что элементы близкие к нулю заменяются нулем. Будет показано, что введение такой области обнуления позволит существенно улучшить минимизационные качества алгоритма.
§2.1. Процедура дискретизации
Как можно понять из описания модели Хопфилда, основные требования на оперативную память налагает матрица связей. Вычислительная сложность алгоритма в основном связана с вычислением локального поля, что в свою очередь опять же упирается в действия с матрицей связей. Таким образом, очевидно, что именно модификация матрицы каким-либо способом позволит, хотя бы частично, решить проблемы с памятью и ускорением. Как упоминалось ранее, бинаризация позволила решить эти проблемы за счет эффективности алгоритма. В данной работе предлагается «расширение» процедуры клиппирования.
Рассмотрим случайную матрицу А, элементы которой подчинены некоторому симметричному распределению /(Ду). Дискретизация
заключается в замене матрицы А некоторой матрицей С. Элементами матрицы С являются целые числа в диапазоне [-