최적화란?
주어진 문제에 가능한 방법/해답 중 가장 좋은 방법 찾는 과정.
어떻게 가장 좋은지 아냐?
- 얼마나 좋은지 수치적으로 측정할 수 있어야 하고, 내가 사용할 수 있는 방법/해답을 변수화해야 한다.
[주요 요소]
- 목적함수, 제약조건, 변수
- 문제 예시
knapsack problem
주어진 물건의 무게/가치, 배낭의 수용 가능 무게가 주어졌을 때, 가방에 물건을 어떻게 담는 것이 좋을지 찾아보는 문제
traveling salesman problem
이동 경로의 최소화. 한 번 방문하면 그이상 방문 불가. 등등..의 제약조건
전역(Optimal) 최적해 vs 지역(Local) 최적해
전역 : 문제의 모든 상황을 고려했을 때 가장! 최고의 해
지역 : 특정 구간에서만 최고의 해
탐색 공간
해를 찾기 위해 알고리즘이 탐색해야 하는 솔루션 집합.
변수에 따라~ 이산변수(정수형), 연속변수(실수형)으로 나뉘고,
그 변수의 개수에 따라 탐색 공간의 차원이 결정된다.
그래디언트 기반 최적화
모델 만드는 것이 목표인데, Loss(MSE)를 최소화해야 함.
그래디언트를 바꿔가며 모델을 설정하고, 예측값과 정답값 사이 차이를 비교해 MSE를 설정해줌.
Gradient : 경사도/변화도/증감률/기울기
목적함수 f(x) : 내가 갖고 있는 변수(x)들을 기준으로 f(x)를 최적화하기. 여기서 목적함수인 f(x)는 Loss값임.
경사하강법 : 목적함수 f(w)를 최소화하고 싶음. 그렇다면, 모든 변수를 f(w)가 줄어드는 방향으로 조금씩 옮겨가보자.
ex) w1를, t 시간에 보니, f에 대한 편미분이 -10이었다면, w1이 1 증가하면 f가 -10 변화된다는 뜻. f(w)가 감소하는 방향이므로, w1를 늘리면 됨.
이 최적화를 사용하려면, 목적함수가 연속적이어야 하고, 목적함수가 변수에 의해 나타낼 수 있어야 하고, 변수에 의해 미분 가능해야 한다.
이러한 그래디언트 기반 최적화는 NN을 학습하기에 적절하다.
optimizer = torch.optim.SGD(model.parameters(), lr = 0.01)
optimizer = torch.optim.Adam(model.parameters(), lr = 0.01)
최적화 방법론
- Gradient를 기반으로 얼마나 그 방향으로 갈 거냐?
<SGD> : 전체 다 보진 말고.. 일단 조금씩 보면서 가보자
<Momentum> : 과거 오던 방향 누적해서.. 가던대로 관성 이용해서 좀 더 가보자
<RMSProp/AdaGrad> : 과거에 좀 많이 갔던 애들은 속도 좀 조절해서 가자
Heuristic 휴리스틱
특정 문제를 빠르게 해결하기 위해 고안된 경험적 규칙이나 전략
전역 최적해는 보장하지 않지만, 구현이 쉽고 빠르게 해답을 제공한다.
ex) Knapsack problem에서 무게당 가치 높은 순대로 일단 담으면 몇 개 못 담을 수도 있음(지역최적해)
근데 모든 조합 생각해보면 더 많은 가치를 담을 수 있음(전역최적해)
메타 휴리스틱
다양한 문제에 적용 가능한 일반화된 최적화 방법론.
여러 휴리스틱을 결합하거나 확장하여 사용.
지역최적해에 빠지지 않도록 해의 탐색 공간을 광범위하게 탐색.
휴리스틱보다 복잡하지만, 휴리스틱보다는 더 좋은 근사해를 찾으려 함. 그렇다고 전역 최적해를 보장하는 건 아님.
Hill-climbing 언덕 오르기 알고리즘
휴리스틱 greedy 알고리즘, 인접해 또는 이웃을 탐색해보고 더 좋으면 바꾸고 아니면 안 바꿈
Simulated Annealing 담금질 알고리즘
금속 서서히 냉각시키는 어닐링 과정 반영, 메타 휴리스틱 알고리즘
무작위로 인접해 생성하고, 현재 해보다 나빠도 일정 확률로 그 해로 이동.
근처에 있는 게 나보다 좋은 해면 이동하는데, 더 안 좋은 해여도, 좋은 게 있을 수도 있기 때문에 그래도 가본다.
E의 변화량은 항상 음수.
Genetic Algorithm 유전 알고리즘
자연 선택과 유전적 진화 원리를 모방한 메타 휴리스틱 알고리즘
초기 해 집단 (Population)을 만들고, 선택/교차/돌연변이 같은 진화 과정 반복
초기해집단 생성 -> 적합도(목적함수) 평가 -> 선택 -> 교차 -> 돌연변이 (밑줄 부분은 정해진 횟수 만큼 반복)
이게 적합한 이유는? 모든 가능 경우의 수를 고려하기엔 탐색 공간이 너무 크다.
- 룰렛 휠 선택 : 각 해의 적합도를 기준으로 확률이 배정된 룰렛 돌리는 개념. 적합도 높은 해가 선택될 확률 높음.
- 토너먼트 선택 : 임의로 k개 선택 후 그 중 최고를 선택
- 순위 기반 선택 : 적합도 순위에 따라 확률 부여해서 선택
- 엘리트주의 : 가장 적합도 높은 개체가 무조건 다음 세대로 전달됨
<선택 Selection > - (다음 세대를 위한 부모 선택)
- 세대 교체 : 초기 개체 수만큼 부모 반복 선택해 다음 세대 생성 후 완전 교체
- 분할 교체 : 적합도가 낮은 일정 비율만 새로운 개체로 바꿈
- 엘리트 주의 : 적합도 가장 높은 10%는 다음 세대로 넘어가고, 나머지는 자식 개체로 대체
<교차 Crossover> - (부모 교차해 다음 세대 생성).
- 부모 개체 유전 정보 조합해 새로운 자식 개체생성
- 특정 해의 구성을 교차/교배하는 것, 적합도 높은 두 개의 해를 적절히 섞어서 새로운 해 탐색
- 단일 지점 교차 : 임의의 교차점 하나를 가지고 교차
- 다중 지점 교차 : 임의의 교차점 여러 개를 가지고 교차
- 균일 교차 : 각 유전자 위치마다 부모 유전자 중 하나 무작위로 선택
<변이 Mutation> - (자식세대 일부 유전자 무작위 변경).
- 자식 개체 유전자를 무작위로 변경해서 유전적 다양성 유지하고 탐색공간 넓힘
- 부모 대체에 없는 유전자 나오도록 유도. -> 지역 최적해에 빠지지 않도록
- 변이 확률에 따라 변경
- Bit flip mutation, Swap mutation 등 다양하게 정의 가능
<예시>
- 시간표 최적화 문제
적합도 점수(공강시간min, 아르바이트 시간 안겹침 등을 만족하는 정도)를 최대화하는 것.
초기 개체군 생성 : 무작위 시간표 생성
적합도 평가 : 각 시간표의 적합도 평가
- 인간의 진화 과정
어떤 건 먹어도 되고, 자야 되고, 맹수 보면 피하거나 싸워야 하고.. 등을 알아감.
다중 목적 최적화
많은 문제들은 하나의 단순 목적 함수로 나타낼 수 없다. 여러 상충될 수도 있는 목표를 동시에 최적화 하고 싶어한다.
<파레토 최적해>
- 다중 목적 최적화에서 어떤 하나의 목적함수 값을 개선시키면 다른 하나의 목적함수가 반드시 감소하는 해
- 파레토 전선 : 모든 파레토 최적해가 구성하는 집합. 다중 목적 최적화에서 가능한 최적해의 경계
- 비지배해 : 파레토 최적해는 비지배해로 불림. 다른 해에 의해 지배되지 않는다는 의미(두 목적함수 모두 좋아짐)
<예시>
제조 비용 최소화, 연비 최소화의 다중 목적 최적화 문제
Pareto front는 해당 비용으로 가장 좋은 연비 or 해당 연비로 가장 저렴한 해의 집합.
- > 제조 비용과 연비를 이용해 그래프를 그리면,
solution A가 중앙에 주어졌을 때,
- 그 A의 오른쪽 상단은 A에 의해 지배되는 영역. 왜냐면 A는 어차피.. 저 영역보단 좋다.
- A의 오른쪽 하단과, A의 왼쪽 상단은 A와 비교불가한 영역.
- A의 왼쪽 하단 영역은 A를 지배하는 영역.
다목적 유전 알고리즘
- 탐색을 통해 파레토 최적해의 집합 찾는 알고리즘
가중합법
- 각 목적에 맞는 가중치 부여해 합산
e-제약법
- 한 목표를 최적화하고 다른 목적은 제약조건 부여.
ex) f1(x)는 최적화, f2(x) < e 의 제약조건 부여.
--> e 변경하며 파레토 최적해 탐색
메타 휴리스틱 종류
PSO(Particle Swarm Optimization)
- 군집 기능에 기초한 최적화 기법
- 물고기 떼나 새 떼와 같은 집단적 행동 모방
- 군집은 여러 입자(Particle, 가능한 해를 의미)로 이루어져 있음
- 입자는 위치와 속도를 가지고, 위치는 가능한 해를, 속도는 위치의 변화를 나타냄.
ACO(Ant Colony Optimization)
- 자연에서 개미의 행동을 모방한 알고리즘
- 그래프 기반 최적화 문제에서 유용하게 쓰임
- 페로몬 : 개미가 경로에 페로몬 남기고, 다른 개미들이 이거 감지해서 따라감
- Exploration and Exploitation : 개미는 페로몬 농도가 높은 경로를 확률적으로 선택하지만, 무작위적으로 새로운 경로 탐색
- 각 경로에 초기 페로몬 값을 설정하고 - 개미 배치하고 - 공간 탐색/해 생성 - 페로몬 업데이트(좋은 곳에 더 높은 페로몬)
출처 : 충남대 박지훈 교수님 수업자료
