탐색과최적화
1. 상태공간과탐색 2. 맹목적탐색 3. 정보이용탐색 4. 게임탐색 5. 제약조건만족문제 6. 최적화
1. 상태공간과탐색 탐색 ( 探索, search) 문제의해 (solution) 이될수있는것들의집합을공간 (space) 으로간주하고, 문제에대한최적의해를찾기위해공간을체계적으로찾아보는것 탐색문제의예 선교사 - 식인종강건너기문제 틱 - 택 - 토 (tic-tac-toe) 루빅스큐브 (Rubik s cube) 8- 퍼즐문제 순회판매자문제 (traveling salesperson problem, TSP) 8- 퀸 (queen) 문제 해 ( 解, solution) 일련의동작으로구성되거나하나의상태로구성
상태공간과탐색 상태 (state) 특정시점에문제의세계가처해있는모습 세계 (world) 문제에포함된대상들과이들의상황을포괄적으로지칭 상태공간 (state space) 문제해결과정에서초기상태로부터도달할수있는모든상태들의집합 문제의해가될가능성이있는모든상태들의집합 초기상태 (initial state) 문제가주어진시점의시작상태 목표상태 (goal state) 문제에서원하는최종상태
상태공간그래프 (state space graph) 상태공간에서각행동에따른상태의변화를나타낸그래프 노드 : 상태 링크 : 행동 선교사 - 식인종문제 상태공간과탐색 m: 선교사 c: 식인종 일반적인문제에서는상태공간이매우큼 미리상태공간그래프를만들기어려움 탐색과정에서그래프생성 해 (solution) 초기상태에서목표상태로의경로 (path)
2. 맹목적탐색 맹목적탐색 (blind search) 정해진순서에따라상태공간그래프를점차생성해가면서해를탐색하는방법 깊이우선탐색 (depth-first search, DFS) 초기노드에서시작하여깊이방향으로탐색 목표노드에도달하면종료 더이상진행할수없으면, 백트랙킹 (backtracking, 되짚어가기 ) 방문한노드는재방문하지않음 i i i i i i 1 1 1 1 4 1 4 제거 2 2 3 2 3 2 3 5
맹목적탐색 8- 퍼즐문제의깊이우선탐색트리 루트노드에서현재노드까지의경로하나만유지 1 6 4 7 5 1 2 3 8 4 목표상태 1 6 4 7 5 1 4 6 4 1 7 5 1 4 2 3 1 8 4 8 3 2 6 4 1 7 5 6 4 1 7 5 8 3 2 1 4 7 1 4 6 5 2 3 1 8 4 8 3 2 6 4 1 7 5 2 3 6 8 4 1 7 5 6 4 1 7 5 6 7 4 1 5 8 3 2 1 4 7 1 4 6 5 1 2 3 8 4 8 3 2 6 4 1 7 5 8 6 3 2 4 1 7 5 2 3 6 8 4 1 7 5 2 3 6 8 4 1 7 5 2 8 6 4 3 1 7 5 6 4 5 1 7 6 7 4 1 5 6 7 4 1 5 8 3 2 1 4 8 1 3 2 4 7 4 6 1 5 7 1 4 6 5 1 2 3 8 4
맹목적탐색 너비우선탐색 (breadth-first search, BFS) 초기노드에서시작하여모든자식노드를확장하여생성 목표노드가없으면단말노드에서다시자식노드확장 i i i 1 2 1 2 3 4 5
맹목적탐색 8- 퍼즐문제의너비우선탐색트리 전체트리를메모리에서관리 1 6 4 7 5 1 6 4 7 5 1 4 1 6 4 7 5 6 4 1 7 5 1 4 2 3 1 8 4 1 4 1 6 7 5 4 8 3 2 6 4 1 7 5 6 4 1 7 5 8 3 2 1 4 7 1 4 6 5 2 3 1 8 4 2 3 1 8 4 2 8 1 4 3 1 4 5 7 6 1 6 7 5 4 2 8 1 6 3 7 5 4 8 3 2 6 4 1 7 5 2 3 6 8 4 1 7 5 6 4 1 7 5 6 7 4 1 5 8 3 2 1 4 7 1 4 6 5 1 2 3 8 4 2 3 4 1 8 2 8 1 4 3 1 4 5 7 6 1 6 7 5 4 2 3 1 8 6 7 5 4 1 5 6 7 4 2 8 1 6 3 7 5 4 8 3 2 6 4 1 7 5 8 6 3 2 4 1 7 5 2 3 6 8 4 1 7 5 2 3 6 8 4 1 7 5 2 8 6 4 3 1 7 5 6 4 5 1 7 6 7 4 1 5 6 7 4 1 5 8 3 2 1 4 8 1 3 2 4 7 4 6 1 5 7 1 4 6 5 1 2 3 8 4
맹목적탐색 반복적깊이심화탐색 (iterative-deepening search) 깊이한계가있는깊이우선탐색을반복적으로적용 a 깊이 0: a
맹목적탐색 반복적깊이심화탐색 (iterative-deepening search) 깊이한계가있는깊이우선탐색을반복적으로적용 a b c 깊이 0: a 깊이 1: a,b,c
맹목적탐색 반복적깊이심화탐색 (iterative-deepening search) 깊이한계가있는깊이우선탐색을반복적으로적용 a b c d e f g 깊이 0: a 깊이 1: a,b,c 깊이 2: a,b,d,e,c,f,g
맹목적탐색 반복적깊이심화탐색 (iterative-deepening search) 깊이한계가있는깊이우선탐색을반복적으로적용 a b c d e f g h i j k l m n o 깊이 0: a 깊이 1: a,b,c 깊이 2: a,b,d,e,c,f,g 깊이 3: a,b,d,h,i,e,j,k,c,f,l,m,g,n,o
맹목적탐색 반복적깊이심화탐색 (iterative-deepening search) 깊이한계가있는깊이우선탐색을반복적으로적용 a b c d e f h i j k l p q 목표상태 깊이 0: a 깊이 1: a,b,c 깊이 2: a,b,d,e,c,f,g 깊이 3: a,b,d,h,i,e,j,k,c,f,l,m,g,n,o 깊이 4: a,b,d,h,i,p,e,j,k,c,f,l,q
맹목적탐색 맹목적탐색방법의비교 깊이우선탐색 메모리공간사용효율적 최단경로해탐색보장불가 너비우선탐색 최단경로해탐색보장 메모리공간사용비효율 반복적깊이심화탐색 최단경로해보장 메모리공간사용효율적 반복적인깊이우선탐색에따른비효율성 실제비용이크게늘지않음 각노드가 10 개의자식노드를가질때, 너비우선탐색대비약 11% 정도추가노드생성 맹목적탐색적용시우선고려대상
맹목적탐색 양방향탐색 (bidirectional search) 초기노드와목적노드에서동시에너비우선탐색을진행 중간에만나도록하여초기노드에서목표노드로의최단경로를찾는방법 초기상태 목표상태
맹목적탐색
3. 정보이용탐색 정보이용탐색 (informed search) 휴리스틱탐색 (heuristic search) 언덕오르기방법, 최상우선탐색, 빔탐색, A * 알고리즘등 휴리스틱 (heuristic) 그리스어 Εὑρίσκω (Eurisko, 찾다, 발견하다 ) 시간이나정보가불충분하여합리적인판단을할수없거나, 굳이체계적이고합리적인판단을할필요가없는상황에서신속하게어림짐작하는것 예. 최단경로문제에서목적지까지남은거리» 현재위치에서목적지 ( 목표상태 ) 까지지도상의직선거리
정보이용탐색 휴리스틱비용추정의예 최단경로문제 현재위치에서목적지까지직선거리 8- 퍼즐문제 8- 퀸문제 제자리에있지않는타일의개수 충돌하는회수 현재상태 목표상태 추정비용 : 4
정보이용탐색 언덕오르기방법 (hill climbing method) 지역탐색 (local search), 휴리스틱탐색 (heuristic search) 현재노드에서휴리스틱에의한평가값이가장좋은이웃노드하나를확장해가는탐색방법 국소최적해 (local optimal solution) 에빠질가능성
정보이용탐색 최상우선탐색 (best-first search) 확장중인노드들중에서목표노드까지남은거리가가장짧은노드를확장하여탐색 남은거리를정확히알수없으므로휴리스틱사용 제자리가아닌타일의개수 a 4 1 6 4 7 5 b 5 1 6 4 c 3 1 4 d 5 7 5 1 6 4 7 5 e 3 1 4 f 3 2 3 1 8 4 g 4 1 4 8 3 h 3 2 1 4 i 4 7 1 4 6 5 j 3 8 3 2 1 4
빔탐색 (beam search) 정보이용탐색 휴리스틱에의한평가값이우수한일정개수의확장가능한노드만을메모리에관리하면서최상우선탐색을적용
정보이용탐색 A * 알고리즘 추정한전체비용 መf n 을최소로하는노드를확장해가는방법 f n 노드 n 을경유하는전체비용 현재노드 n 까지이미투입된비용 g(n) 과목표노드까지의남은비용 h(n) 의합 f n = g n + h n h(n) : 남은비용의정확한예측불가 h n : h(n) 에대응하는휴리스틱함수 (heuristic function) መf n 노드 n 을경유하는추정전체비용 መf n = g n + h(n)
8- 퍼즐문제의 A * 알고리즘적용 정보이용탐색 0+4 1 6 4 7 5 f n = g n + h n 1+5 1 6 4 1+3 1 4 1+5 7 5 1 6 4 7 5 2+3 1 4 2+3 2 3 1 8 4 2+4 1 4 8 3 3+3 2 1 4 3+4 7 1 4 6 5 2 3 3+2 1 8 4 3+4 2 3 1 8 4 4+1 1 2 3 8 4 1 2 3 5+0 8 4 5+2 목표상태 1 2 3 7 8 4
4. 게임에서의탐색 게임트리 (game tree) 상대가있는게임에서자신과상대방의가능한게임상태를나타낸트리 틱 - 택 - 톡 (tic-tac-toc), 바둑, 장기, 체스등 게임의결과는마지막에결정 많은수 (lookahead) 를볼수록유리 자신 X 상대방 O X O X X O X O X O X O O X O X 자신 X X O X X O... X X O
게임에서의탐색 mini-max 알고리즘 (mini-max algorithm) MAX 노드 자신에해당하는노드로자기에게유리한최대값선택 MIN 노드 상대방에해당하는노드로최소값선택 단말노드부터위로올라가면서최소 (minimum)- 최대 (maximum) 연산을반복하여자신이선택할수있는방법중가장좋은것은값을결정 6 자신 MAX 3 6 5 상대방 MIN 5 3 6 7 5 8 자신 MAX 5 4 3 6 6 7 5 8 6 상대방 MIN 5 6 7 4 5 3 6 6 9 7 5 9 8 6 자신 MAX 판세평가값
게임에서의탐색 - 가지치기 (prunning) 검토해볼필요가없는부분을탐색하지않도록하는기법 깊이우선탐색으로제한깊이까지탐색을하면서, MAX 노드와 MIN 노드의값결정 - 자르기 (cut-off) : MIN 노드의현재값이부모노드의현재값보다작거나같으면, 나머지자식노드탐색중지 - 자르기 : MAX 노드의현재값이부모노드의현재값보다같거나크면, 나머지자식노드탐색중지 36 자신 MAX 53 6 5 상대방 MIN 5 3 6 7 5 자신 MAX 5 74 3 6 6 7 5 상대방 MIN 5 6 7 4 5 3 6 6 9 7 5 9 8 6 자신 MAX 간단한형태의 - 가지치기예
게임에서의탐색 몬테카를로시뮬레이션 (Monte Carlo Simulation) 특정확률분포로부터무작위표본 (random sample) 을생성하고, 이표본에따라행동을하는과정을반복하여결과를확인하고, 이러한결과확인과정을반복하여최종결정을하는것 원안의샘플개수 전체샘플의개수 π 4
몬테카를로트리탐색 몬테카를로트리탐색 (Monte Carlo Tree Search, MCTS) 현재상태 트리정책 기본정책 Coulom (06) Chaslot, Saito & Bouzy (06) Slide from Sylvain Gelly
몬테카를로트리탐색 현재상태 트리정책 기본정책 Slide from Sylvain Gelly
몬테카를로트리탐색 현재상태 트리정책 기본정책 Slide from Sylvain Gelly
몬테카를로트리탐색 현재상태 트리정책 기본정책 Slide from Sylvain Gelly
몬테카를로트리탐색 현재상태 트리정책 기본정책 Slide from Sylvain Gelly
몬테카를로트리탐색 현재상태 Kocsis & Szepesvari (06) Slide from Sylvain Gelly
몬테카를로트리탐색 현재상태 Slide from Sylvain Gelly
몬테카를로트리탐색 현재상태 Slide from Sylvain Gelly
게임에서의탐색 몬테카를로트리탐색 (Monte Carlo Tree Search, MCTS) 탐색공간 (search space) 을무작위표본추출 (random sampling) 을하면서, 탐색트리를확장하여가장좋아보이는것을선택하는휴리스틱탐색방법 4 개단계를반복하여시간이허용하는동안트리확장및시뮬레이션 선택 (selection) 확장 (expansion) 시뮬레이션 (simulation) : 몬테카를로시뮬레이션 역전파 (back propagation) 선택확장시뮬레이션역전파 이긴횟수게임수 ( 방문수 )
몬테카를로트리탐색 cont. 게임에서의탐색 선택 (selection) : 트리정책 (tree policy) 적용 루트노드에서시작 정책에따라자식노드를선택하여단말노드까지내려감 승률과노드방문횟수고려하여선택 UCB(Upper Confidence Bound) 정책 : UCB 가큰것선택 선택확장시뮬레이션역전파 이긴횟수게임수 ( 방문수 ) 활용 (exploitation) 탐험 (exploration) v 부모노드, v : 자식노드 N(v ) : 방문횟수 Q(v ) : 점수 ( 이긴횟수 )
게임에서의탐색 몬테카를로트리탐색 cont. 확장 (expansion) 단말노드에서트리정책에따라노드추가 예. 일정횟수이상시도된수 (move) 가있으면해당수에대한노드추가 시뮬레이션 (simulation) 기본정책 (default policy) 에의한몬테카를로시뮬레이션적용 무작위선택 (random moves) 또는약간똑똑한방법으로게임끝날때까지진행 역전파 (backpropagation) 단말노드에서루트노드까지올라가면서승점반영선택확장시뮬레이션역전파 이긴횟수게임수 ( 방문수 ) 몬테카를로시뮬레이션
몬테카를로트리탐색 몬테카를로트리탐색 cont. 동작선택방법 가장승률이높은, 루트의자식노드선택 가장빈번하게방문한, 루트의자식노드선택 승률과빈도가가장큰, 루트의자식노드선택없으면, 조건을만족하는것이나올때까지탐색반복 자식노드의 confidence bound 값의최소값이가장큰, 루트의자식노드선택 선택확장시뮬레이션역전파 이긴횟수게임수 ( 방문수 )
몬테카를로트리탐색 몬테카를로트리검색 cont. 판의형세판단을위해휴리스틱을사용하는대신, 가능한많은수의몬테카를로시뮬레이션수행 일정조건을만족하는부분은트리로구성하고, 나머지부분은몬테카를로시뮬레이션 가능성이높은수 (move) 들에대해서노드를생성하여트리의탐색폭을줄이고, 트리깊이를늘리지않기위해몬테카를로시뮬레이션을적용 탐색공간축소 선택확장시뮬레이션역전파 이긴횟수게임수 ( 방문수 )
알파고의탐색 알파고의몬테카를로트리검색 바둑판형세판단을위한한가지방법으로몬테카를로트리검색사용 무작위로바둑을두는것이아니라, 프로바둑기사들을기보를학습한확장정책망 (rollout policy network) 이라는간단한계산모델을사용 0.6 정책망 : 가능한착수 ( 着手 ) 들에대한선호확률분포 가치망 : 바둑판의형세값을계산하는계산모델 확률에따라착수를하여몬테카를로시뮬레이션을반복하여해당바둑판에대한형세판단값계산 별도로학습된딥러닝신경망인가치망 (value network) 을사용하여형세판단값을계산하여함께사용
알파고의탐색 알파고의몬테카를로트리검색 많은수의몬테카를로시뮬레이션과딥러닝모델의신속한계산을위해다수의 CPU 와 GPU 를이용한분산처리 https://www.youtube.com/watch?v=94ix97apsls Image : Nature
게임에서의탐색
5. 제약조건만족문제 제약조건만족문제 (constraint satisfaction problem) 주어진제약조건을만족하는조합해 (combinatorial solution) 를찾는문제 예. 8- 퀸 (queen) 문제 탐색기반의해결방법 백트랙킹탐색 제약조건전파 백트랙킹탐색 (backtracking search) 깊이우선탐색을하는것처럼변수에허용되는값을하나씩대입 모든가능한값을대입해서만족하는것이없으면이전단계로돌아가서이전단계의변수에다른값을대입
제약조건만족문제 예. 백트랙킹탐색을이용한 4- 퀸 (queen) 문제
제약조건만족문제 제약조건전파 (constraint propagation) 인접변수간의제약조건에따라각변수에허용될수없는값들을제거하는방식 A B C D A B { 1, 2, 3, 4} { 1, 2, 3, 4} C D { 1, 2, 3, 4} { 1, 2, 3, 4}
제약조건만족문제 제약조건전파 (constraint propagation) 인접변수간의제약조건에따라각변수에허용될수없는값들을제거하는방식 A B C D A B { 1, 2, 3, 4} {,, 3, 4} C {,,, } D {, 2,, } A B C D A B { 1, 2, 3, 4} { 1, 2, 3, 4} C D { 1, 2, 3, 4} { 1, 2, 3, 4}
제약조건만족문제
6. 최적화 최적화 (optimization) 여러가지허용되는값들중에서주어진기준을가장잘만족하는것을선택하는것 목적함수 (objective function) 최소또는최대가되도록만들려는함수 조합최적화 유전알고리즘 함수최적화 최대경사법 제약함수최적화
조합최적화 조합최적화 (combinatorial optimization) 순회판매자문제 (TSP) 와같이주어진항목들의조합으로해가표현되는최적화문제 순회판매자문제의목적함수 : 경로의길이 ( 서울, 인천, 광주, 부산, 울산, 대전, 서울 ) ( 서울, 인천, 대전, 광주, 부산, 울산, 서울 )
유전알고리즘 유전알고리즘 (genetic algorithm, GA) 생물의진화를모방한집단기반의확률적탐색기법 (John Holland, 1975) 대표적인진화연산 (evolutionary computation) 의하나 유전알고리즘, 유전자프로그래밍 (genetic programming), 전화전략 (evolutionary strategy) 생물의진화 염색체 (chromosome) 의유전자 (gene) 들이개체정보코딩 적자생존 (fittest survival)/ 자연선택 (natural selection) 환경에적합도가높은개체의높은생존및후손번성가능성 우수개체들의높은자손증식기회 열등개체들도작지만증식기회 집단 (population) 의진화 세대 (generation) 집단의변화 형질유전과변이 부모유전자들의교차 (crossover) 상속 돌연변이 (mutation) 에의한변이 염색체 유전자
유전알고리즘 유전알고리즘 cont. 생물진화와문제해결 개체 후보해 (candidate solution) 환경 문제 (problem) 적합도 해의품질 (quality) 초기모집단생성적합도함수적합도평가 종료조건 No 부모개체선택자식개체생성 Yes 최적개체 유전연산자 새로운모집단구성
유전알고리즘 유전알고리즘 cont. 후보해 (candidate solution) 표현 염색체 (chromosome) 표현 1 0 1 1 0 1 0 0 0 0 1 0 1 0 1 (0.6 0.8... 1.2 0.9) (E2 E5 E3... E11 E7) 모집단 (population) 동시에존재하는염색체들의집합 적합도함수 (fitness function) 후보해가문제의해 (solution) 로서적합한정도를평가하는함수
유전알고리즘 유전알고리즘 cont. 부모개체선택 (selection) 높은적합도의개체가새로운개체를생성할확률이높도록함 적합도에비례하는선택확률 예. 개체 1 의적합도 : 10, 개체 2 의적합도 : 5, 개체 3 의적합도 : 15 유전연산자 (genetic operator) : 새로운개체생성 교차 (crossover) 연산자 돌연변이 (mutation) 연산자
유전알고리즘 유전알고리즘 cont. 세대 (generation) 교체 엘리트주의 (elitism) 우수한개체를다음세대에유지 선택 교차 현재세대 다음세대 돌연변이
메타휴리스틱 메타휴리스틱 (meta heuristics) 최적해는아니지만우수한해를빠르게찾기위한휴리스틱적인문제해결전략 유전알고리즘 (genetic algorithm) 모방알고리즘 (memetic algorithm) 입자군집최적화 (particle swarm optimization, PSO) 개미집단 (ant colony) 알고리즘 타부탐색 (Tabu search) 담금질기법 (simulated annealing) 하모니탐색 (Harmonic search) 유전프로그래밍 (genetic programming) 이주경로 목적지 개미집 먹이 유전알고리즘모방알고리즘입자군집최적화 개미집단알고리즘 image source: Tarek Hegazy
함수최적화 함수최적화 (function optimization) 어떤목적함수 (objective function) 가있을때, 이함수를최대로하거나최소로하는변수값를찾는최적화문제 Find x 1, x 2 which minimizes f x 1, x 2 = (x 1 1) 2 +x 2 2 목적함수 (objective function) f(x 1, x 2 ) x 1 = 2x 1 2 = 0 x 1 = 1 f(x 1, x 2 ) x 2 = 2x 2 = 0 x 2 = 0 x 1, x 2 = (1,0)
함수최적화 제약조건최적화 (constrained optimization) 제약조건 (constraints) 을만족시키면서목적함수를최적화시키는변수값들을찾는문제 가능해 (feasible solutions) 제약조건 (constraints) 기계학습방법인 SVM 의학습에서사용
함수최적화 제약조건최적화 (constrained optimization) 가능해 (feasible solution) 제약조건 (constraint) 라그랑주 (Lagrange) 함수 : 제약조건들과목적함수결합 최적화방법 FS : 가능해 (feasible solution) 의집합 쌍대함수 (dual function) 쌍대함수를최대화하면서상보적여유성을만족하는 x 1, x 2 를구함상보적여유성 (complementary slackness)
함수최적화 제약조건최적화 (constrained optimization) cont.
함수최적화 회귀 (regression) 문제의최적함수 주어진데이터를가장잘근사 ( 近似, approximation) 하는함수 최소평균제곱법 (least mean square method) 오차함수 (error function) 또는에너지함수 (energy function) 를최소로하는함수를찾는방법 최적화문제
함수최적화 경사하강법 (gradient descent method) 함수의최소값위치를찾는문제에서오차함수의그레디언트 (gradient) 반대방향으로조금씩움직여가며최적의파라미터를찾으려는방법 그레디언트 각파라미터에대해편미분한벡터 데이터의입력과출력을이용하여각파라미터에대한그레디언트를계산하여파라미터를반복적으로조금씩조정 a (t) : 현시점에서파라미터 a 의값 : 학습율 (0 < < 1)
함수최적화 최대경사법 (gradient descent method) 회귀모델, 신경망등의기본학습방법 국소해 (local minima) 에빠질위험 개선된형태의여러방법존재
요약 탐색 상태공간과탐색 상태공간, 상태공간그래프 맹목적탐색 깊이우선탐색, 너비우선탐색, 반복적깊이심화탐색, 양방향탐색 정보이용탐색 휴리스틱, 언덕오르기방법, 최상우선탐색, 빔탐색, A* 알고리즘 게임에서의탐색 게임트리, mini-max 알고리즘, α-β 가지치기, 몬테카를로트리탐색 제약조건만족문제 백트랙킹탐색, 제약조건전파방법 최적화 조합최적화 유전알고리즘, 메타휴리스틱 함수최적화 함수최적화문제, 제약조건최적화, 경사하강법