ru.algorithms

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

 
 
 [ю]ДДДДДДДД Begin 05 ДДДДДДД
 
 >Классический (одноточечный) кроссинговер.
 >Дэвид Бисслей, статья
 
     "Традиционный" генетический алгоритм использует одноточечный кроссинговер,
 в  котором две скрещивающиеся хромосомы разрезаются один раз в соответствующей
 точке  и  производится обмен полученными частями. Однако было изобретено много
 других  различных  алгоритмов  с  иными видами кроссинговера, часто включающих
 больше  чем одну точку разреза. 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овая   маска  кроссинговера  случайно
 генерируется для каждой пары родителей.
 ******************************************************************************
 
 >Дифференциальное скрещивание.
 >Ilya S. Potrepalov [ispotrepalov@asu.tnk.ru]
 
      Существуют  и другие методы скрещивания, а не только crossover. Hапример,
 для  поиска минимума/максимума функции многих вещественных переменных наиболее
 удачным  является "дифференциальное скрещивание". А именно, пусть a и b -- это
 два  индивидума в популяции, т.е. вещественные вектора от которых наша функция
 зависит.  Тогда  потомок  c  вычисляется  по формуле с=a+k*(a-b), где k -- это
 некоторый   вещественный   коэффициент  (который  может  зависить  от  ||a-b||
 --растояния  между  векторами).
      В  этой  модели мутация -- это добавление к индивидуму случайного вектора
 малой длины. Если исходная функия непрерывна, то эта модель работает хорошо. А
 если она еще и гладкая, то -- превосходно.
 ******************************************************************************
 
 >Исходники некоторых кроссинговеров.
 >Yuri Burger [2:468/85.3]
 
     Вот вырезки из моих прог. Вполне можно прикрутить куда нужно :)
     Пояснения:
     EBitSize - количество бит на одну переменную
     Сырци вырезаны из задачи с 4-мя переменными.
     Процедуры   GetBit,   SetBit   и   InvertBit   -   соответственно  читают,
 устанавливают  и  инвертируют  указанный  бит  в  векторе (хромосоме). Если Вы
 храните  каждый  бит  в byte и хромосома соответственно представленна массивом
 этих byte, процедурки можна сразу сменить на обращение к массиву :)
 
     v1, v2 - указатели на родительские особи.
     c1, c2 - потомки.
 
         // классический кроссинговер
         q=rand()*(EBitSize*4-1)/RAND_MAX;
         for(t=0;t<q;t++)
         {
            SetBit(c1->r,t,GetBit(v1->r,t));
            SetBit(c2->r,t,GetBit(v2->r,t));
         }
         for(t=q;t<EBitSize*4;t++)
         {
            SetBit(c1->r,t,GetBit(v2->r,t));
            SetBit(c2->r,t,GetBit(v1->r,t));
         }
 
         // 2х точечный кроссинговер
         t1=rand()*(EBitSize*4-1)/RAND_MAX;
         t2=rand()*(EBitSize*4-1)/RAND_MAX;
         t=t1;
         while(t!=t2)
         {
            SetBit(c1->r,t,GetBit(v1->r,t));
            SetBit(c2->r,t,GetBit(v2->r,t));
            t++;
            if(t==EBitSize*4)t=0;
         }
         while(t!=t1)
         {
            SetBit(c1->r,t,GetBit(v2->r,t));
            SetBit(c2->r,t,GetBit(v1->r,t));
            t++;
            if(t==EBitSize*4)t=0;
         }
 
         // Унифицированный кроссинговер
         for(t=0;t<EBitSize*4;t++)
         {
            if(rand()<(RAND_MAX/2))
            {
               SetBit(c1->r,t,GetBit(v1->r,t));
               SetBit(c2->r,t,GetBit(v2->r,t));
            }
            else
            {
               SetBit(c1->r,t,GetBit(v2->r,t));
               SetBit(c2->r,t,GetBit(v1->r,t));
            }
         }
 ******************************************************************************
 
 >Что такое инверсия и переупорядочение?
 >Дэвид Бисслей, статья
 
     Часто  порядок  генов  в  хромосоме  является критическим для строительных
 блоков, позволяющий осуществлять эффективную работу алгоритма. Были предложены
 методы  для  переупорядочения  позиций  генов  в  хромосоме  во  время  работы
 алгоритма.   Одной   из   таких   методик   является   инверсия,   выполняющая
 реверсирование  порядка  генов  между  двумя  случайно  выбранными позициями в
 хромосоме.  (Когда  используются  эти  методы, гены должны содержать некоторую
 "метку",  так, чтобы их можно было правильно идентифицировать независимо от их
 позиции в хромосоме.)
     Цель переупорядочения состоит в том, чтобы попытаться найти порядок генов,
 который имеет лучший эволюционный потенциал. Многие исследователи использовали
 инверсию  в  своей работе, хотя кажется, что немногие попытались ее обосновать
 или   определить   ее   вклад.   Goldberg   &   Bridges  анализируют  оператор
 переупорядочения  на  очень  маленькой  задаче,  показывая, что она может дать
 определенное преимущество, хотя они заключают, что их методы не принесли бы то
 же самое преимущество на больших задачах.
     Переупорядочение  также  значительно  расширяет область поиска. Мало того,
 что  генетический алгоритм пытается находить хорошие множества значений генов,
 он также одновременно пробует находить хорошее упорядочения генов. Это гораздо
 более  трудная  задача для решения.
 ******************************************************************************
 
 >Что такое эпистаз?
 >Дэвид Бисслей, статья
 
     Термин  эпистаз  был  определен генетиками как влияние гена на пригодность
 индивидуума  в  зависимости  от значения гена, присутствующего в другом месте.
 Более  определенно,  генетики  используют  термин  эпистаз  в  смысле  эффекта
 "переключения"  или  "маскирования".  "Ген  считают  эпистатическим, когда его
 присутствие подавляет влияние гена в другом локусе. Эпистатические гены иногда
 называют  ингибирующими  из-за  их влияния на другие гены, которые описываются
 как гипостаз".
     Когда исследователи генетических алгоритмов используют термин эпистаз, они
 говорят  обо  всем,  что  касается  любого вида взаимодействия среди генов, не
 только  эффекта  маскирования,  хотя они избегают давать точное определение.
 ******************************************************************************.
 [ю]ДДДДДДДД End 05   ДДДДДДД
                                                  Kрюгер.
 ---
  * Origin: А хто тут есть, у кого есть за что поесть? (2:468/85.3)
 
 

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