кр. Ю. Ю. Громов, О. Г. Иванова, В. В. Алексеев, М. П. Беляев, Д. П. Швец, аи. Елисеев интеллектуальные информационные системы и технологии
 Скачать 2.03 Mb.
|
|
76 Допустим, что компания, занимающаяся страхованием автомобилей, использует базу данных, которая помимо прочих включает следующие факторы максимальную скорость автомобиля (км/час), возраст автомобиля (лет, возраст водителя (лети риск, определённый экспертно по некоторой шкале на основе анализа обращений клиентов о выплате компенсации по страховым случаям. Правила, задающие оценку страхового риска, сконструированы в виде ЕСЛИ максимальная скорость автомобиля лежит в диапазоне АИ возрастной диапазон автомобиля В И возраст водителя находится в диапазоне СТО страховой риск имеет значение [D l ]. Для конкретной выборки из БД это правило может иметь следующий вид ЕСЛИ максимальная скорость [91…100 км/час] И возраст автомобиля лет И возраст водителя [31 – 40 лет, ТО риск [3]. Здесь уровень риска отображается на интервал [1, 5], при этом высокие значения соответствуют большим страховым рискам. Подобные правила, основанные на фактических значениях переменных, случайным образом выбранных из БД, составляют исходную популяцию. Для каждой из переменных, входящих в популяцию, предварительно задаётся диапазон состояний. Например, переменная возраст автомобиля, может иметь пять возможных состояний 1 – 5, 6 – 10, 11 – 15, 16 – 20, 21 – 25 лет. Далее сформированная популяция обрабатывается генетическими операторами с учётом специфики рассматриваемой задачи. Целевая функция должна показывать, насколько точно сгенерированные правила описывают реальные страховые случаи, хранящиеся в БД. Например, если какое-то правило описывает 4 случая из 5, то значение целевой функции будет 4/5, или 80%. Новые члены популяции образуются в результате скрещивания и мутации начального набора правил. В данном случае при скрещивании двух правил происходит обмен парами «атрибут–значение» на участке строки после точки кроссинговера. В результате образуются два новых правила, жизнеспособность которых оценивается потому, насколько удачно они описывают страховые случаи, которые имели место в прошлом. Мутация правил обеспечивает необходимое разнообразие признаков и заключается в изменении значений атрибутов с заданной вероятностью. Таким образом, первоначально сформированный набор правил преобразуется случайно направленным способом в другой набор, который лучше остальных описывает накопленную статистику страховых случаев. Результирующая система правил в дальнейшем используется для прогнозирования страховых рисков. 77 Следует отметить, что подобный подход к формированию системы правил может приводить к некорректным правилам продукций. В тоже время он освобождает разработчиков и экспертов от трудом- кой работы по формулированию и оценке правил, так как некорректные результаты отбрасываются при сопоставлении сгенерированных продукций с реальными страховыми ситуациями. Привлечение прошлого опыта для оценки пригодности прогнозирующих правил не позволяет предвидеть новые ситуации, которые не имели места в прошлом. Поэтому при решении задач описанным способом очень важно следить за своевременным пополнением и модификацией информации в БД, которая отражает появление новых фактов, атрибутов и тенденций. Классифицирующие системы. На основе генетических алгоритмов Дж. Холланд предложил классифицирующие системы, которые можно использовать для целей управления [11, 14, 17, 30]. Классифицирующая система состоит из трёх вложенных друг в друга подсистем рис. 3.6): классификатора, системы обучения и генетического алгоритма. В классификатор поступают внешние сообщения и положительные оценки (поощрения) его действий. Классификатор содержит правила вида ЕСЛИ<условие>, ТО<сообщение>, с помощью которых формируются выходные сообщения. Обучающая система выполняет оценку используемых правил. Генетический алгоритм предназначен для случайно направленной модификации правил. Схема обработки правил представлена на рис. 3.7. Каждому правилу приписывается численная оценка силы правила. Сообщения и условные части правил (антецеденты) формулируются в одних и тех же терминах. Список сообщений содержит все теку- Рис. 3.6. Схема классифицирующей системы 78 Рис. 3.7. Схема обработки правил в классифицирующей системе щие сообщения – поступающие из внешней среды и те, что формируются внутри системы. В процессе работы КС все сообщения из списка сравниваются с условиями всех правил. Классификатор выполняет следующие действия. Шаг 1. В список сообщений (рабочую память) добавляются все сообщения, поступившие извне. Шаг 2. Проводится сравнение всех сообщений из списка с анте- цедентами всех правил. Все правила, антецеденты которых совпадают с присутствующими в рабочей памяти сообщениями, записываются в список правил М. Шаг 3. Выполняются правила из списка М, при этом сообщения каждого правила посылаются в список новых сообщений. Шаг 4. Обновление списка сообщений. Шаг 5. Сообщения из списка посылаются в выходной интерфейс. 79 Вероятность выдачи сообщения зависит от силы правила не каждое сообщение выдаётся на управляемый объект, часть их может быть связана с изменением внутренней структуры системы (правил. Шаг 6. Возврат к шагу 1. В процессе обучения каждому правилу присваивается численное значение силы, а алгоритм обучения регулирует это значение с учётом полезности правила для системы. На шаге 3 описанного алгоритма для каждого отобранного правила С вычисляется цена по формуле ( ) ( ) ( ) t C s C bR t C B , , = , где s (C, t) – сила правила Св момент t; R(C) – специфичность условия в правиле, равная числу символов, отличающихся от символа * в условии, делённому на длину условия b – коэффициент, который обычно принимают равным 1/8 или 1/6. Цена В определяет вероятность того, что правило пошлёт сообщение в список новых сообщений. Вероятностный подход позволяет аутсайдерам тоже изредка посылать сообщения, что при благоприятных условиях может сделать их лидерами. Послать сообщение могут все правила с допустимым значением В, те. такие, у которых В превышает определённый порог. Правило, пославшее сообщение в новый список, расплачивается за это уменьшением своей силы Для правил С, пославших сообщения, которые наследующем шаге работы оказались полезными (совпали с условиями правила- победителя, имеющего высокую цену, оценка силы возрастает на долю В ) , ( ) , ( ) 1 , ( t C aB t C s t C s + ′ = + ′ , где a = 1/K, K – число правил С, те. каждый поставщик получает равную долю В. Правило полезно только тогда, когда его потребители в своих локальных действиях тоже получают выигрыш. В противном случае правило обесценивается, так как его цена s уменьшается при отсылке сообщения. В свою очередь, полезность потребителей зависит от их потребителей и т.д. Цепочка приводит к конечным потребителям, достигающим цели и получающим поощрения от внешней среды. Классификатор и обучающая система не порождают новых правил. Эту функцию выполняет генетический алгоритм, который работает с учётом силы правил, определённой в системе обучения. Работа генетического алгоритма рассмотрена в предшествующем примере. 80 Комбинированные методы и интеллектуальные системы. В настоящее время активно развиваются методы, основанные на объединении технологий инженерии знаний и генетических алгоритмов. В области ГА разрабатываются операторы, ориентированные на обработку знаний. Генетические алгоритмы используют в теории нечётких систем для настройки параметров функций принадлежности. Интеграция чёт- ких и нечётких нейронных сетей и генетических алгоритмов обеспечивает реализацию оптимизационной задачи. Средства fuzzy–neuro– genetic используются в интеллектуальных системах и содержат следующие процедуры преобразование входных примеров в нечёткое представление извлечение знаний, представленных в виде продукций ЕСЛИ– ТО из нечёткой обучающей выборки с помощью нейронной сети оптимизацию структуры продукционных правил с помощью генетического алгоритма. Активно развивается направление, ориентированное на использование генетических алгоритмов для обучения нейронных сетей [5] и корректировки структуры уже обученной сети [18]. В отличие от метода обратного распространения ошибки генетические алгоритмы малочувствительны к архитектуре сети. Напомним, что основными характеристиками нейронной сети являются следующие − HLN – количество скрытых слов − N k – число нейронов в каждом слое − w ij – весовые коэффициенты межнейронных связей − F j (X, W) – передаточные функции нейронов скрытых слова также нейронов выходного слоя. Сформулируем общую задачу оптимизации сети при заданных количествах входных и выходных нейронов на основе заданного множества обучающих примеров определить оптимальные значения HLN, N k , k = l, ..., HLN, значения всех весовых коэффициентов межнейрон- ных связей w ij , где j – индекс нейрона i – индекс межнейронной связи синапса F j (X, W ) – передаточные функции всех нейронов за исключением нейронов входного слоя. Критерием оптимизации является максимальное отклонение выходного вектора сети Y' от эталонного значения выхода Y, полученное в результате обработки всех примеров, те. необходимо найти Q W X F W N HLN j k δ = δ max min ) , ( , , , * , 81 где Y Y − ′ = δ ; Q – множество обучающих примеров, содержащих значения передаточная функция ИНС, которая строится на основе частных функций отдельных нейронов Даже для простых сетей эта задача является очень сложной, поэтому для её решения применяется декомпозиция, те. сеть оптимизируется в процессе последовательного решения частных задач оптимизации. Например, на первом шаге подбираются оптимальные значения HLN и N k , затем определяется оптимальный вид передаточных функций нейронов, а наконечной стадии подбираются веса межнейронных связей. Генетические алгоритмы чаще всего применяются для улучшения характеристик ИНС, уже созданных и обученных с применением других методов. Краткий обзор программных средств. Коммерческое программное обеспечение, реализующее генетические алгоритмы, можно разделить на программные средства общего назначения, прикладные и алгоритмические программные продукты. Программное обеспечение общего назначения включает разнообразные наборы инструментальных средств для построения конкретных программ, которые содержат библиотеки алгоритмов, программы моделирования, средства визуализации и другие инструменты. Пакеты подобного типа рассчитаны на опытных программистов, требуют знания основ теории эволюционных вычислений и характеризуются высокой трудоёмкостью освоения, которая в значительной мере зависит от квалификации пользователя. Прикладные программные продукты ориентированы на решение проблем определённого класса в конкретных предметных областях (реинжиниринг, маркетинг, стратегическое планирование и др. Такие средства не требуют от пользователя теоретических знаний в области методологии создания интеллектуальных систем. Достаточно, чтобы он был специалистом в своей предметной области. Алгоритмическое программное обеспечение поддерживает один или несколько) генетический алгоритм. Преимущества таких программных продуктов – их гибкость и простота использования. При этом пользователям необходимо иметь представление об основах теории ГА. Перечислим некоторые популярные программные средства [13], реализующие технологии оптимизации с применением генетических алгоритмов и дадим краткую характеристику. 82 Система PC/Beagle представляет собой программу поиска решающих правил, классифицирующих примеры из базы данных. Она превращает данные в знания за счёт использования машинного обучения. Один из модулей системы путём репродукции и селекции порождает правила, представленные в виде логических выражений. Система Evolver реализует шесть методов генетической оптимизации и выполнена в виде расширения MS Excel. Основные области применения пакета – оптимизация доходности с учётом уровня риска и максимизация прибыли с учётом возможных издержек. Genesis – известный алгоритмический программный продукт, который используется в качестве инструмента тестирования генетических алгоритмов. Он позволяет создать модифицированную программную среду и обеспечивает пользователя статистической информацией на выходе. Программный продукт общего назначения EnGENEer помогает адаптировать генетические алгоритмы к новым проблемным областям за счёт использования следующих инструментов специального языка, предназначенного для описания структурных понятий генетики (генов, хромосом и т.д.); эволюционного модельного языка, используемого для отображения таких атрибутов, как размер популяции, типы скрещивания и мутации графических инструментов мониторинга библиотеки инструкций. Объектно-ориентированная среда Game содержит пять основных частей виртуальную машину − высокоуровневый генетический язык библиотеку генетических алгоритмов графический монитор компилятор. Система спроектирована так, что допускает параллельное использование нескольких алгоритмов. Для создания конкретного приложения используются библиотечные модули, из которых строится макро- программа с помощью специального высокоуровневого языка. Известный дистрибьютер программного обеспечения фирма «Тора–Инфо–Центр» распространяет пакет Gene Hunter, который может использоваться как приложение MS Excel и допускает составление собственных программ на языках Си. Методы эволюционного программирования Генетическое программирование. Методы генетического программирования были разработаны вначале х гг. Дж. Козой [27 – 29]. Генетическое программирование – это способ создания компьютерных программ для задач с неизвестным алгоритмом решения. Объектом эволюции является программа, а популяция содержит множество различных программ. Совершенствование объекта осуществляется на основе отбора в соответствии с определённой функцией ценности. Программы строятся из блоков, которые представляют собой примитивные функции и терминалы. В качестве примитивных функций обычно рассматриваются арифметические и логические операции, математические функции и функции специального вида, характерные для класса решаемых задач. Множество терминалов содержит разнообразные данные, не создаваемые программой. Цель состоит в построении наилучшей программы в пространстве программ, которые могут быть составлены из заданных функций и терминалов с учётом определённых правил синтаксиса. Технология генетического программирования включает следующие этапы. Этап 1. Формирование множества терминалов, множества примитивных функций, синтаксических правили критериев оценки создаваемых программ. Этап 2. На основе закона случайности создаётся начальная популяция компьютерных программ, ориентированных на решение поставленной задачи. Этап 3. Каждая программа выполняется, а результаты её работы оцениваются с помощью fitness function (целевой функции. Этап 4. Формируется новая популяция программ, в которую сге- нерированные программы могут попасть с вероятностью, пропорциональной значению целевой функции. Этап 5. Реализуются генетические операторы репродукции, скрещивания и мутации. В результате репродукции осуществляется копирование уже созданных программ с хорошими значениями целевой функции. Оператор скрещивания создаёт новые программы путём комбинирования фрагментов существующих программ. Мутация заключается в замене некоторого фрагмента программы случайно поро- ждённым символьным выражением. Этап 6. Производится тестирование программ-членов новой популяции и принимается решение о продолжении процесса эволюции. Продолжать генерацию новых популяций имеет смысл тогда, когда максимальные и средние значения целевой функции улучшаются. 84 Рассмотрим пример [27] модификации программы на языке LISP, где в качестве терминалов используются переменные логического типа а для их обработки применяются логические операции NOT, OR, AND. Пусть на некотором шаге имеется следующее множество допустимых выражений NOT(D 1 ); NOT(D 0 ); AND(D 0 , D 1 ); OR (AND(D 0 , D 1 ), NOT(D 1 )); AND(NOT(D 0 ), NOT(D 1 )); OR (D 1 , NOT(D 0 )); OR (OR (D 1 , NOT(D 0 )), AND (NOT (D 0 ), NOT(D 1 ))). Эти выражения можно представить в виде деревьев (рис. 3.9). В процессе эволюции на уровне поддеревьев осуществляется рекомбинация и получаются потомки (рис. 3.10). Первый из этих потомков представляет собой реализацию операции исключающего ИЛИ OR (AND (NOT(D 0 ), NOT (D 1 )), AND (D 0 , D 1 ). Результатом применения оператора мутации является замена части дерева другим выражением, сгенерированным случайным образом. Точка мутации также выбирается случайно. Рис. 3.9. Представление символьных выражений языка LISP в виде деревьев 85 Рис. 3.10. Потомки от скрещивания родителей на уровне поддеревьев Идеи генетического программирования положены в основу программ, которые называются симуляторами искусственной жизни. В работе Дж. Козы [27] приводится следующий пример подобной программы. На тороидальной сетке размером 32 × 32, в 89 ячейках помещается пища. Существуют некие препятствия, мешающие насекомым добраться до пищи. Насекомые попадают на сетку из одной точки, и каждое движется согласно командам своей программы. В начальной популяции эти программы формируются случайным образом из операторов, которые проверяют наличие препятствий и предписывают движение прямо, влево или вправо. Задаётся время жизни популяции шагов. Цена каждой программы определяется числом шагов, которые необходимо совершить, чтобы обойти все ячейки спи- щей. Каждая следующая популяция формируется из предыдущей с помощью генетических операторов репродукции, скрещивания и мутации с учётом ценности программ предыдущей популяции. Решение для популяции из 4000 насекомых было найдено за 20 итераций. Последователи Дж. Козы исследовали в своих работах возможность использования ГП для синтеза сложных автоматов, а также для структурной идентификации динамических систем [19]. В примере построения экономической балансовой модели [13] поставлена цель уточнения эконометрического уравнения обмена, связывающего уровень цен, валовой национальный продукт (ВНП), запас денег и скорость оборота денег в экономике. В качестве терминалов здесь используются следующие переменные ВНП82 – уровень ВНП за 1982 г GD – дефлятор ВНП (выходная переменная модели, нормализованный к единице для 1982 г FM – ежемесячная величина запаса денег. Приведённые переменные являются функциями времени. Их значения определяются на основе статистических данных в виде временных рядов. Кроме того, используется множество обобщённых констант действительного типа R. Для обработки переменных предусмотрены следующие операции сложение (+); вычитание (–); умножение (*); защищённое деление (%), результатом которого является единица при попытке разделить на 0; защищённое логарифмирование (RLOG), дающее 1 при нулевом значении аргумента вычисление экспоненты (ЕХР). Грубая оценка пригодности сгенерированных уравнений вычисляется как сумма квадратов отклонений расчётных значений от фактических в заданных экспериментальных точках [ ] ∑ = − = N j j h j h S V t R 1 2 ) ( , где Sj – фактическое значение выходного параметра модели j = 1, ..., N; N – число точек h j V – расчётное значение вычисляемого показателя h – индекс сгенерированной модели. Значение R h (t) масштабируется в целях получения нормированной оценки пригодности ( ) ( ) t R t a h h + = 1 1 , которая изменяется на интервале и позволяет перейти к задаче максимизации. На основе a h (t) вычисляется относительная нормированная оценка пригодности ( ) ( ) ( ) ∑ = = M m m h h t a t a t n 1 , которая имеет более высокие значения для лучших членов популяции и обладает свойством ( ) 1 1 = ∑ = M m m t n , допускающим вероятностную интерпретацию. Критерием окончания процесса эволюции является достижение заданного числа генераций (50) или достижение наилучшего значения целевой функции. Численность популяции была принята равной 500. В процессе генерации новых поколений скрещивание проводилось на 90% численности популяции, те. из каждого поколения выбиралось 225 пар родителей с вероятностью, равной относительной оценке их пригодности. Кроме того, для каждой новой популяции осуществлялась репродукция 10% лучших представителей поколения. Генерируемые модели (программы) удобно представить в виде древовидных структур (рис. 3.11). |