Диссертация (1025823), страница 11
Текст из файла (страница 11)
Таким образом, обоснованоиспользование приближенных методов решения этой задачи.73ГЛАВА 4. Разработка и исследование эффективности алгоритмоврешения задачи ПРЭВсе подключаемые к электросети потребители по уровню запрашиваемогонапряжения разделены на две группы – потребители, подключение которыхпроизводиться к РП на уровне напряжения 10 кВ, и потребители, подключениекоторых производится к ТП на уровне напряжения 0,4 кВ (п. 1.1).
Вопросыопределения мест строительства ТП и РП при решении подзадачи 1 независимыдруг от друга и могут быть рассмотрены последовательно – сначала для объектоводного типа, затем другого. Данное утверждение также справедливо прирассмотрении вопроса подключения потребителей к электросети (решениеподзадачи 2) – подключение потребителей к ТП может быть рассмотренонезависимо от подключения потребителей РП и наоборот.Предложенные в данной главе алгоритмы решения подзадач 1, 2рассматриваются в части строительства ТП и подключения к ним потребителейна уровне 0,4 кВ.
В ИПК ELNET (глава 5) данные алгоритмы применены длярешения аналогичных задач строительства РП и подключения к нимпотребителей на уровне 10 кВ.Оценка эффективности алгоритмовОценка эффективности рассматриваемых в данной главе алгоритмовпроизводится в ИПК ELNET (глава 5), на ЭВМ, основные характеристикикоторой приведены в Таблице 4.1.Параметрырасчетов,приведены в Главе 6.используемыепритестированииалгоритмов,74Таблица 4.1.Характеристики ЭВМ, используемой при исследовании эффективностиалгоритмовХарактеристикаЗначениеПроцессор:Intel Core i5Число ядер2Частота процессора, ГГц1,6Емкость жесткого диска, ГБ34,36Оперативная память (ОЗУ), МБГрафический процессор512Intel HD Graphics 3000Оценка производительности:Операций вычисления в секунду4,5Операций доступа к памяти в секунду3,9Скорость обмена данными с диском7,14.1.
Подзадача 1. Определение числа и мест строительства новых РП и ТППодзадача 1 подразумевает определение числа и мест строительства новыхТП. Исходными данными задачи являются набор потребителейCLʹ ,подключение которых к существующим ТП не представляется возможным ввидуотсутствия у подстанций достаточного объема свободной мощности илисвободных мест для подключения:CLʹ = { CLi X i = 0} , i ∈ [ 1...
CL ].ТРезультатом решения задачи является множество Tнов , состоящее из Х новТП с рассчитанными географическими координатамиTТX1 = ( xi , yi ), X нов, i ∈ ⎡⎣ 1... Tнов ⎤⎦ , Тнов = Х нов.{}В диссертации разработаны следующие алгоритмы решения подзадачи 1.1) Алгоритмы кластеризации:75• алгоритм на основе метода k-средних;• алгоритм, реализующий метод разделительной кластеризации.2) Эвристический алгоритм выделения максимальных подмножеств.4.1.1.
Алгоритмы кластеризацииВ общем случае, подзадачу 1 можно рассматривать как задачукластеризации–задачуразбиениязаданнойвыборкиобъектовнанепересекающиеся подмножества, называемые кластерами [12]. В качествекластеризуемых объектов на итерацииnвыступают неподключенные наитерации ( n − 1) потребители (элементы множества CLʹ ). При n = 0 принимаемCLʹ = ∅ , X1 = 0 .
Классификация методов кластеризации приведена на Рис. 4.1.Методы кластеризацииНеиерархическиеИерархическиеметод k-среднихРазделительнаяОбъеденительнаякластеризациякластеризацияметод выделениясвязанных компонентметоды связи (одиночной,полной, средней)метод минимальногопокрывающего деревадисперсионные методыцентройдные методыпоследовательныйпороговый методпараллельныйпороговый методоптимизирующеераспределениеРис. 4.1.
Классификация методов кластеризацииК иерархическим методам относят методы, реализующие последовательноепостроение кластеров из уже найденных кластеров либо путем разделения76имеющихся кластеров (разделительная кластеризация), либо объединениемотдельных объектов и кластеров (объединительная кластеризация) [72].В случае разделительной кластеризации процесс решения задачиначинается с объединения всех объектов в один кластер, который впоследствиирасщепляется до тех пор, пока каждый объект не окажется в отдельном кластере.В этих методах широко применяется теория графов. Наиболее популярные изэтих методов – метод выделения связанных компонент, метод минимальногопокрывающего дерева [49]. В методе выделения связных компонентов задаетсяпараметр R max и в графе удаляются все ребра, для которых расстояния большеR max .
Соединенными остаются только наиболее близкие пары объектов. Методминимального покрывающего дерева сначала строит на графе минимальноепокрывающее дерево, а затем последовательно удаляет из него ребра снаибольшим весом.Объединительная кластеризация начинается с каждого объекта вотдельном кластере, далее кластеры объединяются до тех пор, пока все объектыне станут членами одного единственного кластера. К методам объединительнойкластеризацииотносятметодысвязи(одиночной,полной,средней),дисперсионные и центройдные методы. В методах связи при формированиикластеров первыми объединяют два объекта, расстояние между которымиминимально.
Далее определяют следующее по величине самое короткоерасстояние, и в кластер с первыми двумя объектами добавляют третий объект.Отличие методов связи заключается в способе определения расстояния междуобъектами. Широко известным дисперсионным методом, используемым дляэтой цели, является метод Варда, в котором кластеры формируют таким образом,чтобы минимизировать квадраты евклидовых расстояний от кластеризуемыхобъектов до центров кластеров. В центройдных методах расстояние междудвумя кластерами представляет собой расстояние между их центройдами.Каждый раз объекты группируют и вычисляют новый центройд.Основная идея неиерархических методов заключается в нахождениизаранее определенного числа кластеров наиболее далеко удаленных друг от77друга.
К этим методам относят метод k-средних, последовательный пороговыйметод, параллельный пороговый метод и оптимизирующее распределение.Последовательный пороговый метод – метод, при котором выбирается центркластера, и все объекты, находящиеся от него на расстоянии не более пороговогозначения, объединяются в кластер. Далее выбирается новый центр кластера, ипроцесс повторяется для не вошедших в кластеры объектов и т. д. В отличие отпоследовательного порогового метода, в параллельном пороговом методе поискрешенияосуществляетсяпараллельноизнесколькихцентров.Методоптимизирующего распределения отличается от пороговых методов тем, чтообъекты можно впоследствии поставить в соответствие другим кластерам(перераспределить), чтобы оптимизировать суммарный критерий, такой каксреднее внутрикластерное расстояние для данного числа кластеров.Два главных недостатка неиерархических методов состоят в том, что числокластеров определяется заранее и выбор кластерных центров происходитнезависимо, при этом результаты кластеризации зависят от выбранных центров.Неиерархическая кластеризация требует меньших вычислительных затрат, чемиерархические методы, и ее выгодно использовать при большом числе объектов[71].В рамках диссертации для решения подзадачи 1 использованы метод kсредних и алгоритм разделительной кластеризации.Алгоритм на основе метода k-среднихИсходными данными для алгоритма (Рис.
4.2) являются множествоподключаемых потребителей СLʹ , для которых на итерации ( n − 1) отсутствуютвозможные варианты подключения к электросети, и минимальное числокластеров N кластер , на которое необходимо разделить элементы множества СLʹ .Также заданным является множество возможных мест строительства новыхобъектов О.78CLʹ, N кластер , ООпределить центры кластеровОпределить принадлежность потребителеймножества Сʹ к одному из кластеровОпределить центры новыхкластеровτ =τ +1τ =τ +1Rmax=RRmaxНет+1NmaxЦентры кластеров=0кластер=NкластерДаизменились+1НетДаЦентры maxкластеровВыполнено Rпопытокизменилиськластеризации?НетДля всех объектов выполненоусловие возможности подключенияк центру кластера?∗XДаРис. 4.2. Схема алгоритма на основе метода k-среднихНа первом шаге алгоритма (τ = 1) из множества О случайным образомвыбираемN кластерточек,которыеобъявляемцентрамикластеров(центройдами).
На следующем шаге решения, каждого потребителя множестваСLʹ относим к кластеру по принципу наименьшего удаления от центра кластера.Иными словами, потребителя СLi относим к j-му кластеру, если для этогопотребителя расстояние до j-ого кластера меньше, чем до любого другого. Далеедля каждого из полученных кластеров выбираем новый центройд и производимперераспределение потребителей по описанному выше принципу. Процессрешения задачи завершается, когда на очередном шаге τ работы алгоритма,координаты центров кластеров не изменятся.79Пример двумерной кластеризации, демонстрирующий алгоритм на основеметода k-средних, приведен на Рис.
4.3. Для удобства считаем, что возможныеместа строительства новых ТП расположены во всех узлах координатной сетки.y10y 10998877665544332211001234567809 100хy10998877665544332211002345678345678910б) Задание начальных центровкластеровy1012ха) Исходные данные01910в) Определение принадлежностиобъектов к одному из кластеровх012345678910г) Пересчет кластерных центровх80y10y1099887766554433221100012345678910д) Перераспределение объектов иперерасчет центров кластеровх012345678910хе) Результаты кластеризацииРис. 4.3. Пример работы алгоритма на основе метода k-средних– кластеризуемый объект;– кластерный центр;– условная граница кластераАлгоритм, реализующий метод разделительной кластеризацииЭто – иерархический метод кластеризации, достоинством которого, посравнению с методом k-средних, является отсутствие необходимости заданиячисла кластеров (Рис. 4.4).Исходными данными для алгоритма являются множество подключаемыхпотребителей СLʹ , для которых на итерации( n − 1) отсутствуют возможныеварианты подключения к электросети.
Также задано множество возможных местстроительства новых подстанций О.На первом шаге работы алгоритма все объекты множества СLʹ объединяемв один кластер и проводим поверку возможности строительства ТП в некоторойточке Oi таким образом, чтобы были удовлетворены условия возможностиподключения для всех потребителей в кластере. Если данное условие выполнено,алгоритм прекращает работу, в точке Oi «строится» ТП. В случае если указанное81условие не выполняется, исходный кластер делим на два кластера последующему принципу (Рис. 4.5).CLʹ, ООбъекты кластераОпределить все объекты в один кластерс нарушенными условиямиОпределить наиболее удаленные объекты,распределить их по разным кластерамВсе объекты кластераНетразделены?ДаНетДля всех объектов выполненоусловие возможности подключения?*XДаРис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
