Решение многокритериальных задач

Решение многокритериальных задач.

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

Проблема.

большой размер парето-оптимальной области,
количество недоминируемых (несравнимых) особей в репродукционной группе больше, чем размер популяции

Цель

Построить метод селекции, направленный на равномерное (в евклидовом пространстве параметров) покрытие Парето - оптимальной области нужным количеством недоминируемых особей.

Метод.

1.Использовать параметр - радиус, задаваемый вручную, и очерчивающий окрестность решения, так чтобы "соседи" этого решения, попавшие в эту окрестность, не "выживали" при отборе. Плюсы: простота реализации. Минусы: сложно вычислить такой радиус, чтобы оставить нужное количество особей; радиус будет меняться на каждом поколении.

На рисунке представлен алгоритм выделения точек для равномерного покрытия. Было 16 решений, осталось - 8.

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

Алгоритм

Rmin = минимальное расстояние между любыми двумя точками.
Rmax = максимальное расстояние между любыми двумя точками.
Если Rmax = Rmin, то поиск не имеет смысла - все решения совпадают. Выход.
R = (Rmax + Rmin) : 2.
Посчитать, сколько особей "выживет" с таким R.
Если выживет больше, чем нужно (>n) - сделать Rmax = R. Переход к п.4.
Если выживет меньше, чем нужно (<n) - сделать Rmin = R. Переход к п.4.
Нужное R - найдено.

Замечание. n - размер популяции. Процесс может зациклится, если k решений совпадают и k>n или слишком велика плотность особей в парето-оптимальной области (сложно определить R, поскольку величина колебания R не поддается машинной арифметике). Поэтому нужно предварительно проверить эти условия.

Тестовые задачи

Задача ╪1.

Размерность = 1.
f₁(x) = -x² -> max f₂(x) = -(x-2)² -> max -6 <= x <= 6

На рисунке показано распределение 20 особей после 200 оценок целевых функций
Горизонтальная ось - x,
Вертикальная ось - f(x)

Задача ╪2.

Размерность = 2.
f₁(x, y) = -1/(x²+y²+1) -> max f₂(x, y) = -(x²+3y²+1) -> max -3 <= x, y <= 3

На рисунке показано распределение 500 особей после 2000 оценок целевых функций
Горизонтальная ось - x,
Вертикальная ось - y

Задача ╪3.

Размерность = 2.
f₁(x, y) = -(x+y+1) -> max f₂(x, y) = -(x²+2y-1) -> max -3 <= x, y <= 3

На рисунке показано распределение 200 особей после 2000 оценок целевых функций
Горизонтальная ось - x,
Вертикальная ось - y

К началу документа

Исаев Сергей e-mail: sergey.isaev @ mailcity.com web: http://www.chat.ru/~saisa