[AI] Optimization (4-3)

제약 충족 문제(Constraint Satisfaction problem)

제약 충족 문제는 일부 조건을 만족하면서 변수에 값을 할당해야 하는 문제 클래스이다.

제약 충족 문제에는 다음과 같은 속성이 있다.

변수 집합: (x₁, x₂, …, xₙ)
각 변수 {D₁, D₂, …, Dₙ}에 대한 도메인 집합
제약 조건 C의 집

스도쿠는 제약 충족 문제로 표현할 수 있다. 여기서 각각의 빈 사각형은 변수이고 도메인은 1-9의 숫자이며 제약조건은 서로 같을 수 없는 사각형인 것이다.

또 다른 예를 생각해 보자. 학생 1~4는 각각 A, B, …, G의 3과목을 수강하고 있다. 각 과목은 시험을 치러야 하며, 시험 가능 요일은 월요일, 화요일, 수요일이다. 단, 같은 학생이 같은 날 두 번의 시험을 볼 수는 없다.

이 경우 변수 = 과목 코스, 도메인 = 날짜, 제약 조건 = (같은 학생이 수강하기 때문에 같은 날 시험을 치를 수 없는)과목 코스이다. 이는 다음과 같이 시각화할 수 있다.

이 문제는 그래프로 표현되는 제약 조건을 사용하여 해결할 수 있다. 그래프의 각 노드는 과목 코스이며, 같은 날에 코스를 예약할 수 없는 경우 두 코스 사이에 선이 그려진다. 이 경우 그래프는 다음과 같다.

제약 조건 만족 문제에 대해 알아야 할 몇 가지 추가 용어는 다음과 같다:

하드 제약 조건: 올바른 솔루션에서 충족되어야 하는 제약 조건이다.
소프트 제약 조건: 어떤 솔루션이 다른 솔루션보다 선호되는지를 표현하는 제약 조건이다.
단항 제약 조건: 하나의 변수만 포함하는 제약 조건이다. 위 예시에서 단항 제약 조건은 코스 A가 월요일 { A ≠ 월요일 } 에 시험을 볼 수 없다는 것이다.
이진 제약조건: 두 개의 변수를 포함하는 제약조건이다. 이는 위의 예에서 사용한 제약 조건 유형으로, 일부 두 코스는 동일한 값 { A ≠ B }를 가질 수 없다.

노드 일관성(Node consistency)

노드 일관성은 변수 도메인의 모든 값이 변수의 " 단항 제약 조건"을 충족하는 경우이다.

예를 들어 A와 B라는 두 코스를 가정해 보자. 각 코스의 도메인은 { 월요일, 화요일, 수요일 }이고 제약 조건은 { A ≠ Mon, B ≠ Tue, B ≠ Mon, A ≠ B }이다. 이제 A와 B 모두 일관성이 없다. 기존 제약 조건으로 인해 도메인에 있는 모든 값을 사용할 수 없기 때문이다. 그러나 A의 도메인에서 월요일을 제거하면 노드 일관성이 유지된다. B에서 노드 일관성을 얻으려면 해당 도메인에서 월요일과 화요일을 모두 제거해야 한다.

아크 일관성(Arc consistency)

아크 일관성은 변수 도메인의 모든 값이 변수의 " 이진 제약 조건"을 충족하는 경우이다(이전에는 "선"이라고 불렀던 것을 이제 "아크"로 대체할 것이다. 아크 건물 형식의 그 아크 맞다).

즉, X에 대해 Y에 대해 아크 일관되게 만들려면 X에 대한 모든 선택이 Y에 대한 가능한 선택이 될 때까지 X 영역에서 요소를 제거해야 한다.

수정된 도메인(A:{ Tuesday, Wednesday } 및 B:{ Wednesday })가 포함된 이전 예(노드 일관성)를 생각해 보자.

A가 B와 일관되도록 하기 위해서 생각해 보자. A의 시험이 해당 도메인에서 예약된 날짜에 관계없이 B는 여전히 시험을 예약할 수 있다(노드 일관함).

