www.machinelearningmastery.ru

Машинное обучение, нейронные сети, искусственный интеллект
Header decor

Home

Введение в генетические алгоритмы - включая пример кода

Дата публикации Jul 8, 2017

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

Понятие естественного отбора

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

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

Пять фаз рассматриваются в генетическом алгоритме.

  1. Начальная популяция
  2. Фитнес-функция
  3. выбор
  4. Кроссовер
  5. перегласовка

Начальная популяция

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

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

В генетическом алгоритме набор генов индивида представлен строкой в ​​алфавитном порядке. Обычно используются двоичные значения (строка из 1 и 0). Мы говорим, что кодируем гены в хромосоме.

Население, хромосомы и гены

Фитнес-функция

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

выбор

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

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

Кроссовер

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

Например, рассмотрим точку пересечения 3, как показано ниже.

Точка пересечения

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

Обмен генами среди родителей

Новое потомство добавлено к населению.

Новое потомство

перегласовка

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

Мутация: до и после

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

прекращение

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

Комментарии

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

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

Psuedocode

START
Generate the initial population
Compute fitness
REPEAT
Selection
Crossover
Mutation
Compute fitness
UNTIL population has converged
STOP

Пример реализации в Java

Ниже приведен пример реализации генетического алгоритма на Java. Не стесняйтесь поиграть с кодом.

Учитывая набор из 5 генов, каждый ген может содержать одно из двоичных значений 0 и 1.

Значение пригодности рассчитывается как число единиц, присутствующих в геноме. Если есть пять единиц, то у него максимальная пригодность. Если нет 1 с, то у него минимальная пригодность.

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

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

Пример вывода, где наиболее подходящее решение найдено в 32-м поколении

редактировать

Проверьте эту удивительную реализацию генетических алгоритмов с визуализацией генофонда в каждом поколении вhttps://github.com/memento/GeneticAlgorithmпомем энто,

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

Оригинальная статья

Footer decor

© www.machinelearningmastery.ru | Ссылки на оригиналы и авторов сохранены. | map