Другие журналы

научное издание МГТУ им. Н.Э. Баумана

НАУКА и ОБРАЗОВАНИЕ

Издатель ФГБОУ ВПО "МГТУ им. Н.Э. Баумана". Эл № ФС 77 - 48211.  ISSN 1994-0408

Модифицированный метод адаптивных взвешенных сумм в задаче многокритериальной оптимизации

# 11, ноябрь 2013
DOI: 10.7463/1113.0632468
Файл статьи: Karpenko_2_P.pdf (2501.02Кб)
авторы: профессор, д.ф.-м.н. Карпенко А. П., Савелов А. С.

УДК 519.6

Россия, МГТУ им. Н.Э. Баумана

apkarpenko@mail.ru

s_savelov@mail.ru

 

Введение

Постановка задачи многокритериальной оптимизации (МКО-задачи) фиксирует множество допустимых значений вектора варьируемых параметров задачи и вектор критериальных функций. Данная информация позволяет обычно выделить не одно решение задачи, но множество таких решений (множество Парето). Поэтому полагаем, как это часто делается в современных публикациях в данной области, что решением МКО-задачи является ее множество Парето. Множество Парето занимает в теории многокритериальной оптимизации исключительное место. Это, прежде всего, связано с тем, что согласно известному принципу Эджворта-Парето, при «разумном» поведении лица, принимающего решения (ЛПР), выбор решения следует производить на этом множестве [1].

Известно большое число методов Парето-аппроксимации, то есть методов построения некоторой конечномерной аппроксимации множества, а тем самым, и фронта Парето. Обзор таких методов представлен, например, в работе [2].

Решение задачи Парето-аппроксимации методом адаптивных взвешенных сумм (AdaptiveWeightedSum (AWS) method) предложили Рю, Ким и Ван (J-H. Ryu, S. Kim, H. Wan) [3]. Метод основан на аддитивной свертке частных критериев оптимальности, но, в отличие от классического метода суммы взвешенных критериев (WeightedSum (WS) method) [1], также использующего такую свертку, предполагает адаптацию весовых коэффициентов в процессе итераций на основе информации о текущем положении подобласти поиска. Целью разработки метода AWSбыло преодоление известного недостатка метода WS, заключающегося в невозможности локализации точек множества Парето, которые соответствуют вогнутым фрагментам фронта Парето.

Для сокращения затрат на вычисление значений критериальных функций метод AWS использует метамодели этих функций. Поскольку в практически значимых задачах вычислительная сложность критериальных функций обычно является высокой, это обстоятельство позволяет сократить вычислительные затраты на решение МКО-задачи и делает метод весьма перспективным, например, в задачах автоматизированного проектирования. Недостатком метода AWS в существующем виде является его ориентация на решение только двухкритериальных задач Парето-аппроксимации.

Авторы метода AWS выполнили исследование его эффективности для двух относительно простых тестовых задач многокритериальной оптимизации [3], которое показало высокую эффективность метода. В работе [4] мы повторили указанное исследование, а также выполнили аналогичное исследование для трех других сложных тестовых задач. Результаты этого исследования показали, что метод AWS дает высокое качество Парето-аппроксимации в случае выпуклого, хотя, быть может, и несвязного фронта Парето. Для задач, имеющих вогнутый фронт Парето, метод не всегда обеспечивает удовлетворительное качество решения или обеспечивает его, но при значительном числе итераций. В некоторых случаях метод дает недопустимые решения, обусловленные используемым способом учета ограничений на текущую подобласть поиска.

Работа открывает цикл из двух публикаций и имеет целью преодоление указанных недостатков метода AWS. Вторая работа будет посвящена приложению представляемого в данной работе методического, алгоритмического и программного обеспечения к решению некоторых задач параметрической идентификации кинетических моделей реакций нейтрального металлокомплексного катализа.

В первом разделе работы даем постановку МКО-задачи. Второй раздел представляет базовые методы решения этой задачи. В третьем разделе рассматриваем несколько предложенных нами модификаций метода AWS. В четвертом разделе приводим краткое описание разработанного программного обеспечения, которое реализует метод AWS и его модификации. Пятый раздел посвящен исследованию эффективности указанных модификаций метода AWS. В заключении формулируем основные результаты работы и обсуждаем перспективы ее развития.

 

1. Постановка задачи

