Кластеризация электроэнергетических систем на зоны надежности при оценке балансовой надежности. Часть 2

Полный текст

ВВЕДЕНИЕ

Электроэнергетические системы (ЭЭС) представляют собой сложные структуры, в составе которых работают сотни тысяч различных элементов [1]. Для анализа балансовой надежности таких систем [2–4], как правило, используют методику на основании метода Монте-Карло [5], которая является наиболее вычислительно эффективной по сравнению с другими [6]. При оценке балансовой надежности из-за высокой размерности анализируемых ЭЭС и, в связи с этим возникающих вычислительных и аналитических трудностей, проводят кластеризацию ЭЭС на зоны надежности (ЗН) и формирование энергетических расчетных моделей (ЭРМ). В практике решения задач анализа систем разработаны различные методы кластеризации [7, 8], но для оценки балансовой надежности формализованных методик кластеризации не существует. При кластеризации для определенных частей ЭЭС исключаются сетевые ограничения, которые слабо влияют на показатели балансовой надежности. Формирование ЭРМ, как правило, проводится до оценки балансовой надежности, и сформированная ЭРМ принимается неизменной для всего периода оценки балансовой надежности, но при необходимости и вычислительной возможности кластеризация ЭЭС на зоны надежности может проводиться многократно в цикле оценки балансовой надежности. Основной причиной многократной кластеризации может быть существенные изменения параметров ЭЭС в течении расчетного периода и, соответственно, влияние этих параметров на возможности сети по передачи мощности. Также это может быть обусловлено тем, что современные ЭЭС имеют сложную структуру с большим разнообразием энергетического оборудования, к тому же ЭЭС имеют тенденцию к укрупнению и объединению, что еще больше усложняет структуру и неопределенность в возможных перетоках мощности.

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

ПОСТАНОВКА ЗАДАЧИ КЛАСТЕРИЗАЦИИ ЭЭС И ФОРМИРОВАНИЕ ЭРМ НА ОСНОВАНИИ МЕТОДОВ ОБНАРУЖЕНИЯ СООБЩЕСТВ В ГРАФАХ

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

При формировании алгоритма кластеризации ЭЭС на зоны надежности необходимо получить функцию a:X→Z, которая каждый узел ЭЭС (x ∈ X) включает в зону надежности z → Z. В рассматриваемом случае множество Z, т.е. количество зон надежности, неопределенно. Оптимальное число зон надежности необходимо определить в процессе вычислений. Стоит отметить, что, как и в любом примере кластеризации, для решаемой задачи справедлива теорема невозможности Клейнберга, в которой указывается, что не существует оптимального алгоритма кластеризации. Каждый применяемый алгоритм будет вносить свою специфику в конечное решение. Это будет зависеть от выбранного критерия и метрики кластеризации.

Решением задачи кластеризации ЭЭС будет являться ее деление, удовлетворяющее заданному критерию оптимальности. В рассматриваемом случае критерием оптимальности выступает минимизация числа зон надежности:

$Z\underset{\rho }{\to }\min .$ (1)

Стремление к минимуму числа зон надежности является естественным, так как это в дальнейшем анализе балансовой надежности приведет к снижению размерности ЭРМ.

Ограничением при решении поставленной задачи будет выступать ограничение, заданное на метрику, которая формируется из различных признаков. В рассматриваемом случае метрика кластеризации должна включать как технические, так и экономические признаки. К техническим признакам можно отнести: установленную мощность генерирующего оборудования в узлах ЭЭС; среднее значение числа часов использования установленной мощности в узлах ЭЭС; сезонные максимумы и минимумы потребления мощности в узлах ЭЭС; аварийность энергетического оборудования; нормативы на проведение плановых ремонтов энергетического оборудования; длины линий электропередачи (ЛЭП) между узлами ЭЭС; пропускные способности ЛЭП [9]. К экономическим: стоимость ввода генерирующих и сетевых объектов. От выбора метрики в итоге будет зависеть результат кластеризации. Метрика должна максимально отражать специфику работы ЭЭС и влияние учитываемых признаков на кластеризацию. В качестве меры расстояния (степени похожести) может быть использована одна из следующих метрик – евклидово расстояние или его квадрат, манхэттенское расстояние, расстояние Чебышева, степенное расстояние и др.

ОБЗОР АЛГОРИТМОВ КЛАСТЕРИЗАЦИИ СИСТЕМ

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

Классификация методов кластеризации может быть проведена на основании способа определения места разделения графа. Можно выделить следующие классы этих методов:

1. Методы на основе сходства. Эти методы определяют кластеры на основе степени сходства между вершинами графа. В таких методах могут использоваться различные метрики сходства, например, косинусное сходство или евклидово расстояние.
2. Методы на основе расстояния. Эти методы определяют кластеры на основе расстояния между вершинами графа. В таких методах могут использоваться различные метрики расстояния, например, евклидово расстояние или расстояние Манхэттена.
3. Методы на основе модели. Эти методы определяют кластеры на основе вероятностной модели графа. Такие методы могут использоваться для кластеризации графов с большим количеством вершин и/или ребер.
4. Методы на основе графовой структуры. Эти методы определяют кластеры на основе структуры графа, такой как плотность графа, центральность вершин и т.д.

