🇺🇸 USC 빅데이터 컨퍼런스 참가기🇺🇸 | [USC AI/DS] Lesson 4. Informed Search와 A* 알고리즘

Lesson 3에서는 BFS, DFS, Uniform Cost Search와 같은
기본적인 Search Algorithm에 대해 정리했다.

이번 Lesson 4에서는 여기에서 한 단계 더 나아가
Informed Search를 다룬다.

말 그대로

목표에 대한 추가적인 정보를 가지고 탐색하는 방법

이다.

이번 단원에서도 Greedy Search와 같은 내용은
코딩테스트를 준비하면서 어느 정도 접해본 내용들이라 비교적 익숙했다.

다만 단순히

Greedy = 지금 가장 좋아 보이는 것을 선택한다.

정도로 알고 있었는데,

이번 강의에서는 이를 Heuristic, Best-First Search, 그리고 A* Search까지 연결해서 설명했다.

특히 A* Search는 예전에 알고리즘 수업에서도 이름만 몇 번 들어봤는데,
이번에는

왜 Greedy Search보다 안정적인지
왜 최적해를 찾을 수 있는지
Heuristic은 어떤 조건을 만족해야 하는지

까지 조금 더 자세히 이해할 수 있었다.

그리고 후반부에는

Local Search
Hill Climbing
Simulated Annealing
Local Beam Search
Genetic Algorithm
Gradient Descent / Ascent

까지 다루면서

탐색이라는 개념이 단순한 그래프 경로 탐색을 넘어 최적화 문제까지 연결될 수 있다.

는 것을 보여준다.

---

Uninformed Search와 Informed Search

먼저 이전 Lesson에서 다뤘던 알고리즘을 생각해보자.

BFS
DFS
Uniform Cost Search

이 알고리즘들은 기본적으로
문제에서 주어진 정보만 가지고 탐색한다.

예를 들어 BFS라면

가장 얕은 Node부터 탐색

하고,

Uniform Cost Search라면

현재까지의 Path Cost가 가장 작은 Node부터 탐색

한다.

그런데 실제로 우리가 목적지에 대한 정보를 조금이라도 알고 있다면 어떨까?

예를 들어 서울에서 부산까지 운전한다고 해보자.

모든 도로를 하나하나 탐색하는 것보다

"부산은 대략 남동쪽에 있다."

라는 정보라도 가지고 있는 편이 훨씬 유리하다.

이러한 추가적인 정보를 탐색에 사용하는 것이
Informed Search다.

---

Best-First Search

강의에서는 먼저 Best-First Search라는 큰 개념부터 설명한다.

핵심 아이디어는 간단하다.

각 Node에 대해

이 Node가 얼마나 좋아 보이는가?

를 평가하는 함수를 만든다.

이것을 Evaluation Function이라고 한다.

그리고 Frontier에 있는 Node 중

가장 좋아 보이는 Node

를 먼저 탐색한다.

즉,

Frontier
↓
각 Node의 Evaluation Value 계산
↓
가장 좋은 Node 선택
↓
Expand

하는 방식이다.

Best-First Search의 대표적인 두 가지 형태가 바로

Greedy Search
A* Search

다.

---

Greedy Search

먼저 Greedy Search다.

Greedy라는 단어 그대로

현재 순간 가장 좋아 보이는 선택을 한다.

라는 아이디어다.

코딩테스트에서도 상당히 자주 등장하는 방법이다.

예를 들어 동전을 최소 개수로 사용해서 금액을 만든다고 할 때
특정 조건에서는 가장 큰 동전부터 선택하는 방식이 Greedy가 될 수 있다.

500원
100원
50원
10원

이 있다고 하면

가장 큰 동전부터 사용

하는 방식이다.

Search Problem에서는 조금 다르게 표현한다.

---

Heuristic이란?

Greedy Search에서는 Heuristic Function이라는 것을 사용한다.

보통

h(n)

이라고 표현한다.

h(n)은

현재 Node n에서 Goal까지 얼마나 비용이 들 것 같은지 추정한 값

이다.

중요한 점은 실제 비용이 아니라 추정값이라는 것이다.

