Решил потратить свободное воскресенье на написание чего-нибудь интересного, размять мозги, освоить какие-нибудь новые приемы, короче говоря разбавить рутину повседневных дел. Задача достаточно тривиальна -написать аналог Hello World используя генетические алгоритмы.
Выложил код на github - Hello World генетическими алгоритмами. Там же лог где можно посмотреть как происходит решение задачи.
Генетические алгоритмы
Что представляют собой эти генетические алгоритмы? Они решают задачи точно так же как это делает природа, т.е. через "естественный отбор", соответственно критерии этого отбора должны быть достаточно просто вычисляемы - в моём случае это так называемая fitness функция которая посимвольно сравнивает решение с оригинальной строкой, чем лучше решение - тем ближе выход функции к нулю.
def fitness(dnk, goal): f = 0 for index, gene in enumerate(dnk): if gene != goal[index]: f -= 1 return f
Решение задачи представляется в виде вектора значений [a, b, c, d, ..., x] (в нашем случае это строка) длина которого известна, я обернул это в класс методы которого предоставляют интерфейс для взаимодейтсвия (class GeneticCode), на начальном этапе создаётся "популяция" (скажем 100) этих векторов инициализируемых случайными значениями.
self.pool = [GeneticCode(goal=goal) for item in range(self.pool_size)]
Затем fitness функция делает оценку каждого вектора популяции в коде, и далее лучшие образцы (скажем 10% от всей популяции) переходят на следующий круг. Существуют разные вариации генетических алгоритмов, кто хоть немножко разбирается в биологии и знает как происходит естественный отбор без труда могут придумать различные улучшения. Напоминаю, на данный момент у нас, после "естественного отбора" осталось 10% от популяции, где-то нужно взять остальные 90%, я решил на этом этапе провести "скрещивание", т.е. различные простейшие рекомбинации исходных векторов данных (одна часть берется от одного вектора, другая от второго и в результате получается, что-то новое). Детали этого этапа реализованы в методе def darvin(self, winners=0.1) класса GenePool.
Далее происходит "эволюция", т.е. кажый вектор испытывает какие-то случайные мутации (не затрагивая те элементы которые уже совпадают с оригинальной строкой). Затем опять приходит старик Дарвин, выбирает лучшие решений и процесс начинается заново. И так до тех пор пока решение не будет найдено. Если строка достаточно длинная + популяция мала и слишком много решений проходит отбор - генетический алгоритм может работать очень долго, поэтому неплохо будет ограничить кол-во итераций, скажем 1000 будет вполне достаточно.
Собственно классический "Hello world" получился примерно так (каждая строчка - лучший результат на каждом шаге) :
s(_soclbi!P*
{k&soclbil^!
oiYloC>otPC!
Evlso$>oil^!
EvlmoC>oild!
oil!oC>orld!
?vlloC>orld!
?elloCqorld!
GelloCqorld!
GelloCqorld!
Tello qorld!
oello qorld!
Tello world!
Tello world!
Tello world!
Hello world!
Естественно я только немного коснулся этой темы, спектр применений генетических алгоритмов достаточно широк, в том числе их используют совместно с нейросетями.
- Оптимизация функций
- Оптимизация запросов в базах данных
- Разнообразные задачи на графах (задача коммивояжера, раскраска, нахождение паросочетаний)
- Настройка и обучение искусственной нейронной сети
- Задачи компоновки
- Составление расписаний
- Игровые стратегии
- Теория приближений
- Искусственная жизнь, проекты типа EvoGrid
- Биоинформатика (свертка белков)
Для тех кто хочет попробовать, есть уже готовые библиотеки для python которые избавят вас от рутины написания лишнего кода.
http://www.freenet.org.nz/python/pygene/
http://pyevolve.sourceforge.net/