Справочник функций

Ваш аккаунт

Войти через: 
Забыли пароль?
Регистрация
Информацию о новых материалах можно получать и без регистрации:

Последние темы форума

Показать новые сообщения »

Почтовая рассылка

Подписчиков: 11642
Последний выпуск: 19.06.2015

Генетический алгоритм

Что такое генетический алгоритм?

Генетический алгоритм (ГА) представляет собой метод оптимизации, основанный на концепциях естественного отбора и генетики. В этом подходе переменные, характеризующие решение, представлены в виде ген в хромосоме. ГА оперирует конечным множеством решений (популяцией) - генерирует новые решения как различные комбинации частей решений популяции, используя такие операторы, как отбор, рекомбинация (кроссинговер) и мутация. Новые решения позиционируются в популяции в соответствии с их положением на поверхности исследуемой функции.

Идею ГА подсказала сама природа и работы Дарвина. Делается предположение, что если взять 2 вполне хороших решения задачи и каким-либо образом получить из них новое решение, то будет высокая вероятность того, что новое решение получится хорошим или даже более лучшим.

Для реализации этого используют моделирование эволюции (естественного отбора) или если проще - борьбы за выживание. В природе, по упрощенной схеме, каждое животное стремится выжить, чтобы оставить после себя как можно больше потомства. Выжить в таких условиях могут лишь сильнейшие.

Тогда нам остается организовать некоторую среду - популяцию, населить её решениями - особями, и устроить им борьбу. Для этого нужно определить функцию, по которой будет определяться сила особи - качество предложенного ею решения. Основываясь на этом параметре можно определить каждой особи количество оставляемых ею потомков, или вероятность того, что эта особь оставит потомка. Причем, не исключен вариант, когда особь со слишком низким значением этого параметра умрёт.

Допустим нам нужно оптимизировать некоторую функцию F(X1,X2,..,Xn). Пусть мы ищем её глобальный максимум. Тогда, для реализации ГА нам нужно придумать, как мы будем хранить решения. По сути, нам нужно поместить все X1-Xn в некоторый вектор, который будет играть роль хромосомы. Один из наиболее распространенных способов - кодировать значения переменных в битовом векторе. Например, выделим каждому иксу по 8 бит. Тогда наш вектор будет длины L=8*n. Для простоты будем считать, что биты лежат в массиве X[0..L-1].

Пусть каждая особь состоит из массива X и значения функции F на переменных, извлеченных из этого массива.

Тогда ГА будет состоять из следующих шагов:

  1. Генерация начальной популяции - заполнение популяции особями, в которых элементы массива X (биты) заполнены случайным образом.
  2. Выбор родительской пары - я всегда использую элитный отбор, то есть берем K особей с максимальными значениями функции F и составляю из них все возможные пары (K*(K-1)/2).
  3. Кроссинговер - берем случайную точку t на массиве X (0..L-1).

    Теперь, все элементы массива с индексами 0-t новой особи (потомка) заполняем элементами с теми-же индексами, но из массива X первой родительской особи. Остальные элементы заполняются из массива второй родительской особи. Для второго потомка делается наоборот - элементы 0-t берут от второго потомка, а остальные - от первого.

  4. Новые особи с некоторой вероятностью мутируют - инвертируется случайный бит массива X этой особи. Вероятность мутации обычно полагают порядка 1%.
  5. Полученные особи-потомки добавляются в популяцию после переоценки. Обычно новую особь добавляют взамен самой плохой старой особи, при условии что значение функции на новой особи выше значения функции на старой-плохой особи.
  6. Если самое лучшее решение в популяции нас не удовлетворяет, то переход на шаг 2. Хотя, чаще всего этого условия нет, а итерации ГА выполняются бесконечно.
Вообще, если строго придерживаться правилам, то ГА должен содержать еще такие шаги как отбор особей для размножения и генерация пар из отобранных особей. При этом каждая особь может быть задействована в одной и более паре, в зависимости от используемого алгоритма.

Однако я предпочитаю эти два шага совмещать, используя построение пар "все на все" в элитной выборке. Имхо, так проще.

Кто придумал генетический алгоритм?

В 1966 г. Л.Дж.Фогель, А.Дж. Оуэнс, М.Дж.Волш предложили и исследовали эволюцию простых автоматов, предсказывающих символы в цифровых последовательностях. В 1975г. Д.Х.Холланд предложил схему генетического алгоритма. Эти работы легли в основу главных направлений разработки эволюционных алгоритмов.

