Записки инженера

Реализация механизма памяти в управляющем клеточном автомате

leonid_grigorev — Sun, 04 Mar 2012 18:14:31 GMT

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

Дальнейшие рассуждения я попробовал изложить в статье.

Моделирование процессов клеточными автоматами

leonid_grigorev — Sat, 03 Dec 2011 13:46:15 GMT

Очередная идея. Для обучения управляющих клеточных автоматов я применяю обучающие последовательности. Но, это хорошо работает только в тех случаях, когда обучающая последовательность простая и конечная. Это подходит для релейных (логических) схем процессов. Для временных рядов, когда имеется достаточно длинный временной ряд. А вот для процессов непрерывных, изменяющихся быстро и плохо регулируемых такой подход не годится. Невозможно создать обучающую последовательность для процессов, например таких, какие обычно регулируются ПИД-регуляторами. Настройка таких регуляторов не такое уж простое дело.
Получается, чтобы "научить" мои автоматы управлению динамическими процессами, надо иметь некую математическую модель этого процесса. Если рассмотреть процесс как черный ящик, то можно заметить, что он протекает под управлением каких-то воздействий. Результатом этих воздействий будут основные его технологические характеристики. Тут прослеживается некоторая аналогия с управляющими автоматами. У них тоже есть некоторые управляющие воздействия - значения которых отображаются входными клетками, и технологические характеристики - значения выходных клеток. Следовательно можно применить клеточные автоматы для моделирования сложных технологических процессов. Для того, чтобы вырастить из клеточного автомата модель технологического процесса надо собрать с существующего процесса телеметрию. Эта телеметрия и послужит обучающей последовательностью для моделмрующего клеточного автомата. Идем к объекту регулирования, навешиваем на него кучу разнообразных датчиков. Включаем объект, производим регулирование или управление процессом в ручном режиме. Записываем телеметрию. Затем используем эти записи для обучения моделирующего процесс клеточного автомата. Тут просто - то, что курутили, управляя процессом - то вход, то, что приходило в процесс - то тоже вход. А то, ради чего регулировали - выход. Методика создания моделирующего клеточного автомата ни чем не отличается от методики создания управляющего клеточного автомата. Вырастив моделирующий клеточный автомат на полученной телеметрии, можно его использовать для создания управляющего клеточного автомата. Вот такая вот идея. Пошел творить.

144-ядерный процессор Чарльза Мура поступил в продажу по $20

leonid_grigorev — Fri, 25 Nov 2011 17:49:21 GMT

Оригинал взят у Блог им. koroandr
Чарльз Мур, создатель языка программирования Форт (Forth), довёл до стадии промышленного производства уникальную разработку — многоядерный процессор GA144. Чип размером 10х10 мм уже поступил в продажу по цене $20 (при заказе от десяти штук), также доступны материнские платы для него. Фактически, это аппаратное воплощение самого языка программирования Форт.

Крайне необычный процессор по ряду параметров не имеет себе равных среди CPU:

144 независимых ядра, которые активируются только при поступлении инструкции, то есть у этого процессора нет такой характеристики как «тактовая частота»;
скорость выполнения инструкций 1400 пикосекунд (эквивалент 700 МГц);
энергопотребление 7 пикоджоулей на одну инструкцию;
энергопотребление в «спящем» режиме менее 100 нановатт;

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

Чак разработал этот процессор самостоятельно с помощью им же созданного инструментария OKAD II VLSI. Инструменты для разработки под GA144, включая ассемблер/компилятор и примеры исходных кодов, распространяются бесплатно в пакете под общим названием arrayForth.

Специалисты пытаются понять, каковы целевые области применения GA144. Вариантов много:

робототехника (манипуляторы, протезы, автономные подвижные роботы);
искусственный интеллект и нейронные сети (классификация, распознавание сигналов/образов);
«бортовые системы» (диагностика состояния в реальном времени, контроль движения);
«академическое» применение (аппаратное обеспечение курсов цифровой обработки сигналов, параллельного программирования, архитектуры вычислительных систем);
распознавание и синтез речи;
модуляторы/демодуляторы сигналов.

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

Мой комментарий: вот и железо уже готово. Наверное, всё-таки придется вернуться к Forth-у.

It's evolution, baby!

leonid_grigorev — Fri, 25 Nov 2011 17:29:38 GMT

Оригинал взят у gest в 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_ подсказал, что про это у нас уже писали - "Эволюция железа".

Еще раз о том, что мне хочется получить

leonid_grigorev — Sat, 01 Oct 2011 12:31:30 GMT

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

Давайте попробуем решить Вашу задачу.
От Вас требуется составить обучающую последовательность - описать каким образом должны изменяться выходные значения при всех возможных вариантах входных значений.
Клеточный автомат имеет входные и выходные клетки. Допустим, вы хотите, чтобы при включенном освещении освещение Вашего актвариума приглушалось. Значит входным значением может быть битовый сигнал, ноль которого говорит, что внешнего света нет, а единица - внешний свет есть. Выходом может быть ключ, замыкающий диод в цепи освещения Вашего аквариума. Если на входе 0, т.е. внешнего освещения нет, то на выходе должна быть единица - диод в цепи освещения закорочен и освещение работает на полную мощность. Если на входе 1 - внешнее освещение включено - на выходе должен быть 0 - диод работает в цепи и уменьшает освещение аквариума.
Обучающая последовательность выглядит так:
1:1 - Имеем один вход и один выход;
1:0 - если на входе 1, то на выходе должен быть 0;
0:1 - если на входе 0 - то на выходе должна быть 1.

Рассмотрим более сложный пример обучающей последовательности. Клапан. Имеем два входных параметра. Допустим, давление и уставку. Оба параметра измеряются с точностью 4 бита. Клапан работает, если значение давления не превышает уставки. Если превышает, то клапан закрывается. Выходом является сигнал управления клапаном - 0 - клапан закрыт, 1 - клапан открыт. В данном случае имеем 8 входных битов и один выходной. Обучающая последовательность записывается следующим образом:
8:1
0:0:0:0:0:1:0:0:1
0:0:0:1:0:1:0:0:1
....
0:1:0:0:0:1:0:0:1
0:1:0:1:0:1:0:0:0
0:1:1:0:0:1:0:0:0
....
1:1:1:1:0:1:0:0:0
Здесь показана обучающая последовательность для значения уставки 0100 и только. Если надо управление уставкой, то длина обучающей последовательности увеличится всего в 16 раз. Для каждого значения уставки надо написать свою обучающую последовательность из 16 строк. Итого 256 строк + 1 строка-заголовок.

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

Для программирования любой задачи, для которой можно написать однозначную управляющую последовательность, создается только одна программа - программа расчета текущих состояний клеток. Текущие состояния клеток - суть биты. Значит в 10 байтах можно разместить систему с 80-ю клетками. Для хранения прошлого состояния системы надо иметь еще 10 байтов. Для хранения алгоритмов расчета каждой клетки потребуется до 3-х байт в случае автоматов с тремя выходами. Значит, расход памяти флэшки составит для 80-клеточной системы до 240 байт. Плюс программа, выполняющая однотипные расчетные операции, ну, пусть еще сотня байт. Вот насчет программ, обрабатывающих вход и выход пока ничего не могу сказать, но, то, что просматривал в готовых программах для МК могу грубо оценить еще сотней байт. И все! Получается, что можно обходиться весьма "слабыми" в плане памяти микроконтроллерами.

Ищу единомышленников

leonid_grigorev — Wed, 21 Sep 2011 15:59:36 GMT

Разместил на разных досках объявлений и в нескольких радио-форумах такое объявление:

Ищу единомышленников (управляющие клеточные автоматы)

В свободное время занимаюсь исследованиями в области управляющих клеточных автоматов.
Похоже, пора заняться воплощением математики в железо.
Проект не коммерческий. Денег не прошу и не предлагаю.
Приглашаю к сотрудничеству. Ознакомиться с вопросом можно в моем ЖЖ: http://legre.pp.ua

Объявление не осталось незамеченным. Некоторые модераторы просто удалили его, о чем любезно сообщили мне.
На форумах объявление вызвало неоднозначную реакцию. Больше всего мне понравилась такая реакция:

Форум "РадиоКот" http://radiokot.ru/forum/viewtopic.php?f=29&t=54675

