Табличная имитация алгоритмов искусственного интеллекта в MS Excel

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

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

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

Генетические и эволюционные алгоритмы являются одним из активно развивающихся и перспективных направлений в искусственном интеллекте. С их помощью могут быть найдены решения многих сложных задач в различных областях, например, при разработке программного обеспечения, в системах искусственного интеллекта,[2] оптимизации, искусственных нейронных сетях и других отраслях знаний.

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

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

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

Возможность обучения — одно из главных преимуществ нейронных сетей (НС) перед традиционными алгоритмами. Обучение НС заключается в нахождении коэффициентов синаптических связей между нейронами. В процессе обучения НС способна выявлять сложные зависимости между входными данными и выходными, а также выполнять обобщение. Это значит, что в случае успешного обучения нейронная сеть может вернуть верный результат на основании данных, которые отсутствовали в обучающей выборке, а также неполных или «зашумленных», частично искаженных данных.

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

Характерной особенностью моделируемых алгоритмов является то, что все они опираются на метод простых итераций, где в клеточных автоматах один цикл итераций означает смену одного поколения популяции клеток, в генетических алгоритмах — цикл скрещивания, мутации и отбора, в ИНС — обучение нейронной сети на одном учебном образце. По этой причине все эти алгоритмы потребовали использования электронных таблиц в режиме множественного пересчета ЭТ, т.е. разработки нестандартных итерационных табличных моделей.

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

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

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

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

Для демонстрации возможности табличной реализации КА рассмотрим два знаменитых клеточных автомата: компьютерную игру Жизнь Конуэя и Муравья Лэнгтона, — а также табличное моделирование спиральных автоволн.

Компьютерная игра Жизнь Конуэя разыгрывается на двумерной решетке клеток, каждая из которых может находиться в двух состояниях:

1 (живая) или 0 (мертвая). Состояния всех клеток меняются синхронно по шагам. На каждом следующем шаге новое состояние клетки определяется текущим состоянием ее окружения по правилам:

1. Клетка, имеющая ровно три живых соседа из восьми, оживает (рождение);
2. Живая клетка, имеющая два или три живых соседа, не изменяет своего состояния (выживание);
3. Во всех остальных случаях клетка умирает (гибель от одиночества или перенаселения).

Далее, следуя великолепной программе М. Войтовича Mcell для исследования дискретных клеточных автоматов, вместо модели игры Жизнь создадим более общую табличную модель семейства клеточных автоматов Жизнь.

Табличная модель семейства КА Жизнь состоит из закрепленной области пользовательского интерфейса в интервале ячеек R1C1:R6C53 (рис.1) и пяти двумерных массивов клеток размером 50х50 ячеек для хранения информации о состоянии клеточного автомата (для краткости будем называть эти массивы полями клеток):

1. R8C3:R57C52 — поле клеток Начальное состояние КА, предназначено для задания детерминированного начального состояния клеточного автомата;
2. R59C3:R108C52 — поле клеток Инициализация КА, при сброшенном флаге Хаос содержимое этого поля является копией поля клеток R8C3:R57C52, при установленном флаге Хаос его ячейки заполняются нулями и единицами случайным образом с заданной вероятностью жизни;
3. R110C3:R159C52 — поле клеток Текущее состояние КА, в каждой итерации определяет текущее состояние клеток автомата: 1 — живая клетка, 0 — мертвая клетка;
4. R161C3:R210C52 — вспомогательное поле клеток Состояние окружения, в клетках этого поля рассчитывается число живых клеток, окружающих каждую клетку поля клеток R110C3:R159C52. Если установлен флаг Центр, то помимо состояния восьми ближайших соседей (окружение Мура) учитывается также состояние центральной клетки;
5. R212C3:R261C52 — поле клеток Копия состояния КА, является копией поля клеток R110C3:R159C52.

Пользовательский интерфейс модели (рис.1) включает:

