Введение к работе
Актуальность темы
Задачи, связанные с обработкой строк, возникают во многих областях науки и имеют очень большое прикладное значение. Среди этих областей - поиск информации в базах данных и в Интернете, анализ генетических последовательностей, поиск и исправление ошибок в тексте, сжатие данных и многие другие. Очень часто строки являются довольно длинными: например, длина генетических последовательностей достигает десятков миллионов символов. В таких случаях время получения точного решения рассматриваемых задач может оказаться слишком большим - поэтому разработка быстрых эвристических алгоритмов для подобных проблем является очень актуальной задачей.
Дискретная оптимизация широко применяется для решения различных задач, которые встречаются во многих сферах практической деятельности. Задачами дискретной оптимизации являются такие известные задачи, как задача коммивояжёра, задача о ранце, задачи выполнимости и минимизации булевых функций и многие другие. Для большинства подобных задач на сегодняшний день нет алгоритмов, решающих их за полиномиальное время. Для некоторых задач существуют алгоритмы, имеющие сложность ниже экспоненциальной, но всё же достаточно высокую: например, для разложения числа на множители существуют алгоритмы, имеющие субэкспоненциальную временную сложность1. Вследствие этого - несмотря на экспоненциальный рост вычислительных мощностей современных компьютеров - во многих прикладных задачах не удаётся найти точного решения за приемлемое время. Поэтому вместо точных алгоритмов для решения многих прикладных задач дискретной оптимизации применяются различные эвристические алгоритмы - позволяющие за приемле-
1 Д.Кнут. Искусство программирования, т.2. Получисленные алгоритмы. - Москва: Вильяме, 2007. -832 с. (Страницы 425-468.) Субэкспоненциальную сложность имеет, например, алгоритм Диксона - а
О /,e2V2v/)ogNv/loglO|N>\
именно, ч J , где N - число, которое требуется разложить на множители.
мое время получить решение, близкое к точному. Во всех известных автору
случаях хорошие результаты даёт применение мультиэвристического подхода .
Данная работа посвящена применению мультиэвристического подхода в области, которая, на первый взгляд, мало для этого подходит - в задачах обработки строк большой длины. Однако на самом деле это не только возможно, но и, как показано в работе, вполне оправдано. Применение указанного метода решения задач дискретной оптимизации к обработке последовательностей символов возможно благодаря связи между указанными разделами теоретической информатики, заключающейся в следующем. Как известно, задачами дискретной оптимизации называются задачи о нахождении экстремума некоторой функции, заданной на дискретном множестве. При этом в некоторых задачах
2 Б.Мельников. Мультиэвристический подход к задачам дискретной оптимизации // Кибернетика и
системный анализ (НАН Украины), 2006, №3. С.32-42.
См. работы автора, приведённые ниже в списке его публикаций, а также следующие публикации:
А.Белозёрова, БМельников. Применение комплекса эвристик в задаче составления схемы нук-лидных превращений // Сборник трудов Второй Всероссийской научной конф. «Методы и средства обработки информации», Москва, изд-во МГУ им М.В.Ломоносова, 2005. С.208-214;
А.Белозёрова, Г.Шиманский. Оптимизация схемы расчёта трансмутации методом ветвей и границ // Труды семинара «Физ. моделирование изменения свойств реакторных материалов в номинальных и аварийных условиях», Димитровград, изд-во ФГУП ГНЦ РФ НИИАР, 2005. С.75-77;
BMelnikov, A.Radionov, V.Gumayunov. Some special heuristics for discrete optimization problems // 8th Int. Conf. on Enterprise of Information Systems (ICEIS-2006), Pathos (Cyprus) 91-95;
М.Алёхина, АЛысенко, Б.Мельников. Об одном подходе к моделированию вычислительных устройств. // Известия вузов. Поволжский регион. Физико-математические науки. No.2,2007. С.2-9;
БМельников, Е.Мельникова. Кластеризация ситуаций и принятие решений в задачах дискретной оптимизации. // Известия вузов. Поволжский регион. Технические науки. № 2,2008. С.23-28;
СБаумгертнер, Б.Мельников. Мультиэвристический подход к проблеме звёздно-высотной минимизации недетерминированных конечных автоматов // Вестник Воронежского гос. унив., сер. Сист. анализ и инф. техн., 2010, № 1, С.5-7;
БМельников, С.Эйрих. Подход к комбинированию незавершённого метода ветвей и границ и алгоритма имитационной нормализации // Вестник Воронежского гос. ун-та, сер. Сист. анализ и инф. техн., 2010, № 1, С.35-38.
обработки строк нужно найти значение некоторой метрики (например, степени сходства) или максимум некоторой функции (например, наибольшая общая подпоследовательность), заданных на множестве строк. Множество строк является дискретным - и поэтому такие задачи являются задачами дискретной оптимизации.
Одной из рассматриваемых в диссертации задач является задача обработки сигналов акустической эмиссии (АЭ) - однако при описании актуальности данной работы стоит отметить, что подобные задачи возникают в самых разных областях, связанных с обработкой строк большой длины. Необходимость создания специальных, «естественных» метрик на подобных строках проявляется в алгоритмах, в которых нужно сравнивать подобные сигналы - например, при распознавании речевых сигналов3, анализе сейсмических данных4, диагностике технических систем5 и т.п.
При этом становится очень важным анализ «адекватности» создаваемых метрик. Такой анализ заключается в сравнении результатов кластеризации с «правильным» результатом (результатом, предлагаемым человеком-экспертом), или в сравнении результатов кластеризации с результатами, полученными при использовании других метрик (в том числе - ранее не описанных).
Цель работы
Целью диссертационной работы являлась разработка и описание эвристических алгоритмов работы со строками большой длины, описание оригинальных модификаций разработанных ранее эвристических оценок эффективности эвристических алгоритмов (на основе модели сравнения алгоритмов с эвристиками и без них), а также описание вариантов применения этих алгоритмов в не-
3 А.Аграновский, Д.Леднов. Теоретические аспекты алгоритмов обработки и классификации речевых
сигналов - Москва: Радио и связь, 2004. - 164 с.
4 А.Шевченко. Скважинная сейсморазведка. - Москва: Изд-во Российского государственного универ
ситета нефти и газа им. Губкина, 2002. - 129 с.
5 Ю.Сато. Обработка сигналов. Первое знакомство. - Москва: Додека, 2000. - 175 с.
скольких задачах дискретной оптимизации. При этом было необходимо разработать оригинальный алгоритм сравнения эффективности эвристических алгоритмов - поскольку подход, предлагавшийся в нескольких известных автору работах, оказался неприемлемым6.
Основные задачи исследования:
-
Разработка - на основе мультиэвристического подхода к задачам дискретной оптимизации - оригинальной метрики на множествахспециальным образом описанных дискретных сигналов.
-
Разработка и реализация алгоритма кластеризации сигналов акустической эмиссии на основе разработанной метрики.
-
Разработка - на основе мультиэвристического подхода кзадачам дискретной оптимизации - специальной метрики на множестве символьных строк. Получение - в зависимости от конкретных применяемых эвристик - нового подхода к определению расстояния между строками, а также быстрых алгоритмов для аппроксимации расстояния Лёвенштейна.
-
Применение разработанных метрик для создания и реализации алгоритмов сравнения генетических последовательностей.
-
Разработка и реализация оригинального алгоритма сравнения эффективности (качества) эвристических алгоритмов.
Е.Мельникова. Применение кластеризации ситуаций в эвристических алгоритмах для задач дискретной оптимизации: дисс. ... жанд. физ.-мат. наук : 05.13.18 // Тольятти, ТГУ, 2009. - 152 с. См. также соответствующие ссылки, приведённые в указанной диссертации.
Невозможность применения известных автору подходов объясняется следующими обстоятельствами. При их использовании априори либо известна сама фитнесс-функция, либо понятны критерии для её практического описания. А как в любых алгоритмах кластеризации, так и случае сравнения длинных цепочек ДНК, мы не знаем вариантов такой фитнесс-функции (т.е. не знаем, «что такое хорошо»). Точнее, известные нам критерии являются слишком неформальными - и, вследствие этого, требуют экспертной проверки.
Объект исследования
Объектами исследования являются длинные строки, а также некоторые структуры данных в задачах дискретной оптимизации, приводящие к работе с длинными строками.
Предмет исследования
Предметом исследования являются алгоритмы работы со строками.
Методы исследования
В качестве аппарата исследований применяются математические методы разработки и анализа алгоритмов.
Результаты исследования
Результатами диссертационного исследования являются новые математические модели и алгоритмы для решения рассматриваемых проблем, а также реализация этих алгоритмов современными программными средствами.
Научная новизна
Разработанные алгоритмы решения рассматриваемых задач являются новыми. Мультиэвристический подход впервые был применён для сравнения сигналов и строк.
Практическая значимость исследования
Разработанные алгоритмы могут быть применены для практического решения задач дискретной оптимизации - в нескольких различных прикладных задачах, причём также и в задачах, не рассматриваемых в диссертационной работе непосредственно.
Достоверность результатов
Достоверность подтверждается результатами вычислительных экспериментов, а также сравнением результатов работы алгоритмов с применением разработанных эвристик и результатов решения рассматриваемых задач другими методами.
Основные положения, выносимые на защиту:
-
Алгоритм кластеризации сигналов акустической эмиссии.
-
Алгоритм сравнения генетических последовательностей, основанный на мультиэвристическом подходе.
-
Алгоритм точного поиска наибольшей общей подпоследовательности.
-
Алгоритм приближённого поиска наибольшей общей подпоследовательности.
-
Метод анализа эффективности эвристических алгоритмов и соответствующих программ и его применение для разработанных алгоритмов.
Апробация работы
Результаты диссертационной работы докладывались и обсуждались на:
-
VII Всероссийской научно-технической конференции «Проблемы информатики в образовании, управлении, экономике и технике», Пенза, 2007;
-
3-й Международной научно-практической конференции студентов и преподавателей «Информационные технологии в современной жизни», Бонн (Санкт-Августин), Германия, 2008;
-
конференции «Технологии искусственного интеллекта в экономике», Москва-Дубна, 2008;
-
VII Всероссийской межвузовской конференции молодых учёных, Санкт-Петербург, 2010;
-
Международной конференции «Современные проблемы математики, информатики и биоинформатики», Академгородок, Новосибирск, 2011;
-
Международной научно-практической конференции «Молодёжь и наука: модернизация и инновационное развитие страны», Пенза, 2011.
Публикации
По теме диссертации опубликовано 8 работ в рецензируемых научных журналах и изданиях, из них 2 - в изданиях, рекомендованных ВАК.
Личный вклад автора
Постановка задач осуществлялась научным руководителем. Описываемые в диссертации эвристики и подходы, разработанные алгоритмы решения поставленных задач выполнены автором самостоятельно, либо в соавторстве с научным руководителем. Алгоритмы поиска наибольшей общей подпоследовательности, а также эвристики для мультиэвристического подхода разработаны автором самостоятельно.
Структура и объём диссертации
Диссертация состоит из введения, 6 глав, 4 приложений и списка литературы, состоящего из 73 наименования источников отечественных и зарубежных авторов. Общий объём диссертации составляет 157 страниц.