Бред и реклама ЖЖ.
Сначала бы научился грамотно писать...

На других форумах реакция есть, но тоже не по делу. Даже не знаю, стоит ли тратить время на болтовню там?

Заканчиваем подсчет

leonid_grigorev — Sat, 17 Sep 2011 16:54:14 GMT

Рассмотрим автоматы релейной схемы "два входа - два выхода". Можно представить их как два сросшихся автомата схемы "два входа - один выход". Оно так и есть, если объеденить входные клетки вух автоматов "2-1", что возможно. В результате получим 254 варианта элементарных клеточных автомата.

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

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

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

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

Рывок триггерных алгоритмов

leonid_grigorev — Fri, 16 Sep 2011 13:33:51 GMT

Рассмотрим элементарные клеточные автоматы, реализующие релейные алгоритмы работы "два входа - один выход". Тут ничего интересного. Согласно Википедии возможны 16 вариантов алгоритмов. Обучающие последовательности приведены в таблице:

In	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0 0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1
0 1	0	0	0	1	1	1	1	0	0	0	0	1	1	1	1
1 0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1
1 1	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1

   Для элементарных клеточных автоматов первую последовательность и последнюю использовать нет смысла, так как они не изменяют значения выходной клетки. Остается 14 вариантов.

   Для релейных схем "три входа - один выход" возможно 256 вариантов входных состояний. Первое и последнее не пригодны для нас. Остается 254 варианта разновидностей алгоритмов работы элементарных клеточных автоматов.

   Тепрь посмотрим, как можно применить идею триггерности в схемах "два входа - один выход".
Если в простейшем алгоритме в схеме с одним входом и одним выходом на вход автомата подается единственное значение, которое и управляет работой триггера, то в случае "два входа - один выход" на вход автомата может прийти аж четыре варианта значений. И каждое из них может вызывать триггерный эффект. Если записать действие, выполняемое автоматом таким образом: ( 0 → (2), 1 → (3) ) - то получился триггер, управляемый единицей. При приходе 0 изменений не происходит (2) - функция клетки "оставить как было", а при приходе 1 происходит инверсия значения клетки (3) - функция клетки "инвертировать прошлое состояние клетки".
     Для четырех вариантов входящих состояний элементарного клеточного автомата "два входа - один выход" можно составить, например, такое описание алгоритма:
0 0 → (2)
0 1 → (3)
1 0 → (2)
1 1 → (3)
   Что означает: если на вход клетки поступили первое или третье значения, то никаких изменений прошлого сотояния не будет. А если второе или четвертое - то прошлое состояние будет проинвертировано.
    И таких комбинаций может быть 16. Но, здесь только одна комбинация "не нужна" - (2), (2), (2), (2), так как не производит никаких изменений в любом случае. А комбинация (3), (3), (3), (3) - полезна - изменения состояния происходят. Получилось 16 вариантов. Уже на 1 больше, чем у релейных схем. По аналогии для автоматов "три входа - один выход" релейных схем алгоритмов возможно 255.
Дозаполним табличку:

Вход	Выход
Вход	1	2	3
1	0р + 2т	12р + 6т	56р + 14т
2	14р + 15т
3	254р + 255т

на распутье трех дорог

leonid_grigorev — Thu, 15 Sep 2011 14:47:30 GMT

Продолжаем рассмотрение видов элементарных клеточных автоматов. Сегодня рассмотрим возможное количество автоматов вида "один вход - три выхода". Вариантов для трех битов может быть 8. Если у нас два значения на входе (0 и 1), то на выходе будет 8 х 8 = 64 варианта. Но, так как варианты, не изменяющие значения выхода составляют 8 штук, то остается 56 вариантов элементарных клеточных автоматов релейного типа, которые пригодны для использования.
Например, вариант пригодного для использования алгоритма: 0 → 0 1 0; 1 → 1 0 0;
вариант не пригодного для использования алгоритма 0 → 0 1 1; 1 → 0 1 1.

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

Теперь оценим количество триггерных вариантов элементарных клеточных автоматов вида "один вход - три выхода". По аналогии с "один вход - два выхода" возможно для одного управляющего входа построить 7 альтернативных состояний. В нашем случае, когда управляющим значением является или 1 или 0, общее количество триггерных вариантов элементарных клеточных автоматов состаляет 14. Дозаполним табличку видов:

Вход	Выход
Вход	1	2	3
1	0р + 2т	12р + 6т	56р + 14т
2
3

В следующей статье рассмотрим автоматы вида "два входа - один выход".

Один вход - два выхода

leonid_grigorev — Wed, 14 Sep 2011 13:23:23 GMT

Теперь попробуем разобраться с элементарными клеточными автоматами, обладающими одним входом и двумя выходами. Не правда ли, что это напоминает железнодорожную стрелку? Поэтому я их называю "маршрутизаторами". Можно представить себе, что поезд, пришедший на вход такой стрелки может поехать по обному из двух возможных маршрутов - налево или направо. Но клеточный автомат не стрелка и единичка, появившаяся на входе - не поезд.
Сколько же вариантов маршрутизации информации можно создать по такой схеме? Прежде всего надо не зацикливаться на единичке. Будто бы только она одна и есть та самая информация, которая должна куда-то на этой "стрелке" поехать. Возможно несколько вариантов продолжения маршрута после того, как единичка приехала к стрелке. Так как выхода два, то они могут принимать 4 варианта состояний: 00, 01, 10 и 11. То же самое может случиться, если управляющим сигналом будет 0. Если совместить все эти варианты, то получим 16 схем, приведенных в таблице:

Значения выходных клеток

Номер варианта	Если на входе 0	Если на входе 1
1	00	00
2	00	01
3	00	10
4	00	11
5	01	00
6	01	01
7	01	10
8	01	11
9	10	00
10	10	01
11	10	10
12	10	11
13	11	00
14	11	01
15	11	10
16	11	11

Четыре строки таблицы, выделенные желтым цветом, ничего не меняют на выходе элементарного клеточного автомата. Значит они нам не нужны. Остается 12 вариантов элементарных клеточных автоматов релейного типа.

Пример алгоритма 8 варианта приведен ниже:

Глаза
(свойства)

Глаз	Номер клетки
Глаз	1	2
0	2	1
1	0	0
2	0	0

Клетки
(функции)

Аргумент	Номер клетки
Аргумент	1	2
0	0
1	1	1

Теперь посмотрим каким образом в этой схеме можно задействовать автоматы типа триггеров. Особенностью всех алгоритмов является начальная инициализация клеток элементарного клеточного автомата в 0. Следовательно, начальное состояние всех выходных клеток любого элементарного клеточного автомата всегда 00.
Возможны три варианта различных состояний выходных клеток по приходу управляющего сигнала на вход, отличные от этого значения, это - 01, 10 и 11. Так как такие состояния могут рассматриваться и при управляющей единице и при управляющем нуле, то всего получается 6 триггерных элементарных клеточных автоматов. Управляющий сигнал либо устанавливает одно из этих состояний в выходных клетках, если они имели нулевое состояние, либо сбрасывает их в 00, если состояние отличалось от 00.

Примеры двух вариантов реализации одного и того же триггерного алгоритма с двумя выходными состояниями 00 и 01 и переключающей единицей приведены ниже:

Глаза
(свойства)

Глаз	Номер клетки
Глаз	1	2
0	1	3
1	0	0
2	0	0

Клетки
(функции)

Аргумент	Номер клетки
Аргумент	1	2
0		3
1	0	2

Глаза
(свойства)

Глаз	Номер клетки
Глаз	1	2
0	2	2
1	0	0
2	0	0

Клетки
(функции)

Аргумент	Номер клетки
Аргумент	1	2
0	0	2
1	0	3

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

Вход	Выход
Вход	1	2	3
1	0р + 2т	12р + 6т
2
3

О схемах "один вход - три выхода" будет следующая статья.

Генерация группы "один вход - один выход"

leonid_grigorev — Tue, 13 Sep 2011 15:32:49 GMT

Такие элементарные клеточные автоматы могут выполнять одну из двух логических функций:

1) репликация: 0 -> 0, 1 -> 1 - значение входа дублируется на выход;
2) инверсия: 0 -> 1, 1 -> 0 - значение входа инвертируется и подается на выход.