• таблицу переходов КА в интервале ячеек R2C6:R4C15;
• управляющие флаги Хаос и Центр и связанные с ними ячейки R1C17, R3C17;
• зависимые от R1C17, R3C17 ячейки R2C17, R4C17, в которых по формулам [R2C17]: = ЕСЛИ(R1C17; 1; 0) и [R4C17]: = ЕСЛИ(R3C17; 1; 0) логические значения ИСТИНА и ЛОЖЬ флагов Хаос и Центр преобразуются в числовые значения 1 и 0;
• управляющие кнопки Пуск и НУ, с которыми ассоциированы универсальные макросы StartBtn_Click() и InitBtn_Click();
• входные ячейки Вероятность жизни R2C23 и Число итераций R2C50;
• ячейка Флаг ручного включения итераций R3C50, устанавливается и сбрасывается программно c помощью макросов StartBtn_Click() и InitBtn_Click();
• ячейка Счетчик числа итераций R4C50, используется для динамического счета числа выполненных итераций по формуле.

[R4C50]:=ЕСЛИ(Start=1;R4C50+1;0).

Значения ячеек полей клеток R59C3:R108C52, R110C3:R159C52, R161C3:R210C52 и R212C3:R261C52 рассчитываются по формулам:

[R59C3:R108C52] = ЕСЛИ(R2C17=1; ЕСЛИ(СЛЧИС() < R2C23; 1; 0);R[-51]C)[R110C3:R159C52] = ЕСЛИ(Start=1; ЕСЛИ(И(СМЕЩ(R2C5; 2; R[51]C + 1) = 1; R[102]C = 0); 1; ЕСЛИ(СМЕЩ(R2C5;1; R[51]C + 1) = 1; R[102]C; 0));R[-51]C)[R161C3] = СУММ(R[-51]C:R[-50]C[1]; R[-51]C[49]:R[-50]C[49];R[-2]C:R[-2]C[1]; R[-2]C[49]) + (R4C17-1) *  R[-51]C[R161C4: R161C51] = СУММ(R[-51]C[-1]:R[-50]C[1]; R[-2]C[-1]:R[-2]C[1]) + (R4C17-1) * R[-51]C[R161C52] = СУММ(R[-51]C[-1]:R[-50]C; R[-51]C[-49]:R[-50]C[-49];R[-2]C[-49]; R[-2]C[-1]:R[-2]C) + (R4C17-1) * R[-51]C[R162C52: R209C52] = СУММ(R[-52]C[-1]:R[-50]C; R[-52]C[-49]:R[-50]C[-49]) + (R4C17-1) * R[-51]C[R162C3: R209C3] = СУММ(R[-52]C:R[-50]C[1]; R[-52]C[49]:R[-50]C[49]) + (R4C17-1) * R[-51]C[R162C4: R209C51] = СУММ(R[-52]C[-1]:R[-50]C[1]) + (R4C17-1) *R[-51]C[R210C3] = СУММ(R[-52]C:R[-51]C[1]; R[-100]C:R[-100]C[1];R[-100]C[49]; R[-52]C[49]:R[-51]C[49]) + (R4C17-1) * R[-51]C[R210C4: R210C51] = СУММ(R[-52]C[-1]:R[-51]C[1]; R[-100]C[-1]:R[-100]C[1]) + (R4C17-1) * R[-51]C[R210C52] = СУММ(R[-52]C[-1]:R[-51]C; R[-52]C[-49]:R[-51]C[-49]; R[-100]C[-1]:R[-100]C; R[-100]C[-49]) + (R4C17-1) * R[-51]C[R212C3: R261C52] = R[-102]C

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

Визуализация работы КА осуществляется посредством инструмента условного форматирования. Для этого нужно выделить поле клеток Текущее состояние КА, и с помощью команды меню Формат/Условное форматирование указать, чтобы клетки со значением 1 заливались черным цветом, а со значением 0 — белым.

Следует отметить, что упомянутая программа excel позволяет моделировать 13 различных семейств КА, и все эти семейства с небольшими видоизменениями были нами успешно реализованы и в табличном варианте. При этом, в сравнении с программной реализацией, выявились два недостатка табличного моделирования КА: 1) меньший размер полей /разрешение/ автомата, 2) более низкое быстродействие модели. Быстродействие табличной модели можно в несколько раз увеличить, скрыв визуализацию работы КА на время выполнения итераций.

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