нечеткие многокритериальные генетические алгоритмы в

9309
УДК 65.011.56
НЕЧЕТКИЕ МНОГОКРИТЕРИАЛЬНЫЕ
ГЕНЕТИЧЕСКИЕ АЛГОРИТМЫ
В ЗАДАЧАХ ОПТИМАЛЬНОГО
ПРЕДВАРИТЕЛЬНОГО
АЭРОДИНАМИЧЕСКОГО
ПРОЕКТИРОВАНИЯ ЛЕТАТЕЛЬНЫХ
АППАРАТОВ С НЕЧЕТКИМИ ЦЕЛЯМИ
Л.А. Панкова
Институт проблем управления им. В.А. Трапезникова РАН
Россия, 117997, Москва, Профсоюзная ул., 65
E-mail: [email protected]
В.А. Пронина
Институт проблем управления им. В.А. Трапезникова РАН
Россия, 117997, Москва, Профсоюзная ул., 65
E-mail: [email protected]
Ключевые слова: аэродинамическое проектирование, нечеткий многокритериальный
генетический алгоритм
Аннотация: Предлагается постановка задачи предварительного аэродинамического
проектирования летательных аппаратов как задачи достижения нечеткой цели при нечетких ограничениях и применение нечеткого многокритериального генетического алгоритма для ее решения.
1. Введение
Целью этапа предварительного аэродинамического проектирования является выбор
схемы и определение наивыгоднейшего сочетания основных параметров самолета и его
систем, обеспечивающие выполнение заданных требований – летно-технических и маневренных характеристик самолета. Традиционно задачи предварительного проектирования решаются прямыми методами расчета, которые требуют много времени и неудовлетворительны по точности. В настоящее время уже на этапе предварительного
проектирования применяют оптимизационные методы. Следует заметить, что в предварительном проектировании нечетко сформулированы цели (желательные характеристики самолета) и нечетко заданы ограничения на проектируемые параметры. В связи с
этим более адекватной является нечеткая постановка задачи поиска оптимальных проектируемых параметров, а именно, задача достижения нечеткой цели при нечетких ограничениях [1]. Кроме того, задачи предварительного проектирования имеют много
сильно связанных входных параметров и много, как правило, многомодальных (с несколькими локальными экстремумами) выходных характеристик. Такие задачи эффекXII ВСЕРОССИЙСКОЕ СОВЕЩАНИЕ ПО ПРОБЛЕМАМ УПРАВЛЕНИЯ
ВСПУ-2014
Москва 16-19 июня 2014 г.
9310
тивно решаются нечеткими адаптивными многокритериальными эволюционными алгоритмами [2].
В докладе предлагается применить нечеткий многокритериальный генетический
алгоритм для решения задачи оптимального предварительного аэродинамического проектирования летательных аппаратов с нечеткими целями при нечетких ограничениях.
2. Задача достижения нечеткой цели
при нечетких ограничениях
Рассмотрим постановку и метод решения задачи оптимизации как задачи достижения нечеткой цели при нечетких ограничениях (подход Беллмана-Заде [1]).
Пусть X – универсальное множество альтернатив и задано однозначное отображение  : X  Y , x  X . Нечеткая цель при этом задается в виде нечеткого подмножества
~
G множества Y, т.е. в виде функции принадлежности  G~ : Y  [0,1] . Задача состоит в
~
том, чтобы определить нечеткое множество альтернатив D  X , обеспечивающих достижение заданной цели. Это множество представляет собой прообраз нечеткого множе~
ства G при отображении  с функцией принадлежности  D~ ( x)  G~ ( ( x)) . Пусть некоторая альтернатива x обеспечивает достижение цели со степенью G~ и удовлетворяет
ограничениям со степенью  C~ ( x) . Тогда нечетким решением задачи достижения нечеткой цели является пересечение нечетких множеств цели и ограничений с функцией
принадлежности [3]:
 D~ ( x)  min{ G~ ( x),  C~ ( x)}.
