미분진화

2D Ackley 기능을 최적화하는 Differential Evolution.

진화적 계산에서, 차분 진화(DE)는 주어진 품질의 척도와 관련하여 후보 솔루션을 개선하려고 반복적으로 시도함으로써 문제를 최적화하는 방법이다. 이러한 방법은 최적화되는 문제에 대해 거의 또는 전혀 가정을 하지 않으며 매우 넓은 범위의 후보 솔루션을 검색할 수 있기 때문에 일반적으로 메타휴리스틱스라고 알려져 있다. 그러나 DE와 같은 메타휴리스틱스는 최적의 해결책이 발견된다고 보장하지는 않는다.

DE는 다차원 실제 가치 함수에 사용되지만 최적화되는 문제의 구배는 사용하지 않으며, 이는 DE가 구배 강하 및 준 뉴턴 방법과 같은 고전적 최적화 방법에서 요구하는 바와 같이 최적화 문제를 차별화할 필요가 없다는 것을 의미한다. 따라서 DE는 연속적이지도 않고, 소음이 심하며, 시간에 따른 변화 등 최적화 문제에도 사용할 수 있다.^[1]

DE는 간단한 공식에 따라 후보 솔루션을 모집단을 유지하고 기존 솔루션을 조합하여 새로운 후보 솔루션을 만든 다음, 어느 후보 솔루션이 가장 높은 점수나 최적화 문제에 적합한지 파악하여 문제를 최적화한다. 이러한 방식으로 최적화 문제는 후보 솔루션에서 주어진 품질의 척도만 제공하는 블랙박스로 취급되며 따라서 구배는 필요하지 않다.

DE는 1990년대에 Storn과 Price에 의해 소개되었다.^[2]^[3] 병렬 컴퓨팅에 DE를 사용하는 이론적·실용적 측면, 다목적적 최적화, 제약적 최적화에 관한 책들이 출판되어 왔으며, 또한 그 책들에는 응용 분야에 대한 조사도 수록되어 있다.^[4]^[5]^[6]^[7] DE의 다면적인 연구 측면에 대한 조사는 저널 기사에서 찾을 수 있다.^[8]^[9]

알고리즘

DE 알고리즘의 기본 변형은 후보 솔루션 모집단(에이전트라고 함)을 갖는 것으로 작동한다. 이러한 요원들은 모집단의 기존 요원의 위치를 결합하기 위해 간단한 수학 공식을 사용하여 검색 공간에서 이동한다. 만약 대리인의 새로운 위치가 개선된다면, 그것은 받아들여지고 인구의 일부를 형성한다. 그렇지 않으면, 새로운 직위는 그냥 버려진다. 그 과정은 반복되며, 그렇게 함으로써 만족스러운 해결책이 결국 발견되기를 바라지만 보장되지는 않는다.

형식적으로 $f:\mathbb {R} ^{n}\to \mathbb {R}$ : $f:\mathbb {R} ^{n}\to \mathbb {R}$ n $f:\mathbb {R} ^{n}\to \mathbb {R}$ → $f:\mathbb {R} ^{n}\to \mathbb {R}$ ${\$ 을(를) 최소화해야 하는 피트니스 기능이 되도록 $f:\mathbb {R} ^{n}\to \mathbb {R}$ 한다(대신 $h:=-f$ $h:=-f$ $h:=-f$ - $h:=-f$ ${\displaysty h:=-f}$ 함수를 고려하여 최대화를 수행할 수 있음). 함수는 후보 솔루션을 실제 숫자의 벡터 형태로 논쟁으로 삼고, 주어진 후보 솔루션의 적합성을 나타내는 출력으로 실수를 산출한다. $f$ $f$ 의 그라데이션은 알 수 없다 $f$ . The goal is to find a solution $\mathbf {m}$ for which $f(\mathbf {m} )\leq f(\mathbf {p} )$ for all $\mathbf {p}$ in the search-space, which means that $\mathbf {m}$ is the global minimum.

$\mathbf {x} \in \mathbb {R} ^{n}$ $\mathbf {x} \in \mathbb {R} ^{n}$ $\mathbf {x} \in \mathbb {R} ^{n}$ $\mathbf {x} \in \mathbb {R} ^{n}$ ${\$ ^{ $n}}}$ 을(를) 모집단에 후보 솔루션(에이전트)을 지정하도록 $\mathbf {x} \in \mathbb {R} ^{n}$ 한다. 기본 DE 알고리즘은 다음과 같이 설명할 수 있다.

