Глава 1. Генетические алгоритмы

1.1 Естественный отбор в природе

1.2 Представление объектов. Кодирование признаков

1.3 Основные генетические операторы

1.4 Схема функционирования генетического алгоритма

Глава 2. Задачи оптимизации

2.1 Задачи, решаемые с помощью генетических алгоритмов

2.2 Математическая постановка задачи оптимизации

2.3 Решение Диофантова уравнения

2.4 Пути решения задач оптимизации

2.5 Задача коммивояжера

Глава 3. Программная реализация. Создание пособия по генетическим алгоритмам

3.1 Обоснование выбора программного обеспечения

3.2 Описание программной реализации

Заключение

1.1. Естественный отбор в природе

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

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

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

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

При наследовании возможны мутации из-за радиоактивности или других влияний, в результате которых могут измениться некоторые гены в половых клетках одного из родителей. Измененные гены передаются потомку и придают ему новые свойства. Если эти новые свойства полезны, они, скорее всего, сохранятся в данном виде - при этом произойдет скачкообразное повышение приспособленности вида. Впервые подобный алгоритм был предложен в 1975 году Джоном Холландом (John Holland) в Мичиганском университете. Он получил название «репродуктивный план Холланда» и лег в основу практически всех вариантов генетических алгоритмов . Однако, перед тем как мы его рассмотрим подробнее, необходимо остановится на том, каким образом объекты реального мира могут быть закодированы для использования в генетических алгоритмах.

1.2. Представление объектов. Кодирование признаков

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

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

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

Таким образом, для того, чтобы определить фенотип объекта (то есть значения признаков, описывающих объект) нам необходимо только знать значения генов, соответствующим этим признакам, то есть генотип объекта. При этом совокупность генов, описывающих генотип объекта, представляет собой хромосому. В некоторых реализациях ее также называют особью. Таким образом, в реализации генетического алгоритма хромосома представляет собой битовую строку фиксированной длины. При этом каждому участку строки соответствует ген. Длина генов внутри хромосомы может быть одинаковой или различной. Чаще всего применяют гены одинаковой длины. Рассмотрим пример хромосомы и интерпретации ее значения. Допустим, что у объекта имеется 5 признаков, каждый закодирован геном длинной в 4 элемента. Тогда длина хромосомы будет 5*4=20 бит

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

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

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

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

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

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

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

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

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

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

Теги: Добавить метки

