메타휴리스틱스(Metaheuristics) / ①

문제2) 메타휴리스틱스(Metaheuristics)

답)

 

 

1. 상위수준의 휴리스틱, 메타휴리스틱스(Metaheuristics) 개념

가. 정의

• meta ('higher level' or 'beyond') 와 heuristic ('to find' or 'to discover') 의 합성어로 상위수준의 휴리스틱
• 특정 휴리스틱 구축을 위한 일반적인 구조와 전략을 안내하는 범용 알고리즘 툴(framework)

 

나. 특징

• 좋은 해 탐색 : 지역최적에서 벗어나 해공간을 강건하게 탐색하는 프로세스와 전략을 갖음
• 자연현상 모방 : 과거 탐색에서 얻은 경험, 정보를 '기억','전달'하여 다음 탐색을 이용
• 해 탐색 과정 반복 : '단일 해' 기반 뿐 아니라, '해 집단' 기반으로 해 공간의 여러지역을 동시에 탐색

 

2. 메타휴리스틱스의 공통 요소 및 대표 기법

가. 공통요소

표현	이진수, 실수 백터, 순열, 그룹, 행렬, 랜덤키, 그래프 등으로 해의 표현이 가능
목적 함수	후보해들을 평가하는 함수, 목적함수 값에 의해 해의 품질, 적합도가 결정
초기해	알고리즘 시작을 위해 필요. 임의(random) 생성과 휴리스틱(or greedy) 생성 존재
파라미터 조정	알고리즘의 주 요소, 고정방식과 실행 중에 갱신가능한 동적적용방식 존재
종료조건	최대 반복 수, 최대 세대 수, 목적함수 평가 최대 횟수, 최대 계산소요시간, 해의 개선이 없는 반복횟수, 사전에 최적해를 알거나 그 한계를 아는 경우 등
이웃구조	단일해 기반(S-MHs) : 현재해의 이웃에서 하나의 이웃해를 선택하고, 이동하ㅕㄴ서 해공간 탐색 집단 기반(P-MHs) : 하나의 집단을 운영하면서 발생하는 탐색의 조기 수렴 또는 조기 정체를 피하고, 탐사력을 높이는 방법으로 사용
공통요소는 모든 메타휴리스틱에서 공통으로 고려되는 기본 요소 기법은 매 반복에서 운용하는 후보해의 수에 따라 집단 기반, 단일해 기반으로 분류가 가능

 

나. 대표적인 메타휴리스틱스 기법

분류	대표 알고리즘	설명
단일해 기반 (S-MHs)	시뮬에이티드 어닐링 (simulated annealing:SA)	하나의 해가 이웃을 확률적(stochastic)으로 탐색해가는 최적화 기법. 전역최적해(global optimum)로의 수렴이 이론적으로 증명됨 적용이 우수하나, 계산시간이 많이 소요
	타부서치 (tabu search:TS)	인간의 기억과정을 모방한 알고리즘으로 하나의 해를 이용한 이웃탐색기법. 조합최적화문제에 효율적 종류 : 경가법, 최소걸침나무 문제
	반복지역탐색 (Iterated local search:ILS)	앞의 지역탐색에서 얻은 지역최적해에 기초하여 다음 초기해를 생성하는 해 공간 탐색방법
	가변이웃탐색 (variable neighboarthood search:VNS)	이웃해 탐색에 기반을 두어 지역최적을 벗어나 다른 해 공간을 탐색하여 '이웃을 체계적으로 변경' 시키는 탐색방법
	유도지역탐색 (guided local search:GLS)	이미 찾은 지역최적해의 정보를 이용하여 목적함수를 동적으로 변화시키면서 탐색하는 지역탐색기법 조합최적화를 위한 메타휴리스틱
집단 기반 (P-MHs)	진화 알고리즘 (evolutionary computationm:EA)	생식(reproduction), 돌연변이(mutation), 재조합(recombination) 같은 생물학이 진화를 본뜬 개체군 기반 조합최적화 알고리즘 종류 : 유전알고리즘(GA), 진화전략(ES), 진화프로그레밍(EP), 유전프로그래밍(GP), 공진화 알고리즘(CEA), 다목적진화 알고리즘
	입자군집최적화 (paticle swarm optimization:PSO)	새, 물고기, 양 등이 무리지어 이동하는 집단 행동을 모방한 최적화 알고리즘 연속변수를 갖는 최적화 문제 해결에 사용 적용 : 신경망 학습의 가중치구하기, 최적화 문제
	개미군체최적화 (ant colony optimization: ACO)	개미 집단이 먹이를 찾고, 이를 둥지로 나르는 행동을 모방한 확률적 탐색기법 이산 탐색 공간을 갖는 조합최적화 문제에 적용 적용 : 외판원 문제, 차량경로문제
	차분진화 (differential evolution:DE)	비 선형이고 미분 불가능한 연속 공간 함수를 최적화하는 알고리즘 집단에 속한 개체 백터의 거리와 방향 정보 사용 적용 : 비가능해 버리기, 비가능해를 가능해로 수리, 벌금부과, Deb 의 방법 등
	별군체최적화 (bee colony optimization:BCO)	벌의 집단행동을 모방한 최초의 알고리즘 빠르고 정확한 최적화 도출 사례 : ABC 알고리즘
	화음탐색 (harmony search:HS)	음악에서 즉흥연주를 위해 화음을 맞추는 과정을 모방한 알고리즘 적용 : 물 분배 계회그 구조설계, 열교환기 설계
메타 휴리스틱은 특정 휴리스틱의 상위 휴리스틱으로 차이를 명확히 이해하고 활용이 필요

 

3. 휴리스틱과 메타휴리스틱스의 비교

구분	휴리스틱	메타휴리스틱
정의	체계적, 합리적 판단이 필요하지 않은 상황에서 빠르게 사용할 수 있게 구성된 간편추론 방법	특정 휴리스틱을 개발 할 때 알고리즘의 기본 틀로 사용하는 상위 휴리스틱
특징	특정한 형태의 문제 해결에 적합하도록 설계된 '특정 휴리스틱'	좋은해 탐색, 자연현상 모방, 해탐색과 정 반복
장점	좋은 해를 찾을 가능성이 높음	단순성, 명확성, 범용성 높음 다양한 문제에 적적한 계산시간 내에 최적해, 근사 최적해 제공 가능
단점	합리적인 계산시간 내에 최적해를 보장하지 못함	구조, 해공간, 해특징 이해 필요 전역최적해로의 강한 수렴을 보장하지 못함. 지역최적에 빠지면 수렴속도가 느려져 긴 시간 소요
적용분야는 조합최적화, 연속최적화, 신경망 학습, 패턴인식, 데이터 마이닝, 인공지능, 화상처리, 공학 구조 최적화 등의 공학 분야이외에도 자연과학, 사회과학 등 적용 가능

 

---

 

공감과 댓글은 아이티신비에게 큰 힘이 됩니다.

블로그 글이 유용하다면 블로그를 구독해주세요.♥