출처: Three Dash Two Four
다들 체스 게임을 들어본 적 있는가? 아마 해 보지는 않았지만 어떻게 구성되어있는지는 알 것이다.
체스는 가로와 세로가 각각 8줄씩 64칸으로 격자로 배열 된 체스보드에서 두 명의 선수가 기물들을 규칙에 따라 움직여 싸우는 보드 게임이다. 세계에서 가장 보편적인 장기류 게임이자, 둘이서 게임하기에 적당하기에 많은 사람들이 즐기고 있다.
그럼 여기서 궁금한 것은, '어떻게 해야 상대방을 이길 수 있는가?'일 것이다.
선수는 킹[♚], 퀸[♛] 각 1개, 룩[♜] 2개, 나이트[♞]2개 비숍[♝]2개 그리고 폰[♟] 8개로 총 16개의 기물을 가지고 시작하고 피스 6종류는 각각 다르게 이동한다. 기물은 상대의 기물을 공격하는데 사용되고 게임의 목적은 상대의 킹을 체크메이트하는 것이다. 체스에서 킹이 공격받은 경우를 우리는 체크라고 부른다. 체크메이트(줄여서 메이트라고도 부른다.)는 공격받은 킹이 체크를 벗어날 수 없는 경우다. 이때, 경기는 상대 킹을 체크메이트한 선수의 승리로 끝난다.
내가 체스를 둔다고 생각을 해보면, 모든 기물에 대해 이동할 수 있는 모든 경우를 고려하지도 않을 뿐더러, 각 경우에 대해 얼마나 좋은 결과가 나오는 지를 정확히 계산하지도 못한다. 하지만 내가 마음속으로 움직일 기물을 몇 개 정해놓고 그 기물로 어떤 위치에 이동했을 때 상대의 기물을 아무 리스크 없이 제거할 수 있거나, 그 움직임을 통해 나중에 상대의 말을 손해 없이 잡을 수 있는 상황을 만들 수 있다는 판단이 서면 이를 행한다. 그게 최적의 수인지 알 수 없고, 상대의 움직임에 의해 더 안좋은 상황으로 변할 수도 있다. 하지만 그 모든 것을 고려할 여력이 안되기 때문에 이와 같은 전략을 사용하게 된다. 이렇게 문제를 해결하는 방법을 휴리스틱이라고 한다.
휴리스틱에 대해 자세하게 들어가기 전, 우리는 Exact Algorithm 과 Heuristic Algorithm에 대한 차이를 이해해야 한다. Exact Alogirthm은 말 그대로 정확한 알고리즘을 뜻한다. 최적의 솔루션을 찾는 것을 목표로 하지만 대규모 문제에는 계산 비용이 많이 들고 비실용적일 수 있다.
이에 반해, Heuristic Algorithm은 좋은 솔루션을 빠르고 효율적으로 찾는 것을 목표로 하지만 최적의 솔루션을 보장하지 못할 수도 있다.
Exact Algorithm과 Heuristic Algorithm은 모두 problem-dependent, 특정 문제의 solution을 구하기 위한 algorithm이라 볼 수 있다. 즉, 숫자들을 sorting하거나 '포켓스탑'의 순서를 정하는 문제 등의 특정 문제를 풀기 위한 Algorithm이라는 것이다.
- Meta-heuristic이 heuristic이 되는 과정.
메타 휴리스틱이란 휴리스틱연산에서 고도의 단계가 필요한 문제이다. 컴퓨터 과학 및 수학적 최적화에서 메타휴리스틱은 최적화 문제 또는 기계 학습 문제에 대해 충분히 좋은 솔루션을 제공할 수 있는 휴리스틱을 찾고, 생성하고, 조정하거나 선택하도록 설계된 상위 수준 절차 또는 휴리스틱이다.
메타 휴리스틱 알고리즘은 Heuristic Algorithm과 같이 good solution을 구하는 Algorithm이지만 problem-independent하다는 차이점이 있다. 즉, 특정 문제에 종속되지 않고 다양한 문제에 적용이 가능한 Frame work가 되는 Algorithm이라는 것이다.
이 이미지는 메타휴리스틱 알고리즘들을 분류한 것을 보여주고 있다. 메타휴리스틱 알고리즘은 복잡한 최적화 문제를 해결하기 위한 전략적 접근 방식으로, 각각의 알고리즘은 특정한 속성이나 전략을 바탕으로 분류된다. 여기서 나타난 분류는 다음과 같다:
-
자연 영감을 받은(Naturally Inspired): 이 범주의 알고리즘들은 자연 현상이나 생물학적 메커니즘에서 영감을 받았다.
- 진화 알고리즘(Evolutionary Algorithm): 유전 알고리즘(Genetic Algorithm), 유전 프로그래밍(Genetic Programming), 진화 프로그래밍(Evolutionary Programming), 차별화 진화(Differential Evolution), 산란 검색(Scatter Search) 등이 여기에 해당한다.
- 입자 군집 최적화(Particle Swarm Optimization), 개미 군집 최적화(Ant Colony Optimization Algorithms) 등은 사회적 동물의 행동에서 영감을 받았다.
-
국소 탐색(Local Search): 이 알고리즘들은 해의 후보들을 지역적으로 탐색하여 점진적으로 개선한다.
- 직접(Direct): 반복된 로컬 서치(Iterated Local Search), 확률적 로컬 서치(Stochastic Local Search)가 여기에 포함된다.
- 동적 목표 함수(Dynamic Objective Function): 가이드 로컬 서치(Guided Local Search), 가변 이웃 탐색(Variable Neighborhood Search)이 이에 해당한다.
-
경로(Trajectory): 이 알고리즘들은 시간에 따라 해의 경로를 추적하면서 개선을 시도한다.
- 타부 검색(Tabu Search), GRASP(Greedy Randomized Adaptive Search Procedure) 등이 여기에 포함된다.
-
메모리 기반(No Memory): 이러한 알고리즘들은 이전에 탐색한 해를 기억하지 않고 독립적으로 해를 개선한다.
- 시뮬레이티드 어닐링(Simulated Annealing), 진화 전략(Evolution Strategy), 분포 추정 알고리즘(Estimation of Distribution Algorithm) 등이 이에 해당한다.
각각의 알고리즘은 특정 문제에 대해 더 적합할 수 있으며, 특정 문제의 특성과 요구 사항에 따라 적절한 메타휴리스틱을 선택해야 한다. 예를 들어, 유전 알고리즘은 넓은 탐색 공간을 가진 문제에 적합할 수 있고, 타부 검색은 해의 품질을 빠르게 개선할 필요가 있을 때 유용할 수 있다.
더 자세한 내용은 다음 화에 설명하겠다. 읽어줘서 고맙다.
