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

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

Слайд 1XI Национальная конференция по искусственному интеллекту, КИИ - 08
Оптимизация многоэкстремальных функций

на основе кластерной модификации
генетического алгоритма

КАЗАКОВ
Павел Валерьевич

Брянский государственный технический университет
кафедра «Компьютерные технологии и системы»

канд. техн. наук, доцент


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

ОПТИМИЗАЦИИ

2


Слайд 3ПРИНЦИПЫ КЛАСТЕРНОЙ МОДИФИКАЦИИ ГЕНЕТИЧЕСКОГО АЛГОРИТМА (КГА)
3
Кластер хромосом – множество хромосом
с «похожим»

фенотипом

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

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

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


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

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

4

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


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


Слайд 6СХЕМА РАБОТЫ КГА
6


Слайд 7ВЫЧИСЛИТЕЛЬНЫЕ ОСОБЕННОСТИ КГА
Временная эффективность КГА (Tz) зависит от числа вычислений мер


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

7

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

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

,

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


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

8


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


Слайд 10РЕЗУЛЬТАТ РАБОТЫ ПРОГРАММЫ, РЕАЛИЗУЮЩЕЙ КГА
10


Обратная связь

Если не удалось найти и скачать презентацию, Вы можете заказать его на нашем сайте. Мы постараемся найти нужный Вам материал и отправим по электронной почте. Не стесняйтесь обращаться к нам, если у вас возникли вопросы или пожелания:

Email: Нажмите что бы посмотреть 

Что такое ThePresentation.ru?

Это сайт презентаций, докладов, проектов, шаблонов в формате PowerPoint. Мы помогаем школьникам, студентам, учителям, преподавателям хранить и обмениваться учебными материалами с другими пользователями.


Для правообладателей

Яндекс.Метрика