Exact and Evolutionary Algorithms for Sequential Multi-Objective Transmission Topology Planning

기술 요약: 순차적 다목적 송전 토폴로지 계획에 대한 정확한 알고리즘 및 진화적 알고리즘

문제 정의
본 논문은 하루 전 송전 토폴로지 계획을 순차적 다목적 최적화 문제로 다룹니다. 목표는 그리드 혼잡을 관리하기 위해 24 시간 시간 범위 (24 시간 단계) 에 걸쳐 네트워크 토폴로지들의 시퀀스를 결정하는 것입니다. 이 문제는 실제 송전 시스템 운영자 (TSO) 의 의사결정 기준을 반영하는 네 가지 운영 목적 함수로 정의되며, 모두 최소화되어야 합니다:

1. 최악의 경우 선로 부하 ($LF_1$): 전체 시간 범위 내 $N-1$ 보안 contingencies 하에서 모든 송전 선로의 최대 용량 활용도.
2. 토폴로지 깊이 ($d$): 기준 토폴로지 (모든 커플러가 닫힌 상태) 대비 버스바 커플러를 개방하여 (노드 분할) 생성된 추가 버스바의 최대 개수. 이는 임의의 시간 시점에서 측정됩니다.
3. 스위칭 동작 수 ($w$): 24 시간 기간 동안 수행된 토폴로지 변경 (스위치) 의 총 횟수.
4. 비기준 토폴로지 활용도 ($z$): 네트워크가 기본 기준 토폴로지와 다른 구성으로 운영되는 시간 단계의 수.

본 연구는 TenneT TSO 가 관리하는 네덜란드 고전압 그리드의 실제 운영 데이터를 활용하며, $N-1$ 조건 하에서 기준 토폴로지가 빈번히 100% 를 초과하는 부하를 겪는 혼잡한 날에 초점을 맞춥니다.

방법론
저자들은 두 가지 상호 보완적인 알고리즘을 제안하고 비교합니다: 정확한 열거법과 맞춤형 진화 휴리스틱입니다.

1. 블록 알고리즘 (정확한 방법):

   • 핵심 개념: 이 알고리즘은 실현 가능한 전략들의 시간적 블록 구조를 활용합니다. 각 시간 단계를 독립적으로 평가하는 대신, 24 시간 범위를 토폴로지가 일정하게 유지되는 연속적이고 중첩되지 않는 구간 (블록) 으로 분할합니다.
   • 메커니즘: 가능한 모든 블록 구성, 기준 토폴로지 할당, 그리고 깊이 수준을 체계적으로 열거합니다. 각 시간 단계별 사용 가능한 모든 토폴로지에 대한 부하 흐름 값을 사전 계산함으로써, 알고리즘은 블록들의 조합을 평가하여 완전한 파레토 프론트를 식별합니다.
   • 복잡도: 최대 깊이 ($d_{max}$) 와 최대 스위칭 횟수 ($s_{max}$) 에 대한 고정된 운영 범위 내에서, 평가 횟수는 계획 시간 범위에 따라 다항식적으로 증가합니다. 이 알고리즘은 비우세 정렬을 기반으로 전략을 필터링하며, 네 가지 목적 함수 중 세 가지가 이산 정수라는 사실을 활용하여 파레토 최적 해를 효율적으로 식별합니다.

2. 다목적 진화 알고리즘 (MOEA):

   • 프레임워크: 다목적 문제 (네 가지 목적 함수) 에서의 효과성으로 선택된 NSGA-III 기반.
   • 표현: 각 유전자가 특정 시간 단계의 토폴로지를 나타내는 직접적인 가변 길이 인코딩을 사용합니다.
   • 초기화: 균일 무작위 초기화 대신 "구조 유도" 샘플링 전략을 사용합니다. 이는 관련 목적 함수 공간 차원에서의 다양성을 보장하기 위해 특정 스위칭 횟수와 토폴로지 깊이를 균형 있게 조정하여 초기 개체군을 생성합니다.
   • 변이: 시간적 일관성을 보존하기 위해 $k$-점 교차 ($k=2$) 를 사용하고, 각 시간 단계별 사용 가능한 토폴로지 집합 내에서 실현 가능성을 보장하기 위해 무작위 재설정 변이를 사용합니다.

주요 기여