Между тем свойства глаз любого клеточного автомата (в моей интерпретации) включают в себя эти возможности. Получается, что нет необходимости дублировать эти свойства специальными элементарными клеточными автоматами. Что же остается? Триггер!
Причем два варианта.
Первый вариант триггера управляется единицей - состояние клетки изменяется если на вход поступает 1.
Второй вариант триггера - триггер управляемый нулем. Состояние клетки изменяется если на вход поступает 0.
В результате получилось 2 элементарных клеточных автомата.
Триггер, управляемый единицей:

Глаза (свойства)

Глаз	Номер клетки
Глаз	1
0	2
1	0

Клетки (функции)

Аргумент	Номер клетки
Аргумент	1
0	2
1	3

Триггер, управляемый нулем:

Глаза (свойства)

Глаз	Номер клетки
Глаз	1
0	3
1	0

Клетки
(функции)

Аргумент	Номер клетки
Аргумент	1
0	2
1	3

В этих схемах входная клетка - № 0, выходная - № 1.

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

Итак, в этой группе остаются только два триггера. Если у кого-то есть другое мнение - выскажите его в комментариях.

Начнем заполнять таблицу групп.

Количество элементарных клеточных автоматов по группам

Вход	Выход
Вход	1	2	3
1	0 + 2т
2
3

Эта запись говорит о том, что в группе "один вход - один выход" может быть 2 элементарных клеточных автомата и причем, только триггеры. Автоматы, реализующих релейную схему работы не используются.

Я разделяю все виды клеточных автоматов на два подвида по методу обработки информации. Первый вид не обрабатывает истории жизни автомата. Это автоматы релейного типа. Они работают как простые релейные схемы. Им нет дела до того, какое значение имела выходная клетка до начала вычислений на каждом такте. Они не обладают исторической памятью. Второй тип автоматов обрабатывает "временной ряд". В этих автоматах требуется, чтобы клетка знала, какое значение она имела перед началом такта вычислений. К таким автоматам относятся триггера. Поэтому они используют в своем алгориме функции: 2 (оставить как было) и 3 (инвертировать прошлое значение). Не путайте эти функции со свойствами глаз, так как для глаз эти свойства говорят не об интерпретации значений клетки, которой эти глаза принадлежат, а об интерпретации значений других, обозреваемых ими клеток: 2 - не изменять значение обозреваемой клетки; 3 - инвертировать значение обозреваемой клетки.

Поэтому в таблице первым идет 0 - нет элементарных клеточных автоматов, реализующих релейную схему работы. Вернее, нет в них необходимости.

Изменение направления исследований

leonid_grigorev — Mon, 12 Sep 2011 16:37:52 GMT

За прошедшее время было получено экспериментальное подтверждение правильности выбраных методов построения управляющих клеточных автоматов и методов мутации в процессе эволюционного отбора. Элементарные клеточные автоматы можно получать практически любой размерности. Вопрос только в имеющихся органичениях вычислительных возможностей. Небольшую проблему составляет создание обучающей последовательности. Но, можно обойтись урезанной обучающей последовательностью с последующей корректировкой алгоритма функционирования управляющего клеточного автомата в ручном режиме. При полной обучающей последовательности в этом нет необходимости.
Усложнение решаемой задачи, увеличение количества входных данных и, как следствие, разрастание обучающей последовательности заставили искать другой подход к созданию управляющих клеточных автоматов. Как вариант, рассматриваю технологию создания суперклеточных автоматов из элементарных клеточных автоматов, реализующих элементарные логические функции. Термин "суперклеточные" вынужден применить вместо термина "многоклеточные", так как сам элементарный клеточный автомат является многоклеточной конструкцией. Термин "элементарный" подчеркивает простоту создаваемого объекта. Если для реализации какой-то логики можгут быть применены клеточные автоматы различного размера, то элементрным будет тот, размер которого минимален. Для каждого "кирпичика", обладающего одной-двумя-тремя входными и одной-двумя-тремя выходными клетками, создать обучающую последовательность не составляет никакого труда. Кроме того, откорректировать алгоритм работы элементарного клеточного автомата, при необходимости, в ручном режиме тоже не сложно. Единственное неудобство - количество разновидностей элементарных клеточных автоматов. Но компьютеру это не помеха. В дальнейших статьях будет представлена логика работы таких "кирпичиков" более подробно.
Работа по созданию "зоопарка" элементарных клеточных автоматов уже близится к некоторому промежуточному пункту, когда можно будет собирать суперклеточные автоматы.
Процесс создания суперклеточной конструкции следующий. В некоторое пространство "высыпаются" глобальные входные клетки, глобальные выходные клетки а также случайным образом выбранное какое-то количество элементарных клеточных автоматов различного типа и, уже имея все клетки будущей особи, можно случайно их связать, указав какой глаз куда будет смотреть.
Интересная особенность получается. Чтобы применить генетический алгоритм необходимо как-то пронумеровать последовательность элементарных клеточных автоматов в особи. Но, так как порядок следования автоматов в особи никакого значения не имеет, а имеют значение только межавтоматные связи, то можно менять последовательность элементарных клеточных автоматов в хромосоме. Например автомат 0-1-2-3-4-5-6-7 полность идентичен по своему поведению с автоматом 4-6-1-2-3-7-5-0. Гланое, чтобы межавтоматные связи не нарушались. Т.е. если глаз № 1 Клетки № 2 элементарного клеточного автомата № 1 "смотрит" на клетку № 2 элементарного клеточного автомата № 5, то и перемешанной хромосоме он должен смотреть туда же. Благодаря этому свойству можно не только "рвать" хромосомы в случайном месте, но и "равть" случайным образом перемешанную структуру. Так если в нормальном перечислении рвем в первом варианте на части, например, так: 0-1-2-3 + 4-5-6-7, то в перемешанном виде можно рвать так: 4-6-1-2 + 3-7-5-0.
Такое перемешивание структуры хромосомы может оказаться мощным мутационным свойством. Кроме этой мутации, может быть, ничего другого и не надо, но можно добавить еще следующие технологии:
1) удаление какого-либо элементарного клеточного автомата из хромосомы;
2) добавление нового элементарного клеточного автомата в хромосому;
3) изменение связей;
4) замена типа элементарного клеточного автомата;
5) изменение номеров входных и выходных клеток.

Но до этого еще далеко. А пока продолжается генерация "кирпичиков", о ходе которой я расскажу в последующих статьях.

Анализ результатов серии экспериментов

leonid_grigorev — Wed, 04 May 2011 16:51:21 GMT

Было проведено построение ряда клеточных автоматов с различным количеством соседних клеток. Задача, решаемая управляющим клеточным автоматом описана в предыдущих постах.

Результаты представлены в таблице:

Количество соседей	Поколение первого результата	Номер особи первого результата	Размер особи	Количество тактов расчета
2	37	26601	9	2
3	37	32381	15	2
4	34	13578	10	2
5	54	24577	13	1
6	52	27101	11	4
7	40	18727	15	2
8	50	22209	17	1
9	54	22551	14	1
10	50	16357	12	1
11	28	9629	15	1
12	50	15047	16	1

Можно сделать предварительные выводы:

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

2. Размер особи стабильно начинает возрастать при увеличении количества соседей свыше количества входных и выходных клеток. В данном случае количество входных и выходных клеток равно 9. Это также связано с особенностью реализации программы.

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

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

Дешифровка диаграмм управляющих клеточных автоматов

leonid_grigorev — Sat, 30 Apr 2011 13:36:57 GMT

Возьмем, для примера, диаграмму двухбитового клеточного автомата, о котором я писал вчера. Автомат решает поставленную задачу в два такта. Напомню, моделируем работу клапана. Имеем вход (4 бита), управляющее воздействие (1 бит) и выход (4 бита). При управляющем воздействии = "1" клапан полностью открыт - информация с входных клеток передается на выходные без искажения. При управляющем воздействии "0" на выходе "0". Видим две таблицы:

Глаза (свойства)

Клетка	5	6	7	8
0	3	0	0	0
1	0	2	0	0
2	0	0	3	0
3	0	0	0	3
4	3	3	3	3
5	0	0	0	0
6	0	0	0	0
7	0	0	0	0
8	0	0	0	0

Клетки (функции)

