차분 진화

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 알고리즘
3. 제약 조건 처리
4. 변형 알고리즘
5. 샘플 코드
참조

1. 개요

차분 진화(DE)는 후보해 집단을 유지하며 작동하는 최적화 알고리즘이다. DE는 모집단 내 기존 해를 결합하는 수학적 공식을 사용하여 검색 공간을 이동시키며, 개선된 해는 수용되고 그렇지 않은 해는 폐기된다. 이 과정은 종료 조건이 충족될 때까지 반복된다. DE는 모집단 크기, 교차 확률, 차등 가중치 등의 매개변수를 가지며, 제약 조건 처리 및 다양한 변형 알고리즘이 존재한다.

더 읽어볼만한 페이지

진화 알고리즘 - 입자 군집 최적화
입자 군집 최적화는 입자들의 군집을 통해 최적해를 찾는 계산 지능 기반 알고리즘으로, 각 입자는 자신의 최적 위치와 군집 전체의 최적 위치를 활용해 속도와 위치를 업데이트하며 최적해를 탐색한다.
진화 알고리즘 - 유전 알고리즘
유전 알고리즘은 생물 진화 과정을 모방하여 최적해를 탐색하는 계산 최적화 기법으로, 해를 유전자로 표현하고 적합도 함수를 통해 평가하며 선택, 교차, 돌연변이 연산을 반복하여 최적해에 근접하는 해를 생성하며, 성능은 매개변수에 영향을 받고 초기 수렴 문제 해결을 위한 다양한 변형 기법과 관련 기법이 존재한다.

차분 진화
개요
상세 정보
주요 논문

2. 알고리즘

DE 알고리즘은 후보 솔루션(에이전트) 집단을 이용하여 최적해를 찾는다. 각 에이전트는 모집단 내 다른 에이전트들의 위치를 결합하는 간단한 수학적 공식을 통해 검색 공간 내에서 이동한다. 새로운 위치가 이전 위치보다 개선된 경우, 에이전트는 새로운 위치로 갱신되며, 그렇지 않으면 이전 위치를 유지한다. 이 과정은 반복적으로 수행되며, 이를 통해 최적해에 근접해 간다.

최소화해야 할 적합성 함수를 $f: \mathbb{R}^n \to \mathbb{R}$ 라고 할 때, 목표는 모든 $\mathbf{p}$ 에 대해 $f(\mathbf{m}) \leq f(\mathbf{p})$ 인 전역 최소값 $\mathbf{m}$ 을 찾는 것이다.

기본 DE 알고리즘은 다음과 같은 단계를 거친다.

1. 매개변수 설정: 모집단 크기 ( $\text{NP} \geq 4$ ), 교차 확률 ( $\text{CR} \in [0,1]$ ), 차등 가중치 ( $F \in [0,2]$ )를 선택한다.

2. 초기화: 검색 공간에서 모든 에이전트 $\mathbf{x}$ 를 무작위 위치로 초기화한다.

3. 반복: 종료 기준(예: 반복 횟수, 적합성 도달)이 충족될 때까지 다음을 반복한다.

모집단의 각 에이전트 $\mathbf{x}$ 에 대해:
모집단에서 임의로 세 에이전트 $\mathbf{a}, \mathbf{b}, \mathbf{c}$ 를 선택한다. 이들은 서로 달라야 하며, $\mathbf{x}$ 와도 달라야 한다.
임의의 인덱스 $R \in \{1, \ldots, n\}$ 를 선택한다. ( $n$ 은 최적화 문제의 차원)
잠재적 새 위치 $\mathbf{y} = [y_1, \ldots, y_n]$ 를 계산한다. 각 $i$ 에 대해:
균등 분포 난수 $r_i \sim U(0,1)$ 를 선택한다.
$r_i < \text{CR}$ 또는 $i = R$ 이면 $y_i = a_i + F \times (b_i - c_i)$ 로 설정하고, 그렇지 않으면 $y_i = x_i$ 로 설정한다.
$f(\mathbf{y}) \leq f(\mathbf{x})$ 이면, 모집단의 에이전트 $\mathbf{x}$ 를 $\mathbf{y}$ 로 바꾼다.

4. 결과: 모집단에서 가장 적합한 에이전트를 최적해로 반환한다.

2. 1. 기본 원리

차분 진화(DE) 알고리즘은 후보해(에이전트) 집단을 이용하여 최적해를 찾는다. 각 에이전트는 모집단 내 다른 에이전트들의 위치를 결합하는 간단한 수학적 공식을 통해 검색 공간 내에서 이동한다. 새로운 위치가 이전 위치보다 개선된 경우, 에이전트는 새로운 위치로 갱신되며, 그렇지 않으면 이전 위치를 유지한다. 이 과정은 반복적으로 수행되며, 이를 통해 최적해에 근접해 간다.

