2.1 국내 사례 조사

국내에서는 에너지저장장치의 최적 충·방전 계획법에 관한 다양한 연구가 진행되고 있다. 첫째, 결정론적 혼합정수 계획법(Deterministic mixed integer programming)을 이용하여 에너지저장장치의 동시 충·방전 제약을 이진 변수를 통해 제어하고, 충·방전 효율과 충전상태를 고려해서 충·방전 계획을 제시했다.⁽⁵⁾ 둘째, 결정론적 이차 계획법 (Deterministic quadratic programming) 기반의 최적 충·방전 계획을 제시했다⁽⁶⁾. 하지만 위의 연구들은 이진 변수를 사용하여 최적 계획을 찾는 시간이 오래 걸렸다. 그뿐 아니라 고정된 한 가지 상황에 대해서만 최적 충·방전 동작을 제시했고 불확실한 미래의 다양한 상황을 고려하지 않았기 때문에 계산된 충·방전 계획은 예상치 못한 모든 상황에 대한 최적 계획은 아니다. 본 논문에서는 이진 변수 없이 동시 충·방전을 제약하여 연산시간을 줄이고, 시나리오 나무를 이용해 불확실한 미래의 다양한 상황을 고려한 최적 충·방전 계획을 제시한다.

2.2 해외 사례 조사

해외에서도 에너지저장장치의 최적 충·방전 계획법에 관한 다양한 연구가 진행되고 있다. 첫째, 확률론적 계획법을 통해 불확실한 미래의 다양한 전력 가격을 고려하여 에너지저장장치의 최적 충·방전 계획을 수립했다⁽⁷⁾. 이 연구에서는 독립적인 시나리오 줄기들을 사용하였으나, 사건들이 서로 의존하는 시나리오 나무를 사용했다면 불확실한 미래의 상황들을 종합적으로 고려한 최적 계획을 구할 수 있었을 것이다⁽⁸⁾. 둘째, 동적 계획법(Dynamic programming)을 이용하여 전력 가격의 불확실성을 고려한 최적 충·방전 계획법을 제시했다⁽⁹⁾. 그러나 동적 계획법을 활용하면 연산시간이 증가한다⁽¹⁰⁾. 이에 반해 본 논문에서는 병렬 연산 기반의 점진적 회피 알고리즘을 이용하여 연산시간을 줄이면서, 시나리오 나무를 사용하는 다단계 확률론적 계획법을 활용하여 동작 단계 사이의 의존성을 고려한 최적 충·방전 계획을 제시한다.

3.1 확률론적 계획법

확률론적 계획법은 불확실한 미래의 동작을 시나리오로 나타내고, 시나리오가 실현될 확률을 고려하여 계획을 수립한다. 확률론적 계획법에는 지금 결정해야 하는 현재 결정변수와 시나리오별로 결정이 다른 미래 결정변수가 있다. 즉, 확률론적 계획법은 두 개의 동작 단계를 갖는다⁽¹¹⁾. 본 논문에서는 현재 변수를 $x_{1}$로 정의하고, 시나리오 집합 $S=\{1,\:\cdots ,\:\kappa\}$에 속하는 $k$번째 시나리오에 대한 미래 변수를 $x_{2,\:k}$로 정의한다. 목적함수가 최적이 되도록 모든 시나리오의 $x_{2,\:k}$와 $x_{1}$을 결정한다. 이때, $x_{2,\:k}$는 시나리오별로 서로 다른 값을 갖지만, 현재 변수 $x_{1}$는 모든 시나리오를 고려한 최적의 결정이므로 시나리오 수와 상관없이 항상 하나의 값을 갖는다. 따라서 확률론적 계획법에서는 최종적으로 현재 변수만 사용된다. 이러한 특징을 반영한 확률론적 계획법의 정식화는 아래와 같다.

단, $x_{1}$ : 1단계 결정변수,

$A_{1}$, $b_{1}$ : $x_{1}$에 대한 제약조건의 계수와 상수,

$x_{2,\:k}$ : 시나리오 $k$에 대한 2단계 결정변수,

$A_{2,\:k}$, $b_{2,\:k}$ : $x_{2,\:k}$에 대한 제약조건의 계수와 상수,

$D_{1,\:k}$ : $x_{1}$과 $x_{2,\:k}$의 의존성 제약조건의 계수,

