Содержание к диссертации
Введение
ГЛАВА 1. Задача перспективного развития электросети (ПРЭ) мегаполиса 20
1.1. Основные особенности электросети мегаполиса 20
1.2. Развитие электросети мегаполиса 29
1.3. Опыт проектирования электросетей в России и за рубежом 35
1.4. Выводы по главе 1 41
ГЛАВА 2. Формализация и постановка задачи ПРЭ 42
2.1. Модель электросети 42
2.2. Постановка задачи ПРЭ как задачи структурно-параметрического синтеза 49
2.3. Сведение многокритериальной задачи ПРЭ к однокритериальной задаче 52
2.4. Выводы по главе 2 55
ГЛАВА 3. Разработка методов решения задачи ПРЭ 56
3.1. Метод, основанный на редукции задачи ПРЭ к совокупности вложенных задач глобальной минимизации (метод редукции) 58
3.2. Метод, основанный на декомпозиции задачи ПРЭ (метод декомпозиции) 61
3.3. Подходы к решению подзадач 1-3, выделенных методами редукции и декомпозиции 69
3.4. Выводы по главе 3 72
ГЛАВА 4. Разработка и исследование эффективности алгоритмов решения задачи ПРЭ 73
4.1. Подзадача 1. Определение числа и мест строительства новых РП и ТП 74
4.1.1. Алгоритмы кластеризации 75 Стр.
4.1.2. Эвристический алгоритм выделения максимальных подмножеств 84
4.1.3. Сравнительный анализ эффективности алгоритмов 86
4.2. Подзадача 2. Определение варианта подключения новых потребителей к электросети 92
4.2.1. Эвристический алгоритм ограниченного перебора 93
4.2.2. Генетический алгоритм 94
4.2.3. Алгоритм, основанный на построении диаграмм Вороного 97
4.2.4. Сравнительный анализ эффективности алгоритмов
4.3. Подзадача 3. Определение итоговой структуры электросети. Генетический алгоритм 104
4.4. Алгоритмы решения задачи координации 106
4.5. Выводы по главе 4 109
ГЛАВА 5. Интерактивный программный комплекс ELNET 110
5.1. Функциональность ИПК ELNET 110
5.2. Архитектура ИПК ELNET 114
5.3. Типовые сценарии работы в ИПК ELNET 116
5.4. Роль ЛПР при работе в ИПК ELNET 122
5.5. Выводы по главе 5 123
ГЛАВА 6. Расчет перспективного развития электросети района мегаполиса 124
6.1. Постановка задачи 124
6.1.1. Исходные данные 124
6.1.2. Ограничения 126
6.1.3. Критерии оптимальности
6.2. Дополнительная информация 135
6.3. Вычислительный эксперимент 137
6.4. Результат решения задачи 142 Стр.
6.5. Выводы по главе 6 143
Общие выводы и заключение 144
Список используемой литературы
- Опыт проектирования электросетей в России и за рубежом
- Сведение многокритериальной задачи ПРЭ к однокритериальной задаче
- Метод, основанный на декомпозиции задачи ПРЭ (метод декомпозиции)
- Сравнительный анализ эффективности алгоритмов
Опыт проектирования электросетей в России и за рубежом
Строительство электросетей радиального типа без резервирования характеризуется наименьшими капиталовложениями. Однако в случае повреждения любой из КЛ или трансформатора, электроснабжение потребителей будет прервано до момента устранения неисправности, что может занять значительное время. Электросети радиального типа с резервированием могут функционировать в случае единичных повреждений КЛ или трансформаторов, однако, уровень их надежности считается низким.
Электроснабжение потребителей, подключенных к электросетям замкнутого петлевого типа, является более надежным по сравнению с первой схемой, тем не менее, эти сети могут быть применены для электроснабжения потребителей, относящихся только к П-ой и Ш-ой категориям.
Одними из наиболее надежных типов сетей являются электросети с двухсторонним питанием - электроснабжение потребителей, подключенных к таким электросетям не прерывается при повреждении одной линии или трансформатора.
Сложнозамкнутые электросети характеризуются значительными капиталовложениями и повышенными требованиями к технической эксплуатации. Данный тип электросетей имеет высокое качество напряжения и минимальные потери электроэнергии в сетях. Сложнозамкнутые электросети зачастую возникают при включении новых подстанций в существующую электросеть любого типа.
В электросетях мегаполисов преимущественно используют сети с двухсторонним питанием и сложнозамкнутые сети. Число ТП, включенных в цепочку, составляет 3-16 подстанций. В нормальном режиме функционирования сети петля (или цепочка) разомкнута.
В мегаполисах применяется двухлучевая схема электросети, при которой питание одной ТП производится по двум КЛ. Каждая из них питает свой трансформатор, на котором со стороны низкого напряжения установлены контакторы, автоматически переключающие нагрузку с одного трансформатора на другой при исчезновении напряжения на каком-либо из них.
Электросеть уровня напряжения 0,4 кВ (а также электросеть 10 кВ в случае подключения потребителя непосредственно к РП) строится по принципу прямого подключения потребителя к ТП или РП (Рис. 1.4). Схема питания потребителей в этом случае также двухлучевая - подключенние к ТП потребителей выполнено двумя параллельно проложенными КЛ.
Л Л Рис. 1.4. Схема подключения потребителей к ТП и РП -РП: О ТП;0 - потребитель электроэнергии Двулучевая схема построения электросети на обоих уровнях напряжения (10 и 0,4 кВ) обеспечивает требуемую надежность электроснабжения потребителей.
Для электросетей России частота колебания напряжения равна 50 Гц. Количество фаз в электросети равно трем (то есть электросеть является трехфазной). Расстояние между объектами электросети Прокладка КЛ в городах и поселках должна производиться в коллекторах и кабельных туннелях [77]. Задача определения мест размещения КЛ в общем виде может быть сведена к известной в теории графов задаче поиска кратчайшего пути в лабиринте. В этом случае лабиринт представляется в виде взвешенного неориентированного графа, вершинами которого являются ТП и РП электросети, подключаемые потребители и места развилок. Ребрам графа соответствуют уже существующие траншеи и кабельные туннели, соединяющие объекты между собой. Перед началом решения задачи для каждого потребителя определяется точка вхождения в лабиринт и граф дополняется соответствую щими новыми ребрами. Вес каждого ребра есть расстояние на местности между двумя соответствующими вершинами. Решением задачи будет являться набор ребер, определяющий минимальный маршрут (маршрут с минимальным суммарным весом ребер) в графе соединяющий две заданными вершинами.
В теории графов существуют различные алгоритмы и методы нахождения минимального пути между вершинами – волновой алгоритм, алгоритм Дейкстры, алгоритм Беллмана-Форда и т. д. [27].
Зачастую при решении реальных задач указанный подход к определению расстояний между объектами не применяется. Это связано с высокими вычислительными затратами на его реализацию, трудоемкостью задания исходного лабиринта и т. д. На практике за длину КЛ с достаточно высокой точностью может быть принято расстояние между объектами. Можно выделить несколько вариантов определения расстояния между объектами (Рис. 1.5). 1) Расстояние Эвклида. Расстояние rij между объектами i и j с координатами (xi,yi ) и (xj,yj ) соответственно, определяется выражением rij \\xi xj) + \УІ У]) . (1.1) 2) Манхэттенское расстояние. В данном случае расчет расстояния между объектами производится по маршрутам, параллельным осям координат. Расстояние Гц определяется выражением Развитие электросети мегаполиса происходит за счет увеличения числа потребителей на вновь застраиваемых территориях и уплотнения застройки в уже существующих районах, а также за счет роста электрических нагрузок уже подключенных электросетям потребителей. Рост числа потребителей происходит за счет естественного развития города и введения в эксплуатацию объектов нового строительства. Рост потребляемой мощности подключенных электроприемников происходит за счет увеличения числа мощности электроприборов, используемых населением, в быту и производстве.
Сведение многокритериальной задачи ПРЭ к однокритериальной задаче
Критерии оптимальности Z1 (X), Z2(X), ..., Z QO в общем случае противоречат друг другу, то есть улучшение значения одного из критериев приводит к ухудшению других. Поэтому решение задачи (2.7) может быть только компромиссным [98]. В настоящее время существует большое число методов решения многокритериальных задач, а также различные подходы к их классификации. На верхнем уровне иерархии методы решения многокритериальных задач классифицируют следующим образом [66].
1) Методы поиска решения без участия лица принимающего решения (ЛПР), построенные на некоторых эвристических принципах [72].
2) Методы поиска решения с участием ЛПР. Существуют различные способы вовлечения ЛПР в процесс решения задачи. В зависимости от варианта вовлечения ЛПР различают априорные, апостериорные и интерактивные методы [36].
Кроме того, известные методы решения многокритериальных задач можно разделить на две группы. 1) Методы, которые не производят свертывание частных критериев в скалярный. К данным методам можно отнести метод справедливого компромисса, метод отклонения от идеальной точки, метод последовательных уступок, метод анализа иерархий и т. д. [25]. Данные методы позволяют получать допустимые решения, но требуют высокой квалификации персонала.
2) Методы, сводящие многокритериальную задачу к однокритериальной путем свертывания векторного критерия скалярный. Наиболее часто используемыми свертками критериев являются следующие.
Метод главного критерия. Метод заключается в выделении одного из критериев в качестве основного и переводе остальных критериев в ограничения. Основной недостаток такого метода заключается в том, что поиск оптимального решения фактически ведется по одному из критериев, значения остальных критериев напрямую не влияют на результаты поиска.
Аддитивная линейная свертка. Метод представляет собой один из самых простых способов скаляризации, в котором итоговый критерий представляет собой взвешенную сумму всех частных критериев: Z Z(Х) = У XiZi (X), Х Є D. /=i Здесь z(X) - скалярный критерий; Аг 0 - коэффициенты свертки, которые трактуют ак «веса» ли «коэффициенты важности» соответствующих критериев, так что более важному из них ЛПР назначает больший «вес», а менее важному - меньший. Основной недостаток данного способа скаляризации заключается в следующем: в случае задачи с невыпуклой границей множества Парето, аддитивная свертка не позволяет получить все эффективные по Парето решения [54].
Мультипликативная свертка. Метод применяется в случае, если влияние каждого критерия значимо и не может быть проигнорировано. Данная свертка имеет вид Z(Х) Z \ Zt (X)A, Х Є D, (2.8) /=i где Яг 0 - коэффициенты свертки. В случае применения свертки (2.8), если значение хотя бы одного из критериев равно нулю, то свертка принимает нулевое значение. Свертка Гермейера. Свертку Гермейера определяет формула Z(Х) = min —— , / Є [ 1...Z ], Х Є D, где Я- 0 - параметры свертки. Свертка Гермейера позволяет получить как эффективные по Парето, так и эффективные по Слейтеру (слабо эффективные) решения [66]. На практике, когда лицо принимающее решение (ЛПР) интересуют только эффективные решения, получение слабо эффективных решений является недостатком.
Результатом применения любой из рассмотренных сверток является сведение исходной многокритериальной задачи (2.7) к однокритериальной детерминированной задаче вида Z(X ) = тІП (X). (29) XЄD Задачу (2.9) исследуем как задачу дискретного программирования, поскольку условие целочисленности переменных на конечном интервале значений может быть заменено условием дискретности [27].
Важной особенностью задачи (2.9), является то, что целевая функция в ней задается алгоритмически, то есть не может быть представлена в аналитическом виде. Таким образом, для каждого полученного в ходе решения задачи варианта потребуется вычисление целевой функции, с использованием довольно сложного алгоритма.
Задача (2.9) имеет большую размерность. Так, при расчете электросети района мегаполиса размерность вектора Х может достигать 3000-5000. В случае если каждый элемент этого вектора может принимать одно из двух возможных 3000 5000 значений, число вариантов решения задачи составит 2 -2 . Таким образом, решение задачи (2.9) полным перебором не представляется возможным и требует разработки эффективных приближенных методов ее решения [27, 42]. Заметим, что в настоящее время в практике решения задач ПРЭ используют метод главного критерия, когда в качестве критерия оптимальности выступают приведенные затраты на строительство и эксплуатацию электросети, а прочие критерии оптимальности переводятся в ограничения [29, 37].
1) Предложена математическая модель электросети в виде взвешенного направленного мультиграфа, вершинам которого соответствуют объекты типа ТП и РП, дугам – КЛ. Даны векторы атрибутов вершин и дуг графа.
2) На основании разработанной математической модели сформулирована математическая постановка задачи ее перспективного развития электросети. Задача представлена в виде многокритериальной многопараметрической дискретной задачи структурно-параметрического синтеза.
3) Рассмотрены известные подходы к решению многокритериальных задач. Опираясь на с уществующую практику решения опт имизационных задач в области электроэнергетики, в качестве метода решения задачи перспективного развития электросети выбран метод главного критерия. С помощью этого метода выполнено сведение поставленной задачи ПРЭ к однокритериальной многопараметрической дискретной задаче структурно-параметрического синтеза.
Метод, основанный на декомпозиции задачи ПРЭ (метод декомпозиции)
К этим методам относят метод k-средних, последовательный пороговый метод, параллельный пороговый метод и оптимизирующее распределение. Последовательный пороговый метод – метод, при котором выбирается центр кластера, и все объекты, находящиеся от него на расстоянии не более порогового значения, объединяются в кластер. Далее выбирается новый центр кластера, и процесс повторяется для не вошедших в кластеры объектов и т. д. В отличие от последовательного порогового метода, в параллельном пороговом методе поиск решения осуществляется параллельно из нескольких центров. Метод оптимизирующего распределения отличается от пороговых методов тем, что объекты можно впоследствии поставить в соответствие другим кластерам (перераспределить), чтобы оптимизировать суммарный критерий, такой как среднее внутрикластерное расстояние для данного числа кластеров.
Два главных недостатка неиерархических методов состоят в том, что число кластеров определяется заранее и выбор кластерных центров происходит независимо, при этом результаты кластеризации зависят от выбранных центров. Неиерархическая кластеризация требует меньших вычислительных затрат, чем иерархические методы, и ее выгодно использовать при большом числе объектов [71].
В рамках диссертации для решения подзадачи 1 использованы метод k-средних и алгоритм разделительной кластеризации. Алгоритм на основе метода k-средних Исходными данными для алгоритма (Рис. 4.2) являются множество подключаемых потребителей СL , для которых на итерации (n -1) отсутствуют возможные варианты подключения к электросети, и минимальное число кластеров Nкластер, на которое необходимо разделить элементы множества СL . Также заданным является множество возможных мест строительства новых объектов О.
На первом шаге алгоритма (=1) из множества О случайным образом выбираем Nкластер точек, которые объявляем центрами кластеров (центройдами). На следующем шаге решения, каждого потребителя множества СL относим к кластеру по принципу наименьшего удаления от центра кластера. Иными словами, потребителя СLi относим к j-му кластеру, если для этого потребителя расстояние до j-ого кластера меньше, чем до любого другого. Далее для каждого из полученных кластеров выбираем новый центройд и производим перераспределение потребителей по описанному выше принципу . Процесс решения задачи завершается, когда на очередном шаге работы алгоритма, координаты центров кластеров не изменятся. Пример двумерной кластеризации, демонстрирующий алгоритм на основе метода -средних, приведен на Рис. 4.3. Для удобства считаем, что возможные места строительства новых ТП расположены во всех узлах координатной сетки.
Это - иерархический метод кластеризации, достоинством которого, по сравнению с методом -средних, является отсутствие необходимости задания числа кластеров (Рис. 4.4).
Исходными данными для алгоритма являются множество подключаемых потребителей CL , для которых на итерации (п-\) отсутствуют возможные варианты подключения к электросети. Также задано множество возможных мест строительства новых подстанций О.
На первом шаге работы алгоритма все объекты множества CL объединяем в один кластер и проводим поверку возможности строительства ТП в некоторой точке Oj таким образом, чтобы были удовлетворены условия возможности подключения для всех потребителей в кластере. Если данное условие выполнено, алгоритм прекращает работу, в точке Ot «строится» ТП. В случае если указанное условие не выполняется, исходный кластер делим на два кластера по следующему принципу (Рис. 4.5).
Схема алгоритма решения подзадачи 1 методом разделительной кластеризации 1) Определяем пару потребителей, расстояние между которыми больше, чем между любыми другими потребителями. Каждый из таких потребителей образует кластер (является его центройдом) и исключается из дальнейшего рассмотрения. 2) Аналогично определяем следующую пару потребителей и разносим их по образованным на предыдущем шаге кластерам: к первому кластеру относим потребителя, наиболее близко расположенного к одному из центройдов; второго потребителя относим к другому кластеру.
Сравнительный анализ эффективности алгоритмов
ГА являются мощным методом оптимизации, позволяющим найти оптимум быстрее, чем многие другие методы случайного поиска. Существенным достоинством ГА является их универсальность и, как правило, высокая скорость сходимости. К недостаткам алгоритмов можно отнести большое время поиска экстремума, что не позволяет их использовать в быстродействующих системах реального времени [64].
Для применения ГА необходимо преобразовать переменные, фигурирующие в условии задачи, в генетические переменные. Такое преобразование задается схемой кодирования. Переменные могут быть представлены в двоичной форме, в форме действительных десятичных чисел или в другой форме, в зависимости от смысла решаемой задачи.
Основными операторами ГА являются кроссовер (обмен генетическим материалом между хромосомами), мутация (локальное изменение одного или нескольких генов хромосомы), выбор родителей для скрещивания и селекция (отбор хромосом в новую популяцию).
В настоящее время существует десятки вариантов модификаций каждого из указанных операторов, применяемых в ГА. Некоторые комбинации схемы кодирования и вида основных операторов ГА приводят к типовым моделям – канонический, простой, гибридный, многопопуляционный ГА и др. [34].
Например, для канонического ГА характерны бинарное кодирование особей; постоянный размер популяции; управление популяцией методом рулетки; селекция особей для скрещивания случайным равновероятностным методом; использование одноточечных кроссовера и мутаций. Простой ГА отличается от канонического только применение метода турнирного отбора вместо рулеточного. Гибридный ГА как правило основан на комбинации ГА с неким алгоритмом локального поиска (например, градиентного), а в многопопуляционном ГА предполагается наличие нескольких популяций, работа с которыми может производиться параллельно [23].
Для решения подзадачи 2 посредством ГА поставим в соответствие каждому подключаемому потребителю СLпjодкл один ген хромосомы (Рис. 4.11). Значением гена (аллелью) является номер ТП/РП Hi , к которой будет подключен СLпjодкл потребитель. Длина хромосомы равна CL . X X1 =Hi X2 =Hj CLподкл 1 2 ... СLподкл
Схема кодирования хромосомы при решении подзадачи 2 ГА Схема решения подзадачи 2 посредством ГА представлена на Рис. 4.12. Tисх , Tнов , СLподкл Определить возможные варианты подключения для каждого потребителя множества Сподкл
Входными данными для ГА является электросеть Gисх и множество подключаемых к ней потребителей СL.
На первом шаге алгоритма для каждого из потребителей множества СL определяется список вариантов, к которым возможно произвести подключение. Полученные варианты должны удовлетворять всем ограничениям (3.8).
При формировании хромосом начальной популяции производится их проверка на выполнение всех наложенных на электросеть ограничений (3.8). В случае если хромосома соответствует всем ограничениям, она добавляется в начальную популяцию. Процесс производится до тех пор , пока в начальной популяции не будет N хромосом. После завершения формирования популяции, над ее особями производятся основные действия ГА - оценка их фитнесс-функции, селекция, скрещивание, мутация.
Если результат решения не удовлетворяет критерию окончания вычислений P(Х ?, Z?) 1, то алгоритм продолжает формирование новых популяций и выполнение над ними основных генетических операций. В противном случае, алгоритм завершает работу. Результатом решения подзадачи 2 является вектор Х . Алгоритм может включать в себя различные варианты реализации основных операторов ГА. ИПК ELNET (глава 5) позволяет пользователю произвести выбор из следующих возможных вариантов. 1) Селекция: случайный равновероятностный метод. 2) Скрещивание: одноточечный кроссовер; многоточечный кроссовер. 3) Мутация: одноточечная; многоточечная.
Диаграмма Вороного некоторого множества точек представляет собой такое разбиение плоскости, на которой расположены данные точки, при котором каждая область этого разбиения образует множество точек более близких к элементу исходного множества, расположенного в указанной области, нежели к любому другому элементу этого множества (Рис. 4.13) [78].
Диаграмма В ороного является одним из основных инструментом вычислительной геометрии и активно применяется при решении задач распознавания образов, робототехники, геодезии, компьютерной графики, САПР [35]. Существует множество различных алгоритмов построения диаграмм Вороного, таких как простой алгоритм, алгоритм Форчуна, р екурсивный алгоритм и т.д. [68].
Схема алгоритма решения подзадачи 2, основанного на построении диаграмм Вороного, приведена на Рис. 4.14.
Схема алгоритма решения подзадачи 2, основанная на построении диаграмм Вороного Исходными данными для решения задачи являются элементы множеств Тисх, Тнов, а также множество подключаемых к электросети потребителей CL. Тi Т и Т На первом шаге алгоритма для ТП множеств исх новстроится диаграмма Вороного. Далее для каждой ТП Тi производится попытка подключения к ней потребителей множества СLподкл , расположенных в ее области. Все потребители, для которых выполнены условия возможности подключения их к Тi СL Т и Т ТП исключаются из множества подкл . Также из множеств исх нов исключаются ТП, к которым отсутствует возможность подключения новых потребителей (нет свободных мест на сборке или отсутствует свободная мощность). Для оставшихся элементов множеств Тисх, Тнов, СLподкл производится повторное построение д иаграммы Вороного и исключение объектов из множеств. Алгоритм прекращает работу, когда во множестве СLподкл не останется ни одного элемента либо на очередном шаге работы алгоритма не будет ни одного возможного варианта подключения потребителей к ТП.