Многокритериальная оптимизация с использованием генетических алгоритмов : Введение
Abdullah Konak, David W. Coit, Alice E. Smith
Содержание
1. Аннотация
2. Введение
3. Разработка многокритериальной оптимизации
4. Генетические алгоритмы

Аннотация

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

Введение

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

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

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

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

Рассмотрим заказчика, которые желает оптимизировать К не соизмеримых друг с другом целей, и при этом нет четких предпочтений критериев относительно друг друга. Без потери общности, тип всех целей – минимизация. Любую задачу минимизации можно развернуть в сторону максимизации поменяв знак. Решение проблемы многоцелевой минимизации по К критериям определяется следующим образом: дан n-мерный вектор решений x = {x1, x2,…,xn} в пространстве решений Х, найти вектор х' который минимизирует данный набор из К целевых функций z(x') = {z1(x'),…zk(x')}. Пространство решений Х в целом ограничено серией правил, таких как gj(x') = bj при j=1,…,m.

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

Если все целевые функции необходимо минимизировать, возможное решение х доминирует над другим возможным решением у (х>y), если и только когда zi(x)?zi(y) для i=1…K и zj(x) < zj(y) для хотя бы одной целевой функции j. Решение называется оптимальным по Парето если оно не доминируемо ни одним другим решением из области решений. Оптимальное по Парето решение не может быть улучшено по отношению к любой целевой функции без ухудшения по отношению к другой. Набор всех возможных не-доминируемых решений в области Х называется оптимальным набором по Парето, и для данного Парето оптимального набора соответствующие значения целевой функции лежат в области, называемой фронт Парето. Для многих проблем, количество Парето оптимальных решений огромно (возможно бесконечно).

Главной целью алгоритма многокритериальной оптимизации является определить решения в Парето оптимальном наборе. Однако, определение решения в целом Парето оптимальном наборе для многих многоцелевых задач практически невозможно в связи с его размером. В дополнение к многим проблема, особенно для комбинаторной оптимизации, доказательство оптимальности решения вычислительно невозможно. Следовательно, практический подход к многокритериальной оптимизации заключается в изучении множества решений (лучшего Парето набора), которые представляют собой Парето оптимальный набор как можно лучше. Ввиду этих проблем, многоцелевой подход к оптимизации должен достичь следующих трех противоречивых целей: 1. Лучший известный фронт Парето должен быть как можно ближе к настоящему фронту Парето. В идеале, лучший из известных набор Парето должен является поднабором оптимального по Парето множества решений.

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

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

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

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

Концепция генетических алгоритмов была разработана Холландом и его коллегами в 1960х и 1970х годах. Генетические алгоритмы берут начало в теории эволюции, объясняющей происхождение видов. В природе, слабые и неприспособленные для своего окружения особи сталкиваются с проблемой вымирания из-за естественного отбора. Сильные же имеют большие возможности для передачи своих генов будущим поколениям с помощью репродукции. На длительном отрезке времени, особи, несущие в себе правильные комбинации генов становятся доминирующими в своей популяции. Иногда, во время неспешного процесса эволюции происходят случайные изменения в генах. Если эти изменения предоставляют дополнительные преимущества в гонке за выживание, новые виды развиваются из старых. Неудачные изменения уничтожаются естественным отбором.

В терминологии ГА, вектор решений х є Х называется особью или хромосомой. Хромосомы составлены из дискретных элементов называемых генами. Каждый ген контролирует одно или более свойств хромосомы. В оригинальной трактовке ГА Холландом, гены было принято считать бинарными цифрами. В дальнейших трактовках были представлены более разнообразные виды генов. Обычно, хромосома соответствует уникальному решению х в пространстве решений. Это предполагает наличие механизма преобразования между пространством решений и хромосомами. Преобразование называется кодированием. Фактически, ГА работает с кодированием проблемы, а не с самой проблемой.

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

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

Оператор мутации представляет собой случайные изменения характеристик хромосом. Обычно мутация применяется на уровне генов. В типовых трактовках ГА, показатель мутации (вероятность изменения характеристик гена) очень мала и зависит от длины хромосомы. Следовательно, появившаяся в связи с мутацией новая хромосома не будет сильно отличатся от оригинальной. Мутация играет критическую роль в ГА. Как обсуждалось ранее, кроссовер приводит к схождению делая хромосомы внутри популяции похожими. Мутация возвращает генетическое разнообразие в популяцию и помогает поиску выйти из локального оптимума. Репродукция включает в себя селекцию хромосом для следующего поколения. В самом общем случае, приспособленность особи определяет вероятность ее выживания в следующем поколении. Существует три разных процедуры селекции в ГА, в зависимости от того, как используются показатели приспособленности - пропорциональная селекция, ранжирование и турнирная селекция.

Наверх
Вернуться назад