ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Yuri Burger                          2:468/85.3     18 Jul 2001  22:32:40
 To : All
 Subject : Mild.Faq: 5/9
 -------------------------------------------------------------------------------- 
 

 
 
 [ю]ДДДДДДДД Begin 5 ДДДДДДД
 
 >1.14 В приведенном сырце ПГА не ясна роль "неэлитных" особей.
 >Yuri Burger [2:468/85.3]
 
     Честно  говоря,  этот  вопрос меня самого поставил в тупик. Прикинул так и
 этак - выходит что не нужны они.. Однако нельзя торопиться с выводами.
      Вопервых,   многое  зависит от процедуры добавления особей в популяцию. В
 зависимости от неё, неэлитные особи могут терять и преобретать значимость.
      И  есть еще одно применение им. Если функция оценки особей (фитнес) будет
 давольно  медленной,  то  эти  особи можно использовать в качестве кэша. Всилу
 особенностей  работы ГА, будет весьма высокая вероятность появления решений из
 окресности текущего оптимума, а значит можно ожидать повторения особей.
 ******************************************************************************
 
 >1.15 Что такое инбридинг, оутбридинг, селективный выбор, панмиксия?
 >(источник не известен)
 
      Существует  несколько  подходов  к  выбору  родительской  пары.  Hаиболее
 простой   из  них  -  панмиксия.  Этот  подход  предполагает  случайный  выбор
 родительской  пары,  когда  обе  особи,  которые  составят  родительскую пару,
 случайным  образом  выбираются  из  всей  популяции. В этом случае любая особь
 может  стать  членом  нескольких  пар.  Hесмотря  на  простоту,  такой  подход
 универсален для решения различных классов задач. Однако он достаточно критичен
 к численности популяции, поскольку эффективность алгоритма, реализующего такой
 подход, снижается с ростом численности популяции.
      Селективный  способ  выбора особей в родительскую пару состоит в том, что
 "родителями"  могут  стать только те особи, значение приспособленности которых
 не  меньше  среднего  значения  приспособленности  по  популяции,  при  равной
 вероятности таких кандидатов составить брачную пару.
      Такой  подход  обеспечивает  более  быструю  сходимость алгоритма. Однако
 из-за  быстрой  сходимости  селективный  выбор  родительской  пары не подходит
 тогда,  когда  ставиться  задача определения нескольких экстремумов, поскольку
 для  таких  задач  алгоритм, как правило, быстро сходится к одному из решений.
 Кроме    того,   для   некоторого   класса   задач   со   сложным   ландшафтом
 приспособленности  быстрая  сходимость  может  превратиться  в преждевременную
 сходимость  к  квазиоптимальному  решению.  Этот недостаток может быть отчасти
 компенсирован   использованием   подходящего   механизма  отбора,  который  бы
 "тормозил" слишком быструю сходимость алгоритма.
      Инбридинг   представляет  собой  такой  метод,  когда  первый  член  пары
 выбирается случайно, а вторым с большей вероятностью будет максимально близкая
 к нему особь.
      Пример  определения  родства  хромосом  при  выборе родительской пары для
 хромосомы 1010001:
 
             Хромосомы популяции         Количество отличающихся локусов
                  1000000                              2
                  1010101                              1
                  0011100                              4
                  0000001                              2
                  0110011                              3
                  0100011                              4
                  1111111                              4
                  0000000                              3
 
      При  аутбридинге  также используют понятие схожести особей. Однако теперь
 брачные пары формируют из максимально далеких особей.
      Последние   два  способа  поразному  влияют  на  поведение  генетического
 алгоритма.  Так инбридинг можно охарактеризовать свойством концентрации поиска
 в  локальных узлах, что фактически приводит к разбиению популяции на отдельные
 локальные  группы  вокруг  подозрительных  на  экстремум  участков  ландшафта.
 Аутбридинг же направлен на предупреждение сходимости алгоритма к уже найденным
 решениям, заставляя алгоритм просматривать новые, неисследованные области.
 ******************************************************************************
 
 >1.16 Динамическая самоорганизация параметров ГА.
 >Yuri Burger [2:468/85.3]
 
      Зачастую,   выбор   параметров   генетического   алгоритма  и  конкретных
 генетических  операторов  производится  на интуитивном уровне, так как пока не
 существует  объективных  доказательств  преимущества  тех  или иных настроек и
 операторов. Однако, не нужно забывать, что сама суть ГА заключается в динамике
 и "мягкости" алгоритма и производимых вычислений. Тогда почему бы не позволить
 алгоритму самому настраиваться во время решения задачи и адаптироваться к ней?
      Hаиболее  просто организовать адаптацию применяемых операторов. Для этого
 встроем  в  алгоритм  несколько  (чем  больше  тем лучше) различных операторов
 выборки  (элитная,  случайная,  рулеточная,..),  кроссинговера  (одноточечный,
 двуточечный,   унифицированный,..)   и   мутации   (случайная  одноэлементная,
 абсолютная,..). Установим для каждого оператора равные вероятности применения.
 Далее,  на  каждом  цикле  алгоритма  будем выберать один из операторов каждой
 группы    (выбор,    кроссинговер,   мутация)   соответственно   вероятносному
 распределению.  Причем, в полученной при помощи этих операторов особи отметим,
 какими  именно  операторами она была получена. Тогда, если новое распределение
 вероятностей  мы  вычислим  исходя  из  информации,  содержащейся  в популяции
 (вероятность  применения  оператора  пропорциональна числу особей в популяции,
 полученных  при  помощи  этого  оператора),  то  генетический алгоритм получит
 механизм динамической самоадаптации.
      Такой  подход дает еще одно преимущество - теперь не нужно беспокоиться о
 применяемом  генераторе  случайных  чисел (линейный, экспоненциальный и т.д.),
 так как алгоритм динамически изменяет характер распределения.
 ******************************************************************************
 
 >1.17 Метод миграции и искусственной селекции.
 >В.В Курейчик, статья
 
      В отличие от обыкновенных ГА выполняется макроэволюция, т.е. создается не
 одна  популяция,  а  некоторое  множество  популяций. Генетический поиск здесь
 осуществляется путем объединения родителей из различных популяций.
 ******************************************************************************
 
 >1.18 Метод прерывистого равновесия.
 >В.В Курейчик, статья
 
      Метод  основан  на  палеонтологической  теории  прерывистого  равновесия,
 которая  описывает  быструю  эволюцию за счет вулканических и других изменений
 земной  коры. Для применения данного метода в технических задачах предлагается
 после  каждой  генерации  случайным  образом  перемешивать  индивидуальности в
 популяции,   а   затем   формировать  новые  текущие  генерации.  Здесь  можно
 предложить,  как  аналог  из живой природы, бессознательный отбор родительских
 пар  и  синтетический  отбор  лучших родительских пар. Далее случайным образом
 смешать результаты обоих отборов и не оставлять размер популяции постоянным, а
 управлять   им  в  зависимости  от  наличия  лучших  индивидуальностей.  Такая
 модификация   метода   прерывистого   равновесия   может  позволить  сократить
 неперспективные  популяции  и  расширить популяции, в которых находятся лучшие
 индивидуальности.
      Метод  прерывистого  равновесия  -  это мощный стрессовый метод изменения
 окружающей  среды,  который  используется для эффективного выхода из локальных
 ям.
 ******************************************************************************.
 [ю]ДДДДДДДД End 5   ДДДДДДД
                                                  Kрюгер.
 ---
  * Origin: А хто тут есть, у кого есть за что поесть? (2:468/85.3)
 
 

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