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

Февраль 20, 2021

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

Содержание

2. ПОДХОДЫ К РАСШИРЕНИЮ ВОЗМОЖНОСТЕЙ СТАНДАРТНОГО ГЕНЕТИЧЕСКОГО АЛГОРИТМА ДЛЯ РЕШЕНИЯ МНОГОЭКСТРЕМАЛЬНЫХ ЗАДАЧ ОПТИМИЗАЦИИ 2
3. ПРИНЦИПЫ КЛАСТЕРНОЙ МОДИФИКАЦИИ ГЕНЕТИЧЕСКОГО АЛГОРИТМА (КГА) 3 Кластер хромосом – множество хромосом с «похожим» фенотипом Степень
4. ПРИНЦИПЫ КЛАСТЕРНОЙ МОДИФИКАЦИИ ГЕНЕТИЧЕСКОГО АЛГОРИТМА (продолжение) Для кластеризации хромосом используется принцип доминирования Пусть Z1, Z2,…,Zk –
5. ОГРАНИЧЕННОСТЬ СТАНДАРТНОГО ГА И ВОЗМОЖНОСТИ КГА ПРИ ЛОКАЛИЗАЦИИ ГРУППЫ ЭКСТРЕМУМОВ 5
6. СХЕМА РАБОТЫ КГА 6
7. ВЫЧИСЛИТЕЛЬНЫЕ ОСОБЕННОСТИ КГА Временная эффективность КГА (Tz) зависит от числа вычислений мер близости при обработке кластеров.
8. ТЕСТОВЫЕ ФУНКЦИИ МНОГОЭКСТРЕМАЛЬНОЙ ОПТИМИЗАЦИИ 8
9. ГРАФИКИ И ПЛОТНОСТИ ИССЛЕДОВАНИЯ ПРОСТРАНСТВА РЕШЕНЙИ КГА ФУНКЦИЙ 9 Функция 1 Функция 2
11. Скачать презентацию

Слайд 2

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

ОПТИМИЗАЦИИ

Слайд 3

ПРИНЦИПЫ КЛАСТЕРНОЙ МОДИФИКАЦИИ ГЕНЕТИЧЕСКОГО АЛГОРИТМА (КГА)

Кластер хромосом – множество хромосом
с «похожим»

фенотипом

Степень «похожести» определяется на
основе вещественной (Евклида), бинарной
(Хемминга) метрики d

Хромосомы Ck принадлежат кластеру
Zi, если d(Ck, Zi) ≤ Rc

Rc ∈ [0, 1] – радиус гиперсферы кластера,
дополнительный управляющий параметр.
Его значение определяет число кластеров

ПРИНЦИПЫ КЛАСТЕРНОЙ МОДИФИКАЦИИ ГЕНЕТИЧЕСКОГО АЛГОРИТМА (КГА) 3 Кластер хромосом –

Слайд 4

ПРИНЦИПЫ КЛАСТЕРНОЙ МОДИФИКАЦИИ ГЕНЕТИЧЕСКОГО АЛГОРИТМА (продолжение)

Для кластеризации хромосом используется принцип доминирования

Пусть

Z1, Z2,…,Zk – k фрагментов популяции Pn, представляющих
собой кластеры. Хромосома C* ∈ Zi доминирует в кластере i, если
∀C’ ∈ Zi : f(C*) ≤ f(C’).

Хромосома C* является центроидом кластера Zi тогда и только тогда,
если ∀C’ ∈ Zi : d(C*, C’) ≤ Rc.

ПРИНЦИПЫ КЛАСТЕРНОЙ МОДИФИКАЦИИ ГЕНЕТИЧЕСКОГО АЛГОРИТМА (продолжение) Для кластеризации хромосом используется

Слайд 5

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

Слайд 6

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

Слайд 7

ВЫЧИСЛИТЕЛЬНЫЕ ОСОБЕННОСТИ КГА

Временная эффективность КГА (Tz) зависит от числа вычислений мер

близости при обработке кластеров.
Расчеты показали, что линейная ≤ O(Tz) ≤ квадратичная и зависит от Rc и Np

Параметр Rc влияет на число
кластеров и определяется
экспериментально. Возможно
аналитическое определение Rc ≥ 2d,
где d – расстояние между двумя наиболее
различными решениями

Критерий определения экстремума в последней популяции:

где f(Zci) – оптимальность i – го центроида кластера;
f (C*) – оптимальность лучшей хромосомы последней популяции;
ε > 0 – параметр, определяющий верхнюю границу «глобального» оптимума.