Системы обработки экономической информации

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

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

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

 

1. Основы теории генетических алгоритмов

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

Можно выделить следующие  основные принципы при построении генетических алгоритмов:

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

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

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

 

1. Решение задач с помощью генетических алгоритмов

Рассмотрим на примере  задачи коммивояжера принципы работы генетических алгоритмов. Задача коммивояжера является типичной оптимизационной  задачей. Суть ее заключается в следующем. Дано множество из n городов и матрица расстояний между ними или стоимостей проезда. Цель коммивояжера – объехать все эти города по кратчайшему пути или с наименьшими затратами.

Выберем для определенности пять городов, стоимость переезда между  которыми определяется матрицей:

                                                  0 4 6 2 9

                                                  4 0 3 2 9

                                                  6 3 0 5 9

                                                  2 2 5 0 8

                                                  9 9 9 8 0

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

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

Например, пусть имеются  две родительские перестановки (12345) и (34521). Случайно и равновероятно  выбираются две точки разрыва, скажем, когда первая точка находится между первым и вторым элементами хромосомы (особи), а вторая точка – между четвертым и пятым: (1ç234ç5), (3ç452ç1).

На первом этапе хромосомы  обмениваются фрагментами, заключенными между точками разрыва: (*ç452ç*), (*ç234ç*). На втором этапе вместо звездочек вставляются соответствующие числа из исходной родительской хромосомы, начиная со второго числа выделенного фрагмента (второе – потому что заменяем первое) и пропуская уже имеющиеся в новой перестановке числа (поскольку в данной задаче они в каждой хромосоме могут встречаться только раз)..

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

№ строки	Код	Значение целевой функции	Вероятность участия  в процессе размножения
1 2   3 4	12345 34521   54521 52341	29 29   32 32	32/122 32/122   29/122 29/122

 

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

1. Генетические алгоритмы и нейросети

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

Рассмотрим в качестве примера небольшую сеть прямого  распространения и построим для  нее обучающий генетический алгоритм.

(Трехслойная сеть с тремя  нейронами во входном слое, двумя  – в промежуточном и одним  – в выходном).

Функция активации равна:

Где

 

 

 

Хромосома в нашем случае будет  представлять массив из 11 действительніх чисел, по четыре на каждый скрытый нейрон и по три для выходного нейрона, которые представляют собой веса соответствующих входов нейронов и параметры их функций активации:

 

w11

w12

w13

P1

w21

w22

w23

P2

w31

w32

P3

 

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

 

Тема «Метод группового учета аргументов»

1. Особенности моделирования экономических систем

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

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

• недостаточной априорной информацией;
• большим количеством неизмеряемых параметров;
• зашумленными или короткими выборками данных;
• слабоформализованными объектами с размытыми характеристиками.

Такие проблемы не могут  быть решены декдуктивными логико-математическими  методами с достаточной точностью.

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

 

 

 

1. Идеология и использование МГУА

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

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

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

Со времени разработки этого метода (1967 г.) МГУА широко применялся для моделирования экономических, финансовых, экологических, медицинских и военных объектов во всех развитых странах. Метод широко используется в мире с помощью разработанного в США компанией Ward Systems Group, Inc  коммерческого программного пакета NeuroShell2, в Германии используется программный пакет KnowledgeMiner. Имеется также ряд других программных пакетов, в которых используется этот метод.

В экономической области за годы исследований этот метод был успешно использован, в частности:

• идентификации процесса инфляции в Великобритании;
• моделирования экономики Великобритании с целью более полного выявления законов ее функционирования и управления этим функционированием;
• анализа и прогнозирования показателей экономических процессов в ГДР;
• прогноза и оценки главных действующих факторов в экономике США и др.

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

1. Общее описание метода МГУА

МГУА решает с помощью процедуры перебора многомерную проблему оптимизации модели:

                

,                (1)