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

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

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

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

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

ЕСЛИ максимальная скорость автомобиля лежит в диапазоне [ A_i ] И возрастной диапазон автомобиля [ B_i ] И возраст водителя находится в диапазоне [ С_i ], ТО страховой риск имеет значение [ D_i ].

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

s (C,t + 1) = s (C,t) − B (C,t).

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

s (C', t + 1) = s (C,t) + aB (C,t),

где a = 1 /К, К − число правил С', т.е. каждый поставщик получает равную долю В.

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

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

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

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

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

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

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

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

• HLN − количество скрытых слоев;

• N_k − число нейронов в каждом слое;

• w_ij − весовые коэффициенты межнейронных связей;

• F_j (X, W) − передаточные функции нейронов скрытых слоев, а также нейронов выходного слоя.

Сформулируем общую задачу оптимизации сети: при заданных количествах входных и выходных нейронов на основе заданного множества обучающих примеров определить оптимальное значение HLN, N_k, k = I,..., HLN, значения всех весовых коэффициентов межнейронных связей w_ij, где j − индекс нейрона; i − индекс межнейронной связи (синапса), F_j(X, W) − передаточные функции всех нейронов, за исключением нейронов входного слоя. Критерием оптимизации является максимальное отклонение выходного вектора сети Y' от эталонного значения выхода, полученное в результате обработки всех примеров, т.е. необходимо найти

(9.4)

где δ = Y' − Y; Q − множество обучающих примеров, содержащих значения X, Y; Y' = F(HLN, N_k, X, W); F(HLN, N_k, X,W) − передаточная функция ИНС, которая строится на основе частных функций отдельных нейронов F_j (X, W).

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

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

Дата добавления: 2014-01-05