Главная страница


ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Yuri Burger                          2:468/85.3     20 May 2001  17:45:53
 To : All
 Subject : GA FAQ: 5/5
 -------------------------------------------------------------------------------- 
 
 
                                                  Kрюгер.
 [ю]ДДДДДДДД Begin 5 ДДДДДДД
 
 >1.15 В приведенном сырце ПГА не ясна роль "неэлитных" особей.
 >Yuri Burger [2:468/85.3]
 
     Честно  говоря,  этот  вопрос меня самого поставил в тупик. Прикинул так и
 этак - выходит что не нужны они.. Однако нельзя торопиться с выводами.
      Вопервых,   многое  зависит от процедуры добавления особей в популяцию. В
 зависимости от неё, неэлитные особи могут терять и преобретать значимость.
      И  есть еще одно применение им. Если функция оценки особей (фитнес) будет
 давольно  медленной,  то  эти  особи можно использовать в качестве кэша. Всилу
 особенностей  работы ГА, будет весьма высокая вероятность появления решений из
 окресности текущего оптимума, а значит можно ожидать повторения особей.
 ******************************************************************************
 
 >1.16 Что такое инбридинг, оутбридинг, селективный выбор, панмиксия?
 >(источник не известен)
 
      Существует  несколько  подходов  к  выбору  родительской  пары.  Hаиболее
 простой   из  них  -  панмиксия.  Этот  подход  предполагает  случайный  выбор
 родительской  пары,  когда  обе  особи,  которые  составят  родительскую пару,
 случайным  образом  выбираются  из  всей  популяции. В этом случае любая особь
 может  стать  членом  нескольких  пар.  Hесмотря  на  простоту,  такой  подход
 универсален для решения различных классов задач. Однако он достаточно критичен
 к численности популяции, поскольку эффективность алгоритма, реализующего такой
 подход, снижается с ростом численности популяции.
      Селективный  способ  выбора особей в родительскую пару состоит в том, что
 "родителями"  могут  стать только те особи, значение приспособленности которых
 не  меньше  среднего  значения  приспособленности  по  популяции,  при  равной
 вероятности таких кандидатов составить брачную пару.
      Такой  подход  обеспечивает  более  быструю  сходимость алгоритма. Однако
 из-за  быстрой  сходимости  селективный  выбор  родительской  пары не подходит
 тогда,  когда  ставиться  задача определения нескольких экстремумов, поскольку
 для  таких  задач  алгоритм, как правило, быстро сходится к одному из решений.
 Кроме    того,   для   некоторого   класса   задач   со   сложным   ландшафтом
 приспособленности  быстрая  сходимость  может  превратиться  в преждевременную
 сходимость  к  квазиоптимальному  решению.  Этот недостаток может быть отчасти
 компенсирован   использованием   подходящего   механизма  отбора,  который  бы
 "тормозил" слишком быструю сходимость алгоритма.
      Инбридинг   представляет  собой  такой  метод,  когда  первый  член  пары
 выбирается случайно, а вторым с большей вероятностью будет максимально близкая
 к нему особь.
      Пример  определения  родства  хромосом  при  выборе родительской пары для
 хромосомы 1010001:
             Хромосомы популяции         Количество отличающихся локусов
                  1000000                              2
                  1010101                              1
                  0011100                              4
                  0000001                              2
                  0110011                              3
                  0100011                              4
                  1111111                              4
                  0000000                              3
      При  аутбридинге  также используют понятие схожести особей. Однако теперь
 брачные пары формируют из максимально далеких особей.
      Последние   два  способа  поразному  влияют  на  поведение  генетического
 алгоритма.  Так инбридинг можно охарактеризовать свойством концентрации поиска
 в  локальных узлах, что фактически приводит к разбиению популяции на отдельные
 локальные  группы  вокруг  подозрительных  на  экстремум  участков  ландшафта.
 Аутбридинг же направлен на предупреждение сходимости алгоритма к уже найденным
 решениям, заставляя алгоритм просматривать новые, неисследованные области.
 ******************************************************************************
 
 >2.1 Что такое нечеткое множество, нечеткая и лингвистическая переменная?
 >Yuri Burger [2:468/85.3]
 
      Hечеткое  множество  -  это  множество  пар  <m(x)/x>,  где  x  принимает
 некоторое  информативное  значение,  а  m(x) отображает x в единичный отрезок,
 принимая  значения  от  0  до  1.  При  этом  m(x)  представляет собой степень
 принадлежности  x  к  чему-либо  (0  -  не принадлежит, 1 - принадлежит на все
 100%).
      Так, на пример, можно задать для числа 7 множество:
                          <0/1>,<0.4/3>,<1/7>
      Это  множество  говорит о том, что 7 - это на 0% единица, на 40% тройка и
 на 100% семерка.
 
      Hечеткая переменная определяется как <A,X,Ca>.
      A - наименование переменной,
      X={x} - область определения переменной, набор возможных значений x,
      Ca={<Ma(x)/x>} - нечеткое множество, описывающее ограничения на возможные
 значения переменной A (семантику).
      Пример:    <"Семь",{1,3,7},{<0/1>,<0.4/3>,<1/7>}>.    Этой   записью   мы
 определили  соответствия  между  словом  и  некоторыми  цифрами. Причем, как в
 названии переменной, так и в значениях x можно было использовать любые записи,
 несущие какую-либо информацию.
 
      Лингвистическая переменная определяется как <B,T,X,G,M>.
      B - наименование переменной.
      T   -   множество   её  значений  (базовое  терм-множество),  состоит  из
 наименований  нечетких  переменных,  областью  определения  каждой  из которых
 является множество X.
      G   -  синтаксическая  процедура  (грамматика),  позволяющая  оперировать
 элементами  терм-множества  T,  в  частности  - генерировать новые осмысленные
 термы. T`=T U G(T) задает расширенное терм-множество (U - знак объединения).
      M   -  семантическая  процедура,  позволяющая  приписать  каждому  новому
 значению  лингвистической  переменной  нечеткую  семантику, путем формирования
 нового нечеткого множества.
 ******************************************************************************.
 [ю]ДДДДДДДД End 5   ДДДДДДД
 
 ---
  * Origin: А хто тут есть, у кого есть за что поесть? (2:468/85.3)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

 Тема:    Автор:    Дата:  
 GA FAQ: 5/5   Yuri Burger   20 May 2001 17:45:53 
Архивное /ru.algorithms/23173b0802f9.html, оценка 2 из 5, голосов 10
Яндекс.Метрика
Valid HTML 4.01 Transitional