메타휴리스틱스(Metaheuristics)

126회 정보관리기술사 1교시 2번 문제

평소 학습으로 개념이나 주요 기법을 알고 있었다면

방어가 가능한 문제이나, 선택이 쉽지 않은 문제였습니다.

 

인공지능 알고리즘이 지엽적인 문제 해결에서

범용적 문제 해결로 발전하고 있는 시대적 흐름에 기반하여

근본적이고 Deep한 문제가 출제되고 있습니다.

 

0.why

 - 인공지능 알고리즘 연구의 활성화

 - 범용성 : 다양한 분야에 두루 적용 가능한 알고리즘 연구 필요

 - 문제해결 어려움 : 한정된 시간에 최적해를 구하기 어려운 문제 존재

 

1.범용 알고리즘의 기틀, 메타휴리스틱스의 개요

 가. 메타휴리스틱스의 개념

   특정 문제에 한정되지 않고, 어떠한 문제에도 범용적으로

   대응할 수 있도록 설계된 알고리즘의 기본적인 프레임워크

 나. 메타휴리스틱스의 특징 

  1)최적화 문제 해결

  2)유연한 구조

  3)다양한 기술과의 결합

 

2.메타휴리스틱스 기법 설명

구분	기법	설명
단일해 기반	시뮬레이티드 어닐링 (simulated annealing)	- 담금질 기법(Simulated Annealing, SA)은 전역 최적화 문제에 대한 일반적인   확률적 메타 알고리즘.  - 광대한 탐색 공간 안에서, 주어진 함수의 전역 최적해에 대한 좋은 근사 제공
	타부서치(tabu search)	- 유전알고리즘, 시뮬레이티드 어닐링의 빈번하게 지역 최적점(local optimum)에 수렴하는 문제발생 - 이를 해결하기 위해, 지역 최적점에 대한 정보를 저장, 이 정보를 기반으로 지역 최적점을 회피하여 전체 최적점을 찾는 알고리즘
	반복지역탐색 (iterated local search)	- 이산 최적화 문제를 해결하기 위한 로컬 검색 또는 언덕 오르기 방법의 수정을 정의.  - 지역 검색 방법은 개선할 수 있는 이웃이 없는 지역 최소값 문제 발생 가능.
집단 기반	진화알고리즘 (evolutionary algorithms)	- 일반 모집단 기반 메타 휴리스틱 최적화 알고리즘 인 진화 계산의 하위 집합 - 번식, 돌연변이, 재조합 및 선택과 같은 생물학적 진화에서 영감을받은 메커니즘을 사용
	개미군체최적화 (ant colony optimization)	- 컴퓨터를 이용 연결그래프의 최적의 길을 찾는 방법을 줄일 수 있는 알고리즘
	벌군체최적화 (bee colony optimization)	- 화음이라는 인공적인 현상에서 착안하여 개발된 고도화된 발견적 기법(Meta-heuristic methods) - 재즈의 즉흥연주에서 반복적인 연습을 거듭할 수 록 좋은 화음 이 만들어지는 현상에 착안(고려대학교 수자원연구실에서 개발)

3. 전역 최적화 기법, 유전자알고리즘

최적화 산출 (출처:  http://blog.clarity.fm/dont-test-optimize )

 

- 생물계의 진화를 설명하는 다윈의 적자생존 이론을 기본 개념으로 하는 계산 모델
- 풀고자 하는 문제에 대한 가능한 해들을 정해진 형태의 자료구조로 표현하고 
  이를 점차 변형함으로써 점점 더 좋은 해를 만들어 내는 과정을 거침