сужение области парето пример

УДК.519.6МГТУ им. Н.Э. Баумана mitinakaterina@gmail.comВведениеИзвестно большое число методов решения задачи многокритериальной оптимизации (МКО-задачи), из числа которых перспективными являются методы, основанные на предварительном построении аппроксимации множества Парето (а тем самым, и фронта Парето) этой задачи [1, 2]. Простейшим из таких методов является сеточный метод [3]. В ситуации, когда требуется высокая точность аппроксимации множеств Парето и/или когда имеет место высокая вычислительная сложность целевых функций, сеточный метод может требовать неприемлемо высоких вычислительных ресурсов. Поэтому в настоящее время интенсивно развиваются альтернативные методы [4].Обычно указанные методы строят на основе эволюционных алгоритмов и чаще всего – на основе генетических алгоритмов [5]. При этом соответствующие методы Парето-аппроксимации называют эволюционными. Обзор таких методов представлен, например, в работах [6, 7]. Принципиальным в этих методах является не использование именно эволюционных алгоритмов, а правила формирования фитнесс-функции, обеспечивающие перемещение индивидов популяции, в конечном счете, в направлении множества Парето. Эволюция же этих индивидов может протекать по законам, отличным от законов, используемых в эволюционных алгоритмах, например, по законам миграции частиц в алгоритме роя частиц [8, 9]. Поэтому в качестве общего названия рассматриваемых методов используем термин «популяционные методы Парето-аппроксимации».Для полноты картины, наряду с популяционными методами в работе рассматриваем наиболее известные не популяционные методы. Особенностью обзора является то, что в той его части, которая посвящена популяционным методам, мы концентрируем наше внимание, преимущественно, на правилах формирования фитнесс-функции, используемых в этих методах. Можно выделить следующие основные требования к методам Парето-аппроксимации [7]: - точки найденной аппроксимации расположены достаточно близко к точному множеству Парето;- аппроксимация покрывает все множество Парето;- распределение точек аппроксимации равномерно.В современных методах Парето-аппроксимации для выполнения последнего требования используют специальные механизмы, обеспечивающие приемлемый разброс (spread) точек аппроксимации. Наиболее известным механизмом такого сорта является механизм нишевания (niching) [10]. Самостоятельную проблему представляет разработка критериев оценки качества Парето-аппроксимации, которые отражали бы указанные требования. Примеры таких критериев рассмотрены, например, в работах [11, 12]. Известно несколько классификаций методов Парето-аппроксимации. Используем классификацию, предложенную Гуменниковой А. В. [13], дополнив ее классом «наивных» методов [14] и классом прочих методов. Итого рассматриваем следующие пять классов методов Парето-аппроксимации: - «наивные» методы;- методы переключающихся целевых функций;- методы агрегации целевых функций;- методы на основе ранжирования агентов популяции;- прочие методы.В разделе 1 приведена математическая постановка задачи, разделы 2 - 6 посвящены рассмотрению указанных классов методов Парето-аппроксима

авторы: Карпенко А. П., Семенихин А. С., Митина Е. В.

Инженерное образование # 04, апрель 2012

77-30569/363023 Популяционные методы аппроксимации множества Парето в задаче многокритериальной оптимизации. Обзор.

Эл № ФС 77 - 48211. Государственная регистрация №0421200025. ISSN 1994-0408

Наука и Образование: научно-техническое издание: 77-30569/363023 Популяционные методы аппроксимации множества Парето в задаче многокритериальной оптимизации. Обзор.