Используемые в работе методы и алгоритмы приближенного построения множества Парето
В работе в качестве базового метода выбран последовательный метод NPGA. Это объясняется теми обстоятельствами, что метод NPGA существенно более прост в реализации, чем метод SPEA, и, в то же время, обеспечивает достаточно высокую эффективность [0]. Использована модификация метода, предложенная в работе [0] и заключающаяся в следующем:
использование аутбридинга (дальнеродственного скрещивания) вместо турнирной селекции [0];
использование метода ранжирования индивидов из метода FFGA;
использование операции клонирования.
Пусть 
- текущая популяция, 
- промежуточная популяция, 
- сравнительное множество, 
- заданный радиус популяционной ниши, 
- заданное количество индивидов в сравнительном множестве (давление доминирования), 
- расстояние между индивидами 
популяции в некоторой метрике.
Схему вычисления пригодности индивида и селекции в методе NPGA можно представить в следующем виде [0].
Шаг 1. Положим 
, 
Ø, 
Ø.
Шаг 2. Из 
случайно выбранных индивидов популяции формируем сравнительное множество 
.
Шаг 3. Из оставшейся части популяции случайно выбираем два индивида .
Шаг 4. Если 
недоминируем ни одним из векторов 
, 
, а 
доминируется хотя бы одним вектором сравнительного множества 
, то победителем турнира считаем индивида 
: 
.
Шаг 5. Если недоминируем ни одним из векторов , , а доминируется хотя бы одним вектором сравнительного множества , то победителем турнира считаем индивида 
: 
.
Шаг 6. Если победитель турнира не определен, то выполняем следующие действия.
а) Вычисляем количество индивидов в промежуточной популяции , которые находятся от индивида на расстоянии, не превышающем радиус ниши :
. (3)
б) Аналогично вычисляем количество индивидов 
в промежуточной популяции , которые находятся от индивида на расстоянии, не превышающем радиус ниши .
в) Если 
, то полагаем . Иначе - .
Шаг 7. Полагаем 
. Если 
, то переходим к шагу 3, иначе – заканчиваем вычисления.
Далее по общей схеме генетического алгоритма выполняется скрещивание индивидов промежуточной популяции и формируется популяция 
. Затем реализуется мутация индивидов популяции , на основе которой получается популяция 
.
Как отмечалось выше, вместо рассмотренной турнирной селекции мы используем ранжирование индивидов на основе Парето-доминирования [0]. По определению ранга, индивиду, для которого ни один из индивидов текущей популяции не лучше него по всем частным критериям оптимальности, присваивается ранг 1. Ранг остальных индивидов определяется по формуле
,
где 
- количество индивидов текущей популяции, лучших по всем частным критериям оптимальности.
Используемые механизмы формирования индивидов обеспечивают выполнение условия 
, но не обеспечивают, в общем случае, выполнение условия
. (4)
Ранг индивидов, которые нарушают ограничение (4) назначается в зависимости от того, в какой мере эти ограничения нарушены. Ранг любого из индивидов из числа тех, для которых ограничение (4) нарушено, выше ранга любого из индивидов, для которых это ограничение выполнено.
Функция пригодности строится на основе функции
, (5)
где 
- число индивидов ранга k. Точнее говоря, в качестве функции пригодности используется функция
, (6)
где 
- нишевое число индивида 
, вычисляемое по формуле
. (7)
Здесь 
- функция разделения:
(8)
В системе PRADIS//FRONT индивиды для скрещивания (индивиды-родители) выбираются по следующему правилу. Первый индивид выбирается случайно (из промежуточной популяции ) вне зависимости от значения его функции пригодности. Второй индивид выбирается из той же популяции на некотором расстоянии от данного индивида (исходя из принципов поддержания разнообразия популяции). В случае если нельзя найти второго индивида на указанном расстоянии, в качестве этого индивида из множества выбирается случайный индивид.
Важнейшим оператором в любом генетическом алгоритме является оператор скрещивания. Существует множество разновидностей этого оператора: одноточечный, двухточечный, равномерный и пр. [0]. В системе PRADIS//FRONT скрещивание выполняется по следующему правилу: выбирается ведущий родитель; к значениям его генов прибавляется разность между соответствующими генами родителей, умноженная на коэффициент скрещивания (CrossoverRate); индивид, полученный в результате скрещивания, записывается во множество .
Известно множество операторов мутации индивидов, отличающихся количеством индивидов, подверженных мутации, алгоритмами мутации, количеством генов, участвующих в мутации, и пр. [0]. В системе PARET//FRONT используется оператор мутации, основанный на стандартном операторе, но со следующими отличиями.
Чтобы усилить эффект от выбранного правила скрещивания, все произведенное потомство подвергается мутации в одном гене хромосомы.
Ген модифицируется с помощью стохастического параметра и параметра мутации – MutationRate.
Нами была сделана попытка использовать также классическую схему оператора мутации – инвертирование заданного количества битов в хромосоме. Однако тестирование показало, что такая схема обеспечивает существенно худшие результаты, чем схема, рассмотренная выше.
Распараллеливание вычислений в работе реализовано по схеме алгоритма GPGA. Основания для такого выбора следующие.
1) Ориентация работы на распределенные вычислительные системы. В результате из рассмотрения исключаются алгоритмы, ориентированные на SIMD-системы, а также алгоритмы, требующие большого количества коммуникаций между процессорами.
2) Высокая вычислительная сложность функции пригодности индивидов, обусловленная тем, что каждое вычисление такой функции требует интегрирования соответствующей системы обыкновенных дифференциальных уравнений и вычисления значений всех частных критериев оптимальности.
3) Простота реализации модели параллельных вычислений master-slave.
Для балансировки загрузки процессоров используется равномерная статическая балансировка [0], при которой каждый slave-процессоров обрабатывает одинаковое количество индивидов, назначаемых ему host-процессором.