Простой генетический алгоритм был впервые описан Гольдбергом на основе работ Холланда.

Преимущества генетических алгоритмов?

  • Они не требуют никакой информации о поверхности ответа;
  • Разрывы, существующие на поверхности ответа имеют незначительный эффект на полную эффективность оптимизации;
  • Они стойки к попаданию в локальные оптимумы;
  • Они хорошо работают при решении крупномасштабных проблем оптимизации;
  • Могут быть использованы для широкого класса задач;
  • Просты и прозрачны в реализации;
  • Могут быть использованы в задачах с изменяющейся средой.

Недостатки генетических алгоритмов?

Не желательно и проблематично использовать ГА:

  • В случае когда необходимо найти точный глобальный оптимум;
  • Время исполнения функции оценки велико;
  • Необходимо найти все решения задачи, а не одно из них;
  • Конфигурация является не простой (кодирование решения).
Alexander Pavlov [2:5030/399.11]

Необходимость поиска всех решений не является помехой. Исаев (статьи на www.algo.4u.ru) пишет: "...существует, по кpайней меpе, тpи класса задач, котоpые могут быть pешены пpедставленным алгоpитмом:

  • задача быстpой локализации одного оптимального значения,
  • задача опpеделения нескольких (или всех) глобальных экстpемумов (!),
  • задача описания ландшафта исследуемой функции, котоpая может сопpовождаться выделением не только глобальных, но и локальных максимумов. ..."

    Для pешения втоpой задачи, очевидно, вопpосу "исследования" пpостpанства поиска должно уделяться гоpаздо большее внимание. Оно достигается за счет дpугого сочетания паpаметpов и достаточно большой численности популяции, пpи этом ГА сможет выделить несколько (или даже все) глобальные экстpемумы ...

    Для выделения нескольких глобальных максимумов, лучше использовать такую комбинацию [паpаметpов]: аутбpидинг в сочетании с инбpидингом, в качестве естественного отбоpа достаточно использовать элитный отбоp или отбоp с вытеснением (последний более надежный). Максимальная эффективность поиска достигается в сочетании аутбpидинга и инбpидинга, пpичем аутбpидинг pекомендуется использовать в начале поиска, достигая максимально шиpокого "исследования", а завеpшать поиск лучше уточнением pешения в локальных гpуппах, используя инбpидинг."

    Что такое простейший генетический алгоритм, схема, теорема Холланда?

    В.М. Курейчик, статья

    Механизм простого ГА (ПГА) несложен. Он копирует последовательности и переставляет их части. Предварительно ГА случайно генерирует популяцию последовательностей - стрингов (хромосом). Затем ГА применяет множество простых операций к начальной популяции и генерирует новые популяции.

    ПГА состоит из 3 операторов: репродукция, кроссинговер, мутация.

    Репродукция - процесс, в котором хромосомы копируются согласно их целевой функции (ЦФ). Копирование хромосом с "лучшим" значением ЦФ имеет большую вероятность для их попадания в следующую генерацию. Оператор репродукции (ОР), является искусственной версией натуральной селекции, "выживания сильнейших" по Дарвину.

    После выполнения ОР оператор кроссинговера (ОК) может выполниться в несколько шагов На первом шаге выбираются члены нового репродуцированного множества хромосом. Далее каждая пара хромосом (стрингов) пересекается по следующему правилу: целая позиция k вдоль стринга выбирается случайно между l и длиной хромосомы минус единицу т.е. в интервале (1,L-1). Длина L хромосомы это число значащих цифр в его двоичном коде. Число k, выбранное случайно между первым и последним членами, называется точкой ОК или разделяющим знаком.

    Механизм ОР и ОК включает случайную генерацию чисел, копирование хромосом и частичный обмен информацией между хромосомами.

    Генерация ГА начинается с репродукции. Мы выбираем хромосомы для следующей генерации, вращая колесо рулетки, такое количество раз, которое соответствует мощности начальной популяции. Величину отношения Fi(x)/SumF(x) называют вероятностью выбора копий (хромосом) при ОР и обозначают Pi(OP). Здесь Fi(x) - значение ЦФ i-той хромосомы в популяции, SumF(x) - суммарное значение ЦФ всех хромосом в популяции. Величину Pi(OP) также называют нормализованной величиной.

    Ожидаемое число копий i-ой хромосомы после ОР определяют N=Pi(OP)*n. Здесь n - число анализируемых хромосом.

    Число копий хромосомы, переходящее в следующее положение, иногда определяют на основе выражения Ai=Fi(x)/СреднееFi(x).

    Далее, согласно схеме классического ПГА, выполняется оператор мутации. Считают, что мутация - вторичный механизм в ГА.

    Понятие "схема" (схемата), согласно Холланду, есть шаблон, описывающий подмножество стрингов, имеющих подобные значения в некоторых позициях стринга. Для этого вводится новый алфавит {0,1,*}, где * - означает: не имеет значения 1 или 0. Для вычисления числа схем или их границы в популяции требуются точные значения о каждом стринге в популяции.

    Для количественной оценки схем введены 2 характеристики: порядок схемы - О(H); определенная длина схемы - L(H).

    Порядок схемы - число закрепленных позиций (в двоичном алфавите - число единиц и нулей), представленных в шаблоне.

    Предположим, что заданы шаг (временной) t, m примеров частичных схем H, содержащихся в популяции A(t). Все это записывают как m=m(H,t) - возможное различное число различных схем H в различное время t.

    В течение репродукции стринги копируются согласно их ЦФ или более точно: стринг A(i) получает выбор с вероятностью, определяемой Pi(OP).

    После сбора непересекающихся популяций размера n с перемещением из популяции A(t) мы ожидаем иметь m(H,t+1) представителей схемы H в популяции за время t+1. Это вычисляется уравнением

                      m(H,t+1)=m(H,t)*n*f(H)/sum[f(j)] (1)
    
    где f(H) - есть средняя ЦФ стрингов, представленных схемой H за время t.

    Если обозначить среднюю ЦФ всей популяции как f`=sum[f(j)]/n, тогда

                           m(H,t+1)=m(H,t)*f(H)/f` (2)
    
    Правило репродукции Холланда: схема с ЦФ выше средней "живет", копируется и с ниже средней ЦФ "умирает".

    Предположим, что схема H остается с выше средней ЦФ с величиной c*f`, где c - константа. Тогда выражение (2) можно модифицировать так

                  m(H,t+1)=m(H,t)*(f`+c*f`)/f`=(1+c)*m(H,t) (3)
    
    Некоторые исследователи считают, что репродукция может привести к экспоненциальному уменьшению или увеличению схем, особенно если выполнять генерации параллельно.

    Отметим, что если мы только копируем старые структуры без обмена, поисковое пространство не увеличивается и процесс затухает. Потому и используется ОК. Он создает новые структуры и увеличивает или уменьшает число схем в популяции.

    Очевидно, что нижняя граница вероятности выживания схемы после применения ОК может быть вычислена для любой схемы. Так как схема выживает, когда точка ОК попадает вне "определенной длины", то вероятность выживания для простого ОК запишется

                               P(s)=1-L(H)/(L-1) (4)
    
    Если ОК выполняется посредством случайного выбора, например, с вероятностью P(ОК), то вероятность выживания схемы определится
                            P(s)=1-P(ОК)*L(H)/(L-1) (5)
    
    Допуская независимость репродукции (ОР) и ОК, получим:
                   m(H,t+1)=m(H,t)*f(H)/f`*[1-P(ОК)*L(H)/(l-L)] (6)
    
    Из выражения (6) следует, что схемы с выше средней ЦФ и короткой L(H) имеют возможность экспоненциального роста в новой популяции.

    Рассмотрим влияние мутации на возможности выживания.

    ОМ есть случайная альтернативная перестановка элементов в стринге с вероятностью Р(ОМ). Для того, чтобы схема H выжила, все специфические позиции должны выжить. Следовательно, единственная хромосома выживает с вероятностью (1-P(ОМ)) и частная схема выживает, когда каждая из l(H) закрепленных позиций схемы выживает.

    Тогда мы ожидаем, что частная схема H получает ожидаемое число копий в следующей генерации после ОР,ОК ОМ

             m(H,t+1) > m(H,t)*f(H)/f`*[1-Р(ОК)*l(H)/(l-1)-l(H)*P(ОМ)] (7)
    
    Это выражение называется "схема теорем" или фундаментальная теорема ГА.

    Ответа на вопрос, почему необходимо давать выживание схемам с лучшей ЦФ, нет или он расплывчатый, или каждый раз зависит от конкретной задачи.

    Основная теорема ГА, приведенная Холландом, показывает асимптотическое число схем "выживающих" при реализации ПГА на каждой итерации. Очевидно,что это число, конечно приблизительное и меняется в зависимости от вероятности применения ГА. Особенно сильное влияние на число "выживающих" и "умирающих" схем при реализации ПГА оказывает значение целевой функции отдельной хромосомы и всей популяции.

    Во многих проблемах имеются специальные знания, позволяющие построить аппроксимационную модель. При использовании ГА это может уменьшить объем и время вычислений и упростить моделирование функций, сократить число ошибок моделирования.

    В элитарном ПГА не ясна роль "не элитных" особей.

    Честно говоря, этот вопрос меня самого поставил в тупик. Прикинул так и этак - выходит что не нужны они.. Однако нельзя торопиться с выводами.

    Во-первых, многое зависит от процедуры добавления особей в популяцию. В зависимости от неё, неэлитные особи могут терять и приобретать значимость.

    И есть еще одно применение им. Если функция оценки особей (фитнесс) будет довольно медленной, то эти особи можно использовать в качестве кэша. Всилу особенностей работы ГА, будет весьма высокая вероятность появления решений из окрестности текущего оптимума, а значит можно ожидать повторения особей.

    Классический (одноточечный) кроссинговер.

    Дэвид Бисслей, статья

    "Традиционный" генетический алгоритм использует одноточечный кроссинговер, в котором две скрещивающиеся хромосомы разрезаются один раз в соответствующей точке и производится обмен полученными частями. Однако было изобретено много других различных алгоритмов с иными видами кроссинговера, часто включающих больше чем одну точку разреза. DeJong исследовал эффективность многоточечного кроссинговера и пришел к выводу, что двухточечный кроссинговер дает улучшение, но что дальнейшее добавление точек кроссинговера редуцирует деятельность генетического алгоритма. Проблема с добавлением дополнительных точек кроссинговера состоит в том, что стандартные блоки, вероятно, будут прерваны. Однако преимущество большего количества точек кроссинговера состоит в том, что пространство состояний может быть исследовано более полно и подробно.

    Двухточечный кроссинговер.

    Дэвид Бисслей, статья

    В двухточечном кроссинговере (и многоточечном кроссинговере вообще) хромосомы расцениваются как циклы, которые формируются соединением концов линейной хромосомы вместе. Для замены сегмента одного цикла сегментом другого цикла требуется выбор двух точек разреза. В этом представлении, одноточечный кроссинговер может быть рассмотрен как кроссинговер с двумя точками, но с одной точкой разреза, зафиксированной в начале строки. Следовательно, двухточечный кроссинговер решает ту же самую задачу, что и одноточечный кроссинговер , но более полно. Хромосома, рассматриваемая как цикл, может содержать большее количество стандартных блоков, так как они могут совершить "циклический возврат" в конце строки. В настоящий момент многие исследователи соглашаются, что двухточечный кроссинговер вообще лучше, чем одноточечный.

                    линейное представление:     УУУУУУУУУУУУ
                                                ------------>
    
                    циклическое представление: ->УУУУУУУУУУУУ-¬
                                               L---------------
    
    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, то ген копируется от второго родителя. Процесс повторяется с обмененными родителями для создания второго потомства. Новая маска кроссинговера случайно генерируется для каждой пары родителей.

    Дифференциальное скрещивание.

    Ilya S. Potrepalov [ispotrepalov@asu.tnk.ru]

    Существуют и другие методы скрещивания, а не только crossover. Hапример, для поиска минимума/максимума функции многих вещественных переменных наиболее удачным является "дифференциальное скрещивание". А именно, пусть a и b -- это два индивидуума в популяции, т.е. вещественные вектора от которых наша функция зависит. Тогда потомок c вычисляется по формуле с=a+k*(a-b), где k -- это некоторый вещественный коэффициент (который может завесить от ||a-b|| --растояния между векторами).

    В этой модели мутация -- это добавление к индивидууму случайного вектора малой длины. Если исходная функция непрерывна, то эта модель работает хорошо. А если она еще и гладкая, то -- превосходно.

    Исходники некоторых кроссинговеров.

    Вот вырезки из моих прог. Вполне можно прикрутить куда нужно :)

    Пояснения:

    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 анализируют оператор переупорядочения на очень маленькой задаче, показывая, что она может дать определенное преимущество, хотя они заключают, что их методы не принесли бы то же самое преимущество на больших задачах.

    Переупорядочение также значительно расширяет область поиска. Мало того, что генетический алгоритм пытается находить хорошие множества значений генов, он также одновременно пробует находить хорошее упорядочения генов. Это гораздо более трудная задача для решения.

    Что такое эпистаз?

    Дэвид Бисслей, статья

    Термин эпистаз был определен генетиками как влияние гена на пригодность индивидуума в зависимости от значения гена, присутствующего в другом месте. Более определенно, генетики используют термин эпистаз в смысле эффекта "переключения" или "маскирования". "Ген считают эпистатическим, когда его присутствие подавляет влияние гена в другом локусе. Эпистатические гены иногда называют ингибирующими из-за их влияния на другие гены, которые описываются как гипостаз".

    Когда исследователи генетических алгоритмов используют термин эпистаз, они говорят обо всем, что касается любого вида взаимодействия среди генов, не только эффекта маскирования, хотя они избегают давать точное определение.

    Что такое ложный оптимум?

    Дэвид Бисслей, статья

    Одним из фундаментальных принципов генетических алгоритмов является то, что хромосомы, включенные в шаблоны, которые содержатся в глобальном оптимуме, увеличиваются по частоте (это особенно верно для коротких, небольшого порядка шаблонов, известных как строительные блоки). В конечном счете, посредством использования кроссинговера, эти оптимальные шаблоны сойдутся, и будет создана глобальная оптимальная хромосома. Но если шаблоны, которые не содержатся в глобальном оптимуме, будут увеличивается по частоте быстрее чем другие, то генетический алгоритм будет введен в заблуждение и уйдет в другую сторону от глобального оптимума, вместо того, чтобы приблизится к нему. Это явление известно как ложный оптимум.

    Ложный оптимум является частным случаем эпистаза, и он был глубоко изучен Goldberg и другими. Ложный оптимум непосредственно связан с вредными влияниями эпистаза в генетических алгоритмах.

    По статистике, шаблон увеличится по частоте в популяции, если его пригодность выше, чем средняя пригодность всех шаблонов в популяции. Задача обозначается как задача ложного оптимума, если средняя пригодность шаблонов, которые не содержатся в глобальном оптимуме, больше, чем средняя пригодность других шаблонов.

    Задачи ложного оптимума трудны для решения. Однако, Grefenstette остроумно демонстрирует, что они возникают не всегда. После первого поколения, генетический алгоритм не получает объективную выборку точек в области поиска. Поэтому он не может оценивать объективную глобальную среднюю пригодность шаблона. Он может только получить необъективную оценку пригодности шаблона. Иногда это предубеждение помогает генетическому алгоритму сходиться (даже при том, что задача иначе могла бы иметь сильный ложный оптимум).

    Что такое инбридинг, аутбридинг, селективный выбор, панмиксия?

    Существует несколько подходов к выбору родительской пары. Наиболее простой из них - панмиксия. Этот подход предполагает случайный выбор родительской пары, когда обе особи, которые составят родительскую пару, случайным образом выбираются из всей популяции. В этом случае любая особь может стать членом нескольких пар. Несмотря на простоту, такой подход универсален для решения различных классов задач. Однако он достаточно критичен к численности популяции, поскольку эффективность алгоритма, реализующего такой подход, снижается с ростом численности популяции.

    Селективный способ выбора особей в родительскую пару состоит в том, что "родителями" могут стать только те особи, значение приспособленности которых не меньше среднего значения приспособленности по популяции, при равной вероятности таких кандидатов составить брачную пару.

    Такой подход обеспечивает более быструю сходимость алгоритма. Однако из-за быстрой сходимости селективный выбор родительской пары не подходит тогда, когда ставиться задача определения нескольких экстремумов, поскольку для таких задач алгоритм, как правило, быстро сходится к одному из решений. Кроме того, для некоторого класса задач со сложным ландшафтом приспособленности быстрая сходимость может превратиться в преждевременную сходимость к квазиоптимальному решению. Этот недостаток может быть отчасти компенсирован использованием подходящего механизма отбора, который бы "тормозил" слишком быструю сходимость алгоритма.

    Инбридинг представляет собой такой метод, когда первый член пары выбирается случайно, а вторым с большей вероятностью будет максимально близкая к нему особь.

    Пример определения родства хромосом при выборе родительской пары для хромосомы 1010001:

                Хромосомы популяции         Количество отличающихся локусов
                     1000000                              2
                     1010101                              1
                     0011100                              4
                     0000001                              2
                     0110011                              3
                     0100011                              4
                     1111111                              4
                     0000000                              3
    
    При аутбридинге также используют понятие схожести особей. Однако теперь брачные пары формируют из максимально далеких особей.

    Последние два способа по-разному влияют на поведение генетического алгоритма. Так инбридинг можно охарактеризовать свойством концентрации поиска в локальных узлах, что фактически приводит к разбиению популяции на отдельные локальные группы вокруг подозрительных на экстремум участков ландшафта. Аутбридинг же направлен на предупреждение сходимости алгоритма к уже найденным решениям, заставляя алгоритм просматривать новые, неисследованные области.

    Alexander Pavlov [2:5030/399.11]

    По поводу источника. Hачало, по кpайней меpе, с www.algo.4u.ru, статья Д.И. Батищева, С.А. Исаева "Оптимизация многоэкстpемальных функций с помощью генетических алгоpитмов" (опубликовано в сбоpнике статей, издаваемом ВГТУ, осень 1997).

    Динамическая самоорганизация параметров ГА.

    Зачастую, выбор параметров генетического алгоритма и конкретных генетических операторов производится на интуитивном уровне, так как пока не существует объективных доказательств преимущества тех или иных настроек и операторов. Однако, не нужно забывать, что сама суть ГА заключается в динамике и "мягкости" алгоритма и производимых вычислений. Тогда почему бы не позволить алгоритму самому настраиваться во время решения задачи и адаптироваться к ней?

    Наиболее просто организовать адаптацию применяемых операторов. Для этого встроим в алгоритм несколько (чем больше тем лучше) различных операторов выборки (элитная, случайная, рулеточная,..), кроссинговера (одноточечный, двухточечный, унифицированный,..) и мутации (случайная одноэлементная, абсолютная,..). Установим для каждого оператора равные вероятности применения. Далее, на каждом цикле алгоритма будем выбирать один из операторов каждой группы (выбор, кроссинговер, мутация) соответственно вероятностному распределению. Причем, в полученной при помощи этих операторов особи отметим, какими именно операторами она была получена. Тогда, если новое распределение вероятностей мы вычислим исходя из информации, содержащейся в популяции (вероятность применения оператора пропорциональна числу особей в популяции, полученных при помощи этого оператора), то генетический алгоритм получит механизм динамической самоадаптации.

    Такой подход дает еще одно преимущество - теперь не нужно беспокоиться о применяемом генераторе случайных чисел (линейный, экспоненциальный и т.д.), так как алгоритм динамически изменяет характер распределения.

    Метод миграции и искусственной селекции.

    В.В Курейчик, статья

    В отличие от обыкновенных ГА выполняется макроэволюция, т.е. создается не одна популяция, а некоторое множество популяций. Генетический поиск здесь осуществляется путем объединения родителей из различных популяций.

    Метод прерывистого равновесия.

    В.В Курейчик, статья

    Метод основан на палеонтологической теории прерывистого равновесия, которая описывает быструю эволюцию за счет вулканических и других изменений земной коры. Для применения данного метода в технических задачах предлагается после каждой генерации случайным образом перемешивать индивидуальности в популяции, а затем формировать новые текущие генерации. Здесь можно предложить, как аналог из живой природы, бессознательный отбор родительских пар и синтетический отбор лучших родительских пар. Далее случайным образом смешать результаты обоих отборов и не оставлять размер популяции постоянным, а управлять им в зависимости от наличия лучших индивидуальностей. Такая модификация метода прерывистого равновесия может позволить сократить неперспективные популяции и расширить популяции, в которых находятся лучшие индивидуальности.

    Метод прерывистого равновесия - это мощный стрессовый метод изменения окружающей среды, который используется для эффективного выхода из локальных ям.

    Почему у меня популяция пpи малых размерах вообще не сходится?

    В популяциях с малым размером гены распространяются слишком быстро. Все особи становятся похожими (популяция сошлась) еще до того, как найдено решение задачи. Получается так, что новый генотип с лучшей оценкой быстро вытесняет менее хорошие комбинации ген, исключая таким образом возможность получения более хорошего решения на их базе.

    Вторая проблема заключается в том, что потомки, получаемые в большей популяции, скорее всего будут разнообразнее, чем потомки из меньшей популяции. С одной стороны, при малых популяциях внимание алгоритма будет сконцентрировано на некоторых направлениях, то есть, эти направления будут изучены быстрей. Но если направление изначально было ошибочным (ложный оптимум) то алгоритм имеет все шансы застрять.

    Выходом может быть увеличение популяции, при условии что время работы алгоритма не критично.

    Также, может помочь самоадаптация алгоритма при выборе операторов (в тупиковых ситуациях увеличить вероятность применения случайного генератора особей).

    Еще можно попытаться складировать отдельно особи, генотип которых был утерян популяцией, и временами добавлять эти особи (случай удачного кровосмешения в племенных формациях).

    Разное.

    vitalie vrabie [2:469/303]

    ГА, однородный побитовый recombination, elitistic selection, все вектора одинакового размера.

    Ввёл такое понятие: "однородность" (степень однородности) популяции. Определяется отношением количества одинаковых битов к общему их числу в векторе.

    Поясню на примере. Скажем, вектор из 10 бит. При следующей популяции:

                                    0101011100
                                    1100010100
                                    0101011110
                                     ^^ ^^ ^ ^
    
    Имеем "однородность" равную 6/10 (шесть из десяти битов у всех одинаковые - в помеченных позициях).

    "Однородность" вычисляю перед каждой итерацией и использую как вероятность мутации. То есть, чем однороднее (скуднее) генофонд, тем выше вероятность мутаций.

    ГА не рекомендуется, если нужно найти точный глобальный экстремум. Почему?

    Это не совсем так... То есть, это не значит что ГА не сможет найти его, совсем нет... Просто ГА не может определить когда он нашел точное глобальное решение.. Часто используют эффект сходимости популяции (когда особи становятся одинаковыми), это позволяет организовать остановку алгоритма, но не гарантирует глобальность решения.

    На каких функциях проверить мой генетический алгоритм?

    Первую проверку можно сделать на простых функциях с известным птимумом - на пример синус, косинус и т.д. Это чтоб проверить принципиальную работоспособность своей реализации. Следующий шаг - проверка на сложных функциях с известным оптимумом. При этом не нужно ожидать точного их решения, т.к. они действительно сложные. Нас в этом случае интересуют такие параметры, как время поиска и качество поиска - они обычно используются для выявления наилучшей конфигурации алгоритма или для его сравнения с другими алгоритмами. Вот известные функции:

    • Функция Растригина. Число переменных 2. Максимумов - 96 локальных, 4 глобальных.
          #define PI 3.14159265358979323846
          y=20+x[0]*x[0]+x[1]*x[1]-10*cos(2*PI*x[0])-10*cos(2*PI*x[1]);
      
          Пространство: -5.12<=x[t]<=5.12
          Максимум: F(4.52299,4.52299)  =80.7065
                    F(-4.52299,4.52299) =80.7065
                    F(4.52299,-4.52299) =80.7065
                    F(-4.52299,-4.52299)=80.7065
      
    • Griewank. Число переменных 2. Максимумов - множество локальных и 1 глобальный.
          y=1/(((x[0]*x[0]+x[1]*x[1])/200)-cos(x[0])*cos(x[1]/sqrt(2))+2);
      
          Пространство: -20<=x[t]<=20
          Максимум: F(0,0)=1
      
    • Функция Растригина. Число переменных 10. Максимумов - (10^10)-1 локальных и 1 глобальный.
          #define PI 3.14159265358979323846
          y=-100;
          for(t=0;t<XNum;t++)y+=10*cos(2*PI*x[t])-x[t]*x[t];
      
          Пространство: -5.12<=x[t]<=5.12
          Максимум: F(0,..,0)=0
      

    Назад | Оглавление | Далее
  • Оставить комментарий

    Комментарий:
    можно использовать BB-коды
    Максимальная длина комментария - 4000 символов.
     

    Комментарии

    1.
    96K
    20 декабря 2015 года
    Хеда Линкаева
    0 / / 20.12.2015
    Мне нравитсяМне не нравится
    20 декабря 2015, 15:39:36
    Lllll
    Реклама на сайте | Обмен ссылками | Ссылки | Экспорт (RSS) | Контакты
    Добавить статью | Добавить исходник | Добавить хостинг-провайдера | Добавить сайт в каталог