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

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

ЧИРИКОВ Роман Юрьевич

ОПТИМИЗАЦИЯ РАЗМЕЩЕНИЯ СЛОЖНЫХ

ОБЪЕКТОВ В ФОРМЕ ПОЛИМИНО НА ОСНОВЕ ГЕНЕТИЧЕСКОГО АЛГОРИТМА

(НА ПРИМЕРЕ ПРОЕКТИРОВАНИЯ АНТЕННЫХ РЕШЕТОК)

Специальность:

13.01 — Системный анализ, управление и обработка информации (в промышленности)

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Уфа - 2014

1 5 И/.П 2014

005547765

Работа выполнена в ФГБОУ ВПО «Уфимский государственный авиационный технический университет» на кафедре телекоммуникационных систем

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

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

д-р техн. наук, профессор Батанов Валерий Хусаинович

д-р техн. наук, старший науч. сотрудник Коровин Валерий Михайлович

ОАО «Башнефтегеофизика», главный геофизик

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

канд. техн. наук

Телицкий Станислав Владиславович

ООО «ГрузАвто», зам. директора по коммерческой деятельности

ФГБОУ ВПО «Башкирский государственный педагогический университет им. М. Акмуллы»

Защита состоится 6 июня 2014 г. в 10 часов на заседании диссертационного совета Д 212.288.03 на базе ФГБОУ ВПО «Уфимский государственный авиационный технический университет» по адресу: 450000, г. Уфа, ул. К. Маркса, 12.

С диссертацией можно ознакомиться в библиотеке ФГБОУ ВПО «Уфимский государственный авиационный технический университет» и на сайте http: //www. ugatu. ас. ги/.

Автореферат разослан 1 апреля 2014 г.

Ученый секретарь диссертационного совета, д-р техн. наук, проф.

В. В. Миронов

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

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

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

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

Степень разработанности темы. Проблема оптимальной упаковки двумерных объектов представлена большим объемом научных исследований. В качестве наиболее известных можно назвать отечественных ученых В. А. За-лгаллера, Л. В. Канторовича, В. М. Картака, Э. А. Мухачеву, И. П. Норенкова, И. В. Романовского, В. Д. Фроловского, а также зарубежных ученых А. Вог1бг1ск, Н. ВукЬоЯ; в. ЗсИейшиег.

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

бежных ученых, как В. В. Денисенко, Ф. И. Емельчеиков, Ю. В. Кривошеев, С. П. Скобелев, А. А. Толкачев, А. В. Шишлов, С. А. Щелкунов, S. Gambadoro, R. Haupt, T. Isemia, A. Morabito, R. J. Mailloux, A. Massa, V. Pierro, S. Santarelli, R. Tang и других.

Объектом исследования является проблема оптимизации размещения сложных объектов, связанная с синтезом прямоугольных структур, составленных из полимино.

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

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

Задачи исследования:

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

2. Разработать метод оптимизации размещения полимино на основе критерия оценки неупорядоченности структур из полимино.

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

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

5. Оценить эффективность предложенного алгоритма и полученных структур методом математического моделирования.

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

Результаты, выносимые на защиту:

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

2. Метод оптимизации размещения полимино, основанный на вычислении автокорреляционной функции развертки Гильберта и позволяющий оценивать степень неупорядоченности структур из полимино.

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

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

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

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

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

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

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

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

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

Апробация результатов. Основные результаты работы обсуждались на: ХП, ХП1 и XIV Международных научно-технических конференциях «Проблемы техники и технологии телекоммуникаций», Уфа, 2011, 2012 и 2013; XIII, XIV и XV Международных конференциях «Computer Science and Information Technologies», Гармиш-Партенкирхен, Германия, 2011, Гамбург, Германия, 2012

и Вена, Австрия, 2013; 7-й Всероссийской зимней школе-семинаре аспирантов и молодых ученых «Актуальные проблемы науки и техники», Уфа, 2012; Международной конференции «ШЕЕ International Symposium On Antennas And Propagation», Чикаго, США, 2012; 19-м национальном совещании по электромагнетике RiNEM, Рим, Италия, 2012; 7-й Европейской конфереции «Antennas And Propagation», Гетеборг, Швеция, 2013.

