[강의정리] 알고리즘 Nonlinear Unconstrained Optimization
Nonlinear Unconstrained Optimizations
- Heuristic: 짐작, 경험등 규칙을 통하여 수행하는 알고리즘
- Optimality: X
Genetic Algorithms (GE) : 유전 알고리즘
- N개의 hypotheses(가설), 유지해나가는 알고리즘
- 집단 유전학의 개체 진화 원리르 이용하는 문제해결공간 탐색 방법
- In population:
- Selection: 어떤것을 선택할것인가
- Crossover: Selection한 후보중 어떤식으로 Mixable 할것인가
- Mutation: 어떻게 변이를 줄건가
- Replacement: 새로운 N개를 대치
유전알고리즘 표현
- 순서 기반 표현: 각각의 노드들을 하나하나 index줘서 표현
선택 연산
- 교차에 쓰이는 두개의 부모 해를 고르기 위한 연산
- 우수한 해가 선택될 확률이 높아야함
품질 비례 룰렛휠 선택
- 각 해의 품질을 평가한 다음 가장 좋은 해의 적합도가 가장 나쁜 해의 적합도의 k배가 되도록 조절
- fi = (Cw - Ci) + ( Cw - Cb ) / (k - 1), k>1
- Cw : 해집단 내에서 가장 나쁜 해의 비용
- Cb : 해집단 내에서 가장 좋은 해의 비용
- Ci : 해 i의 비용
순위기반 선택
- 해잡단 내에서 해들을 품질 순으로 순위를 매긴 후 다음 가장 좋은 해부터 일차 함수적으로 적합도 배정
- fi = max + ( i - 1 ) X (min - max ) / (n - 1)
교차 연산
- 유전 알고리즘의 대표 연산
- 연산 중 가장 다양한 대안 존재
일점 교차(point crossover)
- 길이가 n인 일차원 문자열로된 염색체 상에서 일점 교차로 자르는 방법(총 n-1가지)
다점 교차(multipoint crossover)
염색체의 길이가 n일 때 k점 교차로 자르는 방법의 총 수는 n-1Ck가지
일점교차보다 교란의 정도가 커서 보다 넓은 탐색 공간을 탐색할 수 있음
교란이 강하면 수렴성이 떨어져 주어진 시간 예산내에 제대로 수렴하지 않을 가능성
균등 교차(uniform crossover)
- 자름선을 이용하지않음
- 이론적으로 완벽(모든 재조합 가능성 open)
- 난수를 사용
사이클 교차(cycle crossover)
- 염색체가 순열일경우 사용
- S2[index] = S1
순서 교차(order crossover)
- 염색체가 순열일경우 사용
- 한 부분집합을 고정함, 남은부분 부분집합 뒤부터 순서대로
간선 재조합
TSP를 위해 개발된 교차연산
부모해의 특성을 보존, 변이가 적으면 교란이 너무 적음
인접도시목록을 이용하여 TRACKING
장단점?
- 각각이 생각했던 최종 SOLUTION을 유지해나갈 수 있음
BFS를 이용한 유전자 재배치
- 유전알고리즘 시작 전에 문제에 깃든 정보(유전자들 간의 관계)를 이용하여 유전자들의 위치를 재배치
변이 연산
- 부모해에 없는 속성을 도입하여 탐색 공간을 넓히려는 목적을 가진 연산
전형적 변이
비균등 변이
수선
기타 변이 연산
세대형 유전 알고리즘
해집단 내에서 염색체가 대부분(전체) 대치되므로 대치 연산이 비교전 간단
convergence(수렴)이 일어나기 어려움
안정 상태 유전 알고리즘은 한 개 또는 소수의 해가 생기는 즉시 해집단 내의 해들과 대치하게 되므로 대치될 대상을 고르는 작업이 매우 중요한 영향을 미침
-> 부분적인 최적화가 어렵다
GA가 유용한 문제들
- 전통적 방법으로(결정론적인(deterministic)방법으로) 좋은 해를 잘 구하지 못하는 문제
GA가 소용 없는 문제들
결정론적 알고리즘(deterministic algorithm)으로 쉽게 풀리는 문제
결정론적 알고리즘(deterministic algorithm)으로 쉽게 풀리지 않으나 크기가 너무 작은 문제
- 5-city TSP 등
Solution Space가 가늠할 수 없는 근사치 최대값을 찾기 유용한 알고리즘이다.
GA 장단점
장점
- 빠르다 (메모리 사용량 적음) 엄청 큰 Search space에서.
- 쉽다.
단점
- Randomized - optimal하지 못하고 complete하지 못함
- local maxima에 빠질 수 있음
Downhill Simplex Method
- Starting Guess
- N+1 각형을 유지
N+1개의 꼭짓점 갖는 구조
하나 이상의 테스트 포인트 유지
기본적인 Operation
- 4개의 scalar parameters을 지정
- reflection p
- expansion w
- contraction y
- shrinkage a
- Standard: p = 1, w = 2, y = 1/2 and a = 1/2
진행방식
- Order: 어떤 포인트가 가장 유명한지 판단
- Reflect
- Expand
- Contract
- outside
- inside