최소화해야 할 적합성 함수를

f: \mathbb{R}^n \to \mathbb{R}

라고 할 때, 목표는 모든

\mathbf{p}

에 대해

f(\mathbf{m}) \leq f(\mathbf{p})

인 전역 최소값

\mathbf{m}

을 찾는 것이다.

기본 DE 알고리즘은 다음과 같은 단계를 거친다.

1. 매개변수 설정: 모집단 크기 (

\text{NP} \geq 4

), 교차 확률 (

\text{CR} \in [0,1]

), 차등 가중치 (

F \in [0,2]

)를 선택한다.

2. 초기화: 검색 공간에서 모든 에이전트

\mathbf{x}

를 무작위 위치로 초기화한다.

3. 반복: 종료 기준(예: 반복 횟수, 적합성 도달)이 충족될 때까지 다음을 반복한다.

모집단의 각 에이전트 $\mathbf{x}$ 에 대해:
모집단에서 임의로 세 에이전트 $\mathbf{a}, \mathbf{b}, \mathbf{c}$ 를 선택한다. 이들은 서로 달라야 하며, $\mathbf{x}$ 와도 달라야 한다.
임의의 인덱스 $R \in \{1, \ldots, n\}$ 를 선택한다. ( $n$ 은 최적화 문제의 차원)
잠재적 새 위치 $\mathbf{y} = [y_1, \ldots, y_n]$ 를 계산한다. 각 $i$ 에 대해:
균등 분포 난수 $r_i \sim U(0,1)$ 를 선택한다.
$r_i < \text{CR}$ 또는 $i = R$ 이면 $y_i = a_i + F \times (b_i - c_i)$ 로 설정하고, 그렇지 않으면 $y_i = x_i$ 로 설정한다.
$f(\mathbf{y}) \leq f(\mathbf{x})$ 이면, 모집단의 에이전트 $\mathbf{x}$ 를 $\mathbf{y}$ 로 바꾼다.

4. 결과: 모집단에서 가장 적합한 에이전트를 최적해로 반환한다.

2. 2. 작동 단계

DE 알고리즘은 후보 솔루션(에이전트) 집단을 이용하여 최적해를 찾는다. 이 에이전트들은 간단한 수학 공식을 통해 탐색 공간 내에서 이동하며, 더 나은 위치가 발견되면 해당 위치로 업데이트된다. 이 과정은 반복적으로 수행되며, 최종적으로 만족스러운 해를 찾는 것을 목표로 한다.
작동 단계:1. 초기화:

매개변수 $\text{NP} \geq 4$ (모집단 크기), $\text{CR} \in [0,1]$ (교차 확률), $F \in [0,2]$ (차등 가중치)를 선택한다.
일반적으로 $\text{NP}$ 는 10 $n$ ( $n$ 은 문제의 차원), $\text{CR}$ 은 0.9, $F$ 는 0.8로 설정한다.
탐색 공간 내에서 모든 에이전트 $\mathbf{x}$ 를 무작위 위치에 초기화한다.

2. 반복: 종료 기준(예: 최대 반복 횟수, 목표 적합도 도달)을 만족할 때까지 다음 단계를 반복한다.

모집단의 각 에이전트 $\mathbf{x}$ 에 대해 다음을 수행한다.

1. 돌연변이:

모집단에서 서로 다른 세 에이전트 $\mathbf{a}$ , $\mathbf{b}$ , $\mathbf{c}$ 를 무작위로 선택한다. 이들은 $\mathbf{x}$ 와도 달라야 한다.
$\mathbf{a}$ 는 "기본" 벡터라고도 불린다.
임의의 인덱스 $R \in \{1, \ldots, n\}$ ( $n$ 은 최적화 문제의 차원)을 선택한다.

2. 교차:

각 $i \in \{1,\ldots,n\}$ 에 대해, 균등 분포에서 난수 $r_i \sim U(0,1)$ 를 생성한다.
만약 $r_i < \text{CR}$ 이거나 $i = R$ 이면, $y_i = a_i + F \times (b_i - c_i)$ 로 설정한다. 그렇지 않으면 $y_i = x_i$ 로 설정한다.

3. 선택:

새로운 위치 $\mathbf{y}$ 의 적합도 $f(\mathbf{y})$ 를 계산한다.
만약 $f(\mathbf{y}) \leq f(\mathbf{x})$ 이면, 모집단에서 에이전트 $\mathbf{x}$ 를 $\mathbf{y}$ 로 교체한다.

3. 결과: 모집단에서 가장 적합한 에이전트를 최적해로 반환한다.

2. 3. 매개변수

