AI/Concepts

[AI/Concepts] 07. Optimization

lumana 2024. 11. 19. 21:43

최적화 및 탐색 알고리즘 개요

최적화 (Optimization)

정의: 가능한 여러 옵션 중에서 최선의 옵션을 선택하는 것.
문제 해결 도구: 비용을 최소화하는 방법을 찾는 것 등 더 넓은 범위의 문제 해결.
탐색 문제: 최선의 방법을 찾는 문제.
탐색 방법: 그 중 하나로 지역 탐색이 있음.

지역 탐색 (Local Search)

정의: 단일 노드를 유지하고 인접 노드로 이동하여 탐색하는 알고리즘.
미로 해결과의 비교:
- 미로: 목표까지 가장 빠른 경로를 찾음.
- 지역 탐색: 질문에 대한 최선의 답을 찾는 데 중점.
특징:
- 종종 최적의 답을 찾지는 못하지만, "충분히 좋은" 답을 찾아 계산 자원을 절약함.

예시: 병원 위치 선정

평가 기준: 이동 거리를 비용(cost)으로 사용.
현재 결정의 평가 기준: 현재 decision이 얼마나 좋은지 평가하기 위해 기준이 필요함.
State-Space Landscape:
- 전지적인 신의 관점에서 전체 상태 공간을 봄.
- Global Maximum: 모든 상태 중 가장 높은 값을 가지는 상태.
- Local Maximum: 인접 상태보다 높은 값을 가지는 상태.
- Flat Local Maximum: 동일한 값의 여러 상태가 인접하여 고원(pateau)을 형성하고 neighbors의 값이 더 나쁜 상태.
- Shoulder: 동일한 값의 여러 상태가 인접하고 고원의 이웃이 더 좋을 수도 있고 나쁠 수도 있음.
- 출발점에 따라 local maximum에 갇힐 수도 있음.

목적 함수 (Objective Function)

정의: 솔루션의 가치를 극대화(또는 최소화)하는 함수.
요소:
- Current State: 현재 상태.
- Neighbor State: 현재 상태에서 전환할 수 있는 이웃 상태.
1차원 상태 공간 지형에서 이웃 상태: 현재 상태의 양쪽에 있는 상태.
- 예: 병원 하나를 한 걸음 옮기는 상태가 이웃 상태일 수 있음.
이웃 상태의 특징: 현재 상태와 유사하며, 그 값도 현재 상태 값에 근접.

힐 클라이밍 (Hill Climbing)

정의: 지역 탐색 알고리즘 중 하나.
동작 방식:
1. 현재 상태와 이웃 상태를 비교.
2. 이웃 상태가 더 나으면 현재 상태를 이웃 상태로 변경.
목적 함수 기준: "더 나은"의 기준은 목적 함수(objective function)를 사용해 정의됨.
- 더 높은 값을 선호하거나 더 낮은 값을 선호하는 경우로 나눌 수 있음.

힐 클라이밍 함수 예제

def HILL_CLIMB(problem):
    current = initial_state_of_problem
    while True:
        neighbor = select_best_neighbor(current)
        if not better(neighbor, current):
            return current
        current = neighbor

힐 클라이밍의 변형

Steepest-Ascent: 가장 높은 값을 가진 이웃 선택.
Stochastic: 더 높은 값을 가진 이웃 중 무작위로 선택(비중이 높은 것 중에서).
First-Choice: 처음으로 더 높은 값을 가진 이웃 선택.
주요 방법:
- Random-Restart: 힐 클라이밍을 여러 번 수행.
  - 시작점을 여러 군데에 두어 여러 번 수행해봄.
- Local Beam Search: 재귀적으로 k개의 높은 값을 가진 이웃들을 선택.
  - 로컬 빔 탐색은 k개의 상태를 유지하고, 각 상태의 이웃 상태 중에서 가장 좋은 상태들을 선택하여 계속해서 탐색함.

시뮬레이티드 어닐링 (Simulated Annealing)