Каждый класс представленных выше методов имеет свои преимущества и недостатки, и выбор конкретного метода зависит от решаемой задачи и свойств графа, который необходимо кластеризовать.

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

1. Класс методов разбиения.

1.1. Метод k-средних (k-Means) [11] – это один из наиболее популярных методов кластеризации, принадлежащий к классу методов разбиения. Он основан на разделении вершин графа на заданное число кластеров, так чтобы минимизировать сумму квадратов расстояний между вершинами и центроидами кластеров. Метод k-средних можно применять, когда свойства вершин являются числовыми или когда можно преобразовать их в числовые.

1.2. Метод кратчайшего пути (Shortest Path Clustering) [12] – в этом методе кластеры строятся на основе расстояний между вершинами графа. Данный метод также относится к классу методов разбиения.

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

2.1. Метод Лувена (Louvain Method) [14] – в этом методе вершины графа постепенно объединяются в кластеры, чтобы максимизировать внутрикластерную связность и минимизировать межкластерную связность.

2.2. Метод Spectral Clustering [15] – этот метод основан на анализе собственных значений матрицы смежности графа и позволяет разбивать граф на кластеры на основе его структурной информации.

2.3. Метод Edge Betweenness Clustering [16] – этот метод использует меру межкластерной связности (между центральными вершинами) для разделения графа на кластеры.

3. Методы кластеризации на основе плотности – это методы, которые основаны на анализе плотности распределения вершин графа в пространстве свойств. Они могут быть особенно полезны, если вершины графа не являются числовыми и не могут быть преобразованы в числа. Например, DBSCAN [17] – это метод кластеризации на основе плотности, который позволяет выделять кластеры на основе плотности вершин вокруг определенных центральных точек.
4. Также можно использовать сетевые методы анализа [18] для кластеризации на графах. Сетевые методы – это подход к анализу данных, основанный на представлении данных в виде сетей или графов, что имеет идентичную структуру. Общая идея методов заключается в том, что пространство объектов разбивается на конечное число ячеек, образующих сетевую структуру, в рамках которой выполняются все операции кластеризации. Главное достоинство методов этой группы в малом времени выполнения, которое обычно не зависит от количества объектов данных, а зависит только от количества ячеек в каждом измерении пространства.

4.1. Алгоритм CLIQUE [19], адаптированный под кластеризацию данных высокой размерности, является одним из классических сетевых алгоритмов. Метод основан на том предположении, что если в многомерном пространстве данных распределение объектов не равномерно – встречаются области плотности и разрежения, то проекция области плотности в подпространство с меньшей размерностью будет частью области плотности в этом подпространстве.

4.2. Метод Infomap [20]. Этот метод использует информационную теорию для определения наиболее вероятных сообществ в графе.

Отдельно остановимся на алгоритме на основе модулярности [21], в котором максимизируется разница между фактическим количеством ребер во множестве и ожидаемым количеством таких ребер; различные модификации и улучшения модулярности на основе эвристических методов: метод отжига [22], спектральные алгоритмы [15] и др. [23]. Одним из самых используемых алгоритмов обнаружения сообществ в графах является алгоритм Лувена [14]. Анализ проведенного анализа методов кластеризации выявлено, что для решаемой задачи, кластеризации ЭЭС на зоны надежности, наиболее подходящим является алгоритм Лейдена (Leiden) [24].

КЛАСТЕРИЗАЦИЯ ЭЭС НА ЗОНЫ НАДЕЖНОСТИ С ИСПОЛЬЗОВАНИЕМ АЛГОРИТМА ЛЕЙДЕНА

Алгоритм Лейдена – это алгоритм обнаружения сообществ в больших сетях. Метод Лейдена является итеративным алгоритмом, который работает следующим образом (на рис. 1 показана визуализация работы алгоритма Лейдена):

Изначально каждый узел считается отдельным кластером.

 

Рис. 1. Визуализация работы алгоритма Лейдена.

 

Алгоритм последовательно объединяет близлежащие кластеры, итеративно оптимизируя функционал качества кластеризации.

Функционал качества кластеризации в методе Лейдена основан на распределении объектов между кластерами и показывает насколько хорошо объекты внутри кластера похожи друг на друга, а объекты из разных кластеров различны.

Для объединения кластеров в методе Лейдена используется так называемая “перемещающая модулярность” (modularity gain), которая показывает насколько улучшится качество кластеризации при объединении двух кластеров.

Объединение кластеров происходит до тех пор, пока дальнейшее объединение не приведет к ухудшению функционала качества кластеризации.

После того, как все кластеры объединены, результатом работы алгоритма является итоговое разбиение объектов на кластеры.