Публикации. Результаты диссертационной работы отражены в 15 публикациях, в том числе в 3 статьях в рецензируемых журналах, рекомендованных ВАК, и в 10 публикациях в сборниках материалов международных и всероссийских конференций. Также по результатам работы получено 2 свидетельства о государственной регистрации программ для ЭВМ.

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

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

Во введении обоснована актуальность работы, сформулированы цель и основные задачи исследования, показаны научная новизна и практическая ценность работы, изложены основные положения, выносимые на защиту.

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

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

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

Среди эмпирических методов выбор сделан в пользу генетического алгоритма (ГА) по следующим причинам:

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

2. Дискретность природы задачи. Так как ФАР представляет собой регулярную решетку, и полимино располагаются в узлах этой решетки, имея строго обозначенные возможные ориентации, область поиска является дискретным пространством.

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

■Г т

о е ж

Рисунок 1 - Рассматриваемые формы полимино: тромино Ь-формы (а), тетромино Ь-формы (б), тетромино Б-формы (в), тетромино Т-формы (г), октомино С-формы (д), октомино Ь-формы (е), октомино РЬ-формы (ж)

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

По итогам главы сформулированы цели и задачи исследования.

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

Рассмотрим плоскую эквидистантную ФАР размером М х И, лежащую в плоскости х-у. Межэлементные расстояния в решетке йх и (1у. Решетка заполняется подрешетками, состоящими из д элементов. Максимальное число подреше-ток в структуре:

(1)

1

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

Линия задержки вынесена на уровень подрешеток. Физически она расположена под центральным элементом подрешетки (обозначены буквой «С» на рисунке 1).

Пустая структура представляется нулевой матрицей А. По мере заполнения структуры формами полимино, элементам матрицы, принадлежащим данному полимино, присваивается его порядковый номер, начиная с единицы. Каждая из ориентаций полимино может быть представлена в виде отдельной матрицы с двумя столбцами и числом строк, равным числу элементов в полимино без одного. Элементами матрицы являются координаты, определяющие расположение каждого элемента относительно заранее условленного центра полимино. Каждая строка такой матрицы определяет сдвиг каждого элемента полимино (кроме центра) относительно центра. При этом первый столбец определяет сдвиг по оси у, а второй по оси х. Например, октомино Ь-формы состоит из восьми элементов. Для описания его ориентаций необходимо составить восемь матриц размером 7x2. Ниже приведены первые четыре ориентации Ь-октомино в соответствии с рисунком 1.

-2 -Г -1 -п '-1 -Г -1 0 |

-1 -1 -1 0 -1 0 -1 1

0 -1 -1 1 -1 1 0 1

0 1 , г<» = -1 2 , Г® = 0 -1 Т-(З) = 1 -2

1 -1 0 -1 0 1 1 -1

1 0 1 -1 1 1 1 0

и и 11 12 1 и 1

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

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

( i-i

Y(xy) = JA«-+ S'W,, 0<xi<NA0<yi<M, (3)

[l, хг < О V xi > N V у! < О V ух > М,

V - V J. т®

Х{ — х + i . 2 ,

где (I — номер ориентации полимино, q — число элементов в полимино. При условии У = 0 размещение полимино в указанную позицию считается возможным, а сама позиция считается пригодной.

Таким образом имеется модель структуры (матрица решетки), модель полимино (матрицы ориентаций) и условие размещения полимино в структуре. Этот набор позволяет описывать и учитывать геометрические связи между элементами в системе. Кроме геометрических, необходимо учесть и электродинамические связи для расчета диаграммы направленности. Известно, что электрическое поле фазированной антенной решетки в дальней зоне £(0, ф) выражается через поле отдельного элемента:

Е{9, ф) = £i(G, ф) х AF(Q, ф), (4)

где 8 и ф — сферические координаты, Е\ — поле отдельного элемента, AF — системный множитель решетки. Для удобства вместо сферических координат используются координаты в пространстве синусов:

и = sin 9 cos ф, ,,,

V = sin 0 sin ф.

Системный множитель решетки записывается в виде:

N

AF(Q, ф) = J] 5AF¡(0' (6)

i=i

где N — количество подрешеток в решетке, / — частота, т — временная задержка, SAF — системный множитель подрешетки, который будет выражен в виде:

SAF(Q, ф) = £ (7)

i=i

где а — ток возбуждения элемента.

Структура решетки определяется набором из б или меньше подрешеток с заданными положением и ориентацией. Структура § является оптимальной при выполнении следующих условий:

/У • <8>

[ у ] -> пип,

где Я •— количество дырок в структуре, Ндоп — допустимое количество дырок, у — уровень боковых лепестков (УБЛ). В первом условии говорится, что оптимальная структура должна иметь минимальное количество незаполненных элементов. Это геометрическое условие. Однако оно связано с коэффициентом усиления: чем больше эффективная площадь ФАР, тем выше коэффициент усиления. Второе условие — электродинамическое — выражает требование минимизации. Если количество дырок в структуре поддается простому подсчету и имеет четкую область допустимых значений (от 0 до Мх АО, то УБЛ невозможно определить из структуры без численного моделирования, а ожидаемые значения приходится указывать приблизительно.

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

Как уже говорилось, УБЛ ФАР прямо пропорционален неупорядоченности структуры ФАР. Другими словами, чем меньше в структуре повторяющихся шаблонов, тем лучше подавление боковых лепестков. Исходя из этого было предложено вычислять интеграл автокорреляционной функции развертки структур. Для того, чтобы сохранить в развертке информацию о пространственном отношетии между полимино, применяется развертка Гильберта (рисунок 3).

Рисунок 3 - Первые шесть итераций развертки Гильберта

Автокорреляционная функция вычислялась от вектора £ составленного из ориентации полимино, которым принадлежат их центры. При этом незаполненные участки и остальные элементы полимино не учитываются, так как расположение центра полимино и его ориентация однозначно определяют положение остальных элементов. Была проведена серия экспериментов для выяснения зависимости УБЛ от вычисленного значения самоподобия. Из рисунка 4 видно, что полученное значение самоподобия для структур изменяется схоже с уровнем боковых лепестков по модулю. Данный результат позволяет применять полученную метрику в качестве критерия оценки качества структур при их проектировании.

О -5 -10 -15 -20 -25 -30 -35 -40

-

I -1

У- -

.г-'--""

50000 0

-50000 -100000 -150000

5

а §

л

и

ьз

1А

Э4 Т4

Тип полиомино

Ь8

Ри8

-200000

Самоподобие

УБЛ, = 1,3

Рисунок 4 - Сравнение значений самоподобия и уровня боковых лепестков

В третьей главе разрабатывается алгоритм оптимизации структур из полимино.

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

Первый подход заключался в применении алгоритма Гви—Лима (АГЛ). Данный алгоритм разработан на базе генетического алгоритма для размещения полимино-образных объектов внутри прямоугольной области. Он не допускает нахлеста фигур и выхода их за границы области. Также АГЛ использует круговой метод расстановки полимино — фигуры расставляются, начиная от углов, по направлению к центру.

Был проведен ряд экспериментов с АГЛ. Результаты показали корректное размещение полимино без нахлестов и пересечений границ, но оказалось, что алгоритм не позволяет получить структуру с малым количеством дырок в разумное время. Стоит отметить, что в структурах дырки были сконцентрированы преимущественно в центральной части. Это важно для антенных решеток, так как центральная область в большей степени отвечает за прием узконаправленных лучей.

Для устранения данного недостатка был разработан другой алгоритм, который расставляет полимино от центра к границе, за что и получил название алгоритма «Снежного кома» (АСК). Любая заполненная структура может быть представлена набором ориентаций полимино !> = {|д.ь \i2,..., fig}, которые затем размещаются по определенному правилу. На плоской прямоугольной сетке существуют четыре возможных ориентации полимино. Также, полимино могут быть перевернуты. Таким образом, асимметричное полимино может иметь N¡1 = 8 ориентаций. Симметричное полимино будет иметь четыре ориентации, повторяющиеся дважды. На кодирование N^ ориентаций выделяется Lg = log2 Nv_ = 3 бита; Алгоритм размещения полимино может быть описан в три шага. Соответствующая блок-схема представлена на рисунке 5, где АС — прирост целевой функции. Рассмотрим хромосому длиной L = Lg х Q 100, 001, Oil, 111, 010,____

Рисунок 5 - Блок-схема алгоритма «снежный ком»

Шаг 1 — извлечение генов. Хромосома есть конкатенация ориентаций в двоичной нотации. Хромосома разбивается на блоки по Ьг бит, которые затем переводятся в ориентации ц,. В результате получается вектор ориентаций по одной на каждое полимино ¡1 = (4, 1, 3, 7, 2, ...).

Шаг 2 — установка первого полимино. Центр первого полимино ставится в центр апертуры.

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

Центр решетки

V

\ ...

9 10\ 11 12 13

14 1 3 15

16 4 И 17

18 6 7 8 19

20 21 22 23 24

...

... ...

Граница ^ Поля

Рисунок 6 - Порядок поиска подходящих позиций

В соответствии с условиями была предложена целевая функция (ЦФ) ГА для вектора структуры включающая оба условия:

«ГГ

со,

+ Щ-^г-,

(9)

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

решетки и типа полимино, \|/а, — соответствующие весовые коэффициен-

ты. Значения весовых коэффициентов выбраны в соответствии с рекомендациями Гви и Лима: \|га = 0,17, \)/ffl = 0,33, \|/й = 0,5.

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

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

Для оценки качества работы АСК и выявления его преимуществ по сравнению с АГЛ были реализованы оба алгоритма и протестированы на различных параметрах. Все результаты данной шавы, а именно структуры решеток, их степень заполненности, диаграммы направленности и уровни боковых лепестков получены с использованием разработанного программного обеспечения (ПО). В ПО реализована разработанная математическая модель, описывающая структуры фазированных антенных решеток, составленных из подрешеток в форме полимино, разработанный метод оптимизации размещения полимино в структуре на основе вычисления автокорреляционной функции, разработанный алгоритм «снежного кома», а также алгоритм Гви—Лима. В программе присутствует процедурный аппарат, моделирующий диаграмму направленности ФАР. На рисунке 7 представлена структура разработанного программного обеспечения. Стрелками обозначен обмен данными между блоками. ПО написано на языке С и имеет интерфейс командной строки.

Полученные решетки имеют размер M = N = 32 элемента с межэлементным расстоянием dx = dy = 0,5Х, с направлением сканирования и0 = v0 = 0,5 и оптимизированы для ширины полосы частот г = '/д = 1,3. Длина волны X относится к верхней частоте X - Параметры ГА для АГЛ: рс = 0,9, рт = 0,3, Рът = 0,01; для АСК: рс = 0,65, рт - 0,2, рЬт = 0,005. Эти параметры были получены в процессе калибровки. Для обоих алгоритмов размер популяции Р = 8 и число итераций К = 50.

В эксперименте использованы октомино L-формы (q = 8) (рисунок 1). Оптимизация производилась для полосы г - 1,3. Данные представлены в таблице 1. Оптимизация УБЛ не повлияла значительно на структуру от АГЛ (подавление на 1 дБ) но улучшила результат АСК на 5 дБ до уровня -25,29 дБ. Следует заметить, что все эксперименты доказывают, что АСК способен более эффективно заполнять апертуру, что косвенно увеличивает направленность решетки.

Затем АГЛ и АСК были сравнены с работой Р. Мэйллу. Были проведены симуляции для квадратных решеток разного размера в двух полосах частот. Использовались следующие параметры: размер решетки M = N = {32, 40, 48, 56, 64}, полоса оптимизации г = 1,3, полосы симуляции г = {1,3, 1,82). Параметры ГА те же, какие были получены в процессе калибровки.

Рисунок 8 показывает зависимость УБЛ от размеров решетки с оптимизацией под г - 1,3. Как можно видеть, решетки, полученные с помощью АСК

Рисунок 7 - Структура разработанного программного обеспечения Таблица 1. Сравнение алгоритмов Гви—Лима и «Снежный ком»

Параметр АГЛ АСК

Число полимино 105 146

Значение ЦФ 0,6 0,74

Заполненность решетки, % 82 97,8

УБЛ без оптимизации (г = 1,3), дБ -21,18 -20,33

УБЛ с оптимизацией (г = 1,3), дБ -22,25 -25,29

с оптимизацией УБЛ на г = 1,3 демонстрируют лучшее подавление боковых лепестков на 2-4 дБ в оптимизированной полосе частот по сравнению с Мэйллу.

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

АГЛ, г11т = 1,3 АСК, гпт = 1,3

45 50 55 I

Размер решетки

—■— Р. Мэйллу, г„т = 1,3

Рисунок 8 - УБЛ решеток, оптимизированных под г = 1,3 в сравнении с работой Р. Мэйллу

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

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

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

2. Разработан метод оптимизации, основанный на вычислении автокорреляционной функции, отличающийся применением рекурсивной развертки Гильберта и позволяющий осуществлять многокритериальную оптимизацию с учетом оценки неупорядоченности структур из полимино. Анализ метода показал, что оценка неупорядоченности структуры коррелирует с рассчитанным значени-

ем уровня боковых лепестков и позволяет применять его в процессе оптимизации фазированных антенных решеток.

3. Разработан алгоритм структурно-параметрического синтеза структур из полимино «Снежный ком», основанный на эволюционном принципе, отличающийся способом расстановки полимино в структуре, позволяющий повысить степень заполненности структур до уровня 98-100%. Параметры алгоритма были откалиброваны.

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

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ОПУБЛИКОВАНЫ В РАБОТАХ

В рецензируемых журналах из списка ВАК

1. Проектирование больших антенных решеток как задача оптимальной упаковки / Р. 10. Чириков // Инфокоммуникационпые технологии: периодич. на-уч.-техн. и информационно-аналитический журнал. ПГУТИ. 2013. Т. 12. № 3. С. 77-82.

2. Алгоритм проектирования фазированных антенных решеток для спутниковых систем связи / Р. Ю. Чириков, П. Рокка, В. X. Багманов, А. X. Султанов // Вестник УГАТУ: науч. журнал Уфимск. гос. авиац. ун-та. УГАТУ. 2013. Т. 17. № 4(57). С. 159-166.

3. Калибровка параметров генетического алгоритма для задач проектирования фазированных антенных решеток / Р. Ю. Чириков, П. Рокка, В. X. Багманов // Электротехнические и информационные комплексы и системы: науч. журнал Уфимск. гос. ун-та эконом, и сервиса. УГУЭС. 2013. Т. 9. № 3. С. 89-92.

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

4. Свидетельство о государственной регистрации программы для ЭВМ №2013619538. Программа проектирования фазировашюй антенной решетки / Чириков Р. Ю. Роспатент. М.: Зарег. в Реестре программ для ЭВМ 09.10.2013.

5. Свидетельство о государственной регистрации программы для ЭВМ №2014610187. Программа упаковки прямоугольных полигонов в прямоугольные области / Чириков Р. Ю. Роспатент. М.: Зарег. в Реестре программ для ЭВМ 09.01.2014.

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

6. Генетический алгоритм для проектирования фазированных антенных решеток / Р. Ю. Чириков, П. Рокка // Компьютерные науки и информационные технологии CSIT'2011. Уфа: УГАТУ, 2011. Т. 2. С. 32-34. (Статья на англ. яз.).

7. Эволюционные алгоритмы для составления ФАР из подрешеток / Р. Ю. Чириков, П. Рокка, В. X. Батманов, Г. И. Абдрахманова // Проблемы техники и технологии телекоммуникаций: XII Международная научно-техническая конференция. Казань: КГТУ, 2011. С. 263-264. (Статья на англ. яз.).

8. Разработка фрактальных антенн для СШП систем связи / Р. Ю. Чириков, Г. И. Абдрахманова, А. И. Абдрахманова // Актуальные проблемы науки и техники: Сборник трудов 7-й Всероссийской зимней школы-семинара аспирантов и молодых ученых. Уфа: УГАТУ, 2012. С. 153-156.

9. Размещение полимино-образных подрешеток с помощью генетического алгоритма / Р. Ю. Чириков, П. Рокка, Р. Дж. Мэйллу // ШЕЕ Int. Symp. on Antennas and Propagation. Чикаго: APS, 2012. C. 42-43. (Статья на англ. яз.).

10. Новинки в проектировании антенн в исследовательском центре ELEDIA / Э. Бекеле, Р. Ю. Чириков, М. Карлин и др. // Atti XIX Riunione Nazionale di Elettromagnetismo (XIX RiNEm). Рим: RiNEm, 2012. C. 297-300. (Статья на англ. яз.).

11. Имплементация алгоритма Гви—Лима / Р. Ю. Чириков, П. Рокка // Компьютерные науки и информационные технологии CSIT'2012. Уфа: УГАТУ, 2012. Т. 3. С. 163-166. (Статья на англ. яз.).

12. Оптимизация структуры ФАР с применением генетического алгоритма / Р. Ю. Чириков, П. Рокка, А. Масса // Проблемы техники и технологии телекоммуникаций: XIII Международная научно-техническая конференция. Уфа: УГАТУ, 2012. С. 190-192. (Статья на англ. яз.).

13. Инновационные стратегии размещения полимино в ФАР / Р. Ю. Чириков, П. Рокка, Р. Дж. Мэйллу и др. // ЕиСАР-2013. Гетеборг: EuCAP, 2013. С. 123-127. (Статья на англ. яз.).

14. Инновационный алгоритм для проектирования антенных решеток / Р. Ю. Чириков // Компьютерные науки и информационные технологии CSIT'2013. Уфа: УГАТУ, 2013. Т. 3. С. 87-90. (Статья на англ. яз.).

15. Применение функций Лагерра для моделирования формы импульсов в сверхширокополосных системах связи / Г. И. Абдрахманова, Р. Ю. Чириков, В. X. Батманов // Проблемы техники и технологии телекоммуникаций: XIV Международная научно-техническая конференция. Самара: ПГУТИ, 2013 С. 87-91.

Диссертант

ЧИРИКОВ Роман Юрьевич

ОПТИМИЗАЦИЯ РАЗМЕЩЕНИЯ СЛОЖНЫХ ОБЪЕКТОВ В ФОРМЕ ПОЛИМИНО НА ОСНОВЕ ГЕНЕТИЧЕСКОГО АЛГОРИТМА (НА ПРИМЕРЕ ПРОЕКТИРОВАНИЯ АНТЕННЫХ РЕШЕТОК)

Специальность 05.13.01— Системный анализ, управление и обработка информации (в промышленности)

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Подписано в печать 27.03.2014. Формат 60 х 84 1/16. Бумага офсетная. Печать плоская. Гарнитура Тайме. Усл. печ. л. 1,0. Усл. кр. — отт. 1,0. Уч. — изд. л. 0,9. Тираж 100 экз. Заказ № 217.

ФГБОУ ВПО Уфимский государственный авиационный технический университет Центр оперативной полиграфии 450000, Уфа-центр, ул. К. Маркса, 12

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Уфимский государственный авиационный технический университет»

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

0420145571 7 ЧИРИКОВ Роман Юрьевич

ОПТИМИЗАЦИЯ РАЗМЕЩЕНИЯ СЛОЖНЫХ ОБЪЕКТОВ В ФОРМЕ ПОЛИМИНО НА ОСНОВЕ ГЕНЕТИЧЕСКОГО АЛГОРИТМА

(НА ПРИМЕРЕ ПРОЕКТИРОВАНИЯ АНТЕННЫХ РЕШЕТОК)

Специальность 05.13.01 Системный анализ, управление и обработка информации (в промышленности)

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

Научный руководитель доктор технических наук, профессор Багманов В. X.

Уфа - 2014

Содержание

Введение...................................... 4

Глава 1. Анализ проблемы оптимизации размещения объектов в форме полимино ................................... 9

1.1. Актуальность задачи размещения сложных объектов........ 9

1.2. Анализ существующих методов и подходов к оптимизации пространственно распределенных структур...............20

1.3. Цели и задачи исследования......................27

Выводы по первой главе ...........................28

Глава 2. Разработка модели и методов оптимизации прямоугольных структур из полимино............................29

2.1. Разработка математической модели структур антенных решеток, составленных из подрешеток в форме полимино..........29

2.2. Разработка метода оптимизации на основе оценки неравномерности структур.............................37

2.3. Разработка метода оптимизации на основе оценки самоподобия структур.................................48

Выводы по второй главе ...........................58

Глава 3. Разработка алгоритма оптимизации на основе генетического алгоритма...................................59

3.1. Проблема применения генетического алгоритма ..........59

3.2. Разработка алгоритма «снежный ком» для оптимизации структур, составленных из полимино....................79

3.3. Сравнение алгоритма Гви—Лима и алгоритма «снежный ком» по степени заполненности структур...................96

3.4. Заполнение структур двумя типами полимино одновременно . . .102

3.5. Сравнение алгоритма Гви—Лима и алгоритма «снежный ком» по

степени заполненности структур с двумя формами полимино ... 113 Выводы по третьей главе...........................116

Глава 4. Применение алгоритмов оптимизации структур из полимино в проектировании антенных решеток...................118

4.1. Применение алгоритма Гви—Лима для оптимизации структур фазированных антенных решеток ....................119

4.2. Применение разработанного алгоритма «снежный ком» для оптимизации структур фазированных антенных решеток.......124

4.3. Сравнение алгоритма Гви—Лима и алгоритма «снежный ком» по уровню боковых лепестков ......................129

4.4. Применение разработанного алгоритма и метода оптимизации

для формирования двух лепестков в диаграмме направленности . 136 Выводы по четвертой главе..........................150

Заключение....................................151

Литература ....................................152

Приложение А. Документы, подтверждающие внедрение результатов работы.....................................164

Введение

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

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

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

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

Степень разработанности темы. Проблема оптимальной упаковки двумерных объектов представлена большим объемом научных исследований. В качестве наиболее известных можно назвать отечественных ученых В. А. За-лгаллера, J1. В. Канторовича, В. М. Картака, Э. А. Мухачеву, И. П. Норенкова, И. В. Романовского, В. Д. Фроловского, а также зарубежных ученых A. Bortfeldt, H. Dykhoff, G. Scheithauer.

Задача оптимального размещения подрешеток в фазированных антенных решетках решалась различными путями в работах таких отечественных и зарубежных ученых, как В. В. Денисенко, Ф. И. Емельченков, Ю. В. Кривошеев, С. П. Скобелев, А. А. Толкачев, А. В. Шишлов, С. А. Щелкунов, S. Gambadoro, R. Haupt, T. Isernia, A. Morabito, R. J. Mailloux, A. Massa, V. Pierro, S. Santarelli, R. Tang и других.

Объектом исследования является проблема оптимизации размещения сложных объектов, связанная с синтезом прямоугольных структур, составленных из полимино.

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

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

Задачи исследования:

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

2. Разработать метод оптимизации размещения полимино на основе критерия оценки неупорядоченности структур из полимино.

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

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

5. Оценить эффективность предложенного алгоритма и полученных структур методом математического моделирования.

Результаты, выносимые на защиту:

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

2. Метод оптимизации размещения полимино, основанный на вычислении автокорреляционной функции развертки Гильберта и позволяющий оценивать степень неупорядоченности структур из полимино.

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

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

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

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

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

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

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

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

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

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

Апробация результатов. Основные результаты работы обсуждались на: XII, XIII и XIV Международных научно-технических конференциях «Проблемы техники и технологии телекоммуникаций», Уфа, 2011, 2012 и 2013; XIII, XIV и XV Международных конференциях «Computer Science and Information Technologies», Гармиш-Партенкирхен, Германия, 2011, Гамбург, Германия, 2012 и Вена, Австрия, 2013; 7-й Всероссийской зимней школе-семинаре аспирантов и молодых ученых «Актуальные проблемы науки и техники», Уфа, 2012; Международной конференции «IEEE International Symposium On Antennas And Propagation», Чикаго, США, 2012; 19-м национальном совещании по электромагнетике RiNEM, Рим, Италия, 2012; 7-й Европейской конфереции «Antennas And Propagation», Гетеборг, Швеция, 2013.

Публикации. Результаты диссертационной работы отражены в 15 публикациях, в том числе в 3 статьях в рецензируемых журналах, рекомендованных ВАК, и в 10 публикациях в сборниках материалов международных и всероссийских конференций. Также по результатам работы получено 2 свидетельства о государственной регистрации программ для ЭВМ.

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

Глава 1

Анализ проблемы оптимизации размещения объектов в форме полимино

1.1. Актуальность задачи размещения сложных объектов

Задача оптимизации технологических процессов и решений всегда являлась неотъемлемой частью технической мысли. Оптимизация есть поиск оптимального решения. Оптимальное (от латинского орНтш — наилучшее) решение — такое решение, которое по тем или иным признакам предпочтительнее других [1].

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

- Оптимизация по времени означает, что процесс должен протекать максимально быстро [2]. Например, может потребоваться оптимизация самой медленной части конвейерной сборки продукта для повышения производительности всего процесса сборки.

- Оптимизация материалов преследует своей целью наиболее эффективное использование требуемых материалов. Примером может служить оптимизация формы пластмассового корпуса изделия с целью экономии расходуемой пластмассы [3].

- Оптимизация денежных затрат в отличие от оптимизации ресурсов предполагает минимизацию всех расходов, в том числе зарплату и стоимость оборудования [4, 5].

- Оптимизация качества ставит целью достижения максимального качества в процессе [6]. Примером является ручная чистка картофеля взамен машинной. Процесс становится дорогим и долгим, однако качество повышается.

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

Широким классом оптимизационных задач является оптимальное размещение набора объектов в ограниченном пространстве. Чаще всего таким пространством является область некой формы на плоскости, а объектами — геометрические формы, реальные объекты и даже абстрактные объекты, выраженные геометрическими формами [7]. Далее приводятся примеры таких задач. Все они отсносятся к категории ЫР-сложных.

Задача оптимальной упаковки. Эта задача является классической задачей в таких областях, как системный анализ, комбинаторика и линейная алгебра. Можно сформулировать эту задачу так: имеется контейнер заданной формы, в который требуется разместить максимальное число объектов также заданной формы. Объекты могут быть разной формы и размеров. Такая задача подробно изучалась в одномерном [8], двумерном [9-13], трехмерном [14, 15] и многомерном [16] вариантах. На рисунке 1.1 приведен пример решения такой задачи.

8 2 12 13

10

0 14 4 1 5

11

6

3

9 7

Рисунок 1.1- Пример решения задачи оптимальной упаковки

Задача оптимального раскроя. Отличием данной задачи является то, что имеется некоторое количество форм, на которые требуется раскроить лист материала. Суть задачи в сведении отходов материала к минимуму, то есть наиболее плотному расположению форм. Эта задача освещена в ряде известных работ [17-21].

Задача о рюкзаке. Данная задача отличается от предыдущих тем, что она по определению многокритериальна. Суть ее в следующем: имеется рюкзак ограниченного объема. Имеется набор объектов с заданными размерами и ценой. Требуется положить в рюкзак такой набор объектов, чтобы суммарная их стоимость была максимальной. Есть вариант такой задачи, где вместо ограничения на объем рюкзака есть ограничение на грузоподъемность, а объекты, в свою очередь, задаются не размерами, а массой.

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

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

Антенны могут быть самых разных типов, форм и размеров. Однако есть несколько характеристик, являющихся основными для них всех [22]:

- диаграмма направленности (ДН) — графическое представление зависимости коэффициента усиления антенны или коэффициента напра