Эволюционное моделирование: проблемы формы и содержание

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

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

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

Итак, из поколения в поколение, «хорошие» характеристики распространяются по всей популяции. Скрещивание наиболее приспособленных особей приводит к тому, что исследуются наиболее перспективные участки пространства поиска. В конечном итоге популяция будет сходиться к приблизительно оптимальному решению задачи.

Итак, фундамент ГА составляют только 2 механизма эволюции - естественный отбор и наследственная изменчивость (или т.н. генетическое наследование). Такой фактор эволюции, как борьба за существование, о котором говорилось выше, явным образом в ГА не фигурирует.

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

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

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

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

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

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

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

После выбора родительских пар и размножения старая популяция частично или полностью уничтожается, и мы переходим к рассмотрению следующего поколения.

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

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

Беда в том, что при таком подходе выпадают важнейшие факторы эволюции как таковой.

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

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

Роль мутаций в ГА. Главная роль в процессе «видообразования» в ГА принадлежит кроссинговеру. Мутации носят лишь вспомогательный, дополнительный характер. Однако совершенно очевидно, что в природе перекрестное «перемешивание» 60 тыс. генов, суммарная длина которых составляет более 90 млн. нуклеотидов, вряд ли позволит без случайных мутаций получить столь разнообразные даже внутривидовые отличия, какие имеются, скажем, в человеческой популяции.

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

Но самое главное, что происходит ничем не обоснованный перенос «ДНК-подобного» механизма, механизма полового размножения с «высших» организмов на предельно примитивные формы - строки хромосом в ГА или деревья в генетическом программировании. Впрочем, пусть о достоинствах и недостатках партеногенеза и полового размножения спорят биологи.

Итак, в ГА накопилось слишком много искусственных допущений и механизмов - с одной стороны, и выпало из рассмотрения множество важнейших биологических, эволюционных факторов - с другой. Нельзя выбрасывать борьбу за существование или смешивать ее с естественным отбором; недопустимо говорить о механизме явного формирования новых поколений, тем более что в природе, к которой постоянно аппелируют приверженцы ГА, его нет; теряют смысл такие факторы, как период размножения и тем более - эффекты, связанные с фазой клеточного деления; отсутствие обучения, игнорирование роли фенотипа как такового, сведение его к генотипической составляющей; CF-фактор и многое, многое другое. Все это приводит к тому, что ГА не могут претендовать ни на что иное, нежели на некий оптимизационный поисковый метод, т.е. на то, что понималось изначально.

Заключение