[인공지능] 4.Local Search Algorithms

Local Search Algorithms

1. Hil-climbing Search

2. Simulated Annealing Search

3. Genetic Algorithms

 

 

 

---

Local Search Algorithms 이란?

 

Local Search 를 그대로 해석하면 '지역 탐색' 입니다. 현실 세계에서도 그렇지만 모든 문제들이 알고리즘 처럼 딱딱 떨어지지 않는 경우도 생각보다 많습니다. '정형화'된 문제들 뿐만 아니라 '덜 정형화' 된 문제들도 많다는 의미입니다. 이 '덜 정형화' 된 알고리즘이 오늘 이야기할 'Local Search Algorithms' 알고리즘 입니다. 해석 그대로 지역적인 탐색을 한다는 건데 이는 현재의 상황만 대충 파악해서 가장 적절하다고 여겨지는 행동을 하라는 겁니다. 또 컴퓨터가 랜덤하게 움직일 가능성을 생각하거나 주변, 지역적인 state 만 보고 판단할 때 이 알고리즘이 사용됩니다. 

 

 

 

Local Search Algorithms은 순수한 최적화 문제를 해결할 때 유용합니다. (ex. 외판원 문제(TSP), n-queens) 사실 많은 최적화 문제에 있어서 path(경로)는 무관합니다. (ex. 8-queens problem 의 경우 goal state 가 solution 이었습니다.) 

State space(상태 공간) 은 complete 한 구성 의 집합입니다.

 

- 목적함수(Objective function)에 따라 최적화를 찾거나 (ex.TSP)

- 제한 조건을 만족하는 configuration을 찾는거(ex.time table) 

 

Local Search 는 목적함수를 사용해 현재 노드를 기준으로 이웃 노드들을 확인하여 조금이라도 더 좋은 노드로 이동하는 방식을 사용합니다. 하지만 지나온 경로들은 조금도 유지하지 않습니다. 만약에 Local Search 알고리즘이 덜 체계적이라면 두가지 장점이 있습니다. 

 

1. 아주 적은 메모리를 이용

2. 무한하거나 아주 큰 상태 공간에서 그나마 합리적인 해를 찾음

 

2번을 보면 바둑처럼 무한한 상태 공간을 가지는데 여기서 알고리즘을 돌리면 너무 오래 걸리니 지게 되겠죠? 그래서 시간 초과가 뜨기 전에 대충 적절한 해를 내는겁니다. 이 때까지 배웠던 거처럼 Standard 한 탐색 모델이 아니고 즉 Goal Test와 Path Cost 라는 개념이 사라지는 겁니다. 

결과론적으로 '완전한' 답이 아닌 '적절한' 답을 찾는 Local Search 입니다.

 

 

아래 그림을 보면 목적 함수 값의 최적화가 상태 공간 산맥으로 형상화된 것을 볼 수 있습니다. 함수의 값이 가자 큰다면 산맥의 꼭대기로 표현이 되겠죠. 

 

State space landscape 

 

위치는 state 입니다. 보시는 것과 같이 가장 높은 꼭대기 Global maximum 은 극대화 문제의 최적화된 해로 검색 알고리즘을 통해 찾아내는 것이 목표입니다. Local Maximum은 주변 Neighbors 사이에서 가장 높은 꼭대기를 의미합니다. 그래도 Global maximum 보다는 작습니다. 극대라고 생각 하셔도 되겠네요. 그럼 이제 Local Search 알고리즘에 대해 알아보겠습니다. 

 

다시 한 번 종류를 말씀해드리자면 다음과 같습니다. 

 

Local Search Algorithms

- Hill-climbing Search

- Simulated Annealing Search

- Genetic Algorithms

- Continuous State Spaces

- Constrained Optimization Problem

 

 

---

Hill-climbing Search

 

Hill-climbing Search 는 gradient ascent/descent (경사 증가/하강)라고 불리기도 합니다. 이는 현재 상황에서 주변 노드 중에 올라갈 곳이 있는지 확인 후 더 올라갈 수 있는 곳이 있으면 이동 하는 겁니다. 더 이상 올라갈 곳이 없으면 그 곳이 Peak(꼭대기) 라고 여기는 겁니다. 

등산이라는 이름과 아주 걸맞는 탐색법입니다. 다만 올라와서 꼭대기라고 생각한 곳이 정말 최고 위치의 꼭대기인지 아니면 극대값인 작은 봉우리였는지 알 수가 없습니다. 

 

이는 Search Tree 를 가질 필요도 없고 이전 State 정보를 저장할 필요도 없습니다. Local Search 의 특성입니다. 

 

아래의 슈도코드는 가파른 경사 버전의 Hill-Climbing 입니다. 

보면 Global maximum이 아닌 local maximum 을 return 하는 걸 볼 수 있고 neighbor 값 들 중에 현재 값보다 크면 이를 local maximum으로 리턴하는 것을 알 수 있습니다. 

 