1. 공식화: 문제를 네 가지 특정 TSO 관련 목적 함수를 가진 순차적 다목적 최적화로 공식적으로 정의하여, 단일 목적 함수 또는 고립된 시간 단계 형식을 넘어섰습니다.
2. 정확한 열거: 실제 혼잡한 날에 대한 완전한 파레토 프론트를 3 분 미만으로 계산하는 "블록 알고리즘"을 개발했습니다. 이는 해당 문제 클래스에 대한 기준 (ground-truth) 벤치마크를 제공합니다.
3. 맞춤형 휴리스틱: 구조 유도 초기화와 문제 특화 변이 연산자를 갖춘 전문 MOEA 를 설계하여, 역세대 거리 플러스 (IGD+) 와 새로운 다중 프론트 커버리지 지표를 사용하여 정확한 프론트와 비교 평가했습니다.
4. 실증적 검증: TenneT 데이터를 사용한 비교 연구는 정확한 열거가 계산적으로 실행 가능하며, 진화적 탐색보다 최적 전략의 전체 집합을 복원하는 데 더 우수함을 입증했습니다.

결과

• 블록 알고리즘의 성능: 정확한 방법은 완전한 파레토 프론트를 성공적으로 열거하여 목적 함수 공간에서 83 개의 고유한 점 (163,807,652 개의 고유한 전략을 나타냄) 을 식별했습니다. $LF_1 < 100\%$(완전한 $N-1$ 보안) 를 달성하려면 혼잡 시간 동안 기준 토폴로지를 완전히 포기하고 더 높은 토폴로지 깊이에서 운영해야 함을 발견했습니다.
• MOEA 의 성능: 진화 알고리즘은 파레토 프론트 수렴을 보였으나 정확한 해 집합을 복원하지는 못했습니다.
  • 가장 성능이 우수한 구성 (개체군 크기 1,621, 변이율 0.10) 은 블록 알고리즘이 찾은 고유 파레토 최적 점의 약 6% 만 복원했습니다.
  • MOEA 는 정확한 방법에 의해 식별된 $LF_1 < 100\%$ 해를 찾는 데 어려움을 겪었습니다.
  • 많은 비기준 토폴로지를 포함하는 전략 (검색 공간의 극단적 영역) 에 대한 커버리지는 특히 낮았습니다.
• 비교: MOEA 는 빠른 초기 수렴 (5 분 이내) 을 보였으나, 이후 정체되어 블록 알고리즘의 완전성과는 비교할 수 없었습니다. 모든 실현 가능한 전략을 열거할 수 있는 블록 알고리즘의 능력은 휴리스틱이 놓친 트레이드오프를 식별할 수 있게 했습니다.

의의 및 주장
본 논문은 24 시간 시간 범위에 걸친 토폴로지 전략 최적화의 조합적 복잡성이 종종 해결 불가능한 것으로 인식되지만, 문제의 시간적 블록 구조를 활용함으로써 정확하고 효율적으로 해결될 수 있다고 주장합니다.

• 의사결정 지원: 블록 알고리즘은 TSO 에게 완전한 파레토 최적 전략 메뉴를 제공하여, 운영자가 특정 일일 우선순위 (예: 스위칭 최소화 대 보안 극대화) 에 따라 행동을 선택할 수 있게 합니다.
• 벤치마킹: 정확한 프론트는 향후 휴리스틱 및 학습 기반 방법을 평가하기 위한 엄격한 기준 (ground-truth) 벤치마크 역할을 합니다.
• 실행 가능성: 본 연구는 정확한 열거가 이론적으로 가능할 뿐만 아니라 실제 세계의 고도로 혼잡한 그리드 시나리오에서도 실용적으로 실행 가능함을 입증하여, 이러한 문제에 대해 휴리스틱이 필수적이라는 가정에 도전합니다.

저자들은 DC 전력 흐름 근사, 결정론적 예측, 그리고 사전 계산된 데이터셋에 대한 의존성을 포함한 한계를 인정합니다. 향후 연구는 확률적 형식화, 강건 최적화, 그리고 사전 계산 병목 현상을 우회하기 위한 모방 학습의 적용을 포함할 수 있다고 제안합니다. 그러나 연구 범위 내에서 블록 알고리즘은 정확성, 속도, 그리고 완전성으로 인해 선호되는 방법으로 제시됩니다.