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

Кратко об алгоритме


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

Сама суть метода заключается в том, что мы модулируем эволюционный процесс: у нас есть какая-то популяция (набор векторов), которая размножается, на которую воздействуют мутации и производится естественный отбор на основании минимизации целевой функции. Рассмотрим подробнее эти процессы.

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

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

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

Вот описание классического генетического алгоритма, он прост в реализации и есть место для фантазии и исследований.

Постановка задачи


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

С точки зрения математики такая оптимизация — сущий пустяк. График такой функции представляет собой огромную многомерную «яму» (как трехмерный парабалоид на рисунке), в которую неизбежно скатишься, если идти по градиенту. Единственный локальный минимум является глобальным. image.

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

Реализация


Были реализованы все механизмы, описанные в первом параграфе. Размножение проводилось простым скрещиванием случайных пикселей от «мамы» и от «папы». Мутации производились путем изменения значения случайного пикселя у случайной особи на противоположное. А встряска производилась, если минимум не меняется на протяжении пяти шагов. Тогда производится «экстремальная мутация» — замена происходит более интенсивно, чем обычно.

В качестве исходных картинок я брал нонограмы («японские сканворды»), но, по правде говоря, можно брать просто черные квадраты — нет абсолютно никакой разницы. Ниже показаны результаты для нескольких изображений. Здесь для всех, кроме «домика», количество мутаций было 100 в среднем на каждую особь, особей в популяции было 100, при размножении популяция увеличивалась в 4 раза. Счастливчиков было 30% в каждой эпохе. Для домика значения были выбраны меньшие (30 особей в популяции, мутаций по 50 на особь).

image image image image

Экспериментально я установил, что использование «счастливчиков» в селекции понижает скорость стремления популяции к минимуму, но зато помогает выбираться из стагнации — без «счастливчиков» стагнация будет постоянна. Что можно увидеть из графиков: левый график — развитие популяции «фараона» со счастливчиками, правый — без счастливчиков.

imageimage

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

Глобальная оптимизация


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

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

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

image

Здесь популяция вымирает, и добавляется небольшой штраф (в размере обычного расстояния до известного минимума). Это сильно снижает вероятность повторов.

image

Более интересно, когда популяция не вымирает, а просто начинает подстрариваться под новые условия (след. рисунок). Это достигается при помощи штрафа в виде 0.000001 * sum ^ 4. В таком случае, новые образы становятся немного зашумлены:

image

Этот шум устраняется путем ограничения штрафа в max( 0.000001 * sum ^ 4, 20). Но мы видим, что четвертого локального минимума (динозавра) достичь не удается — скорее всего, потому, что он слишком близко расположен к какому-то другому.

image

Биологическая интерпретация


image

Какие же выводы мы можем сделать из, не побоюсь этого слова, моделирования? Прежде всего, мы видим, половое размножение — важнейший двигатель развития и приспосабливаемости. Но только его не достаточно. Роль случайных, маленьких изменений чрезвычайна важна. Именно они обеспечивают возникновение новых видов животных в процессе эволюции, а у нас обеспечивает разнообразие популяции.

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

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

P.S.


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

Исходный код
function res = genetic(file)
%generating
    global A B;
    im2line(file);
    dim = length(A(1,:)); count = 100; reprod = 4; mut = 100; select = 0.7; stagn = 0.8;
    pop = round(rand(count,dim));
    res = []; B = []; localmin = []; localcount = [];
    for k = 1:300
%reproduction  
        for j = 1:count * reprod
            pop = [pop; crossingover(pop(floor(rand() * count) + 1,:),pop(floor(rand() * count) + 1,:))];
        end
%mutation
        
        idx = 10 * (length(res) > 5 && std(res(1:5)) == 0) + 1;
        for j = 1:count * mut
            a = floor(rand() * count) + 1;
            b = floor(rand() * dim) + 1;
            pop(a,b) = ~pop(a,b);
        end
%selection
        val = func(pop);
	val(1:count) = val(1:count) * 10;
        npop = zeros(count,dim);
        [s,i] = sort(val);
        res = [s(1) res];
        opt = pop(i(1),:);
        fn = sprintf('result/%05d-%d.png',k,s(1));
        line2im(opt*255,fn);
        if (s(1) == 0 || localcount > 10)
	    localmin = []; localcount = [];
	    B = [B; opt];
	%   pop = round(rand(count,dim));
	    continue;
    %       break;
        end
        for j = 1:floor(count * select)
            npop(j,:) = pop(i(j),:);
        end
%adding luckers
        for j = (floor(count*select)+1) : count
            npop(j,:) = pop(floor(rand() * count) + 1,:);
        end
%fixing stagnation
        if (length(res) > 5 && std(res(1:5)) == 0)
	      if (localmin == res(1))
		      localcount = localcount+1;
	      else
		      localcount = 1;
	      end
	      localmin = res(1);
              for j = 1:count*stagn
                  a = floor(rand() * count) + 1;
                  npop(a,:) = crossingover(npop(a,:),rand(1,dim));
              end
        end
        pop = npop;
    end
    res = res(length(res):-1:1);
end


