메타 휴리스틱스(Metaheuristics)의 소개(1)

많은 경우의 최적화 방법 연구는 해결하고자 하는 문제마다 각기 다른 그 특성에 맞추어 개발해야 하는 어려움이 있다.

이에 따라 특정 문제가 갖는 정보에 크게 구속되지 않고 다양한 문제에 적용 가능한 상위 수준의 방법인 메타 휴리스틱스(Metaheuristics)에 대한 이론과 그 응용에 관한 연구가 진행되었다. 대표적인 메타 휴리스틱스로는 유전적 알고리즘, 시뮬레이티드 어닐링, 타부 탐색 등이 있다.

메타 휴리스틱스(Metaheuristics)란 알고리즘에 대한 다른 표현으로 특정 계산 문제에 의존하지 않는 휴리스틱스를 말한다.

즉 특정 문제에 한정되지 않고 어떠한 문제에 대해서도 범용적으로 대응할 수 있도록 설계된 알고리즘의 기본적 뼈대를 의미한다.

메타 휴리스틱스는 모델링, 시뮬레이션 기술과의 결합을 전제로 한 최적화 수법의 개발과 최적화 수법과의 결합을 전제로 한 모델링, 시뮬레이션 기술 개발에 의한 최적화 기술의 발전적 재구축을 위한 주요 기술이 될 것이다. 그리고 이러한 최적화의 뼈대가 실용적인 레벨에서 실현되면 여러 분야에 대한 최적화의 보급을 촉진할 수 있을 것이다.

▒▒▒ 조합 최적화와 지역탐색(local search), 메타휴리스틱스 ▒▒▒

조합최적화 문제와 지역탐색

1. 조합최적화 문제

S는 주어진 제약조건에 맞는 이산적인 집합(=해집합)

x는 가능해(feasible solution)    

⇒ 이 문제는 대부분 NP-hard로 Heuristic 접근 방법이 필요

 

2. Heuristics :

• Constructive

• Local search(지역탐색) : 근방(neighborhood)의 설정,

• 교환알고리즘: 스케줄링(1965), 그래프 분할(Kernigan&Lin, 1970), TSP(L&K, 1973)

 

예1) GPP(Graph Partitioning Problem)

그래프 G(V,E)가 주어졌을 때 vertex의 집합 V를 동일한 개수의 원소를 갖도록 두 개의 집합 V1과 V2로 나눌 때, V1과 V2를 가로지르는 edge의 수(또는 가중치의 합)를 최소로 만드는 방법을 찾는 문제

- 비용함수:

- 근방: 가능해의 k-교환(exchange) 근방

- k개의 vertex쌍 을 선택하여 각각을 교환

 

예2) TSP(Traveling Salesman Problem)

n개의 도시가 주어지고 i, j 도시 사이의 거리가 행렬()로 주어졌을 때 출발 도시에서 가장 최소의 거리로 모든 도시를 한 번씩 거쳐서 다시 출발 도시로 돌아오는 경로(tour)를 찾는 문제

- 해: (는 도시 다음에 방문되는 도시)

- 비용함수:

- 근방: (k-exchange 근방)

Hamiltonian Cycle(or Tour)에서 edge k개를 대체

지역 최적이 전체 최적해가 되려면

3. 근방의 설정

a) k-exchange 근방: k가 크면 근방이 복잡(), 지역해는 좋아짐

b) 변동길이 근방: GPP에 대한 K-L algorithm, 1970

a, b 교환의 이득: (현재 일 때)

[STEP 1] g(a,b)가 최대가 되는 쌍을 선택(음수라도 무관)

[STEP 2] 선택된 쌍을 잠정적으로 교환

[STEP 3] STEP1, 2를 n회 반복하여 를 계산(먼저 고려된 쌍은 제외)

[STEP 4] 를 계산

[STEP 5] 가 최대가 되는 k 선택. 이 때 이면 이웃해로 채택하고 과정반복, 아니면 stop

c) 기타 수정법: GPP에서 2-exchange를 2번의 1-exchange로 하는 방법 등

4. 지역 탐색법에서 최적(에 가까운) 해를 얻는 방안

a) 초기해를 달리하여 여러 번의 지역 탐색을 시도

- 소모된 시간에 대한 알고리즘의 효율성이 문제

- 초기해(가능해)를 만들어 내기도 쉽지 않음

b) 해집합의 보다 많은 부분을 탐색할 수 있도록 근방의 구조를 바꿈

- 문제의 특수성에 따라 적절한 근방 구조를 찾기가 힘들다

c) 지역 탐색법을 수정하여 비용이 증가하는 이동도 제한적으로 허용

- 비용 증가의 이동을 어떤 방식으로 허용하는가?

5. Metaheuristics의 등장

1975: GA(Holland) → EC(Evolutionary Computation)

1983: SA(Kirpatrick et al.)

1987: TS(Glover)

1991: Ant System(Colorni, Dorigo, Maniezzo) → ACO(Ant Colony Optimization) 등