Разум, машины и математика. Искусственный интеллект и его задачи - Белда Игнаси. Страница 27
Классическим примером искусственной жизни (вернее, сложной адаптивной системы) в информатике являются клеточные автоматы. Клеточный автомат — достаточно простое понятие, предназначенное для изучения сложности высших систем.
Оно было предложено авторитетными математиками и друзьями Станиславом Уламом (1909–1984) и Джоном фон Нейманом (1903–1957).
Американский математик польского происхождения Станислав Улам.
Автоматы — это математические модели, которые для определенных входных значений запрограммированы на выполнение ряда инструкций. Иными словами, автомат — это обобщение алгоритма или компьютерной программы. Таким образом, в информатике автоматами является все, от программируемого микрочипа, способного выполнять определенные действия, и заканчивая операционной системой. Еще один пример автомата, о котором мы уже рассказывали, это машина Тьюринга.
Как правило, теоретические автоматы, подобные машине Тьюринга, — это устройства, фиксирующие входные сигналы и печатающие выходные значения на одномерных лентах. Автомат проходит вдоль ленты и считывает написанные на ней символы, как показано на рисунке. На основе считанных символов и заложенных в автомат инструкций он выполняет то или иное действие, к примеру, печатает на определенном участке ленты некий символ.
Два основных компонента машины Тьюринга — бумажная лента и устройство чтения-записи.
Клеточные автоматы представляют собой особый класс автоматов, которые не перемещаются по поверхности двухмерных лент. В них среда, содержащая входные и выходные значения, представляет собой плоскость, разделенную на клетки подобно шахматной доске, причем в каждой клетке расположен неподвижный клеточный автомат. Входную информацию в клеточном автомате содержат клетки, смежные с той, в которой он находится. Выходная информация фиксируется в клетке, где расположен сам клеточный автомат.
Каждый автомат, находящийся в одной из клеток доски, содержит ряд инструкций. К примеру, если число черных клеток, окружающих клетку, где расположен клеточный автомат, четно, он закрасит свою клетку в черный цвет, в противном случае — в белый. Поместив аналогичные автоматы во все клетки доски, мы получим различные рисунки, которые будут меняться в зависимости от того, в какой цвет разные автоматы будут закрашивать те или иные клетки.
Некоторые из бесконечного множества возможных конфигураций клеточного автомата порождают повторяющиеся узоры, как, например, в игре «Жизнь» Конвея.
Читатель найдет в интернете множество фигур, порождающих прекрасные рисунки, которые затем уничтожаются и создаются вновь, причем все подобные фигуры описываются очень простыми правилами.
Паровая машина Тьюринга. Рисунок, сделанный студентами Вашингтонского университета в одной из аудиторий.
* * *
КЛЕТОЧНЫЙ АВТОМАТ ДЖОНА КОНВЕЯ, ИЛИ ИГРА «ЖИЗНЬ»
Игра «Жизнь», придуманная Джоном Хортоном Конвеем (род. 1937), представляет собой клеточный автомат, который, несмотря на простоту, демонстрирует удивительное поведение. Правил, описывающих его работу, всего два. В них учитываются восемь клеток, смежных с каждой, а также состояние самой клетки, в которой расположен клеточный автомат.
Правило № 1: если у белой клетки три соседние с ней клетки имеют черный цвет, то эта клетка также окрашивается в черный цвет. В противном случае клетка остается белой.
Правило № 2: если клетка окрашена в черный, а две или три соседние с ней клетки также черного цвета, то клетка не меняет цвет. В противном случае она становится белой.
Если читатель знаком с основами программирования, мы советуем ему реализовать эти простые правила в программе, чтобы посмотреть на игру «Жизнь» в действии. Для всех остальных далее приведено несколько примеров.
Это одна из конфигураций, возникающих при программировании правил игры «Жизнь», известная как «планер». Она порождает следующую циклическую последовательность.
Как показано на иллюстрации, фигура t + 4 идентична фигуре t, но смещена на одну клетку вниз и вправо. Следовательно, в момент времени t + 9 «планер» (именно так называется фигура, изображенная на рисунке) вновь сместится вдоль диагонали, отмеченной на иллюстрации ниже.
Более сложная версия «планера». Если бы изображение было анимированным, вы смогли бы увидеть, что рисунки, расположенные под стрелкой, смещаются вдоль линии, отмеченной на иллюстрации.
Имитация разумного поведения природы всегда была источником вдохновения для инженеров, занимающихся искусственным интеллектом. В свое время природа подсказала человеку идею нейронных сетей и эволюционных алгоритмов, которые сыграли важнейшую роль в развитии искусственного интеллекта. О них мы уже рассказывали в прошлых главах. Аналогично возникли и другие модели, в частности искусственные иммунные системы, в которых предпринята попытка сымитировать поведение иммунной системы живых существ, или роевой интеллект — попытка смоделировать отдельное и простое поведение членов колонии (например, пчелиного роя), в совокупности демонстрирующих определенное поведение, которое можно назвать интеллектуальными.
Иммунная система животного представляет собой крайне эффективную систему распознавания образов и оптимизации. Для каждой новой задачи, которую необходимо решить (то есть для нового антигена, попадающего в тело), путем упорядоченного процесса проб и ошибок иммунная система быстро находит решение — антитело, способное распознать антиген.
Действие иммунной системы напоминает эволюционный процесс с одним отличием: при работе иммунной системы не происходит скрещивания различных решений с целью выявления среднего решения, сочетающего в себе достоинства родительских. Действие иммунной системы можно представить следующим образом.
1. Случайным образом генерируется обширное множество антител.
2. Оценивается пригодность каждого антитела, или его способность распознать антиген, попавший в организм.
3. На основе антител первого поколения по следующей схеме создается второе поколение.
1) Генерируется множество копий антител. Число копий каждого антитела пропорционально его пригодности. Иными словами, новое поколение будет содержать много копий очень эффективных антител, а неэффективные антитела будут присутствовать лишь в нескольких копиях или вовсе не попадут в следующее поколение.
2) В копии антител вносятся изменения (мутации, если использовать терминологию эволюционных алгоритмов) обратно пропорционально их эффективности. Иными словами, копии эффективных антител в новом поколении почти не изменятся, а копии неэффективных антител претерпят серьезные изменения.
4. Для новых антител, полученных на предыдущих этапах, вновь оценивается способность распознавать искомый антиген, после чего весь процесс повторяется, и создается новое поколение антител.