Пусть множеством допустимых значений вектора варьируемых параметров Xявляется ограниченное и замкнутое множество . Положим, что критериальная вектор-функция  со значениями в критериальном пространстве  определена в области . ЛПР стремится минимизировать в этой области каждый из частных критериев оптимальности , что условно записываем в виде

,                                       (1)

где векторы  ‑искомое решение задачи многокритериальной оптимизации. Здесь и далее запись вида , где  - вектор или некоторое счетное множество, означает размерность этого вектора или мощность множества соответственно.

Вектор-функция  выполняет отображение множества  во множество , которое называется множеством достижимости. Множество и фронт Парето задачи (1) обозначаем ,  соответственно; , . Конечномерные аппроксимации этих множеств обозначаем ,  соответственно и называем архивными.

 

2. Базовые методы решения МКО-задачи

2.1. Метод взвешенных сумм

Классический метод взвешенных целевых функций основан на использовании фитнесс-функция вида

,

где вектор  представляет собой -мерный вектор весовых коэффициентов ;  ‑ символ скалярного произведения. Решение задачи глобальной условной оптимизации

                                    (2)

дает точку  на множестве Парето задачи (1) и соответствующую точку  на фронте Парето этой задачи.

Схема WS-метода включает в себя следующие основные шаги.

1) Множество  допустимых значений вектора весовых множителей  покрываем некоторой сеткой  с узлами , .

2) Для каждого  решаем задачу глобальной условной оптимизации (2) – получает точку , а также соответствующую точку .

Совокупности  полученных точек образует искомые аппроксимации множества и фронта Парето соответственно.

Достоинствами WS-метода являются идейная и реализационная простота. Основные недостатки метода состоят в невозможности аппроксимации невыпуклых частей фронта Парето и отсутствии гарантий получения равномерной аппроксимации.

 

2.3. Базовый метод доверительной области

Поясним суть базового метода доверительной области (BasicTrustRegion, BTR) [5, 6] на примере задачи безусловной однокритериальной оптимизации

.                                       (3)

Содержание основных процедур метода заключается в следующем.

Инициализация.Определяем значения свободных параметров метода:  - начальный радиус области доверия;  - параметры для оценки адекватности метамодели функции , ;  - параметры изменения радиуса области доверия, . Случайным образом выбираем центральную точку .

Формирование метамодели. Метамодель критериальной функции представляет собой аппроксимацию  функции  в пределах текущей области доверия (trustregion)

.

Здесь  - радиус области доверия на текущей итерации ;  ‑ некоторая векторная норма, определяющая форму области доверия. Тип «наилучшей» метамодели зависит от ландшафта критериальной функции. Чаще всего в качестве метамодели  используют квадратичную аппроксимацию функции  в пределах области доверия . При этом возникает задача построения эффективного плана эксперимента [7], на основе которого строится эта аппроксимация. Обычно используют центральный композиционный план на основе дробной реплики. Авторы считают перспективным генерацию плана эксперимента на основе  последовательности [8].

Решение оптимизационной задачи.Данная процедура предполагает решение задачи оптимизации

,                                         (4)

где  ‑ пробная точка (trialpoint).

В работе [5] показано, что для сходимости метода BTRнеобязательно решение задачи (4) как задачи глобальной оптимизации – достаточно лишь, чтобы это решение обеспечивало «существенное уменьшение» (sufficient reduction) значения функции  по сравнению с ее значением в точке . На этом основании для сокращения вычислительных затрат задачу (4) сводят к однопараметрической задаче поиска минимума функции  вдоль дуги Коши (Cauchy arc):

.                                  (5)

Здесь  ‑ параметрически заданная дуга Коши,  ‑ точка Коши.

Схема (5), по сути, является вариацией метода наискорейшего спуска и поэтому может обеспечить лишь линейную скорость сходимости. Более эффективные методы решения задачи (4) основаны на использовании матрицы Гессе  для выбора направления поиска.

Оценка пробной точки.В качестве количественной оценки  адекватности построенной модели  целевой функции  используем отношение реального уменьшения функции  при переходе из точки  в пробную точку , предсказанную моделью:

.

Если , то модель  полагаем адекватной и в качестве новой центральной точки принимаем пробную точку, то есть, полагаем . В противном случае центральная точка остается прежней: .

Выбор радиуса области доверия.Итерацию, для которой , называют удачной; очень удачной; неудачной. Напомним, что . В случае очень удачной итерации радиус доверительной области увеличиваем, то есть, в качестве  принимает некоторое значение из интервала . Если итерация  была удачной , то величину  уменьшаем или оставляем неизменной: . Наконец, в случае неудачной итерации, радиус уменьшаем: .

