Последовательные методы приближенного построения множества Парето на основе генетических алгоритмов

В настоящее время в вычислительной практике наиболее часто используются четыре метода приближенного построения множества Парето на основе генетических алгоритмов [0]:

 метод VEGA (Vector Evaluated Genetic Algorithm);

 метод FFGA (Fonseca and Fleming’s Multiobjective Genetic Algorithm);

 метод NPGA (Niched Pareto Genetic Algorithm);

 метод SPEA (Strength Pareto Evolutionary Algorithm).

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

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

В методе NPGA, в отличие от методов VEGA, FFGA, существует механизм поддержания разнообразия популяции. Метод основан на формировании популяционных ниш.

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

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