예를 들어 전주에서 서울까지 간다고 생각해보자.

실제 도로를 따라 이동하는 거리는

약 200km

일 수 있지만,

지도에서 직선거리만 계산하면

약 170km

가 나올 수 있다.

이 직선거리를

h(n)

으로 사용할 수 있다.

---

Romania 예제

강의에서는 이전 Lesson에서도 사용했던
루마니아 도시 문제를 다시 사용한다.

목표는

Arad
↓
Bucharest

로 이동하는 것이다.

이번에는 각 도시에서 Bucharest까지의
Straight-Line Distance, 즉 직선거리를 추가적으로 알고 있다고 가정한다.

예를 들어

Arad → Bucharest 직선거리 = 366

Sibiu → Bucharest 직선거리 = 253

Timisoara → Bucharest 직선거리 = 329

Zerind → Bucharest 직선거리 = 374

같은 정보가 있다.

Arad에서 갈 수 있는 곳이

Sibiu
Timisoara
Zerind

라면 Greedy Search는

h(Sibiu) = 253
h(Timisoara) = 329
h(Zerind) = 374

를 비교한다.

그리고 가장 작은 값인

Sibiu

를 선택한다.

왜냐하면

"현재 기준으로 Bucharest에 가장 가까워 보이는 도시"

이기 때문이다.

---

Greedy Search의 핵심

Greedy Search는 오직

h(n)

만 본다.

즉,

지금까지 얼마나 왔는가?

는 크게 신경 쓰지 않고

앞으로 Goal까지 얼마나 남았는가?

만 본다.

그래서 평가 함수는 다음과 같다.

f(n) = h(n)

라고 생각할 수 있다.

이 방식의 장점은 분명하다.

Heuristic이 좋다면
쓸데없는 Node를 탐색하지 않고 Goal 방향으로 빠르게 갈 수 있다.

하지만 문제가 있다.

---

Greedy는 항상 최적일까?

아니다.

Greedy Search는 현재 순간의 선택만 보기 때문에
전체 경로가 최적이라는 보장이 없다.

예를 들어

Start
├── A → Goal
└── B → C → Goal

이라는 경로가 있다고 해보자.

A가 Goal에 훨씬 가까워 보인다고 해서
반드시

Start → A → Goal

의 실제 비용이 작은 것은 아니다.

A로 가는 Edge Cost가 엄청나게 클 수도 있다.

즉,

Goal과 가까워 보인다
≠
전체 비용이 작다

이다.

또한 반복 State를 제대로 처리하지 않는다면
Loop에 빠질 수도 있다.

강의에서도 Greedy Search는 일반적으로

Complete X
Optimal X

라고 설명한다.

다만 finite state space에서 repeated-state checking을 한다면
Completeness를 확보할 수 있다.

---

그렇다면 지금까지 온 거리도 같이 보면 되지 않을까?

여기에서 A* Search가 등장한다.

Lesson 3에서 다뤘던 Uniform Cost Search는

g(n)

을 사용했다.

g(n)은

Start Node에서 현재 Node까지 실제로 사용한 비용

이다.

반면 Greedy Search는

h(n)

을 사용했다.

g(n)
= 지금까지 실제로 사용한 비용

h(n)
= 앞으로 Goal까지 필요할 것으로 예상되는 비용

그렇다면 두 개를 더하면 어떨까?

f(n) = g(n) + h(n)

바로 이것이 A* Search의 핵심이다.

---

A* Search

A* Search는

Uniform Cost Search
+
Greedy Search

의 아이디어를 합친 알고리즘이라고 볼 수 있다.

강의에서도 다음과 같이 설명한다.

Uniform Cost Search
→ backward cost g(n)

Greedy Search
→ forward cost h(n)

A*
→ g(n) + h(n)

즉 A*의 평가 함수는

f(n) = g(n) + h(n)

이다.

각각의 의미는 다음과 같다.

g(n)
= Start에서 n까지 실제로 사용한 비용

h(n)
= n에서 Goal까지 예상되는 비용

f(n)
= n을 거쳐 Goal까지 갈 것으로 예상되는 전체 비용

---

간단한 예시로 이해해보자