В качестве критерия останова итерационного процесса принимаем один из классических критериев, например, критерий, основанный на евклидовой норме градиента:

.

Здесь  ‑ заданная малая положительная константа.

Известны модификации метода BTR, ориентированные на решение задачи условной оптимизации вида (3), когда  [5].

2.3. Канонический метод адаптивных взвешенных сумм

Канонический метод адаптивных взвешенных сумм (Canonical Adaptive Weighted Sum, CAWS) предназначен для решения двухкритериальной задачи Парето-аппроксимации и ориентирован на устранение недостатков, присущих WS-методу. Метод предложили Ким и Вик (I.Y. Kim, O.Lde Weck) [9]. Рассмотрим основные процедуры метода.

Построение грубой Парето-аппроксимации. Грубую аппроксимацию множества Парето строим посредством классического WS-метода. Взвешенную сумму критериев записываем в виде

,   .

Шаг  выбираем, исходя из заданного числа разбиений :

.

Удаление близких решений. В качестве меры близости решений в критериальном пространстве используем евклидову норму: точки  и  текущей аппроксимации фронта Парето полагаем близкими, если

,

где  ‑ заданная малая положительная константа. Одну из близких точек исключаем из архивного множества  и соответствующую точку  или  исключаем из множества .

Определение числа разбиений. Число разбиений для i-го сегмента текущей аппроксимации фронта Парето определяет формула

,    ,

где  и  - число разбиений и длина i-ого сегмента соответсвенно;  ‑ средняя длина сегмента;  - константа метода, определяющая плотность разбиения;  ‑ оператор округления до ближайшего целого;  ‑ число сегментов в текущей аппроксимации фронта Парето.

Решение локальных задач Парето-аппроксимации. Построение аппроксимации фронта Парето в i-ом сегменте состоит в решении МКО-задачи вида (1) в области

,

где  ‑ смещения -го сегмента текущей аппроксимации фронта Парето [9]. Для решения этой задачи используется WS-метод с шагом . Полученные точки добавляем в архивы , .

Итерации метода AWS заканчиваются, когда длины всех сегментов оказываются меньше порогового значения:

,   .

 

2.4. Метод адаптивных взвешенных сумм

Метод адаптивных взвешенных сумм (Adaptive Weighted Sum, AWS) для двухкритериальной задачи Парето-аппроксимации предложили, как отмечалось выше, Рю, Ким и Ван (J-H. Ryu, S. Kim, H. Wan) в работе [3]. Метод AWS сочетает в себе элементы метода WS и метода BTR. Основными в методе AWS являются следующие процедуры.

Инициализация метода. Определяем значения свободных параметров метода:  ‑ начальный радиус области доверия (trust region radius);  ‑ коэффициент сужения этой области;  ‑ минимальная величина радиуса. Случайным образом в области  выбираем центральную точку

Определение центральной точки. На итерации  центральную точку  отыскиваем среди точек текущей Парето-аппроксимации . С этой целью элементы множеств  сортируем по возрастанию первого частного критерия  и представляем в виде линейных списков. Расстояние  архивной точки  до ближайших к ней в списке  точек определяет формула

,   .                      (6)

Алгоритм определения центральной точки  использует следующее правило.

1) Если , то полагаем , где

.

Здесь  - множество точек, использованных в качестве центральных на всех предыдущих итерациях . Иными словами, за центральную точку принимаем точку, во-первых, наиболее удаленную от других точек множества  в смысле расстояния (6), и, во-вторых, не использованную на предшествующих итерациях.

2) Если , то с равной вероятностью полагаем  или .

3) Если , то принимается .

Формирование метамоделей. Метамодель  представляет собой квадратичную аппроксимацию функции  в окрестности точки :

Здесь ,  ‑ вектор градиента и матрица Гессе функции  в точке .

Если , то дополнительно строим метамодели

,

,

а если  или  ‑ метамодель

.

В случае  весовые множители ,  определяем по правилу

,

;

в случае  – по правилу

;

в случае  – по правилу . Здесь константы ,  выбираются таким образом, чтобы обеспечить выполнение условий нормировки .

В работе [3] процедура формирования квадратичных метамоделей ,  не раскрыта. Остановимся на этом вопросе.

