Диссертация (1025823), страница 14
Текст из файла (страница 14)
[68].Схема алгоритма решения подзадачи 2, основанного на построениидиаграмм Вороного, приведена на Рис. 4.14.Tисх , Tнов , СLподклПостроение диаграммы Вороного дляэлементов множеств Тисх и ТновК каждой ТП Т i подключаем потребителейИсключаем из Тисх и Тнов перегруженные ТП,из Сподклмножества Сподкл расположенных в его сектореподключенных потребителейНетВсе Сiподкл подключены?∗X 2 ДаРис. 4.14.
Схема алгоритма решения подзадачи 2, основанная на построениидиаграмм Вороного99Исходными данными для решения задачи являются элементы множествТисх , Тнов , а также множество подключаемых к электросети потребителей CL.исхи Тнов строитсяНа первом шаге алгоритма для ТП Т i множеств Тдиаграмма Вороного.Далее для каждой ТП Т i производится попытка подключения к нейпотребителеймножестваСLподкл ,расположенныхвееобласти.Всепотребители, для которых выполнены условия возможности подключения их кисхподкли ТновТП Т i исключаются из множества СL.
Также из множеств Тисключаются ТП, к которым отсутствует возможность подключения новыхпотребителей (нет свободных мест на сборке или отсутствует свободнаямощность). Для оставшихся элементов множествТисх ,Тнов ,СLподклпроизводится повторное построение диаграммы Вороного и исключениеобъектов из множеств.Алгоритм прекращает работу, когда во множестве СLподкл не останется ниодного элемента либо на очередном шаге работы алгоритма не будет ни одноговозможного варианта подключения потребителей к ТП.4.2.4. Сравнительный анализ эффективности алгоритмовОценка эффективности алгоритмов произведена в ИПК ELNET (глава 5).Результаты решения подзадачи 2 на тестовых картах малой размерности (3карты, состоящие из 5 ТП и 35 потребителей каждая) для всех разработанныхалгоритмов решения подзадачи 2 совпадают с точным решением задачи.Анализ эффективности алгоритмов на картах большей размерностипроводим на наборе из 20 тестовых карт, каждая из которых включает в себя 100потребителей и 16-19 ТП, обеспечивающих для каждого подключаемого кэлектросети потребителя хотя бы один допустимый вариант подключения.
Числои координаты ТП для тестовых карт получены с помощью эвристическогоалгоритма решения подзадачи 1.100Для каждой тестовой карты выполнено решение задачи эвристическималгоритмом, алгоритмом, основанным на построении диаграмм Вороного и ГА(30 запусков, мультистарт).Сравнительный анализ решений производим по двум индикаторамкачества:• суммарная стоимость построенных КЛ –d sum ;• время выполнения расчетов – t .Результаты анализа эффективности алгоритмов приведены в Таблицах 4.8.,4.9. и на Рис. 4.15.Вычислительные эксперименты ГА проводились при следующих значенияхпараметров: начальная популяция – 20 особей; число скрещиваний – 5; числомутаций – 5; критерий останова – стагнация.Таблица 4.8.sumСуммарная стоимость строительства КЛ d , тыс.
руб.sumКарта1Суммарная стоимость строительства КЛ, d , тыс. руб.ЭвристическийАлгоритм,Генетическийалгоритмоснованный наалгоритм (min на 30ограниченногопостроении диаграммзапусков)перебораВороного2514722739227392258262893825921326554300202712842456426742245645213452539221203621456239452145672398826483239888229992432323102926232299922699310258922931925925101Таблица 4.8.
Продолжение11219392634721939122234728736222641324342297372434214263842784326873152700132134273821626431293822598317213542783421732182222329031222231925498297432598420257833139226183Среднеепо 20 картам24244,928124,124396,2В Таблице 4.8. красным цветом отмечены ячейки с минимальным значениемsumиндикатора d . Более светлый цвет ячейки означает, что такое же значениеd sum достигнуто еще одним из алгоритмов.Таблица 4.9.Среднее время выполнения алгоритмов t (20 карт), секЭвристическийалгоритмограниченногоперебора2,3Генетическийалгоритм(30 запусков)2330Алгоритм,основанный напостроении диаграммВороного10,5102d sum , тыс.
руб.2900028000270002600025000ГенетическийалгоритмАлгоритм,28124ЭвристическийоснованныйалгоритмнаограниченногопостроенииперебораДиаграмм24245Вороного…240002300022000sumа) Средняя стоимость строительства КЛ (20 карт) d , тыс. руб.t , сек.Генетическийалгоритм233010000100010010Эвристическийалгоритмограниченногоперебора2,3Алгоритм,основанныйнапостроенииДиаграммВороного…1б) Среднее время выполнения алгоритма (20 карт) t , сек.Рис.
4.15. Средняя стоимость строительства КЛ (а) и время выполненияалгоритмов (б)Анализ результатов вычислений, представленных в Таблицах 4.8., 4.9.показывает, что лучшие значения по индикатору суммарная стоимостьsumстроительства КЛ dполучены при решении тестовых задач эвристическиалгоритмом ограниченного перебора (17 случаев из 20) и алгоритмом,основанном на построении диаграмм Вороного (10 случаев из 20). При этом в 7sumслучаях из 20, значения dу данных алгоритмов совпадают.
Решение задачиГА в среднем хуже лучшего значения для тестовой задачи на ~12% и не хуже чемна ~16%. При увеличении числа подключаемых потребителей со 100 до 1000,описанные выше тенденции сохраняются.Зависимости времени вычислений t от числа подключаемых к электросетипотребителей, приведены в Таблице 4.10.103Таблица 4.10.Зависимость среднего времени вычислений t от числа подключаемыхпотребителей СподклЧислоподключаемыхпотребителейСподкл100Среднее время вычислений t , сек.ЭвристическийАлгоритм,Генетическийалгоритмоснованный наалгоритмограниченногопостроении(30 запусков)переборадиаграмм Вороного233010,52,32004,5545614,53007,81278623,150019,32435634,5100027,84896742,7На основании приведенных выше данных можно сделать следующиевыводы.1) Точный алгоритм решения задачи определения варианта подключенияпотребителей к электросетям может быть применим только к картам малойразмерности.
Так, уже для карты, состоящей из четырех ТП и 19 подключаемыхк электросети потребителей, ориентировочное время расчета на ЭВМ составляет~370 часов.2) На картах малой размерности (5 ТП и 35 потребителей) всеразработанные алгоритмы дают решение, совпадающее с точным решением.3) На тестовых картах размерности от 100 до 1000 подключаемыхпотребителей лучшие показатели по обоим индикаторам ( dsumи t ) показываюталгоритм ограниченного перебора и алгоритм, основанный на построенииsumдиаграмм Вороного.
ГА, в среднем, дает результат по индикатору dна ~12,5%хуже, чем у данных алгоритмов, при этом время работы данного алгоритмабыстро растет с увеличением числа подключаемых потребителей.1044.3.Подзадача 3. Определение итоговой структуры электросети.Генетический алгоритмЦелью решения подзадачи 3 является определение варианта возможногоподключения новых ТП, «построенных» при решении подзадачи 1, ксуществующей электросети. В диссертации решение подзадачи 3 производитсяпосредством ГА.Для решения подзадачи 3 посредством ГА поставим в соответствие каждойновой ТП Тiнов два гена хромосомы: первый ген соответствует ТП/РП, откоторой в i-ую ТП производится подача электроэнергии; второй генсоответствует ТП/РП, куда передается электроэнергия от ТП Тiнов .
Значениемгена (аллелью) является номер ТП/РП H j , к которой будет подключенпотребитель Сk . Длина хромосомы равна 2 Тнов (Рис. 4.16)....123X 11 = H iX 21 = H jX 12 = H kТ1новX1X 22 = H nТ 2нов2 Тнов...X2T новT новТ новТ новРис. 4.16. Хромосома ГА для решения подзадачи 3Блок-схема алгоритма решения подзадачи 3 методом генетического поискапредставлена на Рис. 4.17.Исходными данными для подзадачи 3 являются граф электросети G исх ,**векторы Х 1 , Х 2 , полученные в результате решения подзадач 1, 2.На первом шаге алгоритма для каждой ТП Т kнов определяем вариант еевключения в электросеть, удовлетворяющие ограничениям (3.8):• «разрыв» существующей КЛ LH iисх(и удалением ее из множества,jLH исх ) и последующее строительство двух новых КЛ LH iT, k и LH kT, j ;105• строительство новой цепочки РП-ТП-РП посредством прокладки двух КЛLH iT, k и LH kT, j , где i, j – номера РП электросети.В случае если хромосома соответствует всем ограничениям, онадобавляется в начальную популяцию.
Процесс производится до тех пор, пока вначальной популяции не будет N p хромосом.После завершения процесса формирования популяции, над особямипопуляции производятся основные действия ГА – оценка их фитнесс-функции,селекция, скрещивание, мутация. Если в результате выполнения этих процедур,получено решение, удовлетворяющее условию окончания вычислений, тоалгоритм прекращает работу, а результатом решения задачи объявляется вектор*Х 3 . В противном случае, алгоритм продолжает формирование новых популяцийи выполнение над ними указанных генетических операций.G исх , Tнов , R новФормирование начальной популяцииНетОценка особей популяцииСелекцияСкрещиваниеФормирование новой популяцииМутацияНетВыполнен критерийостанова?Нетˆt,Zˆ t ) = 1?P (ХДаСтроительство новых РПДа∗X3Рис.
4.17. Схема алгоритма решения подзадачи 3 на основе ГА1064.4.Алгоритмы решения задачи координации**Исходными данными для задачи координации являются векторы X1t , X t2 ,*X 3t , полученные в результате решения подзадач 1 – 3 на итерации tсоответственно. Алгоритм решения задачи координации включает в себя тримодуля (Рис. 3.2).
Основными функциями, выполняемыми задачей координации,являются:1) расчет параметров координации S t ;2) определение последовательности решения подзадач 1-3;3) определение момента окончания вычислений.Задача координации управляет решением задачи ПРЭ воздействием наподзадачу 1 посредством параметров координации{}S = s1 , s2 , S 3 .Здесьs1 , s 2– лимитирующие параметры координации;S3– векторстимулирующих параметров координации:( )T) – минимальное число ТП, которое должно быть построено;= min (N новR– минимальное число РП, которое должно быть построено;s1 = min N новs2S 3 = {λi , i ∈ [1... O ]}–векторпараметров,гдеλi–величина,характеризующая «полезность» строительства новой ТП в i-й точке множества O.Предполагаем следующие алгоритмы расчета коэффициентов λi .1) Алгоритм, не учитывающий электрические мощности.
Алгоритм задаетсяформулойCλi = α ∑ δ (li, j ) i ∈ [1: O ],,j =0(4.1)107где α – нормировочный коэффициент; C = {c j , j ∈ ⎡⎣1: C ⎤⎦} – текущее множествонеподключенных потребителей; li, j – длина КЛ Li , j ; l max – максимальнодопустимая длина КЛ; δ (li , j ) – вспомогательная функция такая, что⎧⎪1, если li, j < l max ,δ (li, j ) = ⎨⎪⎩0, иначе;Формула (4.1) имеет следующий смысл.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
