Примеры практического применения генетических алгоритмов

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

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

Рассмотрим пример использования генетического алгоритма для оптимизации экспертных правил в сфере страхования.

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

Рис. 6.6. Схема классифицирующей системы

ЕСЛИ максимальная скорость автомобиля лежит в диапазоне И возрастной диапазон автомобиля И возраст водителя находится в диапазоне ТО страховой риск имеет значение

Для конкретной выборки из БД это правило может иметь сле­дующий вид:

ЕСЛИ максимальная скорость [91 — 100 км/час] И возраст ав­томобиля [11 — 15 лет] И возраст водителя [31 - 40 лет], ТО риск . Здесь уровень риска отображается на интервал [1,5], при этом высокие значения соответствуют большим страховым рискам.

Подобные правила, основанные на фактических значениях переменных, случайным образом выбранных из БД, составляют исходную популяцию. Для каждой из переменных, входящих в популяцию, предварительно задается диапазон состояний. На­пример, переменная «возраст автомобиля», может иметь пять возможных состояний: 1 — 5, 6 — 10, 11 — 15, 16 — 20, 21 — 25 лет. Далее сформированная популяция обрабатывается генетически­ми операторами с учетом специфики рассматриваемой задачи. Целевая функция должна показывать, насколько точно сгенери­рованные правила описывают реальные страховые случаи, храня­щиеся в БД. Например, если какое-то правило описывает 4 слу­чая из 5, то значение целевой функции будет 4/5, или 80%.

Новые члены популяции образуются в результате скрещива­ния и мутации начального набора правил. В данном случае при скрещивании двух правил происходит обмен парами «атрибут -значение» на участке строки после точки кроссинговера. В ре­зультате образуются два новых правила, жизнеспособность кото­рых оценивается по тому, насколько удачно они описывают стра­ховые случаи, которые имели место в прошлом. Мутация правил обеспечивает необходимое разнообразие признаков и заключает­ся в изменении значений атрибутов с заданной вероятностью. Та­ким образом, первоначально сформированный набор правил преобразуется случайно направленным способом в другой набор, который лучше остальных описывает накопленную статистику страховых случаев. Результирующая система правил в дальней­шем используется для прогнозирования страховых рисков.

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

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

сообщения и положительные оценки (поощрения) его действий. Классификатор содержит правила вида ЕСЛИ<условие>, ТО<со-общение>, с помощью которых формируются выходные сообще­ния. Обучающая система выполняет оценку используемых пра­вил. Генетический алгоритм предназначен для случайно направ­ленной модификации правил. Схема обработки правил представ­лена на рис. 7.

Рис.7. Схема обработки правил в классифицирующей системе

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

Шаг 1. В список сообщений (рабочую память) добавляются все сообщения, поступившие извне.

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

Шаг 3. Выполняются правила из списка М, при этом сооб­щения каждого правила посылаются в список новых сообщений.

Ш а г 4. Обновление списка сообщений.

Шаг 5. Сообщения из списка посылаются в выходной ин­терфейс. Вероятность выдачи сообщения зависит от силы прави­ла: не каждое сообщение выдается на управляемый объект, часть их может быть связана с изменением внутренней структуры сис­темы (правил).

Ш а г 6. Возврат к шагу 1.

В процессе обучения каждому правилу присваивается чис­ленное значение силы, а алгоритм обучения регулирует это зна­чение с учетом полезности правила для системы. На шаге 3 опи­санного алгоритма для каждого отобранного правила С вычисля­ется цена по формуле — сила прави­ла С в момент t; — специфичность условия в правиле, равная числу символов, отличающихся от символа * в условии, деленно­му на длину условия; — коэффициент, который обычно прини­мают равным 1/8 или 1/6.

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

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

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

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

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

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

Генетические алгоритмы используют в теории нечетких сис­тем для настройки параметров функций принадлежности. Инте­грация четких и нечетких нейронных сетей и генетических алго­ритмов обеспечивает реализацию оптимизационной задачи. Средства fuzzy-neuro-genetic используются в интеллектуальных системах и содержат следующие процедуры:

• преобразование входных примеров в нечеткое представ­
ление;

• извлечение знаний, представленных в виде продукций ЕС-
ЛИ-ТО из нечеткой обучающей выборки с помощью нейронной
сети;

• оптимизацию структуры продукционных правил с помощью
генетического алгоритма.

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

передаточные функции нейронов скрытых слоев, а также нейронов выходного слоя.

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

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

Генетические алгоритмы чаще всего применяются для улуч­шения характеристик ИНС, уже созданных и обученных с приме­нением других методов