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

и на Рис. 4.9. Средниезначения указанных индикаторов рассчитаны на основании 5 вычислительныхэкспериментов на карте каждого типоразмера.Таблица 4.5.~TСреднее число построенных ТП X нов~Числопотребителейна карте1002003005001000TСреднее число построенных ТП X новЭвристическийАлгоритмалгоритмАлгоритмна сновевыделенияразделительнойметодамаксимальных кластеризацииk-среднихподмножеств13,116,014,225,332,031,439,140,046,360,066,068,0122,9120,0188,0Таблица 4.6.Среднее время выполнения программы tЧислопотребителейна карте100200300Среднее время работы алгоритмов tЭвристическийАлгоритмАлгоритмАлгоритмна основевыделенияразделительнойметодамаксимальных кластеризацииk-среднихподмножеств81,6236,4218,4184,5781,01203,4276,41734,12922,091Таблица 4.6. Продолжение5001000640,71625,08063,936700,07114,721828,0t , сек4000035000Эвристическийалгоритм300002500020000k-средние1500010000Разделительнаякластеризация500001002003005001000Числоподключаемыхпотребителейа) Время вычислений~TX нов140120100Эвристическийалгоритмk-средние8060Разделительнаякластеризация402001002003005001000Числоподключаемыхпотребителейб) Число построенных объектовРис.

4.9. Графики зависимостей среднего времени вычислений t и среднего~Tчисла построенных объектов X новот числа подключаемых потребителейНа основании данных, представленных на Рис. 4.9, можно сделать вывод означительном росте времени вычислений t алгоритма на основе метода kсредних, и алгоритма разделительной кластеризации, с ростом числа92подключаемых потребителей. При этом все алгоритмы показывают примерноT. Таким образом, делается вывод оX новодинаковые числа построенных ТПцелесообразностипримененияэвристическогоалгоритмавыделениямаксимальных подмножеств для решения подзадачи 1.4.2.

Подзадача 2. Определение варианта подключения новых потребителейк электросетиПодзадача2заключаетсявопределенииоптимальноговариантаподключения новых потребителей к электросети. При этом подключениепотребителей может производиться как к исходным ТП электросети, так и кновым ТП (построенным в результате решения подзадачи 1).Исходными данными для решения подзадачи являются множествоподключаемыхпотребителейСLимножествоТитог = TΔ ∪ Tнов .ТПВ результате решения для каждого потребителя СLподклопределяется значениеiпараметра X i , определяющего вариант его подключения к электросети.Подзадача 2 относится к классу дискретных. Вычислительную сложностьзадачи иллюстрирует Таблица 4.7. Приведенное в таблице число представляетсобой среднее значение числа альтернатив для трех карт указанной размерности,сгенерированных случайным образом.Таблица 4.7.Среднее число альтернатив при решении подзадачи 2Число ТПЧисло подключаемых потребителей1516171819225656413452048566431382427648124416248832746496420155392285764834031078416124313648372940893Таблица 4.7.

показывает невозможность решения подзадачи 2 посредствомполного перебора. Поэтому решение данной подзадачи в диссертациипроизводится посредством следующих алгоритмов:1) эвристический алгоритм ограниченного перебора;2) генетический алгоритм (ГА);3) алгоритм, основанный на построении диаграмм Вороного.4.2.1. Эвристический алгоритм ограниченного перебораПредложенный эвристический алгоритм относится к классу так называемых«жадных» алгоритмов решения оптимизационных задач.Решение задачидостигается постепенно добавлением в вектор решения элемента, вносящегонаименьший среди всех возможных вариантов вклад в целевую функцию.

Схемаалгоритма приведена на Рис. 4.10.Тисх , Тнов , CLподклДля СLподклпотребителя определитьiсписок возможных вариантов подключенияВыбрать СLподклпотребителя, ближеiдругих расположенного к ТППодключить потребителя СLподклiк ближайщей ТП Т jПодключить неподключенныхпотребителей в первую очередьИмеются вариантыподключения?НетВсе потребителиподключены?ДаДаНет*X t2Рис.

4.10. Схема эвристического алгоритма ограниченного перебора дляподключения потребителей к ТП электросети94Исходными данными являются исходное множество ТП Тисх , множествоТП Тнов , «построенных» в ходе решения подзадачи 1, а также множествоподключаемых потребителей СL .На первом шаге алгоритма определяем список возможных вариантовподключения к электросети для каждого потребителя СLi .Далее из всех потребителей множества CL выбираем СLi потребителя,подключение которого к электросети потребует строительство КЛ наименьшейдлины.

