 |
II . Двоичный/непрерывный ГА
|
|
|
|
Содержание
I. Введение
II. Двоичный/непрерывный ГА
III. Фазо-неравномерная линейная решетка с низким УБЛ
IV. Микрополосковая антенна с круговой поляризацией
V. Прореженные подрешетки
VI. Выводы
I. Введение
В некоторых случаях оптимизационная задача имеет затратную функцию, оперирующую как действительными, так и целочисленными переменными. Если переменные целые, то используются либо целочисленные алгоритмы программирования, либо двоичные генетические алгоритмы (ГА). Двоичные ГА легко преобразуют биты, представляющие конфигурации (хромосомы), в целые значения, не используя действительных значений. Но зачастую решения относительно уровня квантования переменных бывают сложными. Большинство оптимизационных алгоритмов рассчитаны на затратные функции, оперирующие действительными переменными, в особенности те алгоритмы, которые используют производные. Одним из подходов к оптимизации функций, оперирующих как действительными, так и целыми переменными, является рассмотрение всех переменных как действительных с последующим округлением значений целых переменных. Если в решении оптимизационной задачи участвуют оба вида переменных, она называется оптимизацией со смешанными целыми [1]. Самым распространенным подходом здесь является метод ветвей и границ [2], хотя имеется и ряд других. Первоначально эти подходы были предназначены для решения линейных задач программирования, но затем стали использоваться и для нелинейных. Они рассчитаны на малое число переменных и часто дают приблизительные результаты.
В последнее время для оптимизации со смешанными целыми используются эволюционные методы и оптимизация по принципу роения элементов [4-7]. В этих подходах область затрат исследуется более эффективно, можно оптимизировать большее число переменных, но в то же время необходимо каждый раз применять ГА, работающие с двоичными или непрерывными переменными. Такие алгоритмы имеют раздельные операторы для действительных и целых/двоичных переменных. В данной статье представлен ГА, который отличается от описанных ранее, поскольку его хромосомы имеют значения только в интервале от нуля до единицы. В нем использовано однородное скрещивание и имеется несколько направлений (выборов) мутации. Такой ГА универсален, т.к. один алгоритм можно использовать для любого типа переменной. Все масштабирование и картирование (преобразование) переменных имеет место в затратной функции.
|
|
|
Данный ГА применен к расчету трех разных антенных конструкций. В первом случае максимальный уровень боковых лепестков (УБЛ) линейной решетки минимизируется за счет фазовой неравномерности. Фазовые переменные имеют три формы: действительную, двоичную и смешанную. Представлена эффективность алгоритма при работе со всеми тремя формами. Во втором случае рассматривается расчет микрополосковой антенны с круговой поляризацией, имеющей в составе хромосомы двоичные и действительные переменные. Наконец, выполняется оптимизация антенны с прореженными подрешетками, направленная на получение самого низкого из максимальных УБЛ. Преимуществом данного алгоритма является то, что оптимизацию можно проводить, имея значения переменных любого типа без необходимости изменения самого алгоритма.
II. Двоичный/непрерывный ГА
ГА, описанный в данной статье, минимизирует затратные функции, которые при вычислении затрат оперируют действительными и целыми переменными. Для повышения универсальности ГА все переменные картируются (распределяются) по непрерывным значениям от 0 до 1. Термином непрерывный мы пользуемся вместо действительный, поскольку последний подразумевает значения в интервале ±∞, а первый в настоящей работе соответствует значениям от 0 до 1.
|
|
|
Матрица совокупностей npop x nvar для данного ГА представлена Уравнением 1, где vm , n = переменной n в конфигурации (хромосоме) m при 0 ≤ vm , n ≤ 1. Каждый ряд соответствует хромосоме; значения первоначально создают с помощью однородного произвольного генератора чисел. Непрерывная переменная vm , n преобразуется либо в действительную переменную xn, в целое In, либо в двоичное bn. Смотри Ур.2, где min и max представляют границы переменной, x min ≤ xn ≤ x max; 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.
|
|
|
