Глобальная оптимизация: генетические алгоритмы и эволюционные вычисления
Ловушка локальных минимумов
Классические численные методы оптимизации, такие как градиентный спуск или метод Ньютона, обладают одним фатальным недостатком: они являются локальными. Подобно капле воды, стекающей по горному склону, они всегда стремятся в ближайшую впадину. Если целевая функция имеет сложный, «гористый» ландшафт с множеством долин (мультимодальная функция), классический метод просто застрянет в первом попавшемся локальном минимуме, и алгоритм так и не узнает, что за соседним холмом скрывается гораздо более глубокая пропасть (глобальный минимум). В задачах проектирования микросхем, маршрутизации логистики или синтеза новых лекарственных молекул попадание в локальный минимум означает неэффективное и дорогостоящее решение.
Для преодоления этой проблемы были созданы методы глобальной стохастической оптимизации. Одним из самых мощных, универсальных и красивых классов таких методов являются генетические алгоритмы (ГА), которые черпают свое вдохновение напрямую из биологической теории эволюции Чарльза Дарвина.
Биологическая метафора: хромосомы, популяции и отбор
В генетическом алгоритме параметры оптимизируемой задачи кодируются в виде цепочки чисел или битов. Эта цепочка называется «хромосомой» или «геномом» особи. Каждая особь представляет собой одно из возможных решений задачи. Алгоритм работает не с одним решением, а сразу с целой популяцией таких особей (например, генерирует 100 случайных начальных решений, разбросанных по всему пространству поиска).
На каждом шаге (в каждом поколении) алгоритм оценивает приспособленность (fitness) каждой особи. Приспособленность — это просто значение целевой функции, которую мы хотим минимизировать или максимизировать. Чем лучше решение, тем выше шансы особи на выживание. Затем вступает в дело оператор селекции (рулетка или турнирный отбор): алгоритм с большей вероятностью выбирает лучших особей для формирования «родительского пула», безжалостно отсеивая слабые, неудачные решения. Это математическое воплощение принципа выживания наиболее приспособленных.
Кроссовер и мутация: двигатели математического прогресса
Выбранные родители должны произвести потомство. Для этого применяется оператор скрещивания (кроссовер). Алгоритм разрезает хромосомы двух родителей и обменивается их частями, создавая детей, которые комбинируют признаки обоих предков. Идея заключается в том, что объединение хороших частей (строительных блоков) от двух качественных решений может породить одно превосходное решение.
Однако селекция и кроссовер могут привести к тому, что популяция быстро выродится и станет состоять из одинаковых особей, застряв в локальном экстремуме. Чтобы поддерживать генетическое разнообразие и исследовать новые, неизведанные участки пространства, применяется оператор мутации. С небольшой вероятностью (например, 1%) алгоритм случайно изменяет один или несколько генов (битов) у потомков. Мутация позволяет алгоритму случайно «перепрыгивать» через холмы целевой функции, вырываясь из ловушек локальных минимумов. Повторяя эти циклы (оценка, селекция, скрещивание, мутация) на протяжении сотен поколений, генетический алгоритм стягивает популяцию к глобальному оптимуму даже для недифференцируемых, разрывных и зашумленных функций, с которыми не справляется ни один градиентный метод.