정의: 힐 클라이밍의 단점을 보완하는 알고리즘.
동작 방식:
- 초기에는 높은 "온도" 상태에서 무작위적인 결정을 많이 내림.
- 온도가 낮아질수록 무작위적인 결정을 줄여가며 최적해를 향해 수렴.
장점: 로컬 최대치에 갇혔을 때 벗어날 수 있음.
메커니즘: 알고리즘이 현재 상태보다 더 나쁜 이웃으로 상태를 변경할 수 있도록 도와줌.

시뮬레이티드 어닐링 함수 예제

import math
import random

def SIMULATED_ANNEALING(problem, max_iter):
    current = initial_state(problem)
    for t in range(1, max_iter + 1):
        T = temperature(t)
        neighbor = random_neighbor(current)
        delta_E = evaluate(neighbor) - evaluate(current)
        if delta_E > 0 or math.exp(delta_E / T) > random.random():
            current = neighbor
    return current

여행하는 판매원 문제 (Traveling Salesman Problem, TSP)

정의: 모든 지점을 한 번씩 방문하고 가장 짧은 경로를 찾는 문제.
특징:
- 이웃 상태는 두 개의 경로가 바뀐 상태.
- 가능한 모든 경로는 매우 많아 계산 복잡도가 높음.
해결 방법: 시뮬레이티드 어닐링 등 효율적인 탐색 알고리즘 사용.
실생활 예시: 배달 회사가 매장에서 고객들의 집을 경유하며 가장 짧은 경로를 찾아야 함.
이웃 상태의 정의: 두 개의 경로가 바뀌는 상태로 볼 수 있음.
복잡도: 10개의 지점만 있어도 10!개의 가능한 경로가 존재.
알고리즘 선택 이유: 시뮬레이티드 어닐링 알고리즘을 사용하면 계산 비용을 줄이면서도 좋은 해결책을 찾을 수 있음.

선형 프로그래밍 (Linear Programming)

정의: 비용 함수를 최소화 또는 최대화하는 수학적 모델.
구성 요소:
- 비용 함수: 예) (50x_1 + 80x_2)
- 제약 조건: 예) (5x_1 + 2x_2 \leq 20), (-10x_1 - 12x_2 \leq -90)
- 변수 경계: 예) (0 \leq x_1 \leq 200), (0 \leq x_2 \leq 300)

선형 프로그래밍 예시

문제 설정:
- 두 기계 (x_1)과 (x_2).
- (x_1)은 시간당 50달러, (x_2)는 시간당 80달러 소요.
- 목표는 비용을 최소화.
- (x_1)은 시간당 5단위의 노동 필요, (x_2)는 2단위의 노동 필요. 총 20단위의 노동 가능.
- (x_1)은 시간당 10단위의 생산, (x_2)는 12단위의 생산. 회사는 90단위의 생산량 필요.
모델 구성:
1. 비용 함수: (50x_1 + 80x_2)
2. 제약 조건:
  - (5x_1 + 2x_2 \leq 20)
  - (-10x_1 - 12x_2 \leq -90) (또는 (10x_1 + 12x_2 \geq 90))
3. 변수 경계: (x_1, x_2 \geq 0)

Simplex 알고리즘 예제

import scipy.optimize

# 목적 함수: 50x1 + 80x2
c = [50, 80]

# 제약 조건
A = [
    [5, 2],
    [-10, -12]
]
b = [20, -90]

# 변수의 경계
x0_bounds = (0, 200)
x1_bounds = (0, 300)

result = scipy.optimize.linprog(
    c, 
    A_ub=A, 
    b_ub=b, 
    bounds=[x0_bounds, x1_bounds]
)

if result.success:
    print(f"X1: {round(result.x[0], 2)} 시간")
    print(f"X2: {round(result.x[1], 2)} 시간")
else:
    print("해결책 없음")

