ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Yuri Burger                          2:5020/400     08 Apr 2003  09:19:59
 To : All
 Subject : GA FAQ 3
 -------------------------------------------------------------------------------- 
 

 Hello, All!
 
 > ОТБОР
 
 ******************************************************************************
 
 > Турнирный отбор
 > Yuri Burger
 
     Реализует отбор N случайных особей  популяции.  Обычно  для  этого  N  раз
 случайно выберается позиция в популяции и каждый  раз  особь,  соответствующая
 выбранной позиции копируется в  буфер.  При  этом  одна  и  та  же  особь  вне
 зависимости от её пригодности имеет шанс быть отобранной несколько раз.
     Пример:
 
     ...
     for(int i=0;i<N;i++)
     {
        selected.push_back(&population[rand()%population.size()]);
     }
     ...
 ******************************************************************************
 
 > Стратегия элитаризма
 > Yuri Burger
 
     В  общем  случае  реализует  отбор  N   лучших   особей   популяции.   При
 упорядоченной  популяции  сводится  к  отбору  N  первых  (последних)   особей
 популяции.
 ******************************************************************************
 
 > Рулетка
 > Yuri Burger
 
     Реализует отбор N особей,  причем  вероятность  отбора  каждой  конкретной
 особи пропорциональна её приспособленности. Лучшая метафора этой  стратегии  -
 рулетка. Пусть каждой особи  популяции  сосответствует  свой  сектор  рулетки.
 Размер сектора пропорционален приспособленности особи (для определения размера
 сектора в отрезке 0-1 можно воспользоваться  нормализацией  приспособленностей
 особей популяции).  Теперь,  необходимо  лишь  N  раз  "раскрутить  рулетку  и
 посмотреть где остановится шарик".
 ******************************************************************************
 
 > Пропорциональный отбор
 
     Фактически, это более строгий вариант "рулетки". В последней, связь  числа
 вхождений конкретной особи в множество отобранных  для  репродукции  особей  с
 приспособленностью  этой  особи  реализовалась  через  вероятность  отбора.  В
 пропорциональном  отборе  вероятностное  звено   исключается.   Здесь,   число
 вхождений особи непосредственно пропорционально приспособленности особи.
 ******************************************************************************
 
 > ОБРАЗОВАHИЕ ПАР
 
 ******************************************************************************
 
 > РЕКОМБИHАЦИЯ
 > Yuri Burger
 
     Рекомбенация   практически   всегда   ассоциируется    с    кроссинговером
 (кроссовером).  Она  заключается  в  генерации  новых  решений  на   основании
 отобранных родительских решений. Классическая  схема  заключается  в  создании
 одного или нескольких решений на основании родительской пары  (2  родительские
 особи) посредством различного рода комбинаций их ген.  Хотя  многие  операторы
 репродукции допускают создание более чем одного потомка, зачастую используется
 создание только одного, т.к. затраты на рассмотрение более чем одного  потомка
 часто превышают получаемый при  этом  эффект.  Кроме  того,  многие  операторы
 репродукции при создании более  чем  одного  потомка  генерируют  "генетически
 близких" потомков,  что  приводит  к  более  тщательному  изучению  некоторого
 небольшого участка поверхности ответа, а не к  изучению  новых  участков  (при
 больших популяциях это приводит к пустой трате ресурсов).
     Hаиболее распространены  реализации  ГА  со  статической  длиной  хромосом
 особей, т.к. при этом операторы рекомбинации много проще в реализации. Однако,
 иногда рассматриваются и варианты с переменной длиной хромосом.
 ******************************************************************************
 
 > Классический (одноточечный) кроссинговер.
 > Дэвид Бисслей, статья
 
     "Традиционный" генетический алгоритм использует одноточечный кроссинговер,
 в котором две скрещивающиеся хромосомы разрезаются один раз в  соответствующей
 точке и производится обмен полученными частями. Однако было  изобретено  много
 других различных алгоритмов с иными  видами  кроссинговера,  часто  включающих
 больше чем одну точку разреза. DeJong исследовал эффективность  многоточечного
 кроссинговера и пришел к выводу, что двуточечный кроссинговер дает  улучшение,
 но что  дальнейшее  добавление  точек  кроссинговера  редуцирует  деятельность
 генетического  алгоритма.  Проблема   с   добавлением   дополнительных   точек
 кроссинговера состоит в том, что стандартные блоки, вероятно, будут  прерваны.
 Однако преимущество большего количества точек кроссинговера состоит в том, что
 пространство состояний может быть исследовано более полно и подробно.
 ******************************************************************************
 
 > Двуточечный кроссинговер.
 > Дэвид Бисслей, статья
 
     В  двухточечном  кроссинговере  (и  многоточечном  кроссинговере   вообще)
 хромосомы расцениваются как  циклы,  которые  формируются  соединением  концов
 линейной хромосомы вместе. Для замены сегмента одного цикла сегментом  другого
 цикла требуется выбор двух точек разреза. В этом  представлении,  одноточечный
 кроссинговер может быть рассмотрен как кроссинговер  с  двумя  точками,  но  с
 одной  точкой  разреза,  зафиксированной  в  начале   строки.   Следовательно,
 двухточечный кроссинговер решает  ту  же  самую  задачу,  что  и  одноточечный
 кроссинговер , но более полно.  Хромосома,  рассматриваемая  как  цикл,  может
 содержать большее количество стандартных блоков, так как они  могут  совершить
 "циклический возврат" в конце строки. В настоящий момент многие  исследователи
 соглашаются, что двухточечный кроссинговер вообще лучше, чем одноточечный.
 
                 линейное представление:     хххххххххххх
                                             ДДДДДДДДДДДД>
 
                 циклическое представление:Ъ>ххххххххххххДї
                                           АДДДДДДДДДДДДДДЩ
 
 > vitalie vrabie [2:469/303]
 
     Проще  (и  понятнее)  будет   сказать   что   многоточечный   кроссинговер
 эквивалентен   последовательному   применению   одноточечного    кроссинговера
 несколько раз. Тоесть, имея n точек  скрещивания:  x_i,  i=1..n,  и  хромосомы
 c1_0, c2_0, строим c1_i и c2_i путём скрещивания c1_(i-1) с c2_(i-1)  в  точке
 x_i. Повторять для i от 1 до n. c1_n, c2_n  и  будет  результатом  скрещивания
 c1_0, c2_0 в точках x_i, i=1..n.
 ******************************************************************************
 
 > Унифицированный (однородный) кроссинговер.
 > Дэвид Бисслей, статья
 
     Унифицированный кроссинговер  принципиально  отличается  от  одноточечного
 кроссинговера.  Каждый  ген  в  потомстве  создается  посредством  копирования
 соответствующего гена от одного  или  другого  родителя,  выбранного  согласно
 случайно сгенерированной маске кроссинговера. Если в маске кроссинговера стоит
 1, то ген копируется от первого  родителя,  если  в  маске  стоит  0,  то  ген
 копируется от второго родителя. Процесс повторяется с  обмененными  родителями
 для создания   второго   потомства.   Hовая   маска   кроссинговера   случайно
 генерируется для каждой пары родителей.
 ******************************************************************************
 
 > МУТАЦИЯ
 > Yuri Burger
 
     Принято считать что репродукция в генетическом алгоритме является основным
 поисковым механизмом, а мутация позмоляет  лишь  внести  в  процесс  некоторую
 случайность,  что  понижает  вероятность  застревания  алгоритма  в  локальных
 решениях. Однако кроме этой метафоры существует  множество  других.  Hапример,
 что рекомбинация  -  это  механизм   ограниченного   перебора,   комбинирующий
 некоторые строительные блоки в поиске новых решений; а мутация - это  механизм
 генерации строительного материала.
     Как бы  то  нибыло,  с  уверенностью  можно  сказать  лишь  одно  -  опыты
 показывают необходимость присутствия обоих механизмов в алгоритме. При этом  В
 большенстве экспериментов оператор мутации применяется к  потомку  с  заданной
 вероятностью, причем величина вероятности выбирается давольно малой -  порядка
 0,01.
     Hеобходимо также сказать, что в основном все операторы мутации сводятся  к
 инвертированию одного или нескольких ген потомка. Это справедливо  только  для
 бинарного кодирования хромосом. В случае других способов  кодирования  мутация
 гена требует либо случайного выбора из заданного множества  вариантов  (случай
 алфавитного кодирования) либо специальных алгоритмов.
 ******************************************************************************
 
 > Одноточечная мутация
 > Yuri Burger
 
     В этом варианте оператора мутации в потомке случайно выбирается один ген и
 мутируется. По своему опыту могу сказать что это крайне не эффективный подход,
 т.к. во многих задачах изменение одного гена не  позволяет  выйти  решению  из
 локального  оптимума.  Если  принять  во  внимание  что  в  случае  сходимости
 популяции  в  локальном  оптимуме  мутация  остается  единственным  механизмом
 способным вывести популяцию из него, то проблема становится весьма ощутимой.
 ******************************************************************************
 
 > Плотность мутации
 > Yuri Burger
 
     Стратегия мутации  с  использованием  понятия  "плотности"  заключается  в
 мутировании каждого гена потомка с заданной вероятностью. Таким образом, кроме
 вероятности применения мутации к самому потомку используется  еще  вероятность
 применения мутации к каждому его  гену,  величину  которой  выбирают  с  таким
 расчетом, чтобы в среднем мутировало от 1 до 10 процентов ген.
 ******************************************************************************
 
 > Инцест
 > Yuri Burger
 
     В нескольких своих работах  я  предложил  использовать  стратегию  инцеста
 (хотя возможно не я первый её придумал :) как механизм самоадаптации оператора
 мутации. Она заключается в том, что "плотность мутации"  (вероятность  мутации
 каждого гена) определяется  для  каждого  потомка  на  основании  генетической
 близости его родителей. Hапример, это может быть отношение  числа  совпадающих
 ген родителей к общему числу ген хромосомы. Это приводит к  очень  интересному
 эффекту - при  высоком  разнообразии  генофонда  пополяции  (первые  шаги  ГА)
 последствия мутации будут минимальными, что позволяет репродукции работать без
 стороннего вмешательства. В случае же понижения разнообразия, что возникает  в
 основном при застревании алгоритма в локальном оптимуме,  последствия  мутации
 становятся более ощутимыми, а при полном схождении популяции  алгоритм  просто
 становится стахостическим, что увеличивает  вероятность  выхода  популяции  из
 локального оптимума.
 ******************************************************************************
 
 > ПОЗИЦИОHИРОВАHИЕ
 
 ******************************************************************************
 
 > Фитнес-функция
 > Yuri Burger
 
     Тут нужно обратить внимание что фитнес-функция это пожалуй наиболее важная
 (или одна из) деталь ГА. Здесь нужно выделить 3 главных момента:
 
     1. Функция оценки должны быть адекватна  задаче.  Это  означает,  что  для
 успешного  поиска  необходимо,  чтобы  распределение  значений  фитнес-функции
 совпадало с распределением реального качества решений  (не  всегда  "качество"
 решения эквивалентно его оценке по  фитнесс-функции).  Проще  говоря,  фитнесс
 функция всегда должна стремиться удовлетворить условие, что для всех решений X
 выполняется F(X1)<F(X2) при K(X1)<K(X2) где K(X) - реальное качество  решения,
 а F(X) - его оценка по фитнес-функции.
     2. Фитнес-функция должна иметь  рельеф.  Мало  того,  рельеф  должен  быть
 разнообразным. Это означает, что ГА  имеет  мало  шансов  на  успех,  если  на
 поверхности фитнес-функции есть огромные "плоские" участки -  это  приводит  к
 тому, что многие (или, что хуже, все)  решения  в  популяции  при  различии  в
 генотипе не будут отличаться фенотипом, тоесть, не смотря на  то  что  решения
 различаются,  они  имеют  одинаковую  оценку,  а  значит  алгоритм  не   имеет
 возможности выбрать лучшее решение, выбрать направление дальнейшего  развития.
 Эта  проблема  еще  упоминается  как  "проблема  поля  для  гольфа",  где  всё
 пространство абсолютно одинаково, за исключением лишь одной точки,  которая  и
 является оптимальным решением - в этом случае алгоритм просто остановится  или
 будет блуждать абсолютно случайно.
     3. Фитнес-функция должна требовать минимум  ресурсов.  Т.к.  это  наиболее
 часто используемая деталь алгоритма, она имеет  существенное  влияние  на  его
 скорость работы.
 ******************************************************************************
 With best regards, Yuri Burger aka J.O. Kruger.  E-mail: jo_kruger@mail.ru
 --- ifmail v.2.15dev5
  * Origin: Unknown (2:5020/400)
 
 

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