Методы эволюционного моделирования в оптимизации инженерных сетей

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

Article is devoted to the problems of optimum designing of external engineering networks taking into account features of concrete district, and also possible variants of their decision by means of methods of evolutionary modeling

Проблема оптимального проектирования сложных пространственно распределенных инженерных систем является одной из самых актуальных. Основные и весьма типичные задачи проектной практики в данной области заключаются в выборе [6]:

• мест размещения и параметров источников;
• конфигурации сети, которая связывает множество рассредоточенных потребителей с источниками;
• параметров всех элементов системы;
• способов развития и реконструкции (при наличии уже существующей части объекта проектирования).

Первые две задачи можно объединить на этапе схемно-структурной оптимизации решать на уровне разработки топологии сети. Исходными данными здесь будут являться координаты и расчётные нагрузки потребителей, а также координаты предполагаемых источников транспортируемой среды. Определение того, будет ли в данном узле находиться источник, происходит уже в процессе решения. Если расход транспортируемой среды на участке трубопровода от некоторого источника в результате

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

Сложность планировочной структуры большинства районов предопределяет и трудности в функциональном использовании их территорий. В этих условиях выбор рациональных трасс коммуникаций, местоположение соответствующих сооружений и устройств диктуются не только их функциональным назначением, но и стремлением вписать их в планировочную структуру района [1]. Предпочтительным в данном случае видится сравнение целевых функций вариантов прокладки трубопроводов на основе специально разработанных карт стоимости различных факторов, влияющих на топологию сети, построенных методом экспертных оценок [5]. В качестве такой целевой функции можно использовать общий вес сети (здесь понятия вес и стоимость синонимичны), который является суммой весов отдельных её участков. Под весом участка понимается произведение длины участка на весовой коэффициент, определяемый для данного участка. Возможны два крайних варианта: если весовые коэффициенты не заданы, обычно за вес участка принимается его длина (и соответствующая задача оптимизации заключается в нахождении такой топологии сети, чтобы общая длина участков была минимальной), с другой стороны, для каждого участка могут быть определены несколько весовых коэффициентов, распределённых по длине участка, что требует вычисления веса каждого участка. Именно второй вариант соответствует определению целевой функции при использовании карт стоимости.

В случае инженерных систем основными факторами, влияющими на оценку и выбор варианта проектного решения, могут служить следующие затраты [6]:

• непосредственно прокладку участков трубопроводов,
• электроэнергию, требующуюся для перекачки среды,
• строительство и реконструкцию насосных станций,
• энергию, доставляемую потребителям.

Каждый из приведённых параметров может рассчитываться по различным формулам в зависимости от конкретной задачи.

Существуют различные технологии генерирования тех вариантов проекта, которые и будут участвовать в сравнении. Так, может использоваться метод избыточных проектных схем, когда проектировщиком задаётся исходная избыточная схема сети, и в процессе решения производят различного рода манипуляции над элементами этой схемы. Основная трудность в этом случае заключается именно в формировании избыточной схемы, поскольку этот этап относится к разряду эвристических и выполняется проектировщиком, что в случае большой размерности задачи представляется достаточно сложным процессом. В условиях автоматизированного проектирования более предпочтительным видится формирование структуры схемы с минимальным влиянием человеческого фактора. Таким образом, задача определения (и последующей оптимизации) топологии сети может быть представлена как задача Прима (при отсутствии дополнительных точек) или задача Штейнера, когда в исходное множество точек узлов проектируемой сети вводятся дополнительные точки. Эти дополнительные точки носят название точек Штейнера, которые при наложении графа инженерной системы на картографическую основу местности будут соответствовать точкам ветвления сети или местам отклонения участков от прямолинейности. Поставленная задача относится к классу МР полных, для которых не существует эффективных алгоритмов решения с полиномиальной временной сложностью. В связи с этим разрабатываются алгоритмы, в основе которых лежат эвристические приёмы, позволяющие за приемлемое время находить оптимальное решение поставленной задачи (глобальный оптимум) или близкие к нему (квазиоптимальные) решения. Одним из таких методов является применение эволюционного моделирования, позволяющее переносить определённые закономерности в развитии естественных систем живой природы на объекты — искусственные системы. Конкретным приложением эволюционного моделирования для рассматриваемой задачи являются генетические алгоритмы.

