БУМАЖНЫй НОМЕР 

 

Ген-программа

01.09.2001
Михаил Попов

 

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

Основная идея генетических алгоритмов (ГА) довольно проста: вначале на компьютере создается некая беспорядочная популяция, которая затем «эволюционирует» под действием генетических операторов мутаций, рекомбинаций путем взаимного обмена (кроссинговера) и селекции. В простейшей форме каждый член популяции представлен бинарной строкой, где то или иное значение бита (1 или 0) трактуют как один «ген». Строка битов (например 00111 или 01010 и т. д.) обозначается как «генотип» или «индивидуум». Часто, однако, используются и более сложные представления, в том числе диплоидные и множественные хромосомы.

Взаимоотношения каждого «индивидуума» с окружением оцениваются с помощью функции годности (fitness function), причем «окружением» может являться что угодно: взаимодействия с соседями в популяции, действие в физическом мире (робототехника), компьютерная процедура или же субъективное суждение человека. Именно функция годности определяет, с какой конкретной проблемой будет иметь дело универсальный до того момента генетический алгоритм. После оценки каждого «индивидуума» степень их годности используют как критерий для селекции, направленный на исключение из популяции «плохих» участников, а «наследственность» осуществляется путем создания множественных копий индивидуумов с высокой годностью.

Генетические операторы мутаций и кроссинговера реализуют отклонения в индивидуальных битах и обмен субъединицами между двумя строками, создавая тем самым две новые строки и приводя к новой популяции, которая или полностью заменяет прежнюю, или частично перекрывает ее. Трансформируя предыдущую популяцию «хороших» участников, ГА производит новый набор, каждый член которого имеет уже более чем среднюю вероятность оказаться «хорошим». После многократных итераций для многих поколений в конце концов создается заселенность улучшенных «индивидуумов» - решений проблемы, заданной функцией годности.

Для задач, к которым обычно применяют ГА, характерен очень малый объем аналитических данных, высокий уровень шумов, изменения со временем и большая сложность. Поэтому невозможно определить заранее, как будет работать ГА в конкретной системе. Генетические программы по своей сложности напоминают решения, возникающие в природе посредством редупликации генов, мутаций и модификаций структур, и, по мнению теоретиков, именно поэтому ГА могут в будущем революционизировать программирование.

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

ГА, по сути, представляет собой процедуру исследования пространства всех возможных строк фиксированной длины L: {0,1} L, то есть поиска в n-мерном пространстве точек {0,1} L, имеющих высокую «годность». Чем длиннее строки битов (L), тем шире пространство поиска, увеличивающееся экспоненциально с длиной L. Для проблем с достаточно большой L генетический алгоритм может охватить лишь малую часть всего пространства минимумов. В частности, при L > 60 исчерпывающее исследование заданного пространства недоступно современным компьютерным технологиям.