Генетическое программирование – пора прозрения

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

Странные проволочные конструкции на фотографиях, сопровождающих статью, – вовсе не постмодернистские скульптуры. По большому счету это маленькие шедевры инженерной мысли. И реальные изделия, работающие в космических системах. Это... антенны. Настолько странные и выпадающие из спектра общепризнанных конструкций, что даже изучавший курс антенных устройств и имевший с ними дело без явного указания назначения этих «загогулин» не опознает в них нечто, предназначенное для приема/передачи электромагнитных волн. Между тем эти антенны неслучайно используются в космических системах NASA (в том числе и на орбитальной станции проекта Odyssey, обеспечивающей ретрансляцию 95% трафика между марсоходами Spirit и Opportunity и земным центром управления) – их характеристики (габаритно-весовые и электромагнитные) ощутимо превосходят показатели де-факто стандартных конструкций и недостижимы при традиционных подходах к проектированию. Созданы эти антенны как раз с помощью инструментария генетического программирования, что позволило легкому перу журналистов превратить их чуть ли не в продукт «машинного разума» (по крайней мере упоминания о них неоднократно встречаются в научно-популярных статьях одновременно с загадочными словосочетаниями вроде «изобретающая машина» и пр.). Попробуем кратко ознакомиться с тем, каким именно образом команда разработчиков NASA создала такие антенны – дело в том, что между теорией ГП и практикой обычно пролегает настоящая бездна. К слову, о команде разработчиков – в нее входит и является ее идеологом Джейсон Лон (Jason Lohn), один из учеников и протеже считающегося основателем практики и теории ГП Джона Коза (John R. Koza).

Для начала обратимся к истории. Сама теория и практика ГП являются продуктом некоторой весьма продолжительной по меркам скорости развития идей эволюции. В 60-х годах прошлого столетия немецкий ученый Инго Рехенберг (Ingo Rechenberg) ввел в обиход специалистов по решению задач оптимизации термин «эволюционная стратегия» и подтвердил ее эффективность неординарным решением ряда прикладных задач построения аэродинамических поверхностей (в наши дни он возглавляет факультет бионики и эволюционных техник Берлинского технического университета, сайт которого выглядит дерзкой насмешкой над тягой к прекрасному веб-дизайнеров всего мира, goo.gl/DmJMa). Следующий важный шаг был сделан в тех же 60-х годах Джоном Холландом (John Holland, goo.gl/BUn52) в Университете штата Мичиган. Холланда можно считать подлинным отцом современных генетических алгоритмов – именно он, работающий на стыке психологии, биологии, электроники и computer science (Холланд – одновременно трижды профессор таких разных научных дисциплин, бывает и такое), изучал природные механизмы адаптации и строил модели применения этих механизмов в артефактах – технических системах. Его книга 1975 г. «Адаптация в природных и искусственных системах» стала библией для всей последующей теории генетических алгоритмов. И Рехенберг, и Холланд рассматривали некий артефакт как аналог живого существа, обладающего биологическим механизмом передачи информации о себе своим потомкам. Принципиальная разница в подходах двух ученых очень примечательна – Рехенберг строил стратегию эволюции, отталкиваясь чуть ли не от модели Рая, в котором было место собственно для эволюционирующего объекта (Адам) и его наследника, измененного мутацией. Модель эволюции Холланда принципиально другая – в ней есть множественная популяция вариантов объекта и в качестве механизмов эволюции используется не только мутация, но и селекция и кроссовер (пока оставим эти термины без объяснения). Кроме того, Холланд построил теоретическое обоснование работоспособности генетических алгоритмов, фактически заложив основу новой области в ИТ.

