'

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

Понравилась презентация – покажи это...





Слайд 0

XI Национальная конференция по искусственному интеллекту, КИИ - 08 Оптимизация многоэкстремальных функций на основе кластерной модификации генетического алгоритма КАЗАКОВ Павел Валерьевич Брянский государственный технический университет кафедра «Компьютерные технологии и системы» канд. техн. наук, доцент


Слайд 1

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


Слайд 2

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


Слайд 3

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


Слайд 4

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


Слайд 5

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


Слайд 6

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


Слайд 7

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


Слайд 8

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


Слайд 9

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


×

HTML:





Ссылка: