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

Ближе к природе

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

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

Однако в начале 1990-х годов у молодого англичанина Адриана Томпсона (Adrian Thompson), в ту пору аспиранта и сотрудника Центра вычислительной науки и роботехники Сассекского университета, сложилось убеждение, что таким технологиям не хватает одного весьма важного качества.

Что же произойдет (задался однажды вопросом Томпсон), если бы стало возможным снять цифровые ограничения и применить эволюционные принципы природы непосредственно к аппаратному обеспечению? Сумеет ли эволюция воспользоваться всеми электронными свойствами кремниевых компонент таким же образом, как она использует биомолекулярные структуры?

FPGA-чип

Как это нередко бывает в истории научных исследований, вместе с правильно поставленным вопросом довольно скоро появился и способ его решения. Именно в это время начала обретать популярность новая технология - микросхемы FPGA, созданные фирмой Xilinx, или Field-Programmable Gate Array - вентильные матрицы с перепрограммируемой пользователем логикой.

«А что у ей внутре?»

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

В чём была суть эксперимента? Итак, у нас есть чип, матрица из программируемых ячеек, 64 x 64. Для опыта использовался только один угол матрицы, квадрат из ста ячеек:

 Условная схема отдельной ячейки:

Итак, каждая ячейка может получать сигнал с одной из четырёх сторон (по сторонам света - N, S, E, W) и передавать его дальше. Она также может передавать функцию (F) - результат логической операции над одним, двумя или тремя сигналами. Например, слева и справа пришло по "1", передаём вниз "1", слева пришла "1", но справа "0", передаём вниз "0". Поведение каждой ячейки задаётся отдельной программой - что передавать, как и куда.  Естественно, можно настроить ячейку так, чтобы она всегда выдавала одно и то же значение, независимо от того, какой сигнал получен.
Исследователь сформулировал задачу - система из ста ячеек и логических вентилей-переключателей должна "научиться" отличать поступающий на вход (IN) сигнал частотой в 1 герц от сигнала частотой 10 герц. Не используя встроенный таймер! В идеале, система должна была выдавать на выход (OUT) напряжение в 5 вольт, если "слышала" 10 герц, и 0 вольт в остальных случаях.

Можете представить, как эту задачу решал бы обычный инженер? Есть сто программируемых ячеек, фиксированный вход и выход, нужно объяснить системе разницу между "бип, бип" и "бип-бип-бип", таймера нет...
А Адриан Томпсон просто сгенерировал пятьдесят программ с инструкциями для каждой конкретной ячейки. Программы представляли собой случайные последовательности нулей и единиц, длинной в 1800 бит. Эти программы стали "отдельными особями в популяции".

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

И так несколько тысяч поколений.

Чудо превращения

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

Слева указан номер поколения и реакция его лучшего представителя на поступающий сигнал:

Вначале сплошной "белый шум".

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

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

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

Томпсон провёл "вскрытие" победителя, и вот что он обнаружил (за вычетом неработающих и замкнутых на себя ячеек):

Куча мусора, куча линий, ведущих в никуда или пытающихся принять сигнал из ниоткуда - но система работала!

Тогда он стал отключать ячейки, по одной за раз, проверяя, как это повлияет на поведение системы и её способность распознавать сигнал. Это позволило отделить необходимые элементы от случайных и ненужных. В итоге, получилось следующее:

21 ячейка - этого достаточно, чтобы система безошибочно распознавала частоты. Какой инженер смог бы сконструировать подобное? А ведь это устройство возникло из хаоса изначального кода, благодаря случайным мутациям и последующему отбору "сильнейших". Но самое интересное в схеме - ячейки, отмеченные серым цветом. Они закольцованы, замкнуты сами на себя, не получают никаких сигналов извне и ничего не передают. При этом Томпсон обнаружил, что если их отключить, производительность системы резко падает.

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

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

Кстати, этим примером можно проиллюстрировать хроническую ошибку наивного социализма 20 века. "А что это за штука? А откуда она взялась в обществе - и зачем она вообще нужна? Она ведь ни на что не влияет! А давайте её с корнем уничтожим, как устаревшую и неправильную! Мы ведь должны перестроить общество по идеальной схеме, опираясь на чистый разум! ...Что, система стала работать хуже? Это заговор врагов!"

В жару и в холод

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

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

Ну и вывод автора: "Благодаря эволюции можно более полно исследовать пространство возможных решений. Значительная часть этого пространства недостижима обычными методами проектирования... Эволюция способна найти решение, которое будет более эффективно использовать доступные ресурсы, обладать более сложной структурой, демонстрировать динамическое поведение и учитывать особенности среды, в которой предстоит работать".