Евгений Клочков - Применение эволюционных моделей в современном бизнесе

В качестве примера направленной селекции можно привести удивительную и дорогую породу кошек под названием «саванна». Это домашний вариант дикого сервала, саванна была выведена в 1980-х. Дикие кошки всегда были популярны у представителей элиты, и, чтобы защитить настоящих гепардов и леопардов, селекционеры создали альтернативу. Зверь с виду грозный и опасный, но на самом деле ласковый и коммуникабельный. Первую саванну в 1986 году представил миру заводчик бенгалов Дж. Фрэнк. Она получилась в результате скрещивания самца настоящего сервала с домашней сиамской кошкой. А в 2001-м порода была официально признана и зарегистрирована.

Теория Дарвина много раз подвергалась критике, но идея того, что жизнь развивалась, а не была создана в «готовом» виде, не вызывает сомнений у подавляющего числа ученых. Одним из практических выводов из теории эволюции стало появление генетических алгоритмов, предложенных Дж. Холландом в 1975 году. Генетические алгоритмы нам очень пригодятся для использования в рамках предлагаемой автором парадигмы, и об их применении будет сказано ниже.

Генетические алгоритмы – это адаптивные методы поиска, которые применяются для решения задач оптимизации. В них используется как аналог механизма генетического наследования, так и аналог естественного отбора. При этом сохраняются биологическая терминология в упрощенном виде и основные понятия линейной алгебры. Первая схема генетического алгоритма была предложена в 1975 году в Мичиганском университете Дж. Холландом, а предпосылками этому послужили работы Ч. Дарвина «Теория эволюции» и исследования Л. Дж. Фогеля, А. Дж. Оуэнса, М. Дж. Волша по эволюции простых автоматов, предсказывающих символы в цифровых последовательностях. Новый алгоритм получил название «репродуктивный план Холланда» и в дальнейшем активно использовался в качестве базового алгоритма в эволюционных вычислениях. Идеи Холланда развили его ученики К. Де Йонг из Университета Джорджа Мейсона (Вирджиния) и Д. Голдберг из Лаборатории генетических алгоритмов Иллинойса. Благодаря им был создан классический генетический алгоритм, описаны все операторы и исследовано поведение группы тестовых функций. Именно алгоритм Голдберга и получил название «генетический алгоритм». Для понимания сути генетических алгоритмов и возможности их применения в бизнесе стоит чуть более подробно остановиться на этапах этой модели.

1 этап. Создание новой популяции.

На первом этапе создается начальная популяция. Требования к качеству популяции согласно заданными параметрам некритично, так как в итоге алгоритм эту проблему исправит. Главное, чтобы популяция соответствовала «формату» и была приспособлена к размножению.

2 этап. Размножение.

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

3 этап. Мутации.

Мутации схожи с размножением. Из мутантов выбирают некое количество особей и изменяют их в соответствии с заранее определенными операциями.

4 этап. Отбор.

На этом этапе начинается самое важное. Экспериментатор выбирает из популяции долю тех, кто «пойдет дальше». При этом долю «выживших» после отбора определяют заранее, указывая в виде параметра. Затем цикл повторяется с начала. Если результат не устраивает, эти шаги повторяются до тех пор, пока результат не начнет удовлетворять или пока не произойдет одно из нижеперечисленных условий: либо количество поколений (циклов) достигнет заранее выбранного максимума, либо будет исчерпано время на мутацию.

Генетические алгоритмы относят к области мягких вычислений. Термин «мягкие вычисления» был введен Л. Заде в 1994 году. Это понятие объединяет такие области, как нечеткая логика, нейронные сети, вероятностные рассуждения, сети доверия и эволюционные алгоритмы, которые дополняют друг друга и используются в различных комбинациях или самостоятельно для создания гибридных интеллектуальных систем.

Если упростить, то генетический алгоритм – это метод перебора имеющегося множества с отбором только тех решений, которые отвечают заданным параметрам. В качестве примера можно привести решение задачи о поиске кратчайшего пути из точки А к точке Б. Во-первых, нужно построить любые возможные пути из точки А к точке Б, искать все возможные варианты, смещать уже существующие точки маршрута, добавлять и удалять точки, через которые проходит маршрут, то есть создать максимальное количество вариантов. Затем для выбора кратчайшего пути необходимо посчитать длины маршрутов и сравнить их. В процессе перебора отбрасываем часть самых длинных маршрутов, сравниваем оставшиеся и в итоге оставляем только один – самый короткий. Только практика может показать, какой подход будет верен в контексте конкретной задачи.