2. 탐색과 최적화 - 최적화

최적화

: 허용되는 값들 중에서 주어진 기준을 가장 잘 만족하는 것을 선택하는 것

 

목적함수

: 최소 또는 최대가 되도록 만들려는 함수

 

 

1) 조합 최적화

: 주어진 항목들의 조합으로 해가 표현되는 최적화 문제

예) 순회 판매자 문제. 목적함수: 경로의 길이

 

1-1)대표적인 예 - 유전 알고리즘

: 생물의 진화를 모방한 집단 기반의 확률적 탐색 기법

대표적 진화 연산.

 

*후보해(개체) 표현: 염색체로

*모집단: 동시에 존재하는 염색체들의 집합

*적합도 함수: 후보해가 문제(환경)의 해로서 적합한지를 평가하는 함수

*부모 개체 선택: 높은 적합도의 개체가 새로운 개체를 생성할 확률이 높도록 선택.
적합도에 비례하는 선택확률.

*유전 연산자: 새로운 개체 생성

교차(교배) 연산자, 돌연변이 연산자 적용

 

1-2) 메타 휴리스틱

: 최적해는 아니지만 우수한 해를 빠르게 찾기 위한 문제해결 전략

예) 유전 알고리즘. 

 

 

2) 함수 최적화

: 목적함수를 최대 or 최소로 하는 변수 값을 찾는 최적화 문제

-> 변수가 여러개면 각각 편미분으로 0이되는 변수의 값을 찾는다.

 

 

2-1) 제약조건 최적화

: 제약조건을 만족시키면서 목적함수를 최적화시키는 변수값들을 찾는 문제

 

2-2) 회귀(regression) 문제의 최적 함수

: 주어진 데이터를 가장 잘 근사하는 함수

-> 최소 평균제곱법(오차를 최소로 하는 함수를 찾는 방법)으로 구한다.

 

2-3) 경사 하강법=최대 경사법

: 함수의 최소값 위치를 찾는 문제에서 오차 함수의 그레디언트(gradient) 

반대 방향으로 조금씩 움직여 가며 최적의 파라미터를 찾으려는 방법.

국소해에 빠질 위험이 있다.

* 그레디언트: 각 파라미터에 대해 편미분한 벡터.