설명:
- 비용 함수를 최소화하기 위해 scipy.optimize.linprog를 사용.
- 제약 조건과 변수의 경계를 설정.
- 최적해가 존재하면 결과 출력, 아니면 해결책 없음 메시지 출력.

제약 만족 문제 (Constraint Satisfaction Problem, CSP)

정의: 변수를 특정 값으로 할당할 때, 특정 조건을 만족시켜야 하는 문제.
제약 조건의 분류:
- Hard Constraint: 반드시 만족해야 하는 제약 조건.
- Soft Constraint: 다른 해결책보다 우선시되는 제약 조건. 예) SVM.
- Unary Constraint: 하나의 변수만 포함하는 제약 조건.
  - 예: 과목 A는 월요일에 시험을 치를 수 없다.
- Binary Constraint: 두 변수를 포함하는 제약 조건.
  - 예: 두 과목이 동일한 시험 시간을 가질 수 없다.

제약 만족 문제 예시

문제:
- 과목 A는 월요일에 시험을 치를 수 없다.
- 두 과목이 동일한 시험 시간을 가질 수 없다.
초기 도메인:
- (A = {\text{월, 화, 수}})
- (B = {\text{월, 화, 수}})
노드 일관성:
- (A = {\text{화, 수}}) (월요일 제거)
- (B = {\text{수}}) (화요일과 월요일 제거)

아크 일관성 (Arc Consistency)

정의: 변수의 도메인 내 모든 값이 이항 제약 조건을 만족하는 상태.
과정:
1. 변수 간의 아크 일관성을 체크.
2. 필요 시 도메인을 축소.

AC-3 알고리즘 예제

def REVISE(csp, X, Y):
    revised = False
    for x in list(X.domain):
        if not any(constraint(x, y) for y in Y.domain):
            X.domain.remove(x)
            revised = True
    return revised

def AC_3(csp):
    queue = list(csp.all_arcs())
    while queue:
        (X, Y) = queue.pop(0)
        if REVISE(csp, X, Y):
            if not X.domain:
                return False
            for Z in csp.neighbors(X):
                if Z != Y:
                    queue.append((Z, X))
    return True

설명:
- REVISE 함수는 변수 (X)의 도메인에서 (Y)와의 제약 조건을 만족하지 않는 값을 제거함.
- AC_3 함수는 모든 아크를 큐에 넣고, 반복적으로 아크 일관성을 유지함.
- 도메인이 비어있으면 문제 해결 불가를 반환.

탐색 문제로서의 제약 만족 문제 (CSPs as Search Problems)

구성 요소:
- 초기 상태: 아무 변수도 할당되지 않음.
- 액션: 할당에 변수를 추가 (({변수 = 값})).
- 전이 모델: 할당에 변수를 추가할 때 할당이 어떻게 변화하는지.
- 목표 테스트: 모든 변수가 할당되고 모든 제약 조건을 만족하는지 확인.
- 경로 비용 함수: 모든 경로는 동일한 비용을 가짐.

백트래킹 탐색 (Backtracking Search)

동작 방식:
1. 변수를 하나 선택.
2. 가능한 값을 루프 돌며 할당 시도.
3. 할당이 유효하면 재귀적으로 다음 변수 할당.
4. 할당이 실패하면 이전 할당으로 돌아감.

백트래킹 함수 예제

def BACKTRACK(assignment, csp):
    if is_complete(assignment, csp):
        return assignment
    var = SELECT_UNASSIGNED_VAR(assignment, csp)
    for value in DOMAIN_VALUES(var, assignment, csp):
        if is_consistent(var, value, assignment, csp):
            assignment[var] = value
            result = BACKTRACK(assignment, csp)
            if result != "failure":
                return result
            del assignment[var]
    return "failure"

개선된 백트래킹 (Inference 포함)

