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

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

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

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

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

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

 Правила, задающие оценку страхового риска, сконструиро­ваны в виде:

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

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

ЕСЛИ максимальная скорость [91 — 100 км/час] И возраст ав­томобиля [11 — 15 лет] И возраст водителя [31 — 40 лет], ТО риск.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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