$c_{1}$, $c_{2,\:k}$ : 결정변수 $x_{1}$과 $x_{2,\:k}$에 대한 목적함수의 계수.

확률론적 계획법에서는 모든 시나리오가 각각의 확률을 가지므로, 식(1)의 목적함수의 기댓값은 식(4)와 같이 변수와 확률의 곱으로 표현된다. 식(4)의 정식화된 형태를 전개형 (Extensive form)이라 한다.

단, $\rho_{k}$ : $k$번째 시나리오의 확률.

3.2 다단계 확률론적 계획법

다단계 확률론적 계획법은 동작 단계 사이의 의존성을 고려하기 위해 미래 변수를 여러 단계로 나누어 최적화 문제를 푼다⁽¹²⁾. 다단계 확률론적 계획법에서는 시나리오의 동작 시간마다 각각의 미래 변수가 존재하고, 후속 동작 시간의 변수는 이전 시간의 변수에 의존한다⁽¹³⁾. 단위 시간의 집합 $T=\{1,\:$$\cdots ,\:t,\:\cdots\tau\}$에 대한 다단계 확률론적 계획법의 목적함수는 아래와 같이 표현된다.

단, $x_{t,\:k_{t}}$ : $t$단계에서의 $k$번째 시나리오에 대한 결정변수,

$c_{t,\:k_{t}}$ : 결정변수 $x_{t,\:k_{t}}$에 대한 목적함수의 계수,

$k_{t}$ : $t$단계에서의 $k$번째 시나리오.

이때 각 단계 사이의 상관관계는 식(2)와 식(6)으로 표현된다.

단, $S_{t}=\left\{1,\:\cdots ,\:\kappa_{t}\right\}$ : $t$ 단계의 모든 시나리오의 집합.

식(5)의 다단계 최적화 문제를 식(4)와 같이 전개형으로 표현하면 다음과 같다.

단, $\rho_{k_{t}}$ : $t$단계에서의 $k$번째 시나리오의 확률.

식(7)의 전개형을 이용하여 다단계 확률론적 최적화 문제를 선형으로 표현하면 정확한 결과를 빠르게 얻을 수 있다. 하지만 시나리오의 개수와 고려하는 단계의 개수가 많아질수록 문제의 규모가 커지고 연산시간은 증가한다.

3.3 시나리오 나무

그림 1에 시나리오 나무와 시나리오 줄기가 나와 있다. 그림 1에서 왼쪽에 있는 시나리오 나무의 사건들은 특정 마디까지 서로 같은 값을 가지지만, 그 단계 이후에는 분기해 다른 값을 갖는다. $x^{n}$, $\rho^{n}$, 그리고 $c^{n}$은 각각 마디 $n$의 변수, 확률, 그리고 시나리오 상수를 뜻한다. 이때, 시나리오 나무의 주어진 마디의 확률은 해당 마디에서 분기하는 가지들의 확률의 합과 같다.

시나리오 나무를 개별 줄기들로 분리하면, 그림 1의 오른쪽 그림과 같이 표현된다. $x_{1,\:1}$, $x_{1,\:2}$, $x_{1,\:3}$, $x_{1,\:4}$은 뿌리 마디 변수 $x^{1}$에서 파생된 시나리오 줄기의 첫 단계 변수들이다. $x_{2,\:1}$와 $x_{2,\:2}$는 $x^{2}$에서 파생된 시나리오 변수이고, $x_{2,\:3}$과 $x_{2,\:4}$는 $x^{3}$에서 파생된 시나리오 변수들이다. $x_{3,\:1}$은 $x^{4}$와, $x_{3,\:2}$는 $x^{5}$와, $x_{3,\:3}$은 $x^{6}$과, 그리고 $x_{3,\:4}$는 $x^{7}$과 같다.

그림 1의 오른쪽 그림에서 $\rho_{1}$, $\rho_{2}$, $\rho_{3}$, $\rho_{4}$는 각 시나리오 줄기의 확률을 의미한다. 시나리오 줄기의 확률은 각 시나리오가 포함된 시나리오 나무 마디의 확률들의 곱과 같다. 예를 들어 첫 번째 줄기의 확률 $\rho_{1}$은 $\rho^{2}$와 $\rho^{4}$의 곱과 같다.

4.1 시나리오 분할