Выбранного потребителя «подключаем» к ТП, расстояние до которойявляется минимальным. Данную процедуру проводим для всех СLi элементовмножества CL. После каждой процедуры подключения потребителя кэлектросети, множество вариантов подключения определяем повторно.В результате выполнения алгоритма возможна ситуация, когда один илинесколько потребителей не будут подключены к электросети. В этом случаерешение задачи производится повторно, при этом неподключенные напредыдущей итерации потребители «подключаются» первыми.4.2.2. Генетический алгоритмГА являются мощным методом оптимизации, позволяющим найти оптимумбыстрее, чем многие другие методы случайного поиска. Существеннымдостоинством ГА является их универсальность и, как правило, высокая скоростьсходимости. К недостаткам алгоритмов можно отнести большое время поискаэкстремума, что не позволяет их использовать в быстродействующих системахреального времени [64].ДляпримененияГАнеобходимопреобразоватьпеременные,фигурирующие в условии задачи, в генетические переменные.

Такоепреобразование задается схемой кодирования. Переменные могут быть95представлены в двоичной форме, в форме действительных десятичных чисел илив другой форме, в зависимости от смысла решаемой задачи.Основными операторами ГА являются кроссовер (обмен генетическимматериалом между хромосомами), мутация (локальное изменение одного илинескольких генов хромосомы), выбор родителей для скрещивания и селекция(отбор хромосом в новую популяцию).В настоящее время существует десятки вариантов модификаций каждого изуказанных операторов, применяемых в ГА.

Некоторые комбинации схемыкодирования и вида основных операторов ГА приводят к типовым моделям –канонический, простой, гибридный, многопопуляционный ГА и др. [34].Например, для канонического ГА характерны бинарное кодирование особей;постоянный размер популяции; управление популяцией методом рулетки;селекция особей для скрещивания случайным равновероятностным методом;использование одноточечных кроссовера и мутаций. Простой ГА отличается отканоническоготолькоприменениеметодатурнирногоотборавместорулеточного.

Гибридный ГА как правило основан на комбинации ГА с некималгоритмомлокальногопоиска(например,градиентного),авмногопопуляционном ГА предполагается наличие нескольких популяций, работас которыми может производиться параллельно [23].Для решения подзадачи 2 посредством ГА поставим в соответствиекаждому подключаемому потребителю СLподклодин ген хромосомы (Рис. 4.11).jЗначением гена (аллелью) является номер ТП/РП H i , к которой будетподключен СLподклпотребитель. Длина хромосомы равна CL .jX CLподклX1 = H i X 2 = H j12...СLподклРис.

4.11. Схема кодирования хромосомы при решении подзадачи 2 ГАСхема решения подзадачи 2 посредством ГА представлена на Рис. 4.12.96Tисх , Tнов , СLподклОпределить возможные варианты подключениядля каждого потребителя множества СподклФормирование начальной популяцииОценка особей популяцииСелекцияСкрещивани еФормирование новойпопуляцииМутацияˆt,Zˆ t ) = 1?P (Х∗X2ДаРис. 4.12. Схема решения подзадачи 2 ГАВходными данными для ГА является электросеть G исх и множествоподключаемых к ней потребителей СL .На первом шаге алгоритма для каждого из потребителей множества СLопределяется список вариантов, к которым возможно произвести подключение.Полученные варианты должны удовлетворять всем ограничениям (3.8).При формировании хромосом начальной популяции производится ихпроверка на выполнение всех наложенных на электросеть ограничений (3.8).В случае если хромосома соответствует всем ограничениям, она добавляется вначальную популяцию.

Процесс производится до тех пор, пока в начальнойпопуляции не будет N p хромосом.97После завершения формирования популяции, над ее особями производятсяосновные действия ГА – оценка их фитнесс-функции, селекция, скрещивание,мутация.Если результат решения не удовлетворяет критерию окончания вычисленийˆ t , Zˆ t ) ≠ 1, то алгоритм продолжает формирование новых популяций иР(Хвыполнение над ними основных генетических операций. В противном случае,алгоритм завершает работу.*Результатом решения подзадачи 2 является вектор Х 2 .Алгоритм может включать в себя различные варианты реализацииосновных операторов ГА. ИПК ELNET (глава 5) позволяет пользователюпроизвести выбор из следующих возможных вариантов.1) Селекция:• случайный равновероятностный метод.2) Скрещивание:• одноточечный кроссовер;• многоточечный кроссовер.3) Мутация:• одноточечная;• многоточечная.4.2.3.

Алгоритм, основанный на построении диаграмм ВороногоДиаграмма Вороного некоторого множества точек представляет собой такоеразбиение плоскости, на которой расположены данные точки, при которомкаждая область этого разбиения образует множество точек более близких кэлементу исходного множества, расположенного в указанной области, нежели клюбому другому элементу этого множества (Рис. 4.13) [78].98Рис. 4.13.

Разбиение пространства построением диаграммы ВороногоДиаграммаВороногоявляется однимиз основныхинструментомвычислительной геометрии и активно применяется при решении задачраспознавания образов, робототехники, геодезии, компьютерной графики, САПР[35]. Существует множество различных алгоритмов построения диаграммВороного, таких как простой алгоритм, алгоритм Форчуна, рекурсивныйалгоритм и т.д.