ru.algorithms

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

 
 
 [ю]ДДДДДДДД Begin 4 ДДДДДДД
 
 >1.9 Какие существуют методы кроссинговера?
 >Дэвид Бисслей, статья
 
     "Традиционный" генетический алгоритм использует одноточечный кроссинговер,
 в  котором две скрещивающиеся хромосомы разрезаются один раз в соответствующей
 точке  и  производится обмен полученными частями. Однако было изобретено много
 других  различных  алгоритмов  с  иными видами кроссинговера, часто включающих
 больше  чем одну точку разреза. DeJong исследовал эффективность многоточечного
 кроссинговера  и пришел к выводу, что двуточечный кроссинговер дает улучшение,
 но  что  дальнейшее  добавление  точек  кроссинговера  редуцирует деятельность
 генетического   алгоритма.   Проблема   с   добавлением  дополнительных  точек
 кроссинговера  состоит в том, что стандартные блоки, вероятно, будут прерваны.
 Однако преимущество большего количества точек кроссинговера состоит в том, что
 пространство состояний может быть исследовано более полно и подробно.
 
     ДВУХТОЧЕЧHЫЙ КРОССИHГОВЕР.
     В   двухточечном  кроссинговере  (и  многоточечном  кроссинговере  вообще)
 хромосомы  расцениваются  как  циклы,  которые  формируются соединением концов
 линейной  хромосомы вместе. Для замены сегмента одного цикла сегментом другого
 цикла  требуется  выбор двух точек разреза. В этом представлении, одноточечный
 кроссинговер  может  быть  рассмотрен  как  кроссинговер с двумя точками, но с
 одной   точкой   разреза,  зафиксированной  в  начале  строки.  Следовательно,
 двухточечный  кроссинговер  решает  ту  же  самую  задачу,  что и одноточечный
 кроссинговер  ,  но  более  полно.  Хромосома, рассматриваемая как цикл, может
 содержать  большее  количество стандартных блоков, так как они могут совершить
 "циклический   возврат"   в   конце   строки.   В   настоящий   момент  многие
 исследователи  соглашаются,  что  двухточечный  кроссинговер вообще лучше, чем
 одноточечный.
                 линейное представление:     хххххххххххх
                                             ДДДДДДДДДДДД>
 
                 циклическое представление:Ъ>ххххххххххххДї
                                           АДДДДДДДДДДДДДДЩ
 
     УHИФИЦИРОВАHHЫЙ (ОДHОРОДHЫЙ) КРОССИHГОВЕР.
     Унифицированный  кроссинговер  принципиально  отличается  от одноточечного
 кроссинговера.  Каждый  ген  в  потомстве  создается  посредством  копирования
 соответствующего  гена  от  одного  или  другого родителя, выбранного согласно
 случайно сгенерированной маске кроссинговера. Если в маске кроссинговера стоит
 1,  то  ген  копируется  от  первого  родителя,  если  в маске стоит 0, то ген
 копируется  от  второго родителя. Процесс повторяется с обмененными родителями
 для   создания   второго   потомства.   Hовая   маска  кроссинговера  случайно
 генерируется для каждой пары родителей.
 ******************************************************************************
 
 >1.10 А исходники этих кроссинговеров есть?
 >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));
            }
         }
 ******************************************************************************
 
 >1.11 Что такое инверсия и переупорядочение?
 >Дэвид Бисслей, статья
 
     Часто  порядок  генов  в  хромосоме  является критическим для строительных
 блоков, позволяющий осуществлять эффективную работу алгоритма. Были предложены
 методы  для  переупорядочения  позиций  генов  в  хромосоме  во  время  работы
 алгоритма.   Одной   из   таких   методик   является   инверсия,   выполняющая
 реверсирование  порядка  генов  между  двумя  случайно  выбранными позициями в
 хромосоме.  (Когда  используются  эти  методы, гены должны содержать некоторую
 "метку",  так, чтобы их можно было правильно идентифицировать независимо от их
 позиции в хромосоме.)
     Цель переупорядочения состоит в том, чтобы попытаться найти порядок генов,
 который имеет лучший эволюционный потенциал. Многие исследователи использовали
 инверсию  в  своей работе, хотя кажется, что немногие попытались ее обосновать
 или   определить   ее   вклад.   Goldberg   &   Bridges  анализируют  оператор
 переупорядочения  на  очень  маленькой  задаче,  показывая, что она может дать
 определенное преимущество, хотя они заключают, что их методы не принесли бы то
 же самое преимущество на больших задачах.
     Переупорядочение  также  значительно  расширяет область поиска. Мало того,
 что  генетический алгоритм пытается находить хорошие множества значений генов,
 он также одновременно пробует находить хорошее упорядочения генов. Это гораздо
 более  трудная  задача для решения.
 ******************************************************************************
 
 >1.12 Что такое эпистаз?
 >Дэвид Бисслей, статья
 
     Термин  эпистаз  был  определен генетиками как влияние гена на пригодность
 индивидуума  в  зависимости  от значения гена, присутствующего в другом месте.
 Более  определенно,  генетики  используют  термин  эпистаз  в  смысле  эффекта
 "переключения"  или  "маскирования".  "Ген  считают  эпистатическим, когда его
 присутствие подавляет влияние гена в другом локусе. Эпистатические гены иногда
 называют  ингибирующими  из-за  их влияния на другие гены, которые описываются
 как гипостаз".
     Когда исследователи генетических алгоритмов используют термин эпистаз, они
 говорят  обо  всем,  что  касается  любого вида взаимодействия среди генов, не
 только  эффекта  маскирования,  хотя они избегают давать точное определение.
 ******************************************************************************
 
 >1.13 Что такое ложный оптимум?
 >Дэвид Бисслей, статья
 
     Одним  из  фундаментальных  принципов генетических алгоритмов является то,
 что хромосомы, включенные в шаблоны, которые содержатся в глобальном оптимуме,
 увеличиваются  по частоте (это особенно верно для коротких, небольшого порядка
 шаблонов,  известных  как  строительные  блоки). В конечном счете, посредством
 использования кроссинговера, эти оптимальные шаблоны сойдутся, и будет создана
 глобальная  оптимальная  хромосома.  Hо  если шаблоны, которые не содержатся в
 глобальном  оптимуме,  будут  увеличиватся  по  частоте быстрее чем другие, то
 генетический  алгоритм  будет введен в заблуждение и уйдет в другую сторону от
 глобального  оптимума,  вместо  того,  чтобы  приблизится  к нему. Это явление
 известно как ложный оптимум.
     Ложный  оптимум является частным случаем эпистаза, и он был глубоко изучен
 Goldberg и другими. Ложный оптимум непосредственно связан с вредными влияниями
 эпистаза в генетических алгоритмах.
     По  статистике,  шаблон  увеличится  по  частоте  в  популяции,  если  его
 пригодность  выше,  чем  средняя пригодность всех шаблонов в популяции. Задача
 обозначается  как  задача ложного оптимума, если средняя пригодность шаблонов,
 которые  не  содержатся в глобальном оптимуме, больше, чем средняя пригодность
 других шаблонов.
     Задачи ложного оптимума трудны для решения. Однако, Grefenstette остроумно
 демонстрирует,   что   они  возникают  не  всегда.  После  первого  поколения,
 генетический  алгоритм не получает объективную выборку точек в области поиска.
 Поэтому  он  не  может  оценивать  объективную  глобальную среднюю пригодность
 шаблона.  Он  может  только получить необъективную оценку пригодности шаблона.
 Иногда  это предубеждение помогает генетическому алгоритму сходиться (даже при
 том, что задача иначе могла бы иметь сильный ложный оптимум).
 ******************************************************************************.
 [ю]ДДДДДДДД End 4   ДДДДДДД
                                                  Kрюгер.
 ---
  * Origin: А хто тут есть, у кого есть за что поесть? (2:468/85.3)
 
 

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