При наличии нескольких нечетких целей и нечетких ограничений нечеткое решение описывается функцией принадлежности
 D~ ( x)  min{G~1 ( x),..., G~ ( x), C~1 ( x),..., C~ ( x)}.
n
m
В качестве четкого решения задачи достижения нечеткой цели можно взять аль~
тернативу, имеющую максимальную степень принадлежности множеству D , или вы~
брать альтернативу из D , основываясь на информации, не нашедшей отражения в модели.
3. Mногокритериальные генетические алгоритмы
Напомним общую схему генетического алгоритма, основанного на аналогии с естественными процессами cелекции и генетическими преобразованиями, протекающими
в природе [4]:
a) инициализировать случайным образом популяцию решений;
b) с помощью оператора селекции выбрать часть популяции (родителей) для порождения потомков;
c) применить оператор скрещивания;
d) к новым решениям (потомкам) применить оператор мутации;
e) сформировать новую популяцию из родителей и потомков;
f) повторять шаги b–e, пока не выполнится условие остановки.
Наиболее распространенные многокритериальные генетические методы:
XII ВСЕРОССИЙСКОЕ СОВЕЩАНИЕ ПО ПРОБЛЕМАМ УПРАВЛЕНИЯ
ВСПУ-2014
Москва 16-19 июня 2014 г.
9311