언덕 오르기 탐색의 예시로 8-Queens를 이야기 해봅시다.

이는 간단하게 퀸들이 죽지 않게 배치하는 방식입니다. 당연하게도 한 열에 하나의 퀸만 오게 되겠죠. 

 

알고리즘은 간단합니다. 

상태에서 하나의 퀸을 놓을 수 있는 자리를 체크합니다. 그러면 자신이 있는 열을 제외하고 8x7 = 56가지 자식 노드가 생깁니다. 그럼 이 56개의 자식 노드를 각각 평가하여 가장 휴리스틱 함수가 좋게 나온 걸로 다음 상태를 지정해주면 됩니다. 여기서 휴리스틱은 서로 공격가능한 pair 의 개수 입니다. 왼쪽 상태에서는 17개네요. 현재 h = 17 로 생각한 후 h 가 작은 자식 노드로 이동합시다. 

 

참고로 왼쪽 그림의 휴리스틱은 다음과 같습니다.

이 과정이 이해가 되시지 않으시면 다음 그림을 살펴보면 이해가 되실 겁니다.

 

결과 적으로는 아래의 그림에 도달을 하게 됩니다. 

이 알고리즘으로 Hill-climbing Search 를 진행하면 왼쪽 그림과 같은 결과가 나오게 됩니다. 하지만 이럼에도 h = 0이 아닌 걸 알 수 있죠? h = 1 입니다. 즉 최적화된 해가 아닌 겁니다. 최적화 해가 될려면 h=0 이어야합니다. 알고리즘을 공부해보신 분들은 느끼셨겠지만 Hill-climbing Search 는 Greedy 알고리즘과 흡사합니다. 그래서 가끔 Greedy Local Search 라고 불리기도 합니다. 이러한 Hill-climbing Search은 보통 굉장히 빠릅니다. 하지만 무조건 빠르고 좋을 수만은 없는거죠. Hill-climbing Search에도 결함이 존재합니다.이런 탐욕적인 즉 Greediness 때문입니다.

 

Local Maxima(지역 최대치) : Global Maximum에 도달하지 못하고 Local Maximum 안에 갇힐 우려가 있다.

 

이는 Hill Climbing 이 별로 신뢰성이 높지 않다고 볼 수 있게 합니다. Optimality 를 보장할 수 없기 때문입니다. 하지만 알고리즘 자체가 단순하고(슈도코드에서도 확인했듯이) 계산의 부하가 적기 때문에 채택을 하기 위해 여러 방법들이 나왔습니다. 

 

Hill Climbing Search 를 선택하기 위한 여러 해결 방안 

 

1. Stochastic hill climbing (확률적 언덕 오르기)

: 매번 최적의 neighbor 을 선택하는 것이 아니라 현재 상태보단 나은 neighbor 중에 하나를 임의로 선택하는 겁니다. 나봔 나은 이웃 중에 아무거나 고른 다는 의미죠. 단순히 보면 비효율적이라 여겨질지 모르지만 결과 자체는 더 높은 Maximum 을 채택하는 경우가 많아서 사용됩니다.

 

2. First-choice(simple) hill climbing

: 만약 이웃노드의 수가 무수히 많으면 이를 다 조사해서 선택하기란 매우 비효율적이고 Hill-Climbing 알고리즘에 적합하지 않겠죠. 그래서 처음으로 나온 나보단 나은 상태를 바로 채택하는 방식입니다. 

 

3. Random-restart hill climbing 

: 이는 다양한 Hill-Climbing 알고리즘들을 여러 번 반복해서 그 중 가장 좋은 해답을 택하는 Search 방법입니다. 이는 8-jqueens 에 효율적입니다. 3만 개의 퀸도 1분 안에 찾아내는 미친 효율을 낼 수 있습니다. 

 

Complexity

- 언덕 오르기의 성공은 state-space landscape 의 모양의 의존합니다. 

- NP-hard 문제는 전형적으로 지수 수의 local maxima 에 갇힙니다. 

- Good local maximum 은 작은 수의 restart 로 찾을 수 있습니다. 

 

 

---

