ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Yuri Burger                          2:468/85.3     22 Jan 2002  18:47:59
 To : All
 Subject : MildFAQ: 5/12
 -------------------------------------------------------------------------------- 
 

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

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