Идея генетических алгоритмов (ГА) появилась достаточно давно (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. Комбинирование первых трех способов создания популяции.

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

В последнее время все больше «ходят» разговоры про новомодные алгоритмы, такие как нейронные сети и генетический алгоритм. Сегодня я расскажу про генетические алгоритмы, но давайте на этот раз постараемся обойтись без заумных определений и сложных терминах.
Как сказал один из великих ученных: «Если вы не можете объяснить свою теорию своей жене, ваша теория ничего не стоит!» Так давайте попытаемся во всем разобраться по порядку.

Щепотка истории

Как говорит Википедия: «Отец-основатель генетических алгоритмов Джон Холланд, который придумал использовать генетику в своих целях аж в 1975 году». Для справки в этом же году появился Альтаир 8800, и нет, это не террорист, а первый персональный компьютер. К тому времени Джону было уже целых 46 лет.

Где это используют

Поскольку алгоритм самообучающийся, то спектр применения крайне широк:

• Задачи на графы
• Задачи компоновки
• Составление расписаний
• Создание «Искусственного интеллекта»

Принцип действия

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

• Скрещивание
• Селекция (отбор)
• Формирования нового поколения

Если результат нас не устраивает, эти шаги повторяются до тех пор, пока результат нас не начнет удовлетворять или произойдет одно из ниже перечисленных условий:

• Количество поколений (циклов) достигнет заранее выбранного максимума
• Исчерпано время на мутацию

Более подробно о шагах

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

Практика

Вы успешно прослушали «сказку» про чудо-алгоритм и вполне возможно заждались, когда мы его начнем эксплуатировать наконец, хочу вас обрадовать, время настало.
Давайте рассмотрим на примере моих любимых Диофантовых уравнений (Уравнения с целочисленными корнями).
Наше уравнение: a+2b+3c+4d=30
Вы наверно уже подозреваете, что корни данного уравнения лежат на отрезке , поэтому мы берем 5
случайных значений a,b,c,d. (Ограничение в 30 взято специально для упрощения задачи)
И так, у нас есть первое поколение:

1. (1,28,15,3)
2. (14,9,2,4)
3. (13,5,7,3)
4. (23,8,16,19)
5. (9,13,5,2)

Для того чтобы вычислить коэффициенты выживаемости, подставим каждое решение в выражение. Расстояние от полученного значения до 30 и будет нужным значением.

1. |114-30|=84
2. |54-30|=24
3. |56-30|=26
4. |163-30|=133
5. |58-30|=28

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

1. (1/84)/0.135266 = 8.80%
2. (1/24)/0.135266 = 30.8%
3. (1/26)/0.135266 = 28.4%
4. (1/133)/0.135266 = 5.56%
5. (1/28)/0.135266 = 26.4%

Далее будем выбирать пять пар родителей, у которых будет ровно по одному ребенку. Давать волю случаю мы будем давать ровно пять раз, каждый раз шанс стать родителем будет одинаковым и будет равен шансу на выживание.
3-1, 5-2, 3-5, 2-5, 5-3
Как было сказано ранее, потомок содержит информацию о генах отца и матери. Это можно обеспечить различными способами, но в данном случае будет использоваться «кроссовер». (| = разделительная линия)

• Х.-отец: a1 | b1,c1,d1 Х.-мать: a2 | b2,c2,d2 Х.-потомок: a1,b2,c2,d2 or a2,b1,c1,d1
• Х.-отец: a1,b1 | c1,d1 Х.-мать: a2,b2 | c2,d2 Х.-потомок: a1,b1,c2,d2 or a2,b2,c1,d1
• Х.-отец: a1,b1,c1 | d1 Х.-мать: a2,b2,c2 | d2 Х.-потомок: a1,b1,c1,d2 or a2,b2,c2,d1

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

• Х.-отец: (13 | 5,7,3) Х.-мать: (1 | 28,15,3) Х.-потомок: (13,28,15,3)
• Х.-отец: (9,13 | 5,2) Х.-мать: (14,9 | 2,4) Х.-потомок: (9,13,2,4)
• Х.-отец: (13,5,7 | 3) Х.-мать: (9,13,5 | 2) Х.-потомок: (13,5,7,2)
• Х.-отец: (14 | 9,2,4) Х.-мать: (9 | 13,5,2) Х.-потомок: (14,13,5,2)
• Х.-отец: (13,5 | 7, 3) Х.-мать: (9,13 | 5, 2) Х.-потомок: (13,5,5,2)

Теперь вычислим коэффициенты выживаемости потомков.

• (13,28,15,3) - |126-30|=96(9,13,2,4) - |57-30|=27
  (13,5,7,2) - |57-30|=22
  (14,13,5,2) - |63-30|=33
  (13,5,5,2) - |46-30|=16

  Печально так как средняя приспособленность (fitness) потомков оказалась 38.8, а у родителей этот коэффициент равнялся 59.4. Именно в этот момент целесообразнее использовать мутацию, для этого заменим один или более значений на случайное число от 1 до 30.
  Алгоритм будет работать до тех, пор, пока коэффициент выживаемости не будет равен нулю. Т.е. будет решением уравнения.
  Системы с большей популяцией (например, 50 вместо 5-и сходятся к желаемому уровню (0) более быстро и стабильно.

  Код

  На этом простота заканчивается и начинается чудесный C++...
  Класс на C++ требует 5 значений при инициализации: 4 коэффициента и результат. Для вышепривиденного примера это будет выглядеть так: CDiophantine dp(1,2,3,4,30);

  Затем, чтобы решить уравнение, вызовите функцию Solve(), которая возвратит аллель, содержащую решение. Вызовите GetGene(), чтобы получить ген с правильными значениями a, b, c, d. Стандартная процедура main.cpp, использующая этот класс, может быть такой:

  #include "" #include "diophantine.h" void main() { CDiophantine dp(1,2,3,4,30); int ans; ans = dp.Solve(); if (ans == -1) { cout << "No solution found." << endl; } else { gene gn = dp.GetGene(ans); cout << "The solution set to a+2b+3c+4d=30 is:\n"; cout << "a = " << gn.alleles << "." << endl; cout << "b = " << gn.alleles << "." << endl; cout << "c = " << gn.alleles << "." << endl; cout << "d = " << gn.alleles << "." << endl; } }

  Сам класс CDiophantine:

  #include #include #define MAXPOP 25 struct gene { int alleles; int fitness; float likelihood; // Test for equality. operator==(gene gn) { for (int i=0;i<4;i++) { if (gn.alleles[i] != alleles[i]) return false; } return true; } }; class CDiophantine { public: CDiophantine(int, int, int, int, int);// Constructor with coefficients for a,b,c,d. int Solve();// Solve the equation. // Returns a given gene. gene GetGene(int i) { return population[i];} protected: int ca,cb,cc,cd;// The coefficients. int result; gene population;// Population. int Fitness(gene &);// Fitness function. void GenerateLikelihoods(); // Generate likelihoods. float MultInv();// Creates the multiplicative inverse. int CreateFitnesses(); void CreateNewPopulation(); int GetIndex(float val); gene Breed(int p1, int p2); }; CDiophantine::CDiophantine(int a, int b, int c, int d, int res) : ca(a), cb(b), cc(c), cd(d), result(res) {} int CDiophantine::Solve() { int fitness = -1; // Generate initial population. srand((unsigned)time(NULL)); for(int i=0;i 25) break; } temppop[i] = Breed(parent1, parent2);// Create a child. } for(i=0;i

  Статья основана на материалах Википедии и сайта

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

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). Если мы принимаем такое толкование, то операторы скрещивания и мутации могут считаться операторами репродукции, а селекция - отбором особей (хромосом) для репродукции.