Возможности векторного генетического алгоритма для решения многокритериальных задач оптимизации

Размещено на http://www.allbest.ru/

Возможности векторного генетического алгоритма для решения многокритериальных задач оптимизации

Казаков П.В.

Задачи многокритериальной оптимизации (МО) являются достаточно распространенными для прикладных областей, где требуется найти решение лучшее сразу по более, чем одному критерию. Такие критерии часто конфликтуют между собой, то есть попытка оптимизации отдельного критерия приводит к ухудшению качества решения по остальным. Использование для решения данного класса задач традиционных методов, которые варьируются от сведения многокритериальной задачи к однокритериальной до активного привлечения человека к выбору оптимальных решений, не всегда возможно или ограничено. Это связано со сложностью оптимизируемой математической модели задачи, неравномерностью и многомерностью пространства поиска, наличием ограничений, смешанных разношкальных параметров, а также различных форм описания критериев.

В то же время возможность создания многокритериальных математических моделей принятия решений практически любой сложности, с одной стороны, существенно расширяет границы их исследования, с другой - предъявляет повышенные требования к методам их оптимизации. Поэтому важным является поиск, разработка и исследование новых методов, независимых от отмеченных особенностей математической модели и позволяющих эффективно находить оптимальные решения. Перспективным здесь видится применение эволюционных методов научного направления «искусственный интеллект» [1], обладающих указанными свойствами.

ПОСТАНОВКА ЗАДАЧИ МНОГОКРИТЕРИАЛЬНОЙ ОПТИМИЗАЦИИ

В общем случае задача многокритериальной оптимизации включает n оптимизируемых переменных, m критериев оптимальности и k ограничений. Математически постановка задачи МО может быть представлена следующим образом [2]: многокритериальный оператор селекция турнирный

;

;

;

;

.

Множество X здесь обозначает пространство решений, имеющее произвольную форму, непрерывную, дискретную, смешанную, Y - пространство критериев, F - обобщенный векторный критерий.

При выполнении соответствующих ограничений данные пространства сужаются, образуя множества и (рис. 1).

Рисунок 1 - Отображение множеств возможных решений и критериев

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

Решение x' доминирует x'' (), если

,

где знак означает качественную оценку важности, основанную на суждении, что x' лучше (доминирует) x''.

Согласно второму принципу точка x* называется оптимальной по Парето (эффективной, не улучшаемой), если . Множество эффективных точек образует область или множество Парето , которое в общем случае может:

- состоять из одного решения;

- содержать некоторое конечное число решений;

- состоять из бесконечного числа решений.

Множество значений критериев на XP образует так называемую компромиссную кривую YP (m=2) или поверхность (m>2), .

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

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

ВЕКТОРНЫЙ ГЕНЕТИЧЕСКИЙ АЛГОРИТМ

Генетический алгоритм благодаря надежности, независимости от математической модели задачи, а также возможности эффективной компьютерной реализации является наиболее распространенным из «нетрадиционных» средств оптимизации. Эффект параллелизма, свойственный ГА, наделяет их высоким потенциалом к поиску оптимальных по Парето решений в рамках одного запуска алгоритма. Существует несколько оригинальных модификаций ГА для решения задач МО, которые отличаются сложностью реализации, набором допустимых задач, а также качеством и временем поиска множества Парето. Одной из первых разработанных таких модификаций является векторный генетический алгоритм (Vector Evaluated Genetic Algorithm - VEGA), предложенный Шафером (J. D. Schaffer) [4]. В VEGA изменения выполнения генетических операторов стандартного ГА связаны с привлечением в процедуру селекции различных схем ранжирования решений в зависимости от их оптимальности по отдельным критериям. В этом алгоритме пропорциональный отбор применяется к выделенным из основной популяции m подпопуляциям размером Np/m. При этом оптимальность хромосомы j оценивается в соответствии с i-м критерием. Далее все подпопуляции перемешиваются для получения новой популяции исходного размера и к ней впоследствии применяются стандартные генетические операторы (рис. 2).

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

Рисунок 2 - Схема оператора отбора векторного ГА

Для устранения указанного недостатка предлагается использовать в операторе селекции турнирной схемы в сочетании со случайным выбором критерия для сравнения. Также может использоваться и случайный набор группы критериев. В этом случае используется лексикографический принцип: «победителем» оказывается то решение, которое лучше по наиболее предпочтительным критериям. Ниже представлен псевдокод модифицированной версии оператора селекции VEGA(m).

Ns =

Foreach (C Np)

{

Cx = k, k = random();

Choose fi, i=1..k, i = random();

Choose Cj, j = random(), C Cj;

Foreach (i)

If (fi(C) > fi(Cj))

Cx = Cx -1;

If (Cx > (k div 2))

Ns = Ns {C}

Else Ns = Ns {Cj}

}

В новом варианте схемы отбора формируется репродукционная группа Ns по следующим правилам. Для каждой хромосомы C текущей популяции случайно определяется множество из k критериев. Далее они используются для сравнения заданной хромосомы со случайно выбранной Cj. Хромосома, лучшая по большинству критериев, объявляется «победителем» и копируется в репродукционную группу. Затем популяция перемешивается, и к ней применяются остальные генетические операторы.

ЭКСПЕРИМЕНТАЛЬНЫЕ РЕЗУЛЬТАТЫ

Сравнительная эффективность векторных генетических алгоритмов VEGA и VEGA(m) определялась на основе оптимизации двух тестовых функций следующего вида [3]:

Для всех запусков генетических алгоритмов использовались следующие значения управляющих параметров: число поколений (250), размер популяции (Np = 100), вероятность кроссинговера (0,9), вероятность мутации (0,01/бит). Для каждой функции генетические алгоритмы запускались по пять раз и анализировалось соотношение найденных оптимальных решений. Для их определения к последней популяции применялись соответствующие принципы доминирования и оптимальности Парето. Анализ решений показал, что они в различной степени для каждого ГА аппроксимируют компромиссную кривую (рис. 3).

Рисунок 3 - Результаты работы векторных ГА

На рис. 3 показаны пространства критериев для обеих функций. Прямоугольниками и ромбиками показаны найденные ГА точки множества Парето. Видно, что результат работы VEGA(m) есть более равномерное заполнение компромиссной кривой, в то время как VEGA более плотно заполнил ее крайние участки. Варьирование значений вероятностей управляющих параметров не давало принципиальных улучшений качества поиска по сравнению с изначально заданными. Однако эксперименты с размером популяции обнаружили его влияние как на результат, так и на время его получения. В целом, относительное увеличение популяции (Np < 500) для рассматриваемых задач сохраняло преимущество первого в соотношении качество/время поиска.

Заключение

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

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

Литература

1. Казаков, П.В. Основы искусственного интеллекта [Текст]: учеб. пособие для вузов / П.В. Казаков, В.А. Шкаберин. - Брянск: БГТУ, 2007. - 196с.

2. Соболь, И.М. Выбор оптимальных параметров в задачах со многими критериями [Текст] / Соболь И.М, Статников Р.Б. - 2-е изд., перераб. и доп. - М.: Дрофа, 2006. - 175 с.

3. Deb, K. Multi-objective Genetic Algorithms: Problem Difficulties and Construction of Test Problems [Text] / K. Deb. - MIT Press. Evolutionary Computation,1999. - №7(3). - p. 205-230.

4. Schaffer, J.D. Multiple objective optimization with vector evaluated genetic algorithms [Text] / J.D. Schaffer // In Genetic Algorithms and their Applications Proceedings of the First International Conference on Genetic Algorithms. - Lawrence Erlbaum, 1995. - p. 93-100

Размещено на Allbest.ru