Ktator

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

В предыдущем материале мы рассказали, как «Горизонт» строит графы и ищет в них кратчайшие пути при помощи модифицированного 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. Повторить.

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

Генотип:

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

[[x0,y0], [x1,y1], … , [xn,yn]]

Фенотип:

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

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

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

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

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

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

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

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

• и др.

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

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

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

Заключение

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

Важно: по этому предварительному проекту будет делаться геодезическая съёмка – то есть специалисты приедут на местность с приборами и будут измерять, где находятся существующие объекты. А съёмка – дело недешёвое, поэтому черновик маршрута должен быть как можно точнее, чтобы не пришлось «снимать лишнего». Кроме того, если смета окажется завышенной, у заказчика могут возникнуть сомнения в её обоснованности (вплоть до разбирательств с ФАС), а при наличии альтернативных поставщиков он и вовсе может уйти к конкурентам. Заниженная же смета грозит убытками для исполнителя.

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

Строительство в городе, кстати, идёт двумя основными способами: либо роется траншея, и туда укладываются трубы, либо используется метод горизонтально-направленного бурения (ГНБ).

ГНБ – это когда специальная бурильная установка делает под землёй точный горизонтальный канал. В этот канал потом прокладываются кабели, трубы и другие коммуникации. Метод особенно популярен в городах, потому что позволяет обойти множество препятствий, таких как дороги, здания или уже существующие сети – и всё это без необходимости вскрывать асфальт.

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

Что такое «Горизонт»?

«Горизонт» – это специальная программа, созданная для автоматизации проектирования наружных и внутренних инженерных сетей. Мы занимаемся такими инженерными сетями, как электрические, газовые и другие как на улице, так и внутри зданий. Наша главная задача – ускорить проектирование, снизить количество ошибок и сделать процесс максимально эффективным по затратам.

Как это работает?

Основная фишка «Горизонта» – это алгоритмы, работающие с графами. Граф – это удобный способ представить любое пространство и маршруты в виде сети точек и соединяющих их линий. В нашей программе графы учитывают множество факторов: от особенностей местности и зданий до существующих объектов инфраструктуры.

Как мы строим графы

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

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

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

А вот когда дело доходит до финального проекта – всё переходит на микроуровень. Здесь мы уже работаем с чертежами из AutoCAD. Это могут быть планы отдельных кварталов, улиц, зданий. И хотя кажется, что тут всё точнее – на самом деле становится ещё сложнее. Почему? Потому что почти всё, что есть на таких чертежах – это просто линии. Линия может обозначать всё что угодно: дорогу, бордюр, стену здания или кабель. Разобраться, где что – задача не из лёгких.

Мы применяем целый арсенал методов, чтобы превратить такие чертежи в осмысленные графы. Это и анализ текста на чертеже (например, если рядом с линией написано "газопровод" – это важный сигнал), и геометрические алгоритмы, которые по форме объекта определяют его тип. Ещё одна задача – это работа с высотами. Часто есть только отдельные отметки на карте, а нам нужно восстановить рельеф – тут на помощь приходят методы интерполяции.

Короче говоря, построение графа – это целая наука. И именно на этом этапе закладывается основа будущего проекта: если граф будет неправильным, то и маршрут получится нерабочим. Поэтому мы вложили максимум сил, чтобы научить «Горизонт» строить графы максимально точно и надёжно.

Как мы ищем путь на графе

Окей, граф построили. Теперь нужно найти на нём маршрут – от точки А до точки Б. Причём желательно, чтобы маршрут был коротким, шёл по нужным улицам и соответствовал нормативам. Тут на сцену выходит наш главный помощник – алгоритм A* (читается как «эй-стар»).

Почему именно он? A* отлично справляется с задачей поиска пути в условиях, когда у нас есть начальная и конечная точка. Он не бродит вслепую по всему графу, а действует умно: прикидывает, насколько «выгодно» двигаться в том или ином направлении, и благодаря этому избегает лишней траты времени на ненужные маршруты.

Но мы пошли ещё дальше. Нам нужно, чтобы маршрут не только был коротким, но и выглядел естественно. Представьте себе маршрут, который зигзагами обходит препятствия, хотя можно было бы провести сеть почти по прямой. Мы внесли небольшие, но важные изменения в A*, чтобы маршруты, которые он строит, были как можно более прямыми и логичными – особенно в тех случаях, когда это не противоречит нормативам.

На практике это дало крутой эффект: маршруты стали не только короче, но и визуально понятнее. Проектировщики сразу видят, где и как лучше проложить сети, а заказчики – получают решение, максимально близкое к их ожиданиям.

Так что да, наш A* – это не просто алгоритм из учебника. Это адаптированная и доработанная версия, которая знает, как проектировать инженерные сети в реальном мире, а не в идеальных условиях.

Как мы ускоряем расчёты?

Используя Python, мы можем очень быстро проверить разные подходы. Самые "тяжелые" расчеты перенесли на язык C++ и GPU (с использованием OpenCL). Это позволяет нам обрабатывать огромные объемы данных за очень короткое время.

Что получилось в итоге?

С помощью «Горизонта» проектировать стало проще и быстрее. Мы минимизировали человеческие ошибки и сделали проектирование намного более экономичным и качественным. Теперь наши заказчики могут проектировать инженерные сети легко, быстро и без лишних затрат!

Вот так просто и удобно работает наш программный комплекс «Горизонт». Мы постоянно улучшаем его, чтобы сделать вашу работу еще легче и эффективнее!