Л.А Мироновский, К.Ю. Петрова

Санкт-Петербургский государственный университет аэрокосмического приборостроения

Можно выделить три подхода к отысканию оптимальных сигналов: а) прямой поиск; б) итерационный подход; в) генетический подход.

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

Рис. 1. Итерационный принцип получения оптимальных сигналов

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

Рассматриваемая задача относится к числу многоэкстремальных задач, не имеющих однозначного решения. Для того чтобы избежать недостатков детерминированных алгоритмов, был исследован генетический подход [2]. В его рамках были разработаны чисто генетический и гибридный алгоритмы. Программная реализация алгоритмов выполнена в системе Matlab 5.2 и Simulink. Такой выбор был обусловлен наличием в пакете мощных возможностей по моделированию динамических систем, а также наличием необходимых возможностей для программирования и отладки.

Рис. 2. Интерпретация хромосомы (а), одноточечного (б) и двухточечных (в, г) кроссоверов

Мутация интерпретировалась как сдвиг отдельной точки переключения (рис.1,а), либо всей функции сразу вправо или влево на случайное количество позиций.

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

При выборе параметров гибридного алгоритма требовалось решить следующие вопросы:

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

Выбор типа кроссовера (пункт 2) не оказал существенного влияния на работу алгоритма. Наиболее существенными для работы алгоритма оказались пункты 3 и 4.

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

1. Функции с одной точкой переключения в случайный момент времени;
1. Функции со случайным числом точек переключения в случайные моменты;
1. Сигнатуры синусоид со случайными фазами и частотами.

При выборе родителей (п.4) для размножения были опробованы следующие стратегии:

1. Выбор для скрещивания случайных особей;
1. Выбор для скрещивания элитных особей;
1. Скрещивание некоторого количества элитных особей с некоторым количеством случайных.

Наихудшим по эффективности оказался второй вариант, а наилучшим– третий.

В алгоритме отсева (п. 5) использовались три различные процедуры:

1. Отсев худших особей;
1. Отсев произвольных особей помимо пяти лучших;
1. Отсев очень похожих особей: при этом оставляется особь с наилучшим значением критерия.

На каждой итерации отсеивалось от 5 до 15% популяции, либо поддерживалась постоянная популяция.

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

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

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

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

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

Рис.3. Сравнение результатов итерационного и гибридного алгоритмов.

Сходимость гибридного алгоритма для первых десяти поколений и вычислительные затраты, измеряемые количеством операций lsim для той же задачи при Т = 100с. показаны в таблице.

Сходимость гибридного алгоритма

Таблица 1.

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