ЭлБиб

ХРАНЕНИЕ и ПЕРЕРАБОТКА СЕЛЬХОЗСЫРЬЯ • №4 • 2015

Градиентная информация, используемая в гибридном

алгоритме, позволяет получить локально оптимальное,

а следовательно, и глобальное решение задачи (если

оно существует) при меньших вычислительных затратах

по сравнению с алгоритмом PCA. При локальном поис-

ке для многомерных не всюду дифференцируемых кри-

териальных функций вводятся сглаживающие аппрок-

симации. Вместе с тем, существует класс оптимизаци-

онных задач, в которых использование градиентной

информации или затруднено, или требует значительных

вычислительных затрат.

Второй гибридный метод, реализованный в виде

алгоритма PCASFC, построен на основе алгоритма

Метрополиса в сочетании с детерминированным мето-

дом редукции исходной многомерной задачи к экви-

валентной одномерной [8]. Редукция размерности

пространства проводится при локальном поиске

с использованием метода построения кривой, запол-

няющей пространство, по схеме Пеано-Гильберта [9].

Третий гибридный алгоритм PCALMS является моди-

фикацией алгоритма PCAHS [10].

При наличии нескольких критериев целью оптими-

зации становится поиск множества недоминируемых

решений, образующих Парето-оптимальный фронт.

Предполагается, что в общем случае частные критерии

представляют собой непрерывные липшицевы много-

экстремальные функции [11].

Высокую эффективность показывают, например,

новые гибридные алгоритмы решения рассматривае-

мой задачи векторной оптимизации, реализующие

вариант метода линеаризации для задач многокритери-

альной оптимизации [12]. Для каждой функции, пред-

ставляющей частный критерий или функцию ограни-

чений, вводятся двухпараметрические сглаживающие

аппроксимации. В первом алгоритме оптимизация час-

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

ванием гибридного алгоритма глобальной оптимизации

PCALMS, объединяющего стохастический алгоритм

PCA и метод линеаризации при локальном поиске. Вто-

рой алгоритм глобальной оптимизации PCASFC пост-

роен на основе алгоритма Метрополиса в сочетании

с детерминированным методом кривой, заполняющей

пространство; последний применяется только при

локальном поиске. Для решения задачи липшицевой

минимизации исходная многомерная задача редуциру-

ется к эквивалентной одномерной с использованием

кривой Пеано, построение которой проводится по

схеме Гильберта [8].

Версии гибридных алгоритмов многокритериаль-

ной оптимизации V-PCALMS и V-PCASFC реализо-

ваны в виде прикладных программ [13, 14]. Програм-

мная реализация каждого алгоритма включает в себя

модули ввода исходной информации; модуль, реали-

зующий основной цикл алгоритма, в том числе фазу

случайных возмущений для перехода в новую область

поглощения частицы, фазу исследования области пог-

лощения, фазу возмущений в области рассеяния, фазу

исследования решения в области рассеяния; модуль

локального поиска методом редукции размерности;

модуль вычисления текущего значения частного

минимизируемого критерия; модуль формирования

фронта Парето; модуль вывода результатов решения.

Для определения параметров возмущения на соот-

ветствующих шагах алгоритмов используются стан-

дартные встроенные генераторы случайных чисел.

С целью получения оценки вычислительных затрат

в программном обеспечении во всех случаях предус-

мотрены счетчики числа обращений к подпрограммам

вычисления текущих значений критериальной функ-

ции. Некоторые результаты применения гибридных

алгоритмов к задачам векторной оптимизации дина-

мических систем представлены в работе [15].

Для выявления преимуществ описанных гибридных

алгоритмовPCALMS, PCASFC, V-PCALMS, V-PCASFC,

реализованных в пакете прикладных программ, полу-

чено решение задач, принятых в современной литера-

туре в качестве стандартных эталонных тестов недиф-

ференцируемой оптимизации. Подтверждена, в част-

ности, высокая эффективность двухпараметрического

метода сглаживающих аппроксимаций. Кроме того,

тестирование программных комплексов показало,

что гибридный алгоритм PCALMS на один — три

порядка эффективнее стохастического алгоритма PCA,

а для ряда стандартных эталонных тестов сравним

по эффективности с детерминированным алгоритмом

TRUST [16].

Ниже приведены полученные с использованием гиб-

ридных алгоритмов результаты решения стандартных

эталонных тестовых задач глобальной оптимизации,

а также решение стандартной эталонной тестовой зада-

чи ZDT4 векторной оптимизации при наличии много-

экстремальных критериальных функций [11].

Задача 1.

Тестовая функция Леви-Монтальво

где

=1+0,25(

–1); –10

≤

10;

=1, 2, ...,

;

=10;

=1.

Имеет глобальный минимум

(

) =0 при

= 1, 2, ...,

На рис. 1 показан вид функции в ограниченной

области ее определения для случая

= 2.

250

200

150

100

–1

–2

–3 –3

Рис. 1.

Вид функции в ограниченной области ее определения

для случая n = 2

Электронная Научная СельскоХозяйственная Библиотека