Интеллектуальные системы в теории принятия решений в экономике

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

Хромосома. Решение рассматриваемой проблемы. Состоит из генов.

Начальная популяция хромосом.

Набор операторов для генерации новых решений из предыдущей популяции.

Целевая функция для оценки приспособленности решения.

Чтобы применять генетические алгоритмы к задаче, сначала выбирается метод кодирование решений в виде строки. Фиксированная длина (j-бит) двоичной кодировки означает, что любая из 2j возможных бинарных строк представляет возможное решение задачи. По существу, такая кодировка соответствует разбиению пространства параметров на гиперкубы, которым соответствуют уникальные комбинации битов в строке – хромосоме. Для установления соответствия между гиперкубами разбиения области и бинарными строками, описывающими номера таких гиперкубов, кроме обычной двоичной кодировки может использоваться рефлексивный код Грея. Стандартные операторы для всех типов генетических алгоритмов это: селекция, скрещивание и мутация.

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

Метод рулетки – отбирает особей с помощью n "запусков" рулетки. Колесо рулетки содержит по одному сектору для каждого члена популяции. Размер i-ого сектора пропорционален соответствующей величине Psel(i) вычисляемой по формуле:

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

Рисунок 3. Оператор селекции типа колеса рулетки с пропорциональными функции приспособленности секторами

Турнирный отбор реализует n турниров, чтобы выбрать n особей. Каждый турнир построен на выборке k элементов из популяции, и выбора лучшей особи среди них. Наиболее рас- пространен турнирный отбор с k=2.

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

Рисунок 4. Одноточечный оператор скрещивания (точка разрыва равна трем)

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

Рисунок 5. Оператор мутации (четвертый ген мутировал)

Алгоритм работы генетического алгоритма (рис. 6) представляет собой итерационный процесс, который продолжается до тех пор, пока не выполнятся заданное число поколений или какой-либо иной критерий останова.

Рисунок 6. Блок-схема генетического алгоритма

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

2.6. Эволюционное программирование

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

2.7. Алгоритмы ограниченного перебора

Эти алгоритмы вычисляют частоты комбинаций простых логических событий в подгруппах данных. Примеры простых логических событий: X = a; X < a; X > a; a < X < b и др., где X – какой либо параметр, ―a и ―b — константы. Ограничением служит длина комбинации простых логических событий. На основании анализа вычисленных частот делается заключение о полезности той или иной комбинации для установления ассоциации в данных, для классификации, прогнозирования и пр.

2.8. Системы для визуализации многомерных данных

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

лаконичное описание внутренних закономерностей, заключенных в наборе данных;

сжатие информации, заключенной в данных;

восстановление пробелов в данных;

решение задач прогноза и построения регрессионных зависимостей между признаками.

Для того, чтобы описывать в многомерном пространстве вложенное двумерное многообразие, используют обычно век-тор-функцию r = r(u,v) от двух координат u, v, которые называются внутренними координатами или параметрами. Линии, вдоль которых одна из внутренних координат принимает постоянное значение, задают на поверхности внутреннюю координатную сетку. Таким образом, любая точка на поверхности задается, с одной стороны, только двумя внутренними координатами (именно поэтому размерность многообразия, задаваемого формулой r = r(u,v) равна по построению двум), а с другой стороны, будучи точкой в m-мерном пространстве имеет m значений координат в исходном пространстве. Для вычислительных процедур гораздо удобнее производить операции не с самим многообразием, а с его точечной аппроксимацией, задаваемой с помощью сетки узлов. Для описания положения прямоугольной сетки узлов в пространстве достаточно mpq чисел, где m – размерность пространства, а p и q – число узлов прямоугольной сетки по вертикали и горизонтали. Если число узлов сетки гораздо меньше числа точек данных, то используя такую сетку в качестве модели данных, можно получить сжатие информации, заключенной в данных, с точностью, зависящей от способа построения карты и особенностями структуры данных. Изначально карта может быть задана с помощью плоской равномерной сетки узлов, как-то размещенных в пространстве признаков. Под действием тех или иных вычислительных процедур карта может искривляться, прилегая к данным и отражая особенности их структуры. После того, как получена точечная аппроксимация многообразия, для того, чтобы восстановить карту нужно воспользоваться подходящей процедурой интерполяции между узлами. Самым простым вариантом интерполяции является кусочно-линейная интерполяция. Для ее построения на сетке реализуется тот или иной вариант триангуляции, в результате чего карта состоит из отдельных треугольных кусков плоскостей.

Рисунок 7. Вид построенной карты

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

Раздел 3. Классификация стадий ИАД

Процесс ИАД состоит из трех стадий:

выявление закономерностей (свободный поиск);

использование выявленных закономерностей для предсказания неизвестных значений (прогностическое моделирование).

анализ исключений, предназначенный для выявления и толкования аномалий в найденных закономерностях.

На рис. 8 показаны стадии процесса ИАД.

Рисунок 8. Стадии ИАД

3.1. Свободный поиск

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

Стадия свободного поиска может выполняться посредством:

индукции правил условной логики (как в приведенных примерах) - с их помощью, в частности, могут быть компактно описаны группы похожих обучающих примеров в задачах классификации и кластеризации;

индукции правил ассоциативной логики - то есть того, что было определено в рамках классификации задач ИАД по типам извлекаемой информации как выявление ассоциаций и последовательностей;

определения трендов и колебаний в динамических процессах, то есть исходного этапа задачи прогнозирования.

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

3.2. Прогностическое моделирование

Здесь, на второй стадии ИАД, используются плоды работы первой, то есть найденные в БД закономерности применяются для предсказания неизвестных значений:

при классификации нового объекта мы можем с известной уверенностью отнести его к определенной группе результатов рассмотрения известных значений его атрибутов;

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

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

3.3. Анализ исключений

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

Раздел 4. Бизнес-приложения ИАД

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

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