A는 B와 아크 일관하는가?
A가 화요일 값을 취하면 B는 수요일 값을 취할 수 있다. 그러나 A가 수요일 값을 취하면 B가 취할 수 있는 값은 없다(제약 조건 중 하나가 A ≠ B라는 점을 기억하자). 따라서 A는 B와 아크 일관적이지 않는다.
이를 변경하려면 A의 도메인에서 수요일을 제거하면 된다. 그런 다음 A가 취하는 모든 값(화요일은 유일한 옵션)은 B가 취하는 값(수요일)을 남긴다. 이제 A는 B와 아크 일관적이다.

다른 변수와 관련하여 변수를 아크 일관되게 만드는 의사코드 알고리즘을 살펴보자(csp는 "제약 조건 만족 문제"를 나타냄).

function Revise(csp, X, Y):

revised = false
for x in X.domain:
- if no y in Y.domain satisfies constraint for (X, Y):
  - delete x from X.domain
  - revised = true
return revised

이 알고리즘은 revised 변수를 사용하여 X의 도메인이 변경되었는지 추적하는 것으로 시작한다. 이는 우리가 조사하는 다음 알고리즘에서 유용하다. 그런 다음, 코드는 X 도메인의 모든 값에 대해 반복되고 Y가 제약 조건을 충족하는 값이 있는지 확인한다. 맞다면 아무것도 하지 않고, 그렇지 않다면 X의 도메인에서 이 값을 제거한다.

종종 우리는 다른 변수에 대한 하나의 변수가 아니라 전체 문제를 일관되게 만드는 데 관심이 있다. 이 경우 Revise를 사용하는 AC-3이라는 알고리즘을 사용한다.

function AC-3(csp):

queue = all arcs in csp
while queue non-empty:
- (X, Y) = Dequeue(queue)
- if Revise(csp, X, Y):
  - if size of X.domain == 0:
    - return false
  - for each Z in X.neighbors - {Y}:
    - Enqueue(queue, (Z, X))
return true

이 알고리즘은 문제의 모든 아크를 큐(queue)에 추가한다. 아크를 고려할 때마다 큐에서 아크를 제거한다. 그런 다음 Revise 알고리즘을 실행하여 이 아크가 일관성이 있는지 확인한다.

일관성을 유지하기 위해 변경한 경우(if Revise(csp, X, Y)), 다음 action이 필요하다.
X의 결과 도메인이 비어 있는 경우(if size of X.domain == 0), 이는 이 제약 조건 충족 문제를 해결할 수 없음을 의미한다(X가 취할 수 있는 값이 없기 때문에 Y가 제약 조건에 따라 어떤 값도 취할 수 없도록 허용함).
이전 단계에서 문제가 해결 불가능한 것으로 간주되지 않은 경우(for each Z in X.neighbors - {Y}), X의 도메인이 변경되었으므로 X와 관련된 모든 아크가 여전히 일관성이 있는지 확인해야 한다. 즉, Y를 제외한 X의 모든 이웃을 취하고, 그들과 X 사이의 아크를 대기열에 추가한다.
그러나 Revise 알고리즘이 false를 반환하면(도메인이 변경되지 않았음을 의미 = while문 탈출) 다른 아크를 계속해서 고려하면 된다.

아크 일관성을 위한 알고리즘은 문제를 단순화할 수 있지만 반드시 문제를 해결하지는 않는다. 왜냐하면 이진 제약 조건만 고려하고 여러 노드가 어떻게 상호 연결될 수 있는지 고려하지 않기 때문이다. 실제로 4명의 학생이 각각 3과목을 수강하는 이전 예에서는 AC-3을 실행해도 변경되지 않는다.

첫 번째 강의에서 탐색(search) 문제에 직면했었다. 아래의 이유로 제약 충족 문제는 검색 문제로도 보인다:

