Алгоритмы технологии IOSO позволяют успешно решать задачи многокритериальной (десятки критериев) многомерной (сотни переменных) нелинейной оптимизации. Основные достоинства наших алгоритмов:
- не используются свёрточные подходы при решении многокритериальных задач;
- определяется желаемое количество Парето-оптимальных решений, равномерно распределённых в пространстве критериев;
- возможно решение задач для целевых функций со сложной топологией — невыпуклых, недифференцируемых, многоэкстремальных;
- естественным образом используется распараллеливание вычислительного процесса.
Наши алгоритмы многокритериальной оптимизации являются незаменимым инструментом при решении задач многодисциплинарной и многоуровневой оптимизации, а также для оптимизации в условиях неопределённостей.
Постановка задачи
Большинство реальных инженерных задач оптимизации требуют одновременной оптимизации более чем одной целевой функции. В таких случаях маловероятно, что различные критерии будут оптимизироваться одним и тем же набором параметров. Следовательно, для обеспечения приемлемого проектного решения необходим компромисс между критериями.
Поскольку показатели эффективности системы могут быть различными и взаимно противоречивыми, для оптимизации суммарной эффективности целесообразно применять многокритериальный подход. Математически корректно это можно сделать только при использовании некоторого принципа оптимальности. Мы применяем принцип оптимальности по Парето, суть которого состоит в следующем: решение многокритериальной задачи оптимизации считается Парето-оптимальным, если не существует других решений, которые одновременно лучше удовлетворяют всем критериям. Иными словами, могут существовать решения, превосходящие данное по одному или нескольким критериям, однако они неизбежно уступают Парето-оптимальному решению по остальным критериям.
В этом случае задача многокритериальной оптимизации состоит в нахождении полного множества Парето-оптимальных решений. Поскольку в реальных задачах найти полное бесконечное множество Парето-оптимальных решений, как правило, невозможно, инженерная постановка многокритериальной задачи сводится к определению конечного подмножества различимых в пространстве критериев Парето-оптимальных решений.
Наш метод
Предварительная процедура заключается в формировании начального плана эксперимента (XW). Для каждого вектора переменных вычисляются значения критериев оптимизации и ограничений с использованием математической модели исследуемой системы.
Основной алгоритм оптимизации представляет собой следующую последовательность шагов:
Шаг 1. Из текущего плана эксперимента извлекаются все различимые Парето-оптимальные точки (подмножество A, число точек n ≥ 1).
Шаг 2. Из текущего множества Парето-оптимальных точек (подмножество A) случайным образом выбирается единственная точка x_cur.
Шаг 3. Формируется подмножество плана эксперимента XM, состоящее из M точек, ближайших к текущей точке x_cur по линейной метрике. Определяется текущая область поиска.
Шаг 4. В текущей области поиска строятся поверхности отклика для каждого из критериев оптимизации.
Шаг 5. В текущей области поиска решаются задачи оптимизации с использованием построенных поверхностей отклика. В результате определяется набор точек — кандидатов на экстремумы отдельных критериев в текущей области поиска.
Шаг 6. В этих точках вычисляются истинные значения критериев с использованием математической модели системы. План эксперимента обновляется.
Шаг 7. Проверяется критерий останова.
Шаг 8-а. Переход к Шагу 1.
Шаг 8-б. В окрестности текущей Парето-оптимальной точки генерируются дополнительные точки с использованием нормального распределения; они включаются в план эксперимента. Переход к Шагу 1.
Принципиально важно отметить, что на начальном этапе оптимизации точность поверхностей отклика может быть невысокой — вследствие малого числа точек в плане эксперимента и относительно большого размера текущей области поиска. Однако по мере продвижения оптимизации число точек в окрестности Парето-оптимальных решений возрастает, а размер текущей области поиска сокращается. Эти тенденции обеспечивают более точную аппроксимацию целевых функций и, как следствие, повышение эффективности оптимизационного процесса. Фактически в ходе оптимизации непрерывно накапливается информация о целевых функциях в окрестности Парето-оптимальных точек.
Для повышения эффективности предложенного метода по мере накопления информации разработан ряд эвристических процедур, направленных на адаптивное изменение числа точек в плане эксперимента и в текущей области поиска, корректировку параметра нормального распределения, а также рациональный выбор между шагами 8-а и 8-б основного алгоритма.
Основные преимущества метода
Главные преимущества предложенного метода косвенной многокритериальной оптимизации по сравнению с традиционными стратегиями математического программирования:
- Применимость к сложным задачам — возможность решения задач с невыпуклыми, разрывными и стохастическими целевыми функциями и ограничениями;
- Минимальная адаптация модели — не требуется существенной модификации математической модели для решения оптимизационной задачи;
- Экономичность — возможность получения множества Парето-оптимальных решений при относительно небольшом числе обращений к математической модели;
- Глобальность поиска — значительно высокая вероятность нахождения глобального оптимума в многоэкстремальном пространстве проектных переменных.
Именно эти преимущества лежат в основе широкого применения предложенного метода при решении реальных практических задач.
Тестирование метода
В настоящее время единых общепринятых тестов для методов многокритериальной оптимизации не существует. Для оценки эффективности нашего метода было решено большое число оптимизационных задач, в которых в качестве отдельных критериев использовались хорошо известные тестовые функции оптимизации в многокритериальной постановке. При этом было обеспечено условие несовпадения экстремумов отдельных критериев между собой.
В качестве показателей эффективности метода использовались:
- точность нахождения экстремумов отдельных критериев;
- средняя точность по множеству Парето;
- равномерность распределения найденных решений в пространстве критериев.
Полученные результаты подтвердили высокую эффективность нашего метода при решении задач различных типов.
Результаты тестирования
