Рубрики
Без рубрики

Введение в генетические алгоритмы на Java

Автор оригинала: Darinka Zobenica.

Вступление

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

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

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

Основные Понятия

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

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

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

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

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

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

В качестве примера того, где вы можете применить генетический алгоритм, посмотрите на следующий график, представляющий 2D-карту высоты вершины скалы:

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

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

Генетическое представление

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

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

Распространенным способом представления генома является массив двоичных цифр. Это представление отлично, потому что тогда мы сможем использовать быстрые двоичные операции для работы с ним, и очень интуитивно понятно представить, как оно развивается. Например, учитывая сегмент [a,b] и функцию f(x) , определенную на этом сегменте, мы могли бы определить крайнюю левую точку функции , которая a должна быть представлена как 0000000000 (десять нулей), и мы могли бы сказать, что самая правая точка b равна 1111111111 (десять штук).

Есть 2^10=1024 точки, которые мы можем обозначить этими массивами длиной 10. Скажем длина([a,b])/1024 . Тогда мы могли бы представить a+l как 0000000001 , a+2l как 0000000010 , и так далее.

Если p является значением двоичного числа, мы можем вычислить соответствующее реальное значение x по следующей формуле:

$$ +\frac{p}{2^n-1}(b-a) $$

С другой стороны, чтобы назначить двоичное представление числу из интервала [a,b] , мы использовали бы следующее уравнение:

$$ p=\Bigg[\frac{x-a}{b-a}(2^n-1)\Bigg] $$

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

Например, предположим, что ваш алгоритм должен был угадать слово из 5 букв, и он может знать, сколько букв он получил правильно. В этом случае было бы вполне естественно использовать строку в качестве вашего генома. Если вы пытались научить его прыгать через дыры в игре, вы можете использовать массив логических значений, где true означает прыжок, а false означает бег, хотя, опять же, вы могли бы сопоставить его так 1 означает прыжок и 0 значит, беги.

Население

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

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

Функция пригодности и Целевая функция

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

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

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

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

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

Выбор

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

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

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

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

Git Essentials

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

Чтобы избежать этого, мы используем специальные методы отбора.

Выбор рулетки

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

$$ p=\frac{f(i)}{\sum_j^N f(j)} $$

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

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

Выбор Турнира

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

  • Детерминированный турнир всегда выбирает лучший геном в турнире. По сути, это просто поиск генома с максимальной или минимальной пригодностью.
  • турнир в 1 сторону-это турнир только с одним участником, и он эквивалентен стохастическому (случайному) выбору.
  • Пропорциональный турнир по фитнесу сортирует геномы в соответствии с их пригодностью и индексирует их. Затем i – й геном выбирается с вероятностью:

$$ p(1-p)^{i-1} $$

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

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

Кроссовер

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

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

Существуют различные типы кроссоверов:

  • одноточечный кроссовер
  • двухточечный кроссовер
  • пересечение k-точек
  • равномерное пересечение – существует определенная вероятность того, что ген в данном месте будет унаследован от родителя 1, в противном случае он унаследован от родителя 2
  • специальный кроссовер, предназначенный для удовлетворения ограничений конкретной задачи

Мутация

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

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

Политика замены поколений

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

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

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

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

Прекращение

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

  • Лучший геном удовлетворяет минимальным критериям для прекращения, оцениваемым целевой функцией
  • Мы достигли заданного максимального числа поколений
  • Алгоритм превысил максимальное время выполнения или потратил другие ограниченные ресурсы
  • Лучший геном буксует – последовательные итерации больше не дают лучших результатов
  • Комбинация нескольких из вышеперечисленных

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

Реализация

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

// Create genetic algorithm with parameters such as population size
// mutation rate, crossover rate, elitism count, tournament size 
GeneticAlgorithm ga = new GeneticAlgorithm(200, 0.05, 0.9, 2, 10);

// Initializing the population with chromosome length of 128, this
// number depends on the number of genes needed to encode the
// solution
Population population = ga.initPopulation(128);

// Evaluate the population for global fittness
ga.evalPopulation(population, maze);
       
int generation = 1;
       
// Start evolution loop
while (!ga.isTerminationConditionMet(generation, maxGenerations)) {
    Individual fittest = population.getFittest(0);

    // Print fittest individual from population to track progress
    System.out.println("G" + generation + " Best solution (" + fittest.getFitness() + "): " + fittest);

    // Crossover population
    population = ga.crossoverPopulation(population);
    // Mutate population
    population = ga.mutatePopulation(population);
    // Evaluate population
    ga.evalPopulation(population, maze);
           
    // Increment generation counter
    generation++;
}

В следующей статье мы рассмотрим реализацию генетического алгоритма путем решения классической задачи в области информатики – задачи коммивояжера:

Проблема коммивояжера с генетическими алгоритмами в Java

Если вы хотите узнать больше о генетических алгоритмах, отличная книга для начала-это Генетические алгоритмы в основах Java !

Вывод

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

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