It's evolution, baby!

Сегодня я вдруг подумал, что хочу рассказать вам одну историю. Есть на свете такой исследователь - Адриан Томпсон. Однажды он решил изучить процессы эволюции в неживых системах, на примере FPGA-чипа. Field-Programmable Gate Array - по-русски это будет Программируемая пользователем вентильная матрица, частный случай Программируемых логических интегральных схем. Да, Томпсона интересовала практическая сторона вопроса - можно ли использовать принцип эволюции для разработки более эффективных схем?

По-английски об этом можно прочитать тут:

Evolvable hardware
On the Origin of Circuits

В чём была суть эксперимента? Итак, у нас есть чип, матрица из программируемых ячеек, 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 ячеек, расположенный в конкретном месте конкретного чипа. Но зато в популяции оказались особи, которые на новом месте стали работать лучше бывшего чемпиона. А ещё через пару сотен поколений вся популяция подтянулась к прежнему высокому уровню, но уже на новом участке.

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

Update: _hellmaus_ подсказал, что про это у нас уже писали - "Эволюция железа".