Значение	5	6	7	8
0	1	2	1	1
1	2	1	2	2
2	0	2	0	3
3	0	0	3	3

Как работает этот автомат?

У него имеются входные и выходные клетки, расположенные последовательно - с № 0 по № 4 - пять входных клеток, примыкают к ним с № 5 по № 8 - четыре выходные клетки. Итого, девять клеток. Если в процессе генерации размер клеточного автомата превышает сумму входных и выходных клеток, то это не приводит к перемещению входных или выходных клеток и, тем самым, облегчает программирование алгоритмов.

Итак, в первой таблице, называемой "Глаза(свойства)", находятся свойства глаз клеток с № 5 и до конца автомата. Свойства глаз - это алгоритм предварительной обработки сигнала, поступающего в клетку. В нейронных сетях это аналогично весам связей. Но, так как автомат является битовым, и на вход клетки (в глаза) попадает сигнал либо 1, либо 0, то применить веса нельзя.

Поэтому преобразование информации в глазах выполняется по следующим правилам:

Вход	Алгоритм	Выход	Свойство
0	0	0	глаз закрыт, всегда 0
0	1	1	глаз закрыт, но всегда 1
0	2	0	глаз открыт и передает информацию без искажения
0	3	1	глаз открыт, инвертирование входного значения
1	0	0	глаз закрыт, всегда 0
1	1	1	глаз закрыт, но всегда 1
1	2	1	глаз открыт и передает информацию без искажения
1	3	0	глаз открыт, инвертирование входного значения

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

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

В нейросетях такая связь называется ассоциативной памятью. Все вычисления в клетках производятся параллельно в пределах одного такта. Значения клеток изменяются только после завершения вычислений значений всех клеток автомата.

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

0 - клетка принимает значение "0";
1 - клетка принимает значение "1";
2 - клетка не изменяет своего значения;
3 - клетка инвертирует свое значение.

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

Ход вычислений приведен в таблице:

клетки	входное значение	аргумент функции	значение клетки после 1-го такта	аргумент функции	значение клетки после 2-го такта
0	1		1		1
1	0		0		0
2	1		1		1
3	0		0		0
4	1		1		1
5	0	00	1	00	1
6	0	00	0	00	0
7	0	00	1	00	1
8	0	10	0	10	0

В начале вычислений все значения не входных клеток обнуляются. Состояние всех клеток в начале вычислений показано в столбце "входное значение". Начинаем с клетки № 5. По таблице "Глаза(свойства)" в столбце "5" сверху вниз ищем ненулевое свойство и находим его в строке "0" = 3 - свойство инверсии значения клетки № 0 - записываем "0", так как значение клетки было "1". Далее опускаемся по столбцу "5" и находим ненулевое значение в строке "4" = 3 - свойство инверсии - записываем к 0 еще один 0 слева (значение клетки "4" было равно "1"). Получили аргумент функции клетки № 5 = "00" (битовое выражение), т.е. "0" (десятичное выражение). Теперь по таблице "Клетки (функции)" на пересечении столбца "5" и строки "0" находим значение функции клетки "5" для аргумента "0", равное 1. Значит при таком аргументе значение клетки должно стать "1". Ставим это значение в столбец "Значение после первого такта" таблицы вычислений. И так далее. После второго такта получаем на выходных клетках значения, аналогичные значениям входных клеток с № 0 по № 4. Что и требовалось.
Можно проверить правильность работы автомата для любых входных значений. Но, компьютер делает это гораздо быстрее.

Братья по разуму

leonid_grigorev — Sat, 30 Apr 2011 05:01:09 GMT

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

----------------- начало статьи ---------------------

Многонаправленные нейронные сети или многомерные разнопорядковые клеточные автоматы

Классический нейрон имеет строгонаправленное перемещение информации, а клеточные автоматы переносят информацию в разных направлениях. Обычная схема нейронной сети многовходовая – на входы подаются разные сигналы. Выход же может иметь только одно значение. В клеточных автоматах входа имеют разные значения и результаты выходы имеют разные значения. Возникновение устойчивых структур в клеточных автоматах – это память? А в НС обратные потоки – это память?

Итак, имеем многомерную клетку, работа которой состоит в том (а как работают клеточные автоматы?), чтобы, проанализировав состояние своих рецепторов, создать на их концах соответствующие значения. Значения соответствуют функции обработки конкретных сочетаний входов-выходов.

Берем четырехрецепторную клетку. Возможны следующие комбинации:

1-й вход – преобразуется в 1-й выход – клетка изменяет значение выходной функции по первому входу в зависимости от входного значения по этому же входу.

Пример – нагреватель и нагреваемый объект. Температура нагревателя больше температуры нагреваемого объекта, даже если они соприкасаются. Вода в стакане не нагреется более температуры кипения, как бы печка не старалась. А если нагреватель прекратит нагревать, то у него температура может упасть быстрее, чем у нагретого им объекта.

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

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

Если взять все входы и сформировать все выходы, то это и будет такой маршрутизатор.

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

Выбор вида сигнала.

Значение от 0 до 1. Что-то типа "напряжения"
Количество импульсов. Может быть строго дозировано (только 4 импульса), а может быть переменной длины. Впрочем, длинные последовательности можно разбить на конечные.

При количестве импульсов = 1 получаем детерминированную модель со значениями либо 0, либо 1.

Кто соседи?

Допустим, в некоторое пространство "насыпали" клеток. Как между ними устанавливаются связи?

Ну, во-первых по расстоянию – ближайшие клетки как бы территориально связаны между собой. А сколько будет "соседей"? один, два, четыре, шесть, или больше? Да и как определить расстояние до соседей? Может просто провести" атрофацию" – если сигналы по связям достаточно малы, то и связь не нужна. "Вычеркнуть " связь получается легко. А как установить связь? А если установку связей делать по нагрузкам? Допустим некоторая связь сильно нагружена. Что надо делать? Расширять "дорогу". Надо делать новую связь в этом направлении. Можно сделать параллельную связь. Но две одинаковые связи с двумя одинаковыми клетками – это не путь. Скорее всего перенагрузка связи связана с тем, что клетка вынуждена мультиплицировать канал передачи между разнородными данными. Следовательно надо не просто добавлять связь, а делать "развязку" – вставлять дополнительную клетку или несколько клеток, которые распараллеливают цепочку.

С чего начать?

Возьмем несколько клеток и установим между ними все возможные связи "все-со-всеми". Т.е. для 2 клеток будет установлено 1 связь. Для 3 клеток – 3, для 4 – 6, для 5 – 10. Для 6 – 15. И т.д. по формуле S=n*(n-1)*/2 при n=30 получается количество связей 30*29/2=435. Не так уж и много, но, не пора ли "тормозить"? Решим обратную задачу - сколько нужно клеток, чтобы образовать 10000 связей? = 70 клеток. Получаем поле связей. Теперь предположим, что мы устанавливаем связи не "все-со-всеми", а как получится. Т.е. случайным образом. И значит для установления связей между 70 клетками может понадобиться от 1 до 10000 связей. В первом случае будем иметь резерв в 68 клеток, которые не с какими клетками не связаны, а в последнем случай "все-со-всеми".

Я думаю, что требуется какой-то стартовый капитал, например имеем 100 клеток, между которыми случайным образом установлены 1000 связей. Так как одно-связанные клетки также могут работать – формировать выходной сигнал по входному (эхо), то это нормально. Клетки случайно оставшиеся без связей удаляются с вычислительного поля.

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

А какой-же вычислительной функцией должны обладать клетки?