Для формирования квадратичных метамоделей ,  используем центральный композиционный план (ЦКП) с центром в точке  [7]. Для упрощения вычислений «звездное» плечо в ЦКП выбираем таким образом, чтобы этот план приобрел свойство ортогональности. В качестве ядра ЦКП используем полный факторный эксперимент. Легко видеть, что в общем случае необходимое число испытаний (вычислений значений критериальной функции) для построения одной метамодели равно

,

где  ‑ число испытаний в точках ядра плана,  ‑ число «звездных» точек,  ‑ число испытаний в центре плана. Таким образом, в нашем случае (когда ) имеем

.

Серьезной проблемой при использовании ЦКП является генерация эффективной дробной реплики. Используем для этой цели функции Уолша [10].

Решение оптимизационных задач. Данная процедура предполагает решение задач оптимизации

                    (7)

где текущую область доверия  определяет формула

.

Если , то решения  позволяют отыскать приближенно оптимальные по Парето точки , принадлежащие области доверия , путем решения оптимизационных задач

   .                   (8)

Данный этап алгоритмаиллюстрирует рисунок 1, на котором принято

, , .

 

Рис_6

 

Рисунок 1 – К схеме метода AWS: результаты решения задач (7)

 

Важно, что задачи (7), (8) представляют собой задачи оптимизации квадратичных функций, для решения которых известны высокоэффективные методы, алгоритмы и соответствующее программное обеспечение.

В процессе итераций текущий радиус области доверия уменьшаем по правилу  до достижения минимально допустимой его величины . Новое состояние архивного множества  получаем путем добавления в него точек , , ,  и исключения из полученного набора доминируемых решений. Аналогично, множество  формируем путем добавления в него точек , , , .

 

3. Модификации метода адаптивных взвешенных сумм

3.1. Повышение разнообразия множества архивных точек

(модификация )

Наши исследования показали, что в некоторых случаях метод AWSобеспечивает аппроксимацию только части множества Парето, то есть не обеспечивает достаточное разнообразие множества архивных точек  (рисунок 2).

 

 

а) точный фронт Парето

б) результат аппроксимации фронта методом AWS

Рисунок 2 – Тестовая задача ZDT3 (п. 4.1)

 

Суть модификации  состоит в решении на каждой итерации в крайних точках архивного множества  задач

      

      

Здесь

 

3.2. Смещение области доверия (модификация )

Точки множества Парето могут в некоторых случаях плотно прилегать к одной из границ области определения (рисунок 3). При решении таких задач метод AWS уменьшает радиус области доверия  на каждой итераций, сокращая в результате разнообразие архивных точек.

 

Рисунок 3 – Множество Парето тестовой задачи ZDT3 (п. 5.1):

 

Идея модификации  состоит в смещении центра области доверия «вглубь» области определения, не изменяя при этом ее радиуса (рисунок 4).

 

Рисунок 4 – Смещение области доверия:

 

3.3. Нейросетевая аппроксимация целевых функций

(модификация )

Идея данной модификации состоит в построении метамоделей критериальных функций с помощью нейронных сетей [11]. Поскольку на каждой итерации метода AWS аппроксимация критериальных функций производится в пределах «небольшой» области доверия  используем  радиально-базисные нейронные сети. Полагаем число нейронов  в скрытом слое равным девяти (по числу точек испытаний в ЦКП) и располагаем их в указанных точках. Для обучения нейронной сети используется алгоритм Нелдера-Мида, варьируемыми параметрами которого являются веса  и ширины  радиально-базисных функций; .

 

4. Программная реализация

Для реализации метода  и его модификаций  ‑  использовано программное обеспечение, которое является свободным и распространяется по лицензии GPL (GNU Public License). В силу кросс-платформенности и высокой эффективности программная реализация выполнена на языке программирования C++. Для компиляции использовался набор компиляторов GCC (GNU Compiler Collection). Разработанное программное обеспечение использует библиотеку численного анализа GNU Scientific Library (GSL) и аналогичную библиотеку F2C (Fortran to C ) для трансляции программного кода, написанного на языке Fortran, в код на языке C. Графический вывод результатов работы программы реализован с помощью утилиты Gnuplot.

Основными являются следующие классы программной модели:

‑ AWSAlgorithmреализация алгоритма AWS;

‑ OptimAlgorithm, PenaltyAlgorithm, SlaceTolAlgorithmалгоритмы условной оптимизации при решении однокритериальных задач (7), (8);

