CSP vs BFS vs GA for N-Queen

- Constraint Satisfaction Problem (CSP; 제약 만족 문제)

- 사람이 수행하는 systematic적인 search를 효과적으로 할 수 있도록 하며 검색 공간을 줄여주는 방법임

- 문제를 해결하는 제약조건을 이용하여 결과를 검사하고 결과를 만들어 낼 때도 사용됨

- 체계적으로 optimal한 값을 찾으며, trace를 원할 때에는 CSP가 유리함

- 어떤 문제에 대해 제약조건만을 바꿔주면 문제를 해결할 수 있음 (독립적)

- 탐색 중 제약조건을 하나라도 어긋나면 탐색을 중지하는 예측적 성향도 있음

- Best First Search (BFS; 최적 우선 탐색)

- Stochastic적인 search를 하는 방법임

- Heuristic search의 한 종류로 얼마나 효과적인 heuristic function을 사용하느냐에 따라 문제를 해결하는 속도가 좌우됨

- 문제마다 평가함수(evaluation function)를 새로 작성해야 하므로 문제에 대하여 종속적임

- Genetic Algorithm (유전 알고리즘)

- Stochastic적인 search를 하는 방법임

- 식물이나 동물의 유전자 모양으로 search를 하는 것임

- 결과를 못 찾을 수도 있으며, 결과를 찾는다 하여도 찾는 과정은 알 수 없음(trace 불가능)

- near optimal 값을 찾기 쉽고, parallel 처리가 가능하고 local maximum에 빠지지 않는 장점이 있음

- 단점으로 답 사이로 값들이 진행될 수 있고, trace가 불가능 함

- 문제를 어떻게 gene으로 묘사하느냐에 따라 해결 속도와 near optimal를 찾는 것이 다름

- CSP vs BFS vs GA

CSP	BFS	GA
Systematic search	Stochastic search	Stochastic search
체계적으로 Optimal를 찾을 수 있음  (단 존재한다면)	Near optimal를 쉽게 찾을 수 있음	Near optimal를 쉽게 찾을 수 있음  결과를 못찾을 수도 있음  불필요한 시간이 소요될 수 있음
Constraint에 따라 search space를  filtering 하여 문제를 해결 가능	어떤 Heuristic function을 사용했는지에  따라 수행속도가 다름	Gene을 어떻게 표현하였는지와  operator의 사용에 따라 다름
Constraint 자체가 heuristic	각 state를 평가할 수 있는  heuristic function	확률 자체가 heuristic임  병렬 탐색 가능
trace 가능	trace 가능	trace 불가능

- N-Queen problem

- N * N 크기의 체스판 위에 n 개의 퀸이 서로를 공격하지 못하는 위치에 배치하는 문제

- 어느 행, 열, 또는 대각선에도 반드시 하나의 퀸만이 있어야 한다는 제약조건하에서 행과 열에 하나씩 배치하는 문제

- NP-Hard문제, 체스판의 크기가 커질수록 탐색 공간이 기하급수적으로 커지는 특성이 있음

- CSP : 4-Queen 문제의 경우

- domain variable = { Q1, Q2, Q3, Q4 }

- domain value = { 1, 2, 3, 4 }

- constraint  = { Q1 ≠ Q2, Q2 ≠ Q3, Q3 ≠ Q4, Q1 ≠ Q2-1, Q1 ≠ Q2+1, ... }

- 다음과 깉은 트리에서 검색할 때 위의 제약조건에 맞지 않는 노드는 더 이상 그 하위 노드를 검색하지 않는다.

- 모든 Tree를 가지고 검색하는 일반적인 검색보다 제약 조건을 두어 조건을 만족하지 않는 Tree의 가지를 검사하지 않음으로서 시간적으로 수행 능력이 향상된다.

Back tracking	Forward checking

- GA : 8-Queen 문제의 경우

- 염색체 표현 방법

- Random number

Queen이 위치할 좌표ㅡㄹ 숫자로 표현, 구현간단, 무효한 해가 많이 나옴

- Linear Random number

Queen의 좌표는 가로와 세로 어느 방향으로도 같은 위치를 가질수 없음에 착안

염색체에서 나타나는 숫자를 체스판의 각 열(또는 행)에 매칭

- Permutation

위 방법을 더욱 개선한 방식, Queen이 행 또는 열 상에서 충돌하는 해가 발생하지 않음을 보장

- Fitness function 

서로 공격하지 않는 Queen의 수

N이 목표값이며 높을 수록 좋음

- 랜덤한 Initial population을 생성하고 각 해의 fitness 함수 값을 계산

- Selection : 평가 값에 따라 해의 쌍을 선택

- Cross-over : 선택된 쌍의 값을 랜덤하게 교환

- Mutation : 랜덤한 값을 변경

- 위와 같은 한 번의 새대가 지난 후 다시 평가

- 각 연산자가 적용되는 모습

- Cross-over 연산자가 적용되는 모습

<끝>

블로그 내의 관련 글

2009/07/01 - [Study/Artificial Intelligence] - 유전 알고리즘(Genetic Algorithm)

2010/09/30 - [Study/Artificial Intelligence] - Genetic Algorithm (GA; 유전 알고리즘)