자동차 내비게이션을 생각하면 꽤 이해하기 쉽다.

현재까지

전주 → 대전

으로 100km를 이동했다고 하자.

그리고 대전에서 서울까지 남은 거리를
약 150km라고 추정한다면

g(n) = 100
h(n) = 150

이므로

f(n) = 250

이다.

반면 다른 경로에서는

g(n) = 150
h(n) = 80

일 수도 있다.

그러면

f(n) = 230

이다.

A*는 이 둘 중

230

인 경로를 먼저 탐색한다.

즉,

이미 사용한 비용과 앞으로 사용할 것 같은 비용을 동시에 고려한다.

---

A*가 Greedy보다 좋은 이유

Greedy Search는

h(n)

만 본다.

따라서 목표에 가까워 보인다는 이유만으로
매우 비싼 경로를 선택할 수도 있다.

A*는

g(n) + h(n)

을 보기 때문에

앞으로 얼마나 남았는가?
+
지금까지 얼마나 썼는가?

를 모두 고려한다.

개인적으로 이 부분을 보고

"A*는 Greedy를 조금 더 현실적으로 만든 알고리즘이구나."

라고 이해했다.

---

A*는 Goal을 발견하면 바로 끝날까?

여기서 중요한 주의점이 하나 있다.

A*에서는 Goal Node를 Frontier에 넣었다고 바로 종료하면 안 된다.

즉,

Goal을 Enqueue
→ 종료 X

이다.

Goal이 Frontier에서 실제로

Dequeue

될 때 종료해야 한다.

왜냐하면 Goal을 처음 발견했더라도
Frontier 안에 더 작은 f(n) 값을 가진 다른 Node가 존재할 수 있기 때문이다.

그 다른 경로를 통해

더 작은 실제 비용으로 Goal

에 도달할 가능성이 있다.

강의의 Romania 예제에서도
Bucharest가 처음 Frontier에 등장한 시점보다

Pitesti

의 f(n) 값이 더 작아서 Pitesti를 먼저 탐색한다.

결국 Pitesti를 거쳐가는 경로가
더 저렴한 Bucharest 경로를 만들어낸다.

---

A*에서 가장 중요한 것은 Heuristic이다

여기까지 들으면 한 가지 의문이 생긴다.

h(n)

은 그냥 내가 아무렇게나 추정해도 되는가?

그렇지 않다.

A*가 최적해를 보장하기 위해서는
Heuristic이 특정 조건을 만족해야 한다.

이를 Admissible Heuristic이라고 한다.

---

Admissible Heuristic

실제 n에서 Goal까지의 최소 비용을

h*(n)

이라고 하자.

A*에서 사용하는 Heuristic h(n)은

h(n) ≤ h*(n)

을 만족해야 한다.

쉽게 말하면

실제 비용보다 크게 추정하면 안 된다.

라는 것이다.

이를 강의에서는

optimistic

하다고 표현한다.

조금 낙관적으로 보는 것이다.

---

왜 비용을 크게 잡으면 안 될까?

예를 들어 실제 Goal까지의 거리가

10

인데

h(n) = 100

이라고 해버렸다고 하자.

그러면 A*는 이 경로를

너무 비싼 경로

라고 판단해 탐색하지 않을 수 있다.

그런데 실제로는 그 경로가 최적 경로일 수도 있다.

즉 Heuristic이 실제 비용을 과대평가하면

좋은 경로를 미리 버릴 수 있다.

그래서 A*에서 사용하는 Heuristic은

실제 비용 이하

여야 한다.

---

직선거리가 좋은 Heuristic인 이유

Romania 예제에서 사용했던

Straight-Line Distance

는 좋은 예다.

두 도시 사이를 실제 도로로 이동하면
보통 직선거리보다 짧아질 수 없다.

즉,

직선거리 ≤ 실제 도로거리

이다.

따라서 Bucharest까지의 직선거리를 h(n)으로 사용하면
실제 비용을 과대평가하지 않는다.

그래서 Admissible Heuristic이 된다.

---

8-Puzzle의 Heuristic

강의에서는 8-Puzzle을 이용해서
두 가지 Heuristic을 소개한다.