점진적 회피 알고리즘의 첫 번째 절차인 시나리오 분할 단계에서는 시나리오 나무, 제약조건 식(2)와 (6), 그리고 목적함수 식(7)을 시나리오 줄기별로 분리한다. 여기서 시나리오 줄기와 그에 따른 제약조건과 목적함수들의 집합을 하위문제라 하고, 다음 절차에서 하위문제들을 병렬로 푼다.

하지만 각 시나리오 줄기의 미래 변수들은 식(2)와 (6)을 통해서 연결되어 있으므로, 식(7)을 개별 시나리오 줄기별로 분리하는 것에 대한 대가로 다음 두 가지 조건이 필요하다. 첫째, 같은 마디에서 분기한 시나리오 줄기의 마디 변수들은 모두 같은 값을 가져야 한다. 따라서 시나리오 나무의 단계에 해당하는 변수를 시나리오 줄기의 단계에 해당하는 변수로 복제한다. 그림 1을 예시로 첫 번째 조건을 표현하면 아래와 같다.

둘째, 시나리오 나무의 마디에서 분기한 시나리오 줄기들의 확률 가중 평균은 시나리오 나무의 마디의 변수와 같아야 한다. 이 조건을 수식으로 표현하면 아래와 같다.

위의 두 조건을 합하면 아래와 같이 나타낼 수 있다.

단, $J=\operatorname{diag}\left(\left[\rho_{1} \mathbf{1}_{4}, \rho_{2} \mathbf{1}_{4}, \rho_{3} \mathbf{1}_{4}, \rho_{4} \mathbf{1}_{4}\right]^{T},\left[\rho^{4} \mathbf{1}_{2}, \rho^{5} \mathbf{1}_{2}\right]^{T},\left[\rho^{6} \mathbf{1}_{2}, \rho^{7} \mathbf{1}_{2}\right]^{T}\right)$,

$\mathbf{1}_{4}=[1,1,1,1]^{T}, \quad \mathbf{1}_{2}=[1,1]^{T}$,

$X$ : 결정변수 $x_{1}$ 및 $x_{t,\:k}$의 집합.

시나리오 나무의 같은 마디에서 파생된 시나리오 줄기들의 변수들이 같은 값을 가지도록 하는 식(10)을 ‘비 예상 제약조건(Non-anticipativity constraint)’이라 한다. 이때 마지막 단계의 변수들은 모두 분기 확률을 1로 가지므로, 비 예상 제약조건을 고려하지 않아도 된다. 이때, 시나리오 집합 $S=\{1,\:\cdots ,\:\kappa\}$를 갖는 다단계 확률론적 최적화 문제를 각 시나리오에 대해 분할하여 수식화하면 아래와 같다.

4.2 최적화 문제 정식화

점진적 회피 알고리즘은 비 예상 제약조건을 고려하며, 서로 다른 제약조건을 갖는 각 시나리오에 대한 하위문제를 개별적으로 풀어 최적해를 결정한다⁽¹⁴⁾. 식(11)과 같이 시나리오 분할 방법을 통해 각각의 시나리오 줄기에 대한 하위문제가 생성되었을 때, $k$번째 시나리오 줄기에 해당하는 하위문제는 아래와 같다.

단, $x_{k}=\left\{x_{1,\:k},\:x_{2,\:k},\:\ldots ,\:x_{\tau ,\:k}\right\}$ : $k$ 시나리오의 모든 변수 $x_{t,\:k}$ 집합

$\forall x_{k}\in\Omega_{k}$는 각 시나리오 줄기의 모든 변수 $x_{t,\:k}$가 해당 하위문제의 제약조건을 만족해야 함을 의미한다. 이때, 하위문제의 최적해는 비 예상 제약조건도 만족해야 하므로 다른 줄기의 변수들과 여전히 엮여있다. 점진적 회피 알고리즘에서는 이 엮임을 풀기 위해서 라그랑지안 방식을 이용한다. 라그랑지안 방식에서는 제약조건을 완화한 후, 완화된 제약조건의 오차를 페널티의 의미를 갖는 이중변수(dual variable) $\lambda_{k}$를 곱하여 목적함수에 반영한다. 오차는 개별 하위문제들의 최적해를 식(10)을 이용해서 가중 평균한 후 구해진 시나리오 줄기의 마디별 대푯값 $\hat x = J X$와 개별 하위문제들의 최적해와의 차이가 된다. 결과적으로 비 예상 제약조건을 제약조건에서 제외하고, 해당 하위문제와 관련 없는 변수들은 이전 반복에서 구했던 값들로 대체해서 독립된 하위문제를 가진다. 식(12)의 하위문제에 비 예상 제약조건을 반영한 하위문제는 아래와 같다.