Теперь попробуем, одновременно поясняя термины, взглянуть на процесс проектирования уже упомянутых хитрых антенн. Но несколько упростим задачу – так как команда разработчиков начинала вовсе не с них, а с хорошо известной даже далеким от ИТ и радиотехники пользователям телевизоров антенны Яги-Уда (именно они применяются в качестве персональных телевизионных антенн), мы не будем нарушать последовательности. Конструкция этих антенн проста – перпендикулярно к несущей балке крепятся один за другим ни с чем не соединенные, грубо говоря, отрезки из проводящего материала (они называются директорами), затем – единственный отрезок, активный вибратор, подключенный к антенному входу приемника (или выходу передатчика), после него, опять же один за другим, установлены ни с чем не соединенные отрезки рефлекторов. Такое изделие с точки зрения «компьютерных эволюционистов» является «носителем ДНК», состоящей всего из одной хромосомы, полностью описывающей конструкцию конкретного варианта антенны. Хромосома 14-элементной антенны Яги-Уда с одинаковым диаметром всех элементов состоит из пятнадцати генов – один отвечает за описание диаметра элементов и электромагнитные свойства материала, из которого они выполнены, следующие – за длину элемента (проводящего отрезка) и его расположение на несущей балке. Описываемый такой хромосомой (программистам не надо объяснять самое простое ее представление – массив пар чисел, но здесь своя терминология, где каждая пара – ген, а значение каждого числа – аллель) «организм» фактически является кандидатом на решение задачи синтеза конкретной антенны. Если совсем углубиться в биологию, а при изучении ГП это неизбежно, такой «организм» – типичный гаплоидный (у него одна непарная хромосома). Пока все было понятно. Но теперь начинается самое сложное. Как и всякий живой организм, все варианты конструкции 14-элементной антенны Яги-Уда характеризуются пригодностью (fitness). В биологии она определяется как жизнеспособность (вероятность выживания и порождения потомства) или плодовитость (количество оставленного после себя потомства). В 1931 г. Сьюэл Грин Райт, американский ученый-эволюционист, сформулировал понятие «ландшафта пригодности», для описываемой задачи имеющего простое геометрическое представление, – это бесконечная кривая, описывающая значения пригодности для всех возможных вариантов хромосомы антенны Яги-Уда. И если бы мы имели возможность окинуть взглядом этот ландшафт пригодности, можно было бы не городить весь огород ГП – мы бы просто выбрали самую экстремальную точку кривой, и задача решена – найден самый пригодный организм. Но дело-то в том, что кривая бесконечна. И далеко не всегда речь идет о двумерной кривой (если хромосом у организма всего четыре, задача «визуальным методом» не решаема – мы не способны визуально воспринимать пространства размерности выше трех). Иными словами, даже без описания реализации одного из множества генетических алгоритмов мы уже знаем смысл задачи – это фактически поиск оптимального решения в бесконечном пространстве всех возможных решений. Для антенны как организма пригодность оценивается по нескольким показателям – коэффициентам стоячей волны (КСВ) и усиления, диаграмме направленности etc. Это все рассчитывается относительно просто и точно (не следует забывать, что хороший инженер – хороший игрок, и знает, что такое компромиссы, поэтому в общем случае показатели пригодности могут быть взаимоисключающими, и для получения единой оценки надо прибегать к теории игр и принятия решений). Дальше начинается «все как у людей». Первичная популяция множества возможных организмов-антенн формируется случайным образом. После чего, выражаясь простонародным языком, конкретные представители популяции начинают друг с другом «встречаться», результатом «встреч» становится потомство и, естественно, обмен генной информацией. Мутации оказывают влияние на значения отдельных генов особей (изменяют аллели), механизм кроссовера обеспечивает обмен фрагментами подмножеств двух родительских хромосом при формировании двух потомков, а механизм селекции отвечает за увеличенную вероятность участия в репродуктивном процессе наиболее пригодных особей (с наилучшим показателем пригодности хромосом). Вся эта вероятностная механика повторяется поколение за поколением. Чтобы понять масштабы необходимых вычислений такой искусственной эволюции – на 1000-процессорном кластере синтез антенны-«загогулины» потребовал почти три месяца машинного времени (это все равно меньше, чем требуется при обычном проектировании).

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

Ready, set, buy! Посібник для початківців - як придбати Copilot для Microsoft 365