Initial state: 비어있는 할당 (모든 변수에는 할당된 값이 없다).
Actions: 할당에 { 변수 = 값 }을 추가한다. 즉, 일부 변수에 값을 제공하는 것.
Transition model: 할당을 추가하면 할당이 어떻게 변경되는지 보여준다. 여기는 별로 깊지 없다: Transition model은 최신 작업 이후의 할당을 포함하는 상태를 반환한다.
Goal test: 모든 변수에 값이 할당되고 모든 제약 조건이 충족되는지 확인한다.
Path cost function: 모든 경로의 비용은 동일합니다. 앞서 언급했듯이 일반적인 검색 문제와 달리 최적화 문제는 솔루션에 대한 경로가 아니라 솔루션 자체에 관심을 둔다.

그러나 일반적인 검색 문제처럼 제약 충족 문제를 순진하게 처리하는 것은 매우 비효율적이다. 대신 제약 충족 문제의 구조를 활용하여 검색문제처럼 처리하는 보다 효율적으로 해결할 수 있다.

역추적 탐색(Backtracking search)

역추적 탐색은 제약 충족 문제의 구조를 고려한 탐색(search) 알고리즘의 일종이다. 일반적으로 제약 조건을 만족하는 한 값을 계속 할당하려고 시도하는 재귀 함수이다. 제약 조건을 위반하면 다른 할당을 시도한다. 이에 대한 의사코드를 살펴보자:

function Backtrack(assignment, csp):

if assignment complete:
- return assignment
var = Select-Unassigned-Var(assignment, csp)
for value in Domain-Values(var, assignment, csp):
- if value consistent with assignment:
  - add {var = value} to assignment
  - result = Backtrack(assignment, csp)
  - if result ≠ failure:
    - return result
  - remove {var = value} from assignment
return failure

이 알고리즘은 완료되면 현재 할당(assignment)을 반환하는 것으로 시작한다.

이는 알고리즘이 완료되면(if assignment complete), 추가 작업을 수행하지 않는다는 것이다. 대신 완료된 할당만 반환한다.
할당(assingment)이 완료되지 않은 경우(var = Select-Unassigned-Var(assignment, csp)), 알고리즘은 아직 할당되지 않은 변수를 선택한다. 그런 다음 알고리즘은 변수에 값을 할당하려고 시도하고 결과 할당(재귀)에 대해 역추적 알고리즘을 다시 실행한다. 그런 다음 결과 값을 확인한다.
실패가 아닌 경우(if result ≠ failure), 할당이 제대로 수행되었음을 의미하며 이 할당을 반환한다.
결과 값이 실패인 경우(remove {var = value} from assignment), 최신 할당이 제거되고 가능한 새 값이 시도되어 동일한 프로세스가 반복된다.
도메인의 가능한 모든 값이 실패를 반환한 경우(return failure), 이는 역추적해야 함을 의미한다. 즉, 이전 과제에 문제가 있다는 것이다. 시작하는 변수에서 이런 일이 발생하면 제약 조건을 충족하는 솔루션이 없음을 의미한다.

다음 과정을 보며 생각해 보자:

1. 빈 할당(왼쪽 위)부터 시작한다.

2. 그런 다음 변수 A를 선택하고 여기에 월요일(오른쪽 상단)이라는 값을 할당한다. 그런 다음 이 할당을 사용하여 알고리즘을 다시 실행한다.

3. 이제 A에는 이미 할당이 있으므로 알고리즘은 B를 고려하여 월요일을 B에 할당한다(왼쪽 아래).

4. 이 할당은 false를 반환하므로 이전 할당에 따라 C에 값을 할당하는 대신 알고리즘은 화요일(오른쪽 아래) B에 새 값을 할당하려고 시도한다. 이 새로운 할당은 제약 조건을 충족하며, 이 할당이 주어지면 다음에 새로운 변수가 고려된다.

예를 들어 B에 화요일이나 수요일을 할당하는 것이 실패하게 되면 알고리즘은 A를 다시 고려하여 화요일에 다른 값을 할당하는 것으로 되돌아가진다. 화요일과 수요일에도 실패가 반환 되면 가능한 모든 할당을 시도했지만 문제를 해결할 수 없다는 의미다.

