ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Yuri Burger                          2:5020/400     06 Dec 2002  13:41:47
 To : All
 Subject : MildFAQ: 3
 -------------------------------------------------------------------------------- 
 

 Hello, All!
 
 ****************************************************************************
 **
 
 >А на исходник ГА посмотреть можно?
 >Yuri Burger [2:468/85.3]
 
     Мыльте мне, заюючу. Из чистого ГА есть:
 
     GA.RAR              - простой  элитарный  ГА для оптимизации  функции
 двух
                           переменных (Watcom C; 1,827b)
     GEN2.RAR            - оптимизация  введенной  в эдит-боксе функции,
 разбор
                           выражения  (кривоват),  выделение  переменных  и
 всё
                           такое (Visual C; 125,151b с релизом)
     GENETIC.RAR         - ГА оптимизации функции двух переменных, можно
 видеть
                           функцию в 2-D и сам процесс оптимизации -
 отмечаются
                           точки, просмотренные алгоритмом (Visual C;
 118,017b
                           с релизом)
 ****************************************************************************
 **
 
 >В элитарном ПГА не ясна роль "не элитных" особей.
 >Yuri Burger [2:468/85.3]
 
     Честно  говоря,  этот  вопрос меня самого поставил в тупик. Прикинул так
 и
 этак - выходит что не нужны они.. Однако нельзя торопиться с выводами.
      Вопервых,   многое  зависит от процедуры добавления особей в популяцию.
 В
 зависимости от неё, неэлитные особи могут терять и преобретать значимость.
      И  есть еще одно применение им. Если функция оценки особей (фитнес)
 будет
 давольно  медленной,  то  эти  особи можно использовать в качестве кэша.
 Всилу
 особенностей  работы ГА, будет весьма высокая вероятность появления решений
 из
 окресности текущего оптимума, а значит можно ожидать повторения особей.
 ****************************************************************************
 **
 
 >Классический (одноточечный) кроссинговер.
 >Дэвид Бисслей, статья
 
     "Традиционный" генетический алгоритм использует одноточечный
 кроссинговер,
 в  котором две скрещивающиеся хромосомы разрезаются один раз в
 соответствующей
 точке  и  производится обмен полученными частями. Однако было изобретено
 много
 других  различных  алгоритмов  с  иными видами кроссинговера, часто
 включающих
 больше  чем одну точку разреза. 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  анализируют
 оператор
 переупорядочения  на  очень  маленькой  задаче,  показывая, что она может
 дать
 определенное преимущество, хотя они заключают, что их методы не принесли бы
 то
 же самое преимущество на больших задачах.
     Переупорядочение  также  значительно  расширяет область поиска. Мало
 того,
 что  генетический алгоритм пытается находить хорошие множества значений
 генов,
 он также одновременно пробует находить хорошее упорядочения генов. Это
 гораздо
 более  трудная  задача для решения.
 ****************************************************************************
 **
 
 >Что такое эпистаз?
 >Дэвид Бисслей, статья
 
     Термин  эпистаз  был  определен генетиками как влияние гена на
 пригодность
 индивидуума  в  зависимости  от значения гена, присутствующего в другом
 месте.
 Более  определенно,  генетики  используют  термин  эпистаз  в  смысле
 эффекта
 "переключения"  или  "маскирования".  "Ген  считают  эпистатическим, когда
 его
 присутствие подавляет влияние гена в другом локусе. Эпистатические гены
 иногда
 называют  ингибирующими  из-за  их влияния на другие гены, которые
 описываются
 как гипостаз".
     Когда исследователи генетических алгоритмов используют термин эпистаз,
 они
 говорят  обо  всем,  что  касается  любого вида взаимодействия среди генов,
 не
 только  эффекта  маскирования,  хотя они избегают давать точное определение.
 ****************************************************************************
 **
 
 >Что такое ложный оптимум?
 >Дэвид Бисслей, статья
 
     Одним  из  фундаментальных  принципов генетических алгоритмов является
 то,
 что хромосомы, включенные в шаблоны, которые содержатся в глобальном
 оптимуме,
 увеличиваются  по частоте (это особенно верно для коротких, небольшого
 порядка
 шаблонов,  известных  как  строительные  блоки). В конечном счете,
 посредством
 использования кроссинговера, эти оптимальные шаблоны сойдутся, и будет
 создана
 глобальная  оптимальная  хромосома.  Hо  если шаблоны, которые не содержатся
 в
 глобальном  оптимуме,  будут  увеличиватся  по  частоте быстрее чем другие,
 то
 генетический  алгоритм  будет введен в заблуждение и уйдет в другую сторону
 от
 глобального  оптимума,  вместо  того,  чтобы  приблизится  к нему. Это
 явление
 известно как ложный оптимум.
     Ложный  оптимум является частным случаем эпистаза, и он был глубоко
 изучен
 Goldberg и другими. Ложный оптимум непосредственно связан с вредными
 влияниями
 эпистаза в генетических алгоритмах.
     По  статистике,  шаблон  увеличится  по  частоте  в  популяции,  если
 его
 пригодность  выше,  чем  средняя пригодность всех шаблонов в популяции.
 Задача
 обозначается  как  задача ложного оптимума, если средняя пригодность
 шаблонов,
 которые  не  содержатся в глобальном оптимуме, больше, чем средняя
 пригодность
 других шаблонов.
     Задачи ложного оптимума трудны для решения. Однако, Grefenstette
 остроумно
 демонстрирует,   что   они  возникают  не  всегда.  После  первого
 поколения,
 генетический  алгоритм не получает объективную выборку точек в области
 поиска.
 Поэтому  он  не  может  оценивать  объективную  глобальную среднюю
 пригодность
 шаблона.  Он  может  только получить необъективную оценку пригодности
 шаблона.
 Иногда  это предубеждение помогает генетическому алгоритму сходиться (даже
 при
 том, что задача иначе могла бы иметь сильный ложный оптимум).
 With best regards, Yuri Burger.  E-mail: kruger@selena.net.ua
 --- ifmail v.2.15dev5
  * Origin: Unknown (2:5020/400)
 
 

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