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

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

. (2)

Основными операциями генетического алгоритма при приближенном построении множества Парето являются операции скрещивания (кроссовера, рекомбинации), мутации, вычисления пригодности индивида и отбора (селекции), из которых специфическими для задачи построения множества Парето являются только две последние операции [0].

Выделяют следующие основные способы селекции в генетических алгоритмах приближенного построения множества Парето:

 селекция по переключающимся частным критериям оптимальности;

 агрегирующая селекция;

 селекция, основанная на понятии Парето-доминирования.

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

 формирование популяционных ниш (подпопуляций);

 ограниченное скрещивание;

 переопределение;

 перезапуск процесса эволюции;

 уплотнение (объединение).

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