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

Предположим, есть задача, для которой можно найти множество решений. Каждому решению соответствует некоторое значение целевой функции, которую требуется оптимизировать. Алгоритм может вычислить эту функцию, на основе полученных результатов выбрать несколько лучших решений, создать на их основе новые и повторять этот процесс, пока не найдется удовлетворяющее решение. Если описать этот метод определениями из «Происхождения видов» Чарльза Дарвина, то решение задачи — это особь, набор решений — это поколение, целевая функция — это «функция приспособленности» (определяет, насколько хорошо особь приспособлена к окружающей среде), а алгоритм — это естественный отбор.

«Когда мы решаем такие задачи, надо иметь в виду, что у них очень и очень много решений. С одной стороны, человечество, скорее всего, уже что-то знает о решаемой задаче, поэтому пространство поиска можно сократить за счет использования имеющихся знаний. С другой стороны, все ли мы при этом учитываем, не отсекаем ли какое-либо хорошее решение? Мы должны „рассказать“ компьютеру, что нужно проверять, а что — нет. Зачастую эволюционные вычисления выдают такие результаты, о которых человек просто не задумывался. Например, с помощью такого алгоритма был создан новый вид антенны, который ученые разрабатывали для определенного вида передачи данных. Эта антенна имела неправильную форму, человек бы не пришел к такому решению самостоятельно так быстро», — пояснил Максим Буздалов.

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

Одновременно с этим алгоритм обучается: постепенно определяются «сильные особи» с определенным набором признаков, и при создании новых поколений алгоритм ориентируется на эти признаки как на первоочередные.

Конкретные реализации генетических алгоритмов создаются под определенные классы задач. Можно, конечно, использовать «универсальный» алгоритм, но эффективность его работы будет крайне низкой. Это будет либо полный перебор возможных решений, либо совершенно случайный поиск решения, который синтезируется без заданных условий, с нуля.

«Генетический алгоритм применяется, когда нужно найти не точное решение, а наилучшее из возможных за максимально короткие сроки. Например, есть город. В этом городе — 100 складов, 5 грузовиков и 300 магазинов. Грузовики должны развести товар со складов в магазины. И если с помощью алгоритма удастся снизить расходы на перевозку товара хотя бы на 20%, то это уже хороший результат. Бывают ситуации, когда нужно оптимизировать не одну величину, а несколько, при этом конфликтующих друг с другом. Допустим, в примере выше нужно оптимизировать как общее время доставки товаров, так и, например, расход топлива. При этом если один из показателей целевой функции будет оптимизирован (например, достигнуты лучшие показатели по времени), то другие показатели могут от этого ухудшиться (в данном случае произойдет большой расход топлива). Для этого применяют многокритериальные эволюционные алгоритмы, — привел примеры организатор секции на GECCO-2016.

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

Чем сложнее генетические алгоритмы, чем больше особей приходится анализировать, тем медленнее работает алгоритм и осуществляется оптимизация. Как правило, число особей одного поколения алгоритма не превышает 100, но если этим же алгоритмом попытаться работать с10 000 особями в поколении? Это может привести к тому, что большую часть времени алгоритм будет тратить на построение новых особей и обновление своего состояния, а не на вычисление функции приспособленности и получение новой информации о задаче.

«Возьмем обычный алгоритм сортировки. Если нужно расставить 10 000 книг по порядку, то алгоритм может действовать „в лоб“ и переставлять по отдельности каждую книгу. Для этого он произведет около 100 миллионов операций. А если разделить книги на части и переставлять их внутри этих блоков, то это займет не более одного миллиона операций. Примерно такие вещи мы будем обсуждать на GECCO-2016 в рамках моей секции — как улучшить работу генетического алгоритма», — сказал Максим Буздалов.

Иными словами, требуется изменить внутреннюю реализацию генетических алгоритмов. Для этого необходимо объединить усилия программистов-теоретиков и разработчиков эволюционных вычислений. По словам Максима Буздалова, долгое время специалисты этих областей работали порознь друг от друга, за исключением некоторых групп. При этом свойства эволюционных алгоритмов не изучались теоретиками, а их вычислительная сложность не уменьшалась. Точно так же разработчики эволюционных алгоритмов могли не знать о каких-то прорывных открытиях теоретиков, способных улучшить реализацию эволюционных алгоритмов.

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

Подробная информация о воркшопе доступна по ссылке.