Traditional Methods – Part 1

Presentation on theme: "Traditional Methods – Part 1"— Presentation transcript:

1 Traditional Methods – Part 1

2 Exhaustive Search Exhaustive search search space 내의 모든 가능한 solution 탐색
global solution 가능, but search space 가 작은 경우에만 사용 가능 알고리즘 단순 어떻게 가능한 solution 들을 순차적으로 발생시키는 가?

3 Exhaustive Search SAT : n-bits binary string을 어떻게 생성할 것인가?
<방법 1> 0 ~ 2 𝑛−1 의 정수 생성 각 정수를 bit 의 2 진수로 변환 (ex) 0 → 0000, 1 → 0001, 2 → 0010, , 15 → 1111 <방법 2> ( )에서 시작 ( )을 더하여 새로운 string 생성

4 Exhaustive Search SAT <방법 3> depth-first search
search space 중 일부를 제거하고 탐색 진행 가능 (ex) or => 하위 노드에 대한 탐색 불필요

5 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)

6 Exhaustive Search NLP : 실수 𝑥 1 , ⋯, 𝑥 𝑛 에 대한 탐색 cell 생성
∆ 𝑥 1 = , ∆ 𝑥 2 =0.02, => 𝑥 1 : 400 intervals 𝑥 2 : 600 intervals => total 400 x 600 = 240,000 cells

7 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'을 어떻게 결정할 것인가?

8 Local Search SAT Neighborhood: 1-flip mapping

9 Local Search TSP <방법1> 2-opt ☞ k-opt
Neighborhood: 2-swap mapping ☞ k-opt

10 Local Search TSP <방법 2> Lin-Kernighan (LK) Algorithm 𝛿-path

11 Local Search NLP - Update rule: steepest decent
<방법> Gradient Method of minimization min 𝑓(𝒙) - Update rule: steepest decent - Newton's method : Hessian matrix

12 Local Search NLP (ex)

13 Linear Programming LP Problem
LP problem → CP (convex programming) problem

14 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