Vector Evaluated Genetic Algorithm (VEGA);
Fonseca and Fleming’s Multiobjective Genetic Algorithm (FFGA);
Niched Pareto Genetic Algorithm (NPGA);
Strength Pareto Evolutionary Algorithm (SPEA).
Эти методы реализуют различные схемы назначения пригодности и селекции.
Метод VEGA, впервые предложенный Шафером в 1984 году, относится к категории селекции по переключающимся целевым функциям. Это означает, что селекция
производится по пригодности индивидов для каждого из K критериев в отдельности.
Промежуточная популяция заполняется равными порциями индивидов, отобранных по
каждому из частных критериев – для каждого из K критериев создается подпопуляция
размером N / K , где N – размер всей популяции. В эти подпопуляции индивиды отбираются с помощью выбранной селекции относительно пригодности по каждому критерию в отдельности. Затем все подпопуляции смешиваются для получения популяции
размером N. Далее, как обычно, осуществляются скрещивание и мутация согласно общей схеме генетического алгоритма.
Метод FFGA [5] использует основанную на Парето-доминировании процедуру
ранжирования индивидов, где ранг каждого индивида определяется числом доминирующих его индивидов. Пригодность индивида, в отличие от пригодности в методе
VEGA, назначается не для каждого критерия в отдельности, а для индивида в целом и
определяется не значениями целевых функций, а рангом каждого индивида в популяции, который основан на понятии Парето-доминирования.
Метод NPGA [6] принципиально отличается от двух предыдущих, так как в нем заложен механизм поддержания разнообразия индивидов. Этот метод представляет собой
комбинацию турнирной селекции и концепции доминирования по Парето. Этап назначения пригодности заменяется модифицированной схемой деления пригодности с использованием понятия ниши, которая определяется для индивидов в пространстве целевых функций и обеспечивает возможность поддержания разнообразия, позволяя получить представительное множество Парето.
Метод SPEA [7] был задуман как способ интеграции различных многокритериальных генетических методов. Используется архив, содержащий недоминируемые решения, ранее найденные. Для каждой индивида в архиве вычисляется значение силы, пропорциональное числу решений, которые он доминирует. Фитнес каждого индивида вычисляется по силе всех недоминируемых решений из архива, которые доминируют его.
Эффективность метода зависит от размера архива.
Вопрос выбора наилучшего метода многокритериальной оптимизации в конкретном случае пока остается открытым. Постоянные значения параметров операторов случайных изменений могут негативно сказываться на качестве работы генетического алгоритма, не позволяют оказывать достаточное влияние на процесс сходимости алгоритма и как следствие увеличивают вероятность попадания его в локальный оптимум.
Адаптация метода к конкретной задаче сводится к настройке параметров генетического
алгоритма.
Показано, что адаптивные генетические алгоритмы, способные осуществлять самонастройку своих параметров, обладают лучшими качественными характеристиками,
с большей вероятностью и за меньшее время находят глобальные решения [8].
4. Нечеткие многокритериальные генетические алгоритмы
Для динамической настройки основных параметров генетического алгоритма, чтобы избежать проблемы преждевременной сходимости, используются методы, основанXII ВСЕРОССИЙСКОЕ СОВЕЩАНИЕ ПО ПРОБЛЕМАМ УПРАВЛЕНИЯ
ВСПУ-2014
Москва 16-19 июня 2014 г.
9312
ные на нечеткой логике. Такой алгоритм, сочетающий поисковые возможности генетических алгоритмов и возможности математического аппарата нечеткой логики, называют нечетким генетическим алгоритмом.
Для контроля и динамического изменения соответствующих параметров генетического алгоритма в систему вводится нечеткий логический контроллер [9], который с
помощью базы нечетких правил определяет с помощью механизма нечеткого логического вывода управляющее воздействие и корректирует значения контролируемых параметров. В качестве входных данных в правилах может использоваться среднее или
лучшее значение целевой (фитнес) функции, меры разнообразия индивидов и т.д. В
общем случае механизм нечеткого логического вывода включает в себя четыре этапа:
введение нечеткости (фаззификация), нечеткий вывод, композиция и приведение к четкости, или дефаззификация. Структура нечеткого логического вывода показана на рис.
1, где A – входной четкий вектор; A% – вектор нечетких множеств, соответствующий
входному вектору A; B% – результат логического вывода в виде вектора нечетких множеств; B – выходной четкий вектор
Рис. 1. Схема нечеткого логического вывода.
Нечеткий логический контроллер преобразует заданные параметры к нечеткому
виду, затем на основе базы нечетких правил определяет управляющее воздействие и
возвращает скорректированные значения контрольных параметров (рис. 1).
5. Задача оптимального предварительного
аэродинамического проектирования летательных аппаратов
Для задачи предварительного аэродинамического проектирования весовой сводки
летательного аппарата может быть использован нечеткий многокритериальный генетический алгоритм достижения нечеткой цели при нечетких ограничениях.
XII ВСЕРОССИЙСКОЕ СОВЕЩАНИЕ ПО ПРОБЛЕМАМ УПРАВЛЕНИЯ
ВСПУ-2014
Москва 16-19 июня 2014 г.
9313
Входные параметры для расчета весовой сводки летательного аппарата представлены в таблице 1, выходные характеристики – в таблице 2.
Таблица 1. Входные параметры для расчета весовой сводки истребителя.
S [m2]
V [m3]

Площадь омываемой поверхности
Объем самолета
Средняя плотность
Масса авионики-экипажа-доп. оборудования
[kg/m3]
M 01 [kg]
M 02 [kg]
Масса экипажа
M v [kg]
P [kg]
Масса доп. оборудования
Форсажная тяга на H = 0, M = 0
Относительный вес
2
Km
K eq
Коэффициент использования композитов
Kf
Коэффициент фирмы
Коэффициент технологии
Таблица 2. Выходные характеристики весовой сводки летательного аппарата.
M toff [kg]
Взлетный вес
M emp [kg]
Масса пустого самолета
M k [kg]
Масса корпуса
M pow [kg]
Масса силовой установки
M eq [kg]
Масса оборудования
M t [kg]
Масса топлива
Детерминированный метод расчета выходных характеристик весовой сводки летательного аппарата и ограничений на входные параметры дан в [10].
Нечеткая цель (множество значений выходных характеристик) задается в виде не~
четкого подмножества G множества Y выходных характеристик с функцией принад~
лежности G~ : Y  [0,1] , нечеткие ограничения – в виде нечеткого подмножества C
множества X входных параметров с функцией принадлежности C~ ( x) . Задача состоит в
~
том, чтобы определить нечеткое множество входных параметров D  X с функцией
принадлежности
 D~ ( x)  min{ G~ ( x),  C~ ( x)}.
