Материал: 2488

Классификация выполнима, только если I I 0 I I 0 и ЛПР должен классифицировать все целевые функции.

Метод STOM основан на концепции, аналогичной подходу опорной точки,нососредоточеннанахожденииудовлетворительных решений.

У ЛПР запрашивают информацию для отнесения целевых функций к одному из трёх классов: 1) значения целевых функций должны улучшиться I ; 2) значения целевых функций могут быть ослаблены

Нагрузка (количество информации) на ЛПР должна быть уменьшена.

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

Полученные решения Парето оптимальны.

Процесс решений может быть начат с запроса ЛПР определения опорной точки; затем ЛПР запрашивают классифицировать целевые

функции и определить уровни функций I ,I ,I . Процесс решений продолжается, пока ЛПР не будет улучшать/ухудшать значения целевой функции.

STEM (step method) интерактивный метод, позволяющий ЛПР искать желательное решение. Метод основан на -норме и обеспечивает процедуру, последовательно редуцирующую область поиска. STEM использует базовую минимаксную модель для отыскания эффективногорешения: min d ; j fj x fj* d , j 1,...,k, x 0 .

При использовании STEM для линейных задач

i

i 1

156

k

ны быть нормализованы: j 1; 0 j 1.

j 1

Если ЛПР удовлетворен оптимальным решением, оно может использоваться как лучшее компромиссное решение. Иначе ЛПР должен оценить результаты, провести анализ компромиссных решений среди целевых функций и определить направление поиска.

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

Интерактивный процесс включает две стадии: извлечение привилегированной информации и формирование эффективного решения. Новые ограничения добавляются к первоначальному пространству решений. Решение обновленной задачи приведет к новому эффективному решению.

Предположим, что целевая функция fl x может быть изменена от текущего значения fl xi на fl xi , в то время как все другие целевые функции должны быть сохранены. Тогда новая однокритериальная задача оптимизации может быть сформулирована следующим образом:

дет к новому эффективному решению.

GAs (GA) имеют три основных направления: исследование в области генетических алгоритмов, оптимизация с использованием генетических алгоритмов и обучение с классифицирующими системами.

GAs появились в результате моделирования процессов, наблюдаемых при эволюции природы (например, биологические процессы). Эволюция отражается на хромосомах устройствах кодирования структур живых существ. Используются следующие особенности теории эволюции: эволюционные процессы воздействует на хромосомы, которые кодируются; процессы естественного отбора формируют

157

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

Джон Холланд полагал, что GAs могут привести к методике решения проблемы при формировании соответствующего компьютерного алгоритма. Он начал исследование алгоритмов, которые манипулировали строками двоичных цифр, представляющих хромосомы. Алгоритмы Холланда моделировали эволюцию на популяции таких хромосом. Используя механизмы кодирования и репродукции, алгоритмы решали трудные задачи. В настоящее время GAs стохастические глобальные методы поиска, подражающие естественной биологической эволюции. Применяя правило выживания, наиболее пригодного для формирования лучшего приближения к решению, GAs оперируют на популяции потенциальных решений. Новое множество приближений в каждом поколении формируется в процессе селекции хромосом, согласно их уровню приспособленности к проблемной области, и размножению с использованием операций, заимствованных от генетики (скрещивание и мутация).

Рассмотрим два механизма, связывающие GAs с задачами, которые они решают: кодирование хромосомами решений задачи и возвращение меры ценности любой хромосомы в контексте задачи. Функция эволюции – звено между генетическим алгоритмом и решаемой задачей. Функция эволюции имеет хромосому (как вход) и возвращает список чисел, который является мерой характеристик хромосомы.

Предполагается, что заданы следующие начальные данные: задача, механизм кодирования решений и функция, которая измеряет, насколько подходит кодирование. Базовая структура GAs: инициализация популяции хромосом; эволюция каждой хромосомы в популяции; создание новых хромосом скрещиванием текущих хромосом; удаление некоторых элементов популяции для создания пространства для новых хромосом; внесение новых хромосом в популяцию; получение лучшей хромосомы и переход к скрещиванию.

Отличие Gas от традиционных методов оптимизации: GAs ищут на популяции точек, а не на одной точке; GAs не запрашивают вспомогательную информацию о целевой функции; GAs используют веро-

158

ятностные правила перехода; GAs могут работать на различных кодированиях множества параметров.

Многокритериальная оптимизация с GAs. Множественные ха-

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

Оптимизация с ограничениями. Учет ограничений в GAs зада-

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

Оптимизация не по Парето. Шаффер указал на необходимость рассмотрения вектора аппроксимирующих решений POF (ParetoOptimal Front). Более ранние алгоритмы пыталась найти только одну Парето оптимальную точку. VEGA (vector evaluated genetic algorithm)

выбирает различные части популяции, основан на различных критериях. В каждом поколении популяция разделена на M групп, каждая группа соответствует своему критерию и селекция применяется к каждой группе отдельно. Результирующие группы рекомбинируются для формирования исходной популяции и применяется скрещивание, как в стандартных GA. Таким образом, индивидуумы выбираются только для одной цели, но, возможно, следующее поколение будет создано от родителей с различными целями. Поскольку селекция основана на индивидуальных целях, VEGA выбирает индивидуумы из «крайних» POF они выступают хорошо для одной цели, они не-

159

удовлетворительны для других. Курсаве использовал «лексическое упорядочение» индивидуумов для отбора в эволюционных алгоритмах. При лексическом упорядочении популяция упорядочена каждым критерием по порядку «важности».

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

Взаимозависимость критериев

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

ценность MCDM (multiple criteria decision making – многокритериаль-

ное принятие решений): 1) нехватка времени сокращает количество учитываемых критериев; 2) чем более полное и точное определение задачи, тем меньше необходимо критериев; 3) автономные ЛПР должны использовать больше критериев, чем ЛПР, которыми управляет иерархическая система ПР; 4) изоляция от возмущений окружения редуцирует потребность во множественных критериях.

Определим взаимозависимости между целями в терминах множе-

ственных целей. Рассмотрим следующую задачу: max f1 x ,...,fk x ,

x X

где fi x целевые функции; x – вектор решений.

Пусть fi x , fj x целевые функции. Будем считать, что:

160