Диссертация (Разработка математической модели, численных методов и алгоритмов для структурно-параметрического синтеза электросети мегаполиса с учетом его перспективного развития), страница 12

4.4. Схема алгоритма решения подзадачи 1 методом разделительнойкластеризации1) Определяем пару потребителей, расстояние между которыми больше, чеммежду любыми другими потребителями. Каждый из таких потребителейобразует кластер (является его центройдом) и исключается из дальнейшегорассмотрения.2) Аналогично определяем следующую пару потребителей и разносим их пообразованным на предыдущем шаге кластерам: к первому кластеру относимпотребителя, наиболее близко расположенного к одному из центройдов; второгопотребителя относим к другому кластеру. Данную процедуру выполняемпоследовательно до тех пор, пока из рассмотрения не будут исключены все82потребители.

Если потребителей нечетное число, то последнего оставшегосяпотребителя относим к кластеру, к центройду которого он расположен ближе.Для обоих полученных кластеров производим проверку возможностистроительства в кластере ТП таким образом, чтобы все потребители кластераимели возможность подключения к этой ТП. Если указанное условие невыполняется, то данный кластер делим на два кластера по описанному вышепринципу. Алгоритм продолжает работу пока для всех выделенных кластеров небудет выполнено условие возможности строительства новой ТП и подключенияк ним всех потребителей.y 10y1099887766554433221100012345678901012345678910ха) Исходные данные.

Объединениевсех объектов в один кластерхб) Деление исходного кластера надва единичных кластераy 10y 1099887766554433221100012345678910х012345678910х83в) Добавление в кластеры двухнаиболее удаленных объектовг) Перерасчет центров кластеров.Добавление в кластеры двухнаиболее удаленных объектовy10y 10998877665544332211000123456789100хд) Перерасчет центров кластеров.Добавление в кластеры двух наиболееудаленных объектовy 1012345678910хе) Перерасчет центров кластеров.Добавление в кластеры двухнаиболее удаленных объектов.9876543210012345678910хж) Результат кластеризацииРис.

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

4.6.CLʹ, ОВыбрать точку Оi и определитьNmaxближайщих к ней потребителейИсключить наиболее уделенныйот Oi объектК ТП T j ( x j , y j ) = ( xi , yi ) можно подключитьвсех выбранных потребителей?НетДаОi - место строительства новой ТП,исключить выбранные объекты из С ʹНетτ =τ +1Сʹ = ∅ ?∗ДаXРис. 4.6. Схема эвристического алгоритма выделения максимальныхподмножествИсходными данными для решения задачи на итерации tмножество потребителей CLʹ =является{ СLi ( X i )n−1 = 0 }, неподключенных к ТП напредыдущей итерации ( n − 1) решения подзадачи 2.На первом шаге алгоритма из множества CLʹ выбираем потребителя СL0 и(N max − 1) потребителей, наиболее близко расположенных к нему. Здесь N max –85максимальный размер кластера, равный числу потребителей, которые могутбыть подключены к новой ТП.Если для N max потребителей удается определить такую точку строительствановой ТП ( xi , yi ) ∈ О , что расстояние от них до точки ( xi , yi ) меньше заданной( xi , yi )величины llim , то точкуназначаем местом строительства новойподстанции, а всех отобранных на предыдущем шаге потребителей удаляем измножества СLʹ .

В случае если такой точки обнаружить не удается, то измножества отобранных потребителей исключаем наиболее удаленного отпотребителя и производим повторную попытку определения точкиСLподкл0строительства.Алгоритм заканчивает работу, когда из множества СLʹ будут исключенывсе элементы. Работу алгоритма иллюстрирует Рис. 4.7. Считаем, что N max = 4 ,llim = 3 ед.y 10y10998877665544332211000123456789100123456789ха) Исходные данные10хб) Выбор начального объекта имножества объектов, наиболееблизких к нему86y 10y 1099887766554433221100012345678910012345678910хв) Выбор второго объекта имножества объектов, наиболееблизких к немухг) Выбор третьего объекта имножества объектов, наиболееблизких к нему.

