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

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

• 1. Оптимизация функций
• 2. Оптимизация запросов в базах данных
• 3. Разнообразные задачи на графах (задача коммивояжера, раскраска, нахождение паросочетаний)
• 4. Настройка и обучение искусственной нейронной сети
• 5. Задачи компоновки
• 6. Составление расписаний
• 7. Игровые стратегии
• 8. Теория приближений
• 9. Искусственная жизнь
• 10. Биоинформатика (фолдинг белков)

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

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

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

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

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

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

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

1. Решение задачи представляется в виде хромосомы. 2. Создается случайный набор хромосом — это изначальное поколение решений. 3. Они обрабатываются специальными операторами репродукции и мутации. 4. Производится оценка решений и их селекция на основе функции пригодности. 5. Выводится новое поколение решений, и цикл повторяется. В результате с каждой эпохой эволюции находятся более совершенные решения.

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

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

Еще один метод — нечеткая логика, моделирующая процессы мышления. В отличие от бинарной логики, требующей точных и однозначных формулировок, нечеткая предлагает иной уровень мышления. Например, формализация утверждения «продажи в прошлом месяце были низкими» в рамках традиционной двоичной или «булевой» логики требует однозначного разграничения понятий «низкие» (0) и «высокие» (1) продажи. Например, продажи равные или большие 1 миллиона шекелей — высокие, меньше — низкие.

Возникает вопрос: почему продажи на уровне 999 999 шекелей уже считаются низкими? Очевидно, что это не совсем корректное утверждение. Нечеткая логика оперирует более мягкими понятиями. Например, продажи на уровне 900 тыс. шекелей будут считаться высокими с рангом 0,9 и низкими с рангом 0,1.

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

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

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

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