Верховный алгоритм

Первым успехом генетического программирования стала в 1995 году разработка электронных схем. Начав с кучи элементов — транзисторов, резисторов и конденсаторов, — система Коза вновь изобрела запатентованный ранее фильтр нижних частот, который можно использовать, например, для усиления басов в танцевальной музыке. С тех пор Коза превратил повторное изобретение запатентованных устройств в своего рода спорт и начал выдавать их дюжинами. Следующей вехой стал патент на разработанную таким образом промышленную систему оптимизации, выданный в 2005 году Ведомством США по патентам и торговым знакам. Если бы тест Тьюринга79 заключался в обмане патентного эксперта, а не собеседника, 25 января 2005 года вошло бы в учебники истории.

Своей самоуверенностью Коза выделяется даже среди представителей дисциплины, где скромность не в чести. Он видит в генетическом программировании машину для изобретений, Кремниевого Эдисона XXI столетия. Коза и другие эволюционисты верят, что такой алгоритм может получить любую программу, и ставят на него в гонке за Верховным алгоритмом. В 2004 году они учредили ежегодную премию Humies, которую вручают за «соперничающие с человеком» генетические творения. На сегодняшний день присуждено 39 премий.

Зачем нужен секс?

Несмотря на все успехи и озарения, которые принесли нам генетические алгоритмы в таких вопросах, как градуализм против прерывистого равновесия, одна великая тайна остается неразгаданной: какую роль в эволюции играет половое размножение. Эволюционисты возлагают большие надежды на кроссинговер, однако представители других «племен» считают, что игра не стоит свеч. Ни один из теоретических результатов Холланда не показывает, что кроссинговер полезен: чтобы со временем экспоненциально увеличить частоту наиболее подходящих схем в популяции, достаточно мутаций, а логика «строительных блоков» привлекательна, но быстро сталкивается с проблемами даже при использовании генетического программирования. Когда в ходе эволюции появляются крупные блоки, кроссинговер со все большей вероятностью начинает их разбивать, а если удается вывести очень приспособленную особь, ее потомки, как правило, быстро захватывают популяцию и закрывают собой потенциально более перспективные схемы, содержащиеся в менее приспособленных в целом особях. В результате поиск вариантов сводится к определению чемпиона по приспособленности. Исследователи придумали много приемов сохранения разнообразия в популя­ции, но результаты пока неубедительны. Инженеры, несомненно, широко используют строительные блоки, но для их правильного соединения нужно, скажем так, много инженерии: сложить их вместе любым старым способом непросто, и неясно, может ли кроссинговер здесь помочь.

Если исключить половое размножение, у эволюционистов в качестве двигателя останутся одни мутации. Когда размер популяции значительно превышает количество генов, есть шанс, что все точечные мутации в ней уже представлены, и тогда поиск становится разновидностью восхождения по выпуклой поверхности: попробуй все возможные шаги, выбери лучший и повтори. (Или выбери несколько лучших вариантов: в таком случае это называется лучевой поиск.) Символисты, например, постоянно используют такой подход для получения наборов правил и не считают его формой эволюции. Чтобы не застрять в локальном максимуме, восхождение можно усилить случайностью (допустить с некоторой вероятностью движение вниз) и случайными пере­запусками (через некоторое время перепрыгнуть в произвольное состояние и продолжать восхождение там). Этого достаточно, чтобы найти удачные решения проблем. Оправдывает ли польза от добавления кроссинговера лишние затраты на вычисления — вопрос открытый.