Содержание
I. Введение
II. Двоичный/непрерывный ГА
III. Фазо-неравномерная линейная решетка с низким УБЛ
IV. Микрополосковая антенна с круговой поляризацией
V. Прореженные подрешетки
VI. Выводы
I. Введение
В некоторых случаяхоптимизационная задача имеет затратную функцию, оперирующую какдействительными, так и целочисленными переменными. Если переменные целые, тоиспользуются либо целочисленные алгоритмы программирования, либо двоичныегенетические алгоритмы (ГА). Двоичные ГА легко преобразуют биты, представляющиеконфигурации (хромосомы), в целые значения, не используя действительныхзначений. Но зачастую решения относительно уровня квантования переменных бываютсложными. Большинство оптимизационных алгоритмов рассчитаны на затратныефункции, оперирующие действительными переменными, в особенности те алгоритмы,которые используют производные. Одним из подходов к оптимизации функций,оперирующих как действительными, так и целыми переменными, являетсярассмотрение всех переменных как действительных с последующим округлениемзначений целых переменных. Если в решении оптимизационной задачи участвуют обавида переменных, она называется оптимизацией со смешанными целыми [1]. Самымраспространенным подходом здесь является метод ветвей и границ [2], хотяимеется и ряд других. Первоначально эти подходы были предназначены для решениялинейных задач программирования, но затем стали использоваться и длянелинейных. Они рассчитаны на малое число переменных и часто даютприблизительные результаты.
В последнее время дляоптимизации со смешанными целыми используются эволюционные методы и оптимизацияпо принципу роения элементов [4-7]. В этих подходах область затрат исследуетсяболее эффективно, можно оптимизировать большее число переменных, но в то жевремя необходимо каждый раз применять ГА, работающие с двоичными илинепрерывными переменными. Такие алгоритмы имеют раздельные операторы длядействительных и целых/двоичных переменных. В данной статье представлен ГА,который отличается от описанных ранее, поскольку его хромосомы имеют значениятолько в интервале от нуля до единицы. В нем использовано однородноескрещивание и имеется несколько направлений (выборов) мутации. Такой ГАуниверсален, т.к. один алгоритм можно использовать для любого типа переменной.Все масштабирование и картирование (преобразование) переменных имеет место взатратной функции.
Данный ГА применен красчету трех разных антенных конструкций. В первом случае максимальный уровеньбоковых лепестков (УБЛ) линейной решетки минимизируется за счет фазовойнеравномерности. Фазовые переменные имеют три формы: действительную, двоичную исмешанную. Представлена эффективность алгоритма при работе со всеми тремяформами. Во втором случае рассматривается расчет микрополосковой антенны скруговой поляризацией, имеющей в составе хромосомы двоичные и действительныепеременные. Наконец, выполняется оптимизация антенны с прореженнымиподрешетками, направленная на получение самого низкого из максимальных УБЛ.Преимуществом данного алгоритма является то, что оптимизацию можно проводить,имея значения переменных любого типа без необходимости изменения самогоалгоритма.
II. Двоичный/непрерывный ГА
ГА, описанный в даннойстатье, минимизирует затратные функции, которые при вычислении затрат оперируютдействительными и целыми переменными. Для повышения универсальности ГА всепеременные картируются (распределяются) по непрерывным значениям от 0 до 1.Термином непрерывный мы пользуемся вместо действительный,поскольку последний подразумевает значения в интервале ±∞, а первый внастоящей работе соответствует значениям от 0 до 1.
Матрица совокупностей npopxnvar для данного ГА представлена Уравнением1, где vm,n = переменной n в конфигурации(хромосоме) m при 0 ≤vm,n≤ 1. Каждый ряд соответствуетхромосоме; значения первоначально создают с помощью однородного произвольногогенератора чисел. Непрерывная переменная vm,n преобразуется либо в действительнуюпеременную xn, в целое In, либо в двоичное bn. Смотри Ур.2, где min иmax представляют границы переменной, xmin ≤ xn ≤ xmax;rounddown — функция, которая округляет доследующей меньшей целой; а round- функция, которая округляет до ближайшей целой. Как и в двоичном ГА, группадвоичных знаков образует ген (последовательность). Преимуществом данногоподхода является то, что все масштабирование, квантование и округлениепроисходит внутри затратной функции, так что ГА действует независимо от типа переменной.Поскольку операторы работают с любым сочетанием типов переменных, нетнеобходимости использовать двоичный ГА, действительный ГА и ГА со смешаннымицелыми. В хромосоме может быть любое сочетание действительных, целых и двоичныхпеременных.
Продолжительностьсуществования конфигурации (хромосомы) можно обеспечить с помощью ряда разныхспособов. В данном случае в фонде скрещивания сохраняются верхние 50% хромосом.Мы используем турнирный отбор при участии в одном турнире двух хромосом. Почтите же результаты дает выбор по правилам рулетки в сочетании с расстановкой порангам [9].
Теперь можно выполнитьскрещивание двух выбранных хромосом за счет одного из многих различных двоичныхскрещиваний или скрещиваний на основе действительного ГА [9]. Однородноескрещивание дает большие возможности исследования области затрат, чемдругие подходы к скрещиванию [9]; какраз оно и реализовано в этом алгоритме. Вначале создают произвольный двоичныйшаблон. Единица в его колонке означает, что результат (потомок) наделенпеременным значением в графе parent#1(родитель#1). Если там будет 0, то результат наделен переменным значением вграфе parent#2 (см. Ур.3). При таком подходе от каждой выбранной пары родителейсоздается только один потомок. Если значения являются двоичными, то такой типскрещивания дает разнообразие результатов, а если они целые или непрерывные, толишь обменивает значения у хромосом. Далее благодаря мутации в рамкахсовокупности непрерывных значений появляются новые значения. В таком алгоритметакже хорошо действует непрерывное скрещивание.
Один из подходов кмутации заключается в произвольном выборе переменных в совокупности и замене иходнородными произвольными значениями. Другим подходом является введениепроизвольного поправочного коэффициента. Такой коэффициент можно создать путемумножения каждого элемента хромосомы на произвольное число (-1 ≤ βrm ≤ 1) и далее умножением всейхромосомы на коэффициент мутации (0 ≤ αr ≤ 1). Смотри Ур.4, где rem — функция остатков (разряды слева отдесятичной точки опускаются). Такой вид мутации приводит к изменению всейхромосомы, а не отдельной переменной.
В попытке определитьподходящий размер совокупности и αr были проведены испытания алгоритмана двух затратных функциях. В обоих случаях ГА завершал работу после 400 оценокфункций и показывал самые благоприятные результаты. Первой тестовой функциейбыла (Ур.5), имеющая минимум нуля при xn = 0. Результатыусреднили по 100 прогонам при размере совокупности от 8 до 96 и частоте мутацииот 0,01 до 0,3. Наилучшие результаты были при размере совокупности 8 и частотемутации 0,1. Второй тестовой функцией была (Ур.6), имеющая минимум нуля при xn= 0. Результаты усреднили по 500 прогонам при размере совокупности от 8 до 96 ичастоте мутации от 0,005 до 0,3. Наилучшие результаты были при размересовокупности 40 и частоте мутации 0,01.
III. Фазо-неравномерная линейная решеткас низким УБЛ
Первым примером былрасчет линейной решетки, состоящей из 2nvar+1 равно удаленных изотропныхточечных источников, имеющих однородные амплитудные весовые коэффициенты. Дляданной фазовой неравномерности затратная функция дает максимальныйотносительный УБЛ множителя решетки, включающей 31 элемент при интервале 0,5λ.Фазовые весовые коэффициенты симметричны относительно центра решетки, причем центральныйэлемент имеет фазу, равную нулю. Затратная функция дает максимальный УБЛмножителя решетки (af)(см. Ур.7), где (см.) [cost — затраты].
Данная конструкция служитиспытательным стендом для проверки эффективности ГА в условиях, когдапеременные являются только либо двоичными, либо действительными, либосмешанными — при одинаковой затратной функции. Критерий эффективности былнаилучшим после оценки 2000 функций. Поскольку ГА относится к типупроизвольного поиска, отдельный прогон не является показателем ожидаемойэффективности. Следовательно, усреднение лучших результатов по 20 отдельнымпрогонам дает гораздо лучшую оценку эффективности ГА, чем отдельный прогон.Сравнение эффективности каждого алгоритма производили для сочетанийкоэффициента мутации (0,01 ≤ αr ≤ 0,15) и размера совокупности(8 ≤ npop ≤ 128). Использовалисьоднородное скрещивание и мутация, представленная в Ур.4.
Самые низкие максимальныеУБЛ, найденные в каждом из 20 отдельных прогонов, были усреднены для трехслучаях.
1) Действительные фазовыевесовые показатели: фазовые весовые показатели могут принимать любые значенияот нуля до 2π и при nvar = 15.
2) Двоичные фазовыевесовые показатели: 4-х битная точность при минимальном квантовании π/8. Вэтом случае nvar = 4 х 15= 60.
3) Смешанныедействительные и двоичные: восемь элементов с каждой стороны от центральногоимеют действительные фазовые значения, а семь элементов на каждой стороне имеют4-битные фазовые изменения.
Эффективность трех типовхромосом схожа с нескольких точек зрения. Во-первых, не очень удачным являетсясочетание очень маленького размера совокупности и очень маленькой частотымутации. Во-вторых, плохие результаты бывают при одновременном увеличении иразмера совокупности и частоты мутации. В-третьих, очень хорошая эффективностьдостигается при сочетании умеренного размера совокупности и частоты мутацииниже 10%.
Чтобы показать сходимостьхорошего прогона ГА, использовали значения npop = 40 и αr = 0,05. Из результатов прогоновкажется, что эти значения дают хорошие результаты для всех хромосом, содержащихлибо непрерывные, двоичные, либо смешанные значения. Число прогонов ГА длякаждого из типов хромосом составило 20. Оптимизация закончилась после 10000оценок функций. На Рис.2 представлены кривые наилучших прогонов для каждоготипа хромосом. Даже при том что размер совокупности для этих типов хромосомодинаков, тот факт, что двоичная хромосома имеет больше переменных (по одной накаждый двоичный разряд) дает более мутированные хромосомы (следовательно,больше оценок функций) в каждом поколении данной совокупности. Такой примерпоказывает, что ГА со смешанными целыми хорошо проявляет себя на фоне какдвоичного, так и непрерывного ГА.
Нахождение глобальногоминимума — задача более сложная. Часто гораздо лучшие результаты, чемкакой-либо отдельный алгоритм, дает гибридный алгоритм, совмещающий ГА слокальным оптимизатором.
IV. Микрополосковая антенна с круговойполяризацией
Целью второго примераявляется расчет прямоугольного излучателя для круговой поляризации при 10 ГГц.У затратной функции есть шесть входных переменных [v1v2v3v4v5v6]: (см.)
= положение облучателяэлемента (датчика)
= длина излучателя внаправлениях х и у
= толщина подложки
= относительнаядиэлектрическая постоянная подложки, где λ дано в мм. На
Затратная функция(реализованная с использованием FEKO[10]) дает максимум от трех рассчитанных членов (см. Ур.8), где Е =… =электрическое поле; s11 = коэффициент отражения.
Первые два члена в Ур.8при круговой поляризации равны нулю, поскольку компоненты электрического полятета и фита должны иметь одинаковую величину и несовпадение по фазе в 90градусов. Для идеального соответствия при 50Ω |s11| равно нулю. Когда излучатель имеет круговую поляризацию иидеальное соответствие, cost(затраты) = 0.
Результаты ГАсоответствовали результатам нисходящего симплексного алгоритма Нельдера-Мида втечение пяти отдельных прогонов (при новом произвольном выборе для каждогопрогона). Каждый прогон заканчивался после 400 оценок функций. ГА имел npop = 40, αr = 0,05 и использовал мутацию,представленную в Ур.4. Как показано в Таблице II, результаты ГА превосходят результаты алгоритмаНельдера-Мида. Тем не менее, его эффективность не является исключительной. Ещераз ГА протестировали при размере совокупности, равной 12, αr = 0,05, и частоте мутации,представленной в Ур.4. Сходимость, показанная на Рис.5, явно превосходитрезультаты предшествующих прогонов ГА.
В оптимальный расчет излучшей хромосомы можно включить следующие значения (см.). Полученный излучательимеет правостороннюю круговую поляризацию при коэффициенте эллиптичности 1,009и s11 = 0,012. Излучатель имееткоэффициент направленного действия, равный 6,97 дБ. Таким образом, с помощью ГАудалось создать очень хорошую микрополосковую конструкцию.
V. Прореженные подрешетки
генетический алгоритмхромосомы
Большие антенны сфазированными решетками строить весьма накладно. Если делить решетки наподрешетки, можно получить выигрыш в затратах на расчет, сооружение иобслуживание большой решетки. Если амплитудное и/или фазовое взвешиваниевыполнять не на уровне элемента, а на уровне подрешетки, можно добиться дифракционногомаксимума решетки.
Существует соотношениемежду УБЛ и простотой конструкции. Одно из упрощений заключается в сочетанииамплитудной неравномерности идентичных подрешеток с амплитуднойнеравномерностью, производимой на портах (вводах/выводах) подрешеток.Получаемая амплитудная неравномерность гораздо эффективней, чем выполняемаятолько на подрешетках. Поскольку все подрешетки идентичны, конструкция облучателя(схемы возбуждения) является очень простой. В линейных и плоских решетках ГАиспользуют для расчета оптимальной амплитудной неравномерности как у элементовподрешеток, так и на выходах подрешеток.
В представленном здесьподходе все подрешетки являются идентичными (половина зеркально отражает другуюполовину). Но вместо амплитудной неравномерности, производимой у элементовподрешетки, выполняется прореживание элементов. Прореживание — это, когдаэлемент имеет амплитудные весовые коэффициенты, равные нулю и единице. Вположении нуля элемент связан с согласованной нагрузкой, а в положении единицы- со схемой возбуждения. Порты подрешеток также имеют весовые коэффициенты,которые нормализованы между нулем и единицей.
В качестве примеравозьмем квадратную решетку точечных источников, разнесенных в направлениях xи y с интервалом в 0,5λ. Решетка из 900 элементовразделена на 36 подрешеток по 25 элементов в каждой. Цель заключается вминимизации максимального УБЛ путем сочетания оптимизации прореживания подрешетокс амплитудной неравномерностью, выполняемой на выводах подрешеток. Затратнаяфункция, учитывающая симметрию решетки, дана в Ур.9, где an- произведение весового коэффициентаэлемента и весового коэффициента подрешетки для элемента n; (xn, yn) — положение элемента n; а Ne — общее число элементов в одномквадранте решетки.
На Рис.6 показаноконечное оптимизированное прореживание решетки. Темная точка — это элемент,связанный с питающей схемой и имеющий амплитудный весовой коэффициентсоответствующей подрешетки. Белая точка — это элемент, связанный ссогласованной нагрузкой. Заметим, что подрешетки являются либо идентичными,либо зеркальными отображениями друг друга.
Затраты представляютсобой максимальный относительный УБЛ, вычисляемый согласно Ур.9. К примеру, врешетке 6 х 6 = 36 подрешеток, в каждой из которых 5 х 5 = 25 элементов.Интервал между элементами в обоих направлениях квадратной решетки составляетполовину длины волны.
С помощью ГА находимоптимальные весовые коэффициенты. Если веса подрешетки оптимизированы так, чтовсе элементы являются однородно взвешенными, максимальный УБЛ оказываетсяравным -18,4 дБ. Коэффициент направленного действия равен 28,3 дБ приэффективности неравномерности 75%. Такие результаты соответствуют результатампри однородном растворе антенны, имеющей коэффициент направленного действия29,5 дБ и максимальный УБЛ -13,2 дБ. Если веса подрешетки однородны, аподрешетка прорежена, то коэффициент направленного действия равен 27,3 дБ,максимальный УБЛ равен -15,3 дБ, а эффективность неравномерности — 60%.
Если одновременнооптимизировать и прореживание элементов и весовые коэффициенты подрешеток, тооптимизированные веса элементов имеют вид Рис.6, а оптимизированные весаподрешетки — Рис.7. Перемножение весов подрешетки и весов элементов даетполезные веса элементов, показанные на Рис.8 (для одного квадранта).Эффективность такой неравномерности — 54,5%. Получаемый множитель решетки имеетвид Рис.9. Коэффициент направленного действия равен 26,9 дБ, а максимальный УБЛравен -22,9 дБ. Снижение уровня боковых лепестков на 4,5 дБ по сравнению срезультатом от оптимизированного взвешивания подрешетки достигается за счетуменьшения эффективности неравномерности и снижения коэффициента направленногодействия.
VI. Выводы
При расчете некоторыхантенн встречаются переменные с целыми и действительными значениями. В статьепредлагается версия ГА, который работает со значениями в интервале от нуля доединицы и использует однородное скрещивание и непрерывную мутацию. Впредставленных трех примерах, ГА со смешанными целыми показал себя сположительной стороны. Основным преимуществом такого ГА является то, что онработает с любым сочетанием типов переменных. Все масштабирование икартирование переменных происходит в затратной функции. Масштабирование икартирование происходят при очень низких затратах на вычисление. К примеру, дляфазо-неравномерной решетки с низким УБЛ время вычисления составляет 1,227 х 10-4сек на функцию, тогда как обычная оценка функции занимает 7,8 х 10-3сек. Для такой простой затратной функции непроизводительные затраты составляюттолько около 1,5%. В общем времени вычисления для время-емких затратных функцийвремя на масштабирование и картирование составляет лишь малую долю. К примеру,в случае микрополосковой антенны оно равно 1,687 х 10-5 сек на вызовфункции, тогда как обычная оценка функции занимает 67,5 сек. Для такой болеевремя-емкой затратной функции непроизводительные затраты составляют толькооколо 2,5 х 10-5%. Данный алгоритм является альтернативой двоичномуГА, в котором приходится квантовать все переменные, и действительному ГА,который не работает с целыми и двоичными значениями. При решении задачиускорения сходимости алгоритма можно исследовать многие другие возможные схемыскрещивания и мутации.
VII.Список литературы
1.Устройства СВЧ и антенны. Методические указания к курсовому проектированию.Сост.: В.И. Елумеев, А.Д. Касаткин, В.Я. Рендакова. Рязань, 1998. №2693
2. А.Л.Драбкин, В.Л. Зузенко, А.Г. Кислов. Антенно-фидерные устройства. -М.: Советскоерадио, 1974.
3. Д.М. Сазонов. Антенны и устройстваСВЧ. Учебник для радиотехнических специальных вузов. — М.: Высшая школа,1988г.
4. М.С.Жук, Ю.Б.Молочков. Проектирование антенно-фидерных фидерныхустройств. М: Энергия, 1973