Содержание
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%.