Наши любимые дети

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

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

Читайте также

Последние новости