Traditional Methods – Part 1
Exhaustive Search Exhaustive search search space 내의 모든 가능한 solution 탐색 global solution 가능, but search space 가 작은 경우에만 사용 가능 알고리즘 단순 어떻게 가능한 solution 들을 순차적으로 발생시키는 가?
Exhaustive Search SAT : n-bits binary string을 어떻게 생성할 것인가? <방법 1> 0 ~ 2 𝑛−1 의 정수 생성 각 정수를 bit 의 2 진수로 변환 (ex) 0 → 0000, 1 → 0001, 2 → 0010, ...... , 15 → 1111 <방법 2> (0 0 ... 0 )에서 시작 (0 0 ... 1 )을 더하여 새로운 string 생성
Exhaustive Search SAT <방법 3> depth-first search search space 중 일부를 제거하고 탐색 진행 가능 (ex) or => 하위 노드에 대한 탐색 불필요
Exhaustive Search TSP n 개의 자연수 (도시) 에 대한 순열 (permutation, 방문순서)를 어떻게 생성할 것인가? (ex) n = 3 (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2) (3,2,1)
Exhaustive Search NLP : 실수 𝑥 1 , ⋯, 𝑥 𝑛 에 대한 탐색 cell 생성 ∆ 𝑥 1 =0.01 , ∆ 𝑥 2 =0.02, => 𝑥 1 : 400 intervals 𝑥 2 : 600 intervals => total 400 x 600 = 240,000 cells
Local Search Search space Procedure ※ 'transformation'을 어떻게 정의할 것인가? exhaustive search: entire space local search: local neighborhood Procedure S1. Pick a solution from the search space and evaluate its merit. Define this as the current solution S2. Apply a transformation to the current solution to generate a new solution and evaluate its merit. S3. If the new solution is better than the current solution then exchange it with the current solution; otherwise discard the new solution. S4. Repeat S2 and S3 until no transformation in the given set improves the current solution. ※ 'transformation'을 어떻게 정의할 것인가? ※ 'initial solution'을 어떻게 결정할 것인가?
Local Search SAT Neighborhood: 1-flip mapping
Local Search TSP <방법1> 2-opt ☞ k-opt Neighborhood: 2-swap mapping ☞ k-opt
Local Search TSP <방법 2> Lin-Kernighan (LK) Algorithm 𝛿-path
Local Search NLP - Update rule: steepest decent <방법> Gradient Method of minimization min 𝑓(𝒙) - Update rule: steepest decent - Newton's method : Hessian matrix
Local Search NLP (ex)
Linear Programming LP Problem LP problem → CP (convex programming) problem
Linear Programming Production scheduling problem Profit chair : $20 / unit table : $30 / unit Requirements Problem determines the number of chairs and tables produced to maximize factory's profit Wood (unit) Labor (hour) Chair 1 3 Table 6 Total available 288 99