Если рассмотреть клетку внутри, то между её рецепторами тоже существуют внутренние связи, но их максимальное количество больше, чем в вычислительном поле на количество этих рецепторов – связь "эхо". s=n*(n-1)*/2+n. Но, так как для поля из 6 клеток существует 15 связей, то каждая из клеток может иметь только 5 рецепторов, а значит только 15 внутренних маршрутов. Каждый из которых может каким-то образом изменять принятую информацию. Получается, что информация распространяется по вычислительному полю волнами. Но, это при внешнем возбуждении. А может быть и внутреннее возбуждение. Предположим, информация "закольцовывается" в вычислительном поле. Тогда кольцо время от времени будет будоражить клетки кольца, что вызовет запуск побочных возбуждений. Может быть так получится механизм памяти? Каждый из внутренних маршрутов характеризуется передаточной функцией. При двух рецепторах имеем 3 маршрута. Предположим, что мы передаем или не передаем возбуждение. Пусть в простейшем случае это будет 1. Если на вход 1 поступила 1, то на следующий такт на выходы 1 и 2 поступит, или не поступит 1. В данном случае принятие решения заложено в самой точке входа. И она не знает, что твориться на второй точке. Фактически она решает, кому транслировать пришедшую единицу. Это получилась "неуправляемая" или "голая" маршрутизация. Пришла 1 – кинули по 1 на 1 и 2 рецепторы. В не зависимости от того, что твориться на втором рецепторе. Если в клетке имеется только один вход, то в случае "невозврата" единицы на него эта клетка не нужна – она всегда "молчит". А в случае постоянного возврата единицы она тоже не нужна, так как это дублирование функций клетки, пославшей ей единицу. Значит, должна быть какая-то внутренняя логика когда посылать единицу назад, а когда не посылать. Например, через раз. Получается делитель. Или посылать после приема одной единицы – три в ответ. Это умножитель. Оказывается, для однорецептороной клетки тоже может найтись работа. Это уже не "голая" маршрутизация, а логическая – по заранее установленной программе.

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

"Голая" маршрутизация. Единица траслируется на конкретные рецепторы.
Маршрутизация с памятью – деление или умножение импульсов. Этим может обладать каждый конкретный канал внутри клетки.
Маршрутизация с учетом внешних возмущений.

Маршрутизация с учетом внешних возмущений – это "голая" маршрутизация, но с учетом состояний всех рецепторов клетки. Допустим, на трех-рецептроную клетку подан сигнал 1-0-1. В этом случае клетка формирует ответ 1-1-0.

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

Программы клетки – это некоторые гены. Для трех-рецепторной клетки ген "голой" маршрутизации записывается как три триады 111 101 110 – соответственно для трех рецепторов. Первый рецептор всегда транслирует 1 на все другие и сам. Второй рецептор транслирует 1 на себя и рецептор 3, третий рецептор транслирует 1 на себя и второй.

Ген маршрутизации с памятью в простейшем случае может добавлять 1 к пришедшей или пропускать её. Пришла 1 с рецептора 1 код 1 говорит, что единицу надопропустить и "задержать" в рецепторе на следующий такт. В не зависимости от того, придет или не придет единица в следующем такте, будет считаться, что пришла. Код 0 говорит, что если приходит единица, то её надо задержать на один такт, после чего пропустить. Для трех рецепторов получается трехзначный ген 010 – первый рецептор задержывает, третий задерживает, второй пропускает и запоминает.

Третий ген – логическая маршрутизация выглядит как ряд триад для каждого маршрута:

000 - 0

001 – 1

010 –1

100 –1

101 –0

110 –0

111 –1

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

Входы			выходы			Условие деления/умножения
1	2	3	1	2	3	1	2
0	0	0	1	1	0	00	01
0	0	1	0	1	1	00	01
0	1	0	0	1	0	00	10
0	1	1	0	0	1	11	00
1	0	0	0	1	0	00	10
1	0	1	1	0	0	00	10
1	1	0	1	0	0	00	00
1	1	1	0	0	1	00	00

Расшифровка третьей строки – при появлении на входах ситуации 010 формируется отклик 010, причем по второму выходу происходит пропуск с задержкой (в следующем такте в нем на ходе вне зависимости от внешнего возмущения будет 1), а по третьему входу пропуск со стиранием – в следующем такте на входе три будет 0 вне зависимости от внешнего возмущения).

Получается, что "голая" маршрутизация этими условиями "накрывается". Она вообще не нужна.

Первый такт – считываем состояние рецепторов (опрос соседей).

Второй такт – формируем состояние рецепторов (ответ соседям).

Получается двухтактная модель.

И еще усложнение третьего гена имеем 4 варианта:

00 – ген не работает – осуществляется просто маршрутизация.

01 – происходит пропуск со стиранием или задержка единицы на 1 такт

10 – происходит дублирование единицы на следующий такт

11 – инвертирование входа – если принята 1 – считается, что принят 0 и наоборот.

Ход построения вычислительного поля.

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

Предположим, что параметр изменяется в пределах 0-10 с дискретностью 0.1, а управляющее воздействие в пределах 0-10 с дискретностью 0.1.

На вход вычислительного поля подается код, соответствующий 100 – 8F – 000 0000 – семь бит.

С выхода снимается также семибитный код.

Берем 100 клеток

Случайно соединяем их случайным количеством связей.
Несвязанные клетки удаляем.
Случайно назначаем 7 входных связей и 7 выходных.
Генерируем в каждой клетке случайный генный набор в зависимости от количества связей.
Проводим численный эксперимент – подаем на вход сигналы из всего диапазона входных сигналов
Смотрим, что получилось.
Запоминаем конфигурацию и ставим ей оценку пригодности.
Мутируем гены.
Повторяем с п.6 и так 1000 раз.
Выбираем 10 наиболее подходящих случаев.
Скрещиваем их получаем 1000 потомков.
Повторяем п.6 ,7 и 11. Еще раз 100.

А как бы количество клеток и связей закодировать в гены?

А так и закодировать! Первый ген – количество клеток, второй ген –количество связей. И если будет какое-либо движение к успеху, то принятая кодировка правильная. А для этого надо сразу генерировать 1000 вычислительных полей, по вышеприведенной методике тестировать их, выявлять наиболее подходящих, и т.д.

091121

Особь – это многомерный полносвязный клеточный автомат.

Свойства связей внутри клетки описываются 4-мя правилами?

00 – связь работает как константа "0" – всегда передается 0 вне зависимости от состояния рецептора;

01 – связь работает как передатчик состояния одного рецептора на ругой ("Проводимость");

10 – связь передает инверсное состояние рецептора.

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

Вычислительные свойства рецептора описываются двумя состояниями:

0 – осуществляется операция "И";

1 – осуществляется операция "ИЛИ".

Предположим, мы хотим построить особь, которая имеет 8 входов (2⁸ = 128 значений, что позволяет различать входной параметр с точностью 1/128 = 0.0078 диапазона измерения). И 8 выходов – что также позволяет получить сигнал с градацией 0.0078 диапазона. Для этого берем многомерный полносвязный клеточный автомат, состоящий их 17 клеток. Получаем 17*(17-1)/2= 136 межклеточных связей. Каждая клетка будет иметь 16 рецепторов. Теперь берем одну клетку и "разрываем". Присваиваем 8 рецепторам из неё значение "вход", а оставшимся другим рецепторам "выход".

Внутренние связи клетки определяются двунаправленными межрецепторными связями, количество которых равно 16*(16-1)= 240 и вычислительными свойствами рецепторов (16 шт).

Следовательно хромосома особи состоит из 16 генов клеток, которые, в свою очередь состоят из 16 генов рецепторных вычислений и 240 генов межрецепторных связей. Получаем длину хромосомы 16(16+240*2)=7936 бит.

Как сохранить наследственность?

Если рассмотреть хромосому как структуру, состоящую из 16 участков – каждый участок соответствует клетке, то внутри такого участка структура выглядит как 16+240*2 битов.

При скрещивании каждый осуществляется скрещивание клетка-клетка, каждая n-я клетка особи 1 скрещивается с каждой n-той клеткой особи 2. Причем, участок клетки со свойствами рецепторных вычислений особи 1 скрещивается только с участком вычислений той же клетки особи 2, и, соответственно, участки переноса скрещиваются только между собой.

Это один способ.

Можно "перемешать клетки" и скрестить разные с разными, но, даст ли это наследование свойств? Этот вопрос можно исследовать в дальнейщем.

Кроме того мутации после скрещивания позволят несколько расшатать аппарат наследования и так.

Процесс скрещивания выглядит следующим образом (как это принято в генетических алгоритмах).

Выбирается случайная пара чисел от 0-16 и 0-240 – точка разрыва гена. Производится скрещивание генов родителей в точке разрыва. При значении 0 происходит полный обмен участками. Получаются две особи. Затем производятся в каждой особи мутации – в случайно выбранной клетке инвертируется случайно выбранный бит. Получаем 4 особи – две немутированных и две с мутациями и две родительских. Из них выбираем 2 наиболее приспособленные и оставляем для следующего скрещивания. Т.о. если скрещивание не принесло улучшения результатов, то родители продолжают этот процесс в новой популяции. Т.к. количество новых особей из двух родителей получается 4, то 2/3 особей исходной популяции отбрасывается и не участвует в размножении.

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