${\text{NP}}\geq 4$ ${\text{NP}}\geq 4$ ${\text{NP}}\geq 4$ ${\displaystyle {\text{$ $NP}}\geq 4$ ${\text{CR}}\in [0,1]$ ${\text{CR}}\in [0,1]$ [ ${\text{CR}}\in [0,1]$ ${\text{CR}}\in [0,1]$ ${\text{CR}}\in [0,1]$ ${\displaystyle {\$ { $CR}\in [0,1]$ 및 F $F\in [0,2]$ [ $F\in [0,2]$ $F\in [0,2]$ $F\in [0,2]$ ${\displaystyle F\in [0,2$
- ${\$ $NP}}$ 은(는) 모집단 크기(예: 후보 에이전트 또는 "부모"의 수입니다. 일반적인 ${\text{NP}}$ 설정은 $10n$ $n$ 입니다 $n$
- 파라미터 ${\text{CR}}\in [0,1]$ ${\text{CR}}\in [0,1]$ [ 0 ${\text{CR}}\in [0,1]$ , ${\text{CR}}\in [0,1]$ ${\text{CR}}\in [0,1]$ ${\displaystyle {\text{$ $CR}\in [0,1]}$ 을(를) 교차 확률이라고 하고 ${\text{CR}}\in [0,1]$ , F $F\in [0,2]$ $F\in [0,2]$ 0 $F\in [0,2]$ $F\in [0,2]$ $F\in [0,2]$ $F\in [0,2]$ 을(를) 미분중량이라고 한다 $F\in [0,2]$ . 일반적인 설정은 $F=0.8$ = $F=0.8$ $F=0.8$ 이고 $F=0.8$ $CR=0.9$ $CR=0.9$ = $CR=0.9$ $CR=0.9$ 입니다 $CR=0.9$
- 최적화 성능은 이러한 선택의 영향을 크게 받을 수 있다. 아래를 참조하십시오.
검색 공간의 임의 위치를 사용하여 모든 $\mathbf {x}$ 에이전트 $\mathbf {x}$ ${\$ 를) 초기화하십시오.
종료 기준이 충족될 때까지(예: 수행된 반복 횟수 또는 적절한 체력에 도달할 때까지) 다음을 반복하십시오.
- 모집단의 $\mathbf {x}$ 각 에이전트 $\mathbf {x}$ ${\$ 에 대해 다음 작업을 수행하십시오.
  - Pick three agents $\mathbf {a} ,\mathbf {b}$ , and $\mathbf {c}$ from the population at random, they must be distinct from each other as well as from agent $\mathbf {x}$ . ( $\mathbf {a}$ is called the "base" vector.)
  - $R\in \{1,\ldots ,n\}$ 인덱스 $R\in \{1,\ldots ,n\}$ 1 $R\in \{1,\ldots ,n\}$ , $R\in \{1,\ldots ,n\}$ … $R\in \{1,\ldots ,n\}$ , n $R\in \{1,\ldots ,n\}$ $R\in \{1,\ldots ,n\$ 을(를) 선택하십시오. 여기서 $R\in \{1,\ldots ,n\}$ $n$ ${\displaystyn}$ 은 $n$ (는) 최적화 중인 문제의 차원성이다.
  - 에이전트의 잠재적으로 새로운 위치 $\mathbf {y} =[y_{1},\ldots ,y_{n}]$ = $\mathbf {y} =[y_{1},\ldots ,y_{n}]$ [ $\mathbf {y} =[y_{1},\ldots ,y_{n}]$ 1 $\mathbf {y} =[y_{1},\ldots ,y_{n}]$ , $\mathbf {y} =[y_{1},\ldots ,y_{n}]$ … , $\mathbf {y} =[y_{1},\ldots ,y_{n}]$ $]$ {\ $displaystyle \mathbf$ {y} =[ $y_{1},\ldots$ , $y_{n$ }]}을(를) 다음과 $\mathbf {y} =[y_{1},\ldots ,y_{n}]$ 같이 계산하십시오.
    - 각 $i\in \{1,\ldots ,n\}$ … $i\in \{1,\ldots ,n\}$ , $i\in \{1,\ldots ,n\}$ $i\in \{1,\ldots ,n\}$ ${\displaystyle$ i $\in \{1,\ldots ,n\}}$ 에 대해 균일하게 분포된 임의 번호 $r_{i}\sim U(0,1)$ i ~ $r_{i}\sim U(0,1)$ U ( $r_{i}\sim U(0,1)$ ) ${\displaystyle r_{i}\sim$ U $(0,1$ )를 선택하십시오 $.$
    - $r_{i}<CR$ r $r_{i}<CR$ < $r_{i}<CR$ $r_{i}<CR$ ${\displaystyle r_{i}<$ 인 경우 $i=R$ $}$ 또는 $r_{i}<CR$ $i=R$ = R ${\displaystyle$ i $=R}$ 을 $i = R$ (를) 설정한 다음 $y_{i}=a_{i}+F\times (b_{i}-c_{i})$ = $y_{i}=a_{i}+F\times (b_{i}-c_{i})$ + $y_{i}=a_{i}+F\times (b_{i}-c_{i})$ $y_{i}=a_{i}+F\times (b_{i}-c_{i})$ ( $y_{i}=a_{i}+F\times (b_{i}-c_{i})$ - $y_{i}=a_{i}+F\times (b_{i}-c_{i})$ $y_{i}=a_{i}+F\times (b_{i}-c_{i})$ ) ${\displaystyle y_{i}=a_{i}++$ $F\times(b_{i}-c_{i}}$ 을(를) 다르게 $y_{i}=a_{i}+F\times (b_{i}-c_{i})$ $y_{i}=x_{i}$ 하지 않으면 y $y_{i}=x_{i}$ = $y_{i}=x_{i}$ $y_{i}=x_{i}$ ${\$ (인덱스 $위치$ R ${\displaysty R}$ 은(확정적으로 교체됨 $R$ )
  - $f(\mathbf {y} )\leq f(\mathbf {x} )$ ( $f(\mathbf {y} )\leq f(\mathbf {x} )$ ) $f(\mathbf {y} )\leq f(\mathbf {x} )$ $f(\mathbf {y} )\leq f(\mathbf {x} )$ ( x $f(\mathbf {y} )\leq f(\mathbf {x} )$ ) ${\displaystyle$ f $(\mathbf {y} )\leq$ f $(\mathbf$ ${x$ $} )$ 인 경우 $f(\mathbf {y} )\leq f(\mathbf {x} )$ , 개체군에서 $\mathbf {x}$ $\mathbf {x}$ x ${\\$ $\mathbf$ {x $}$ 을(를 $)$ 개선되거나 동일한 후보 솔루션 $\mathbf {y}$ ${\$ y로 교체하십시오 $\mathbf {y}$
가장 적합성이 높은 모집단에서 에이전트를 선택하고 가장 적합한 후보 솔루션으로 반환하십시오.

파라미터 선택

두 DE 매개변수

{\text{NP}}

{\

을(를) 변경할 때 Speare 및 Rosenbrok 벤치마크 문제에 대해 기본 DE가 총체적으로 어떻게 수행되는지 보여주는 성능 풍경

{\text{F}}

}}

및 F

{\text{NP}}

{\

F

고정

{\text{CR}}

{\

CR}}

{\text{CR}}

0.9.

DE 매개 변수 ${\text{NP}}$ ${\$ $NP$ ${\text{CR}}$ ${\$ $CR}}$ 및 ${\text{CR}}$ F {\ $디스플레이$ 스타일F}은 $($ 는) 최적화 성능에 큰 영향을 미칠 수 있다 $F$ . 따라서 좋은 성과를 내는 DE 매개변수를 선택하는 것은 많은 연구의 대상이 되었다. 매개변수 선택을 위한 엄지손가락 규칙은 스턴 외 ^[3]^[4]연구원과 류와 램피넨이 고안했다.^[10] 매개변수 선택과 관련된 수학 수렴 분석은 자하리에가 수행했다.^[11]

변형

DE 알고리즘의 변형은 최적화 성능을 향상시키기 위한 노력으로 지속적으로 개발되고 있다. 위에 주어진 기본 알고리즘에서 에이전트 교차 및 돌연변이를 수행하기 위한 여러 가지 다른 방법이 가능하다(예: 참조).^[3]

참고 항목

참조

^ Rocca, P.; Oliveri, G.; Massa, A. (2011). "Differential Evolution as Applied to Electromagnetics". IEEE Antennas and Propagation Magazine. 53 (1): 38–49. doi:10.1109/MAP.2011.5773566. S2CID 27555808.
^ Storn, R.; Price, K. (1997). "Differential evolution - a simple and efficient heuristic for global optimization over continuous spaces". Journal of Global Optimization. 11 (4): 341–359. doi:10.1023/A:1008202821328. S2CID 5297867.
^ ^a ^b ^c Storn, R. (1996). "On the usage of differential evolution for function optimization". Biennial Conference of the North American Fuzzy Information Processing Society (NAFIPS). pp. 519–523. doi:10.1109/NAFIPS.1996.534789. S2CID 16576915.
^ ^a ^b Price, K.; Storn, R.M.; Lampinen, J.A. (2005). Differential Evolution: A Practical Approach to Global Optimization. Springer. ISBN 978-3-540-20950-8.
^ Feoktistov, V. (2006). Differential Evolution: In Search of Solutions. Springer. ISBN 978-0-387-36895-5.
^ G. C. 온우볼루와 B V 바부,
^ Chakraborty, U.K., ed. (2008), Advances in Differential Evolution, Springer, ISBN 978-3-540-68827-3
^ S. Das와 P. N. Sugantan, "Different Evolution: 진화적 계산에 관한 최신" IEEE 트랜스.의 조사, 15권, 1권, 4-31부, 2011년 2월, DOI: 10.1109/TEVC.2010.2059031.
^ S. Das, S. S. Mullick, P. N. Sugantan, "최근의 차등 진화 발전 - 업데이트된 조사", 군집 및 진화 연산, doi:10.1016/j.swevo.2016.01.004, 2016.004.
^ Liu, J.; Lampinen, J. (2002). "On setting the control parameter of the differential evolution method". Proceedings of the 8th International Conference on Soft Computing (MENDEL). Brno, Czech Republic. pp. 11–18.
^ Zaharie, D. (2002). "Critical values for the control parameters of differential evolution algorithms". Proceedings of the 8th International Conference on Soft Computing (MENDEL). Brno, Czech Republic. pp. 62–67.
^ Zervoudakis, Konstantinos; Tsafarakis, Stelios (2020). "A mayfly optimization algorithm". Computers & Industrial Engineering. ahead-of-print (ahead-of-print): head-of-print. doi:10.1016/j.cie.2020.106559.

[elediadereview-1] Rocca, P.; Oliveri, G.; Massa, A. (2011). "Differential Evolution as Applied to Electromagnetics". IEEE Antennas and Propagation Magazine. 53 (1): 38–49. doi:10.1109/MAP.2011.5773566. S2CID 27555808.

[storn97differential-2] Storn, R.; Price, K. (1997). "Differential evolution - a simple and efficient heuristic for global optimization over continuous spaces". Journal of Global Optimization. 11 (4): 341–359. doi:10.1023/A:1008202821328. S2CID 5297867.

[storn96usage-3] Storn, R. (1996). "On the usage of differential evolution for function optimization". Biennial Conference of the North American Fuzzy Information Processing Society (NAFIPS). pp. 519–523. doi:10.1109/NAFIPS.1996.534789. S2CID 16576915.

[price05differential-4] Price, K.; Storn, R.M.; Lampinen, J.A. (2005). Differential Evolution: A Practical Approach to Global Optimization. Springer. ISBN 978-3-540-20950-8.

[feoktistov06differential-5] Feoktistov, V. (2006). Differential Evolution: In Search of Solutions. Springer. ISBN 978-0-387-36895-5.

[6] G. C. 온우볼루와 B V 바부,

[chakraborty08advances-7] Chakraborty, U.K., ed. (2008), Advances in Differential Evolution, Springer, ISBN 978-3-540-68827-3

[8] S. Das와 P. N. Sugantan, "Different Evolution: 진화적 계산에 관한 최신" IEEE 트랜스.의 조사, 15권, 1권, 4-31부, 2011년 2월, DOI: 10.1109/TEVC.2010.2059031.

[9] S. Das, S. S. Mullick, P. N. Sugantan, "최근의 차등 진화 발전 - 업데이트된 조사", 군집 및 진화 연산, doi:10.1016/j.swevo.2016.01.004, 2016.004.

[liu02setting-10] Liu, J.; Lampinen, J. (2002). "On setting the control parameter of the differential evolution method". Proceedings of the 8th International Conference on Soft Computing (MENDEL). Brno, Czech Republic. pp. 11–18.

[zaharie02critical-11] Zaharie, D. (2002). "Critical values for the control parameters of differential evolution algorithms". Proceedings of the 8th International Conference on Soft Computing (MENDEL). Brno, Czech Republic. pp. 62–67.

[12] Zervoudakis, Konstantinos; Tsafarakis, Stelios (2020). "A mayfly optimization algorithm". Computers & Industrial Engineering. ahead-of-print (ahead-of-print): head-of-print. doi:10.1016/j.cie.2020.106559.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

Search

미분진화

네임스페이스

더

목차

알고리즘

파라미터 선택

변형

참고 항목

참조