Предыдущая часть: Введение в генетические алгоритмы
В качестве разминки возьмём самый простой генетический алгоритм – преобразование строки. В чём его суть: мы создаём популяцию случайных строк, которые должны эволюционировать в финальную строку.
Генами строки являются буквы латинского алфавита a..z и пробел. Можно, конечно, добавить в набор и другие символы, но это не принципиально для работы алгоритма. Комбинируя гены в разном порядке, мы получаем разные строки.
Финальная строка обычно задаётся такая:
the quick brown fox jumps over the lazy dog
Это обусловлено тем, что данная строка содержит все буквы латинского алфавита (то есть все возможные гены), и поэтому эволюция демонстрируется более наглядно. Но ничто не мешает взять любую другую строку.
А это точно генетический алгоритм?
Здесь нам нужно договориться, что мы на что-то закрываем глаза. Самой примитивной реализацией алгоритма будет просто случайный перебор: мы генерируем популяцию случайных строк до тех пор, пока кто-то из них не совпадёт с требуемой строкой. Такой перебор может занять 100500 лет, но главное, что принципиально мы уже реализовали алгоритм. Можно назвать эту реализацию, скажем, супермутационной, так как популяция полностью мутирует в каждом следующем поколении.
Однако генетический алгоритм интересует нас именно с точки зрения отбора генов. Для этого из случайно сгенерированных строк мы должны отбирать наиболее удачные, но как говорилось в предыдущей части, нужно определить критерий удачности (фитнес-функцию) – кто получился более удачным, а кто нет.
А этим критерием является степень совпадения с финальной строкой. А так как мы знаем финальную строку... то нам это всё вообще не нужно. Надо просто присвоить строке финальное значение, и вот задача решена :)
Но наша цель – на практике реализовать генетический алгоритм, чтобы пощупать его руками. Поэтому сейчас мы прикидываемся, что не знаем финальную строку, но знаем фитнес-функцию, и позволим генетике сделать всё остальное.
Фитнес-функция в нашем случае это расстояние между двумя строками (оно же дистанция/расстояние Левенштейна). Это количество несовпадающих символов в соответствующих позициях двух строк.
У каждой строки будет рейтинг, равный расстоянию от финальной строки. Чем меньше значение рейтинга, тем лучше. Если у какой-то из строк в популяции рейтинг станет равен 0, значит у неё совпадают с финальной все символы и мы решили задачу.
Имея строки с рейтингами, мы можем реализовать уже более внятную версию генетического алгоритма: брать самые удачные строки, применять к ним мутации, и смотреть, получились ли более удачные строки. Но всё это, а также дальнейшие усложнения (селекция, выбор родителей, скрещивание) связано с манипуляциям над строками, и поэтому сейчас, не начиная писать программу, мы должны поговорить об этом.
Немутабельные строки
Речь идёт вообще не о генетическом алгоритме, а о таком понятии в программировании, как мутабельность или немутабельность данных.
Так как алгоритм будет работать над строками, то самое очевидное решение – хранить эти строки именно в виде строк, типа:
a = 'qwerty'
Удобная и наглядная структура. Доступ к каждому гену строки мы можем осуществлять через индекс:
gene = a[3]
Но по ходу алгоритма символы внутри строк должны меняться. Если мы хотим изменить в строке символ с индексом 3 на другой, мы могли бы написать так:
a[3] = 'x'
Но в Питоне это сделать нельзя. Строку, однажды заданную, нельзя изменить. Поэтому они называются немутабельными.
Но ведь как-то в строке можно заменить символ? Да, но получается чудовищно громоздкая процедура: нужно взять подстроку слева от символа (это будет новая строка), присоединить к ней изменённый символ (это ещё одна строка), и присоединить подстроку справа от символа (это ещё одна строка).
И наконец, эти три строки, соединившись, станут ещё одной новой строкой. То есть, чтобы просто поменять один символ в строке, Питон должен создать в памяти три новые строки (не считая самого символа).
В языке PHP, например, мы можем заменить символ в строке элементарно:
$a[3] = 'x';
Но хотя внешне всё красиво, это также создаст в памяти новую строку (как минимум одну, так как детали от нас скрыты). Строки в PHP тоже немутабельны. Изменение строки приводит к появлению её копии.
В языке C также есть немутабельные строки, но можно создать и честную мутабельную строку. И тогда операция:
a[3] = 'x';
Будет заменять символ прямо в строке без всяких копий.
Почему всё это важно?
Генетический алгоритм работает с большим количеством повторений (десятки, сотни тысяч). Имея популяцию из, например, 20 строк, мы за 1 цикл порядка трёх раз устраиваем над ними модификации, затрагивающие до 50% длины строки. То есть, если строка длиной 43 символа, то за 1 цикл алгоритма мы меняем в ней до 60 символов и следовательно создаём до 180 новых строк. Только для одной строки и только за 1 цикл!
Нетрудно догадаться, что при большом количестве повторений нас интересует скорость работы алгоритма, а постоянное создание в памяти новых строк и уборка старых этому совсем не способствует.
Поэтому, несмотря на удобство строкового представления, стоит выбрать другую модель данных.
Байтовый массив
Нам заранее известны: длина строки (хромосомы) и размер популяции. Значит, желательно создать массив фиксированной длины, соответствующей размеру популяции, и заполнить его опять же массивами-хромосомами фиксированной длины, которые не должны пересоздаваться.
В этом случае вся выделенная память будет использоваться повторно и процессорное время не будет тратиться на создание и удаление объектов.
К счастью, в Питоне есть мутабельный тип данных, максимально похожий на строку – байтовый массив.
Мы можем проинициализировать байтовый массив заданной дины (например, 10):
chromosome = bytearray(10)
Также мы можем проинициализировать список для популяции строк (например, 20) стандартным питоновским способом:
population = [None] * 20
И после этого момента мы больше ничего не создаём и не удаляем.
Давайте начнём писать актуальный код. Писать будем на Питоне, но у нас есть кандидат на второй язык для сравнения – PHP или C. Приглашаю вас выбрать, какой из них интереснее.
Генофонд и финальная строка
Генофонд – это строка-справочник, которая содержит все возможные гены. Его и финальную строку (будем теперь говорить по-научному: хромосому) мы закодируем в байтовые массивы, используя другой способ инициализации:
genes = bytearray(b'abcdefghijklmnopqrstuvwxyz ')
final_chromo = bytearray(b'the quick brown fox jumps over the lazy dog')
Странная буква "b" перед строкой включает "буферный интерфейс", чтобы строка скопировалась в байтовый массив.
Переменная genes содержит все буквы алфавита и пробел – из неё мы будем добывать случайные гены. А переменная final_chromo содержит финальную последовательность генов, с которой мы будем сравнивать хромосомы из нашей популяции. Так как нам часто придётся работать и с тем и с другим, запомним их длины, а также зададим размер популяции и массив для содержания популяции:
genes_size = len(genes)
chromo_size = len(final_chromo)
population_size = 20
population = [None] * population_size
Теперь напишем функцию для генерации случайной хромосомы. Функция принимает два параметра: длина хромосомы, которую надо получить, и набор генов, из которого нужно сделать хромосому.
Обратите внимание, что хотя genes_size мы уже посчитали, внутри функции он считается ещё раз. Это сделано для того, чтобы функция не зависела от глобальных переменных. Возможно, глобальный genes_size нам уже и не понадобится.
Теперь напишем заполнение популяции:
В функцию заполнения популяции мы также передаём размер популяции, размер хромосомы и генофонд, чтобы не зависеть от глобальных переменных.
Теперь мы можем создать популяцию и распечатать её:
population = create_population(population_size, chromo_size, genes)
print(population)
Результат:
Мы получили список из 20 случайно заполненных байтовых массивов.
Вся программа:
Читайте дальше: Окончание