Можно создать "опухоль" – разорвать какую-либо клетку и вставить в неё целую особь.

Еще одна идея – свойства клетки могут носить нечеткий характер, т.е. они присущи клетке с какой-то вероятностью. В клетке "сидит" датчик вероятностей. И в каждый момент времени свойство, например, прямой связи меду рецепторами 3 и 6 имеет то или иное значение в зависимости от значения датчика вероятности. Например, связь отсутствует. А в следующий момент появляется как инвертор. И т.д.

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

---------------------- конец статьи -----------------------

Трехбитовый клеточный автомат

leonid_grigorev — Sat, 30 Apr 2011 04:42:58 GMT

При увеличении количества ненулевых глаз до 3-х, получен в 37 поколении трехбитовый клеточный автомат. Количество клеток резко возросло до 15. Количество тактов осталось прежним - 2.

Глаза (свойства)

Клетка	5	6	7	8	9	10	11	12	13	14
0	2	0	0	0	0	0	0	0	0	0
1	0	2	0	0	0	0	0	0	0	0
2	0	0	0	0	0	2	0	0	0	0
3	0	0	0	2	0	0	0	0	0	0
4	0	3	3	3	0	3	0	0	3	3
5	0	0	0	1	0	0	0	0	0	1
6	2	0	0	0	0	0	0	0	0	0
7	0	1	0	0	0	1	0	0	0	0
8	0	0	1	0	0	0	0	0	1	0
9	1	0	0	0	0	0	0	2	0	0
10	0	0	2	0	0	0	3	3	2	0
11	0	0	0	0	3	0	3	0	0	2
12	0	0	0	0	3	0	0	0	0	0
13	0	0	0	0	0	0	0	2	0	0
14	0	0	0	0	2	0	0	0	0	0

Клетки (функции)

Значение	5	6	7	8	9	10	11	12	13	14
0	1	1	2	3	3		1	0	2	2
1	0	1	0	1	0	1	1	0	1	0
2	0	2	0	3	3		2	0	2	2
3	1	0	3	2	0	3	2	1	3	3
4	0	3	0	2	2	2	3	0	0	0
5	2	1	1	1	1	1	2	2	1	1
6	0	0	1	0	1	2	0	1	1	1
7	1	0	2	2	3	0	2	0	2	2

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

Новая реализация программы генерации автоматов

leonid_grigorev — Fri, 29 Apr 2011 16:55:57 GMT

Сегодня закончил отладку еще одной версии программы.
Немного изменил алгоритмы глаз и клеток.
Для глаз теперь выбор состоит из 4-х свойств:

0 - глаз закрыт - всегда "0";
1 - глаз закрыт, но всегда "1";
2 - глаз передает то, что видит;
3 - глаз инвертирует наблюдаемое.

Для внутриклеточных табличных функций тоже действуют четыре правила:

0 - клетка принимает значение "0";
1 - клетка принимает значение "1";
2 - клетка не меняет значения;
3 - клетка инвертирует свое значение.

Значение аргумента высчитывается из битов глаз. Например, имеем два глаза, значения свойств которых больше нуля. Тогда, переводя их значения из битовой формы в десятичную, получаем значение аргумента внутриклеточной функции. Если бит 0 равен 1 и бит 1 равен тоже единице, то аргумент равен 3, чему соответствует в таблице значение, например, 2. Значит, оставим значение клетки без изменения.
Так как мне не удалось понять механизм скрещивания разнобитовых особей, то пришлось остановится на равнобитовой схеме. Т.е. каждая клетка особи (клеточного автомата) имеет строго определенное количество глаз, обладающих ненулевыми свойствами. Количество таких глаз определяет количество битов, которые обрабатывает клетка. Вообще-то у клетки может быть любое количество глаз, но ненулевыми свойствами могут обладать только строго определенное число, например, 8 глаз. Количество всех глаз у клетки одинаково для всего клеточного автомата. Разные автоматы в популяции могут обладать разными количествами глаз. Вообще-то количество глаз каждой клетки в отдельном автомате равно количеству клеток в этом автомате. А вот количество глаз клеточного автомата, обладающих "ненулевыми" свойствами, равно для всех клеток и одно и то же для всей популяции. В связи с этим можно говорить о битовости клеточного автомата, имея в виду именно количество битов, определяющих аргумент внутриклеточной функции.
Как я уже писал, для экспериментов я использую модель клапана. На 4 входные клетки подается сигнал. На еще одну входную клетку подается управляющее значение. И с 4-х выходных клеток снимается выходящий сигнал. Требуется сформировать клеточный автомат, который при входном сигнале, равным 1, будет без искажений транслировать вход на выход, а при управляющем сигнал, равным нулю, выход в любом случае будет нулевым, то есть отсутствовать.
Первые эксперименты, проведенные уже сегодня, показали, что для двухбитового клеточного автомата в 37 поколении сформирован 9-клеточный автомат со ледующими свойствами глаз и функциями клеток:

Глаза (свойства)

Клетка	5	6	7	8
0	3	0	0	0
1	0	2	0	0
2	0	0	3	0
3	0	0	0	3
4	3	3	3	3
5	0	0	0	0
6	0	0	0	0
7	0	0	0	0
8	0	0	0	0

Клетки (функции)

Клетка	5	6	7	8
0	1	2	1	1
1	2	1	2	2
2	0	2	0	3
3	0	0	3	3

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

Выращивание битового клеточного автомата

leonid_grigorev — Fri, 18 Mar 2011 19:14:06 GMT

В статье "Битовый автомат помог сделать следующий шаг" был изложен принцип создания битовых клеточных автоматов, но до реализации конкретного механизма для выращивания любых битовых клеточных автоматов я, к сожалению, дошел только сегодня. "К сожалению" - потому что на пути реализации "роддома" для битовых клеточных автоматов были трудности различного рода. И путь этот был очень интересен. А теперь, когда "роддом" создан, стало как-то грустно. Опять всё решено и решать больше нечего... Но, не будем о грустном.
Поставленная задача: создать механизм "выращивания" битовых клеточных автоматов, который не зависит от количества входных и выходных клеток, функции преобразования во всех клетках которого заданы табличным образом и так же "выращиваются".
От предыдущих предположений о функциональном наполнении глаз осталась только "зрячесть", так как другие свойства для битовых глаз не имеют реализации.
От внутриклеточных функций, набор которых, описан в статье "Ядро" и следа не осталось. Первоначально я предполагал, что удастся "вырастить" таблицу для функции ядра, набирая одну мутацию за другой. Но, в эксперименте оказалось, что такой подход не продуктивен. Время вычислений очень сильно увеличивается и даже в 1000-ном поколении до оптимума не добраться. Пришлось ограничить свой аппетит таблицей из 256 точек, что привело к ограничению "открытых" глаз для каждой клетки 8-ю. В принципе, для экспериментов, вполне достаточно.
Идея одновременного выбора размера клеточного автомата, описанная в статье "Скрещивание ужа и ежа" , оказалась полностью работоспособной при некоторых ограничениях. В экспериментах наблюдался неограниченный рост хромосом. Чтобы его как-то ограничить, пришлось применить удаление лишних клеток по принципу - если на клетку никто не смотрит, значит она не нужна.
Еще один неясный момент с количеством тактов расчета. Клеточные автоматы живут тактами. И было не ясно, сколько же тактов давать им на жизнь? Пока решил, что "роддом" сам выберет количество тактов, но не более 16-ти. Число взято "с потолка". Но получилось, что реальный результат достигается за меньшее число тактов. Иногда, и чаще всего, на простых конфигурациях, это 1 такт, иногда 5-6. Редко 12. Впрочем, это не вопрос. Если понадобится, то число тактов можно увеличивать.
Как это все работает? Допустим, нам надо создать клеточный автомат, реализующий функцию клапана. На входе имеем параметр и "заслонку", на выходе либо ноль при закрытой заслонке, либо значение входного параметра. Предположим, что параметр займет 4 бита, "заслонка" - один бит, выход также 4 бита.
Составляем таблицу для обучения (приведено небольшое начало таблицы в csv-формате):

