탐색과 최적화 기법 (3)

3-5 게임 탐색

• 게임의 참가자가 이기기 위해 매순간 최선의 방법을 찾는 것을 모방한 것

미니맥스 알파베타 가지치기

• 자신의 순서에서 최댓값을 선택하고, 상대방의 순서에서 최솟값을 선정하는 과정을 반복적으로 수행하는 것
• 알파 컷오프: 최소 점수를 선택하면서 이미 저장된 점수보다 큰 점수의 노드가 나오면 제외하는 것
• 베타 컷오프: 최대 점수를 선택하면서 이미 저장된 점수보다 작은 점수의 노드가 나오면 제외하는 것

몬테카를로 트리 탐색

• 몬테카를로: 무작위(Random)라는 의미를 가짐
• 플레이아웃(Playout): 현상태에서 게임 종료 시까지 무작위 플레이를 수행하는 것
• 시뮬레이션
• 알파고와 같은 프로그램에서 사용

3-6 제약 조건 만족 문제

• 주어진 제약 조건을 만족하는 해를 찾는 것
• Constant Satisfaction Problem

백트래킹 탐색

• 제약 조건을 만족하는 해를 찾기 위해 가능한 모든 방법을 탐색한다는 아이디어에 기반을 두고 개발된 알고리즘
• 주어진 문제에 대해 가능한 모든 해를 깊이우선 탐색을 이용해 검색하고, 검색 과정에서 해당 사항이 없는 것은 가지치기를 수행하는 방법

제약 조건 전파 방법

• 진행하면서 인접 변수 간의 제약 조건에 따라 각 변수에 허용되지 않는 값을 제거하는 방식으로 변숫값을 결정해 해를 찾는 방법
• 진행하면서 제약 조건이 계속 변경될 때 이를 고려해 해를 찾는 방법

분기 한정법

• 최적의 경우를 찾는 알고리즘
• '최소한 이 정도는 돼야 답이 될 가능성이 있다'라는 범위
• 전체를 찾아보지 않아도 최적의 방법을 확인할 수 있음

3-7 최적화

• 허용되는 값 중 주어진 기준을 가장 잘 만족하는 것을 찾는 알고리즘
• 조합 최적화(Combination Optimization)
• 계산 과정의 최적화
• 함수 최적화

유전 알고리즘

• 인공지능의 최적화 방법 중 주어진 조건을 만족하는 최적의 조합을 구하는 경우에 가장 많이 사용
• 최고의 조합이 아닌 최적의 조합을 구하는 알고리즘

메타 휴리스틱(Meta Heuristic)

• 유전 알고리즘처럼 최적해는 아니지만, 우수한 해를 빠르게 찾기 위한 휴리스틱(시행착오)적 문제 해결 전략
• 모방 알고리즘(Memetic Algorithm)
• 입자 군집 최적화(Particle Swarm Optimization, PSO)
• 개미 집단 최적화(Ant Colony Optimization, ACO)
• 인공 물고기 집단 최적화(Artificial Fish Swarm Optimization, AFSO)
• 타부 탐색(Tabu Search)
• 담금질 기법(Simulated Annealing)
• 하모니 탐색(Harmonic Search)

동적 프로그래밍

• 인공지능의 최적화 방법 중 계산 과정의 최적화를 위해 가장 많이 사용되는 대표적인 알고리즘
• Dynamic Programming, DP
• 메오라이제이션: 분할된 부분의 답을 기억했다가 필요할 때마다 불러 내 사용하는 방법

함수 최적화

• 인공지능의 최적화 방법 중 주어진 상태를 함수로 표현하고, 이를 바탕으로 최적화의 과정을 수행하는 것

 

 

 

 

 

※ 해당 내용은 <인공지능 바이블>의 내용을 토대로 학습하며 정리한 내용입니다.