[Local Search Algorithms] - 개요

1. Local Search Algorithms

인공지능을 공부하다 보면 항상 min을 찾으라고 한다. 

 

local Serach Algorithms는 말 그대로 local min을 찾는 알고리즘이다. 

2. Problem 

Local Search Algorithms를 풀기 위해 2개의 문제를 준비했다.

1) Numeric

연속함수의 Minimum을 구하는 것이 목표이다. 

 

- Ackley

위의 예시 사진은 변수가 2개이지만 준비된 Ackley는 변수가 5개인 함수이다.

각 변수마다 범위가 (-30, 30)이다. 

20 + math.e - 20 * math.exp(-(1/5) * math.sqrt((1/5) * (x1 ** 2 + x2 ** 2 + x3 ** 2 + x4 ** 2 + x5 ** 2))) - math.exp((1/5) * (math.cos(2 * math.pi * x1) + math.cos(2 * math.pi * x2) +math.cos(2 * math.pi * x3) +math.cos(2 * math.pi * x4) +math.cos(2 * math.pi * x5)))
x1,-30,30
x2,-30,30
x3,-30,30
x4,-30,30
x5,-30,30

 

- Convex

위의 예시 사진은 변수가 2개이지만 준비된 Convex는 변수가 5개인 함수이다.

각 변수마다 범위가 (-30, 30)이다. 

(x1 - 2) ** 2 +5 * (x2 - 5) ** 2 + 8 * (x3 + 8) ** 2 + 3 * (x4 + 1) ** 2 + 6 * (x5 - 7) ** 2
x1,-30,30
x2,-30,30
x3,-30,30
x4,-30,30
x5,-30,30

 

- Griewank

 

위의 예시 사진은 변수가 2개이지만 준비된 Griewank는 변수가 5개인 함수이다.

각 변수마다 범위가 (-30, 30)이다. 

1 + (x1 ** 2 + x2 ** 2 + x3 ** 2+ x4 ** 2 + x5 ** 2) / 4000 - math.cos(x1) * math.cos(x2 / math.sqrt(2)) * math.cos(x3 / math.sqrt(3)) * math.cos(x4 / math.sqrt(4)) * math.cos(x5 / math.sqrt(5))
x1,-30,30
x2,-30,30
x3,-30,30
x4,-30,30
x5,-30,30

 

 

 

위 3개의 함수를 통해 Numeric 문제를 풀면서 local min을 찾을 것이다. 

 

아직은 어떻게 풀지 설명은 안 했지만 단순하게 생각해 보자.

 

random 한 위치에서 시작할 경우, 그 주변의 데이터만 보고 min을 찾을 것이기 때문에 더 낮은, 계속 더 낮은 값을 찾는다. 

 

이 생각을 계속 가지고 다음 포스트부터 알려줄 문제를 보면 이해하기 쉬울 것이다. 

 

2) TSP(traveling salesman problem)

TSP는 salesman이 물건을 팔러 각 지역을 돌아다닐 건데 어떻게 하면 가장 적게 이동하여 모든 지역을 갈 수 있을까의 문제다.

 

 

빨간 점을 지역이라고 하면, 왼쪽은 최적화되지 않은, 마음대로 이동한 것이고, 오른쪽은 최적화하여 가장 적게 이동한 것이다.

 

첫 번째 줄에는 몇 개의 지역인지, 그다음줄부터는 각 지역의 x, y좌표가 지정되어 있다. 

 

30
(8, 31)
(54, 97)
(50, 50)
(65, 16)
(70, 47)
(25, 100)
(55, 74)
(77, 87)
(6, 46)
(70, 78)
(13, 38)
(100, 32)
(26, 35)
(55, 16)
(26, 77)
(17, 67)
(40, 36)
(38, 27)
(33, 2)
(48, 9)
(62, 20)
(17, 92)
(30, 2)
(80, 75)
(32, 36)
(43, 79)
(57, 49)
(18, 24)
(96, 76)
(81, 39)

3. Algorihms

Local Search Algorithms를 풀기 위해 3가지의 알고리즘을 공부해 보자.

 

1) Hill Climbing Algorithm : 단순하게 현재 state에서 주변의 값을 보고 학습을 시켜 min을 찾는 것이다.

- Steepest Ascent

https://hccode0419.tistory.com/entry/Local-Search-Algorithms-Hill-climbing-Algorithms-Steepest-Ascent-1

[Local Search Algorithms - Hill climbing Algorithms] Steepest Ascent

 

- First Choice

https://hccode0419.tistory.com/entry/Local-Search-Algorithms-Hill-climbing-Algorithms-First-Choice

[Local Search Algorithms - Hill climbing Algorithms] First Choice

 

2) Meta heuristic Algorithm : 가장 최적의 값을 찾는 것이 아니라, 그나마 좋은 값을 찾는 것이다. 즉 best가 아니라 good value를 찾는 알고리즘이다. 

- Simulated Annealing

https://hccode0419.tistory.com/entry/Local-Search-Algorithms-Meta-Heuristic-Algorithm-Simulated-Annealing

[Local Search Algorithms - Meta Heuristic Algorithm] Simulated Annealing

 

- Genetic Algorithm

https://hccode0419.tistory.com/entry/Local-Search-Algorithms-Meta-Heuristic-Algorithm-Genetic-Algorithm

[Local Search Algorithms - Meta Heuristic Algorithm] Genetic Algorithm

 

 

결론적으로 해당 블로그 및 추후에 나올 블로그에서는 Local Search Algorithms을 Numeric과 TSP를 통해 공부할 것이며, 각 포스트마다 다양한 Algorithms을 이용하여 풀어볼 것이다.