def BACKTRACK(assignment, csp):
    if is_complete(assignment, csp):
        return assignment
    var = SELECT_UNASSIGNED_VAR(assignment, csp)
    for value in DOMAIN_VALUES(var, assignment, csp):
        if is_consistent(var, value, assignment, csp):
            assignment[var] = value
            inferences = INFERENCE(assignment, csp)
            if inferences != "failure":
                assignment.update(inferences)
                result = BACKTRACK(assignment, csp)
                if result != "failure":
                    return result
            del assignment[var]
            # Remove inferences if any
    return "failure"

설명:
- 할당이 완료되었는지 확인.
- 할당되지 않은 변수 중 하나를 선택.
- 도메인 값을 순회하며 일관성 있는 값을 할당.
- 할당 후 추론(Inference)을 통해 도메인을 축소.
- 재귀적으로 백트래킹 수행.
- 실패 시 할당과 추론을 제거하고 다음 값 시도.

변수 선택 기준 (Variable Selection)

최소 남은 값 (MRV) 휴리스틱: 도메인이 가장 작은 변수를 선택.
차수 휴리스틱 (Degree Heuristic): 차수가 가장 높은 변수를 선택.
- 높은 차수를 가진 변수를 선택하면 하나의 할당으로 여러 다른 변수를 제한할 수 있어 알고리즘의 처리 속도를 높임.

도메인 값 선택 기준 (Domain-Values)

가장 적게 제약하는 값 (Least-Constraining Values) 휴리스틱:
- 이웃 변수들에 대해 가장 적은 선택지를 제거하는 값을 먼저 시도.
- 이웃 변수들의 선택 가능한 값을 최대한 유지.
- 예: 변수 C에서 Tuesday를 고르면 BE를 고려해야 하고, Wednesday를 고르면 BE만 고려하면 됨.
- 목표: 변수를 고를 때는 연결을 많은 변수를 고르고, 도메인을 고를 때는 제약이 적은 값을 고름.

코드 예제 요약

Simplex 알고리즘을 사용한 선형 프로그래밍 예제

import scipy.optimize

# 목적 함수: 50x1 + 80x2
c = [50, 80]

# 제약 조건
A = [
    [5, 2],
    [-10, -12]
]
b = [20, -90]

# 변수의 경계
x0_bounds = (0, 200)
x1_bounds = (0, 300)

result = scipy.optimize.linprog(
    c, 
    A_ub=A, 
    b_ub=b, 
    bounds=[x0_bounds, x1_bounds]
)

if result.success:
    print(f"X1: {round(result.x[0], 2)} 시간")
    print(f"X2: {round(result.x[1], 2)} 시간")
else:
    print("해결책 없음")

AC-3 알고리즘 예제

def REVISE(csp, X, Y):
    revised = False
    for x in list(X.domain):
        if not any(constraint(x, y) for y in Y.domain):
            X.domain.remove(x)
            revised = True
    return revised

def AC_3(csp):
    queue = list(csp.all_arcs())
    while queue:
        (X, Y) = queue.pop(0)
        if REVISE(csp, X, Y):
            if not X.domain:
                return False
            for Z in csp.neighbors(X):
                if Z != Y:
                    queue.append((Z, X))
    return True

백트래킹 탐색 함수 예제

def BACKTRACK(assignment, csp):
    if is_complete(assignment, csp):
        return assignment
    var = SELECT_UNASSIGNED_VAR(assignment, csp)
    for value in DOMAIN_VALUES(var, assignment, csp):
        if is_consistent(var, value, assignment, csp):
            assignment[var] = value
            result = BACKTRACK(assignment, csp)
            if result != "failure":
                return result
            del assignment[var]
    return "failure"

개선된 백트래킹 탐색 함수 예제 (Inference 포함)

def BACKTRACK(assignment, csp):
    if is_complete(assignment, csp):
        return assignment
    var = SELECT_UNASSIGNED_VAR(assignment, csp)
    for value in DOMAIN_VALUES(var, assignment, csp):
        if is_consistent(var, value, assignment, csp):
            assignment[var] = value
            inferences = INFERENCE(assignment, csp)
            if inferences != "failure":
                assignment.update(inferences)
                result = BACKTRACK(assignment, csp)
                if result != "failure":
                    return result
            del assignment[var]
            # Remove inferences if any
    return "failure"