DE 알고리즘의 성능에 큰 영향을 미치는 주요 매개변수는 다음과 같다.

매개변수	설명	일반적인 값	역할
NP (모집단 크기)	후보 솔루션 (에이전트)의 수	10 $n$ (문제 차원의 10배)	값이 클수록 탐색 능력이 향상되지만, 계산 비용이 증가한다.
CR (교차율)	돌연변이 벡터와 대상 벡터를 결합하여 자손 벡터를 생성할 때, 돌연변이 벡터의 요소를 상속받을 확률	0.9	값이 클수록 다양한 자손 벡터가 생성되어 탐색 능력이 향상될 수 있다.
F (차등 가중치)	돌연변이 벡터 생성 시, 두 벡터 간 차이에 곱해지는 가중치	0.8	값이 클수록 탐색 공간을 더 넓게 탐색할 수 있지만, 수렴 속도가 느려질 수 있다.

이러한 매개변수들의 선택은 최적화 성능에 큰 영향을 미칠 수 있다. 따라서 주어진 문제에 적합한 매개변수를 선택하는 것이 중요하다.
매개변수 선택 전략다음은 다양한 연구에서 제안된 DE 매개변수 선택 전략이다.

경험 법칙: Storn 등은 경험에 기반한 매개변수 선택 규칙을 제안했다.
수렴 분석: Zaharie는 매개변수 선택과 관련된 수학적 수렴 분석을 수행했다.

3. 제약 조건 처리

차분 진화는 제약 최적화에도 활용될 수 있다.

일반적인 방법은 제약 위반에 대한 페널티를 포함하도록 목표 함수를 수정하는 것이다. 이는 다음과 같이 표현된다: $f\tilde(x) = f(x) + \rho \times \mathrm (x)$ . 여기서 $\mathrm (x)$ 는 제약 위반 (L1 페널티) 또는 제약 위반의 제곱 (L2 페널티)을 나타낸다.

그러나 이 방법에는 몇 가지 단점이 있다. 한 가지 중요한 문제는 페널티 계수 $\rho$ 를 적절하게 선택하는 것이다. $\rho$ 가 너무 낮게 설정되면 제약을 효과적으로 적용하지 못할 수 있다. 반대로 너무 높게 설정하면 수렴 속도가 크게 느려지거나 심지어 중단될 수도 있다. 이러한 어려움에도 불구하고, 이 접근 방식은 단순하고 차분 진화 알고리즘 자체를 변경할 필요가 없기 때문에 널리 사용된다.

가능한 집합으로 투영하거나 차원을 줄이는 것과 같은 대안적인 전략이 있으며, 이는 상자 제약 또는 선형 제약의 경우에 사용될 수 있다. 그러나 일반적인 비선형 제약의 경우, 가장 신뢰할 수 있는 방법은 일반적으로 페널티 함수를 사용하는 것이다.

4. 변형 알고리즘

DE 알고리즘의 최적화 성능을 향상시키기 위해 다양한 변형 알고리즘들이 지속적으로 개발되고 있다.^[5] 다음과 같은 개발 방향을 제시할 수 있다.

에이전트의 교차 및 돌연변이를 수행하기 위한 새로운 방식.
제약 조건을 처리하기 위한 다양한 전략
모집단 크기, F 및 CR 매개변수를 동적으로 조정하는 적응형 전략
대규모 최적화를 위한 특수 알고리즘
다중 목표 및 다중 목표 알고리즘
이진/정수 변수를 처리하기 위한 기술

최적화 성능을 개선하기 위해, 기본 알고리즘에서 교차 및 에이전트의 변이 방법을 변경한 많은 DE 아종(亞種)이 개발되었다.^[8]

5. 샘플 코드

java

// 모집단의 개별 개체를 정의한다.

class Individual {

// 차분 진화는 일반적으로 부동 소수점 변수를 사용한다.

float data1, data2;

// 정수를 사용하는 것도 가능하다.

int data3;

}