Метод Лейдена относится к категории жадных алгоритмов, так как он на каждом шаге выбирает локально оптимальное решение. Он также относительно быстрый и показывает хорошие результаты для кластеризации больших графов и сетей.

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

1. Локальное перемещение узлов в кластеры, основанное на значении модулярности (метрики), которая определяется, как:

$Q=\frac{1}{2m}\underset{ij}{}\left(A_{ij}-\frac{k_i{k}_j}{2m}\right)\delta \left(c_i,c_j\right),$ (2)

где $A_{ij}$ – вес ребра, образованный в соответствии с используемыми признаками; $k_i$ и $k_j$ – сумма весов ребер, присоединенных к узлам j и i; m – сумма всех весов ребер в графе; $c_j$ и $c_i$ – кластеры; $\delta$ – дельта-функция Кронекера.

$\delta \left(c_i,c_j\right)=\left\{\begin{array}{c}\mathrm{1,}{c}_i=c_j \\ \mathrm{0,}{c}_i\ne c_j \end{array}\right..$ (3)

Для определения модулярности кластера применяется следующее выражение:

$Q_c= \frac{\sum in}{2m}-{\left(\frac{\sum tot}{2m}\right)}^2,$ (4)

где $\sum in$ – это сумма весов ребер между узлами внутри кластера (каждое ребро учитывается дважды); $\sum tot$ – сумма всех весов ребер для узлов внутри кластера.

В итерационном процессе происходит перемещение узлов из одного кластера в другой. Для каждого варианта перемещения рассчитывается разница модулярностей $\Delta Q$:

$\Delta Q={\left(\frac{\sum in+2k_{i,in}}{2m}-\frac{\sum tot+k_i}{2m}\right)}^2-{\left(\frac{\sum in}{2m}-{\left(\frac{\sum tot}{2m}\right)}^2-\frac{k_i}{2m}\right)}^2.$ (5)

На основании наилучшего результата соответствующий узел закрепляется за соответствующим кластером.

2. Уточнение кластеров, а именно идентификация кластеров, предложенных на первом этапе. Кластеры, предложенные на первом этапе, могут разделяться на несколько кластеров. Фаза уточнения не следует жадному подходу и может объединить узел со случайно выбранным кластером, что увеличивает функцию качества (модулярности). Эта случайность позволяет более широко раскрыть пространство кластера.
3. Агрегация и повторение этапов 1 и 2 до тех пор, пока качество перемещения и объединения узлов нельзя будет повысить.

ЭКСПЕРИМЕНТАЛЬНЫЕ ИССЛЕДОВАНИЯ

Для оценки работы алгоритма Лэйдена были выполнены экспериментальные исследования на тестовой схеме Объединенной энергосистемы (ОЭС) Сибири, которая включает в себя Алтайскую, Бурятскую, Иркутскую, Красноярскую, Кузбасскую, Новосибирскую, Омскую, Томскую, Хакасскую и Забайкальскую энергосистемы. Для последующей кластеризации ОЭС Сибири была представлена в виде неориентированного графа, в котором каждая из вершин характеризуется максимальной и минимальной генерацией и нагрузкой, линии характеризуются длиной и напряжением. Исходные данные для кластеризации ОЭС Сибири были приняты в соответствии [25]. Стоит отметить, что исходная схема ОЭС Сибири при кластеризации состояла из 540 генерирующих и нагрузочных узлов и 1025 линий электропередачи.

На рис. 2 показан результат работы метода (алгоритма) кластеризации Лэйдена в виде графического представления разделения узлов ОЭС Сибири по зонам надежности.

 

Рис. 2. Графическое представление отнесения узлов ОЭС Сибири к зонам надежности на основании применения алгоритма Лейдена.

 

Та же кластеризация, но уже в границах географических регионов представлена на рис. 3.

 

Рис. 3. Результат кластеризации ОЭС Сибири на ЗН на основании применения алгоритма Лейдена (географическая привязка).

 

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

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

ЗАКЛЮЧЕНИЕ

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

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

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

Исследование выполнено за счет гранта Российского научного фонда № 23-71-01090.

Об авторах

Д. С. Крупенёв

Федеральное государственное бюджетное учреждение науки Институт систем энергетики им. Л.А. Мелентьева Сибирского отделения Российской академии наук

Автор, ответственный за переписку.
Email: krupenev@isem.irk.ru
Россия, Иркутск

Н. А. Беляев

Акционерное общество “НТЦ ЕЭС”

Email: belyaev.na@yandex.ru

Department for Electricity and Power

Россия, Москва

Д. А. Бояркин

Федеральное государственное бюджетное учреждение науки Институт систем энергетики им. Л.А. Мелентьева Сибирского отделения Российской академии наук

Email: krupenev@isem.irk.ru
Россия, Иркутск

Д. В. Якубовский

Федеральное государственное бюджетное учреждение науки Институт систем энергетики им. Л.А. Мелентьева Сибирского отделения Российской академии наук

Email: krupenev@isem.irk.ru
Россия, Иркутск

Список литературы

Дополнительные файлы