Чарльз Дарвин создал теорию «выживания наиболее приспособленных» (хотя этот термин был придуман Гербертом Спенсером), что означает, что наиболее приспособленные и наиболее быстро адаптирующиеся организмы в определенной среде всегда будут преобладать над другими. Это имеет большой смысл; более сильные организмы с большей вероятностью выживают, а также с большей вероятностью передают свой генетический код. Что делает это интересным, так это то, что в хромосомах организмов иногда случаются мутации. Таким образом, мутация может привести к появлению слона, чье зрение было намного лучше, чем у других, и тогда он, вероятно, выживет дольше, поскольку сможет избегать львов лучше остальных и передать свою особую черту. Это означает, что если мы хотим «оптимизировать» силу определенного вида животных, мы, вероятно, можем просто подождать пару миллионов лет, пока происходят мутации и наиболее сильная победа над остальными.
Информатики и математики 1950-х годов начали заимствовать идеи из биологии и привели их в информатику. Одной из таких идей были генетические алгоритмы. Используя генетические алгоритмы (GA), мы копируем процесс эволюции на компьютере, чтобы оптимизировать функцию или выполнять поисковые запросы. Говоря простым языком, мы определяем правило, которое говорит вам, когда «организм» лучше другого. Мы слегка мутируем их и получаем наиболее подходящее воспроизведение, чтобы получить (после некоторого количества циклов) оптимальный «организм». Я говорю «организм» (в кавычках), потому что на самом деле нет никаких организмов; мы просто используем упрощенную модель одного. Таким образом, оказывается, что генетические алгоритмы позволяют компьютеру принимать «умные» решения для оптимизации или поиска (или множества других приложений).
Если вы не очень понимали многое из вышеперечисленного, это прекрасно. Мы будем писать собственный код генетического алгоритма (конечно, на Ruby), чтобы решить проблему оптимизации, и каждый шаг будет объяснен гораздо глубже, чем выше.
Детали
Давайте начнем с примера задачи, из которой мы разработаем идею генетических алгоритмов.
Предположим, у нас есть машина, которая при задании двоичного числа длиной четыре бита (то есть в двоичном виде имеет четыре цифры) выполняет операцию XOR с номером 1010 и выводит результат. Например, если входное значение равно 1100, выходное значение будет 0110 (или, в десятичном виде, 6).
Мы хотим выяснить, какой вклад сделает вывод этой машины как можно лучше.
При использовании генетических алгоритмов мы выполняем несколько шагов:
- Организм представлен хромосомой, которая представляет собой просто строку
- Мы случайным образом генерируем группу организмов (то есть строк)
- Мы определяем пригодность организмов, беря последовательность каждого из них и записывая возвращаемое значение из «функции пригодности» (т. Е. Правила, которому следует тренажер; в нашем случае операция XOR)
- Мы присваиваем вероятности каждому организму на основе пригодности (т.е. более высокая приспособленность подразумевает более высокую вероятность). После этого мы выбираем организм, который мы затем «воспроизводим», и организмы, которые не могли размножаться, вымирают.
- Все организмы находят партнеров, с которыми нити «пересекаются».
- Мы выполняем много итераций этого цикла.
Опять же, не волнуйтесь, если это слишком быстро для вас. Мы подробно рассмотрим каждый шаг.
Итак, наши организмы в этом случае очень легко представлены; они просто кусочки У нас будет двоичное число длиной 4 бита; что-то вроде 1011, которое представляет вход машины.
Затем мы должны случайным образом сгенерировать эти битовые строки, что довольно легко сделать.
Мы берем все случайно сгенерированные битовые последовательности (называемые пулом организма / хромосомы) и измеряем их пригодность, пропуская их через функцию пригодности, которая является операцией XOR.
Вам может быть интересно, почему у нас не просто достаточно большой пул, который может охватывать все возможные входные данные. Затем мы могли бы просто подключить их к функции фитнеса и выбрать организм с максимальной физической подготовкой; это будет всего 16 битовых строк, которые у нас есть (поскольку мы рассматриваем четыре бита). Предположим, что вместо четырех бит мы рассматривали 40 бит. Если бы мы собирали пул из всех возможных битовых строк, у нас было бы всего 1099511627776 битов; это много! Короче говоря, из-за эффективности мы не учитываем все возможные входные данные, и в некоторых случаях их может быть бесконечно много. Фактически, суть использования генетических алгоритмов заключается в том, чтобы повысить эффективность оптимизации. Если это не представляет проблемы, методы перебора намного проще реализовать.
Вернуться к алгоритму. Вероятности назначаются на основе пригодности, и отбирается несколько организмов, которые затем «клонируются», то есть копия хромосомы вставляется в пул хромосом.
Затем, чтобы получить новые хромосомы (основанные на старых), хромосомы соединяются с другими хромосомами, при этом части хромосом обмениваются друг с другом.
Итак, это основная идея генетических алгоритмов. Не ожидайте понять все это только пока; но общая идея должна начать формироваться. Просто продолжай читать; все это упадет вместе.
Организм
Базовая структура генетических алгоритмов — это организм, поэтому нам будет полезно определить класс вокруг него.
| class Chromosome | |
| attr_accessor :bitstring | |
| def initialize (length, bitstring=nil) | |
| @bitstring ||= rand(2**length+1).to_s(2).rjust(length, ‘0’) | |
| fitness | |
| end | |
| def self.random_chromosomes(length, number) | |
| return Array.new(length) { Chromosome.new(length) } | |
| end | |
| def to_s | |
| @bitstring | |
| end | |
| end |
by Это дает нам структуру данных, к которой мы можем прикреплять методы, так что этот компонент кода GA будет полностью повторно использован. Конструктор генерирует случайную битовую строку заданной длины, когда она не указана, так как это то, что мы будем много делать.
Если вы протестируете конструктор этого класса с аргументами, такими как 4 для длины и 100 для so_many, он выдаст гигантский список двоичных чисел в качестве вывода (если вы решите напечатать цепочку битов для каждого объекта Chromosome).
Я не знаю как вы, но я чувствую себя довольно круто, когда у меня на экране прокручиваются двоичные числа!
фитнес
Теперь нам нужно упростить нашу фитнес-функцию; это то, что все зависит от. Мы XOR вводим с 1010 и затем возвращаем результат.
Вот это в нашем любимом Ruby:
| class Chromosome | |
| attr_accessor :bitstring | |
| def fitness_func(n) | |
| return n^0b1010 | |
| end | |
| … |
Если вы протестируете его с 1100, вы должны получить результат 6 или 0110 в двоичном виде, что является правильным.
Весовые рандомы
Особая проблема, с которой нам приходится иметь дело, — это «взвешенное» случайное поколение. Таким образом, мы должны назначить вероятности для каждого организма, а затем выбрать на основе этих вероятностей.
Это часто называют выбором колеса рулетки, так как оно напоминает колесо рулетки с порциями разных размеров. Это не самый быстрый способ сделать это, но это один из самых простых и простых в реализации.
Мы можем сделать это с помощью массива, в котором части зарезервированы для каждой хромосомы в зависимости от того, какова хромосома. Вот реализация, добавленная к нашему классу Chromosome:
| class Chromosome | |
| ... | |
| def self.roulette(chrs) | |
| roulette=[] | |
| chrs.each { |chr| | |
| chr.fitness.times { roulette << chr } | |
| } | |
| roulette.sample | |
| end | |
| ... | |
| end |
Мы делаем процесс в двух частях; один, в котором установлено «колесо» рулетки, и другой, в котором случайное число выбирается из колеса рулетки. Конечно, колесо рулетки должно быть обновлено непосредственно перед использованием рулетки.
Во второй части этой статьи я закончу наше исследование, сосредоточив внимание на таких вещах, как размножение, поиск партнеров и «скрещивание» наших хромосом.