Продолжение: как «Горизонт» научился «разумно» прокладывать трассы

Или почему мы решили задействовать эволюционне алгоритмы, если есть классический A*

От классики к эволюции

В предыдущем материале мы рассказали, как «Горизонт» строит графы и ищет в них кратчайшие пути при помощи модифицированного A*. Этот подход прекрасно работает, когда:

• пространство маршрута хорошо формализовано (дороги, тротуары, подземные галереи);  

• критерии оптимизации едины и линейны (длина, стоимость, количество поворотов);  

• ограничения можно записать в виде «жёстких» запретов (минимальный радиус, максимальный уклон).

Однако реальность «на земле» оказывается сложнее. Существуют «мягкие» ограничения («лучше не переходить дорогу под острым углом, но и строго под 90° не обязательно»), мульти-критериальные задачи (одновременно минимизировать длину, стоимость, сроки и риски), а также разные критерии у разных видов инженерных сетей. Например, кто-то хочет делать приоритет траншейного метода, а кто-то — ГНБ.

В итоге мы пришли к тому, что при помощи поиска пути на графе мы строим трассу, которая хороша «почти везде», а дальше доводим её при помощи эволюционных алгоритмов.

Что такое эволюционные вычисления

Эволюционные алгоритмы (ЭА) — это семейство **безградиентных** методов оптимизации, которые имитируют естественный отбор:

1. Кодируем каждый возможный маршрут как генотип (набор точек-опор).  

2. Превращаем генотип в фенотип — реальную ломаную на местности.  

3. Оцениваем «приспособленность» (fitness) по множеству критериев.  

4. Отбираем лучших «родителей», скрещиваем и мутируем их, порождая новое поколение.  

5. Повторяем, пока не получим приемлемое решение или не закончится лимит итераций.

Среди огромного количества вариантов эволюционных алгоритмов мы остановились на CMA-ES (Covariance Matrix Adaptation Evolution Strategy) по следующим соображениям:

• При проектировании протяженных сетей мы часто имеем дело с десятками и сотнями параметров, а CMA-ES отлично себя показывает в непрерывных пространствах высокой размерности;  

• алгоритм автоматически адаптирует «шаг мутации» и направления поиска, учитывая корреляции между переменными;  

• городская застройка создает «холмистый» ландшафт оптимизации с множеством локальных оптимумов (например, обходить здания можно как слева, так и справа, дорогу пересекать можно в огромном количестве мест), и CMA-ES умеет эффективно из них выбираться, так как он устойчив к зашумлённым функциям и и локальным минимумам;  

• не требует ручной настройки большинства гиперпараметров.

Схема одной итерации CMA-ES:

1. Сгенерировать λ особей из многомерного нормального N(m, σ²C).

2. Отсортировать по fitness, взять лучшие μ.

3. Пересчитать среднее m, дисперсию σ и ковариационную матрицу C.

4. Повторить.

Как мы кодируем маршрут

Генотип:

Массив координат «контрольных точек» — вершин ломаной.

Фенотип:

Собственно, сама трасса.

Функция приспособленности (fitness-функция):  

Сумма штрафов и бонусов, которая зависит от следующих параметров:

• длина трассы;  

• стоимость ГНБ-проходки (зависит от диаметра и грунта);  

• штраф за пересечение чужих коммуникаций;  

• штраф за острые углы при переходе через дорогу;  

• бонус за размещение в муниципальном коридоре;  

• штраф за близость к зданиям;

• и др.

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

Пример: эволюция простого маршрута

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

Заключение

Эволюционные алгоритмы, и в частности CMA-ES, стали той технологией, которая позволила нам поднять автоматизацию проектирования инженерных сетей на новый уровень. Благодаря этому, сокращаются трудозатраты и общее время на ввод объектов в эксплуатацию.

Источник