‑ ApproximatorNNet, ApproximatorCCDаппроксимация критериальных функций;

‑ Design, FullFactorialDesign, WalshDesignпланирование экспериментов для квадратичной аппроксимации целевых функций;

 HyperSphereConstrain, LinearConstrainформирование ограничений;

‑ ParetoBruteForcerгенерация начальной аппроксимации множества Парето;

‑ ParetoMeasurerоценка качества аппроксимации множества (фронта).

Программное обеспечение реализует планы полного факторного эксперимента и дробной реплики на основе функций Уолша (классы FullFactorialDesignи WalshDesignсоответственно). Интерфейс абстрактного класса Design позволяет использовать любой метод локальной условной оптимизации. Метод наименьших квадратов реализован с использованием библиотеки GSL(функция gsl_multifit()). Решение задач локальной условной однокритериальной оптимизации (7), (8) осуществляется методами штрафных функций и скользящего допуска в комбинации с известным методом Нелдера-Мида (классы PenaltyAlgorithmи SlaceTolAlgorithmсоответственно). Интерфейс абстрактного класса OptimAlgorithm позволяет использовать любой метод локальной условной оптимизации.

Общий объем программного кода составляет около 5000 строк.

 

5. Исследование эффективности модификаций метода адаптивных взвешенных сумм

5.1. Организация экспериментов

Индикаторы качества алгоритма. Качество аппроксимации множества Парето оцениваем с помощью следующих индикаторов [12]:

‑ мощностьмножестварешений (overall non-dominated vector generation)

;

‑ близость найденных решений к точному множеству Парето рассматриваемой МКО-задачи (generational distance)

,

где  - расстояние от i-ой точки архива недоминируемых решений  до ближайшего точного решения;

‑ равномерность распределения решений в полученной Парето-аппроксимации (spacing)

,

где  - расстояние от i-ой точки архива  до ближайшей соседней точки;  - среднее значение .

В качестве индикатора вычислительной эффективности метода используем число испытаний .

Число итераций в вычислительных экспериментах ограничиваем величиной .

Тестовые МКО задачи. Вычислительные эксперименты выполнены с использованием следующих тестовых задач.

1) Двухмерная двухкритериальная задача Аудета (С. Audet):

;

,

;

,

Фронт Парето задачи является непрерывным; значению  соответствует выпуклый фронт, а значению   ‑ невыпуклый[13].

2) Двумерная двухкритериальная задача ZDT3 [12]

,

где

Сложность задачи обусловлена несвязным, хотя и выпуклым, фронтом Парето.

3) Двумерная двухкритериальная задача ZDT6 [12]:

;

,

;

Сложность заключается в том, что задача имеет невыпуклый фронт Парето.

4) Двумерная двухкритериальная задача ZDT7 [12]:

;

,

;

Задача имеет непрерывный выпуклый фронт Парето и несколько локальных фронтов.

 

5.2. Результаты экспериментов

Модификация  (п. 3.1). Рассматриваем случай . Исследование выполнено на двухкритериальных тестовых задачах Аудета и ZDT3. Результаты экспериментов представлены в таблицах 1 - 4 и на рисунках 5 ‑ 14. На этих рисунках и далее черные точки показывают конечное состояние множеств , а светлые точки – их промежуточные состояния. Для задачи ZDT3 представляем результаты двух экспериментов (старты 1, 2).

 

Таблица 1 – Тестовая задача Аудета (выпуклый фронт): результаты экспериментов

 

Метод

Индикаторы эффективности

637

70

0,202

0,065

450

33

0,087

0,122

 

Таблица 2 – Тестовая задача Аудета (невыпуклый фронт): результаты экспериментов

 

Метод

Индикаторы эффективности

868

19

0,008

0,052

450

16

0,028

0,13

 

Таблица 3 – Тестовая задача ZDT3: результаты экспериментов; старт 1

 

Метод

Индикаторы эффективности

494

90

0,011

0,04

450

84

0,012

0,04

 

Таблица 4 – Тестовая задача ZDT3: результаты экспериментов; старт 2

 

Метод

Индикаторы эффективности

527

76

0,01

0,045

 

Рисунок 5 – Задача Аудета (выпуклый фронт):

метод ; ; ; ;

 

Рисунок 6 – Задача Аудета (выпуклый фронт):

метод AWS; ; ; ;

 