function res = crossingover(a, b)
    x = round(rand(size(a)));
    res = a .* x + b .* (~x);
end

function res = func(v)
    global A B;
    res = inf;
    for i = 1:size(A,1)
	res = min(res,sum(v ~= A(i,:),2));
    end
    for i = 1:size(B,1)
	res = res + max(0.000001 * sum(v == B(i,:),2) .^ 4,20);
    end
end

function [] = im2line(files)
global A sz;
A = [];
files = cellstr(files);
for i = 1:size(files,1)
	imorig = imread(char(files(i,:)));
	sz = size(imorig);
	A = [A; reshape(imorig,[1 size(imorig,1)*size(imorig,2)])];
end
A = A / 255;
end

function [] = line2im(im,file)
global sz;
imwrite(reshape(im*255,sz),file);
end

Комментарии (12)


  1. rma4ok
    02.04.2015 18:48
    +9

    Эта статья №4 в Google по запросу «голимые матрицы»


    1. mifki
      02.04.2015 19:12
      +9

      Уже (или у меня) — первая. Но ирония в том, что правильно пишется «галимые».


  1. OlegUV
    02.04.2015 20:37
    +5

    Хотелось бы больше деталей, а то получается «Берём песок, старый аккумулятор и немного цветмета — и вот у нас готова хрустальная люстра». Что есть особь, как она записывается на бумаге символами, какой вообще аппарат аналитических выкладок, как происходит мутация — запись формулами и т.д. Всего этого не хватает, а почитал бы с большим удовольствием.


    1. unciia Автор
      02.04.2015 21:27
      +3

      Особь — это просто вектор, содержащий нули или единицы. Мы показываем его в виде изображения. Как раз гифки показывают лучшую особь в каждой эпохе.
      «Мутации производились путем изменения значения случайного пикселя у случайной особи на противоположное». Как говорится, берем и меняем.
      Что касается аналитических выкладок — не очень понял, о чем вы.


      1. OlegUV
        03.04.2015 07:15

        Вот, уже понятнее! Но всё равно, вопросов масса, просто идём по тексту дальше, и по ходу:

        > Здесь для всех, кроме «домика», количество мутаций было 100 в среднем на каждую особь, особей в популяции было 100, при размножении популяция увеличивалась в 4 раза.

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

        и т.д.
        В тексте полно мест, вызывающих массу вопросов у людей не знакомых с генетическими алгоритмами…

        Обязательно продолжайте писать про генетику — это очень интересно.


        1. unciia Автор
          03.04.2015 08:21

          Во все процессы добавлен элемент случайности. Так, при размножении выбирается 4*N раз пара особей (случайно), и у них получается детеныш. Получается он путем случайного скрещивания каких-то элементов векторов — в таком дискретном пространстве это есть аналог среднего арифметического. Опять же мера скрещивания (в какой мере детеныш будет похож на одного из родителей) определяется случайно. Все распределения равномерны.

          Далее просто ведется сортировка и отбирается 70% из «топа». Остальные 30% забиваются случайно — я показал, что такие «счастливчики» очень важны, если мы реализуем встряску.

          Если что-то еще не понятно, расспрашивайте.


  1. bya
    03.04.2015 05:52
    +1

    Автор не написал самое главное. Но это не его вина. Практически все про это не пишут.
    Самое сложное и нетривиальное (в отличие от самого алгоритма) это правильно выбрать генетический код.

    1. Генетический код не обязан представлять решение задачи. Из него достаточно просто (относительно объема вычислений) должно строится решение и желательно, но не обязательно, однозначно.

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

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


    1. unciia Автор
      03.04.2015 08:30

      У меня как раз получается задача ставится очень просто: устремить генетический код к некоторому значению. Я сделал так, что вот есть лучший экземпляр, к нему можно как-то стремиться, а уж по каким требованиям он является лучшим — это не моя забота. Задача очень формализована.

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


  1. nemilya
    03.04.2015 09:14

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

    Если мы ждем появления буквы А — то ведь все другие варианты тоже должны присутствовать.


    1. unciia Автор
      03.04.2015 09:56

      Тут случайности контроллируемые. Т.е. на каждом шаге у нас все ближе и ближе к искомой картинке. Тут нет полного перебора всех варинатов


  1. iroln
    03.04.2015 14:11

    Раз уж реализовали на языке Matlab, не пробовали забавы ради сравнить свою реализацию с реализацией ГА из Global Optimization Toolbox? Вот документация: www.mathworks.com/help/gads/ga.html
    www.mathworks.com/help/gads/genetic-algorithm.html

    Я когда-то возился с ГА, ради интереса пробовал использовать его для оптимизации параметров стеганографического контейнера, но практического смысла особо не узрел. Надёжнее использовать какой-нибудь pattern search метод, вроде такого:
    www.mathworks.com/help/gads/particle-swarm.html
    www.norg.uminho.pt/aivaz/pswarm/


  1. optimizer
    11.04.2015 08:54

    я интересовался этой темой в конце 90-х начале 2000-х, и тогда не попадался на глаза прием со «счастливчиками», наоборот, протаскивали «элит» (по блату так сказать). Прям прогресс в демократии :)