ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Yuri Burger                          2:468/85.3     19 Feb 2002  21:23:15
 To : All
 Subject : MildAlg FAQ: 06/10
 -------------------------------------------------------------------------------- 
 

 
 
 [ю]ДДДДДДДД Begin 06 ДДДДДДД
 
 >Что такое ложный оптимум?
 >Дэвид Бисслей, статья
 
     Одним  из  фундаментальных  принципов генетических алгоритмов является то,
 что хромосомы, включенные в шаблоны, которые содержатся в глобальном оптимуме,
 увеличиваются  по частоте (это особенно верно для коротких, небольшого порядка
 шаблонов,  известных  как  строительные  блоки). В конечном счете, посредством
 использования кроссинговера, эти оптимальные шаблоны сойдутся, и будет создана
 глобальная  оптимальная  хромосома.  Hо  если шаблоны, которые не содержатся в
 глобальном  оптимуме,  будут  увеличиватся  по  частоте быстрее чем другие, то
 генетический  алгоритм  будет введен в заблуждение и уйдет в другую сторону от
 глобального  оптимума,  вместо  того,  чтобы  приблизится  к нему. Это явление
 известно как ложный оптимум.
     Ложный  оптимум является частным случаем эпистаза, и он был глубоко изучен
 Goldberg и другими. Ложный оптимум непосредственно связан с вредными влияниями
 эпистаза в генетических алгоритмах.
     По  статистике,  шаблон  увеличится  по  частоте  в  популяции,  если  его
 пригодность  выше,  чем  средняя пригодность всех шаблонов в популяции. Задача
 обозначается  как  задача ложного оптимума, если средняя пригодность шаблонов,
 которые  не  содержатся в глобальном оптимуме, больше, чем средняя пригодность
 других шаблонов.
     Задачи ложного оптимума трудны для решения. Однако, Grefenstette остроумно
 демонстрирует,   что   они  возникают  не  всегда.  После  первого  поколения,
 генетический  алгоритм не получает объективную выборку точек в области поиска.
 Поэтому  он  не  может  оценивать  объективную  глобальную среднюю пригодность
 шаблона.  Он  может  только получить необъективную оценку пригодности шаблона.
 Иногда  это предубеждение помогает генетическому алгоритму сходиться (даже при
 том, что задача иначе могла бы иметь сильный ложный оптимум).
 ******************************************************************************
 
 >Что такое инбридинг, оутбридинг, селективный выбор, панмиксия?
 >(источник не известен)
 
      Существует  несколько  подходов  к  выбору  родительской  пары.  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аиболее  просто организовать адаптацию применяемых операторов. Для этого
 встроем  в  алгоритм  несколько  (чем  больше  тем лучше) различных операторов
 выборки  (элитная,  случайная,  рулеточная,..),  кроссинговера  (одноточечный,
 двуточечный,   унифицированный,..)   и   мутации   (случайная  одноэлементная,
 абсолютная,..). Установим для каждого оператора равные вероятности применения.
 Далее,  на  каждом  цикле  алгоритма  будем выберать один из операторов каждой
 группы    (выбор,    кроссинговер,   мутация)   соответственно   вероятносному
 распределению.  Причем, в полученной при помощи этих операторов особи отметим,
 какими  именно  операторами она была получена. Тогда, если новое распределение
 вероятностей  мы  вычислим  исходя  из  информации,  содержащейся  в популяции
 (вероятность  применения  оператора  пропорциональна числу особей в популяции,
 полученных  при  помощи  этого  оператора),  то  генетический алгоритм получит
 механизм динамической самоадаптации.
      Такой  подход дает еще одно преимущество - теперь не нужно беспокоиться о
 применяемом  генераторе  случайных  чисел (линейный, экспоненциальный и т.д.),
 так как алгоритм динамически изменяет характер распределения.
 ******************************************************************************
 
 >Метод миграции и искусственной селекции.
 >В.В Курейчик, статья
 
      В отличие от обыкновенных ГА выполняется макроэволюция, т.е. создается не
 одна  популяция,  а  некоторое  множество  популяций. Генетический поиск здесь
 осуществляется путем объединения родителей из различных популяций.
 ******************************************************************************
 
 >Метод прерывистого равновесия.
 >В.В Курейчик, статья
 
      Метод  основан  на  палеонтологической  теории  прерывистого  равновесия,
 которая  описывает  быструю  эволюцию за счет вулканических и других изменений
 земной  коры. Для применения данного метода в технических задачах предлагается
 после  каждой  генерации  случайным  образом  перемешивать  индивидуальности в
 популяции,   а   затем   формировать  новые  текущие  генерации.  Здесь  можно
 предложить,  как  аналог  из живой природы, бессознательный отбор родительских
 пар  и  синтетический  отбор  лучших родительских пар. Далее случайным образом
 смешать результаты обоих отборов и не оставлять размер популяции постоянным, а
 управлять   им  в  зависимости  от  наличия  лучших  индивидуальностей.  Такая
 модификация   метода   прерывистого   равновесия   может  позволить  сократить
 неперспективные  популяции  и  расширить популяции, в которых находятся лучшие
 индивидуальности.
      Метод  прерывистого  равновесия  -  это мощный стрессовый метод изменения
 окружающей  среды,  который  используется для эффективного выхода из локальных
 ям.
 ******************************************************************************.
 [ю]ДДДДДДДД End 06   ДДДДДДД
                                                  Kрюгер.
 ---
  * Origin: А хто тут есть, у кого есть за что поесть? (2:468/85.3)
 
 

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