Рисунок 7 – Задача Аудета (невыпуклый фронт);

метод AWS; ; ; ;

 

Рисунок 8 – Задача Аудета (невыпуклый фронт):

метод ; ;  ; ;

 

Рисунок 9 – Задача ZDT3: метод AWS; ; ; ; ; старт 1

 

Рисунок 10 – Задача ZDT3 (пространство параметров): метод AWS; ; ; ; ; старт 1

 

Рисунок 11 – Задача ZDT3: метод ; ; ; ; ; старт 1

 

Рисунок 12 – Задача ZDT3 (пространство параметров): метод ; ; ; ; ; старт 1

 

Рисунок 13 – Задача ZDT3: метод ; ; ; ; ; старт 2

 

Рисунок 14 – Задача ZDT3 (пространство параметров): метод ; ; ; ; ; старт 2

 

Представленные результаты показывают, что для задачи Аудета, имеющей выпуклый фронт Парето, модификация  превосходит метод  по индикатору  более чем в два раза, а по индикатору  ‑ почти в два раза. В то же время, модификация  проигрывает методу  по индикатору  примерно на 30% и по индикатору  ‑ примерно на 60%. Для более сложной задачи Аудета, имеющей невыпуклый фронт Парето, модификация  обеспечивает близкие к методу  результаты по индикатору  и примерно в 3,5 и 2,5 раз лучшие результаты по индикаторам  и  соответственно. С другой стороны, для этой задачи метод  проигрывает методу  по индикатору  примерно на 50%.

Иная картина наблюдается в случае задачи ZDT3, имеющей, напомним, выпуклый, но разрывный фронт Парето. В этом случае модификация  по всем рассматриваемым индикаторам обеспечивает результаты, близкие к методу . В то же время, из сравнения результатов, представленных на рисунках 9, 11, 13, вытекает, что в условиях экспериментов метод  локализует три из пяти фрагментов разрывного фронта Парето, а метод  ‑ четыре. Таким образом, в случае задачи ZDT3 метод AWSне обеспечивает удовлетворительное качество Парето-аппроксимации, отыскивая только часть множества и фронта Парето. Модифицированный метод  справляется с этой задачей лучше, находя большую часть этих множеств.

Модификация  (п. 3.2).Эффективность данной модификации оценена с помощью двухкритериальной задачиZDT3. Результаты экспериментов при числе итераций  представлены на рисунках 15, 16. Эти результаты показывают, что ожидаемое увеличение скорости сходимости в сравнении с методом AWS не достигнуто. Необходимы дополнительные исследования для объяснения этого эффекта.

 

Рисунок 15 – Задача ZDT3: метод ; ; ; ;

 

Рисунок 16 – Задача ZDT3 (пространство параметров): метод ; ; ; ;

 

Модификация  (п. 3.3). Исследование выполнено на двухкритериальных тестовых задачах ZDT3 и ZDT7 при . Результаты экспериментов представлены в таблицах 5, 6 и на рисунках 17 - 20.

 

Таблица 5 – Тестовая задача ZDT3: результаты экспериментов

Метод

Индикатор эффективности

10314

438

0,0007

0,017

35536

91

0,005

0,046

 

Таблица 6 – Тестовая задача ZDT7: результаты экспериментов

Метод

Индикаторы эффективности

9654

133

0,001

0,015

36384

388

0,0005

0,009

 

Рисунок 17 – Тестовая задача ZDT3: метод ;

; ; ;

 

Рисунок 18 – Тестовая задача ZDT3: метод ;

; ; ;

 

Рисунок 19 – Тестовая задача ZDT7: метод ; ; ; ;

 

Рисунок 20 – Тестовая задача ZDT7: метод ; ; ; ;

 

Представленные результаты показывают, что для задачи ZDT3 модификация  проигрывает методу  по всем четырем рассматриваемым индикаторам эффективности. Для задачи ZDT7 имеет место иная ситуация: по индикатору  модификация  лучше метода  почти в три раза, по индикаторам ,  ‑ в два и 1,7 раза соответственно. С другой стороны, такие высокие результаты достигаются модификацией  за счет почти четырехкратного увеличения числа испытаний, то есть индикатора .

 

Заключение