아래 소스 코드를 보면 역추적 알고리즘의 처음부터 구현을 찾을 수 있다. 그러나 이 알고리즘은 널리 사용되므로 여러 라이브러리에 이미 해당 알고리즘의 구현이 포함되어 있다.

"""
Naive backtracking search without any heuristics or inference.
"""

VARIABLES = ["A", "B", "C", "D", "E", "F", "G"]
CONSTRAINTS = [
    ("A", "B"),
    ("A", "C"),
    ("B", "C"),
    ("B", "D"),
    ("B", "E"),
    ("C", "E"),
    ("C", "F"),
    ("D", "E"),
    ("E", "F"),
    ("E", "G"),
    ("F", "G")
]


def backtrack(assignment):
    """Runs backtracking search to find an assignment."""

    # Check if assignment is complete
    if len(assignment) == len(VARIABLES):
        return assignment

    # Try a new variable
    var = select_unassigned_variable(assignment)
    for value in ["Monday", "Tuesday", "Wednesday"]:
        new_assignment = assignment.copy()
        new_assignment[var] = value
        if consistent(new_assignment):
            result = backtrack(new_assignment)
            if result is not None:
                return result
    return None


def select_unassigned_variable(assignment):
    """Chooses a variable not yet assigned, in order."""
    for variable in VARIABLES:
        if variable not in assignment:
            return variable
    return None


def consistent(assignment):
    """Checks to see if an assignment is consistent."""
    for (x, y) in CONSTRAINTS:

        # Only consider arcs where both are assigned
        if x not in assignment or y not in assignment:
            continue

        # If both have same value, then not consistent
        if assignment[x] == assignment[y]:
            return False

    # If nothing inconsistent, then assignment is consistent
    return True


solution = backtrack(dict())
print(solution)

추론(Inference)

역추적 검색은 단순 검색보다 효율적이지만 여전히 많은 계산 능력이 필요하다. 반면에 아크 일관성을 적용하는 것은 자원 사용도가 낮다. 역추적 검색에 추론(아크 일관성 강화)을 삽입(interleaving)함으로써, 보다 효율적인 알고리즘을 얻을 수 있다.

이 알고리즘을 유지 아크 일관성 알고리즘(Maintaining Arc-Consistency algorithm)이라고 한다. 이 알고리즘은 역추적 검색을 새로 할당할 때마다 아크 일관성을 적용한다. 특히, X에 새로운 할당을 한 후, AC-3 알고리즘을 호출하고 Y는 X의 이웃인 모든 아크의 큐( Y,X )로 시작한다 (그리고 이 문제에서 모든 아크의 큐는 아니다. 깐부인 아크의 큐만 시작).

다음은 아크 일관성을 유지하는 revised 역추적 알고리즘이며 의사코드 내의 굵은 글씨는 새로 추가된 내용이다.

function Backtrack(assignment, csp):

if assignment complete:
- return assignment
var = Select-Unassigned-Var(assignment, csp)
for value in Domain-Values(var, assignment, csp):
- if value consistent with assignment:
  - add {var = value} to assignment
  - inferences = Inference(assignment, csp)
  - if inferences ≠ failure:
    - add inferences to assignment
  - result = Backtrack(assignment, csp)
  - if result ≠ failure:
    - return result
  - remove {var = value} and inferences from assignment
return failure

추론 함수는 설명한 대로 AC-3 알고리즘을 실행시킨다. 그 출력은 아크 일관성을 적용하여 만들 수 있는 모든 추론이다. 말 그대로 이전 할당(assignment)과 제약 충족 문제의 구조로부터 추론할 수 있는 새로운 할당이다.

추론 효울성 강화

알고리즘을 보다 효율적으로 만드는 추가 방법이 있다. 지금까지는 할당되지 않은 변수를 무작위로 선택했었다. 그러나 일부 선택은 다른 선택보다 더 빠르게 솔루션을 가져올 가능성이 높다. 이를 위해서는 휴리스틱의 사용이 필요하다. 휴리스틱은 최선의 선택이다. 즉, 순진하게 접근 방식을 따르는 것보다 더 나은 결과를 가져올 가능성이 높지만, 반드시 그렇게 된다는 보장은 없다(최적화니깐~).

