Differential Evolution Algorithm

지토의 개발일기/논문리뷰

Differential Evolution Algorithm

지아토 2024. 12. 20. 14:27

Differentail Evolution (차분진화알고리즘) 이란?

차분 진화 알고리즘은 진화 알고리즘의 한 종류로, 주로 '적자생존;의 개념에서 영감을 받아 개발되었다. 진화 알고리즘은 교차, 돌연변이 및 선택과 같은 다양한 유전적 연산을 활용하여 우수한 성질을 가진 새로운 후손 솔루션을 생성한다. 차분 진화 알고리즘은 복잡한 최적화 문제를 풀기에 인기 있는 최적화 문제 해결 방법의 하나로 주목받고 있다. 차분 진화 알고리즘은 진화 알고리즘(EA)의 영역에 속하며 다양한 최적화 문제를 해결하기 위해 사용되는 모집단 기반 방법을 사용한다. 차분 진화 알고리즘은 여러 가지 경쟁력 있는 장점 덕분에 연구 자와 실무자들사이에서 널리 사용되고 있다.

첫 번째는 차분 진화 알고리즘의 구현은 다른 메타 휴리스틱 알고리즘보다 간단하고 직관적이다. 이는 프로그래밍에 익숙하지 않은 실무자들도 쉽게 사용할 수 있게 한다.

두 번째는 차분 진화 알고리즘은 비선형성, 다모달성 및 비분리성과 같은 특징을 가진 문제에 대해서도 다른 메타 휴리스틱 알고리즘보다 유용하게 사용할 수 있다.

세 번째는 차분 진화 알고리즘은 도전적인 최적화 문제에서 잘 수행될 수 있다. 공간 복잡성이 낮고, 대규모 및 계산 비용이 많이 드는 최적화 문제에 대하 일부 메타 휴리스틱 알고리즘 보다 더 나은 확장성을 가지고 있다.

3. Differentail Evolution(DE)의 기본원리

DE는 다음과 같은 원리로 작동한다.

1. 초기화(Initizalization):

● 초기 후보 해 (popluation)를 무작위로 생성한다. 각 후보 해는 D차원의 벡터로 표현된다.

● 각 객체에 대해 목적 함수의 값을 계산한다.

2. 변이(Mutation)

● 각 후보 해에 대해, 세 개의 다른 후보해를 무작위로 선택한다. 변이 벡터는 다음과 같이 계산된다.

F는 변이 인자 (mutation factor)로 일반적으로 [0,2]사이의 값을 가진다.

● 각 개체의 해에 무작위 변화를 주고, 이를 통해 새로운 후보 해를 생성한다.

3. 교차(Crossover)

● 변이 벡터와 현재 후보 해를 사용하여 자식 벡터를 생성한다 이는 교차 확률 CR을 사용하여 결정된다.

여기서 j = 1,2,... D, randj(0,1)은 [0,1]사이의 균일 난수 j rand는 무작위로 선택된 인덱스이다.

4. 평가(Evaluation)

● 새로운 후보 해의 성능을 평가하고 목적 함수의 값을 계산한다.

5. 선택(Selection)

자식 벡터와 부모 벡터를 비교하여 더 좋은 적합도(Fitness)를 가진 벡터를 다음 세대에 선택한다.

● 선택된 개체들이 다음 세대로 전파된다.

6. 반복(Iteration)

● 위 단계들을 여러 번 반복하여 최적의 해를 찾을 때까지 탐색을 진행한다.

7. 종료 조건 확인(Termination Condition Check)

● 수렴 기준이 충족되는지 확인한다. 예를 들어 최대 반복 횟수에 도달하거나 적합도의 변화가 미미할 때 종료된다.

여기서 앱실론은 수렴 허용 오차이다.

8. 종료(Termination)

● 종료 조건이 충족되면 알고리즘을 종료하고 최적해를 반환한다.

처음에는 해를 생성하고, 변이 및 교차를 통해 새로운 후보 해를 생성, 그 후 후보 해의 평가와 선택을 반복하여 최적해를 찾을 때까지 반복되며종료 조건을 만족하면 알고리즘이 종료되는 흐름으로 진행된다. 차분 진화 알고리즘 FlowChart는 다음과 같다.