단, $\lambda_{k}$ : 이중변수 $\lambda_{k}$의 집합,

$\hat x$ : 가중 평균값 $\hat x$의 집합.

이때, 볼록성(convexity)을 보존하기 위해 증강 라그랑지안(Augmented Lagrangian)을 아래와 같이 이용한다.⁽¹⁵⁾

단, $r$ : 이중변수 $\lambda_{k}$의 값을 결정할 때의 페널티,

$\|\cdot\|$ : 유클리드 노름 (Euclidean norm).

다음 절차에서는 반복적인 연산을 통해 하위문제들의 최적해를 구하고, 이들을 이용하여 $\hat x$과 $\lambda_{k}$를 갱신한다.

4.3 점진적 회피 알고리즘의 진행 절차

점진적 회피 알고리즘은 표 1에 나와 있는 절차를 통해 다단계 확률론적 최적화 문제의 최적해를 찾는다.

첫째, 시나리오 분할을 통해 구한 식(14)에 나와 있는 각각의 하위문제를 개별적으로 풀어 변수의 값을 결정하고, 비 예상 제약조건 관련 식(10)을 통해 시나리오 나무의 나뭇잎에 해당하는 변수를 제외한 나머지 마디의 변수의 값 $\hat x$을 결정한다. 둘째, 시나리오 나무의 마디 변수와 각 하위문제의 시나리오 줄기의 마디 변수 사이의 거리 $(x_{k}-\hat x)$를 구하고, $(x_{k}-\hat x)$를 통해 $\lambda_{k}$를 갱신한다. 셋째, 모든 거리의 합이 일정 기준을 만족하지 못하면 위의 과정을 반복한다.

최적해의 수렴은 근위 점 알고리즘(Proximal Point Algorithm)에 의해 증명된다.⁽¹⁶⁾ 근위 점 알고리즘에 의해 구해진 중간 단계의 최적해는 실제 최적해에 대한 재귀적인 투영을 통해 최적값으로 수렴한다. 논문에서 사용한 증강 라그랑지안 방법은 근위 점 알고리즘에서 파생되었기 때문에 점진적 회피 방법을 이용하여 구해진 각 하위문제의 해는 모두 하나의 최적해에 수렴한다.

5.1 에너지저장장치의 전력시장 참여 설계

이 논문에서 모든 에너지저장장치 사업자는 세 가지 가정 하에 가상의 한 시간 전 전력시장에 참가한다. 첫째, 에너지저장장치의 발전 및 수명감소 비용은 없다. 둘째, 에너지저장장치의 동작 기준은 한 시간이다. 셋째, 차익거래를 허용하기 위해 에너지저장장치는 24시간 동안 판매 입찰과 구매 입찰을 자유롭게 선택할 수 있지만, 같은 시간에 대해 판매 입찰과 구매 입찰을 동시에 선택할 수 없다. 세 가지 가정하에서 에너지저장장치의 시간당 최적 충·방전 입찰량을 결정하는 하위문제의 목적함수는 아래와 같다.

단, $\pi_{t,\:k}$ : $t$단계, $k$번째 시나리오의 전력 가격 [KRW],

$b_{t,\:k}^{+}$ : $t$단계, $k$번째 시나리오에 대한 판매 입찰 [kW],

$b_{t,\:k}^{-}$ : $t$단계, $k$번째 시나리오에 대한 구매 입찰 [kW].

식(15)에서 에너지저장장치 사업자의 수익은 판매 입찰과 구매 입찰의 차이와 전력 가격의 곱으로 계산한다. 추가로 허위입찰을 방지하기 위해 구매 및 판매 입찰은 에너지저장장치의 최대 충·방전량을 기반으로 계산된 최대 입찰량을 초과하지는 않는다.

5.2 에너지저장장치

에너지저장장치 동작은 여러 가지 제약조건에 의존한다. 첫째, 충전 손실과 방전 손실이 있다. 둘째, 완전 충전과 완전 방전은 에너지저장장치의 수명을 단축하므로 에너지저장장치의 용량에 상·하한선을 둔다. 셋째, 충·방전량은 전력기기의 출력에 제한된다. 제약조건들은 아래와 같다.

