Введение к работе
Актуальность темы. В настоящее время существует большое количество работ в области исследования аттракторов динамических систем. Решению задачи построения дифференциальных уравнений по экспериментальным данным посвящены работы: Р. Брауна, В. С. Анищенко, О. Л. Аносова, Т. Е. Вадивасовой., А. Н. Павловой, Н. Б. Янсона, Р. Кастро и Т. Сойера, Е. В. Никульчева и др. Однако, в работах, основанных на геометрическом анализе фазовых траекторий, не предложены методы выявления схожих и симметричных участков. Разработка автоматического поиска преобразований симметрии делает указанные методы конструктивными для моделирования систем различной природы. Вместе с тем, задача выявления преобразований симметрии многомерной числовой последовательности сводится к задаче выделения множества симметричных областей, которая, в свою очередь, является NP-полной задачей.
Одним из современных бионических принципов решения NP-полных задач является применение генетических алгоритмов (ГА) — адаптивных методов поиска, разновидности эволюционных вычислений, основанной на генетических процессах биологических организмов. Основные принципы ГА были сформулированы Д. X. Холландом (1975), и описаны в работах: Л. А. Гладкова, Д. И. Голдберга, В. В. Емельянова, В. В. Курейчика, В. М. Курейчика и др. Хотя модель эволюционного развития, применяемая в ГА, сильно упрощена, тем не менее, ГА являются мощным средством и могут применяться для широкого класса прикладных задач, включая те, которые трудно решить другими методами, особенно в области NP-полных задач оптимизации.
Всё вышесказанное делает разработку методики выявления симметрии в многомерных числовых последовательностях на основе использования эволюционных вычислений актуальной задачей.
Решение этой задачи позволит применить методику для других областей науки: для определения фрактальных структур в минералогии, исследования хаотических процессов при цифровой обработке сигналов, оценки симметрических явлений при исследовании медико-биологических систем, а также выявления преобразований симметрии в процессах различной физической природы.
Цель диссертационной работы. Разработка методики, направленной на выявление преобразований симметрии (поворот, сдвиг, растяжение/сжатие) и их числовых показателей в многомерных числовых последовательностях в условиях слабого нарушения симметрии. Основные задачи исследования.
-
Обзор методов реконструкции аттракторов и динамических моделей по временным рядам.
-
Формализация задачи выявления симметрических закономерностей в многомерных числовых последовательностях.
-
Обоснованный выбор геометрических методов предобработки и генетических алгоритмов для решения сформулированной задачи.
-
Разработка методики, позволяющей в автоматическом режиме выявить симметрии поворота, сдвига и растяжения/сжатия (масштабирования) в многомерных числовых последовательностях, получить числовые показатели преобразований, а также оценить степень нарушения симметрии.
-
Разработка специфических модификаций генетического алгоритма для нахождения решения задачи.
-
Разработка алгоритмического обеспечения для выявления преобразований симметрии и его программная реализация.
-
Анализ результатов по автоматическому выявлению симметрии поворота, сдвига и сжатия/растяжения в многомерных числовых последовательностях.
Объект исследования: многомерные числовые последовательности, полученные как результат восстановления и-мерного аттрактора по экспериментальным данным.
Предмет исследования: геометрические методы анализа числовых последовательностей и поиск решений оптимизационных задач с помощью генетических алгоритмов.
Методы исследования. В работе используются методы нелинейной динамики, математического моделирования, качественной теории систем, геометрические методы анализа числовых последовательностей, методы теории решения оптимизационных задач с помощью генетических алгоритмов и современные информационные технологии. Научная новизна исследования:
-
Разработана методика выявления преобразований симметрии в многомерных числовых последовательностях, основанная на научно обоснованном применении генетических алгоритмов.
-
Для контура, полученного путем соединения точек исходной многомерной числовой последовательности, разработана процедура его приведения в нормированную систему координат, инвариантную относительно преобразований сдвига, поворота, растяжения/сжатия.
-
Разработан генетический алгоритм поиска разбиения контура на множество непересекающихся фрагментов при условии максимизации их длины и минимизации нарушения симметрии.
Практическая ценность. Результаты диссертации использованы при выполнении НИР по гранту РФФИ, проект № 08-07-00433а «Построение динамических моделей управления распределением загрузки каналов связи в вычислительных сетях».
Разработано программное обеспечение «Методика выявления симметрии трёхмерных контуров», на которое получено свидетельство о регистрации программы для ЭВМ Роспатента, № 2008615062.
Реализация результатов работы. Результаты работы использованы для построения динамических моделей загрузки каналов связи в вычислительных сетях в ЗАО «Московский Центр Деловой Информации "БИНЕК"».
Апробация результатов работы. Результаты работы докладывались и обсуждались на 4-х научных конференциях и семинарах:
Третьей всероссийской научной конференции «Проектирование научных и инженерных приложений в среде MATLAB» (Санкт-Петербург, СПбГУ, 2007).
Семинаре молодых ученых «Задачи системного анализа, управления и обработки информации» (Москва, МГУПИ, 2006),
Научно-технической конференции молодых ученых МГУП (Москва, МГУП, 2008);
Регулярном научно-методическом семинаре кафедры прикладной математики и моделирования систем Московского государственного университета печати.
Публикации по теме диссертации: Основные результаты диссертации опубликованы в 5-й работах, в том числе имеется 1 статья в журнале, рекомендованном ВАК РФ.
Структура и объем диссертации. Диссертационная работа изложена на 124 страницах машинописного текста, и состоит из введения, четырёх глав, заключения и двух приложений.
