На этом шаге мы поговорим об их применимости.
Генетические алгоритмы - это не панацея. В сущности, для большинства задач они не подходят. Для любой задачи, для которой существует быстрый детерминированный алгоритм, подход с использованием генетического алгоритма не имеет смысла. Стохастическая природа генетических алгоритмов не позволяет предсказать время их выполнения. Чтобы решить эту проблему, можно прерывать работу алгоритма через определенное количество поколений. Но тогда остается неясным, было ли найдено действительно оптимальное решение.
Стивен Скиена, автор одного из самых популярных текстов об алгоритмах, даже написал следующее: "Я никогда не сталкивался с задачей, для которой генетические алгоритмы показались бы мне подходящим способом решения. Кроме того, мне никогда не встречались вычислительные результаты, полученные с использованием генетических алгоритмов, которые произвели бы на меня благоприятное впечатление" (Skiena S. The Algorithm Design Manual, 2nd ed. Springer. - 2009.).
Мнение Скиены несколько радикально, но оно свидетельствует о том, что к генетическим алгоритмам следует прибегать, только когда вы совершенно уверены: лучшего решения не существует. Еще одна проблема генетических алгоритмов - определить, как представить потенциальное решение задачи в виде хромосомы. Традиционная практика заключается в представлении большинства задач в виде двоичных строк (последовательности 1 и 0, необработанные биты). Зачастую это оптимально с точки зрения использования пространства и позволяет легко выполнять функции кроссинговера. Но большинство сложных задач не так легко представить в виде кратных битовых строк.
Еще одна, более специфичная особенность, на которую стоит обратить внимание, - это проблемы, связанные с отбором методом рулетки, описанным ранее. Отбор методом рулетки, иногда называемый пропорциональным отбором по жизнеспособности, может привести к отсутствию разнообразия в популяции из-за преобладания довольно хорошо подходящих особей при каждом отборе. В то же время, если значения жизнеспособности близки, то отбор методом рулетки может привести к отсутствию давления отбора (Eiben A. E., Smith J. E. Introduction to Evolutionary Computation, 2nd ed. Springer. - 2015.). Кроме того, этот метод не работает в задачах, в которых жизнеспособность может принимать отрицательные значения, как в простом уравнении на 67 шаге.
Короче говоря, для большинства задач, достаточно больших, чтобы для них стоило использовать генетические алгоритмы, последние не могут гарантировать поиск оптимального решения за предсказуемое время. По этой причине такие алгоритмы лучше всего применять в ситуациях, которые требуют найти не оптимальное, а лишь приемлемое решение. Эти алгоритмы довольно легко реализовать, но настройка их параметров может потребовать множества проб и ошибок.
На следующем шаге мы подведем некоторые итоги.