5:4:0:0:0:0:0:0:0
0:0:0:0:1:0:0:0:0
0:0:0:1:1:0:0:0:1
0:0:1:0:1:0:0:1:0
0:0:1:1:1:0:0:1:1
0:1:0:0:1:0:1:0:0
0:1:0:1:1:0:1:0:1
0:1:1:0:1:0:1:1:0
...

В первой строке рассказываем "роддому", что входных битов будет 5, а выходных - 4.
В последующих строках обучающие последовательности. Как видим, при значении 1 пятого бита выход должен повторять вход. Если же этот бит будет равен нулю, то на выходе должны быть сплошные нули.
Таблица получилась небольшая, всего 32 строки. Запускаем "роддом" и через 50 поколений (в данном случае) получаем клеточный автомат, который способен работать по данному алгоритму.

Генетический алгоритм построен по следующей схеме:

0. Создание популяции - создается популяция разновеликих особей в количестве 200 штук. Цифра взята в результате предыдущих экспериментов с клеточными автоматами. Как оказалось, что это оптимальный размер популяции.
1. Случайный выбор родителей. При неслучайном переборе популяции время расчета увеличивается весьма существенно!
2. Кроссовер. Ну, тут все просто - способ "ре-кле" - разрезали и склеили. Получили две новых особи.
3. Оптимизация размера. Чтобы не жирели. Удаляем "лишние" клетки.
4. Случайные мутации. Случайно выбирается количество мутаций от 1 до 5 штук. Ограничение опять же взято "с потолка". За одну мутацию осуществляется изменение таблицы открытых глаз. Один открытый глаз закрывается, один закрытый открывается. Опять же случайным образом. И, кроме того, изменяется функциональная таблица случайно выбранной клетки. Случайно выбирается правило и изменяется его действие. Например, если правило приводило к единице, то случайно изменяется на ноль или на неизменение значения клетки. Надо было бы добавить сюда и инверсию.
5. Определение приспособленности. Взяли, посчитали для различного количества тактов. Выбрали наилучшее значение и количество тактов, при котором оно получается.
6. Конкуренция. Убивается наименее приспособленная особь, в том числе и новорожденная, если она как раз менее приспособлена.

Пока не решена задача многоклеточности. Не в смысле много клеток в одном автомате, а много автоматов в одной особи. В статье "На пути к многоклеточности" удалось "подсмотреть" идею объединения клеточных автоматов. Но, пока не понятно, зачем это делать? В сети встретил предположение, что многоклеточность появилась в результате голода. "Голод превращает одноклеточные организмы в многоклеточные - Наука и техника - Биология - Компьюлента". Интересная цитата: "Тут необходимо подчеркнуть, что поляризация клеток (когда у них появляются молекулярно-морфологические «перед» и «зад», или «верх» и «низ») — это главный процесс в развитии организма и образовании всякой ткани и органа". Получается, что у моих клеточных автоматов как раз это имеется - "перед" это входные клетки, "зад" это выходные клетки. Значит они вполне готовы к преобразованию в многоклеточные особи. Осталось понять, зачем это нужно и как их объединять... Так что зря я плакался в начале статьи - есть еще над чем размышлять!

Применение КА. Моделирование автотранспортных потоков

leonid_grigorev — Mon, 14 Feb 2011 11:54:10 GMT

Долгушин Дмитрий Юрьевич.
Многофакторное моделирование автотранспортных потоков на основе клеточных автоматов.

Защита диссертации на соискание ученой степени кандидата технических наук состоится 11 марта 2011 года в Тюменском государственном университете. С диссертацией можно ознакомиться в библиотеке университета.

Краткое содержание автореферата:

Рассмотрены подходы к проблеме моделирования автотранспортных потоков, ставшей актуальной с середины XX века и нашедшей своё отражение в работах Б. Гриншилдса, М. Лайтхилла и Дж. Уизема. Исследования в этом направлении продолжены И. Пригожиным, Р. Германом, Д. Газисом. В настоящее время проблемой активно занимаются К. Даганзо, Б.С. Кернер, М. Шрекенберг, К. Нагель, Д. Хелбинг.

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

Автомат представлен массивом ячеек длины и ширины (число полос). Длина ячейки характеризует разрешающую способность автомата и принимается равной 5,5 м (значение ширины ячейки не оказывает влияния на обновление автомата и потому опущено). Т. к. время в модели дискретно и один шаг обновления соответствует 1 сек, возможно моделирование движения машин со скоростью 20, 40, 60 км/ч и т. д.

Каждая ячейка массива представляет сегмент дорожного полотна и обладает эксплуатационным состоянием, которое обозначается с помощью параметра. Его значение варьируется от 0 до 3: 0 — движение невозможно; 1 — площадь повреждений превышает 2,5 м2 на 1000 м2; 2 — площадь повреждений не выше 2,5 м2 на 1000 м2; 3 — выбоины и прочие дефекты на дороге отсутствуют (нормы согласно ГОСТ 50597-93). Каждому значению соответствует рекомендованная скорость движения.

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

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

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

Игра «Жизнь» или вся жизнь игра?

leonid_grigorev — Sun, 06 Feb 2011 11:37:32 GMT