Lesson 3에서도 나왔던 퍼즐이다.

현재 퍼즐
↓
타일 이동
↓
Goal State

여기에서 대표적인 Heuristic이 두 가지 있다.

---

h1 : 잘못 놓인 타일의 개수

첫 번째는

h1(n)
= 목표 위치에 있지 않은 Tile의 개수

다.

예를 들어 8개의 Tile 중
6개가 잘못된 위치에 있다면

h1(n) = 6

이다.

각 Tile은 최소 한 번은 움직여야 제자리로 돌아갈 수 있으므로
이 값은 실제 비용을 넘지 않는다.

따라서 Admissible하다.

---

h2 : Manhattan Distance

두 번째는 Manhattan Distance다.

각 Tile이 현재 위치에서
자신의 목표 위치까지 이동해야 하는

가로 칸 수 + 세로 칸 수

를 계산한다.

예를 들어 한 Tile이

오른쪽 2칸
아래 3칸

을 이동해야 한다면

Manhattan Distance = 5

이다.

그리고 모든 Tile의 Manhattan Distance를 합한다.

강의 예제에서는

h2(S) = 14

가 나온다.

---

어떤 Heuristic이 더 좋은가?

둘 다 Admissible하다고 해서
성능이 똑같은 것은 아니다.

강의에서는 Dominance라는 개념을 설명한다.

만약 모든 Node에 대해

h2(n) ≥ h1(n)

이고 두 Heuristic 모두 Admissible이라면

h2가 h1을 dominate한다.

고 한다.

왜 더 큰 값이 좋은 걸까?

단,

실제 비용을 넘지 않는 범위

에서는 Goal까지의 실제 비용을 더 정확하게 추정하기 때문이다.

즉,

너무 작게 추정하는 Heuristic

보다

실제 비용에 최대한 가깝게 추정하는 Heuristic

이 탐색할 Node를 더 많이 줄일 수 있다.

강의의 8-Puzzle 예제에서도 Manhattan Distance를 사용했을 때
잘못 놓인 Tile 개수를 사용하는 것보다 탐색 Node 수가 크게 감소한다.

---

좋은 Heuristic은 Search Cost를 크게 줄인다

이 부분이 꽤 인상적이었다.

Heuristic이 조금만 좋아져도
탐색해야 하는 Node의 개수가 엄청나게 달라질 수 있다.

결국 A*의 성능은

A* 알고리즘 자체

뿐만 아니라

얼마나 좋은 h(n)을 만들 수 있는가?

에 크게 좌우된다.

즉,

A*를 잘 쓰는 핵심은 결국 문제에 적합한 Heuristic을 설계하는 것이다.

---

여러 Heuristic을 합칠 수도 있다

만약 두 개의 Admissible Heuristic

ha(n)
hb(n)

이 있다면

h(n) = max(ha(n), hb(n))

으로 사용할 수도 있다.

둘 모두 실제 비용을 넘지 않는다면
그중 큰 값을 사용하더라도 여전히 실제 비용을 넘지 않는다.

따라서 새로운 h(n)도 Admissible하다.

그리고 기존 두 Heuristic보다
더 실제 값에 가까운 추정치를 사용할 가능성이 높다.

---

Relaxed Problem

그렇다면 좋은 Heuristic은 어떻게 만들까?

강의에서는 한 가지 중요한 방법으로
Relaxed Problem을 소개한다.

원래 문제의 조건을 조금 완화한 문제를 만드는 것이다.

예를 들어 8-Puzzle에서는 실제로 Tile이 움직일 수 있는 방법에 제약이 있다.

그런데

Tile이 아무 위치로 이동할 수 있다.

고 조건을 완화하면 문제는 훨씬 쉬워진다.

이 Relaxed Problem에서 구한 최적 비용은
원래 문제의 최적 비용보다 클 수 없다.

Relaxed Problem Cost
≤
Original Problem Cost

따라서 Relaxed Problem의 정확한 Solution Cost를
원래 문제의 Heuristic으로 사용할 수 있다.

---

TSP에서도 활용할 수 있다

