О некоторых алгоритмах работы с длинными строками и их применении в задачах дискретной оптимизации

• Автор: Панин, Александр Геннадьевич
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2011
• Место защиты: Тольятти
• Количество страниц: 157 с. : ил.

Содержание

Глава 1. Введение

1.1 Основные задачи исследования.

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

1.3 Краткое содержание работы

Глава 2. Фундаментальные понятия предметной области.

2.1 Эвристические алгоритмы

2.2 Вейвлетанализ

2.3 Кластеризация.

2.4 Генетические алгоритмы

2.5 Задачи обработки строк

Глава 3. Мультиэврнстический подход в задаче сравнения сигналов
акустической эмиссии
3.1 Математическая модель сигнала.
3.2 Предварительная обработка сигналов
3.2.1 Выделение импульсов акустической эмиссии.
3.2.2 Вейвлетпреобразование сигналов
3.2.3 Особенности применения технологии VII А.
3.3 Сравнение сигналов
3.3.1 Использование мультиэвристического подхода.
3.3.2 Функция корреляции.
3.3.3 Специальная версия алгоритма вычисления расстояния Лвенштейна для сравнения сигналов.
3.3.4 Ещ один способ задания признаков
3.4 Кластеризация.
3.5 Оптимизация параметров алгоритма
3.5.1 Генетический алгоритм
3.5.2 Метод Брента.
3.5.3 Параметры оптимизации
3.6 Результаты кластеризации
Глава 4. Мультиэвристический подход в задаче сравнения генетических последовательностей
4.1 Математическая модель ДНК.
4.2 Реализация мультиэвристичсского подхода.
4.3 Алгоритм поиска наибольшей общей подпоследователности.
4.4 Алгоритм НидлманаВунша.
4.5 Результат сравнения цепочек ДНК.
Глава 5. Алгоритм поиска наибольшей обшей подпоследовательности.
5.1 Математическая постановка задачи
5.2 Описание нового алгоритма.
5.2.1 Изменение порядка перебора ячеек матрицы .
5.2.2 Использование массивов длин префиксов.
5.2.3 Использование списков вхождения символов
5.3 Некоторые свойства алгоритма
5.4 Схема алгоритма .
5.5 Оценка сложности
5.6 Тестирование алгоритма
Глава 6. Апнроксимационный алгоритм поиска наибольшей общей подпоследовательности.
6.1 Описание алгоритма
6.2 Тестирование алгоритма
Заключение
Предметный указатель
Приложение 1
Приложение 2.
Приложение 3.
Приложение 4.
Литература


Это преобразование можно рассматривать как разновидность временно-частотного преобразования сигнала. В отличие от преобразования Фурье, традиционно применяемого для анализа сигналов, вейвлет-преобразование обеспечивает двумерную развёртку исследуемого одномерного сигнала, в результате чего появляется возможность исследовать свойства сигнала одновременно во временном и частотном пространствах [4]. Кластеризация - задача разбиения заданной выборки объектов . Для решения этой задачи прежде всего необходимо задать метрику на пространстве исходных объектов, от правильного выбора которой существенно зависит результат кластеризации. Решение задачи кластеризации всегда неоднозначно, так как не существует однозначно наилучшего критерия качества кластеризации. Кроме того, выбор метрики и количества кластеров, как правило, осуществляется на основе субъективных критериев. Кластерный анализ широко применяется для анализа статистических • данных в различных областях, сложных сетей взаимодействующих генов в биоинформатикс, для группировки результатов поиска в поисковых системах, для сегментации изображений и т. Генетический алгоритм - эвристический алгоритм поиска, в основе которого лежит модель биологической эволюции. В соответствии с этой моделью к возможным решениям задачи — особям — итеративно применяются операторы естественного отбора, скрещивания и мутации. Первоначальное множество особей - популяция - генерируется случайным образом. Оператор скрещивания создаёт одну или несколько новых особей, «рекомбинируя» их из случайно выбранных родительских особей. Мутация вносит в код особи случайные изменения. Приспособленность особи оценивается специальным алгоритмом - фитнес-функцией, и представляет собой качество решения. Генетический алгоритм не гарантирует нахождения оптимального-решения, но, как правило, средняя приспособленность популяции растёт в ходе эволюции,' и- через некоторое количество поколений можно получить решение, близкое к оптимальному. Генетические алгоритмы являются частью более общей группы методов, называемой эволюционными вычислениями, объединяющих различные варианты использования эволюционных принципов для достижения поставленной цели. Генетические алгоритмы применяются для решения- задач оптимизации функций, комбинаторной оптимизации, настройки и обучения искусственной нейронной сети, составления расписаний и многих других []. Опишем общую схему генетических алгоритмов на примере задачи оптимизации. Работа генетического алгоритма, как правило, начинается с формирования начальной популяции - конечного набора допустимых решений задачи (особей). Качество начальной популяции положительно влияет на время работы - чем выше средняя приспособленность, тем быстрее генетический алгоритм найдёт глобальный оптимум. Поэтому имеет смысл генерировать начальные решения с помощью каких-либо быстрых эвристических алгоритмов [2, , ]. После этого начинается процесс, моделирующий биологическую эволюцию. На каждом шаге эволюции с помощью оператора естественного отбора из популяции удаляются самые «слабые» особи. Затем к «выжившим» особям применяется оператор скрещивания. Существует много различных версий этого оператора. В простейшем случае по родительским особям Л7, . По аналогии с этим оператором скрещивания можно предложить и другие операторы, использующие произвольное число родителей []. Реализация оператора скрещивания может зависеть от особенностей кодирования решений в конкретных задачах. Так же существуют так называемые непрерывные генетические алгоритмы [], которые кодируют решение в виде последовательности вещественных чисел; для них существуют специальные версии оператора скрещивания []. Затем к каждой особи может применяется необязательный оператор мутации, с некоторой вероятностью случайным образом меняющий значение каждого параметра решения. Так же модификация особи может состоять не только в случайной мутации, но и в частичной перестройке решения алгоритмами локального поиска. Применение локального спуска позволяет генетическому алгоритму сосредоточиться только на локальных оптимумах.