Методы моделирования и оптимизации коммуникационных сетей

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

Задача проектирования коммуникационных сетей является обобщением геометрической задачи, которая еще в 1837 году была сформулирована немецким механиком Якубом Штейнером: требуется соединить n заданных на плоскости точек сетью минимальной длины с использованием любого количества свободно размещаемых добавочных точек, названных впоследствии точками Штейнера (ТШ). При заданной топологии (порядке соединения точек) сеть имеет минимальную длину при оптимальном положении ТШ. Число возможных вариантов топологии сети зависит от количества фиксированных точек и выражается формулой, которая дает оценку более сильную, чем факториал [11]. Известно, что задача относится к классу NP-трудных и точное решение можно найти только полным перебором топологий.

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

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

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

В истории развития математических моделей транспортного освоения лесных массивов [2], [3], [4], [5], [10], [12], [23] ясно просматриваются тенденции их усложнения при одновременном смягчении, уточнении допущений, что приводит к увеличению их адекватности объектам и повышению точности проектных решений. Применявшиеся в простейших аналитических моделях методы оптимизации углов примыкания, расстояний между путями одного вида, размеров и форм лесосырьевых баз [10], [12], [23] давали типовые решения на основе усредненных характеристик лесосырьевых баз, не учитывающие разнообразия локальных неоднородностей их территорий.

Методы линейного, нелинейного и целочисленного программирования позволили осуществлять комплексную оптимизацию положения элементов сети, связывающей заданное множество точек [3]. Основное допущение в этих моделях состояло в том, что в каждую из точек, априори выбранных на территории лесосырьевой базы, собирают древесину с близлежащего участка, которую затем доставляют на нижний склад. Каждой точке и ее окрестности приписывают количественные характеристики. При этом допускаются точки с нулевым объемом собираемой древесины для учета безлесных территорий в лесосырьевой базе. Это вполне адекватно объекту при концентрации древесины на погрузочных площадках.

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

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

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

Такие модели выбора наивыгоднейшего варианта сети позволяют учитывать неправильность формы лесосырьевой базы, неоднородность распределения запасов, геологические условия строительства дорог и вывозки. Однако эти модели имеют и существенные недостатки: отсутствие учета фактора времени и неопти-мальность положения заданных транзитных точек и развилок дорог. С первым недостатком можно частично справиться, определяя очередность строительства фрагментов сети с помощью методов динамического программирования [5]. Второй недостаток в некоторой степени преодолевается введением свободно размещаемых развилок и оптимизацией их координат итеративными методами [4]. Позднее проблема была полностью решена за счет перехода к обобщению геометрической задачи Штейнера на случай с потоками и зависящими от них весами, называемой потоковой задачей [20].

Эти модели стали основой разработки системы проектирования сети лесовозных дорог СЕТИ-ЕС, реализованной на ЭВМ ЕС 1052. На первом этапе работы системы строилась и оптимизировалась связывающая сеть на множестве фиксированных точек. На втором этапе в автоматическом режиме на каждом узле сети решалась потоковая задача Штейнера: выполнялось расщепление узла с полным перебором топологий и оптимизировались координаты развилок. На третьем этапе в интерактивном режиме искались локальные улучшения. Предпринимались попытки изменить топологию сети вручную. Кроме того, на выделенных фрагментах сети решалась потоковая задача Штейнера с помощью оригинального алгоритма исчерпывающего и неизбыточного перебора полных топологий, ставшего ключевым моментом этой разработки. На завершающем этапе оптимизировались координаты развилок на всей сети. Эта операция на всех этапах выполнялась методами случайного поиска [24].

Система проектирования СЕТИ-ЕС была принята в эксплуатацию комиссией Минлес-древпрома СССР и использовалась ее проектными организациями.

В сравнении с вариантами проектировщиков при подготовленных ими исходных данных в разных регионах страны оптимизация структуры сети и положения ее элементов на заданном множестве точек методами линейного программирования [2] позволила снизить суммарные затраты на строительство сетей и вывозку древесины: в Казахском леспромхозе в среднем на 1,5 %, Немском – на 23,1 %, Ертомском – на 5,8 %, Зеленоборском – на 10,2 %. При определении очередности строительства участков сети с использованием динамического программирования [5] суммарные приведенные затраты уменьшились на 1,8 %. Решение задачи Штейнера с перебором топологий и оптимизацией координат развилок на отдельных фрагментах реальных сетей давало значительное снижение суммарных затрат – от 2 до 27 % [20].

С помощью системы СЕТИ-ЕС исследовалась зависимость улучшения целевой функции от числа категорий лесовозных дорог. С увеличением числа категорий до 12 улучшение было значимо, свыше этого числа оно было в пределах погрешности входной информации. Исследования показали несовершенство существовавшей на тот момент классификации лесовозных дорог.