В работе представлен обзор метода AWS, а также методов, на которых он основан. Предложены три модификации метода AWS, имеющие целью устранение его недостатков. Выполнена программная реализация метода AWS и его указанных модификаций. На известных тесовых МКО-задачах выполнено широкое исследование эффективности разработанного методического, алгоритмического и программного обеспечения. Рассмотрены четыре индикатора эффективности, характеризующие, как качество получаемой Парето-аппроксимации, так и соответствующие вычислительные затраты. Исследование показало, что часто предложенные модификации обеспечивают значительно превосходство над методом AWS. В тоже время, исследование не позволило получить все ожидаемые результаты. Авторы предполагают дополнительные исследования для локализации причин неудачных модификаций. Кроме того, авторы планируют исследование эффективности модификаций на тестовых задачах высокой размерности.

Работа поддержана грантом РФФИ № 12-07-00324-а «Структурная и параметрическая идентификация кинетических моделей реакций нейтрального металлокомплексного катализа».

 

Список литературы

1.              Ларичев О.И. Теория и методы принятия решений: учебник для ВУЗов. М.: Университетская книга, Логос, 2006. 392 с.

2.              Карпенко А.П., Митина Е.В., Семенихин А.С. Популяционные методы аппроксимации множества Парето в задаче многокритериальной оптимизации. Обзор // Наука и образование. МГТУ им. Н.Э. Баумана. Электрон. журн. 2012. № 4.  Режим доступа: http://www.technomag.edu.ru/doc/363023.html  (дата обращения 01.10.2013).

3.              Jong-hyun Ryu, Sujin Kim, Hong Wan. Pareto front approximation with adaptive sum method in multiobjective simulation optimization // Proc. of the 2009 Winter Simulation Conference (WSC), 2009, Austin, pp. 623-633. Available at: http://www.informs-sim.org/wsc09papers/060.pdf , accessed 01.10.2013.

4.              Карпенко А.П., Савелов А.С., Семенихин А.С. Адаптивный метод взвешенных сумм в задаче Парето-аппроксимации // Наука и образование. МГТУ им. Н.Э. Баумана. Электрон. журн. 2012. № 6. DOI: 10.7463/0612.0423283

5.              Conn A.R, Gould N.I.M., Toint P.L. Trust-Region Methods. SIAM, Philadelphia, USA, 2000. 959 p. (MPS-SIAM Series on Optimization; no. 1).

6.              Nocedal J., Wright S.J. Numerical Optimization. Springer, 1999. 634 p. DOI: 10.1007/b98874

7.              Асатурян В.И. Теория планирования эксперимента. М.: Радио и связь, 1983. 248 с.

8.              Соболь И.М., Статников Р.Б. Выбор оптимальных параметров в задачах со многими критериями: учеб. пособие для вузов. М.: Дрофа, 2006. 182 с.

9.              Kim I.Y., de Weck O.L. Adaptive weighted-sum method for bi-objective optimization: Pareto front generation // Structural and Multidisciplinary Optimization. 2005. Vol. 29, no. 2. P. 149-158. DOI: 10.1007/s00158-004-0465-1

10.          Susan M. Sanchez, Paul J. Sanchez. Very large fractional and central composite design // ACM Transactions on Modeling and Computer Simulation. 2005. Vol. 15, no. 4. P. 362-377.

11.          Хайкин С. Нейронные сети: полный курс: пер. с англ. М.: Издательский дом «Вильямс», 2006. 1104 с.

12.          Zitzler E., Deb K., Thiele L. Comparison of Multiobjective Evolutionary Algorithms: Empirical Results // Evolutionary Computation. 2000. Vol. 8, no. 2. P. 173-195. DOI: 10.1162/106365600568202

13.          Audet C., Savard G., Zghal W. Multiobjective optimization through a series of single-objective formulations // SIAM Journal on Optimization. 2008. Vol. 19, no. 1. P. 188-210. DOI: 10.1137/060677513

Поделиться:
 
ПОИСК
 
elibrary crossref ulrichsweb neicon rusycon
 
ЮБИЛЕИ
ФОТОРЕПОРТАЖИ
 
СОБЫТИЯ
 
НОВОСТНАЯ ЛЕНТА



Авторы
Пресс-релизы
Библиотека
Конференции
Выставки
О проекте
Rambler's Top100
Телефон: +7 (915) 336-07-65 (строго: среда; пятница c 11-00 до 17-00)
  RSS
© 2003-2020 «Наука и образование»
Перепечатка материалов журнала без согласования с редакцией запрещена
 Тел.: +7 (915) 336-07-65 (строго: среда; пятница c 11-00 до 17-00)