ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Yuri Burger                          2:468/85.3     22 Jan 2002  18:48:10
 To : All
 Subject : MildFAQ: 6/12
 -------------------------------------------------------------------------------- 
 

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

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