public class DifferentialEvolution {

// 변수

// 모집단을 포함하는 연결 리스트

LinkedList population = new LinkedList();

// Random number generator의 새 인스턴스

Random random = new Random();

int PopulationSize = 20;

// 차등 가중치 [0,2]

float F = 1;

// 교차 확률 [0,1]

float CR = 0.5;

// 문제의 차원, 즉 문제가 갖는 변수의 수이다. 이 경우 3 (data1, data2, data3)

int N = 3;

// 이 함수는 주어진 개체가 주어진 문제에서 얼마나 잘 수행하는지를 알려준다.

public float fitnessFunction(Individual in) {

...

return fitness;

}

// 이 함수는 프로그램의 주요 기능이다.

public void Main() {

// 균일한 무작위 노이즈로 초기화된 개체로 모집단을 초기화한다.

// 균일한 노이즈는 검색 공간 내의 무작위 값이다.

int i = 0;

while (i < populationSize) {

Individual individual = new Individual();

individual.data1 = random.UniformNoise();

individual.data2 = random.UniformNoise();

// 정수는 부동 소수점 값을 사용할 수 없으며 반올림해야 한다.

individual.data3 = Math.floor(random.UniformNoise());

population.add(individual);

i++;

}

i = 0;

int j;

// 진화의 메인 루프.

while (!StoppingCriteria) {

i++;

j = 0;

while (j < populationSize) {

// 새로운 후보 솔루션 계산

// 모집단에서 임의의 지점을 선택

int x = Math.floor(random.UniformNoise() % (population.size() - 1));

int a, b, c;

// 모집단에서 세 개의 다른 임의의 지점을 선택

do {

a = Math.floor(random.UniformNoise() % (population.size() - 1));

} while (a == x);

do {

b = Math.floor(random.UniformNoise() % (population.size() - 1));

} while (b == x | b == a);

do {

c = Math.floor(random.UniformNoise() % (population.size() - 1));

} while (c == x | c == a | c == b);

// 임의의 인덱스 [0-Dimensionality]를 선택한다.

int R = rand.nextInt() % N;

// 에이전트의 새로운 위치 계산

Individual original = population.get(x);

Individual candidate = original.clone();

Individual individual1 = population.get(a);

Individual individual2 = population.get(b);

Individual individual3 = population.get(c);

//if(i==R | i
//candidate=a+f*(b-c)

//else

//candidate=x

if (0 == R | random.UniformNoise() % 1 < CR) {

candidate.data1 = individual1.data1 + F * (individual2.data1 - individual3.data1);

} // else는 원본을 후보로 복제했기 때문에 필요하지 않다.

if (1 == R | random.UniformNoise() % 1 < CR) {

candidate.data2 = individual1.data2 + F * (individual2.data2 - individual3.data2);

}

// 정수는 부동 소수점과 동일하게 작동하지만 반올림해야 한다.

if (2 == R | random.UniformNoise() % 1 < CR) {

candidate.data3 = Math.floor(individual1.data3 + F * (individual2.data3 - individual3.data3));

}

// 원본보다 나은지 확인하고, 그렇다면 교체한다.

if (fitnessFunction(original) < fitnessFunction(candidate)) {

population.remove(original);

population.add(candidate);

}

j++;

}

}

// 최상의 후보 솔루션 찾기

i = 0;

Individual bestFitness = new Individual();

while (i < populationSize) {

Individual individual = population.get(i);

if (fitnessFunction(bestFitness) < fitnessFunction(individual)) {

bestFitness = individual;

}

i++;

}

// 솔루션

return bestFitness;

}

}

참조

_[1] 학술지 Differential evolution—a simple and efficient scheme for global optimization over continuous spaces https://cse.engineer[...] 2024-04-03
_[2] 서적 New Optimization Techniques in Engineering https://www.springer[...] 2016-09-17
_[3] 간행물 Differential Evolution: A Survey of the State-of-the-Art https://www.research[...] 2011-02
_[4] 간행물 Recent Advances in Differential Evolution - An Updated Survey http://web.mysites.n[...] 2016
_[5] 서적 Recent advances in differential evolution 2016
_[6] 학술지 Differential Evolution as Applied to Electromagnetics
_[7] 학술지 Differential evolution - a simple and efficient heuristic for global optimization over continuous spaces
_[8] 학회자료 On the usage of differential evolution for function optimization
_[9] 서적 Differential Evolution: A Practical Approach to Global Optimization http://www.springer.[...] Springer
_[10] 서적 Differential Evolution: In Search of Solutions http://www.springer.[...] Springer
_[11] 웹사이트 New Optimization Techniques in Engineering http://www.springer.[...] 2016-09-17
_[12] 서적 Advances in Differential Evolution http://www.springer.[...] Springer
_[13] 학술지 Differential Evolution: A Survey of the State-of-the-art
_[14] 학술지 Recent Advances in Differential Evolution - An Updated Survey
_[15] 학회자료 On setting the control parameter of the differential evolution method
_[16] 학회자료 Critical values for the control parameters of differential evolution algorithms
_[17] PhD thesis Tuning & Simplifying Heuristical Optimization http://www.hvass-lab[...] University of Southampton, School of Engineering Sciences, Computational Engineering and Design Group
_[18] 학술지 Good parameters for differential evolution http://www.hvass-lab[...] Hvass Laboratories
_[19] 학회자료 A Minimax Fitting Algorithm for Ultra-Precision Aspheric Surfaces
_[20] 학술지 Transforming geocentric cartesian coordinates to geodetic coordinates by using differential search algorithm

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com