3 Модели решения функциональных и вычислительных задач

Моделирование - процесс изучение объекта (его свойств, поведения) на его модели.

Существует два основных способа моделирования:

1. Физическое моделирование. Создается физическая копия объекта, на которой изучаются свойства/поведение объекта (проводятся испытания). Эта копия может копировать как объект целиком, так и только некоторые структуры объекта, требующие изучения. Также при физическом моделировании часто используются уменьшенные копии объекта (Примеры. Макеты зданий/объектов, Испытание моделей самолетов в аэродинамической трубе и т.п. ).

2. Информационное моделирование.

В зависимости от вида данных и способов их обработки (алгоритмов обработки) используются следующие информационные модели:

алгоритмическая модель (математическая модель) - моделирование реализуется с помощью различных алгоритмов. Такое моделирование используется для объектов поведение/свойства, которых можно описать математически (изменение свойств, которых происходит по известным математическим/физическим закономерностям). Примеры. Алгоритмы решения степенных уравнений, Алгоритмы построения кривых в векторной графике, Алгоритмы построения многогранных (объемных) объектов и моделирования отражения света в 3D графике, Алгоритмы расчета тока/напряжения/сопротивления в сети и т.п.;

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

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

иерархическая модель – объекты связанные, иерархическими отношениями образуют ориентированный граф (перевернутое дерево). Иерархическое дерево имеет только одну вершину на самом верхнем уровне;

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

3.1 Графы, деревья, фреймы и сети, Нейронные сети, Генетические алгоритмы

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

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

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

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

Если N- множество узлов, то любое подмножество NxN является обобщенным графом G. Если в парах подмножества NxN имеет значение порядок, то граф G является ориентированным.

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

Если G- обыкновенный граф, в котором имеется п узлов и п-1 связей и отсутствуют циклы, то такой граф является деревом.

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

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

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

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

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

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

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

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

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

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

Генетические алгоритмы (ГА) представляют собой новое направление в алгоритмике. Они способны не только решать и сокращать перебор в сложных задачах, но и легко адаптироваться к изменению проблемы.

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

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

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

Схема генетического алгоритма.

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

2. Вычисление коэффициента выживаемости (fitness). Каждому решению (хромосоме) сопоставляется некое численное значение, зависящее от его близости к ответу.

3. Воспроизводство. Хромосомы, имеющие большую выживаемость (fitness), попадают к потомкам (которые затем могут мутировать) с большей вероятностью. Потомок, результат слияния «отца» и «матери», является комбинаций их ген. Этот процесс называется «кроссинговер» (crossing over).

4. Следующее поколение. Если новое поколение содержит решение, достаточно близкое к ответу, то задача решена. В противоположном случае оно проходит через тот же процесс. Это продолжается до достижения решения.