'AI > Concepts' 카테고리의 다른 글

[AI/Concepts] 06. Uncertainty (0)	2024.11.19
[AI/Concepts] 05. Knowledge (0)	2024.11.19
[AI/Concepts] Agent and Search (0)	2024.10.18
[AI/Concepts] Data Processing (0)	2024.10.18
[AI/Concepts] Data Analysis (0)	2024.10.18

현재글[AI/Concepts] 07. Optimization

Brute force Study

배움을 나누는 공간 https://github.com/DawnGlow

Today :
Yesterday :

일	월	화	수	목	금	토
1	2	3	4	5	6	7
8	9	10	11	12	13	14
15	16	17	18	19	20	21
22	23	24	25	26	27	28
29	30	31

Brute force Study

[AI/Concepts] 07. Optimization

최적화 및 탐색 알고리즘 개요

최적화 (Optimization)

지역 탐색 (Local Search)

예시: 병원 위치 선정

목적 함수 (Objective Function)

힐 클라이밍 (Hill Climbing)

힐 클라이밍 함수 예제

힐 클라이밍의 변형

시뮬레이티드 어닐링 (Simulated Annealing)

시뮬레이티드 어닐링 함수 예제

여행하는 판매원 문제 (Traveling Salesman Problem, TSP)

선형 프로그래밍 (Linear Programming)

선형 프로그래밍 예시

Simplex 알고리즘 예제

제약 만족 문제 (Constraint Satisfaction Problem, CSP)

제약 만족 문제 예시

아크 일관성 (Arc Consistency)

AC-3 알고리즘 예제

탐색 문제로서의 제약 만족 문제 (CSPs as Search Problems)

백트래킹 탐색 (Backtracking Search)

백트래킹 함수 예제

개선된 백트래킹 (Inference 포함)

변수 선택 기준 (Variable Selection)

도메인 값 선택 기준 (Domain-Values)

코드 예제 요약

Simplex 알고리즘을 사용한 선형 프로그래밍 예제

AC-3 알고리즘 예제

백트래킹 탐색 함수 예제

개선된 백트래킹 탐색 함수 예제 (Inference 포함)

'AI > Concepts' 카테고리의 다른 글

'AI/Concepts'의 다른글

티스토리툴바

[AI/Concepts] 07. Optimization

최적화 및 탐색 알고리즘 개요

최적화 (Optimization)

지역 탐색 (Local Search)

예시: 병원 위치 선정

목적 함수 (Objective Function)

힐 클라이밍 (Hill Climbing)

힐 클라이밍 함수 예제

힐 클라이밍의 변형

시뮬레이티드 어닐링 (Simulated Annealing)

시뮬레이티드 어닐링 함수 예제

여행하는 판매원 문제 (Traveling Salesman Problem, TSP)

선형 프로그래밍 (Linear Programming)

선형 프로그래밍 예시

Simplex 알고리즘 예제

제약 만족 문제 (Constraint Satisfaction Problem, CSP)

제약 만족 문제 예시

아크 일관성 (Arc Consistency)

AC-3 알고리즘 예제

탐색 문제로서의 제약 만족 문제 (CSPs as Search Problems)

백트래킹 탐색 (Backtracking Search)

백트래킹 함수 예제

개선된 백트래킹 (Inference 포함)

변수 선택 기준 (Variable Selection)

도메인 값 선택 기준 (Domain-Values)

코드 예제 요약

Simplex 알고리즘을 사용한 선형 프로그래밍 예제

AC-3 알고리즘 예제

백트래킹 탐색 함수 예제

개선된 백트래킹 탐색 함수 예제 (Inference 포함)

'AI > Concepts' 카테고리의 다른 글

'AI/Concepts'의 다른글

관련글

티스토리툴바