Клеточный автомат, придуманный английским математиком Джоном Конвеем в 1970 году, получивший название Игра «Жизнь» (англ. Conway's Game of Life), был тем самым началом моего интереса к клеточным автоматам.

Правила игры:

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

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

Казалось бы - что толку в этой митушне клеток?

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

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

Герард Хоофт, являющийся лауреатом в 1999 году Нобелевской премии по физике разработал новую теорию, должную объединить квантовую механику и гравитационное взаимодействие. В новой исследовательской работе Нобелевский лауреат проводит моделирование взаимодействия в рамках целой Вселенной как единой системы из массива клеток.

Стивен Вольфрам уверяет, что все явления, которые мы видим вокруг себя, подчиняются простым правилам и скоро мы сможем найти единое правило Вселенной — то есть объяснить все. В своих объяснениях он использует все теже самые клеточные автоматы.

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

Приветствие

leonid_grigorev — Tue, 11 Jan 2011 18:12:28 GMT

Здравствуйте!
Благодарю Вас за посещение моего живого журнала старого инженера.
Это просто технический дневник, посвященный созданию управляющих клеточных автоматов.
Основное применение этих математических систем - визуализация различных физических процессов - течение жидкости, теплопроводность и другие. Можно поиграться ими в жизнь. Все зависит от алгоритма, закладываемого в каждую клетку. Я немного отошел в сторону от этого направления и решил попробовать использовать клеточные автоматы в роли управляющих структур. Похоже получается что-то среднее между клеточными автоматами и нейронными сетями, впрочем, всё это разные слова из одной песни под названием графы. Не смотря на свой преклонный возраст, занимаясь самообразованием в этой области, получаю огромное удовольствие от процесса выращивания вычислительных структур. По ходу дела получается некий инкубатор клеточных автоматов. Мне нравится постоянно переделывать этот инкубатор. Ставить на нем эксперименты и наблюдать как рождаются мои автоматики. Единственным методом инкубации является генетический алгоритм. Процесс познания идет медленно. Для меня это развлечение. Поэтому тем, кому не терпится узнать что-то конкретное, рекомендую заняться этими исследованиями самостоятельно. Может быть у Вас получится всё гораздо быстрее и веселее. А я буду продолжать своё баловство в темпе, который мне нравится. Если у Вас есть что сказать по рассматриваемому направлению - добро пожаловать в комментарии.
С уважением,
Григорьев Леонид Николаевич,
г. Кривой Рог, Украина.

На пути к многоклеточности

leonid_grigorev — Mon, 10 Jan 2011 15:59:06 GMT

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

Источник

Вот только в моем случае "липкость" пятнышек получается пока однонаправленной. В управляющем клеточном автомате я различаю два вида клеток - входные и все другие. Входные клетки не смотрят внутрь автомата, а как раз являются наблюдателями за внешним миром. А вот все остальные клетки могут быть теми, к которым взор входных клеток других клеточных автоматов может быть направлен. Тогда слипание клеточных автоматов будет происходить между входными клетками одного автомата и обычными другого. Характерной особенностью искусственных коллоидных систем — пятнистых коллоидов (patchy colloids) является их геометрия. Они имеют размеры. "Липкие" точки находятся на каком-то определенном расстоянии друг от друга, как показано на рисунке. У моих же клеточных систем геометрии никакой (пока) нет. Вариант шарообразного клеточного автомата - это всего лишь вариант. Если равномерно разместить клетки на шаре, то и тут пока не понятно, какого радиуса должен быть шар? Так как в популяции "проживают" разновеликие клеточные автоматы, то должны ли их оболочки быть равными или разными? Вопросов больше, чем ответов. Но, идея искусственных коллоидных систем мне очень понравилась!
А зачем? Зачем мне объединение клеточных автоматов в многоклеточную структуру? Вероятно можно вырастить клеточный автомат на любой случай. Мне так кажется, что увеличение одного клеточного автомата приведет к высоким непроизводительным вычислительным потерям. Для обсчета его математики может не хватить вычислительных ресурсов. В объединении автоматов в много-автоматную структуру может быть выход из этой ситуации. А может быть и нет. Ставим исследование этого момента в план экспериментов.

Битовый автомат помог сделать следующий шаг

leonid_grigorev — Thu, 30 Dec 2010 17:44:14 GMT

Создавая технологию разработки управляющих клеточных автоматов я применял подход, используемый в искусственных нейронных сетях, немного изменив его для своих целей. В искусственных нейронных сетях обучение сети производится подбором весов связей. Ни структура ИНС, ни математика нейрона, а в основном это применение сигмоидальной функции к сумме входных значений, не подлежат изменению в процессе обучения. У меня же в процессе обучения изменяются не только веса, но и чувствительность связей, а также структура сети, количество элементов сети и внутриклеточная математика. Автомат сам растет или уменьшается в зависимости от решаемой проблемы. Один момент мне все время не нравился — ограниченный выбор вариантов внутриклеточной математики. В последнем варианте программы осуществляется выбор всего из 16 алгоритмов. Кроме того, применение некоторых алгоритмов, требовало нормирования результатов вычислений чтобы не выходить за пределы интервала [0,1].

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

Несколько идей помогли сдвинуться с мертвой точки.
Первая — цветные клеточные автоматы, которые представляют собой многослойную плоскую структуру, каждому слою которой присваивается определенный цвет.
Вторая идея — битовый клеточный автомат. Если входные значения — биты, то какой может быть математика клетки? Скорее всего элементарной логикой.
Третья идея — представление функций в виде таблиц. Изменяя таблицу мы конструируем новую функцию.
И четвертая идея — ограничение разрядности вычислений реальными значениями. В технике точность обычных измерений редко бывает выше 1%. Для такой точности вполне хватает одного байта. При необходимости точность легко увеличивается путем увеличения разрядности числа.

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

Рассмотрим простой двухклеточный битовый автомат, решающий задачу инвертирования входящего значения. Первая клетка — входная. Она не имеет глаз и потому никаких внутриклеточных вычислений в ней не производится. Вторая клетка — выходная. Она имеет два глаза и, соответственно, два входных сигнала, которые могут принимать значение 0 либо 1. Схема такого автомата приведена на рисунке.

Для обеспечения правильного функционирования автомата достаточно одного правила. Если клетка 1 имеет значение 0, то клетка 2 должна принимать значение 1, а собственное значение должна игнорировать. Если «обязательный ноль» обозначить как 00, обязательную единицу обозначить как 11, то необязательность значения можно обозначить как 01 или 10. В битовой нотации правило инверсии для двухклеточного битового автомата записывается как 0001 или 0010, что равнозначно по своему действию. Такое изображение правила в процессе обучения клеточного автомата методом генетических алгоритмов позволяет изменять его путем мутации случайных битов. Для многоразрядных входных и выходных значений можно применять многоразрядные правила, причем, количество правил для каждого разряда не ограничено. Оптимизацию количества правил (удаление лишних) можно делать после окончания процесса генерации структуры управляющего клеточного автомата как в ручном так и в автоматическом режиме. Исследование данной технологии будет заключаться в определении оптимальных параметров мутации внутриклеточной математики.

Завершение очередной серии экспериментов

leonid_grigorev — Sun, 05 Dec 2010 15:21:35 GMT

Провел эксперименты на 10 популяциях по 2000 особей в каждой. Решал задачи:
1) о влиянии инцеста на скорость достижения результата,
2) поиск методов выбора партнеров.
По первому вопросу никакого вразумительного ответа не получил. Заперт на участи в кроссовере родственников первого или первого и второго колена закономерностей не выявил. А вот второй вопрос удалось решить. В процессе экспериментов установлено, что самым эффективным приемом оказался выбор для кроссовера лучших по приспособленности партнеров с последующим уничтожением двух самых худших особей в популяции. У меня два родителя дают два потомка. Для исключения "топтания" на лучших особях, когда они всё время будут родителями, ввел параметр, учитывающий количество участия особи в кроссовере. Таким образом удалось организовать полный перебор популяции. Если найденное решение не экранировать от последующих расчетов, то, в большинстве случаев, оно начинает сильно доминировать в последующих вариантах решений, иногда оставаясь единственным. Если же найденные решения экранируются от дальнейших вычислений, то появляются другие варианты решений. Если алгоритм выходной клетки фиксировать, т.е. запретить его изменение, то задача решалась для любого алгоритма выходной клетки. Просто решение получалось более сложным.
Напомню, что в качестве "лабораторной крысы" решается задача автоматического программирования реле с уставкой. На входе имеем два аналоговых сигнала - контролируемый параметр и уставку. Диапазон изменения - от 0 до 1. На выходе - логический сигнал - 0, если параметр меньше уставки и 1, если больше либо равен уставке. Самым простым решением из всех вариантов, предложенных генетическим алгоритмом, оказался 3-х клеточный автомат, реализующий задачу по следующему алгоритму:
Если (А - В) больше либо равно 0, то 1;
если (А - В) меньше нуля, то 0, где
А - параметр, В - уставка.
В выходной клетке выбрана генетическим алгоритмом пороговая функция.
В других решениях, использующих в выходной клетке другие функции (медиану, треугольную, пороговую с насыщением и т.д.), клеточный автомат получается более сложным, до 5 клеток, с присутствием элементов ассоциативной памяти. Начальные размеры особей были более 7 клеток (до 24-х), в процессе расчетов образовывались особи размером до 33 клеток, но результат всегда не превышал 5 клеток. Т.е. происходит автовыбор размера и структуры клеточного автомата.
Ближайшие цели - программирование более универсальной программы, позволяющей моделировать клеточные автоматы с бОльшим количеством входных и выходных клеток, а также разработка метода задания алгоритма оценки функции приспособленности вне программы.

Проведен первый комплексный эксперимент

leonid_grigorev — Tue, 30 Nov 2010 16:13:59 GMT

Сегодня проведен первый комплексный эксперимент!
Завершил создание программы для расчета и решил протестировать на 10 популяциях параллельно. Всё, на удивление, получилось.
Исходные данные для всех вариантов сгенерированы случайным образом.Результаты приведены на картинке. Даже второй тест со временем закончился с отличным результатом = 0. Я измеряю приспособленность как отрицательное отклонение от нужного результата. Там, где приспособленность = 0, результат идеальный! Скорость просчета удалось увеличить с нескольких недель до нескольких часов.И притом, провести 10 расчетов параллельно. Больше не пробовал, хотя подозреваю, что можно запустить и больше процессов.
Два предварительных результата видны невооруженным глазом - метод деления хромосом на неравные отрезки дает самые лучшие результаты. Особи быстро приближаются к цели и количество клеток уменьшается. Хотелось бы думать, что получены оптимальные алгоритмы. А вот инцест (кровосмешение) пока не понятно, влияет ли на скорость схождения или нет. Следующие эксперименты поставлю с целью выяснения этого фактора.

In	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0 0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1
0 1	0	0	0	1	1	1	1	0	0	0	0	1	1	1	1
1 0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1
1 1	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1

In	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0 0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1
0 1	0	0	0	1	1	1	1	0	0	0	0	1	1	1	1
1 0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1
1 1	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1

In	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0 0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1
0 1	0	0	0	1	1	1	1	0	0	0	0	1	1	1	1
1 0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1
1 1	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1