Эвристическое программирование: алгоритмы имитации отжига и муравьиные колонии

Одним из самых известных физически вдохновленных алгоритмов является метод имитации отжига (Simulated Annealing). В металлургии отжиг — это процесс медленного охлаждения расплавленного металла, при котором его атомы успевают выстроиться в идеальную кристаллическую решетку с минимальной внутренней энергией. В исследовании операций этот алгоритм используется для поиска минимума сложных невыпуклых функций. Метод начинает работу при высокой виртуальной температуре, случайным образом перепрыгивая из одного решения в другое. Главная хитрость алгоритма заключается в том, что он может с некоторой вероятностью принимать решения, которые хуже текущего! Эта вероятность зависит от текущей температуры и подчиняется распределению Больцмана.

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

Другим выдающимся примером бионических эвристик является алгоритм муравьиной колонии (Ant Colony Optimization, ACO). Он был вдохновлен тем, как слепые муравьи в природе безошибочно находят кратчайший путь от муравейника до источника пищи. Муравьи оставляют за собой след из пахучего химического вещества — феромона. Чем короче путь, тем быстрее муравей пробегает его туда и обратно, и тем сильнее на этом пути концентрируется феромон, который привлекает других членов колонии. В компьютерной симуляции виртуальные муравьи блуждают по графу задачи коммивояжера. Узлы и ребра с наилучшими результатами получают порцию виртуального феромона, а старые следы со временем программно испаряются.

Эта система коллективного интеллекта самоорганизуется, стягивая тысячи случайных траекторий в один оптимальный маршрут. В арсенал эвристического программирования также входят генетические алгоритмы (основанные на принципах биологической эволюции, кроссинговера и мутаций), алгоритмы роя частиц (имитирующие полет стаи птиц) и поиск с запретами (Tabu Search, который ведет строгий список последних посещенных решений, чтобы алгоритм не ходил по кругу). Метаэвристики совершили революцию в логистике, позволив решать задачи маршрутизации транспорта (Vehicle Routing Problem) с временными окнами для тысяч грузовиков, доказывая, что скорость получения решения в бизнесе часто намного важнее его абсолютной математической безупречности.