Функция принадлежности может принимать различные формы: треугольную, трапецеидальную, в виде колокола или s-образную. Выбор формы, как правило, субъективен и позволяет ЛПР выразить свое предпочтение. Для задачи предварительного аэродинамического проектирования весовой сводки летательного аппарата предлагается
использовать s-образную форму [11].
В качестве четкого решения задачи достижения нечеткой цели можно взять вход~
ные параметры, имеющие максимальную степень принадлежности множеству D :
x  arg(max  D~ ( x)) .
XII ВСЕРОССИЙСКОЕ СОВЕЩАНИЕ ПО ПРОБЛЕМАМ УПРАВЛЕНИЯ
ВСПУ-2014
Москва 16-19 июня 2014 г.
9314
6. Заключение
Предлагается постановка задачи предварительного аэродинамического проектирования летательных аппаратов как задачи достижения нечеткой цели при нечетких ограничениях. Обосновывается применение нечеткого многокритериального генетического
алгоритма для ее решения.
Рассматривается задача предварительного аэродинамического проектирования –
оптимизация весовой сводки летательного аппарата. Для проверки адекватности предложенного подхода предполагается сравнение параметров весовой сводки, полученных
предложенным алгоритмом, с оценками экспертов.
Список литературы
1.
Bellman R.E., Zadeh L.A. Decision-Making in a Fuzzy Environment // Management Science. 1970.
No 17. P. B-141-B-164.
2. Herrera F., Lozano M. Adaptation of genetic algorithm parameters based on fuzzy logic controllers // Genetic Algorithms and Soft Computing. Heidelberg: Physica-Verlag, 1996. P. 95-124.
3. Заде Л. Понятие лингвистической переменной и его применение к принятию приближенных решений. М: Мир, 1976. 100 с.
4. Guliashki V., Toshev H., Korsemov Ch. Survey of Evolutionary Algorithms Used in Multiobjective Optimization // Problems of Engineering Cybernetics and Robotics. 2009. Vol. 60. P. 42-54.
5. Fonseca C.M., Fleming P.J. Multiobjective optimization and multiple constraint handling with evolutionary
algorithms. Part I: A unified formulation. Technical report 564. Sheffield, UK: University of Sheffield,
1995.
6. Horn J., Nafpliotis N., Goldberg D. E. A niched Pareto genetic algorithm for multiobjective optimization //
Proceedings of the First IEEE Conference on Evolutionary Computation. Piscataway, 1994. Vol. 1. P. 8287.
7. Zitzler E., Thiele L. Multiobjective evolutionary algorithms: A comparative case study and the strength Pareto approach // IEEE Transactions on Evolutionary Computation. 1999. No. 3(4). P. 257-271.
8. Wang Lei, Tang Dun-bing. An improved adaptive genetic algorithm based on hormone modulation mechanism for job-shop scheduling problem // Expert Systems with Applications. 2011. Vol. 38, No. 6. Р. 72437250.
9. Herrera F., Lozano M. Fuzzy Adaptive Genetic Algorithms: design, taxonomy, and future directions // Soft
Computing. 2003. No. 7. P. 545-562.
10. Колоколова Л.Г. Метод обобщенных моделей свойств самолета для этапа раннего проектировании //
ТВФ. 1995. № 5-6.
11. Mehmet Cunkas. Design optimization of electric motors by multiobjective fuzzy genetic algorithms
// Mathematical and Computational Applications. 2008. Vol. 13, No. 3. P. 153-163.
XII ВСЕРОССИЙСКОЕ СОВЕЩАНИЕ ПО ПРОБЛЕМАМ УПРАВЛЕНИЯ
ВСПУ-2014
Москва 16-19 июня 2014 г.