При переходе с «больших» вычислительных машин на персональные компьютеры (ПК) система СЕТИ-ЕС не была реализована. На основе подсистемы решения потоковой задачи Штейнера была разработана автономная система проектирования лесовозных дорог на ПК [18]. В ней были заново запрограммированы все наработки из прежней подсистемы, включая интерактивный режим проектирования.

В 1990-е годы, когда в России начался переход к рыночным отношениям, возникла необходимость выбора стратегии транспортного освоения лесосырьевой базы в изменившихся условиях. Был разработан прототип системы STEIN [18], [19], [9]. В ней реализованы основные функции проектирования лесовозных дорог с учетом фактора времени и оценки инвестиционных проектов.

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

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

В рамках эволюционного подхода получены следующие оригинальные результаты: эволюционная модель, генетические операторы и реализованный на ПК эволюционный композитный алгоритм с направленным поиском для решения потоковой задачи Штейнера [13], [14], [15], [16], [8]. Ключевыми моментами разработки являются способ представления хромосомы и принцип ее коди-рования/декодирования и генетические операторы, основанные на геометрических эвристиках. Алгоритм тестировался на лесотранспортных сетях. За приемлемое время он находил оптимальное решение или ряд субоптимальных, качество которых оказалось существенно лучше найденных в интерактивном режиме работы системы STEIN.

Современный этап развития вычислительной техники связан с появлением многопроцессорных систем и кластеров, рассчитанных на выполнение параллельных алгоритмов. Решение потоковой задачи Штейнера большой размерности с помощью последовательного алгоритма требует значительных затрат компьютерного времени, тогда как параллельный эволюционный алгоритм может экономить время за счет распределенных вычислений. Анализ композитного эволюционного алгоритма [14] показал, что он имеет достаточный потенциал для распараллеливания в кластерной системе. Целесообразна разработка параллельного алгоритма последовательного типа с пространственной декомпозицией, то есть алгоритма с независимым параллельным поиском в пространстве допустимых решений. Считают, что для алгоритмов последовательного типа хорошо подходят различные топологии кластеров, в том числе простые линейные топологии.

Постановка потоковой задачи Штейнера инвариантна по отношению к ориентации сети, так что эту задачу можно применять для проектирования разомкнутых однородных электрических сетей. С помощью композитного эволюционного алгоритма с направленным поиском решалась задача на фрагментах существующей распределительной сети 10 кВ в Олонецком районе Республики Карелия [7]. Эта сеть поэтапно проектировалась, строилась и частично модернизировалась с начала 1950-х годов, когда расположение подстанций всех уровней требовало привязки к населенным пунктам. Общая протяженность сети составляет 286,59 км. Сеть имеет 3 понизительные подстанции 110/35/10 кВ в Олонце, Коткозе-ре и Видлице и 39 потребителей (подстанции 10/0,4 кВ), большая часть которых – объекты сельского и жилищно-коммунального хозяйства.

Оптимизация фрагментов осуществлялась независимо друг от друга, а их структура была взята по нормальному режиму работы сети. Алгоритм за несколько секунд нашел оптимальные решения для всех фрагментов, поскольку число фиксированных точек в них было невелико. Эффективность оптимизации составила 6–14 % и оказывалась тем больше, чем больше общая протяженность линий электропередачи и число подстанций.

Эволюционный алгоритм, разработанный для решения потоковой задачи, позволяет находить конфигурацию однородной электрической сети минимальной длины с минимальными затратами на строительство и эксплуатацию. Полученное оптимальное решение устойчиво по отношению к изменениям экономической ситуации, так как в роли критерия выступает суммарная длина сети. Такой критерий согласуется и с другими составляющими многокритериального выбора при проектировании сети [21]: максимум надежности и минимум расхода металла. Они трудно поддаются учету при финансово-экономической оценке эффективности по официальным методическим рекомендациям. Кроме того , при минимизации длины сети снижается средний уровень потерь напряжения, мощности и энергии, пропорционально длинам отдельных линий.

Возможно также применение потоковой задачи Штейнера и к оптимизации неоднородных электрических сетей при условии, что издержки, зависящие от рассчитанных нагрузок сети, можно надежно прогнозировать на длительный период ее эксплуатации [10].

Таким образом, основными результатами исследований по моделированию и оптимизации коммуникационных сетей являются:

• 1.    Повышение степени адекватности математических моделей коммуникационных сетей путем учета в них потоков, территорий размещения сетей произвольной формы и характеристик местности.

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

• 3.    Разработка и реализация на ПК эволюционного композитного алгоритма с направленным поиском. Оценка его эффективности на тестовых примерах и фрагментах реальных лесотранспортных и высоковольтных электрических сетей.