Это вторая часть статьи из двух частей. Пожалуйста, прочитайте первую статью, если вы еще этого не сделали.
репродукция
Хромосомы воспроизводятся с помощью взвешенного случайного кода (то есть машины с рулеткой), который мы только что добавили в класс Chromosome. Идея проста; возьмите существующий пул хромосом и замените его новым пулом того же размера, но только с некоторыми старыми организмами, способными размножаться и поддерживать их хромосомы (мы можем думать о старых организмах как умирающих).
| class Chromosome | |
| ... | |
| def self.produce_new(chrs) | |
| roulette(chrs) | |
| newchrs = [] | |
| chrs.each do |c| | |
| newchrs.push(roulette(chrs)) | |
| end | |
| fitnesses(newchrs) | |
| return newchrs | |
| end | |
| ... |
by Соответственно, реализация также очень проста, это просто цикл и некоторые расчеты фитнеса (так что нам не нужно пересчитывать фитнес вручную). Однако есть важная деталь, на которую следует обратить внимание. Мы вызываем setRoulette вне цикла, поскольку setRoulette — довольно тяжелая функция, и в противном случае мы бы вызывали ее без необходимости несколько раз.
Шаг назад
Вы, вероятно, пытаетесь поглотить целый поток информации, брошенной на вас сразу, и важно понять основную идею, а не просто как ее «кодировать».
До сих пор мы реализовали возможность генерировать случайные битовые строки указанной длины, которые называются хромосомами. Затем мы можем рассчитать «пригодность» этих хромосом по функции, которую мы пытаемся оптимизировать. Наконец, в зависимости от этих уровней пригодности, мы можем выбрать, какие организмы / хромосомы смогут размножаться.
Хромосомы, которые не могут размножаться, вымирают, поскольку они не были достаточно приспособлены для выживания.
В поисках товарищей
Как мы скоро увидим, необходимо сопоставить хромосому с другой. Обычно это делается случайным образом, но для этого требуется тонна ресурсов, и, поскольку порядок для начала более или менее случайный, мы просто собираемся связать хромосомы с хромосомой рядом с ними в массиве. ,
| class Chromosome | |
| ... | |
| def self.get_mates(chrs) | |
| i = 0 | |
| res = {} | |
| #again, the counting is very important (and mistakes are very hard to catch) | |
| #so, we are writing it out in full | |
| while i < chrs.length | |
| res[i] = i+1 | |
| res[i+1] = i | |
| i += 2 | |
| end | |
| end | |
| ... | |
| end |
Метод просто связывает двух соседей вместе, затем из них делается хеш для записи отношений.
скрещивание
Конечно, мы просто продолжали воспроизводить те же самые хромосомы, с которых мы начинали, в конце концов, у нас был бы пул наиболее приспособленных из исходных хромосом. Но это не наша цель; наша цель состоит в том, чтобы взглянуть на всю совокупность ресурсов.
Таким образом, мы «скрещиваем» хромосомы с другими, чтобы получить некоторую случайность в миксе. Пересечение — очень простая идея; если у вас есть одна хромосома 1011, а другая 1100, пересечение их в двух местах слева приводит к тому, что первая становится 1000, а вторая 1111. По сути, мы меняем концы хромосом.
Место, где их поменять, называется crossover_site.
| class Chromosome | |
| ... | |
| def cross(mate) | |
| cs = crossover_site = rand(@bitstring.length—1)+1 | |
| mate.bitstring[cs..-1], @bitstring[cs..-1] = @bitstring[cs..-1], mate.bitstring[cs..-1] | |
| end | |
| def self.do_crossings(chrs, mates) | |
| i = 0 | |
| completed = [] | |
| #not very idiomatic, but, the i variable is important | |
| while i < chrs.length | |
| #due to the symmetric nature of the data structure we’re using | |
| if completed.include? i | |
| i += 1 | |
| next | |
| end | |
| chrs[i].cross(chrs[mates[i]]) | |
| completed.push(mates[i]) | |
| i += 1 | |
| end | |
| return chrs | |
| end | |
| … | |
| end |
Опять же, код очень прост. Метод «cross» — это метод экземпляра, он пересекает объект Chromosome с другим, и doCrossings использует метод getMates для того, чтобы пересечь весь список хромосом с их сопряженными элементами.
Вне класса!
Хорошо! Мы закончили с определением класса!
Теперь нам просто нужно вставить немного кода, который заставит их методы в определении класса работать вместе, и вот он во всей своей красе:
| class Chromosome | |
| attr_accessor :bitstring | |
| def fitness | |
| @fitness = @bitstring ^ 0b0101 | |
| end | |
| def self.random_chromosomes(length, number) | |
| return Array.new(length) { Chromosome.new(length) } | |
| end | |
| def initialize(length, bitstring = nil) | |
| if bitstring | |
| @bitstring = bitstring | |
| else | |
| @bitstring = rand(2**length+1).to_s(2).rjust(length, ‘0’) | |
| end | |
| fitness | |
| end | |
| def self.fitnesses(chrs) | |
| chrs.each do |c| | |
| c.fitness | |
| end | |
| end | |
| def self.total_fitness(chrs) | |
| total = 0 | |
| chrs.each do |c| | |
| total += chrs.fitness | |
| end | |
| return total | |
| end | |
| def self.roulette(chrs) | |
| roulette=[] | |
| chrs.each { |chr| | |
| chr.fitness.times { roulette << chr } | |
| } | |
| roulette.sample | |
| end | |
| def self.produceNew(chrs) | |
| newchrs = [] | |
| chrs.each do |c| | |
| newchrs.push(roulette(chrs)) | |
| end | |
| fitnesses(newchrs) | |
| return newchrs | |
| end | |
| def cross(mate) | |
| cs = crossover_site = rand(@bitstring.length—1)+1 | |
| mate.bitstring[cs..-1], @bitstring[cs..-1] = @bitstring[cs..-1], mate.bitstring[cs..-1] | |
| end | |
| def self.do_crossings(chrs, mates) | |
| i = 0 | |
| completed = [] | |
| #not very idiomatic, but, the i variable is important | |
| while i < chrs.length | |
| #due to the symmetric nature of the data structure we’re using | |
| if completed.include? i | |
| i += 1 | |
| next | |
| end | |
| chrs[i].cross(chrs[mates[i]]) | |
| completed.push(mates[i]) | |
| i += 1 | |
| end | |
| return chrs | |
| end | |
| def self.get_mates(chrs) | |
| i = 0 | |
| res = {} | |
| while i < chrs.length | |
| res[i] = i+1 | |
| res[i+1] = i | |
| i += 2 | |
| end | |
| res | |
| end | |
| end | |
| i = 0 | |
| chrs = Chromosome.random_chromosomes(4, 4) | |
| 100.times do | |
| chrs = Chromosome.produce_new(chrs) | |
| mates = Chromosome.get_mates(chrs) | |
| chrs = Chromosome.do_crossings(chrs, mates) | |
| puts chrs.inspect | |
| end | |
| puts chrs.inspect |
Сначала мы генерируем случайные хромосомы, затем на каждой итерации создается новый набор путем воспроизведения из старых хромосом (чьи родительские организмы предположительно умерли). Затем мы распечатываем объект Chromosome, чтобы увидеть уровень пригодности и строку битов. Наконец, новые помощники найдены и пересечение проводится.
Готов грохотать!
Запустив этот код, вы должны увидеть много выходных данных, которые не имеют большого значения. Важным является последняя часть вывода, которая распечатывает хромосомы. Говорят, что из них тот, у кого самый высокий уровень физической подготовки, является нашим прогнозируемым оптимальным организмом.
Итак, похлопайте себя по плечу, вы только что решили проблему оптимизации, используя эволюционные алгоритмы!
Прибавь громкости
Но мы все еще имеем дело только с 4 битами. Это заняло бы всего лишь 16 испытаний, связанных с грубой силой.
Генетические алгоритмы намного более мощные в более высоких масштабах, потому что они работают намного лучше, чем грубая сила для некоторой потери точности в решении. Но, чтобы сохранить код простым, оптимизации не были реализованы. Например, алгоритм рулетки может быть сделан намного быстрее, но это потребует некоторого более глубокого понимания и действительно помешает при попытке обдумать концепцию генетических алгоритмов.
Завершение
Генетические алгоритмы могут быть применены к множеству мест; проблемы поиска и оптимизации сразу бросаются в глаза, но есть и другие очень интересные случаи использования. Например, GA постоянно используются в криптографии для взлома кодов, поскольку это может быть сведено к оптимизации функции в определенном направлении.
Ruby, в некоторых отношениях, является отличным языком для работы с GA, потому что он быстр и быстр со строками. Но нужно помнить, что Ruby не будет работать так же быстро, как C или C ++, и не все приложения могут работать с ним. Но, по моему опыту, Ruby работал отлично для всех, кроме самых тяжелых обязанностей.
Кроме того, класс Chromosome, который мы разработали в этом посте, можно использовать повторно . Это означает, что для решения различных задач все, что вам нужно сделать, — это изменить фитнес-функцию, и, возможно, настроить способ спаривания и пересечения, и вы готовы к работе!
Если вам понравилась эта статья, пожалуйста, сделайте ее с помощью кнопки Twitter, и я хотел бы услышать ваши мысли об этом в разделе комментариев ниже.
Конечно, если у вас есть какие-либо вопросы, пожалуйста, не стесняйтесь оставить комментарий ниже, и я помогу, как только смогу.