Algorithm. Solution Search Algorithm
[Visual Studio과 C#으로 구현/해 탐색 알고리즘]
Algorithm solution search Coding // Week13
2021202_20615034
[이론]
[백트래킹(Backtracking) 기법]
해를 찾는 도중에 ‘막히면’ (즉, 해가 아니면) 되돌아가서 다시 해를 찾아 가는 기법이다.
백트래킹 기법은 최적화(optimization) 문제와 결정 (decision) 문제를 해결한다.
- 결정 문제
문제의 조건을 만족하는 해가 존재하는 지의 여부를 ‘yes’ 또는 ‘no’로 답하는 문제
+ TSP를 위한 백트래킹 알고리즘
tour = [시작점]
tour는 점의 순서 (sequence)
bestSolution = (tour, ∞)
bestSolution은 현재까지 찾은 가장 거리가 짧은 해
2개의 성분 (tour, tour의 거리)으로 표시
tour는 점의 순서
tour의 거리는 ‘bestSolution의 거리’로 표현
초기에 tour는 시작점만 가지므로 그 거리는 가장 큰 상수로 초기화
>코드 알고리즘
tour = [시작점] // tour는 점의 순서
bestSolution = (tour, ∞)
BacktrackTSP(tour)
1. if tour가 완전한 해이면
2. if tour의 거리 < bestSolution의 거리
3. bestSolution = (tour, tour의 거리)
4. else
5. for tour를 확장 가능한 각 점 v에 대해서
6. newTour = tour + v // 기존 tour의 뒤에 v 를 추가
7. if newTour의 거리 < bestSolution의 거리
8. BacktrackTSP(newTour)
+ BacktrackTSP 알고리즘의 수행 과정
01. 시작점 A, tour=[A]이고, bestSolution=([A],∞)
02. BacktrackTSP(tour) 호출
>newTour = [A, B]
03. tour [A]를 확장할 수 있는 점은 B, C, D, E, 따라서 각 점에 대해 루프 수행
04. 먼저 점 B에 대해서
05. newTour = [A, B], newTour의 거리 = 2, 왜냐하면 간선 (A, B)의 가중치가 2이므로
06. BacktrackTSP([A, B]) 순환 호출
>newTour = [A, B, C]
07. tour [A, B]를 확장할 수 있는 점은 C, D, E, 따라서 각 점에 대해 루프 수행, 먼저 점 C에 대해서
08. newTour=[A, B, C], newTour의 거리 = 5, 왜냐하면 간선 (B,C)의 가중치가 3이므로
09. BacktrackTSP([A, B, C]) 순환 호출
>bestSolution=([A, B, C, D, E, A], 30)
10. 이와 같이 계속 탐색을 진행하면 첫 번째 완전한 해
bestSolution=([A, B, C, D, E, A], 30)
>bestSolution=([A, B, C, E, D, A], 18)
11. 첫 번째 완전한 해를 찾은 후, 더 짧은 해인 bestSolution=([A, B, C, E, D, A], 18)을 찾는다.
(그림 5)
>> 시간복잡도
Backtracking 알고리즘의 시간 복잡도는 상태 공간 트리의 노드 수에 비례
n개의 점이 있는 입력 그래프에 대해서 BacktrackTSP 알고리즘이 탐색하는 최대 크기의 상태 공간 트리
문제에 따라서 이진 트리 형태의 상태 공간 트리가 형성되기도 하는데 이때에도 최악의 경우에 2n개의 노드를 대부분 탐색해야 하므로 지수 시간이 걸림
이는 모든 경우를 다 검사하여 해를 찾는 완전 탐색 (Exhaustive Search)의 시간 복잡도와 같음
그러나 일반적으로 백트래킹 기법은 ‘가지치기’를 하므로 완전 탐색보다 훨씬 효율적임
[분기 한정 (Branch-and-Bound) 기법]
백트래킹 기법은 깊이 우선 탐색수행
최적화 문제에 대해서는 최적해가 상태 공간 트리의 어디에 있는지 알 수 없으므로, 트리에서 대부분의 노드를 탐색하여야 함
입력의 크기가 커지면 해를 찾는 것은 거의 불가능
분기 한정(Branch-and-bound) 기법은 이러한 단점을 보완하는 탐색 기법
분기 한정 기법은 상태 공간 트리의 각 노드(상태)에 특정한 값 (한정값)을 부여
노드의 한정값을 활용하여 가지치기를 함으로써 백트래킹 기법보다 빠르게 해를 찾는다.
분기 한정 기법에서는 가장 우수한 한정값을 가진 노드를 먼저 탐색하는 최선 우선 탐색(Best First Search)으로 해를 찾는다.
- 분기 한정 기법의 효율적인 탐색 원리
최적해를 찾은 후에 나머지 노드의 한정값이 최적해의 값과 같거나 나쁘면 더 이상 탐색하지 않는다.
상태 공간 트리의 대부분의 노드가 문제의 조건에 맞지 않아서 해가 되지 못한다.
최적해가 있을 만한 영역을 먼저 탐색한다.
>코드 알고리즘
Branch-and-Bound(S) // S는 문제의 초기 상태
1. 상태 S의 한정값을 계산한다.
2. activeNodes = { S } // 탐색되어야 하는 상태의 집합
3. bestValue = ∞ // 현재까지 탐색된 해 중의 최솟값
4. while ( activeNodes ≠ ∅ ) {
5. Smin= activeNodes의 상태 중에서 한정값이
가장 작은 상태
6. Smin을 activeNodes에서 제거
7. Smin의 자식(확장 가능한) 노드 S1, S2, ..., Sk를
생성하고, 각각의 한정값을 계산한다.
8. for i=1 to k // 확장한 각 자식 Si에 대해서
9. if Si의 한정값 ≥ bestValue
10. Si를 가지치기한다. // 더 우수한 해가 없으므로
11. else if Si가 완전한 해이고 Si의 값 < bestValue
12. bestValue = Si의 값
13. bestSolution = Si
14. else
15. Si를 activeNodes에 추가
+TSP
분기 한정 기법으로 문제의 최적해를 찾으려면, 먼저 각 상태에서의 한정값을 계산하여야
- 한정값 계산을 위한 여행자 문제의 조건
문제의 해는 주어진 시작점에서 출발하여 모든 다른 점을 1번씩만 방문하고 시작점으로 돌아와야 한다.
- 경로 상의 1개의 점 x를 살펴보면, 다른 점에서 점 x로 들어온 후에 점 x를 떠나 또 다른 점으로 나간다. 이를 점 x의 한정값 계산에 활용
+ TSP의 한정값 계산 방법
TSP에서 임의의 점 x에서의 한정값 = 시작점부터 점 x까지의 경로 길이 + 점 x를 떠나서 남은 다른 점들을 1번씩만 방문하고 시작점으로 돌아오는 경로의 ‘예측’ 길이
여행자 문제는 최단 경로를 찾는 문제이므로 앞으로 방문해야 할 각 점 x에 연결된 간선 중에서 가장 짧은 두 간선의 가중치의 평균의 합을 예측 길이를 계산하는데 사용
가중치의 합을 1/2로 곱하는
(평균을 내는) 이유는 한 점에서 나가는 간선은 인접한(다른) 점에서 들어오는 간선과 동일하므로 단, 소수점 이하의 숫자는 올림.
- 점에 인접한 간선 중에서 2개의 가장 작은 가중치
가중치 3인 간선으로 들어와서 가중치 2인 간선으로 나가든지 (왼쪽 그림)
반대로 가중치 2인 간선으로 들어와서 가중치 3인 간선으로 나가든지 (오른쪽 그림)
두 경우 모두 최소의 비용으로 점을 방문한다.
(그림 8)
+ Branch-and-Bound 알고리즘 수행 과정
5개의 점(A, B, C, D, E)으로 된 그래프
초기 상태= [A]
Branch-and-Bound([A]) 호출
[유전자 알고리즘]
(Genetic Algorithm, GA)
다윈의 진화론으로부터 창안된 해 탐색 알고리즘
‘적자생존’의 개념을 최적화 문제를 해결하는데 적용
- GA 사이클
- 코드 알고리즘
1. 초기 후보해 집합 G0을 생성
2. G0의 각 후보해를 평가
3. t = 0
4. repeat
5. Gt로부터 Gt+1을 생성
6. Gt+1의 각 후보해를 평가
7. t = t + 1
8. until 종료 조건이 만족될 때까지
9. return Gt의 후보해 중에서 가장 우수한 해
여러 개의 해를 임의로 생성하여 이들을 초기 세대 (generation) G0로 놓고
repeat-루프에서 현재 세대의 해로부터 다음 세대의 해를 생성해가며,
루프가 끝났을 때의 마지막 세대에서 가장 우수한 해를 반환
이 해들은 repeat-루프의 반복적인 수행을 통해서 최적해 또는 최적해에 근접한 해가 될 수 있으므로 후보해 (candidate solution)라고 부른다.
- 후보해
TSP: 5개의 도시 (A, B, C, D, E), 시작 도시 = A
TSP는 시작 도시에서 출발하여 모든 다른 도시를 1번씩만 방문하고 시작 도시로 돌아와야 하므로, ABCDEA, ACDEBA, AECDBA 등이 후보해
- 후보해의 수
시작 도시를 제외한 4개의 도시를 일렬로 나열하는 방법의 수: (5-1)! = 4! = 24
n개의 도시의 후보해 수 = (n-1)!
- 후보해의 평가
ABCDEA의 값 =
(A와 B 사이의 거리)
+ (B와 C 사이의 거리)
+ (C와 D 사이의 거리)
+ (D와 E 사이의 거리)
+ (E와 A 사이의 거리)
= 5 + 2 + 1 + 3 + 9
= 20
- 적합도
후보해의 값 = 후보해의 적합도(Fitness value)
후보해 중에서 최적해의 값에 근접한 적합도를 가진 후보해를 ‘우수한’ 해라고 부른다.
+ GA 연산
선택 (selection) 연산
교차 (crossover) 연산
돌연변이 (mutation) 연산
[모의 담금질 기법]
모의 담금질(Simulated Annealing) 기법은 높은 온도에서 액체 상태인 물질이 온도가 점차 낮아지면서 결정체로 변하는 과정을 모방한 해 탐색 알고리즘
용융 상태에서는 물질의 분자가 자유로이 움직이는데 이를 모방하여, 해를 탐색하는 과정도 특정한 패턴 없이 이루어진다.
온도가 점점 낮아지면 분자의 움직임이 점점 줄어들어 결정체가 되는데, 해 탐색 과정도 이와 유사하게 점점 더 규칙적인 방식으로 이루어진다.
- 이웃해
이러한 방식으로 해를 탐색하려면, 후보해에 대해 이웃하는 해 (이웃해)를 정의하여야
아래의 오른쪽 그림에서 각 점은 후보해이고 아래쪽에 위치한 해가 위쪽에 있는 해보다 우수한 해이다. 또한 2개의 후보해 사이의 화살표는 이 후보해들이 서로 이웃하는 관계임을 나타낸다.
- 탐색 과정
높은 T에서의 초기 탐색은 최솟값을 찾는데도 불구하고 확률 개념을 도입하여 현재 해의 이웃해 중에서 현재 해보다 ‘나쁜’ 해로 (위 방향으로) 이동하는 자유로움을 보일 수도 있다.
T가 낮아지면서 점차 탐색은 아래 방향으로 향한다.
T가 낮아질수록 위 방향으로 이동하는 확률이 점차 작아진다.
그림에서 처음 도착한 골짜기 (지역 최적해, local optimum)에서 더 이상 아래로 탐색할 수 없는 상태에 이르렀을 때 ‘운 좋게’ 위 방향으로 탐색하다가 전역 최적해 (global optimum)를 찾은 것을 보여준다.
- 모의 담금질 기법의 특성
유전자 알고리즘과 마찬가지로 모의 담금질 기법도 항상 전역 최적해를 찾아준다는 보장은 없다.
모의 담금질 기법의 또 하나의 특징은 하나의 초기 해로부터 탐색이 진행된다는 것이다. 반면에 유전자 알고리즘은 여러 개의 후보해를 한 세대로 하여 탐색을 수행
>코드 알고리즘
1. 임의의 후보해 s를 선택
2. 초기 T를 정한다.
3. repeat
4. for i = 1 to kT // kT는 T에서의 for-루프 반복 횟수
5. s의 이웃해 중에서 랜덤하게 하나의 해 s'를 선택
6. d = (s'의 값) - (s의 값)
7. if d < 0 // 이웃해인 s'가 더 우수한 경우
8. s ← s'
9. else // s'가 s보다 우수하지 않은 경우
10. q ← (0,1) 사이에서 랜덤하게 선택한 수
11. if ( q < p ) s ← s' // p는 자유롭게 탐색할 확률
12. T ← T // 1보다 작은 상수 를 T에 곱하여 새로운 T를 계산
13. until 종료 조건이 만족될 때까지
14. return s
+ TSP의 이웃 해 정의 3가지 예
삽입 (Insertion)
교환 (Switching)
반전 (Inversion)
++
반도체 회로 설계
유전자 배열
단백질 구조 연구
경영 분야의 재고 계획
원자재 조달
상품의 생산 및 유통
운송 분야의 스케줄링
건축 분야의 빌딩 구획 및 배치 (Building Layout)
항공기 디자인
복합 물질 모델링
금융 분야의 은행의 재무 분석 등 매우 광범위하게 활용
[요약]
백트래킹 (Backtracking) 기법은 해를 찾는 도중에 ‘막히면’ 되돌아가서 다시 해를 찾아 가는 기법으로 상태 공간 트리에서 깊이 우선 탐색 (Depth First Search)으로 해를 찾는 알고리즘
백트래킹 기법의 시간 복잡도는 상태 공간 트리의 노드 수에 비례하고, 이는 모든 경우를 다 검사하여 해를 찾는 완전 탐색의 시간 복잡도와 같다. 그러나 일반적으로 백트래킹 기법은 ‘가지치기’하므로 완전 탐색보다 훨씬 효율적이다.
분기 한정 기법은 상태 공간 트리의 각 노드(상태)에 특정한 값(한정값)을 부여하고, 노드의 한정값을 활용하여 가지치기를 함으로서 백트래킹 기법보다 빠르게 해를 찾는다.
분기 한정 기법에서는 가장 우수한 한정값을 가진 노드를 먼저 탐색하는 최선 우선 탐색 (Best First Search)으로 해를 찾는다.
유전자 알고리즘은 다윈의 진화론으로부터 고안된 해 탐색 알고리즘이다. ‘적자생존’ 개념을 최적화 문제를 해결하는데 적용한 것이다.
유전자 알고리즘은 여러 개의 해를 임의로 생성하여 이들에 대해 선택, 교차, 돌연변이 연산을 반복 수행하여 마지막에 가장 우수한 해를 리턴
유전자 알고리즘은 문제의 최적해를 알 수 없고, 기존의 어느 알고리즘으로도 해결하기 어려운 경우에, 최적해에 가까운 해를 찾는데 매우 적절한 알고리즘
모의 담금질 (Simulated Annealing) 알고리즘은 높은 온도에서 액체 상태인 물질이 온도가 점차 낮아지면서 결정체로 변하는 과정을 모방한 해 탐색 알고리즘
유전자 알고리즘과 마찬가지로 모의 담금질 기법도 항상 전역 최적해를 찾아준다는 보장은 없다.
댓글 없음:
댓글 쓰기