автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:Методика эволюционного выявления преобразований симметрий в многомерных числовых последовательностях

На правах рукописи

OQ3452886

Козлов Олег Владимирович

Методика эволюционного выявления преобразований симметрии в многомерных числовых последовательностях

05.13.17 — Теоретические основы информатики

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

003452886

Работа выполнена на кафедре прикладной математики и моделирования систем Московского государственного университета печати

Научный руководитель:

доктор технических наук, доцент Евгений Витальевич Никульчев

Официальные оппоненты:

доктор физико-математических наук, профессор Владимир Александрович Ковалев

кандидат технических наук Михаил Евгеньевич Волович

Ведущая организация:

«МАТИ» - Российский государственный технологический университет им. К. Э. Циолковского

Защита состоится «04» декабря 2008 г. в 14— на заседании диссертационного совета Д 212.147.03 в Московском государственном университете печати по адресу: Москва, ул. Прянишникова, 2а, зал заседаний ученого совета.

С диссертацией можно ознакомиться в библиотеке МГУП.

Автореферат разослан «1» ноября 2008 г.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. В настоящее время существует большое количество работ в области исследования аттракторов динамических систем. Решению задачи построения дифференциальных уравнений по экспериментальным данным посвящены работы: Р. Брауна, В. С. Анищенко, О. Л. Аносова, Т. Е. Вадивасовой., А. Н. Павловой, Н. Б. Янсона, Р. Кастро и Т. Сойера, Е. В. Никульчева и др. Однако, в работах, основанных на геометрическом анализе фазовых траекторий, не предложены методы выявления схожих и симметричных участков. Разработка автоматического поиска преобразований симметрий делает указанные методы конструктивными для моделирования систем различной природы. Вместе с тем, задача выявления преобразований симметрий многомерной числовой последовательности сводится к задаче выделения множества симметричных областей, которая, в свою очередь, является ЫР-полной задачей.

Одним из современных бионических принципов решения ЫР-полных задач является применение генетических алгоритмов (ГА) — адаптивных методов поиска, разновидности эволюционных вычислений, основанной на генетических процессах биологических организмов. Основные принципы ГА были сформулированы Д. X. Холландом (1975), и описаны в работах: Л. А. Гладкова, Д. И. Голдберга, В. В. Емельянова, В. В. Курейчика, В. М. Курейчика и др. Хотя модель эволюционного развития, применяемая в ГА, сильно упрощена, тем не менее, ГА являются мощным средством и могут применяться для широкого класса прикладных задач, включая те, которые трудно решить другими методами, особенно в области ЫР-полных задач оптимизации.

Всё вышесказанное делает разработку методики выявления симметрий в многомерных числовых последовательностях на основе использования эволюционных вычислений актуальной задачей.

Решение этой задачи позволит применить методику для других областей науки: для определения фрактальных структур в минералогии, исследования хаотических процессов при цифровой обработке сигналов, оценки симметрических явлений при исследовании медико-биологических систем, а также выявления преобразований симметрий в процессах различной физической природы.

Цель диссертационной работы. Разработка методики, направленной на выявление преобразований симметрий (поворот, сдвиг, растяжение/сжатие) и их числовых показателей в многомерных числовых последовательностях в условиях слабого нарушения симметрии. Основные задачи исследования.

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

временным рядам.

2. Формализация задачи выявления симметрических закономерностей в

многомерных числовых последовательностях.

3. Обоснованный выбор геометрических методов предобработки и генетических алгоритмов для решения сформулированной задачи.

4. Разработка методики, позволяющей в автоматическом режиме выявить симметрии поворота, сдвига и растяжения/сжатия (масштабирования) в многомерных числовых последовательностях, получить числовые показатели преобразований, а также оценить степень нарушения симметрии.

5. Разработка специфических модификаций генетического алгоритма для нахождения решения задачи.

6. Разработка алгоритмического обеспечения для выявления преобразований симметрий и его программная реализация.

7. Анализ результатов по автоматическому выявлению симметрий поворота, сдвига и сжатия/растяжения в многомерных числовых последовательностях.

Объект исследования: многомерные числовые последовательности, полученные как результат восстановления и-мерного аттрактора по экспериментальным данным.

Предмет исследования: геометрические методы анализа числовых последовательностей и поиск решений оптимизационных задач с помощью генетических алгоритмов.

Методы исследования. В работе используются методы нелинейной динамики, математического моделирования, качественной теории систем, геометрические методы анализа числовых последовательностей, методы теории решения оптимизационных задач с помощью генетических алгоритмов и современные информационные технологии. Научная новизна исследования:

1. Разработана методика выявления преобразований симметрий в многомерных числовых последовательностях, основанная на научно обоснованном применении генетических алгоритмов.

2. Для контура, полученного путем соединения точек исходной многомерной числовой последовательности, разработана процедура его приведения в нормированную систему координат, инвариантную относительно преобразований сдвига, поворота, растяжения/сжатия.

3. Разработан генетический алгоритм поиска разбиения контура на множество непересекающихся фрагментов при условии максимизации их длины и минимизации нарушения симметрии.

Практическая ценность. Результаты диссертации использованы при выполнении НИР по гранту РФФИ, проект № 08-07-00433а «Построение динамических моделей управления распределением загрузки каналов связи в вычислительных сетях».

Разработано программное обеспечение «Методика выявления симметрий трёхмерных контуров», на которое получено свидетельство о регистрации программы для ЭВМ Роспатента, № 2008615062.

Реализация результатов работы. Результаты работы использованы для построения динамических моделей загрузки каналов связи в вычислительных сетях в ЗАО «Московский Центр Деловой Информации "БИНЕК"».

4

Апробация результатов работы. Результаты работы докладывались и обсуждались на 4-х научных конференциях и семинарах:

- Третьей всероссийской научной конференции «Проектирование научных и инженерных приложений в среде МАТЬАВ» (Санкт-Петербург, СПбГУ,

2007).

- Семинаре молодых ученых «Задачи системного анализа, управления и обработки информации» (Москва, МГУПИ, 2006),

- Научно-технической конференции молодых ученых МГУП (Москва, МГУП,

2008);

- Регулярном научно-методическом семинаре кафедры прикладной математики и моделирования систем Московского государственного университета печати.

Публикации по теме диссертации: Основные результаты диссертации опубликованы в 5-и работах, в том числе имеется 1 статья в журнале, рекомендованном ВАК РФ.

Структура и объем диссертации. Диссертационная работа изложена на 124 страницах машинописного текста, и состоит из введения, четырёх глав, заключения и двух приложений.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

Во введении обосновывается актуальность исследования характеристик восстановленных аттракторов динамических систем в целях выявления симметрий (поворот, сдвиг, сжатие/растяжение) с помощью геометрических методов анализа и генетических алгоритмов. Также формулируются цели, задачи, объект и предмет исследования, научная новизна и практическая ценность; приводится краткая характеристика основных разделов диссертации. В первой главе проводится обзор методов нелинейной динамики, включая методы реконструкции систем по экспериментальным данным.

Рассмотрен алгоритм глобальной реконструкции уравнений динамической системы по ее одномерной реализации (Д. Кремерс, А. Хюблер, 1987 г.). По одномерной реализации процесса в некоторой системе, которая считается «черным ящиком», восстанавливается фазовый портрет, топологически эквивалентный аттрактору исходной системы по теореме Ф. Такенса. Искомая динамическая система задается в виде «-мерного дискретного отображения:

где х,, — координаты вектора состояния, рассмотренного в моменты времени /; — нелинейные функции.

Выбор функций осуществляется априорно и достаточно произвольным способом. Обычно представляются в виде суперпозиции некоторых базисных функций, наиболее популярным является представление в виде полиномов (П. Грассбергер, И. Прокаччо, Р. Кастро, Т. Сойер, Р. Браун, М. Мюннер, М. Попп, В. С. Анищенко, О. Л. Аносов, Т. Е. Вадивасова, А. Н. Павлов, Н. Б. Янсон и др.). Далее применяется метод наименьших квадратов, в результате которого модель получается громоздкой, но при

удачном выборе общего вида нелинейных функций воспроизводит сигнал с высокой степенью точности.

Проведен анализ геометрического метода моделирования нелинейных систем, допускающих группы симметрий, по экспериментальным данным (Е. В. Никульчев), позволяющий на основании временного ряда идентифицировать параметры модели в форме Шильникова-Овсянникова. Сделан вывод, что в рассмотренном методе отсутствуют конструктивные предложения по поиску симметрий фазовых траекторий, что определяет необходимость разработки автоматической процедуры выявления преобразований симметрий. Во второй главе сформулирована задача выявления преобразований симметрий (поворот, сдвиг, масштабирование) многомерной числовой последовательности, полученной в результате восстановления «-мерного аттрактора по экспериментальным данным, как задача выделения симметричных фрагментов. Необходимо выделить на исходной последовательности набор участков таким образом, чтобы при приведении их к единому масштабу, положению и углу поворота они были бы максимально схожи между собой, а также получить численные показатели преобразований, переводящих один фрагмент в другой без учёта нарушений симметрии, и дать численную оценку степени нарушения симметрии.

Доказана NP-полнота поставленной задачи путём сведения её к задаче о поиске клики (clique) графа, являющейся NP-полной.

Исходная задача разбита на подзадачи предобработки и подбора лучшего решения.

Задача предобработки заключается в выделении на исходной последовательности набора рассматриваемых фрагментов и получении на основе каждого из них дескриптора, т. е. образа, инвариантного относительно сдвига, поворота и масштабирования исходного фрагмента.

Рассмотрены известные алгоритмы решения поставленной задачи предобработки, а именно: «Неокогнитрон» К. Фукушимы, его модификации и метод предобработки двухмерных контуров с помощью дискретного преобразования Фурье, предложенный С. Осовским. На основании проведенного анализа сделан вывод о необходимости разработки нового алгоритма получения дескрипторов фрагментов с учётом специфики поставленной задачи.

Задача подбора лучшего решения заключается в отборе совокупности дескрипторов непересекающихся фрагментов при максимальной длине и минимальном нарушении симметрий.

Рассмотрены наиболее подходящие к рассматриваемому классу задач многокритериальной оптимизации алгоритмы, а именно: алгоритмы на основе моделирования отжига, методы кластеризации и генетические алгоритмы. На основании проведённого анализа в качестве метода решения обоснованно выбраны генетические алгоритмы.

Разработана методика выявления преобразований симметрий фрагментов контура, состоящая из двух этапов.

Этап I. Предобработка.

1. Получение «-мерного контура (восстановление аттрактора).

2. Маркировка полученного контура.

3. Извлечение фрагментов.

4. Нормализация фрагментов.

Этап II. Генетический подбор решения задачи разбиения контура на

фрагменты.

На основе проведенного анализа уточнена формулировка постановки задачи, заключающаяся в разработке механизмов, реализующих предложенную методику.

В третьей главе описывается алгоритмическое обеспечение первого этапа методики выявления преобразований симметрий фрагментов контура, выполняющее предобработку данных.

Описан механизм выделения фрагментов исходного /¡-мерного контура, полученного путём восстановления аттрактора, заключающийся в определении на нём специальных точек - маркеров. В качестве маркеров имеет смысл рассматривать только некоторые точки контура, например, экстремумы функций каждой из координат (рис. 1) и точки равномерно распределённые по длине слабо изменяющихся участков, т. к. выделение всех возможных фрагментов из контура увеличивает затраты ресурсов на поиск решения основной задачи не пропорционально достигаемому увеличению точности. Такой подход (маркировка экстремумов) обеспечивает достаточно рациональное разбиение контура, хотя и является избыточным. В дальнейшем рассматриваются только те фрагменты, которые образуются всеми возможными парами маркеров.

Предложен механизм нормализации выделенных фрагментов, целью которого является преобразование каждого выделенного фрагмента в дескриптор - образ, инвариантный относительно переноса, поворота и масштабирования исходного фрагмента (рис. 2), а также получение численных показателей этого преобразования.

Рис. 1 .Примермаркировки экстремумов контура

и их общий дескриптор (снизу) полученный в результате нормализации. Предлагается использовать следующую последовательность действий:

1. Выделение во фрагменте так называемых «осей» - пар точек, расстояние между которыми максимально в текущем пространстве-проекции.

2. Поворот фрагмента таким образом, чтобы его оси стали параллельны координатным осям.

3. Построение ограничивающего фрагмента и-мерного параллелепипеда и сдвиг фрагмента таким образом, чтобы центр этого параллелепипеда совпал с центром координат.

4. Масштабирование фрагмента таким образом, чтобы длина его главной оси стала равна 1.

Фрагмент и-мерного контура ^ состоящий из т действительных точек, представляется в виде матрицы т*п:

гдеХ, =[*,, х,л ... х1т]Т,1 = 1,п.

Всего в фрагменте можно выделить п-1 ось. В трёхмерном случае (рис. 3) оси будет две: пара наиболее удалённых точек в пространстве ОХ1Х2Х3 (главная ось А1) и пара наиболее удалённых точек в проекции фрагмента на плоскость Р, перпендикулярную А1 (ось второго порядка А2).

дескриптор с ограничивающим параллелепипедом (справа).

Чтобы А1 стала параллельна координатной оси X/, необходимо произвести п-1 поворот в плоскостях ОХ,Х„, ОХ:Х„_,,...,ОХ,Х2. После этого преобразования А2 находится простым перебором точек в пространстве-проекции ОХ2...Х„ и выбором точки с максимальным расстоянием от оси X/. В приведённом трёхмерном случае это означает, что плоскость Р совпадёт с плоскостью ОХ2Х3. Для того, чтобы А2 стала параллельной координатной оси Х2 необходимо произвести п - 2 поворотов в плоскостях ОХ]Х„_:, ...,ОХ2Х3 и т.д.

Приводится пошаговое описание алгоритма нормализации для общего случая фрагмента /2-мерного контура, в котором применяется метод однородных координат, позволяющий описывать любое преобразование симметрий, а также их последовательность одной матрицей размера Сп+1)х(п+1).

Результатом алгоритма нормализации является дескриптор фрагмента Рнорт матрица Мнорм , осуществляющая преобразование фрагмента в его дескриптор, а также набор показателей и матриц всех промежуточных преобразований: п-1 матриц сдвига, (п2-п)/2 матриц поворота и одна матрица масштабирования. Матрица преобразования одного фрагмента в другой получается следующим образом:

^преобрАВ ~ МнориЛ х ^нор мВ'

Предлагается механизм численной оценки нарушения симметрии двух произвольных фрагментов РА и Рв, основанный на свойствах дискретного преобразования Фурье (ДПФ). Для и-мерного дескриптора заданного /и-точками независимо для каждой координаты применяется п одномерных

преобразований Фурье следующего вида:

™ ——, —

р=1