Simulated Annealing

 

 Annealing 은 '가열 냉각' 이라는 뜻입니다.  이는 Simulated Annealing 은 금속을 '가열 냉각'하는 과정을 알고리즘처럼 사용하여 합리적인 목표 상태에 이르는 방식입니다. 

 

 위에서 언급한 Random-Restart Hill Climbing 은 여러 Climbing 알고리즘을 반복해 가장 효율적인 대안을 찾는다고 하였습니다. 하지만 이 또한 Hill-climbing 으로 계속 올라가는 알고리즘입니다. 만약 local Maximum을 만났을 때 다시 뒤 돌아서 내려가 다른 봉우리로 이동한다면 어떨까요? 이는 Simulated Annealing 에 관한 내용입니다. 이러면 언덕 오리기 보다 Global Maximum 에 도달할 가능성이 올라갑니다.

 

 파칭코 게임을 상상하시면 됩니다. 산이라는 입체 지도가 상자안에 들어있다고 생각합시다. 이 입체 지도에 공을 던지고 상자를 마구 흔드는 겁니다. 속도를 낮추면 어느 계곡으로 들어갈텐데 그 계곡을 가장 합리적인 Goal 로 보는 겁니다. 설사 초반에 Local Maximum에 빠져도 마지막에는 Global Maximum으로 돌아갈 수 있습니다. 

 

 금속 공학에서 쓰이는 방법으로 안정적인 금속 하나를 가열한 뒤에 천천히 온도를 낮춰서 초기보다 낮은 에너지를 가지는 결정의 형태로 금속 원자들이 결합하게 되는데 이게 풀림(Annealing)이라고 합니다. 이를 알고리즘에 적용합니다. 

 

 

 구체적인 알고리즘은 다음과 같습니다. 이웃한 상태 노드 중에서 임의로 상태 하나를 선택합니다. 그 뒤에는 해당 상태가 현 상태보다 낫다면 바로 전이를 시작하고 혹시 더 안 좋다면 '온도'와 더 안 좋아지는 정도를 가지고 전이할지 말지를 정하는 겁니다. 

 

 여기서 온도는 anneling schedule 을 결정하는 겁니다. 쉽게 말해 랜덤성을 조정하는 거죠. 시작 시 T가 높을 때 보통 Bad moves 가 많이 일어납니다. 온도는 천천히 낮아집니다. 

 

 온도 T, 안 좋아지는 정도는 df(x) 라고 하면 확률은 e^ ( -df(x)/T) = e^(-E(x)/kT) 입니다. 만약에 T -> 0 이면 simple hill-climbing 입니다. 

 

 신기하게 이 Simulated Annealing 알고리즘은 온도가 충분히 느리게 낮아지면 Optimal 하다는 것이 증명이 되었습니다. 하지만 실제로 이용하기에는 너무 느리고 그래서 융통성 있게 온도를 조절하여 사용되는 겁니다. 따라서 최적해를 반드시 구할 때보다는 어느 정도 수준이 보장되는 해답을 구해야할 때 주로 사용 되는 방법이 할 수 있습니다.

 

 

 

---

Genetic Algorithms

 

이는 자연 계의 유전적인 현상을 그대로 계산에 적용한 겁니다. 그러니 가장 좋은 유전자만 남기는 습성이 있고 또 돌연변이 유전자로 통해서 유전자 변형이 일어날 수도 있겠죠. 이것도 또 하나의 유전 알고리즘입니다. 

 

Genetic Algorithms 에서는 자연의 유전 알고리즘에 입각하여 만들어졌습니다. 각 유전자가 state 으로 비유되고 유전자가 섞이는 과정은 내부 요소들이 섞이는 과정으로 생각할 수 있습니다. 일반적으로 이진수로 표현되는 문자열로 인코딩을 한 뒤에 문자열의 일부를 서로 치환하는 방법을 채택하지만 실제로는 융통성있게 잘 조절해서 사용되는 경우가 많습니다. 

 

유전 알고리즘을 살펴봅시다. 이는 임의의 state 로 시작 됩니다. 

다음 자손으로 세대가 교체될 때 모든 유전자들은 Fitness Function 에 의해 평가가 됩니다. 이 Fitness 가 높게 측정되는 유전자에 한정되어  번식이 가능하게 되는 겁니다. 그럼 Fitness 가 높은 유전자들 끼리 만나면 랜덤하게 기준을 선택하고 그 기준으로 Crossover 합니다. 그리고 Swap 하고 자손 문자열 중 임의의 돌연변이(Mutation)를 만들어주면 됩니다.

이 돌연변이도 반드시 만드는 것이 아니라 임의로 만들어주어야합니다. 

crossover 의 기준은 랜덤입니다. 

 

Local Search algorithms 는 구체적인 휴리스틱을 사용하지 않습니다. 

Simulated annealing 와 GA 는 높은 레벨의 휴리스틱을 사용합니다. 이를 메타 휴리스틱 알고리즘이라고 합니다.  

 

예를 들어 봅시다. 

GA 알고리즘 과정

위와 같은 이진 수가 있다고 합시다. 1이 많을 수로 Fitness의 수치가 높습니다. 

초기화

평가를 진행해줍시다. 

이 중에 가장 높은 Fitness를 가진 걸 골라줍니다. 

이제 Crossover 을 진행해줍시다. Crossover 의 기준이 되는 선은 임의로 정해줍니다. 

랜덤하게 돌연변이를 발생시킵니다. 

이를 갱신하고 3번 Fitness evaluation 으로 돌아갑니다. 

 

 

 

 

아래 그림은 GA 의 예시입니다. 

 

아래는 GA의 슈도 코드 입니다. 

---