Для каждой конкретной задачи разрабатывается собственный алгоритм генетического поиска, происходит настройка его параметров. Первым шагом является формирование начального множества вариантов проектных решений, или, в терминах генетических алгоритмов, начальной популяции, состоящей из особей. Именно они послужат основой для дальнейших преобразований с целью получения оптимального решения (речь идёт не только о глобальном оптимуме, но и о близких к нему решениях). Исследователи предлагают ряд способов составления начальной популяции. Например, можно группировать узлы сети по три и в каждой группе по специальным формулам находить координаты соответствующей точки Штейнера, затем повторять процедуру относительно всех узлов, в результате чего строится полное дерево Штейнера [2]. Другой вариант предполагает распределять точки Штейнера по всей площади, планируемой для прокладки инженерной сети. Закон этого распределения сам по себе является объектом отдельного исследования. Наиболее рациональным представляется объединять узлы в области [3] (не менее трёх точек в области), вводить в пределах области дополнительные точки, после чего провести соединение узлов в сеть, используя любой эвристический алгоритм, в т.ч. случайным образом. Необходимым условием при формировании сети является включение в неё всех заданных узлов. Каждое построенное дерево Штейнера будет являться особью в популяции.

В ряде случаев могут вводиться дополнительные ограничения в процесс формирования особи, касающиеся конкретной задачи. Одним из таких ограничений является введение радиусов близости. Для каждого узла сети определяется некоторая область. Новый узел может быть присоединён к данному узлу, только если находится в этой области. Помимо строгого запрета здесь возможен вероятностный подход, позволяющий добиться рассмотрения более широкого спектра вариантов решения. При проектировании инженерных сетей с учётом особенностей и условий конкретной местности должен решаться вопрос о возможности прокладки коммуникаций по данному участку. Предлагается использовать коэффициенты запрещённости. Чем выше этот коэффициент для данной территории, тем меньше вероятность того, что участок сети пройдёт по ней. При этом возможно назначение отрицательных коэффициентов для некоторых областей, т.е. при проектировании сети её участки и дополнительные точки будут тяготеть к этой области (например, в случае, когда требуется привязать новую сеть к уже существующим коммуникациям). Важным этапом в случае применения генетических алгоритмов для решения задач является кодирование информации, т.е. представление варианта решения в виде хромосомы, состоящей из генов (свойств варианта, существенных в конкретной задаче). От того, каким образом будет производиться кодирование декодирование информации, зависят, во многом, такие параметры алгоритма, как его быстродействие и точность решения. При разработке генетических алгоритмов требуется особое внимание к вопросу выбора операторов генетического поиска, а также их модификации при необходимости. Зачастую выбор операторов продиктован определённым ранее методом кодирования информации. Многие параметры алгоритмов не фиксируются, а определяются решением определённого множества тестовых задач, т.е. происходит настройка алгоритма под конкретную задачу. Таким образом, эволюционное моделирование может быть использовано в задаче оптимизации структуры проектируемой инженерной системы, после чего необходимо произвести расчёт соответствующей сети. Решение на данном этапе во многом зависит от того, какие характеристики сети считаются заданными. Например, при известных топологии сети и параметрах узлов потребителей (расчётная нагрузка) необходимо найти наиболее рациональные диаметры трубопроводов, расположение и параметры источников напора в сети, соблюдая при этом требование обеспечения потребителей транспортируемой средой с заранее определёнными свойствами (давление, расход). Здесь также возможно применение методов эволюционного моделирования, позволяющих проводить вычисления с учётом имеющихся материалов и оборудования. Зачастую при решении оптимизационных задач получают решения (например, диаметры участков трубопроводной системы), отвечакищие минимуму (максимуму) целевой функции, но не соответствующие реальным значениям диаметров из сортамента. Возникает необходимость округления теоретически полученных диаметров до реально возможных значений, что с большой степенью вероятности повлечёт за собой отклонение целевой функции от оптимального значения. При использовании генетических алгоритмов на этапе формирования начальной популяции для каждого участка назначается диаметр из имеющегося сортамента, что будет гарантировать рассмотрение в процессе решения только практически осуществимых вариантов. Поэтому результатом станет наиболее близкий к оптимальному вариант (с учётом имеющегося сортамента).

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

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

Литература

1. Авдотьнн Л.Н., Лежава И.Г., Смоляр И.М. Градостронтельное проектирование. М.: Строй издат, 1989
2. Емельянов В.В., Курейчик В.В., Курейчик В.М. Теория и практика эволюционного моделирования. М.: Физматлит, 2003
3. Калашников Р.С. Разработка и исследование комбинированных алгоритмов построения деревьев Штейнера на основе эволюционного подхода: Дис. ... канд. техн. наук: 05.13.12,05.13.17: Таганрог, 2005
4. Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение н анализ, 2 е издание. : Пер. с англ. М.: Вильямс, 2005
5. Кузнецов Р.Н. Определение оптимального маршрута прокладки газопровода: Дис. ... канд. техн. наук: 05.23.03: Воронеж, 2009
6. Меренков А.П., Хасилев В.Я. Теория гидравлических цепей. М.: Наука, 1985