Внедрение генетических алгоритмов путем эволюции Моны Лизы
На первый взгляд это может показаться неочевидным, но алгоритмы информатики часто вдохновлены природой и биологическими процессами. Некоторые из этих алгоритмов включают нейронные сети, оптимизацию роя частиц, искусственную пчелиную колонию, оптимизацию муравьиной колонии, эволюционные алгоритмы и многие другие. На самом деле биологические процессы можно считать просто алгоритмами, которые придумала природа для решения проблем. С этой точки зрения легко понять, почему многие из этих алгоритмов являются эвристикой оптимизации и метаэвристикой. Ведь природа оптимизирует для выживания.
Эвристика, если этот термин вам не знаком, — это алгоритмы, которые пытаются решить проблему быстрее, делая некоторые предположения. В результате эвристики часто не оптимальны, но более полезны в тех случаях, когда получение наилучших результатов занимает слишком много времени. Метаэвристика выводит это на новый уровень — это эвристика, которая генерирует или находит эвристики.
Генетические алгоритмы
Генетические алгоритмы — это метаэвристики, основанные на процессе естественного отбора. Генетические алгоритмы представляют собой тип эволюционного алгоритма.
Естественный отбор, как напоминание, является ключевым механизмом эволюции. Это естественный процесс, который заставляет популяции (организмов) со временем адаптироваться к окружающей среде. Эти популяции имеют различия в признаках. Отдельные организмы с более подходящими чертами имеют более высокие шансы на выживание в окружающей среде. Следующие поколения, воспроизведенные от этих выживших организмов, унаследуют их черты, что в конечном итоге приведет к появлению популяции с этими более подходящими чертами.
Однако, если вся популяция будет иметь одинаковые черты, а окружающая среда изменится, популяция вымрет. К счастью, иногда возникающие мутации вызывают вариации признаков, что позволяет организмам с признаками, более подходящими для изменившейся среды, выживать и становиться доминирующими.
Популярно используемой иллюстрацией является вариация окраски у перченых мотыльков в Англии. До начала 1800-х годов перечная моль в Англии была в основном белой, и ее окраска помогала ей прятаться от хищных птиц, поскольку она хорошо сочеталась со светлыми лишайниками и английскими деревьями. Однако во время промышленной революции светлые лишайники погибли из-за загрязнения, и многие деревья, на которых отдыхали мотыльки, почернели от сажи. Это давало темным бабочкам преимущество в укрытии от хищников, в то время как светлых бабочек было легко обнаружить. К середине 1800-х годов количество бабочек темного цвета увеличилось, и к концу века почти все бабочки были темной разновидности. Баланс был нарушен в результате действия Закона о чистом воздухе 1956 года, и мотыльки темного цвета снова стали редкостью.
Так что это естественный отбор. Как в дело вступают генетические алгоритмы? Генетические алгоритмы — это эвристика, использующая те же механизмы, что и естественный отбор: ДНК, популяция, изменчивость, приспособленность, отбор, воспроизводство, наследование и мутация.
- ДНК – определение организмов, имеющих одну или несколько ДНК.
- Популяция — начните с начальной популяции организмов с разными генами (значениями) для их ДНК.
- Приспособленность — определение приспособленности каждого организма к окружающей среде.
- Отбор – выберите организмы с наилучшей приспособленностью и дайте им более высокие шансы на размножение.
- Размножение — создание следующего поколения популяции из выбранных наиболее подходящих организмов.
- Наследование — следующее поколение популяции должно унаследовать значения генов
- Мутация — с каждым поколением есть небольшой шанс, что значения генов изменятся.
Обезьяны, пишущие машинки и Шекспир
Теорема о бесконечных обезьянах гласит, что бесконечное количество обезьян, сидящих за бесконечным количеством пишущих машинок и случайно нажимающих клавиши, через достаточное количество времени воспроизведут все произведения Шекспира полностью. Допустим, мы хотим, чтобы всего одна обезьяна воспроизвела эту цитату: Быть или не быть. Как вы думаете, сколько времени потребуется обезьяне, чтобы выковать это случайным образом?
Цитата состоит из 18 символов (включая пробел). Вероятность того, что обезьяна напечатает 't' (будем великодушны и скажем, что можно писать только прописные буквы), равна 1 из 26. Таким образом, вероятность ввода точной последовательности «To be или не быть» равно 1 из 26 в степени 18 или 1 из примерно 29 479 510 200 013 920 000 000 000. Если, скажем, обезьяна печатает букву каждую секунду, есть только 1 шанс из 934 789 136 225 707 600 лет, что она напечатает эту цитату. Это 1 раз за 934 триллиона лет.
Очевидно, что грубый способ сделать это ни к чему нас не приведет. Что, если мы попытаемся «развить» цитату? Давайте посмотрим, как мы можем использовать генетические алгоритмы для этого. Вот шаги для генетического алгоритма, используемого для решения проблемы:
Дайте определение организму, состоящему из одной или нескольких ДНК.
Организм в нашем алгоритме Шекспира состоит из одной ДНК, которая представляет собой массив байтов и число, представляющее приспособленность Организма.
type Organism struct {
DNA []byte
Fitness float64
}Начните с начальной популяции организмов
Нам нужно создать организмы для нашей начальной популяции, поэтому вот функция для этого.
func createOrganism(target []byte) (organism Organism) {
ba := make([]byte, len(target))
for i := 0; i < len(target); i++ {
ba[i] = byte(rand.Intn(95) + 32)
}
organism = Organism{
DNA: ba,
Fitness: 0,
}
organism.calcFitness(target)
return
}target — это то, чего мы хотим достичь, в данном случае это представление массива байтов строки «быть или не быть». В этой функции мы случайным образом создаем массив байтов той же длины, что и цель, и устанавливаем его как значение гена во вновь созданном Организме.
Теперь, когда мы можем создавать Организмы, нам нужно создать их популяцию.
func createPopulation(target []byte) (population []Organism) {
population = make([]Organism, PopSize)
for i := 0; i < PopSize; i++ {
population[i] = createOrganism(target)
}
return
}population — это массив Организмов, а PopSize — это глобальная переменная, определяющая размер популяции.
Найдите приспособленность организмов
Нам нужно рассчитать приспособленность организмов в нашей популяции. Это было вызвано ранее, когда мы создали Организм, но также будет вызвано позже, когда мы будем пересекать Организмы.
func (d *Organism) calcFitness(target []byte) {
score := 0
for i := 0; i < len(d.DNA); i++ {
if d.DNA[i] == target[i] {
score++
}
}
d.Fitness = float64(score) / float64(len(d.DNA))
return
}Эта фитнес-функция относительно проста. Мы просто подсчитываем, сколько раз байты в гене совпадают с целью. Оценка делится на общее количество байтов в целевом объекте, чтобы соответствие было процентным, то есть числом от 0,0 до 1,0. Это означает, что если приспособленность равна 1,0, мы развили бы ген Организма, чтобы он соответствовал цитате «быть или не быть».
Выберите организмы с наилучшей приспособленностью и дайте им больше шансов на размножение.
Теперь, когда у нас есть популяция, и мы можем выяснить, какие организмы обладают наилучшей приспособленностью, мы хотим выбрать наиболее приспособленные организмы и позволить им размножаться, чтобы создать следующее поколение популяции. Есть много разных способов сделать это, но в данном случае мы используем механизм «воспроизводящего пула».
func createPool(population []Organism, target []byte, maxFitness float64) (pool []Organism) {
pool = make([]Organism, 0)
// create a pool for next generation
for i := 0; i < len(population); i++ {
population[i].calcFitness(target)
num := int((population[i].Fitness / maxFitness) * 100)
for n := 0; n < num; n++ {
pool = append(pool, population[i])
}
}
return
}Что мы делаем, так это создаем своего рода пул для размножения, куда я помещаю в пул несколько копий одного и того же организма в соответствии с его приспособленностью. Чем выше приспособленность организма, тем больше копий организма попадает в пул.
Создайте следующее поколение популяции из выбранных наиболее подходящих организмов
После этого мы случайным образом выбираем 2 организма из пула размножения и используем их в качестве родителей для создания следующего поколения организма для популяции.
func naturalSelection(pool []Organism, population []Organism, target []byte) []Organism { next := make([]Organism, len(population))for i := 0; i < len(population); i++ { r1, r2 := rand.Intn(len(pool)), rand.Intn(len(pool)) a := pool[r1] b := pool[r2]child := crossover(a, b) child.mutate() child.calcFitness(target)next[i] = child } return next }
Следующее поколение населения должно унаследовать значения генов
Затем child в следующем поколении происходит от скрещивания двух случайно выбранных организмов и наследует ДНК обоих организмов.
func crossover(d1 Organism, d2 Organism) Organism { child := Organism{ DNA: make([]byte, len(d1.DNA)), Fitness: 0, } mid := rand.Intn(len(d1.DNA)) for i := 0; i < len(d1.DNA); i++ { if i > mid { child.DNA[i] = d1.DNA[i] } else { child.DNA[i] = d2.DNA[i] }} return child }
Для кроссовера я просто выбрал среднюю точку mid и использовал первые mid байтов из первого организма, а остальные байты из второго организма.
Случайно мутировать каждое поколение
После того, как новый дочерний организм был воспроизведен из двух родительских организмов, мы видим, происходит ли мутация с дочерним организмом.
func (d *Organism) mutate() {
for i := 0; i < len(d.DNA); i++ {
if rand.Float64() < MutationRate {
d.DNA[i] = byte(rand.Intn(95) + 32)
}
}
}Здесь мутация просто означает определить, меньше ли случайно сгенерированное число MutationRate. Зачем нужно мутировать детский организм? Если мутация никогда не произойдет, ДНК внутри популяции всегда останется такой же, как и исходная популяция. Это означает, что если исходная популяция не имеет определенного гена (значения), который необходим, оптимальный результат никогда не будет достигнут. Как в примере, если буква t вообще не встречается в начальной популяции, мы никогда не сможем придумать цитату, сколько бы поколений мы ни прошли. Другими словами, естественный отбор не работает без мутаций.
С технической точки зрения, мутации выводят нас из локального максимума, чтобы найти глобальный максимум. Если мы посмотрим на генетические алгоритмы как на механизм поиска оптимального решения, то, если у нас нет мутации, как только будет найден локальный максимум, механизм просто остановится на нем и никогда не будет двигаться дальше, чтобы найти глобальный максимум. Мутации могут вывести популяцию за пределы локального максимума и, следовательно, дать алгоритму возможность продолжить поиск глобального максимума.
Как только мы проверяем мутацию, мы вычисляем приспособленность дочернего организма и вставляем его в следующее поколение популяции.
Вот и все, что нужно знать о генетическом алгоритме! Теперь давайте объединим все это в функцию main.
func main() { start := time.Now() rand.Seed(time.Now().UTC().UnixNano())target := []byte("To be or not to be") population := createPopulation(target)found := false generation := 0 for !found { generation++ bestOrganism := getBest(population) fmt.Printf("\r generation: %d | %s | fitness: %2f", generation, string(bestOrganism.DNA), bestOrganism.Fitness)if bytes.Compare(bestOrganism.DNA, target) == 0 { found = true } else { maxFitness := bestOrganism.Fitness pool := createPool(population, target, maxFitness) population = naturalSelection(pool, population, target) }} elapsed := time.Since(start) fmt.Printf("\nTime taken: %s\n", elapsed) }
В основной функции мы проходим поколения и для каждого поколения пытаемся найти наиболее подходящий организм. Если бы ген наиболее подходящего организма был таким же, как у мишени, мы бы нашли ответ.
Теперь запустите программу! Сколько времени это заняло у вас?
Поскольку начальная популяция генерируется случайным образом, вы каждый раз будете получать разные ответы, но в большинстве случаев мы можем изменить цитату менее чем за секунду! Это довольно большая разница по сравнению с 934 триллионами лет, если бы нам пришлось переборщить.
Эволюция Моны Лизы
Развитие Шекспира кажется довольно простым. В конце концов, это всего лишь строка. Как насчет чего-то другого, скажем, изображения? Или самая известная картина всех времен, Мона Лиза Леонардо да Винчи? Можем ли мы развить это?
Давайте обратимся к этому так же. Мы начнем с определения организма для изображения Моны Лизы.
Дайте определение организму, состоящему из одной или нескольких ДНК.
Вместо массива байтов наша ДНК теперь представляет собой структуру из стандартной библиотеки image.
type Organism struct {
DNA *image.RGBA
Fitness int64
}Начните с начальной популяции организмов
Как и раньше, давайте сначала рассмотрим создание организма.
func createOrganism(target *image.RGBA) (organism Organism) {
organism = Organism{
DNA: createRandomImageFrom(target),
Fitness: 0,
}
organism.calcFitness(target)
return
}Вместо создания случайного массива байтов мы вызываем другую функцию для создания случайного изображения.
func createRandomImageFrom(img *image.RGBA) (created *image.RGBA) {
pix := make([]uint8, len(img.Pix))
rand.Read(pix)
created = &image.RGBA{
Pix: pix,
Stride: img.Stride,
Rect: img.Rect,
}
return
}Структура image.RGBA состоит из массива байтов Pix (byte и uint8 — одно и то же), Stride и Rect. Что важно для нас, так это Pix, мы используем те же Stride и Rect в качестве целевого изображения (которое является изображением Моны Лизы). К счастью для нас, в стандартной библиотеке math/rand есть метод Read, который красиво заполняет массив байтов случайными байтами.
Вам может быть любопытно, так о каком большом массиве байтов мы здесь говорим? Pix — это не что иное, как массив байтов с 4 байтами, представляющими пиксель (R, G, B и A, каждый из которых представлен байтом). С изображением размером 800 x 600 мы говорим о 1,92 миллиона байт в каждом изображении! Чтобы программа оставалась относительно быстрой, мы будем использовать меньшее изображение размером 67 x 100, что дает массив размером 26 800 байт. Это, если вы еще не поняли, далеко не те 18 байт, с которыми мы играли в предыдущей программе.
Кроме того, вы можете понять, что, поскольку каждый пиксель теперь окрашен случайным образом, мы получим цветной статичный снежный узор.
Давайте двигаться дальше.
Найдите приспособленность организмов
Приспособленность организма — это разница между двумя изображениями.
// calculate the fitness of an organism func (o *Organism) calcFitness(target *image.RGBA) { difference := diff(o.DNA, target) if difference == 0 { o.Fitness = 1 } o.Fitness = difference}// find the difference between 2 images func diff(a, b *image.RGBA) (d int64) { d = 0 for i := 0; i < len(a.Pix); i++ { d += int64(squareDifference(a.Pix[i], b.Pix[i])) } return int64(math.Sqrt(float64(d))) }// square the difference between 2 uint8s func squareDifference(x, y uint8) uint64 { d := uint64(x) - uint64(y) return d * d }
Чтобы найти разницу, мы можем вернуться к теореме Пифагора. Если вы помните, мы можем найти расстояние между двумя точками, если возведем в квадрат разницу значений x и y, сложим их, а затем возьмем из результатов квадратный корень.
Задайте 2 точки a(x1, y1) и b(x2, y2), расстояние d между a и b равно:
Это в двухмерном пространстве. В трехмерном пространстве мы просто повторяем теорему Пифагора дважды, а в четырехмерном — трижды. Значения RGBA пикселя, по сути, являются точкой в 4-мерном пространстве, поэтому, чтобы найти разницу между 2 пикселями, мы возводим в квадрат разницу между значениями r, g, b и a двух пикселей, складываем их все, а затем извлекаем квадратный корень. результаты.
Это разница между 2 пикселями. Чтобы найти разницу между всеми пикселями, мы просто суммируем все результаты вместе и получаем окончательную разницу. Поскольку Pix по сути является одним длинным массивом байтов с последовательными значениями RGBA, мы можем использовать простой ярлык. Мы просто возводим в квадрат разницу между каждым соответствующим байтом в изображении и цели, затем складываем их все и извлекаем квадратный корень из конечного числа, чтобы найти разницу между двумя изображениями.
Для справки, если 2 изображения абсолютно одинаковы, разница будет равна 0, а если 2 изображения полностью противоположны друг другу, разница составит 26 800. Другими словами, наиболее приспособленные организмы должны иметь приспособленность, равную 0, и чем выше число, тем менее приспособленным является организм.
Выберите организмы с наилучшей приспособленностью и дайте им больше шансов на размножение.
Здесь мы по-прежнему используем механизм племенного пула, но с некоторыми отличиями. Во-первых, мы сортируем популяцию от лучшей приспособленности к худшей приспособленности. Затем мы берем лучшие организмы и помещаем их в пул для разведения. Мы используем параметр PoolSize, чтобы указать, сколько наиболее подходящих организмов мы хотим добавить в пул.
Чтобы выяснить, что поместить в пул размножения, мы вычитаем каждый из лучших организмов с наименее приспособленным организмом в верхней части. Это создает дифференцированный рейтинг между лучшими организмами, и в соответствии с этим дифференциальным рейтингом мы помещаем соответствующее количество копий организма в пул размножения. Например, если разница между наиболее приспособленным организмом и наименее приспособленным организмом в топе лучших составляет 20, мы помещаем 20 организмов в племенной пул.
Если между наиболее подходящими организмами нет разницы, это означает, что популяция стабильна, и мы не можем создать надлежащий пул для размножения. Чтобы преодолеть это, если разница равна 0, мы устанавливаем пул как всю популяцию.
func createPool(population []Organism, target *image.RGBA) (pool []Organism) {
pool = make([]Organism, 0)
// get top best fitting organisms
sort.SliceStable(population, func(i, j int) bool {
return population[i].Fitness < population[j].Fitness
})
top := population[0 : PoolSize+1]
// if there is no difference between the top organisms, the population is stable
// and we can't get generate a proper breeding pool so we make the pool equal to the
// population and reproduce the next generation
if top[len(top)-1].Fitness-top[0].Fitness == 0 {
pool = population
return
}
// create a pool for next generation
for i := 0; i < len(top)-1; i++ {
num := (top[PoolSize].Fitness - top[i].Fitness)
for n := int64(0); n < num; n++ {
pool = append(pool, top[i])
}
}
return
}Создайте следующее поколение популяции из выбранных наиболее подходящих организмов
После того, как у нас есть пул, нам нужно создать следующее поколение. Код для естественного отбора здесь ничем не отличается от предыдущей программы, поэтому мы не будем его здесь показывать.
Следующее поколение населения должно унаследовать значения генов
Функция crossover немного отличается, поскольку ДНК ребенка представляет собой не массив байтов, а изображение .RGBA. Вместо этого фактический механизм кроссовера работает с Pix, байтовым массивом пикселей.
func crossover(d1 Organism, d2 Organism) Organism { pix := make([]uint8, len(d1.DNA.Pix)) child := Organism{ DNA: &image.RGBA{ Pix: pix, Stride: d1.DNA.Stride, Rect: d1.DNA.Rect, }, Fitness: 0, } mid := rand.Intn(len(d1.DNA.Pix)) for i := 0; i < len(d1.DNA.Pix); i++ { if i > mid { child.DNA.Pix[i] = d1.DNA.Pix[i] } else { child.DNA.Pix[i] = d2.DNA.Pix[i] }} return child }
Случайно мутировать каждое поколение
Соответственно, функция mutate также отличается.
func (o *Organism) mutate() {
for i := 0; i < len(o.DNA.Pix); i++ {
if rand.Float64() < MutationRate {
o.DNA.Pix[i] = uint8(rand.Intn(255))
}
}
}Теперь, когда у нас есть все, мы собираем все вместе в функции main.
func main() { start := time.Now() rand.Seed(time.Now().UTC().UnixNano()) target := load("./ml.png") printImage(target.SubImage(target.Rect)) population := createPopulation(target)found := false generation := 0 for !found { generation++ bestOrganism := getBest(population) if bestOrganism.Fitness < FitnessLimit { found = true } else { pool := createPool(population, target) population = naturalSelection(pool, population, target) if generation%100 == 0 { sofar := time.Since(start) fmt.Printf("\nTime taken so far: %s | generation: %d | fitness: %d | pool size: %d", sofar, generation, bestOrganism.Fitness, len(pool)) save("./evolved.png", bestOrganism.DNA) fmt.Println() printImage(bestOrganism.DNA.SubImage(bestOrganism.DNA.Rect)) } } } elapsed := time.Since(start) fmt.Printf("\nTotal time taken: %s\n", elapsed) }
Теперь запустите его и посмотрите. Что вы получаете?
С параметрами, которые я установил, когда я запускаю его, я обычно начинаю с пригодности 19 000 или около того. В среднем мне требуется более 20 минут, прежде чем я достигаю физической формы ниже 7500.
Вот последовательность изображений, которые были созданы с течением времени:
Эволюция Моны Лизы с кругами и треугольниками
Я немного позабавился с развитием Моны Лизы, рисуя круги, а также рисуя треугольники на изображении. Результаты были не такими быстрыми, а изображения не такими очевидными, но они дают представление о том, что происходит на самом деле. Вы можете проверить остальную часть кода из репозитория и настроить параметры самостоятельно, чтобы посмотреть, сможете ли вы получить более качественные изображения, но вот некоторые изображения, которые я получил.
Треугольники Моны Лизы
Круги Моны Лизы
Развлекайся!
Отображение изображений на терминале
Вы могли заметить на моих скриншотах, что я действительно отображал изображения на терминале. Я мог бы создать веб-приложение, чтобы показать это, но я хотел, чтобы все было намного проще, поэтому я решил отображать изображения непосредственно на терминале. Хотя консоль терминала находится не там, где вы обычно ожидаете отображения изображений, на самом деле есть несколько способов сделать это.
Я выбрал один из самых простых. Мне довелось использовать отличный iTerm2, который является заменой терминального приложения по умолчанию в MacOS, и в iTerm2 есть интересный хак, позволяющий отображать изображения.
Фокус в том, что если вы можете закодировать свое изображение в Base64, вы можете использовать специальную команду для вывода изображений на терминал. Вот код Go для этого, но вы также можете сделать это на любом другом языке. В приведенной выше документации есть несколько сценариев, которые показывают, как это можно сделать с помощью простых сценариев оболочки.
func printImage(img image.Image) {
var buf bytes.Buffer
png.Encode(&buf, img)
imgBase64Str := base64.StdEncoding.EncodeToString(buf.Bytes())
fmt.Printf("\x1b]1337;File=inline=1:%s\a\n", imgBase64Str)
}К сожалению, это означает, что если вы запустите этот код в любом другом iTerm2, вы не сможете увидеть эволюцию изображений. Однако вы всегда можете настроить выходные данные так, чтобы каждые несколько поколений вы получали выходные данные.
Код
Весь код и изображения в этом посте можно найти здесь: https://github.com/sausheong/ga
использованная литература
Пример кода был вдохновлен следующей работой:
- Прекрасная книга Дэниела Шиффмана The Nature of Code http://natureofcode.com — отличная и понятная книга! Я также взял часть кода Дэниела на Java и преобразовал его в Go для алгоритма цитирования Шекспира.
- Отличная работа Роджера Йоханссона в посте Генетическое программирование: эволюция Моны Лизы https://rogerjohansson.blog/2008/12/07/genetic-programming-evolution-of-mona-lisa/– хотя в итоге я использовал совершенно другой способ создания генетических алгоритмов, его оригинальная работа вдохновила меня на использование Моны Лизы, а также на попытки сделать это с треугольниками и кругами.
