Scientific journal
Modern problems of science and education
ISSN 2070-7428
"Перечень" ВАК
ИФ РИНЦ = 0,931

APPLICATION OF GLOBAL OPTIMIZATION TO SOLVE THE TASK OF RADIOLOCATION, BASED ON APPLICATION OF THE THEORY OF OPTIMAL RECEPTION

Strokov V.I. 1
1 Baltic federal university. Kant
В работе предложен новый алгоритм глобальной оптимизации, адаптированный под решение задачи локации, основанной на применении теории оптимального приема. Как известно из теории, времена прихода сигналов локации входят в функционал правдоподобия в таком виде, что получение явных выражений для их определения затруднительно. Отсюда естественным способом определения искомых параметров является поиск минимума функционала правдоподобия и вместе с тем искомых значений параметров, соответствующих этому минимуму, численно. Однако большая вычислительная сложность расчета значения функционала затрудняет прямой перебор его значений в узлах n-мерной сетки с N узлами на ребро, поэтому весьма естественным шагом является применение методов глобальной оптимизации. Построению именно такого алгоритма и посвящена данная статья.
In this paper, we propose a new global optimization algorithm, adapted to the solution of the problem of location. As is known from the theory, the arrival times of signals are included in the functional of the maximum likelihood in such a way that to obtain explicit expressions for their determination difficult. Hence, a natural way to determine the unknown parameters is to find the minimum of the functional and at the same time the required values corresponding to minimum. However, the high computational complexity makes it difficult to calculate the values of the functional, so the use of global optimization methods is a natural step. The construction of such an algorithm is the subject of this article.
theory of optimum detection
global optimization

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

, (1)

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

Тогда функционал правдоподобия, соответствующий данной системе, имеет вид:

, (2)

где , - корреляционная матрица и вектор корреляций соответственно.

Данный функционал зависит только от времён , определить которые можно, найдя его минимум.

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

Пример.

Пусть имеется отраженный от ионосферы сигнал длительности 6.018 мс на несущей частоте 465 кГц. Интервал дискретизации сигнала составляет 0.2 мкс. Пусть ожидаемые времена прихода отраженных сигналов лежат в интервале от 1.0 до 5.3 мс. Если взять шаг сетки, по которой будет осуществляться поиск минимума функционала равным 5 мкс, то количество узлов на ребро составит , и число вычислений превысит .

Пусть машинное время вычисления одного значения функционала составляет примерно 6 мкс, тогда суммарное время для нахождения решения составит примерно 38 суток.

Важно отметить, что для обработки типовой ионограммы, построенной с шагом по частоте, равным 10 кГц, в интервале частот от 1 до 9 Мгц, необходимо обработать 800 файлов с записями отраженных сигналов, поэтому задачу минимизации нужно производить 800 раз. Отсюда следует огромное число лет, необходимое для решения задачи построения высотно-частотной характеристики – 83 года.

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

Для наглядности перейдем от четырехмерной задачи к двумерной и рассмотрим реализацию, изображенную на рисунке 1 и имитирующую отражённый от ионосферы сигнал. Сигнал имеет следующие параметры: времена прихода первой и второй отраженной М-последовательностей соответственно равны 1.6 и 1.8 мс. Амплитуды сигналов одинаковы и равны 1.0 В, СКО гауссова шума равно 0.25 В.

Рис. 1. Модельный сигнал (темно-серый) и его корреляционная функция (светло-серый).

Для данного сигнала построим функционал правдоподобия с шагом 5 мкс. Его внешний вид изображен на рисунке 2.

Рис. 2. Функционал правдоподобия.

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

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

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

Применение таких популярных алгоритмов, как DIRECT [1; 2], ISRES [4; 5], CRS [3; 6; 7], показало их недостаточную эффективность при решении указанной задачи, поэтому автором предложен алгоритм CRSM_LGM (контролируемый случайный поиск с локальными и глобальными мутациями).

Данный алгоритм является модификацией алгоритма CRS, предложенного W.L. Price [6; 7]. Базовый алгоритм CRS находит нового потенциального индивида в популяции на основании случайной комбинации нескольких индивидуумов, уже принадлежащих популяции. В случае если данный потенциальный индивид лучше самого худшего индивидуума в популяции, то он заменяет его.

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

Работа всегда ведется с наихудшим индивидом в популяции или с новым индивидом, заменившим его в процессе работы базового CRS-шага.

Процедуры локальной и глобальной мутации принципиально не отличаются друг от друга, различия в них лишь в степени вносимого в координаты индивида «шума». Шум определен как аддитивный гауссовский со средним значением, равным нулю, и неким СКО, определенным пользователем. Стандартно СКО для локальной мутации – 25 минимальных шагов алгоритма, а для глобальной мутации четверть области определения одной из переменных.

После осуществления стандартного CRS-шага мы производим операцию глобальной мутации, причем делаем ее покоординатно, а именно «шатаем» значения одной из координат индивидуума и смотрим на значение его пригодности. Если она улучшилась, то заменяем старого индивида на нового. Так же поступаем для всех остальных координат.

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

Итак, шаг алгоритма CRSM_LGM представляет собой следующее.

  1. Базовый CRS-шаг.
  2. Глобальная покоординатная мутация индивида, полученного на предыдущем шаге (или наихудшего индивида в популяции в случае неудачного CRS-шага).
  3. Локальная покоординатная мутация индивида, полученного на предыдущем шаге.

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

Рис. 3. Итерационный ход алгоритма CRSM_LGM.

Блок-схема алгоритма приведена на рисунке 4.

Рис. 4. Блок-схема алгоритма CRSM_LGM.


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

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

Пример. Вернемся к примеру, приведенному в начале главы, и оценим время обработки одной сигнальной записи в случае использования описанного алгоритма. Используя то же предположение, что машинное время вычисления одного значения функционала составляет примерно 6 мкс, получим оценочное время, требуемое для завершения расчета: . Это время, по сравнению с перебором по сетке, сократилось в 20 млн раз. Отсюда время расчета типовой ионограммы, без учета издержек на другие операции, составит 2 мин 12 секунд.

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

Рецензенты:

Пахотин В.А., д.ф.-м.н., профессор, БФУ им. И. Канта, г. Калининград;

Никитин М.А., д.ф.-м.н., профессор, БФУ им. И. Канта, г. Калининград.