Application of a Genetic Algorithm for Pipeline Route Design

Full Text

Введение Проектирование трубопроводов является сложной инженерной задачей, требующей специалистов из разных сфер науки и сотен часов для оценки разных факторов: геологических, экологических, экономических и инфраструктурных [1]. При строительстве протяженных магистралей даже незначительные изменения траектории трубопровода приводят к существенной экономии ресурсов. Цель исследования - разработка метода проектирования маршрута трубопровода. Для достижения цели были решены следующие задачи: изучена возможность применения многофакторного анализа пригодности территории; применен генетический алгоритм для оптимизации весовых коэффициентов факторов; предложены варианты траекторий газопровода. Новизна подхода заключается в применении генетического алгоритма для подбора весовых коэффициентов факторов на основе существующих трубопроводов, что позволяет решать задачу даже при отсутствии экспертной оценки влияния факторов на стоимость работ по проектированию маршрута. В качестве координат начала и конца проектируемого газового трубопровода рассмотрены Ковыктинское газоконденсатное месторождение, город Новосибирск и участок в окрестностях Красноярска. Выбор связан с тем, что уровень газификации Красноярского края в среднем составляет около 19 %, что значительно ниже среднего показателя по стране - 73 %[37]. В нефтегазовой отрасли планирование маршрута основано на минимизации затрат на строительство и эксплуатацию трубопроводов: проектирование траектории трубопровода требует построения пути с наименьшей стоимостью прокладки [2; 3]. 1. Методы 1.1. Многофакторный анализ пригодности территории Стоимость прокладки в интересующей области определяется методом анализа пригодности территории. Создается карта пригодности, где каждый пиксель карты имеет значение, обозначающее, насколько конкретный участок подходит для использования [4]. В нашем случае итоговая карта пригодности представляет собой карту стоимости прохождения маршрута [5; 6], в которой чем ближе значение пикселя к нулю, тем выгоднее область. Первым этапом проведения анализа пригодности является определение факторов, влияющих на стоимость [7]. Были выделены следующие группы признаков, усложняющих постройку трубопровода: водные преграды, особенности рельефа, транспортные магистрали и особо охраняемые зоны. Дополнительно был рассмотрен фактор близости к населенными пунктам для баланса между доступностью и безопасностью трубопровода. Основой для формирования факторов пригодности послужили данные из двух источников: OpenStreetMap (OSM)[38], данные из которого получались при помощи плагина QuickOSMв QGIS, и облачного сервиса Google Earth Engine (GEE). Информация по выгружаемым из OSM факторам представлена в табл. 1. Векторные данные преобразовывались в растровые изображения, где значение 1 обозначало наличие фактора, а 0 - его отсутствие. Таблица 1 / Table 1 Данные, обрабатываемые в QGIS / Data processed in QGIS Фактор / Factor Тег выгрузки / Export tag Тип данных / Data type Болота 1-й тип / Wetlands 1st type Wetland = Bog Полигон / Polygon Болота 2-й тип / Wetlands 2nd type Wetland = Fen Полигон / Polygon Болота 3-й тип / Wetlands 3rd type Natural = Wetland (- Fen, Bog) Полигон / Polygon Реки / Rivers Waterway = River Линия / Line Автодороги / Highways Highway = Motorway | Trunk | Primary | Secondary Линия / Line Железные дороги / Railways Landuse = Railway Линия / Line И с т о ч н и к: выполнено М.С. Кондрашиной / S o u r c e: by M.S. Kondrashina В GEE обрабатывались наборы данных: цифровая модель рельефа SRTM[39] для расчета уклонов, снимки ночной освещенности VIIRS[40] за период 01.01.2024 - 31.01.2025 для опреде-ления удаленности от жилых зон и полигоны особо охраняемых природных территорий (ООПТ) из базы WDPA[41]. Уклоны учитывались по следующему правилу: значение менее 20° - 0,5, от 20° до 40° - 0,8, а свыше 40° - 0.9. Удаленность от населенных пунктов рассчитывалась через евклидово расстояние и инвертировалась для соответствия логике анализа, где 1 - это зоны вблизи городов, а 0 - удаленные территории. Также добавлялись буферные зоны вокруг некоторых факторов. Например, для автодорог устанавливался буфер 25 м, для железных дорог - 50 м, а для болот и рек - 30 м. Это позволило учесть не только непосредственное наличие объектов, но и влияние зоны вокруг. На основе обработанных данных была сформирована карта стоимости с применением методов растровой алгебры. Рассчитывается взвешенная сумма факторов (без ООПТ), затем для исключения особо охраняемых природных территорий выполняется умножение результата на бинарную маску ООПТ, обнуляющее значение стоимости в этих зонах. На заключительном этапе нулевые значения заменяются на бесконечно высокую стоимость (∞), что исключает их из рассмотрения алгоритмом поиска пути наименьшей стоимости A* [8]. Каждый пиксель финальной карты отражает увеличение стоимости построения пути. 1.2. Генетический алгоритм для оптимизации весовых коэффициентов факторов Традиционно для оценки факторов используют экспертный подход. При анализе литературы были найдены сведения о повышающих коэффициентах для расчета стоимости строительства 1 км трубопровода, прокладываемого в сложных условиях или на пересечениях с естественными и искусственными препятствиями[42]. Данные весовые коэффициенты были нормализованы и выбраны в качестве опорных. В ходе исследования изучался вопрос: насколько полученные коэффициенты факторов актуальны и применимы к нашей территории? Каким образом не представленные в исследованиях факторы следует оценивать? Воз-можен ли анализ при отсутствии экспертных оценок? Мы применили эволюционный алгоритм, в котором в качестве эталона использовался существующий трубопровод, и на его основе получали весовые коэффициенты для каждого интересующего фактора. Генетический алгоритм (ГА) - это адаптивный эвристический метод поиска, основанный на принципах естественного отбора из биологии. Впервые был предложен в 1975 г. Джоном Холландом в книге «Adaptation in Natural and Artifical Systems» [9]. Применение ГА для подбора весовых коэффициентов, влияющих на стоимость прокладки газопровода, приведено на схеме 1 (рис. 1). В алгоритме особи популяции представляются в виде набора весов каждого фактора. Ключевым отличием предложенного решения от общепринятого является блок селекции, поскольку оценка весовых коэффициентов производится на основе построенного маршрута. Следовательно, для каждой особи необходимо получить карту стоимости и спроектировать маршрут на основе алгоритма A*, после чего рассчитать степень схожести между опорным и построенным маршрутами. В каждом поколении лучшие комбинации весов «выживают» и дают потомство, то есть ГА позволяет получить значение веса, оптимального для исследуемых территориальных условий. В работе составляющие блоки алгоритма, описываются следующим образом [10]: 1) селекция - выбор родителей для скрещивания. Применялся турнирный подход, из 5 особей выбиралась одна с максимальным значением оценки; 2) оценка приспособленности (fitness) - совпадение маршрутов (построенного и целевого) и их буферных зон с использованием коэффициента Жаккара, вычисляемого как отношение размера их пересечения к размеру их объединения; 3) скрещивание - комбинация генов родителей для создания потомков. В предложенном решении использовался арифметический метод, где Child = a × Parent1 + (1 - a) × Parent2; 4) мутация - случайное изменение генов (веса одного фактора). Скрещивание / CrossoverПостроение карты стоимости / Cost surface map Превышено число поколений? / Maximum generations reached?да / yesнет / noОценка каждого набора весов / fitness evaluation for each weight set КОНЕЦ / ENDFitness (коэффициент Жаккарда) / Fitness (Jaccard sismilarity coefficient) Мутация / Mutation Новая популяция / New population Селекция / SelectionНахождение маршрута наименьшей стоимости (А*) / Last coast path calculation (A*) НАЧАЛО / STARTИнициализация популяции (весов) / Weight population initializationИзображение выглядит как диаграмма, текст, План, Технический чертеж Содержимое, созданное искусственным интеллектом, может быть неверным. Рис. 1. Алгоритм работы ГА для оптимизации весов факторов И с т о ч н и к: выполнено М.С. Кондрашиной Figure 1. Genetic Algorithm for Optimizing Factor Weights S o u r c e: by M.S. Kondrashina 2. Результаты и обсуждение В качестве опорного трубопровода был выбран участок маршрута Омск - Иркутск, который пролегает через большую часть области интереса и представлен на рис. 2. Для обучения были выгружены все факторы с масштабом растрового изображения 500 м/пкс. Основные параметры используемые во время поиска весов при помощи ГА, представлены в табл. 2. По итогам обучения были получены новые весовые коэффициенты представленные в табл. 3 и спроектированы маршруты газопрово-дов на рис. 3, a и б. Сравнительный анализ маршрутов показывает, что использование генетического алгоритма для настройки весовых коэффициентов позволяет минимизировать расхождения между построенной и обучающей траекторией. Данный результат подтверждает эффективность предложенного подхода для нахождения весов различных признаков с учетом территориальной особенности. Кроме того, в рамках проведенного исследования были разработаны траектории газопро-водов для достижения поставленной цели - газификации Красноярска. Первый маршрут проложен от Новосибирска до участка вблизи Красноярска, а второй - от месторождения Жигалово до этого же места. Оба трубопровода представлены на рис. 4 и 5 в двух вариантах - построение на основе начальных и подобранных коэффициентов. Изображение выглядит как карта, текст, атлас Контент, сгенерированный ИИ, может содержать ошибки. Рис. 2. Участок нефтепровода Омск - Иркутск (точками отмечены рекомендованные места начала и конца газопровода, проектируемого в работе) И с т о ч н и к: выполнено М.С. Кондрашиной Figure 2. Section of the Omsk - Irkutsk Oil Pipeline (points indicate the recommended start and end locations of the gas pipeline designed in this work) S o u r c e: made by M.S. Kondrashina Таблица 2 / Table 2 Параметры обучения ГА / Genetic Algorithm (GA) Training Parameters Параметр / Parameter Значение / Value Число поколений / Number of Generations 10 Размер популяции / Population Size 30 Значение мутации / Mutation Value 0,5 Дополнительный параметр перекрытие путей / Additional Parameter Route Overlap 500 И с т о ч н и к: выполнено М.С. Кондрашиной / S o u r c e: by M.S. Kondrashina Таблица 3 / Table 3 Весовые коэффициенты факторов / Factor Weight Coefficients Фактор / Factor Начальный вес / Initial Weight Подобранный вес / Optimized Weight Болота 1-й тип / Wetlands 1st type 0,5 0,5 Болота 2-й тип / Wetlands 2nd type 0,9 0,4 Болота 3-й тип / Wetlands 3rd type 0,7 0,9 Уклон / Slope 1 0,9 Реки / Rivers 0.7 0,4 Автодороги / Highways 0,6 1 Железные дороги / Railways 0,6 0,3 Удаленность от жилых зон / Distance from Residential Areas 1 0,5 И с т о ч н и к: выполнено М.С. Кондрашиной / S o u r c e: by M.S. Kondrashina Изображение выглядит как текст, диаграмма, снимок экрана, График Контент, сгенерированный ИИ, может содержать ошибки. Изображение выглядит как текст, снимок экрана, диаграмма, линия Контент, сгенерированный ИИ, может содержать ошибки. a б Рис. 3. Построенные маршруты на основе: a - начальных весов; б - оптимизированных И с т о ч н и к: выполнено М.С. Кондрашиной Figure 3. Constructed routes based on: a - initial weights; б - optimized S o u r c e: by M.S. Kondrashina Изображение выглядит как текст, снимок экрана, программное обеспечение, Операционная система Контент, сгенерированный ИИ, может содержать ошибки. a Изображение выглядит как текст, снимок экрана, программное обеспечение, Мультимедийное программное обеспечение Контент, сгенерированный ИИ, может содержать ошибки. б Рис. 4. Маршрут Новосибирск - Красноярск: a - начальные веса; б - оптимизированные веса И с т о ч н и к: выполнено М.С. Кондрашиной Figure 4. Novosibirsk - Krasnoyarsk route: a - initial weights; б - optimized weights S o u r c e: by M.S. Kondrashina Изображение выглядит как текст, снимок экрана, Красочность, График Контент, сгенерированный ИИ, может содержать ошибки. Изображение выглядит как текст, снимок экрана, График, линия Контент, сгенерированный ИИ, может содержать ошибки. а б Рис. 5. Маршрут Жигалово - Красноярск: a - начальные веса; б - оптимизированные веса И с т о ч н и к: выполнено М.С. Кондрашиной Figure 5. Zhigalovo-Krasnoyarsk route: a - initial weights; б - optimized weights S o u r c e: by M.S. Kondrashina Заключение Исследование было посвящено гибридному подходу, соединяющему в себе многофакторный анализ территории и оптимизацию весовых коэффициентов для построения маршрутов с использованием геопространственных данных. Реализация такого подхода позволяет на основе генетического алгоритма и отобранных признаков создать комплексную систему проектирования и принятия решения, сочетающую преимущества искусственного интеллекта и геопространственного анализа. В ходе работы проанализированы полученные из открытых источников факторы, влияющие на стоимость построения газопроводов. Разработанный метод оптимизации весовых коэффициентов с использованием генетического алгоритма доказал свою эффективность для решения задачи проектирования магистральных трубопроводов. Преимуществами предложенного подхода являются автоматизация процесса и учет региональных особенностей территорий. В качестве практического применения нами разработаны траектории для решения задачи газификации Красноярского края. Ограничения вычислительных мощностей при проведении экспериментов позволяли использовать факторы в масштабе 500 м/пкс. Даже при этом получены улучшения для оптимизации весов. При наличии больших вычислительных мощностей рекомендуется использовать максимально доступный для спутниковых снимков Sentinel масштаб - 10 м/пкс, а также увеличить число поколений и размер популяции с целью охватить большую вариативность значений весов. Это, безусловно, позволит получить более качественные коэффициенты при применении генетического алгоритма.

About the authors

Vasily K. Lobanov

RUDN University

Email: lobanov-vk@rudn.ru
ORCID iD: 0000-0001-8163-9663
SPIN-code: 7266-5340

Senior Lecturer of the Department of Mechanics and Control Processes, Academy of Engineering

6 Miklukho-Maklaya St, Moscow, 117198, Russian Federation

Mariia S. Kondrashina

RUDN University

Author for correspondence.
Email: 1132236536@rudn.ru
ORCID iD: 0009-0008-8526-9143

Graduate student of the Department of Mechanics and Control Processes, Academy of Engineering

6 Miklukho-Maklaya St, Moscow, 117198, Russian Federation

Shamil M. Gadzhiev

RUDN University

Email: 1132236511@rudn.ru
ORCID iD: 0009-0006-1570-4133

Graduate student of the Department of Mechanics and Control Processes, Academy of Engineering

6 Miklukho-Maklaya St, Moscow, 117198, Russian Federation

References

Supplementary files