[인공지능] 탐색과 최적화 - 제약조건 만족 문제, 최적화

제약조건 만족 문제(constraint satisfaction problem)

• 주어진 제약조건을 만족하는 조합 해(combinatorial solution)를 찾는 문제
• ex) N Queen problem
• 탐색 기반의 해결 방법
  • backtracking search(백트래킹 탐색)
    • DFS를 하는 것처럼 변수에 허용되는 값을 하나씩 대입
    • 모든 가능한 값을 대입해서 해가 없으면 이전 단계로 돌아가서 이전 단계의 변수에 다른 값을 대입
  • constraint propagation(제약조건 전파)
    • 인접 변수 간의 제약 조건에 따라 각 변수에 허용될 수 없는 값들을 제거하는 방식

 

최적화(optimization)

• 여러 가지 허용되는 값들 중에서 주어진 기준을 가장 잘 만족하는 것을 선택하는 것
• 목적 함수(objective function) = 최적화의 대상이 되는 함수
• 최적해(optimal solution) = 주어진 제약조건을 만족하면서 목적 함수의 값을 최대 또는 최소로 하는 값(들)
• 조합 최적화(combinatorial optimization)
  • TSP(traveling salesperson problem)와 같이 주어진 항목들의 조합으로 해가 표현되는 최적화 문제
    • TSP의 목적 함수 = 경로의 길이
  • 유전 알고리즘(genetic algorithm, GA)
    • 생물의 진화를 모방한 집단 기반의 확률적 탐색 기법
    • 대표적인 진화 연산(evolutionary computation)의 하나
    • 생물의 진화
      • 염색체(chromosome)의 유전자(gene)들이 개체 정보 코딩
      • 적자생존(fittest survival) / 자연선택(natural selection)
        • 환경에 적합도가 높은 개체의 높은 생존 및 후손 번성 가능성
        • 우수 개체들에게 높은 자손 증식 기회를 부여
        • 열등 개체들에게도 작지만 증식 기회를 부여
      • 집단(population)의 진화
        • 세대(generation) 집단의 변화
      • 형질 유전과 변이
        • 부모 유전자들의 교차(crossover) 상속
        • 돌연변이(mutation)에 의한 변이
      • 생물 진화와 문제 해결
        • 개체 ↔ 후보 해(candidate solution)
        • 환경 ↔ 문제(problem)
        • 적합도 ↔ 해의 품질(quality)

        • 

      • 적합도 함수(fitness function) = 후보 해가 문제의 해로서 적합한 정도를 평가하는 함수
      • 부모 개체 선택(selection)
        • 높은 적합도의 개체가 새로운 개체를 생성할 확률이 높도록 함
        • 적합도에 비례하는 선택 확률
      • 유전 연산자(genetic operator) = 새로운 개체 생성
        • 교차(crossover) 연산자
        • 돌연변이(mutation) 연산자
      • 세대(generarion) 교체
        • 엘리트주의(elitism) = 우수한 개체를 다음 세대에 유지
  • 메타 휴리스틱(meta heuristics)
    • 최적해는 아니지만 우수한 해를 빠르게 찾기 위한 휴리스틱적인 문제 해결 전략
    • 유전 알고리즘(genetic algorithm)
    • 모방 알고리즘(memeticalgorithm)
    • 입자 군집 최적화(particle swarm optimization, PSO)
    • 개미집단(ant colony) 알고리즘
    • 타부 탐색(Tabusearch)
    • 담금질 기법(simulated annealing)
    • 하모니 탐색(Harmonic search)
    • 유전 프로그래밍(genetic programming)
• 함수 최적화(function optimization)
  • 어떤 목적 함수(objective function)가 있을 때, 이 함수를 최대로 하거나 최소로 하는 변수 값을 찾는 최적화 문제
  • 제약 함수 최적화
    • 제약조건(constraints)을 만족시키면서 목적함수를 최적화시키는 변수값들을 찾는 문제
    • 기계학습 방법인 SVM(Soft Vector Machine)의 학습에서 사용
    • 가능해(feasible solution) = 제약조건을 만족하는 해
  • 회귀(regression) 문제의 최적 함수
    • 주어진 데이터를 가장 잘 근사(approximation)하는 함수
    • 최소 평균제곱법(least mean square method)
      • 오차 함수(error function)또는 에너지 함수(energy function)를 최소로 하는 함수를 찾는 방법

      • 

        오차 함수. 양의 오차와 음의 오차가 상쇄되는 것을 방지하기 위해 제곱을 한다.

    • 경사 하강법(gradient descent method)
      • 함수의 최소값 위치를 찾는 문제에서 오차 함수의 그레디언트(gradient) 반대 방향으로 조금씩 움직여 가며 최적의 파라미터를 찾으려는 방법
      • 그레디언트 = 각 파라미터에 대해 편미분한 벡터
      • 데이터의 입력과 출력을 이용하여 각 파라미터에 대한 그레디언트를 계산하여 파라미터를 반복적으로 조금씩 조정
      • 학습률이 너무 크면 최적값을 찾아가지 못하고, 너무 작으면 학습 속도가 느려진다.
    • 최대 경사법
      • 회귀 모델, 신경망 등의 기본 학습 방법
      • 국소해(local minima)에 빠질 위험
      • 개선된 형태의 여러 방법 존재