최소 잔여 값(MRV: Minimum Remaining Values) 휴리스틱은 휴리스틱 중 하나다. 여기서의 아이디어는 변수의 도메인이 추론에 의해 제한되었고, 이제는 하나의 값만 남게 된 경우(또는 두 개의 값인 경우에도), 이 할당을 수행함으로써 나중에 수행해야 할 역추적 횟수를 줄일 수 있다는 것이다.

즉, 이 할당은 아크 일관성을 적용함으로써 추론되므로 언젠간 이 할당을 수행해야 한다. 이 할당이 실패하게 되면, 가능한 한 빨리 이 값에 대해 알아보고 나중에 역추적하지 않는 것이 좋다(아까 말했듯이 가능성이 높은 거 먼저 하는 것).

예를 들어, 현재 할당된 변수의 영역을 좁힌 후, MRV 휴리스틱을 사용하여 다음으로 변수 C를 선택하고 여기에 수요일 값을 할당한다.

정도 휴리스틱(Degree heuristic)은 변수의 정도(degree)에 의존한다. 여기서 정도(degree)는 변수를 다른 변수에 연결하는 아크의 수이다. 한 번의 할당으로 가장 높은 수준의 변수를 선택함으로써 여러 다른 변수를 제한하여 알고리즘 프로세스를 가속화한다.

예를 들어 위의 모든 변수는 동일한 크기의 도메인을 갖는다. 따라서 가장 높은 정도를 갖는 도메인인 변수 E(5개)를 선택한다.

두 가지 휴리스틱이 항상 적용되는 것은 아니다. 예를 들어, 여러 변수가 해당 정의역에서 동일한 최소 개수의 값을 갖거나 여러 변수의 최고 차수가 동일한 경우가 있다.

알고리즘을 더욱 효율적으로 만드는 또 다른 방법은 변수 영역에서 값을 선택할 때, 또 다른 휴리스틱을 사용하는 것이다. 여기서는 최소한의 다른 변수를 제한하는 값을 선택하는 최소 제한 값(Least Constraining Values) 휴리스틱을 사용하려고 한다.

여기서 아이디어는 정도 휴리스틱에서는 다른 변수를 제한할 가능성이 더 높은 변수를 사용하고 싶었지만, 여기서는 이 변수가 다른 변수에 최소한의 제한을 두기를 원한다는 것이다. 즉, 우리는 문제의 가장 큰 잠재적 원인이 될 수 있는 것(가장 높은 정도를 가진 변수)을 찾은 다음 가능한 한 가장 덜 문제가 되도록 만다(최소 제한 값을 할당).

예를 들어, 변수 C를 생각해 보자. 화요일을 할당하면 B, E, F 모두에 제한을 가하게 된다. 그러나 수요일을 선택하면 B, E에만 제한을 가하게 된다. 아마도 수요일에 가는 것(최소 제한 값)을 선택하는 것이 더 나을 것 같다.

이로써 마지막으로 조건 충족 문제를 알아보면서 최적화 문제를 알아봤다. 다음은 Learning에 대해 알아보자. 빠이~

'인공지능 > 인공지능개론' 카테고리의 다른 글

[AI] Uncertainty (3-2) (1)	2024.06.24
[AI] Learning (5-1) (0)	2024.06.21
[AI] Optimization (4-2) (0)	2024.06.05
[AI] Optimization (4-1) (1)	2024.06.05
[AI] Uncertainty(3-1) (0)	2024.04.24

정보보안공부

[AI] Optimization (4-3)

'인공지능 > 인공지능개론' 카테고리의 다른 글

티스토리툴바

[AI] Optimization (4-3)

'인공지능 > 인공지능개론' 카테고리의 다른 글

관련글

티스토리툴바