강의에서는 Travelling Salesperson Problem, 즉 TSP도 예로 든다.

TSP는

모든 도시를 한 번씩 방문하면서 총 이동 거리를 최소화하는 문제

다.

굉장히 어려운 최적화 문제다.

하지만 문제의 조건을 완화해서
Minimum Spanning Tree를 계산하면

실제 TSP Tour의 비용보다 작은 Lower Bound

를 얻을 수 있다.

이 값을 Heuristic으로 활용할 수 있다.

---

A* Search의 특징

강의 자료에서 A*의 특징을 정리하면

Complete: Yes

Optimal: Yes

이다.

물론 앞에서 설명한 것처럼
적절한 Heuristic 조건이 필요하다.

또한 A*는 같은 Heuristic을 사용하는 Optimal Search Algorithm 중
필요 이상으로 많은 Node를 확장하지 않는다는 의미에서
Optimally Efficient하다고 설명한다.

다만 문제가 있다.

---

A*의 가장 큰 단점, Memory

A*는 Frontier와 탐색한 Node들을 계속 저장한다.

그래서 상태 공간이 매우 커지면

Memory

가 큰 문제가 된다.

Heuristic이 좋아지면 탐색 Node 수를 크게 줄일 수 있지만,
문제가 충분히 크다면 A* 역시 많은 Memory를 요구한다.

즉,

좋은 Heuristic
→ 탐색량 감소

하지만
→ 모든 문제가 갑자기 쉬워지는 것은 아니다.

---

A*는 어디에 사용될까?

강의에서는 A*의 활용 분야도 여러 개 소개했다.

대표적으로

Video Game
Path Finding
Routing
Resource Planning
Robot Motion Planning
Language Analysis
Machine Translation
Speech Recognition

등이다.

개인적으로 가장 익숙한 것은 역시 게임의 Path Finding이다.

NPC가 장애물을 피해 목적지까지 이동해야 하는 상황에서

현재 위치
↓
A*
↓
목적지까지 효율적인 경로

를 계산할 수 있다.

---

이제 경로 자체가 중요하지 않은 문제를 생각해보자

여기부터 강의가 조금 다른 방향으로 넘어간다.

지금까지는

Start
↓
...
↓
Goal

이라는 경로가 중요했다.

그런데 어떤 최적화 문제에서는
경로가 별로 중요하지 않다.

중요한 것은

최종 상태 자체

다.

예를 들어 TSP에서는

어떤 과정을 거쳐 이 Tour를 만들었는가?

보다

최종 Tour의 길이가 얼마인가?

가 중요하다.

이러한 문제를 해결하기 위해
Local Search를 사용할 수 있다.

---

Local Search

Local Search는 현재 State에서 시작해서

주변의 Neighbor State

를 탐색한다.

하지만 기존 Graph Search와 달리
지나온 경로를 모두 저장하지 않는다.

현재 State
↓
Neighbor 평가
↓
더 좋은 State로 이동
↓
다시 Neighbor 평가

를 반복한다.

쉽게 말하면

현재 답을 조금씩 수정하면서 더 좋은 답을 만들어가는 방식

이다.

---

TSP를 Local Search로 풀어보자

예를 들어 아무 Tour 하나를 만든다.

A → B → C → D → E → A

그리고 두 경로를 서로 바꿔본다.

현재 Tour
↓
일부 Edge 교환
↓
새로운 Tour

새로운 Tour의 비용이 더 작다면
그 상태를 채택한다.

이러한 과정을 반복하면
점점 더 좋은 Solution으로 이동할 수 있다.

---

n-Queens

Local Search의 또 다른 대표 예제가
n-Queens Problem이다.

체스판 위에 n개의 Queen을 놓는데

같은 Row X
같은 Column X
같은 Diagonal X

가 되도록 해야 한다.

여기에서 Heuristic을

서로 공격 가능한 Queen Pair의 수

라고 정의할 수 있다.

예를 들어

h = 5

라면 충돌이 5개 있다는 뜻이고,

Queen을 하나 이동해서

h = 2

로 만든다.

계속 줄여서

h = 0

이 되면 Solution이다.

---

Hill Climbing

