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

• 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