Результат работыалгоритмаРис. 4.7. Иллюстрация результатов работы эвристического алгоритмавыделения максимальных подмножеств– подключаемый потребитель;– выбранный объект4.1.3. Сравнительный анализ эффективности алгоритмовДля анализа эффективности алгоритмов решения подзадачи 1 проведенывычислительные эксперименты на наборе из пяти карт, состоящих из 100подключаемых потребителей каждая.

Для каждой карты проведено 20 запусковрасчетов в ИПК ELNET (глава 5). В качестве оценки эффективности алгоритмовиспользуем два индикатора:T1) число ТП, строительство которых необходимо произвести X нов;2) время вычислений t .В Таблицах 4.2.-4.3. и на Рис. 4.8 приведены результаты расчетов натестовых картах для алгоритма на основе метода k-средних, алгоритма,основанного на разделительной кластеризации и эвристического алгоритмавыделения максимальных подмножеств.87Таблица 4.2.~TСреднее число построенных ТП X нов~TСреднее число построенных ТП X нов(20 экспериментов)ЭвристическийАлгоритм наАлгоритмАлгоритмосновевыделенияразделительнойметодамаксимальныхкластеризацииk-среднихподмножеств13,616,014,012,716,014,512,816,014,513,316,013,912,916,014,2Карта12345Среднеепо 5 картам13,116,014,2Таблица 4.3.Среднее время выполнения программы tКарта12345Среднеепо 5 картамСреднее время работы алгоритмов t(20 экспериментов)ЭвристическийАлгоритм наалгоритмАлгоритмосновевыделенияразделительнойметодамаксимальныхкластеризацииk-среднихподмножеств86,1250,0205,476,5234,0230,481,2234,0231,480,1214,0206,283,9250,0221,081,6236,4218,988Таблица 4.4.~TСреднеквадратичное отклонение σ величин X новиtКартаTσ X нов(Эвристическийалгоритмвыделениямаксимальныхподмножеств0,80,80,80,90,812345σ (t ))Алгоритмна основеметода kсреднихЭвристическийалгоритмвыделениямаксимальныхподмножеств1,21,41,31,31,11,31,71,41,41,38ЧислоэкспериментовЧислоэкспериментов7654321012131415161,61,71,61,81,8109876543210121713ПостроеноТП141516171617ПостроеноТПа) Карта 1б) Карта 212111098765432101211109876543210ЧислоэкспериментовЧислоэкспериментовАлгоритм наоснове методаk-средних12131415ПостроеноТПв) Карта 3161712131415ПостроеноТПг) Карта 4Числоэкспериментов891413121110987654321012131415ПостроеноТП1617д) Карта 5Рис.

4.8. Результат расчета тестовых примеров- эвристический алгоритм выделения максимальных подмножеств;– алгоритм на основе метода k-среднихАнализ результатов, представленных на Рис. 4.8, показывает, что среднеевремя решение задачи tалгоритмом на основе метода k-средних иразделительной кластеризации более чем в два раза превышает время решениязадачи эвристическим алгоритмом выделения максимальных подмножеств. При~Tэтом среднее число построенных ТП X новпри решении задачи эвристическималгоритмом выделения максимальных подмножеств на ~10% меньше, чем прирешении задачи алгоритмом на основе метода k-средних и на ~20% меньше, чемпри решении задачи алгоритмом разделительной кластеризации.TTНаилучший результат по индикатору X новдля каждой из карт ( X нов= 12 )был достигнут при решении задачи эвристическим алгоритмом выделениямаксимальных подмножеств и алгоритмом на основе метода k-средних.

Данныйрезультат достигался при решении задачи эвристическим алгоритмом выделениямаксимальных подмножнств в пять раз чаще, чем алгоритмом на основе методаTTk-средних. Наихудший результат по индикатору X нов( X нов= 17 ) был полученпри решении задачи методом k-средних (данный результат достигался дважды).Среднее квадратичное отклонение величины~Tдля эвристическогоX нов90алгоритма выделения максимальных подмножеств почти в два раза превосходитэту величину, полученную при решении задачи алгоритмом на основе метода kсредних.TГрафики зависимостей среднего числа построенных объектов X новисреднего времени вычислений tпотребителейдляэвристическогоот числа подключаемых к электросетиалгоритмавыделениямаксимальныхподмножеств, алгоритма разделительной кластеризации и алгоритма на основеметода k-средних, приведены в Таблицах 4.5., 4.6.