ГЕНЕТИЧЕСКИЕ АГЛОРИТМЫ И БЕТОННАЯ СТЕНА

Продолжу про ИИ. Если вы работали с машинным обучением, то могли ощутить то, что я называю бетонной стеной, пределом возможностей.

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

Суть алгоритма простая: для всех параметров, которые входят в ответ, делаем случайный набор. Это у нас будет ген, или ДНК некоей особи. У особи можем посчитать живучесть -- то есть целевую функцию, и оценить, насколько она хороша -- скажем, посчитать время поездки по задаче коммивояжёра, или насколько ракета не дотягивает до идеальной траектории.

Делаем таких случайных особей много штук и считаем их живучесть. Получаем популяцию. Выбираем из популяции самых живучих и делаем им потомство, скрещивая -- каким-либо случайным образом комбинируем их ДНК (можно, скажем, для каждого параметра взять значение случайно из одной или другой скрещиваемых особей). Получаем новое поколение популяции (можно оставлять старых хороших особей или не оставлять -- как хотим). Чтобы не комбинировать одни и те же значения, делаем ещё и мутации -- с вероятностью, скажем, в 1%, выбираем случайный параметр и случайно меняем его.

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

На практике оказалось всё не так хорошо. Из моих опытов я заметил, что алгоритм всё время застревал в далеко не самых оптимальных решениях, и невооружённым глазом было видно, как можно это решение улучшить. Причина -- в том, что мутации по сути двигали параметры бестолково, и почти все мутации отбрасывались. Это был либо плохой локальный оптимум -- то есть, улучшить можно было только поменяв сразу несколько параметров, и точно в нужную сторону. Либо если это не был локальный оптимум, это просто была слепота мутаций.

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

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

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