Результатом преобразования будет спектр следующей структуры: ^=[^.0 ••• ^,т]Т> <1 = 1,п.

Пары (5, ^М^ 5„_2),...,($(я

ЯВЛЯЮТСЯ

комплексно

сопряженными числами. Переход от спектра к исходному контуру (дескриптору) осуществляется с помощью обратного дискретного преобразования Фурье (ОДПФ) вида:

Предлагается критерий оценки близости контуров, основанный на свойстве ДПФ выделения главных компонент: чем ближе пара сопряженных элементов к середине спектра, тем более мелкие, высокочастотные особенности контура она описывает. Каждая из пар, сопряженных элементов спектра, определяет при восстановлении эллипс, а вся восстановленная фигура является суперпозицией этих эллипсов.

В качестве числовой оценки различия между контурами (нарушения симметрии в случае сравнивания дескрипторов фрагментов) предлагается суммировать расхождения соответствующих элементов спектров этих контуров после ДПФ (1) с учётом относительной важности различных частот спектра.

где ц — количество сопряженных пар элементов спектра, п - размерность фазового пространства, /?, - коэффициенты дисконтирования (г = 1,</), определяющие степень важности составляющих спектра по частотам, 5() — соответствующие элементы спектра контуров А и В. Коэффициенты Д выбираются эмпирически, исходя из условий задачи. В работе рассматривалась задача выявления симметрий низкочастотных колебаний, поэтому выбран экспоненциальный вид зависимости Д от номера члена ряда разложения Фурье.

В четвёртой главе описывается алгоритмическое обеспечение второго этапа методики выявления преобразований симметрий фрагментов контура, выполняющее подбор решения задачи с помощью генетического алгоритма.

Предлагается модификация алгоритма генетического поиска, учитывающая специфику поставленной задачи и включающая создание следующих специальных механизмов.

Формулируется специфика задачи, заключающаяся в невозможности описания решения битовым полем фиксированной длины, а также в том, что не любая последовательность из отобранных ранее фрагментов является корректным решением (рис. 4). Предлагается представление решения последовательностью произвольной длины, содержащей номера фрагментов.

(1)

1. Генерация случайного решения задачи (хромосомы).

2. Скрещивание решений (кроссинговер).

3. Случайные изменения при скрещивании решений (мутации).

х маркеры фрагменты исходный контур

Рис. 4. Исходный маркированный контур и набор выделенных из него фрагментов Пунктиром выделено одно из возможных случайных решений.

Предлагается алгоритм случайной генерации решения, основной особенностью которого является сортировка списка фрагментов и построение матрицы смежности фрагментов. В каждой её ячейке указывается 1, если фрагмент / может находиться в одном решении рядом с фрагментом у, и 0 в противном случае. Пошаговое описание алгоритма имеет вид.

1. Выбрать случайный стартовый фрагмент: сгенерировать случайное число в диапазоне от 1 до п. Стартовыми считаются фрагменты, у которых нет смежных предшественников, они находятся в начале сортированного списка фрагментов.

2. Добавить текущий фрагмент в генерируемую цепочку.

3. Для текущего фрагмента извлечь из матрицы смежности показатель т - количество соседей и к— номер первого соседа.

4. Если т=0, фрагмент финишный, генерация цепочки окончена - выход.

5. Сгенерировать случайный номер соседа в диапазоне от 0 до т.

6. Сделать текущим фрагмент к+т и перейти к шагу {2}.

Предлагается механизм скрещивания (кроссинговера) решений,

позволяющий получать из двух родительских решений два валидных дочерних решения: случайным образом на исходном контуре выбирается позиция скрещивания, которая, скорее всего, попадает в середину фрагментов родительских решений. Из двух родителей выбирается один, целостность которого приоритетна: если позиция скрещивания попадает на середину фрагмента, то разделение происходит в точке его окончания. После этого из родительских решений собирается два дочерних, в которых используются их соответствующие части.

Предлагается механизм случайных модификаций (мутаций) при скрещивании решений, не нарушающий валидность генерируемых дочерних решений, заключающийся в случайной замене одного из родителей при скрещивании на новое, случайно сгенерированное решение с определённой вероятностью, а также исключении у дочерних решений случайных фрагментов.

Для оценки схожести дескрипторов вводится критерий:

МАВ=---, (2)

' 1 + А,,

где ИЛВ — оценка, вычисляемая по формуле (1).

11

Предложены следующие критерии оценки решения:

1. Средний показатель схожести пар дескрипторов фрагментов входящих в решение:

К=—г-^-У У Л^,-ягах, (3)

где к - количество фрагментов в решении п, а - схожесть фрагментов / и j, вычисляемая в соответствии с (2).

2. Длина покрытия фрагментами исходного контура:

Л/„ шах, (4)

(=1

где к— количество фрагментов в решении п, а Ь— длина фрагмента г. Задача поиска решения многокритериальна, в общем случае область решений в пространстве критериев имеет вид, изображенный на рис. 5 (серая область слева).

ш

ш

Область решений

Ш

средняя попарная схожесть фрагментов

Рис. 5. Область решений в пространстве критериев (3) и (4), и области этапов подбора решения

Предлагается вести однокритериальный поиск последовательными этапами (рис. 5), на каждом из которых длина покрытия фрагментами решений исходного контура ограничена снизу, а в качестве оценки использовать критерий (3). Этап завершается при выполнении условий сходимости, количество этапов задаётся изначально. Это позволяет равномерно исследовать пространство критериев и получить набор Парето-оптимальных решений, как множество компромиссных решений по противоречивым критериям (3) и (4).

Сформулирован обобщенный критерий оценки:

Ф„ = ■ -> тах > (5)

где п - номер особи, Ь- длина исходного контура.

С помощью критерия (5) производится выбор единственного решения из множества предварительно отобранных Парето-оптимальных решений.

Проводится обзор и обосновывается выбор механизмов отбора особей (решений) в следующее поколение и выбора родителей для скрещивания. Рассмотрены следующие механизмы отбора: элитарный, турнирный и метод рулетки. Выбран элитарный тип отбора (в следующее поколение переходят п

лучших особей из числа родителей и детей) в силу его свойства сохранения лучших решений и большей, по сравнению с аналогами, иеленаправлености поиска. Рассмотрены следующие механизмы выбора родителей: панмиксия, инбридинг и аутбридинг. Выбран механизм инбридинга (случайный выбор одного родителя, второй же выбирается таким образом, чтобы его показатель критерия схожести был максимально схож с первым), в силу того, что из набора рассмотренных, он наилучшим образом компенсирует избыточную скорость сходимости элитарного отбора за счет более широкого распределения особей популяции в области поиска.

Вводится требование уникальности особей в популяции, что снижает скорость сходимости, но расширяет область поиска решений и при изменении условий после схождения (переход к следующему этапу) препятствует вырождению генофонда популяции.

Предлагается следующая итеративная процедура генетического отбора.

1. Создание начальной популяции из случайных решений (особей).

2. Установка ограничения на область допустимых решений по длине.

3. Оценка всех решений в популяции по критерию (3), усечение популяции таким образом, чтобы в ней осталось N наиболее приспособленных особей.

4. Произведение N скрещиваний особей, согласно стратегии инбридинга;

5. Мутация дочерних решений с вероятностью М.

6. Совмещение промежуточной и основной популяции, для сохранения найденных лучших решений.

7. Проверка условий сходимости популяции (к шагов с неизменными средними параметрами решений или р шагов с неизменным лучшим решением, причём р на порядок больше к), в случае их невыполнения переход к шагу {3}.

8. Переход к следующему этапу - расширение области допустимых решений по длине, если это ещё возможно, то переход к шагу {3}.

9. Выбор из набора полученных Парето-оптимальных решений наилучшего по композитному критерию (5).

Рассмотрены примеры применения методики (рис.6-14). Методика применена для выявления симметричных участков временного ряда, порожденного уравнением х, = 30 / 50) + / Бт(/ / 7) /100. На рис. 6-8 приведены результаты работы программного обеспечения методики.

Методика использовалась для выявления симметрий в восстановленном аттракторе системы Ресслера (с коэффициентами а=0,2; ¿=0,2; с=2,6). Графическое представление результатов приведено на рис. 9-11.

В рамках проекта построения динамических моделей управления распределением загрузки каналов связи в вычислительных сетях, восстановлен аттрактор и выявлены преобразования симметрий в динамике загрузки вебсервера. Результаты приведены на рис. 12-14.

Рис. 6. Исходные данные (слева) и фазовый портрет (справа)

Л 05 ое 0.7 С=3 0.9

средняя попарная схожесть фрагментов

количество итераций

количество итераций

Рис. 7. Жизненный цикл популяции в пространстве критериев (слева) и графики изменения оценки победителя по критерию А (справа-сверху) и В (справа-снизу)

5® 63?

1, время

' Х2

I, время

... * . *

Рис. 9. Исходные данные (слева) и фазовый портрет (справа)

средняя попарная схожесть фрагментов

количество итерации

Рис. Ю. Жизненный цикл популяции в пространстве критериев (слева) и графики изменения оценки победителя по критерию А (справа-сверху) и В (справа-снизу)

1, время

количество итераций

Рис. 12. Исходные данные (слева) и фазовый портрет (справа)

2001-,-,-1-,-■-,-

оз о ж о i о й5 05 056 об количество итераций

средняя попарная схож есть фрагментов

Рис. 13. Жизненный цикл популяции в пространстве критериев (слева)

Анализ результатов показал, что разработанная методика позволяет автоматически выявлять преобразования симметрий в произвольных числовых последовательностях и оценивать степень нарушения симметрии. В задачах, где необходимо выяснить подтверждение допущения системой группы симметрий требуется дополнительный анализ результатов — введение порогов степени нарушения симметрии и т.д.

Определены наиболее важные параметры процедуры выявления симметрий: распределение величины Д в оценке схожести фрагментов (1) и ограничение длины рассматриваемых фрагментов исходной последовательности.

Определена область эффективного применения разработанной методики, которую составляют фазовые портреты динамических систем, допускающих группы симметрий. Сделан вывод, что результаты могут быть использованы для выявления преобразований сдвига, поворота и масштабирования в процессах различной физической природы.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

1. Проведён обзор методов реконструкции аттракторов и динамических моделей по временным рядам.

2. Формализована задача выявления симметрических закономерностей в многомерных числовых последовательностях, доказана её МР-полнота.

3. Обоснован выбор геометрических методов предобработки и генетических алгоритмов для решения сформулированной задачи.

4. Разработана методика выявления преобразований симметрий в многомерных числовых последовательностях, позволяющая получить числовые показатели преобразований, а также оценить степень нарушения симметрии.

5. Для контура, полученного путем соединения точек исходной многомерной числовой последовательности, разработана процедура приведения в нормированную систему координат, инвариантную относительно преобразований сдвига, поворота, растяжения/сжатия.

6. Разработан генетический алгоритм поиска разбиения контура на множество непересекающихся фрагментов при условии максимизации их длины и минимизации нарушения симметрий.

7. Разработано и программно реализовано алгоритмическое обеспечение методики выявления преобразований симметрий. Получено свидетельство Роспатента о регистрации программы.

8. Результаты диссертации использованы при выполнении НИР по гранту РФФИ, проект № 08-07-00433а и для построения динамических моделей загрузки каналов связи в вычислительных сетях в ЗАО «Московский Центр Деловой Информации "БИНЕК"».

9. Проведен анализ результатов выявления преобразований симметрий в экспериментальных и модельных данных.

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

В журналах, входящих в перечень периодических изданий ВАК.

1. Козлов О. В. Методика эволюционного выявления симметрических закономерностей в многомерных числовых последовательностях // Известия вузов. Проблемы полиграфии и издательского дела. — 200В. — №5. — С.29-41.

В других изданиях.

2. Козлов О. В. Выявление симметрий реконструированных фазовых траекторий динамических систем // Вестник МГУП. — 2008.— № 10.— С.46-56.

3. Козлов О. В. Методика определения симметрий фазовых траекторий динамических систем // Вестник МГУП. — 2007.— № 3.— С.40-46.

4. Козлов О. В. Выявление симметрий реконструированных фазовых траекторий динамических систем // Труды Всероссийской научной конференции «Проектирование научных и инженерных приложений в среде МАТЬАВ». — СПб.: Изд-во С.ПбГУ, 2007. — С. 698-705.

5. Козлов О. В. Алгоритмы двухмерного поиска и прохождения пути для совокупностей перемещающихся объектов в системах реального времени // Задачи системного анализа, управления и обработки информации: Межвузовский сборник трудов. Вып. 1.— М.: МГУП, 2006.— С. 104-111.

Патенты, свидетельства на программы для ЭВМ.

6. Козлов О. В., Никульчев Е. В. Методика выявления симметрий в трёхмерном контуре - свидетельство об официальной регистрации программы для ЭВМ № 200814048 // Федеральная служба по интеллектуальной собственности, патентам и товарным знакам. — 21.10.2008.

Отпечатано в типографии ИП Скороходов В.А. Зак. № 6654 Подписано в печать 31.10.2008

Тираж 100 экз. Усл. п.л. 1,25

ВВЕДЕНИЕ.

ГЛАВА 1. ОБЗОР МЕТОДОВ МОДЕЛИРОВАНИЯ НЕЛИНЕЙНЫХ СИСТЕМ.

1.1. Анализ развития нелинейной динамики.

1.2. Аффинные динамический модели нелинейных процессов.

1.5. Качественное исследование динамических систем.

1.4. Реконструкция аттракторов систем, допускающих группы симметрии.

1.5. Геометрический метод моделирования нелинейных систем по экспериментальным данным.

ГЛАВА 2. ОБЗОР МЕТОДОВ ВЫЯВЛЕНИЯ ПРЕОБРАЗОВАНИЙ СИММЕТРИИ В МНОГОМЕРНЫХ ЧИСЛОВЫХ ПОСЛЕДОВАТЕЛЬНОСТЯХ.

2.1. задача выявления преобразований симметрии в многомерных числовых последовательностях.

2.2. доказательство np-полноты задачи выявления преобразований симметрии

2.3. Задача нормализации фрагмента многомерной последовательности.

2.3.1. «Неокогнитрон» К. Фукуишмы.

2.3.2. Метод нормализации с помощью ДПФ.

2.4. задача подбора лучшего решения.

2.4.1. Алгоритм имитации отжига.

2.4.2. Кластерный анализ.

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

2.5. Методика выделения симметричных фрагментов.

ГЛАВА 3. МЕТОДИКА - ПРЕДОБРАБОТКА ДАННЫХ.

3.1. Получение исходных данных.

3.2. Маркировка.

3.3. Извлечение фрагментов.

3.4. Нормализация.

3.5. Оценка нарушения симметрии.

Выводы.

ГЛАВА 4. МЕТОДИКА - ГЕНЕТИЧЕСКИЙ ПОДБОР РЕШЕНИЙ.

4.1. Генерация случайного решения задачи (хромосомы).

4.2. Скрещивание решений (кроссинговер).

4.3. Случайные изменения при скрещивании (мутации).

4.4. Критерии оценкци решений.

4.5. Итеративная процедура генетического отбора решений.

4.7. Применение методики.

4.7.1. Тестовая синусоидальная функция.

4.7.2. Система Ресслера с коэффициентами а=0,2 Ь=0,2 и с=2,6.

4.7.3. Данные статистики нагрузки веб-сервера.

Выводы.

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

В настоящее время существует большое количество работ в области исследования аттракторов динамических систем. Решению задачи построения дифференциальных уравнений по экспериментальным данным посвящены работы: Р. Брауна [66], В. С. Анищенко [6], О. JT. Аносова [9], Т. Е. Вадивасовой [7], А. Н. Павлова [8], Н. Б. Янсона [53] и Т. Сойера [94], Е. В. Никульчева [51] и др. Однако, в работах, основанных на геометрическом анализе фазовых траекторий, не предложены методы выявления схожих и симметричных участков. Разработка автоматического поиска преобразований симметрий делает указанные методы конструктивными для моделирования систем различной природы. Вместе с тем, рассмотрение отдельных участков многомерных числовых последовательностей с целью выявления преобразований симметрий является NP-полной задачей.

Одним из современных бионических принципов решения NP-полных задач является применение генетических алгоритмов (ГА) — адаптивных методов поиска, разновидности эволюционных вычислений, основанной на генетических процессах биологических организмов. Основные принципы ГА были сформулированы Д. X. Холландом [80], и описаны в работах: Д. И. Голдберга [77], В. В. Емельянова [31], JI. А. Гладкова [27], В. В. Курейчика [41], В. М. Курейчика [42] и др. Хотя модель эволюционного развития, применяемая в ГА, сильно упрощена, тем не менее, ГА являются мощным средством и могут применяться для широкого класса прикладных задач, включая те, которые трудно решить другими методами, особенно в области NP-полных задач оптимизации.

Всё вышесказанное делает разработку методики выявления симметрий в многомерных числовых последовательностях на основе использования эволюционных вычислений актуальной задачей.

Решение этой задачи позволит применить методику для других областей науки: для определения фрактальных структур в минералогии, исследования хаотических процессов при цифровой обработке сигналов, оценки симметрических явлений при исследовании медико-биологических систем, а также выявления преобразований симметрий в процессах различной физической природы.

Цель.

Разработка методики, направленной на выявление преобразований симметрий (поворот, сдвиг, растяжение/сжатие) и их числовых показателей в многомерных числовых последовательностях в условиях слабого нарушения симметрии.

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

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

2. Формализация задачи выявления симметрических закономерностей в многомерных числовых последовательностях.

3. Обоснованный выбор геометрических методов предобработки и генетических алгоритмов для решения сформулированной задачи.

4. Разработка методики, позволяющей в автоматическом режиме выявить симметрии поворота, сдвига и растяжения/сжатия (масштабирования) в многомерных числовых последовательностях, получить числовые показатели преобразований, а также оценить степень нарушения симметрии.

5. Разработка специфических модификаций генетического алгоритма для нахождения решения задачи.

6. Разработка алгоритмического обеспечения для выявления преобразований симметрий и его программная реализация.

7. Анализ результатов по автоматическому выявлению симметрий поворота, сдвига и растяжения/сжатия в многомерных числовых последовательностях.

Объект исследования.

Объектом исследования являются многомерные числовые последовательности, полученные как результат восстановления я-мерного аттрактора по экспериментальным данным.

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

Методами исследования являются геометрические методы анализа числовых последовательностей и поиск решений оптимизационных задач с помощью генетических алгоритмов.

Научная новизна исследования:

1. Разработана методика выявления преобразований симметрий в многомерных числовых последовательностях, основанная на научно обоснованном применении генетических алгоритмов.

2. Для контура, полученного путем соединения точек исходной многомерной числовой последовательности, разработана процедура его приведения в нормированную систему координат, инвариантную относительно преобразований сдвига, поворота, растяжения/сжатия.

3. Разработан генетический алгоритм поиска разбиения контура на множество непересекающихся фрагментов при условии максимизации их длины и минимизации нарушения симметрии.

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

Результаты диссертации использованы при выполнении НИР по гранту РФФИ, проект № 08-07-00433а «Построение динамических моделей управления распределением загрузки каналов связи в вычислительных сетях».

Разработано программное обеспечение «Методика выявления симметрий трёхмерных контуров», на которое получено свидетельство о регистрации программы для ЭВМ Роспатента, № 2008615062.

Реализация результатов работы.

Использованы для построения динамических моделей загрузки каналов связи в вычислительных сетях в ЗАО «Московский Центр Деловой Информации "БИНЕК"».

Апробация результатов работы.

Результаты работы докладывались и обсуждались на 4-х научных конференциях и семинарах:

1. Всероссийской научной конференции «Проектирование научных и инженерных приложений в среде MATLAB» (Санкт-Петербург, СПбГУ, 2007).

2. Семинаре молодых ученых «Задачи системного анализа, управления и обработки информации» (Москва, МГУПИ, 2006),

3. Научно-технической конференции молодых ученых МГУП (Москва, МГУП, 2008);

4. Научно-методическом семинаре кафедры прикладной математики и моделирования систем Московского государственного университета печати.

Результаты проведенных исследований подробно изложены в последующих четырёх главах.

В первой главе проводится обзор методов нелинейной динамики, включая методы реконструкции систем по экспериментальным данным. Рассмотрен алгоритм глобальной реконструкции уравнений динамической системы по ее одномерной реализации [74]. Проведен анализ геометрического метода моделирования нелинейных систем, допускающих группы симметрий, по экспериментальным данным [51], позволяющий на основании временного ряда идентифицировать параметры модели в форме Шильникова

Овсянникова. Сделан вывод, что в рассмотренном методе отсутствуют конструктивные предложения по поиску симметрий фазовых траекторий, что определяет необходимость разработки автоматической процедуры выявления преобразований симметрий.

Во второй главе сформулирована задача выявления преобразований симметрий (поворот, сдвиг, масштабирование) многомерной числовой последовательности, полученной в результате восстановления «-мерного аттрактора по экспериментальным данным, как задача выделения симметричных фрагментов. Доказана NP-полнота поставленной задачи путём сведения её к задаче о поиске клики (clique) графа, являющейся NP-полной. Рассмотрены известные алгоритмы решения поставленной задачи предобработки, а именно: «Неокогнитрон» К. Фукушимы [76], его модификации и метод предобработки двухмерных контуров с помощью дискретного преобразования Фурье, предложенный С. Осовским [52]. На основании проведенного анализа сделан вывод о необходимости разработки нового алгоритма получения дескрипторов фрагментов с учётом специфики поставленной задачи. Рассмотрены наиболее подходящие к рассматриваемому классу задач многокритериальной оптимизации алгоритмы, а именно: алгоритмы на основе моделирования отжига, методы кластеризации и генетические алгоритмы. На основании проведённого анализа в качестве метода решения обоснованно выбраны генетические алгоритмы.

Во третьей главе описывается первая часть методики, относящаяся к предобработке данных. Описан механизм выделения фрагментов исходного n-мерного контура, полученого путём восстановления аттрактора, заключающийся в определении на нём специальных точек - маркеров. Предложен механизм нормализации, целью которого является преобразование каждого выделенного фрагмента в дескриптор - образ, инвариантный относительно переноса, поворота и масштабирования исходного фрагмента, а также получение численных показателей этого преобразования. Приводится пошаговое описание алгоритма нормализации для общего случая фрагмента n-мерного контура. Предлагается механизм численной оценки нарушения симметрии двух произвольных фрагментов FA и Fb, основанный на свойствах преобразования Фурье.

В четвёртой главе приводится описание второго этапа методики выделения в исходной n-мерной числовой последовательности симметричных, заключающегося в разработке механизмов эволюционного выбора решений. Предлагается модификация алгоритма генетического поиска учитывающая специфику поставленной задачи. Приводится пошаговое описание алгоритма случайной генерации решения, предлагается механизм скрещивания решений позволяющих получать из двух родительских решений два валидных дочерних решения, предлагается механизм случайных модификаций при скрещивании решений (мутаций), не нарушающий валидность генерируемых дочерних решений. Проводится обзор и обосновывается выбор механизмов выбора решений для скрещивания и их отбора в следующее поколение. Описывается итеративная процедура генетического отобора.

В заключении приводятся основные выводы и результаты работы.

Выводы

Анализ результатов применения показал, что разработанная методика позволяет автоматически выявлять преобразования симметрий в произвольных числовых последовательностях и оценивать степень нарушения симметрии. В задачах, где необходимо выяснить подтверждение допущения системой группы симметрий требуется дополнительный анализ результатов — введение порогов степени нарушения симметрии и т.д.

Наиболее важные параметры процедуры выявления симметрий, это распределение величины Д в оценке схожести фрагментов (3.6) и ограничение длины рассматриваемых фрагментов исходной последовательности.

Область эффективного применения разработанной методики составляют фазовые портреты динамических систем, допускающих группы симметрий. Результаты могут быть использованы для выявления преобразований сдвига, поворота и масштабирования в процессах различной физической природы.

Заключение

Проведенное диссертационное исследование позволило получить следующие результаты:

1. Проведён обзор методов реконструкции аттракторов и динамических моделей по временным рядам.

2. Формализована задача выявления симметрических закономерностей в многомерных числовых последовательностях, доказана её NP-полнота.

3. Обоснован выбор геометрических методов предобработки и генетических алгоритмов для решения сформулированной задачи.

4. Разработана методика выявления преобразований симметрий в многомерных числовых последовательностях, позволяющая получить числовые показатели преобразований, а также оценить степень нарушения симметрии.

5. Для контура, полученного путем соединения точек исходной многомерной числовой последовательности, разработана процедура приведения в нормированную систему координат, инвариантную относительно преобразований сдвига, поворота, растяжения/сжатия.

6. Разработан генетический алгоритм поиска разбиения контура на множество непересекающихся фрагментов при условии максимизации их длины и минимизации нарушения симметрий.

7. Разработано и программно реализовано алгоритмическое обеспечение методики выявления преобразований симметрий. Получено свидетельство Роспатента о регистрации программы.

8. Результаты диссертации использованы при выполнении НИР по гранту РФФИ, проект № 08-07-00433а и для построения динамических моделей загрузки каналов связи в вычислительных сетях в ЗАО «Московский Центр Деловой Информации "БИНЕК"».

9. Проведен анализ результатов выявления преобразований симметрий в экспериментальных и модельных данных.

1. Аграчеев А. А., Сачков Ю. JI. Геометрическая теория управления.— М.: Физматлит, 2005.

2. Андронов А. А. Предельные циклы Пуанкаре и теория автоколебаний // Собрание трудов А. А. Андронова.— М.: Изд-во АН СССР, 1956.

3. Андронов А. А., Леонтович Е. А., Гордон И. И., Майер А. Г. Качественная теория динамических систем второго порядка.— М.: Наука, 1966.

4. Андронов А. А., Леонтович Е. А., Гордон И. И., Майер А. Г. Теория бифуркаций динамических систем на плоскости.— М: Наука, 1967.

5. Анищенко В. С. Знакомство с нелинейной динамикой: лекции соросовского профессора: учеб. пособие.— Саратов: Изд-во ГосУНЦ «Колледж», 2000.

6. Анищенко В. С., Астахов В. В., Вадивасова Т. Е. и др. Нелинейные эффекты в хаотических и стохастических системах / Под ред. В. С. Анищенко.— М.-Ижевск: Институт компьютерных исследований, 2003.

7. Анищенко В. С., Вадивасова Т. Е., Постнов Д. Э., Сафонова М. А. Внешняя и взаимная синхронизация хаоса // Радиотехника и электроника.— 1991.— Т. 36.— С. 338.

8. Анищенко В. С., Павлов А.Н., Янсон Н.Б. Реконструкция динамических систем в приложении к защите информации // ЖТФ.— 1998.— Т. 68.— № 12.

9. Аносов Д. В., Бронштейн И. У., Арансон С. X., Гринес В. 3. Гладкие динамические системы // Итоги науки и техн. Соврем, пробл. матем. Фунд. напр. 1: Динамические системы — 1. М.: ВИНИТИ, 1985. С. 151242.

10. Арнольд В. И., Козлов В. В., Нейштадт А. И. Современные проблемы математики. Фундаментальные направления. Т.З.— М.: ВНИТИ, 1985.

11. Арнольд В. И. Доказательство теоремы Колмогорова о сохранении условно-периодических движений при малом изменении функции Гамильтона // УМН.— 1963.— Т. 18.— Вып. 5 (113).— С. 130.

12. Арнольд В. И. Малые знаменатели и проблема устойчивости движения в классической и небесной механике // УМН.— 1963.— Т. 18.— Вып. 6(114).—С. 81-192.

13. Арнольд В. И. Математические методы классической механики.— М: Наука, 1989.

14. Ассарин Е. А., Козякин В. С., Красносельский М. А., Кузнецов Н. А. Анализ устойчивости рассинхронизированных дискретных систем.— М.: Наука, 1992.

15. Астахов В. В., Сильченко А. Н., Стрелкова Г. И., Шабунин А. В., Анищенко В. С. Управление и синхронизация хаоса в системе связанных генераторов // Радиотехника и электроника.— 1996.— Т. 41.— С. 1323.

16. Афраймович В. С. Внутренние бифуркации и кризисы аттракторов // В сб. Нелинейные волны / Под ред. А. В. Гапонова-Грехова и М. И. Рабиновича.— М.: Наука, 1987.— С. 189-213.

17. Афраймович В. С., Быков В. В., Шильников JI. П. О возникновении и структуре аттрактора Лоренца // ДАН СССР.— 1977.— Т. 234.— № 2.— С. 336-339.

18. Афраймович В. С., Гаврилов Н. К., Лукьянов В. И., Шильников Л. П. Основные бифуркации динамических систем.— Горький: Изд-во ГГУ (ННГУ), 1985.

19. Ахромеева Т. С., Курдюмов С. П., Малинецкий Г. Г., Самарский А. А. Нестационарные структуры и диффузионный хаос.— М.: Наука, 1992.

20. Береснев В. JL, Гимади Э. X., Дементьев В. Т. Экстремальные задачи стандартизации. Новосибирск: Наука, 1978.

21. Берже П., И. Поио, Видаль К. Порядок в хаосе. О детерминистском подходе к турбулентности: пер. с франц.— Череповец: Меркурий-ПРЕСС, 1998.

22. Беркс У. Пространство — время, геометрия, космология.— М.: Мир. 1985.

23. Биркгоф Дж. Д. Динамические системы.— М.—Ижевск: НИЦ «Регулярная и хаотическая динамика», 2002. (переизд. 1941).

24. Бланк М. JI. Устойчивость и локализация в хаотической динамике.— М.: МЦНМО, 2001.

25. Бутковский А. Г. Фазовые портреты управляемых динамических систем.— М.: Наука. 1985.

26. Гарев К. Г. Приложения непрерывных групп симметрий к дифференциальным уравнениям // Соросовский образовательный журнал.— 1998.—№ 12.—С. 113-118.

27. Гладков JI. А., Курейчик В. В., Курейчик В. М. Генетические алгоритмы / Под ред. В.М. Курейчика. 2-е изд., испр. и доп. - М.: ФИЗМАТЛИТ, 2006. - 320 с.

28. Гукенхеймер Дж. Странный, странный аттрактор // Кн. : Марсден Дж., Мак-Кракен М. Бифуркация рождения цикла и ее приложения. Гл. 12.— М.: Мир, 1980.—С. 284-293.

29. Гэри В., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.

30. Елкин В. И. Редукция нелинейных управляемых систем: дифференциально-геометрический подход.— М.: Наука, 1997.

31. Емельянов В.В. Теория и практика эволюционного моделирования / В.

32. B. Емельянов, В. В. Курейчик, В. М. Курейчик. — М. : ФИЗМАТЛИТ,2003. — 432 с.

33. Еремеев А.В. Разработка и анализ генетических и гибридных алгоритмов для решения задач дискретной оптимизации. Дисс. канд.физ.-мат.наук. Омск, 2000.

34. Жевакин С.А. Об отыскании предельных циклов в системах, близких к некоторым нелинейным // ПММ.— 1951.— Т. 15.— Вып. 2.— С. 237244.

35. Каток А. Б., Хассельблат Б. Введение в современную теорию динамических систем.— М.: Факториал УРСС, 1999.

36. Колмогоров А. Н. О сохранении условно-периодических движений при малом изменении функции Гамильтона // ДАН СССР.— 1954.— Т. 98.—1. C. 527-530.

37. Кондратьев Г. В. Геометрическая теория синтеза оптимальных стационарных гладких систем управления.— М.: Физматлит, 2003.

38. Костылев И. А., Малинецкий Г. Г., Потапов А. Б. Параметры порядка в нейронной сети Хопфилда // Журнал вычисл. математики и матем. физ.— 1994.— Т. 34.— С. 1733-1740.

39. Краснощеков В. И. Геометрические методы исследования систем управления // Теория и компьютерные методы исследования стохастических систем / Пупков К. А. и др. Приложение 3.— М.: Физматлит, 2003.— С. 350-399.

40. Крищенко А. П. Исследования управляемости и множества достижимости нелинейных систем управления // Автоматика и телемеханика.— 1984.— № 6.— С. 30-36.

41. Кузнецов С. П. Динамический хаос (курс лекций). Серия: современная теория колебаний и волн.— М.: Наука, 2001.

42. Курейчик В.В., Сороколетов П.В., Хабарова И.В. Динамические генетические алгоритмы в системах поддержки, принятия решений. Таганрог: Изд-во ТРТУ, 2006.

43. Курейчик В.М. Генетические алгоритмы. Таганрог: изд-во ТРТУ, 1998. - 242 с.

44. Лесин В.В., Лисовец Ю.П. Основы методов оптимизации. М.: МАИ,1998.

45. Лоренц Э. Н. Детерминированное непериодическое течение // В кн.: «Странные аттракторы».— М.: Мир. 1981.— С. 88-116.

46. Магницкий Н. А., Сидоров С. В. Новые методы хаотической динамики.—М.: Едикториал УРСС, 2004.

47. Магницкий Н. А., Сидоров С. В. О некоторых подходах к проблеме управления диффузионным хаосом // Дифференциальные уравнения.—1999.— Т. 35.—№ 5.— С. 664-669.

48. Малинецкий Г. Г. Математические основы синергетики. Хаос, структуры, вычислительный эксперимент. Изд. 4-е.— М.: КомКнига, 2005.

49. Малинецкий Г. Г. Потапов А. Б. Современные проблемы нелинейной динамики.— М.: Эдиториал УРСС. 2000.

50. Малинецкий Г. Г., Курдюмов С. П. Нелинейная динамика и проблемы прогноза //Доклады РАН.— 2001.— Т. 71.— № 3. с. 210-232

51. Музыкин С. Н., Родионова Ю. М. Моделирование систем.— М.: МГАПИ, 2004.

52. Никульчев Е.В. Геометрический подход к моделированию нелинейных систем по экспериментальным данным: Монография. — М.: МГУП, 2007.

53. Осовский С. Нейронные сети для обработки информации // М.: Финансы и статистика, 2002.

54. Павлов А. Н., Янсон Н. Б., Анищенко В. С. Реконструкция динамических систем // Радиотехника и электроника.— 1999.— Т. 44.— № 9.— С. 1075-1092.

55. Павловский Ю. Н., Яковенко Г. Н. Группы, допускаемые динамическими системами // Методы оптимизации и их приложения.— Новосибирск: Наука, 1982.— С.155-189.

56. Рейсинг Р, Сансоне Г., Конти Р. Качественная теория нелинейных дифференциальных уравнений.— М.: Наука, 1974.

57. Селезнев Е. П., Захаревич А. М. Динамика нелинейного осциллятора при квазипериодическом воздействии // Письма в ЖТФ.— 2005.— Т. 31.— Вып. 17.—С. 13-18

58. Смейл С. Дифференцируемые динамические системы // Успехи мат. наук.— 1970.—Т. 25.—№ 1.—С. 113-185

59. Смейл С. Математические проблемы следующего столетия // Кн.: Современные проблемы хаоса и нелинейности.— Ижевск: Изд-во Института компьютерных исследований, 2002.— С. 280-303.

60. Уоссермен Ф. Нейрокомпьютерная техника. Теория и практика. -М: Мир, 1992. -240 с.

61. Хенон М. Двумерное отображение со странным аттрактором // В сб. «Странные аттракторы».— М.: Мир, 1981.— С. 152-163.

62. Хрящев С. М. Оценки времени управления в системах с хаотическим поведением. Часть 1,2// Автоматика и телемеханика.— 2004.— №10, 11.

63. Чеботарев Н.Г. Теория групп Ли.— Л.: ГИТТЛ, 1940.

64. Шильников Л. П., Шильников А. Л., Тураев Д. В., Чуа Л. Методы качественной теории в нелинейной динамики.— М.-Ижевск: Институт компьютерных исследований, 2003.

65. Шильников Л. П. К вопросу о структуре расширенной окрестности грубого состояния равновесия типа седло-фокус // Матем. сборник.— 1970.— Т. 81(123).—№ 1.— С. 92-103.

66. Яковенко Г. Н. Регулярные математические модели систем с управлением: инвариантность, симметрии // Автореф. доктора физ.-мат. наук: 05.13.18.— М.: ВЦ РАН, 1995.

67. Aggarwal С. С., Orlin J. В., Tai R. P. Optimized crossover for maximum independent set. Oper. Res. v45 (1997), pp 225-234.

68. Balas E., Niehaus W. Finding large cliques in arbitrary graphs by bipartite matching. Cliques, coloring, and satisfiability. DIMACS Ser. Discrete Math. Theoret. Comput. Sci. v26 (1996), pp 29-49.

69. Boese K. D., Kahng А. В., Muddu S. A new adaptive multi-start technique for combinatorial global optimizations. Oper. Res. Lett. vl6 (1994), N2, pp 101-114.

70. Brawn R., Rulkov N. F., Tracy E. R. Modelling and synchronizing chaotic systems from time-series data // Pthys. Rev. E.— 1994.— V. 49.— P. 3784.

71. Breeden J. L., Hubler A. // Phys. Rev. A.— 1990.— V. 42.— N. 10.— P. 5817-5826.

72. Bremermann H. J., Roghson J., Salaff S. Global properties of evolution processes. Natural automata and useful simulations. London: Macmillan. 1966. pp 3-42.

73. Chua L. O., Komyro M., Matsumoto T. The double scroll family // IEEE Trans. Circuits Syst., CAS-33. —1986.— P. 1072.

74. Chua's Circuit: a Paradigm for Chaos ed. R.N.Madand. // World Sci. Ser. on Nonlinear Sci. Series B. — 1993.—V. 1.

75. Cremers X., Hubler A. // Z. Naturforschung A.— 1987.— V. 42.— P. 797802.

76. Crutchfield J.P., McNamara B.S. // Complex Systems.— 1987.— V. 1.— P 417-452.

77. Fukushima K. Neocognitron: a self-organising neural network for mechanism of pattern recognition unaffected by shift in position. Biological Cybernetics 36,1980, pp. 193-202.

78. Goldberg D. E. Genetic algorithms in search, optimization, and machine learning. Reading, MA: Addison-Wesley. 1989.

79. Gouesbet G., Letellier С. II Phys. Rev. E.— 1994.— V. 49.— P. 4955^972.

80. Hermann M. Mesure de Lebesgue et nombre de rotation // Proc. Symp. Geomerty and Topology; Lecture notes in Math.— Springer-Verlag: NY, 1971.— V. 597.— P. 371-395.

81. Holland J. H. Adaptation in natural and artificial systems. Ann Arbor: University of Michigan Press. 1975.

82. King G. P., Steward I. Phase space reconstruction for symmetric dynamical systems // Physica D: Nonlinear Phenomena.— 1992.— V. 58.— P. 216-228.

83. Kocarev L., Shang A., Chua L. O. Transitions in dynamical regimes by driving: A unified method of control and synchronization of chaos // Int. J. Bif. Chaos.— 1993.— V. 3.— P. 479.

84. Lorenz E. N. Deterministic Nonperiodic Flow // J. Atmos. Sci.— 1963.— V. 20.—P. 130-141

85. Nienhuis В., A. Van Ooyent. Pattern recognition in the neocognitron is improved by neural adaptation. Biological Cybernetics 70, 1993, pp. 47-53.

86. Ott E, Grebogi C, Yorke J. Controlling chaos // Physical Review Letters.— 1990.—V. 64.—N. 11.—P. 1195-1199.

87. Packard, N. H., Crutchfield, J. P., Farmer, J. D., Shaw, R. S. Geometry from a time series // Phys. Rev. Lett.— 1980.— V. 45.— P. 712-716.

88. Pecora L. M., Caroll Т. I., Jonnson G. A, Mar D. J., Heagy J. F. Fundamentals of synchronization in chaotic systems. Concepts and applications // Caos.— 1997.— V. 7.— N. 4.— P. 520-543.

89. Pecora, L. M., Carroll T. L. Synchronization in chaotic systems // Phys. Rev. Lett. — 1990— V. 64.— P. 821-824.

90. Peng J. H., Ding E. J., Ding M., Yang W. Synchronizing hiperchaos with a scalar transmitted signal // Ph. Rev. Lett.—1996.—V. 76.— № 6.— P. 904907.

91. Rechenberg I. Evolutionsstrategie: Optimierung technischer Systeme nach Prinzipien der Biologischen Information, Freiburg: Fromman, 1973.

92. Rosenstein M. Т., Collins J. J., DeLucaC. J. Reconstruction expansion as a geometry-based framework for choosing proper delay times // Physica D.— 1994.— V. 73.—P. 82-98.

93. Rul'kov N. F., Volkovskii A. R., Rodriguez-Lozano A., Del Rio E., Velarde M. G. Mutual synchronization of chaotic self — oscillators with dissipative coupling // Int. J. Bif. Chaos.— 1992.— V. 2.— P. 669.

94. Rychlik M. Lorenz attractors through a Shilnikov-type bufurcation, Part 1. Ergodic theory dynamical systems— 1989.— V. 10.— P. 793-821.

95. SauerT. Reconstruction of dynamical systems from interspike intervals 11 Phys. Rev. Lett.— 1994.— V. 72.— P. 3811-3814.

96. Schwefel H. P. Numerical optimization of computer models. Chichester: Wiley, 1981.

97. Shunji Satoh, Hirotomo Aso, Shogj Miayake Evaluation of two neocognitron-type models for recognition of rotated patterns. Pr c. IWANN'2000, 2, 2000, pp. 501-513.

98. Shunji Satoh, Hirotomo Aso, Shogj Miayake,Jousuke Kuroiwa (1999) Pattern Recognition system with Top-Down Process of Mental Rotation. Pr c. IWANN'99, 1, 1999, pp. 816-825.

99. Sparrow C. The Lorenz equations : Bifurcations, chaos and strange attractors.-N.-Y.: Springer Yerlag, 1982.

100. Takens F. Detecting strange attractors in turbulence // Dynamical Syst. and Turbulence / Eds.: Rand D.A., Young L.-S.— Berlin: Springer, 1981.— P. 366-381.

101. Takens F. Detecting nonlinearities in stationary time series // Int. J. of Bifurcation and Chaos.— 1993.— Y. 3.— P. 241-256.

102. Tanaka K., Jkeda Т., Wang H. O. A Unified Approach to Controlling Chaos via an LMIBased Fuzzy Control Systems Design // IEEE Trans. Circuits Syst. J.—1998.—V.45.—N. 10.—P. 1021-1040.

103. Tryon R.C. Cluster Analysis. New York: McGraw-Hill. 1939

104. Williams R. F. The structure of the Lorenz attractors // Publ. Math. IHES.— 1979. v. 50.— P. 321-347

105. Wolf, A., J.B.Swift, L. Swinney, J.A. Vastano, Determining Lyapunov exponents from a time series // Physica D.— 1985.— V. 16.— P. 285-317.

106. Yorke J. A., Yorke E. D. Metastable chaos : the transition to sustained chaotic oscillations in a model of Lorenz // J. Stat. Phys.—1979.—V. 21.— P. 263267.

107. Козлов О. В. Методика эволюционного выявления симметрических закономерностей в многомерных числовых последовательностях //

108. Известия вузов. Проблемы полиграфии и издательского дела. — 2008. — №5. — С.29-41.

109. Козлов О. В. Выявление симметрий реконструированных фазовых траекторий динамических систем // Вестник МГУП. — 2008.— № 10.— С.46-56.

110. Козлов О. В. Методика определения симметрий фазовых траекторий динамических систем // Вестник МГУП. — 2007.— № 3.— С.40-46.

111. Козлов О. В. Выявление симметрий реконструированных фазовых траекторий динамических систем // Труды Всероссийской научной конференции «Проектирование научных и инженерных приложений в среде MATLAB». — СПб.: Изд-во С.ПбГУ, 2007. — С. 698-705.