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

1 XI Национальная конференция по искусственному интеллекту, КИИ - 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