Применение генетического алгоритма для задачи оптимизации геометрической структуры протяженного антенного поля

На сегодняшний день для проведения радиолокационного отслеживания прилегающего к Земле космического пространства, прогнозирования траекторий космических объектов естественного и искусственного происхождения, которые могут быть опасны в случае столкновения с Землей и с эксплуатируемой в космосе техникой, используются радиоинтерферометры с малой базой [1]. Это достаточно компактные объекты, состоящие из некоторого количества антенных элементов, расположенных на заданной площади. Известны строения интерферометров, в которых антенны располагаются на площади 1 км2, – The Square Kilometre Array (SKA)1.

Ввиду отсутствия аналитического решения для определения геометрической структуры задача оптимизации решается путем перебора, но перебор всевозможных вариантов требует огромного количества времени и вычислительных возможностей, поэтому применяют ряд эмпирических методов для сокращения количества операций. Генетический алгоритм (далее – ГА) является одним из таких методов и позволяет найти лучшее решение, чем полностью случайная решетка, путем применения процессов живого мира (отбор, скрещивание, мутация) к исследуемой модели [2]. В данной работе модель – протяженное антенное поле с точечными всенаправленными источниками излучения. Протяженность поля позволяет не учитывать взаимное влияние антенных элементов на диаграмму направленности (далее – ДН).

Постановка задачи

Задана площадь для антенного поля, представляющая собой прямоугольник с шириной a и длиной b. При этом площадь достаточно мала, что можно использовать модель плоской Земли. Также задана частота f , на которой необходимо определить уровень боковых лепестков (далее – УБЛ). Требуется определить количество элементов n и их расположение для достижения минимального УБЛ, при этом минимальное расстояние между любыми двумя антеннами должно составлять не менее R .

Предлагаемое решение

Определение максимального количества антенных элементов N , которые можно расставить на заданной площади так, чтобы минимальное расстояние между любыми двумя было не менее R , является задачей об упаковке окружностей в прямоугольнике. Наиболее плотная упаковка для окружностей одного размера на плоскости – упаковка по шестиугольной сетке [3].

Вестник Российского нового университета

Серия «Сложные системы: модели, анализ и управление», выпуск 2 за 2025 год

Количество элементов в решетке n берется как 0,8 от максимально возможного числа антенн, которые можно разместить на заданной площади.

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

Для оптимизации геометрической структуры антенного поля используется ГА. Для вычисления диаграммы направленности и определения УБЛ используется быстрое преобразование Фурье (далее – БПФ).

Механизм работы ГА

Генетический алгоритм представляет собой модель процессов, протекающих в живой природе: естественный отбор, скрещивание, мутации. Также ГА оперирует моделями объектов реального мира: популяции, особи, поколения (эпохи) [4].

Под особью понимается одна геометрическая структура антенного поля, то есть заполненная n элементами площадь. Популяция представляет собой набор из M особей. Поколение (эпоха) – номер итерации ГА.

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

Pik = p.0 + (0i - P,0 )(1 - e"ak) , где i = 1, 2, 3 – номер варианта алгоритма; pik – вероятность применения алгоритма на k-й эпохе; pi0 - начальная вероятность применения алгоритма; 0i - бинарный параметр: значение 1 обеспечивает повышение вероятности, 0 - понижение; a - коэффициент скорости переключения алгоритмов отбора.

Отбор усечением – выбор доли T лучших особей (по критерию минимального уровня УБЛ). В данной работе доля порядка 40 %, в общем случае – это заданный параметр.

Элитарный отбор – выбор доли µ ×T лучших особей, остальная часть ( T (1 – µ)) формируется случайным образом.

Отбор вытеснением – выбор особи-чемпиона – особи с лучшим показателем УБЛ. Затем выбор кандидатов – особей, чей УБЛ не выше, чем γ ×L . Особи-кандидаты выбираются в новую популяцию с вероятностями, пропорциональными евклидовому расстоянию между кандидатом и чемпионом – сумме расстояний между антенными элементами кандидата и чемпиона.

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

Равновероятностный выбор – все особи-родители могут с равной вероятностью быть выбраны для скрещивания.

Показатель конфиденциальности в математических моделях оценки качества образовательного процесса

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

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

Скрещивание. Данный этап представляет собой формирование новой особи из генов родителей. Под геном понимаются координаты одного антенного элемента в решетке. При скрещивании участвует k родителей, доля генов каждого родителя определяется случайно.

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

Блок-схема генетического алгоритма изображена на Рисунке 1.

Рисунок 1. Блок-схема ГА

Источник : здесь и далее рисунки выполнены авторами.

Вычисление ДН и нахождение УБЛ

Диаграмма направленности решеток, состоящих из точечных изотропных излучателей, рассчитывается по формуле

Вестник Российского нового университета

Серия «Сложные системы: модели, анализ и управление», выпуск 2 за 2025 год

N i ²ⁿ-[_ x n sm ( 0 ) ^cos (_v) + У п sm ( 0 ) sin (_V) ]

F (0, Ф) = Х e

где X - длина волны; N - общее число элементов решетки; ( x_n , у_п ) - координаты n -го элемента решетки; φ – азимут; θ – угол места [5].

Однако для определения УБЛ необходимо обеспечить шаг сетки, равный 1/10…1/5 ширины луча, чтобы не потерять локальные максимумы при моделировании. Это требует много времени для определения УБЛ решетки, поэтому был применен алгоритм быстро- го преобразования Фурье.

Для корректной работы БПФ необходимо применить следующие шаги:

• 1)    заданную площадь разбить сеткой с шагом, равным длине волны (частоте), на которой требуется определение УБЛ;

• 2)    все антенные элементы выравниваются по этой сетке.

• 3)    формируется матрица АФР для ввода в БПФ: в узлах, в которых есть антенные эле-

• менты, записывается значение 1, в остальных – 0.

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

Анализ полученных результатов

В ходе работы по созданию ГА для оптимизации геометрической структуры поля для минимизации УБЛ были исследованы следующие зависимости УБЛ:

• •    от количества элементов в решетке (см. Рисунок 2);

• •    количества эпох ГА;

• •    количества особей в популяции ГА.

Все зависимости исследовались на площади 1 км2, представляющей собой квадрат со стороной 1 км. Также зависимости (1)–(3) исследовались для межэлементного расстояния 60 м.

С увеличением числа антенных элементов УБЛ падает, что соответствует ожиданиям, поскольку из-за увеличения числа антенн создается более сложное распределение энергии – на большей площади возникает наложение волн в разной фазе, из-за чего УБЛ падает. Наиболее заметное уменьшение УБЛ происходит на интервале от 10 до 120 элементов, далее скорость изменения УБЛ снижается.

Результаты ГА улучшаются с увеличением числа эпох (см. Таблицу); это наблюдается до 35-й эпохи, далее значительного улучшения показателей не наблюдается.

Таблица

Зависимость УБЛ от количества эпох ГА

Количество эпох ГА	УБЛ, дБ
10	–11,6
15	–11,9
20	–12,1
25	–12,3
30	–12,5
35	–12,6
40	–12,6

Показатель конфиденциальности в математических моделях оценки качества образовательного процесса

Рисунок 2. Зависимость УБЛ от количества элементов в антенной решетке

Увеличение числа особей в популяции с 100 до 200 никак не повлияло на уровень УБЛ.

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

УБЛ случайной антенной решетки, состоящей из 250 антенных элементов, в среднем составляет –10,8 дБ. Средний УБЛ решетки после работы ГА составил –12,6 дБ. Таким образом, УБЛ улучшился на 16 %.

Заключение

Наибольшее влияние на УБЛ имеет количество элементов в антенном поле – с увеличением числа антенн УБЛ уменьшается; однако есть необходимость в определении оптимального количества элементов ввиду того, что при слишком большом числе получится эквидистантная решетка, УБЛ которой 0.

Результаты ГА улучшаются с увеличение числа эпох; это наблюдается до 35-й эпохи, далее значительного улучшения показателей не наблюдается. При увеличении количества особей в популяции ГА не замечено изменения УБЛ.

Сравнив среднее значение УБЛ случайной решетки и решетки, полученной после работы ГА, можно сказать, что ГА позволяет улучшить УБЛ на 15 %.