Top.Mail.Ru
? ?
Григорий "Это ж Гест"(с) [entries|archive|friends|userinfo]
Григорий

[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

It's evolution, baby! [Nov. 22nd, 2011|06:17 am]
Григорий
Сегодня я вдруг подумал, что хочу рассказать вам одну историю. Есть на свете такой исследователь - Адриан Томпсон. Однажды он решил изучить процессы эволюции в неживых системах, на примере 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_ подсказал, что про это у нас уже писали - "Эволюция железа".
linkReply

Comments:
[User Picture]From: hemdall
2011-11-22 04:11 am (UTC)

Удивлен

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

В принципе если развить мысль - такое "эволюционное развитие" позволяет сделать самодостаточно эволюционирующих роботов.
(Reply) (Thread)
[User Picture]From: aamonster
2011-11-22 10:09 am (UTC)

Re: Удивлен

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

А за исключением этого косяка - ничего нового...
(Reply) (Parent) (Thread) (Expand)
[User Picture]From: vlkamov
2011-11-22 04:29 am (UTC)
Критиковать таким образом "наивный социализм" - это повторять ту же ошибку. Понимаю, что хочется, но статье сильно повредило.

Чтобы решить задачу измерения частоты(времени) НЕОБХОДИМА мера частоты или времени. Единица. Опорный сигнал, камертон, кварц, колебательный контур, RC цепочка etc. В данном исследовании камертон был исключен сознательно (а отнюдь не по недомыслию = наивно). Исследователи хотели посмотреть, будут ли задействованы недокументированые особенности (сопротивления утечки, паразитные емкости), с которыми у инженеров-проектировщиков непримиримая борьба.

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

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

В другой серии опытов, система научилась ловить помеху - строчную развертку стоявшегов лаборатории монитора, то есть опорную частоту. Вырос радиоприемник.
(Reply) (Thread)
[User Picture]From: gest
2011-11-22 09:55 am (UTC)
"Критиковать таким образом "наивный социализм" - это повторять ту же ошибку. Понимаю, что хочется, но статье сильно повредило".

Ваши контраргументы?

"В данном исследовании камертон был исключен сознательно (а отнюдь не по недомыслию = наивно)". Блин, я пишу, что таймер был выключен по условиям задачи.

"результат абсолютно непригоден для тиражирования и вообще нестабилен" - результат: решение задачи.
(Reply) (Parent) (Thread) (Expand)
(Deleted comment)
[User Picture]From: dimag0g
2011-11-25 03:57 pm (UTC)

Ваша ссылка не работает

Расскажите, что там было?
(Reply) (Parent) (Thread)
[User Picture]From: aamonster
2011-11-22 10:07 am (UTC)
А по моему, автор - дилетант обыкновенный, чуть лучше старикашки Эдельвейса.

1. Загнал микросхему в неустойчивый режим, где она не описывается спецификацией. (Таймера нет? Агащазблин! У него там не одна сотня времязадающих элементов - правда, с неизвестными параметрами)
2. С помощью эволюционного алгоритма добился результата (неудивительно: все и так в курсе, что эти алгоритмы работают... если бы была нормальная схема, где переходы между ячейками ведут себя известным образом - можно было бы добиваться результата на модели и получить схему проще и лучше, чем выдал его алгоритм. На выбор - или аналогично эволюционным алгоритмом, или просто подумать)
3. Нарисовал "схему прохождения сигнала", которая в силу пункта 1 отношения к реальности не имеет.
4. Убедился, что сделал хрень (в силу пункта 1 - небольшое изменение параметров рушит все).

В общем, инженер не стал бы так делать просто потому, что подход изначально порочный. Он добавил бы к схеме RC-цепочку или еще что, и получил бы нормальный результат (воспроизводящийся от микросхемы к микросхеме и не зависящий от температуры).
(Reply) (Thread)
[User Picture]From: gest
2011-11-22 10:16 am (UTC)
А по-моему, нет.
(Reply) (Parent) (Thread) (Expand)
[User Picture]From: _hellmaus_
2011-11-22 11:09 am (UTC)
Я немного писал об этом три года назад: http://users.livejournal.com/_hellmaus_/82208.html

Спасибо, что ты пересказал это более человеческим языком!
(Reply) (Thread)
[User Picture]From: gest
2011-11-22 12:56 pm (UTC)
О, спасибо, я тогда это пропустил - читал только на английском.

Сейчас добавлю апдейт.
(Reply) (Parent) (Thread)
[User Picture]From: wedun26
2011-11-23 10:38 am (UTC)

А-а-а-а-а, я тащусь!

Наконец-то инженеры доказали существование души!
И то, что она возникает естественным путем в ходе эволюции!!!

(Reply) (Thread)
From: kodusass
2011-11-23 05:53 pm (UTC)

Все фигня.

У nature_wonder я грозился разгромить, желаете? :-)
(Reply) (Thread)
[User Picture]From: gest
2011-11-23 08:44 pm (UTC)