단, $LB$ : 에너지저장장치의 최소 저장량 [kWh],

$UB$ : 에너지저장장치의 최대 저장량 [kWh],

$soc_{i n i,\:k}$ : 에너지저장장치의 초기 저장량 [kWh],

$soc_{t,\:k}$ : $t$단계, $k$번째 시나리오의 저장량 [kWh],

$qc_{t,\:k}$ : $t$단계, $k$번째 시나리오의 충전량 [kW],

$qd_{t,\:k}$ : $t$단계, $k$번째 시나리오의 방전량 [kW],

$\eta^{c/d}$ : 에너지저장장치의 충전/방전 효율 [%],

$RR^{c/d}$ : 에너지저장장치의 최대 증발량/감발량 [kW].

에너지저장장치만을 이용하여 전력시장에 참가하므로, 임의의 시간 $t$에서의 구매 입찰량과 배터리의 충전량, 그리고 판매 입찰량과 배터리의 방전량은 각각 같아야 한다.

또한, 같은 시간에 판매 및 구매 입찰은 동시에 선택할 수 없으므로 판매 및 구매 입찰 중 하나는 반드시 0이 되어야 한다. 본 논문에서는 추가 비용 변수 $M$을 아래의 목적함수에 사용하여 시장 참가 세 번째 가정과 에너지저장장치의 동시 충·방전 제약을 한꺼번에 구현한다.

식(25)를 $f_{k}( x_{k})$로 갖는 식(14)를 목적함수로 하는 다단계 확률론적 계획법을 통해 입찰량을 선정한다. 모든 시나리오에 해당하는 다단계 확률론적 최적화 문제가 하나씩 존재하고, 각 문제의 최적해는 각 시간의 입찰량을 의미한다.

5.3 시나리오 작성

가격 시나리오는 예측 가격에 다양한 예측 오차를 중첩하여 구한다. 본 논문에서는 아래 표 2에 제시한 것처럼 현재의 값을 예측값으로 가정하는 방법인 연속 예측법을 통해 가격을 예측한 뒤, 예측 가격과 실제 가격 간의 비교를 통해 예측 오차를 구한다. 구해진 예측 오차의 평균과 분산을 가우시안 확률밀도함수를 기준으로 구하고, 구해진 평균과 분산을 기반으로 반복 난수 생성을 통해 예측 오차 표본들을 만든다.

그림 2에는 사례 연구에 사용된 2017년 계통한계가격에 연속 예측법을 적용해서 생성한 100,000개의 예측 오차 표본의 분포도가 있다. 예측 오차의 분포도를 다수의 구간으로 분리하여 각 범위에 속하는 표본의 수를 전체 표본의 수로 나누어 확률을 구한다. 최종적으로 예측 오차를 2017년 5월의 계통한계가격 예측값에 중첩하여, 예측 시나리오와 그것의 확률을 쌍으로 가지는 가격 시나리오를 만든다.

6.1 시뮬레이션 구조

다단계 확률론적 계획법의 수익성을 증명하기 위해 전력 가격의 두 가지 서로 다른 예측 정확도에 대해 각각 다단계 확률론적 최적화 방법과 결정론적 최적화 방법을 이용하여, 한 달 동안 한 시간 전 전력시장에서 차익거래를 한다. 이 과정에서 2단계와 4단계 계획법을 사용한다. 이때 실제 전력 가격이 사용된 경우에는 결정론적 2단계와 4단계 모델로 실험하고, 전력 가격이 예측된 경우에 대해 각각 아래의 4가지 모델로 실험을 한다.

1. [Model 1] 125개의 시나리오로 구성된 4단계 시나리오 나무를 이용한 4단계 확률론적 최적화 계획법 활용.

2. [Model 2] 1개의 시나리오를 이용한 4단계 결정론적 최적화 계획법 활용

3. [Model 3] 5개의 시나리오로 구성된 2단계 시나리오 나무를 이용한 2단계 확률론적 최적화 계획법 활용.

4. [Model 4] 1개의 시나리오를 이용한 2단계 결정론적 최적화 계획법 활용.