이 아이디어를 가장 단순하게 구현한 것이
Hill Climbing이다.

강의의 표현이 재미있었다.

"Like climbing Everest in thick fog with amnesia"

안개가 자욱한 에베레스트에서
주변만 보면서 더 높은 곳으로 계속 올라가는 것과 같다.

현재 위치에서 주변을 본다.

현재보다 좋은 Neighbor가 있는가?

있다면 이동한다.

현재 State
↓
가장 좋은 Neighbor
↓
이동
↓
반복

더 좋은 Neighbor가 없다면 종료한다.

---

Hill Climbing의 문제

문제는 우리가 도착한 곳이
진짜 최고의 지점이라는 보장이 없다는 것이다.

예를 들어

        Global Maximum
           /\
          /  \
    /\   /    \
   /  \_/      \
Local Maximum

같은 공간이 있다고 해보자.

Hill Climbing은 Local Maximum에 도착하면

주변에 더 좋은 곳이 없음

이라고 판단하고 종료할 수 있다.

하지만 멀리 떨어진 곳에는
더 좋은 Global Maximum이 있을 수도 있다.

---

Random Restart

이 문제를 완화하기 위한 간단한 방법은

다른 위치에서 다시 시작

하는 것이다.

이를 Random-Restart Hill Climbing이라고 한다.

Random Start
↓
Hill Climbing

Random Start
↓
Hill Climbing

Random Start
↓
Hill Climbing

을 반복하면서 더 좋은 Solution을 찾는다.

---

Simulated Annealing

Local Maximum 문제를 해결하기 위한
더 재미있는 방법도 있다.

바로 Simulated Annealing이다.

핵심 아이디어는

가끔은 일부러 더 나쁜 선택도 허용하자.

이다.

Hill Climbing은 항상

좋아지는 방향

으로만 이동한다.

그런데 그러면 Local Optimum을 빠져나오기 어렵다.

Simulated Annealing은 경우에 따라

나쁜 상태

로도 이동할 수 있게 한다.

---

왜 일부러 나쁜 선택을 할까?

예를 들어 현재 Local Minimum에 갇혀 있다고 해보자.

     Global Minimum
        \        /
         \      /
      ___ \____/
     /
Local Minimum

Global Minimum으로 가려면
일시적으로 더 높은 비용의 상태를 지나야 할 수도 있다.

Hill Climbing / Descending은 이를 허용하지 않는다.

하지만 Simulated Annealing은 일정 확률로

일시적으로 더 나쁜 상태

를 받아들인다.

그래서 Local Optimum을 빠져나갈 가능성이 생긴다.

---

Temperature

Simulated Annealing에서는 Temperature T라는 개념을 사용한다.

초반에는 T가 크다.

T가 큼
→ 나쁜 선택도 비교적 자주 허용
→ Exploration

시간이 지나면 T를 점점 줄인다.

T가 작음
→ 나쁜 선택을 거의 허용하지 않음
→ Exploitation

즉,

초반
→ 다양하게 탐색

후반
→ 좋은 지역에 집중

한다.

Machine Learning에서 자주 듣는

Exploration vs Exploitation

의 관계와 비슷하다.

---

Local Beam Search

Local Search를 하나의 State만 가지고 하지 않고
여러 개의 State를 동시에 유지할 수도 있다.

이것이 Local Beam Search다.

현재 State k개
↓
각 State의 Successor 생성
↓
전체 중 좋은 k개 선택
↓
반복

중요한 것은

독립적인 Search를 k개 돌린다

는 의미가 아니라는 것이다.

모든 Successor를 함께 비교하고
그중 가장 좋은 k개를 선택한다.

---

그런데 좋은 State들만 남기면 비슷해지지 않을까?

맞다.

계속 좋은 State만 선택하면
결국 k개의 State가 모두 비슷한 Local Optimum에 모일 수 있다.

그래서 좋은 State를 선택할 확률을 높이되
Randomness를 섞는 방법도 사용할 수 있다.

여기에서 강의는 자연스럽게
Genetic Algorithm으로 연결한다.

---

Genetic Algorithm

Genetic Algorithm은
생물의 자연 선택과 진화를 모방한 알고리즘이다.

