УДК 519.872

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

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

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

После апробации алгоритма на сложных задачах однокритериальной оптимизации были решены некоторые задачи многокритериальной оптимизации.

Математическая модель задачи многокритериальной оптимизации имеет следующий вид:

y = f ( x ) = ( f₁ ( x ),f ₂ ( x ), ..., f _K ( x)) → opt,

где x = ( x₁ , x₂ , ..., x_N ) ∈ X  –      вектор     решений;

y = ( y₁ , y ₂ , ..., y _K ) ∈ Y – вектор целевых функций; Х – пространство решений; Y – пространство целей, или критериальное пространство.

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

1. Метод VEGA (Vector Evaluated Genetic Algorithm) относится к категории селекции по переключающимся целевым функциям.
2. Метод FFGA (Fonseca and Fleming’s Multiobjective Genetic Algorithm) при назначении пригодности индивидов использует концепцию доминирования по Парето.
3. Метод Аддитивная свертка объединяет все критерии в один, используя линейное соотношение с весовыми коэффициентами.
4. Метод SPEA (Strength Pareto Evolutionary Algorithm) сочетает преимущества многих подходов в одном алгоритме. Так, например, для назначения индивидам скалярного значения пригодности используется концепция Парето доминирования; индивиды, недоминируемые относительно других членов популяции, хранятся внешне в специальном внешнем множестве; для обеспечения разнообразия последующих поколений используется концепция ниширования.

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

Постановка задачи:

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

Алгоритм SPEA показал наилучшие результаты, однако SPEA более сложен в реализации и обладает большим количеством дополнительных настроек. В результате этого незнакомый с генетическими алгоритмами специалист не сможет в полной мере воспользоваться его преимуществом. Если требуется просто получить хотя бы одно недоминируемое относительно других решение, то можно использовать алгоритм аддитивной свертки, который является простым алгоритмом и не требует особых усилий при реализации. Этот метод очень удобно использовать, когда ЛПР четко знает, какой критерий является для него приоритетным и важности всех критериев. Если ЛПР устраивает вариант, когда решение значительно превосходит все остальные по одному из критериев, но уступает по другим, то стоит использовать алгоритм VEGA. Алгоритм FFGA стоит использовать, когда ЛПР необходимо получить некое компромиссное решение.