Живность в коде. Часть 1. Генетические алгоритмы

Когда-то мне пришлось заниматься задачами оптимизации (обучение нейронных сетей в моем случае) и очень хорошо в этом плане себя проявили генетические алгоритмы, которые относятся к категории эволюционных или биологических. К этой категории относится также ряд других алгоритмов - например метод муравьиных колоний (о нем попытаюсь подробнее рассказать в следующей статье).

Генетический алгоритм— это алгоритм, который позволяет найти удовлетворительное решение к аналитически неразрешимым проблемам через последовательный подбор и комбинирование искомых параметров с использованием механизмов, напоминающих биологическую эволюцию. Является разновидностью эволюционных вычислений. Отличительной особенностью генетического алгоритма является акцент на использование оператора «кроссовера», который производит операцию, роль которой аналогична роли скрещивания в живой природе.

Задача кодируется таким образом, чтобы ее решение могло быть представлено в виде вектора - хромосомы. Хромосома зачастую называется особью. Ее приспособленность (верность решения задачи закодированного в особи) оценивается при помощи целевой функции. Затем случайным образом создается начальная популяция - набор таких хромосом. Работа генетического алгоритма состоит в следующем:

1. Селекция - выбираются особи для "производства потомства" (выборка может осуществляться различными способами, например случайным или выборка особей с приспособленностью не ниже заданной) - обычно две особи (хромосомы) но может быть и больше
2. Между особями производится "скрещивание" - генетический оператор кроссовера, который состоит в следующем - вектора "разрезаются" а затем их части меняются местами. К стати сказать, это простейший вид оператора кроссовера - есть еще двухточечный кроссовер - когда "рассечение" особей происходит двумя сечениями, и другие
3. Затем производится с определенной вероятностью мутация получившихся особей - в простейшем случае - инверсия случайного бита (гена) в хромосоме
4. Также может применяться генетический оператор (опять таки с определенной вероятностью) "инверсия" - это когда хромосома рассекается и начальная часть с конечной меняются местами (есть и более сложные варианты) - хотя в принципе этот оператор можно считать разновидностью мутации
5. Также можно вводить свои какие-либо генетические операторы, если оптимизируемая функция слишком сложна, но это больше поле для экспериментов
6. Далее вычисляется приспособленность получившихся особей/особи - и если она выше наименее приспособленной особи в популяции то последняя заменяется на получившуюся (опять таки это всего лишь один из вариантов)
7. Таким образом моделируется эволюционный процесс, который продолжается до тех пор, пока не будет найден глобальное, либо субоптимальное решение, либо пока не сменится несколько поколений (смена одного поколения - некий процент новых особей заменил старых особей), либо пока не будет выполнено определенное количество итераций алгоритма

Генетические алгоритмы служат, главным образом, для поиска решений в очень больших, сложных пространствах поиска. И, надо признаться, с этой задачей они довольно хорошо справляются.
В заключение хочу привести ссылку на библиотеку - реализацию генетических алгоритмов на С++, которой я пользовался и которая, на мой взгляд, довольно удачно и грамотно спроектирована. Это библиотека GAlib, изначально написанная Matthew Wall при финансировании MIT, сейчас распространяется под BSD like лицензией и поддерживается автором. Недавно к стати вышел очередной релиз.