핵심은

Population
Selection
Crossover
Mutation
Next Generation

이다.

---

Representation

먼저 하나의 Solution을
어떤 형태로 표현해야 한다.

Genetic Algorithm에서는 보통 하나의 Solution을

String

으로 표현한다.

예를 들어

1011010011

같은 Binary String을 사용할 수도 있다.

이것을 생물의

Chromosome

처럼 생각하는 것이다.

---

Population

Solution 하나만 사용하는 것이 아니라
여러 Candidate Solution을 만든다.

Solution 1
Solution 2
Solution 3
Solution 4
...

이 집합을 Population이라고 한다.

초기 Population은 보통 Random하게 생성한다.

---

Fitness Function

각 Solution이 얼마나 좋은지 평가해야 한다.

이를 Fitness Function이라고 한다.

Fitness가 높다
→ 좋은 Solution

Fitness가 낮다
→ 좋지 않은 Solution

이라고 생각할 수 있다.

---

Selection

좋은 Solution일수록
다음 Generation에 자신의 정보를 전달할 확률을 높인다.

강의에서는 Roulette Wheel Selection을 예로 든다.

Fitness가 높은 개체일수록
Roulette Wheel에서 더 큰 영역을 차지한다.

따라서 선택될 확률이 높다.

---

Crossover

선택된 두 Parent를 섞어서
새로운 Child를 만든다.

예를 들어

Parent 1

11011 | 00100

Parent 2

10101 | 11100

이라고 하면

Child 1

11011 | 11100

Child 2

10101 | 00100

처럼 만들 수 있다.

이를 Crossover라고 한다.

한 지점에서 자르면

Single Point Crossover

이고,

두 지점에서 자르면

Two Point Crossover

가 될 수 있다.

---

Mutation

하지만 Parent끼리 계속 섞기만 하면
Population이 점점 비슷해질 수 있다.

그러면 Local Optimum에 빠질 가능성이 높다.

그래서 아주 작은 확률로 일부 값을 Random하게 변경한다.

예를 들어

101101

에서

101001

로 Bit 하나를 바꾸는 것이다.

이를 Mutation이라고 한다.

Mutation은 Population에 새로운 다양성을 제공한다.

---

Next Generation

Selection, Crossover, Mutation을 통해
새로운 Candidate Solution을 만든다.

그리고 이들을 다음 Generation으로 사용한다.

Generation 1
↓
Selection
↓
Crossover
↓
Mutation
↓
Generation 2
↓
...

이 과정을 반복한다.

때로는 이전 Generation의 가장 좋은 Solution을
다음 Generation에 그대로 유지시키기도 한다.

이를 Elitism이라고 한다.

---

결국 Genetic Algorithm도 Search다

처음에는 Genetic Algorithm이
Graph Search와 완전히 다른 내용처럼 보였다.

하지만 강의를 따라가다 보면
결국 이것도

State Space에서 더 좋은 State를 찾는 Search

라는 큰 틀 안에 있다.

단지

BFS / DFS
→ 명확한 Frontier를 탐색

Local Search
→ Neighbor를 이용해 개선

Genetic Algorithm
→ Population을 진화시키며 탐색

이라는 차이가 있을 뿐이다.

---

마지막은 Continuous State Space

지금까지 대부분의 Search 문제는
State가 명확하게 구분되는 Discrete Space였다.

예를 들어

City A
City B
City C

또는

Puzzle State 1
Puzzle State 2

처럼 구분된다.

그런데 현실에는 Continuous한 문제도 많다.

예를 들어 지도 위에 공항 3개를 어디에 배치할지 결정한다고 해보자.

각 공항의 위치가

(x1, y1)
(x2, y2)
(x3, y3)

라고 하면

총 6개의 Continuous Variable이 존재한다.

---

Gradient-Based Algorithm

Continuous State Space에서는
Neighbor를 하나하나 생성하기보다 Gradient를 사용할 수 있다.

Gradient는 쉽게 생각하면

현재 위치에서 함수 값이 가장 빠르게 변하는 방향

이다.

값을 최대화하고 싶다면

Gradient Ascent