실험들은 다음과 같은 가정을 가진다. 에너지저장장치의 용량은 1MWh, 초기 에너지저장량은 전체 용량의 50%, 최대 방전 깊이(Depth of Discharge)는 80%, SOC 하한과 상한은 각각 배터리 용량의 10%와 90%, 시간당 최대 충·방전량은 모두 0.5MW로 가정한다. 최대 구매와 판매 입찰량은 최대 충·방전량과 같은 0.5MW로 가정하고, 충·방전 효율은 95%로 가정한다. 끝으로 에너지저장장치의 수명비용은 없다.

6.2 시뮬레이션 결과

본 절에서는 실제 전력 가격을 사용한 경우와 전력 가격을 예측한 경우에 대해서 각각 2가지, 4가지 모델에 대해 실험한다.

6.2.1 실제 전력 가격을 사용한 경우의 시뮬레이션

그림 3에는 하루 동안의 시간당 전력 가격이 나와 있고, 그림 4에는 같은 시간에서의 에너지저장장치의 동작이 나와 있다. 2시부터 7시까지는 가격 변동이 없다가 8시에 가격이 갑자기 올라간다. 2단계 모델과 4단계 모델 모두 해당 시간에 방전하였다. 하지만 2단계 모델은 7시에만 방전하는 반면 4단계 모델은 더 많은 후속 시간을 고려하여 5시에도 방전한다.

추가로 10시에서 13시까지 가격이 소폭 내려가다가 14시에 갑자기 내려간다. 이 가격에 대해서도 2단계 모델은 한 시간 앞까지만 고려하기 때문에 13시에 방전하지만, 4단계 모델은 세 시간 앞까지 고려하기 때문에 앞 시간을 모두 고려했을 때 가격이 가장 높은 10시에 방전한다.

표 3에는 2단계와 4단계 결정론적 모델의 한 달 수익이 적혀 있다. 4단계 모델이 2단계 모델보다 많은 후속 시간의 가격을 고려했기 때문에 한 달 동안 약 70.5% 더 많은 수익을 확보한다.

6.2.2 전력 가격을 예측한 경우의 시뮬레이션

두 번째 실험에서는 전력 가격을 예측한 후 한 시간 전 전력시장에서의 한 달 수익을 계산한다. 그림 5에는 모델별로 에너지저장장치의 동작들이 있고, 그림 6에는 대표일의 가격 시나리오가 그려져 있다. 2단계와 4단계 결정론적 모델에서는 연속 예측법을 이용해서 예측한 값을 시나리오로 사용한다. 확률론적 모델에서는 5장에서 설명한 방법을 통해 시나리오를 제작한다.

그림 5에서 에너지저장장치는 결정론적 계획법을 이용하면 주어진 가격 범위 안에서 충·방전 효율 95%로는 에너지저장장치가 수익을 낼 수 없으므로 동작을 하지 않는다. 반면 확률론적 계획법을 이용하면 최대한 최적 충·방전 계획을 수립하여 전력시장에 참가한다. 또한, 4단계 확률론적 모델이 2단계 확률론적 모델보다 더 많은 후속 동작을 고려함으로써 연속적으로 더 많은 양을 충·방전한다.

표 4에 각 모델의 한 달 수익이 있다. 4단계 확률론적 모델이 가장 많은 수익을 낸다. 2단계 결정론적 모델에서는 예측을 기반으로 1시간 뒤의 동작만을 고려하고 근시안적인 동작을 수행하여 가장 적은 음의 수익을 냈다. 4단계 결정론적 모델의 경우 2단계 결정론적 모델보다 더 많은 후속 시간을 고려하여 수익을 내지만 확률론적 모델들보다는 작다.

2단계와 4단계 확률론적 모델의 경우 4단계 결정론적 모델보다 약 4배의 수익을 냈고, 이 과정에서 4단계 확률론적 모델이 더 많은 시나리오에서 더 많은 후속 동작을 고려하여 2단계 확률론적 모델보다 약 1% 더 많은 수익을 낸다.

표 4에는 720시간에 대한 연산시간도 제시되어 있다. 4단계 확률론적 모델의 연산속도가 다른 모델에 비해 길지만, 720시간에 대한 시뮬레이션임을 고려한다면 상대적으로 짧은 연산시간이다. 점진적 회피 알고리즘은 복잡한 다단계 확률론적 최적화 문제를 병렬 연산을 통해 빠르게 풀기 때문에 연산속도가 문제 크기에 비례해서 많이 증가하지 않는다.