Re: Все фигня.

Я всегда готов выслушать чужое мнение. Если вас волнует алгоритм оценки "жизнеспособности", то вот он:

(Reply) (Parent) (Thread) (Expand)
[User Picture]From: xenonchik
2011-11-23 09:10 pm (UTC)
В программировании это называется генетическими алгоритмами)
http://megaswf.com/serve/1031310/ - вот один из примеров его реализации) только учтите, залипнуть можно надолго))
(Reply) (Thread)
[User Picture]From: samepaul
2011-11-27 08:48 am (UTC)
а, ну вот да. оно самое.
(Reply) (Parent) (Thread)
[User Picture]From: rekenavri
2011-11-24 09:27 am (UTC)
Чудесно. Только это скорее не социализм, а холизм (который может исходить из любых идей, от социалистических до либеральных) - в духе "а давайте поменяем всю систему"
(Reply) (Thread)
[User Picture]From: frothuss
2011-11-25 08:46 am (UTC)
Автор, Вы читали "Сумма Технологий" Лема? Если нет, то очень рекомендую по данной теме.
(Reply) (Thread)
[User Picture]From: v_michurin
2011-11-25 01:41 pm (UTC)
Про социализм это вы зря, не понимаете ведь, о чём говорите. Устранением "устаревших и неправильных" штук занимались на волне революционного энтузиазма, также как французы в своё время, например. Потом Сталин всё это пресёк на корню. С точки зрения подгонки мира под идеал, социализм ничем не отличается от либерализма, царизма и прочих измов. А с точки зрения работы системы - она работала до определённого момента всё лучше и лучше. Ухудшение же связано с причинами далёкими от управленческого кризиса, а связано с кризисом идеологии. Как только тот самый идеал для подгонки размылся, всё и рухнуло.

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

насчёт выводов автора - сложность структуры это скорее недостаток, чем достоинство, надёжность падает. Да и многие свойства таких эволюционных объектов непредсказуемы - что тоже добавляет головной боли потенциальным разработчикам.
(Reply) (Thread)
[User Picture]From: dlinyj
2011-11-25 02:38 pm (UTC)
Вы не могли бы сделать кросспост в сообщество ru_radio_electr . Мне кажется, там специалисты оценят данный пост по достойинству. Спасибо!
(Reply) (Thread)
[User Picture]From: samepaul
2011-11-27 08:46 am (UTC)
А я честно говоря не увидел какого-то принципиального отличия от всё тех же "нейронных сетей". Ну да, выглядит чуть по-другому, но принцип очень похож:
-сетке из функций задается какие-то изначальные значения
-через сетку прогоняют тонны входных данных, при этом значение селекторных функций "подкручивается"
-соответсвенно позитинвые результаты сохраняются, негативные отсеиваются.
-получается машина, которая умеет великолепно отвечать на один конкретно поставленный вопрос.
Но почему-то никто не увидел в этом "эволюции". Это селекция.
(Reply) (Thread)
[User Picture]From: haritonoff
2011-11-28 08:21 am (UTC)
Селекция и есть частный случай эволюции.
(Reply) (Parent) (Thread)
[User Picture]From: red_valjok
2011-12-01 03:17 pm (UTC)
> Понятно, что первые поколения были "никакими", ведь их поведением управлял случайно набранный код. Победителями становились системы, отвечавшие на внешние сигналы неизменным "белым шумом" - в конце концов, любая активность лучше, чем полное отсутствие признаков жизни. Но затем количество начало перерастать в качество...

Лажа. Когда цель постоянное занчение, колебания на выходе - хуже, а не лучше!
(Reply) (Thread)
[User Picture]From: nemetss
2012-01-07 04:57 am (UTC)
очень интересно, спасибо.

мне (как дилетанту) остался неясен один момент:
=остальные 49 "особей" производились от родителей предыдущего поколения, с учётом определённого процента случайных мутаций в коде. =

если изначальный код программы был случайной генерацией нулей и единиц, то есть никакую логику в работу программы не закладывали, то как на основании кода "подающего признаки жизни" родителя генерировали (опять же случайным образом) его детей?
(Reply) (Thread)