Экстерналии генетический алгоритм статьи. Генетический алгоритм — наглядная реализация

  • Программирование

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

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

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

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

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

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

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

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

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

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

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

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

    Реализация

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

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




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


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

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

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

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

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

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

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

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

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


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

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

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

    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 = ; 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); = sort(val); 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 = ; % 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 = )]; end A = A / 255; end function = line2im(im,file) global sz; imwrite(reshape(im*255,sz),file); end

    Теги:

    • генетический алгоритм
    • многомерная оптимизация
    • эволюция
    • matlab
    Добавить метки

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

    Часть первая. Жизнь и творчество генетического алгоритма.

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

    Если ситуация простая, и решение такой задачи можно явно посчитать из условий при помощи этих ваших матанов, то и славно, тут и без наших премудростей все хорошо, нас наебали, все расходимся. Например, при решении квадратного уравнения ответ (значения x1, x2) получаются из начального условия (коэффициентов a, b, c) путем применения формулы, которую мы все учили в школе. А что делать в более печальном случае, когда нужной формулы в учебнике нету? Можно попробовать с помощью мозгового штурма решить одну из задач. Аналитически. Численными методами. Силой отчаянного перебора функций. Через некоторое время послышатся мечтательное студенческое «хоть бы оно само решилось». Ага, тут-то мы и вылезаем из-за занавесок. Итак, цель - написать программу, которая бы находила функцию (программу), получающую на вход исходные данные и возвращающую годные циферки. Сила метапрограммирования, в бой!

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

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

    Искусство спаривания программ

    Думаю, многие из нас иногда испытывают жгучее желание применить к программам насильственное действие сексуального характера. Тут мы вынуждены заранее предупредить, что у нас такие межвидовые девиации не поощряются. У нас всё как завещала католическая церковь: программа с программой, только после брака… и партнеров не меняют, даже если тот томный парень купил тебе коктейль в баре. Хотя нет, вру, многоженство гаремного типа процветает. Да, и еще, несмотря на применение ниже таких слов как «отец» или «сын», программы у нас гермафродиты. Ну и инцест тоже… Тьфу, и я еще о церкви говорил *facepalm*. Ладно, об этом позже.

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

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

    Например: некоторая особь-программа square из двух выражений, пытающаяся (не особо удачно) решить квадратное уравнение:
    function square(a, b, c){ x1 = min(sin(b)*(a+1), 0); x2 = 3 + exp(log(b*a)); return {x1, x2}; }
    С представлением определились, теперь надо разобраться с хранением. Так как вокруг этих самых программ еще предстоит множество плясок, в том числе передача их из одной часть системы в другую (которые, вообще говоря, в моем случае вообще были написаны на разных языках), то хранение нашей особи в виде дерева не очень-то удобное. Для представления более удобным способом (идеально - набор строк над некоторым конечным алфавитом) нашу особь-программу-набор_деревьев придется научиться кодировать/раскодировать.

    Вроде как дерево, а вроде и нет
    Итак, надо представить дерево в виде строки. Тут нас выручит сила karva-деревьев. Для начала стоит определиться с набором функций, переменных и констант, которые могут попасться в дереве. Переменные и константы соответствуют листьям дерева и будут называться терминалами, функции - остальным (внутренним) узлам дерева, именуются нетерминалами. Так же стоит обратить внимание на то, что функции могут иметь разное количество аргументов, посему такие знания («арность», - тихо пробежало слово по губам знатоков) нам очень даже понадобятся. В итоге получается таблица кодировки, например, такая:

    Здесь n, +, *, if - функции; 2 - константа; a и b - переменные. В реальных задачах таблица поувесистей, с таким набором и квадратное уравнение не решить. Также надо иметь ввиду тот факт, что во избежании деления на нуль и других сценариев апокалипсиса все функции должны быть определены на всём множестве вещественных чисел (ну, или какое вы там множество используете в задаче). А то придется сидеть на карауле, отлавливать логарифмы от нуля и потом разбираться, что с этим делать. Мы люди не гордые, мы пойдем легким путем, исключая подобные варианты.

    Так вот, с помощью такой таблицы гонять функции из дерева в строку и обратно не проблема. Например, пришла нам такая строка на расшифровку:

    По таблице идентифицируем каждый элемент, вспоминаем также и про арность:

    Теперь при помощи арности расставляем ссылки на аргументы функций:

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

    Теперь если его потянуть вверх за первый элемент, то у нас в руке будет болтаться дерево выражения:

    Значение функции можно вычислить рекурсивным обходом по дереву, она у нас оказывается такой:

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

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

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

    Эй, эта девушка со мной!

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

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

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

    Функция приспособленности выдает каждой особи поколения некоторое число, показывающее ее полезность, приспособленность. Это значение будет влиять на процедуру отбора (селекции): чем больше у особи это значение, тем больше у нее вероятность найти пару для скрещивания (и даже не одну). На практике, после вычисления приспособленности для всех особей поколения мы нормируем эти значения (чтобы сумма приспособленностей особей равнялась 1) и для каждого из мест для поцелуев бросается жребий (случайное число от 0 до 1), определяющий счастливчика. Альфа-самец может получить себе несколько мест, неудачник ничего не получит и так и останется в одиночестве с потертым календариком 1994 года с Памеллой. Такой способ селекции называется «отбором методом рулетки», и схематично это выглядит как-то так:

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

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

    Сотворения мира и Апокалипсис

    Как переходить от поколения к поколению выяснили, теперь вопрос следующий - «а что стало первопричиной, с чего все началось?». В отличие от этого вашего мира, у нас для объяснения таких вещей не надо придумывать уловки типа «большого взрыва» или «7 дней». Тут ответ предельно ясен - всё началось с нулевого поколения, которое было сотворено случайным образом. Да-да, просто генерируем рандомом строки/деревья. Единственное требование - корректность особи, а насколько она ущербна - никого не волнует, отбор сделает свое дело.

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

    Эй, ты! Харошш парить мозг! Что в итоге-то?

    Сделаем паузу в этом увлекательном словоблудии и оглянемся назад (ну т.е. наверх). Если подводить итоги, то генетический алгоритм выглядит так:

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

    Часть вторая. Роль генетического алгоритма в образе бота Robocode.

    Что-то первая часть затянулась, мы все утомились, поэтому не будем повторяться. Также опустим некоторые особенности реализации.
    Узнать что такое Robocode можно тут: habrahabr.ru/blogs/programmers_games/59784 (картинки утеряны правда). Если коротко - эта программистская игра, изначально созданная для изучения особенностей языка Java, которая позволяет участникам создавать своих ботов-роботов и устраивать между ними бои. Каждый участник пишет код на Java, который управляет небольшим танком, и сражается с другими такими же танками.

    Перед нами стоит следующая задача: разработка при помощи генетического алгоритма автоматизированную системы управления ботом-танком. Робот должен создаваться и модифицироваться автоматически, т.е. в ходе своей эволюции «подстраиваться» под конкретного и заранее выбранного соперника в боях 1 на 1.

    Как представить решение задачи в виде особи

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

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

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

    Для составления таблицы кодирования необходимо определиться с набором базовых функций, переменных и констант.

    Функции:
    +(x, y) = x + y
    ++(x, y, z) = x + y + z
    n(x) = -x
    *(x, y) = x * y
    **(x, y) = x * y * z
    min(x, y) = x > y? y: x
    s(x) = 1/(1+exp(-x))
    if(x, y, z, w) = x > y? z: w

    Переменные:
    x, y - координаты танка соперника относительно нашего танка;
    dr - расстояние, которое осталось «доехать» нашему танку;
    tr - угол, на который осталось повернуться нашему танку;
    w - расстояние от нашего танка до края поля;
    dh - угол между направлением на танк соперника и пушкой нашего танка;
    GH - угол поворота пушки нашего танка;
    h - направление движения танка соперника;
    d - расстояние между нашим танком и танком соперника;
    e - энергия танка соперника;
    E - энергия нашего танка.

    Ну и константы: 0.5, 0, 1, 2, 10

    Функция приспособленности

    Опишем, как была выбрана функция приспособленности. Результаты боя «Robocode» формирует на основе множества нюансов. Это не только количество побед, но и всевозможные очки за активность, за выживаемость, за попадание в соперника и т.д. В итоге «Robocode» ранжирует роботов по параметру «total scores», который учитывает все вышеописанные тонкости. Его мы и будем использовать при подсчете приспособленности особи: итоговая приспособленность будет равняться доле в процентах очков нашего танка от суммы очков обеих танков, и принимает значение от 0 до 100. Соответственно, если значение приспособленности больше 50, то наш робот набрал больше очков, чем соперник, следовательно, сильнее его. Заметим, что согласно такой системе подсчета, первое место далеко не всегда занимает тот, кто победил в большинстве раундов боя. Ну тут мы разводим руками с фразой про мотороллер: создатели определили критерии, мы им следуем.

    Вообще говоря, вычисление приспособленности особи включает в себя проведение серии боев! Т.е. такой, казалось бы, незначительный пункт, как просчет приспособленности, состоит из таких плясок с бубном:
    1) Наша система сохраняет закодированные хромосомы особи в файл chromosome.dat;
    2) Для каждой особи запускается среда «Robocode», которая организовывает поединок. На вход ей мы подаем файл формата.battle, описывающий условия боя - список сражающихся танков, размеры поля, количество раундов и прочее;
    3) Для битвы Robocode загружает танки, наш робот-оболочка считывает файл chromosome.dat с закодированным поведением, интерпретирует его в набор действий и ведет согласно им бой;
    4) Среда Robocode по окончании поединка записывает результат битвы в файл results.txt и на этом завершает свою работу;
    5) Наша система подбирает этот файл, парсит и выделяет из него значения total score нашего танка и соперника. Путем нехитрой арифметики получаем значение приспособленности.

    Как наши их, да?

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

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

    В качестве результата продемонстрируем итоги создания соперника роботам Walls и Crazy:




    В первом случае мы остановили процесс после достижения одной из особей приспособленности рубежа 70, во втором нам было достаточно, что средняя приспособленности особей поколения превышает 50.

    После созерцания промыть глаза спиртом

    Если кто не боится плакать кровавыми слезами в конвульсиях от созерцания быдлокодинга (особенно волосы начнут шевелиться от кода робота - у нас с java взаимная ненависть), то прикрепляю

    Основной (классический) генетический алгоритм (также называемый элементарным или простым генетическим алгоритмом) состоит из следующих шагов:

    1) инициализация, или выбор исходной популяции хромосом;

    2) оценка приспособленности хромосом в популяции;

    3) проверка условия остановки алгоритма;

    4) селекция хромосом;

    5) применение генетических операторов;

    6) формирование новой популяции;

    7) выбор «наилучшей» хромосомы.

    Блок-схема основного генетического алгоритма изображена на рис. 4.3. Рассмотрим конкретные этапы этого алгоритма более подробно с использованием дополнительных подробностей, представленных на рис. 4.4.

    Рис. 4.3. Блок-схема генетического алгоритма.

    Рис. 4.4. Схема выполнения генетического алгоритма.

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

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

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

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

    , (4.2)

    , (4.3)

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

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

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

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

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

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

    1) потомок, хромосома которого на позициях от 1 до состоит из генов первого родителя, а на позициях от до - из генов второго родителя;

    2) потомок, хромосома которого на позициях от 1 до состоит из генов второго родителя, а на позициях от до - из генов первого родителя.

    Действие оператора скрещивания будет проиллюстрировано примерами 4.4 и 4.5 (п.п. 4.5 и 4.6).

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

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

    Выбор «наилучшей» хромосомы. Если условие остановки алгоритма выполнено, то следует вывести результат работы, т.е. представить искомое решение задачи. Лучшим решением считается хромосома с наибольшим значением функции приспособленности.

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

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

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

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

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

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

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

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

    ГА производит над особями следующие действия

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

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

    Целевая функция будет иметь вид

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

    Мутацией будет являться операция генерации нового случайного числа рассматриваемой популяции.

    Инверсия будет изменять значение хромосомы на некоторую небольшую величину, таким образом осуществляя поиск в окрестностях точки с наилучшим решением.
    Реализация на C++

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80

    #define _USE_MATH_DEFINES
    #include
    #include
    #include
    using namespace std;
    double func(double x)
    {
    return sin(M_PI * x / 180) - 1 / x;
    }
    double mutation(double x0, double x1) // мутация: генерация случайной величины
    {
    const int NUM = 100000000;
    return fabs((double )((rand() * NUM) % (int )((x1 - x0)*NUM) + 1) / NUM) + x0;
    }
    double inversion(double x, double eps) // инверсия: поиск в окрестностях точки
    {
    static int sign = 0;
    sign++;
    sign %= 2;
    if (sign == 0) return x - eps;
    else return x + eps;
    }
    void crossover(double *x, double eps, double x0, double x1) // кроссовер: среднее арифметическое
    {
    int k = 99;
    for (int i = 0; i < 8; i++)
    for (int j = i + 1; j < 8; j++)
    {
    x[k] = (x[i] + x[j]) / 2;
    k--;
    }
    for (int i = 0; i < 8; i++)
    {
    x[k] = inversion(x[i], eps); k--;
    }
    for (int i = 8; i < k; i++)
    x[i] = mutation(x0, x1);
    }
    void sort(double *x, double *y) // сортировка
    {
    for (int i = 0; i < 100; i++)
    for (int j = i + 1; j < 100; j++)
    if (fabs(y[j]) < fabs(y[i])) {
    double temp = y[i];
    y[i] = y[j];
    y[j] = temp;
    temp = x[i];
    x[i] = x[j];
    x[j] = temp;
    }
    }
    double genetic(double x0, double x1, double eps) // поиск решения с использованием ГА
    {
    double population;
    double f;
    int iter = 0;
    for (int i = 0; i < 100; i++) // Формирование начальной популяции
    {
    population[i] = mutation(x0, x1);
    f[i] = func(population[i]);
    }
    sort(population, f);
    do {
    iter++;
    crossover(population, eps, x0, x1);
    for (int i = 0; i < 100; i++)
    f[i] = func(population[i]);
    sort(population, f);
    } while (fabs(f) > eps && iter<20000);
    cout << iter << " iterations" << endl;
    return population;
    }
    int main()
    {
    srand(time(NULL ));
    cout << genetic(1.0, 10.0, 0.000001);
    cin.get();
    return 0;
    }

    Результат выполнения

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

    Идея генетических алгоритмов (ГА) появилась достаточно давно (1950-1975 гг.), но по-настоящему объектом изучения они стали только в последние десятилетия. Первооткрывателем в этой области признано считать Д. Холланда, который позаимствовал многое из генетики и адаптировал под вычислительные машины. ГА широко используются в системах искусственного интеллекта, нейронных сетях и задачах оптимизации.

    Эволюционный поиск

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

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

    Зачем нужны генетические алгоритмы

    ГА преследуют следующие цели:

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

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

    Особенности ГА

    Перечислим главные отличия ГА от большинства других методов поиска оптимального решения.

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

    Критерии работы

    Генетические алгоритмы производят расчеты исходя из двух условий:

    1. Выполнение заданного числа итераций.
    2. Качество найденного решения соответствует требованиям.

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

    Базовая терминология

    Ввиду того, что ГА основаны на генетике, то и большая часть терминологии соответствует ей. Любой генетический алгоритм работает исходя из начальной информации. Множество начальных значений есть популяция П t = {п 1 , п 2 , ..., п n }, где п i = {г 1 , ..., г v }. Разберем подробнее:

    • t - это номер итерации. t 1 , ..., t k - означает итерации алгоритма с номера 1 по k, и на каждой итерации создается новая популяция решений.
    • n - размер популяции П t .
    • п 1 , ..., п i - хромосома, особь, или организм. Хромосома или цепочка - это закодированная последовательность генов, каждый из которых имеет порядковый номер. При этом следует иметь в виду, что хромосома может быть частным случаем особи (организма).
    • г v - это гены, являющиеся частью закодированного решения.
    • Локус - это порядковый номер гена в хромосоме. Аллель - значение гена, которое может быть как числовым, так и функциональным.

    Что значит "закодированный" в контексте ГА? Обычно любое значение кодируется на основе какого-либо алфавита. Простейшим примером является перевод чисел из десятеричной системы счисления в двоичное представление. Таким образом алфавит представляется как множество {0, 1}, а число 157 10 будет кодироваться хромосомой 10011101 2 , состоящей из восьми генов.

    Родители и потомки

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

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

    Функция приспособленности

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

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

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

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

    Базовый генетический алгоритм

    Разложим по шагам наиболее простой (классический) ГА.

    1. Инициализация начальных значений, то есть определение первичной популяции, того множества особей, с которыми будет происходить эволюция.
    2. Установление первичной приспособленности каждой особи в популяции.
    3. Проверка условий прекращения итераций алгоритма.
    4. Использование функции селекции.
    5. Применение генетических операторов.
    6. Создание новой популяции.
    7. Шаги 2-6 повторяются в цикле до выполнения необходимого условия, после чего происходит выбор наиболее приспособленной особи.

    Пройдемся вкратце по мало очевидным частям алгоритма. Условий прекращения работы может быть два:

    1. Количество итераций.
    2. Качество решения.

    Генетическими операторами является оператор мутаций и оператор скрещивания. Мутация изменяет случайные гены с определенной вероятностью. Как правило, вероятность мутации имеет низкое числовое значение. Поговорим подробнее о процедуре генетического алгоритма "скрещивание". Он происходит по следующему принципу:

    1. Для каждой пары родителей, содержащих L генов, случайным образом выбирается точка скрещивания Тск i .
    2. Первый потомок составляется путем присоединения к генам первого родителя [Тск i+1 ; L] генов второго родителя.
    3. Второй потомок составляется обратным путем. Теперь к генам второго родителя добавляется гены первого родителя на позициях [Тск i+1 ; L].

    Тривиальный пример

    Решим задачу генетическим алгоритмом на примере поиска особи с максимальным числом единиц. Пусть особь состоит из 10 генов. Зададим первичную популяцию в количестве восьми особей. Очевидно, наилучшей особью должна быть 1111111111. Составим для решения ГА.

    • Инициализация. Выберем 8 случайных особей:

    Из таблицы видно, что особи 3 и 7 имеют наибольшее число единиц, а значит являются наиболее подходящими членами популяции для решения задачи. Так как на данный момент решения требуемого качества нет, алгоритм продолжает работу. Необходимо провести селекцию особей. Для простоты объяснения пусть селекция происходит случайным образом, и мы получаем выборку особей {п 7 , п 3 , п 1 , п 7 , п 3 , п 7 , п 4 , п 2 } - это родители для новой популяции.

    • Использование генетических операторов. Снова для простоты положим, что вероятность мутаций равна 0. Иными словами все 8 особей передают свои гены такими, какие есть. Для проведения скрещивания, составим пары особей случайным образом: (п 2 , п 7), (п 1 , п 7), (п 3 , п 4) и (п 3 , п 7). Так же случайным способом выбираются точки скрещивания для каждой пары:
    • Составление новой популяции, состоящей из потомков:

    Дальнейшие действия очевидны. Самое интересное в ГА открывается в случае, если оценить среднее количество единиц в каждой популяции. В первой популяции в среднем на каждую особь приходилось 5,375 единиц, в популяции потомков - 6,25 единиц на особь. И такая особенность будет наблюдаться даже в случае, если в ходе мутаций и скрещивания особь с наибольшим числом единиц в первой популяции потеряется.

    План реализации

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

    1. Определение представления (алфавита).
    2. Определение операторов случайных изменений.
    3. Определение выживания особей.
    4. Генерация первичной популяции.

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

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

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

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

    Эффективность

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

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

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