Оптимизация многоэкстремальных функций на основе кластерной модификации генетического алгоритма

ПОДХОДЫ К РАСШИРЕНИЮ ВОЗМОЖНОСТЕЙ СТАНДАРТНОГО ГЕНЕТИЧЕСКОГО АЛГОРИТМА ДЛЯ РЕШЕНИЯ МНОГОЭКСТРЕМАЛЬНЫХ ЗАДАЧ ОПТИМИЗАЦИИ
2

ПРИНЦИПЫ КЛАСТЕРНОЙ МОДИФИКАЦИИ ГЕНЕТИЧЕСКОГО АЛГОРИТМА (КГА)
3
Кластер хромосом – множество хромосом
с «похожим» фенотипом
Степень «похожести» определяется на
основе вещественной (Евклида), бинарной
(Хемминга) метрики d
Хромосомы Ck принадлежат кластеру
Zi, если d(Ck, Zi) ≤ Rc
Rc ∈ [0, 1] – радиус гиперсферы кластера,
дополнительный управляющий параметр.
Его значение определяет число кластеров

ПРИНЦИПЫ КЛАСТЕРНОЙ МОДИФИКАЦИИ ГЕНЕТИЧЕСКОГО АЛГОРИТМА (продолжение)
Для кластеризации хромосом используется принцип доминирования
Пусть Z1, Z2,…,Zk – k фрагментов популяции Pn, представляющих
собой кластеры. Хромосома C* ∈ Zi доминирует в кластере i, если
∀C’ ∈ Zi : f(C*) ≤ f(C’).
4
Хромосома C* является центроидом кластера Zi тогда и только тогда,
если ∀C’ ∈ Zi : d(C*, C’) ≤ Rc.

ОГРАНИЧЕННОСТЬ СТАНДАРТНОГО ГА
И ВОЗМОЖНОСТИ КГА ПРИ ЛОКАЛИЗАЦИИ
ГРУППЫ ЭКСТРЕМУМОВ
5

СХЕМА РАБОТЫ КГА
6

ВЫЧИСЛИТЕЛЬНЫЕ ОСОБЕННОСТИ КГА
Временная эффективность КГА (Tz) зависит от числа вычислений мер
близости при обработке кластеров.
Расчеты показали, что линейная ≤ O(Tz) ≤ квадратичная и зависит от Rc и Np
7
Параметр Rc влияет на число
кластеров и определяется
экспериментально. Возможно
аналитическое определение Rc ≥ 2d,
где d – расстояние между двумя наиболее
различными решениями
Критерий определения экстремума в последней популяции:
,
где f(Zci) – оптимальность i – го центроида кластера;
f (C*) – оптимальность лучшей хромосомы последней популяции;
ε > 0 – параметр, определяющий верхнюю границу «глобального» оптимума.

ТЕСТОВЫЕ ФУНКЦИИ
МНОГОЭКСТРЕМАЛЬНОЙ ОПТИМИЗАЦИИ
8

ГРАФИКИ И ПЛОТНОСТИ ИССЛЕДОВАНИЯ ПРОСТРАНСТВА РЕШЕНЙИ КГА ФУНКЦИЙ
9
Функция 1
Функция 2