를 사용하고,

값을 최소화하고 싶다면

Gradient Descent

를 사용할 수 있다.

---

Gradient Descent

Machine Learning을 조금 공부했다면
정말 자주 보는 이름이다.

예를 들어 Loss Function을 줄이고 싶다고 해보자.

현재 Parameter에서

Loss가 가장 빠르게 증가하는 방향

이 Gradient라면,

그 반대 방향으로 이동한다.

Parameter
↓
Gradient 계산
↓
Gradient 반대 방향 이동
↓
Loss 감소
↓
반복

이것이 Gradient Descent다.

결국 Deep Learning에서 사용하는 Optimization도
큰 관점에서 보면

더 좋은 State를 찾는 Search

라고 볼 수 있다는 점이 인상적이었다.

---

Lesson 4를 정리하면

이번 Lesson은 사실 꽤 많은 알고리즘을 다루고 있다.

하지만 큰 흐름으로 묶으면 생각보다 단순하다.

먼저

Uninformed Search

에서 벗어나

Heuristic

이라는 추가 정보를 사용한다.

그리고

Greedy Search
→ h(n)

Uniform Cost Search
→ g(n)

A*
→ g(n) + h(n)

으로 연결된다.

그 이후에는 경로 자체보다
최종 상태가 중요한 Optimization Problem으로 확장하면서

Local Search
↓
Hill Climbing
↓
Simulated Annealing
↓
Local Beam Search
↓
Genetic Algorithm

을 다룬다.

마지막으로 Continuous State Space에서는

Gradient Ascent
Gradient Descent

까지 연결된다.

---

수업을 듣고 나서

이번 Lesson의 앞부분은 꽤 익숙했다.

Greedy Algorithm은 코딩테스트를 준비하면서 자주 접해왔고,
문제를 보고

현재 가장 좋은 선택을 반복해서 해도 되는가?

를 고민하는 과정도 어느 정도 익숙했다.

그런데 이번 강의를 들으면서
Greedy를 단순한 코딩테스트 풀이 기법이 아니라

Heuristic을 이용하는 Search Strategy

라는 관점에서 볼 수 있었다.

특히

Greedy
→ h(n)

Uniform Cost
→ g(n)

A*
→ g(n) + h(n)

이라는 연결이 가장 기억에 남았다.

그동안 A* Search는

"길 찾기에 사용하는 유명한 알고리즘"

정도로만 알고 있었는데,

왜 g(n)과 h(n)을 더하는지 이해하고 나니
알고리즘 구조가 훨씬 자연스럽게 느껴졌다.

또한 Heuristic이 단순히

대충 Goal과 가까운 정도

가 아니라,

A*의 최적성을 보장하기 위해

h(n) ≤ 실제 남은 비용

이라는 조건을 만족해야 한다는 점도 새롭게 정리할 수 있었다.

---

마무리

Lesson 3에서는

어떤 순서로 State Space를 탐색할 것인가?

를 배웠다면,

Lesson 4에서는

Goal에 대한 정보를 알고 있다면 그 정보를 어떻게 탐색에 활용할 것인가?

를 배웠다고 생각한다.

특히 가장 핵심적인 내용을 하나만 고르라고 한다면
역시 A* Search다.

g(n)
= 지금까지 실제 비용

h(n)
= 앞으로 필요할 것으로 예상되는 비용

f(n)
= g(n) + h(n)

그리고 좋은 Heuristic을 사용하면
불필요한 탐색을 크게 줄이면서도 최적해를 찾을 수 있다.

후반부의 Local Search와 Genetic Algorithm, Gradient Descent까지 보고 나니
Search라는 개념이 생각보다 훨씬 넓다는 것도 알게 되었다.

Graph에서 길을 찾는 것도 Search

최적의 TSP Tour를 찾는 것도 Search

Queen의 배치를 개선하는 것도 Search

Neural Network의 Loss를 줄이는 것도 Search

결국 많은 알고리즘 문제는

수많은 가능한 상태 중에서 더 좋은 상태를 어떻게 효율적으로 찾아갈 것인가?

라는 하나의 질문으로 연결되는 것 같다.