[메타 휴리스틱] 메타휴리스틱의 알고리즘

 

이번 글의 내용은 전남대학교 산업공학과 김여근 교수님의 메타휴리스틱 교재 정리 및 참조하였음을 먼저 밝힙니다.

(다른 참조한 논문과 자료들은 아래에 기재되어 있습니다.) 

 

 

이 포스트는 "메타 휴리스틱" 책의 내용을 참조 및 공부한 것을 바탕으로 제가 이해한 정보를 추가하여 쓰여졌습니다.  

 

 

혹시 제가 잘못 알고 있는 점이나 보완할 점 있다면 댓글로 알려주시면 감사하겠습니다. 

 

---

 

 

 

 

※ 1960년대 중반부터 현재까지 메타휴리스딕의 여러 알고리즘이 꾸준이 제안되어 오고 있고, 그 적용 또한 확대되고 있습니다.

 

 

위의 표는 주요 메타휴리스틱 기법들을 보여주고 있습니다. 이들 메타휴리스틱이 모방한 현상에 따라 분류하면

(1) 자연의 진화과정을 모방한 진화 알고리즘(evolutionary algorithm: EA)

(2) 군집(Swarm & colony) 생활하는 생물들의 행위를 모방하는 알고리즘

(3) 자연 및 사회 현상을 모방한 알고리즘

(4) 체계적인 반복으로 이웃을 탐색하는 알고리즘

 

---

 

첫째, 자연의 진화 과정을 모방한 알고리즘에는 진화전략(evolution strategy: ES), 진화프로그래밍(evolutionary porgrammin: EP), 유전알고리즘(genetic algorithm: GA), 유전프로그래밍(genetic programming: GP), 차분진화(differential evolution: DE)등이 있습니다. 이들 알고리즘을 진화알고리즘이라 부릅니다.

 

 

둘째, 개미, 벌, 물고기, 새 등 군집(swarm & colony) 생활하는 생물들의 행동을 모방한 알고리즘으로 개미군체최적화(ant colony optimization: ACO), 입자군집최적화(particle swarm optimization: PSO), 벌군체최적화(Bee Colony Optimization: BCO), 인공벌군체(artificial bee colony: ABC) 등이 있습니다.

 

셋째, 열역학의 어닐링과정을 모방한 시뮬레이티드 어닐링(simulated annealing: SA), 기억 과정을 모방한 타부서치(tabu search: TS), 면역시스템을 모방한 인공면역시스템(aritificial immune system: AIS), 음악의 화음 조율과정을 모방한 화음탐색(harmony search: HS) 알고리즘이 있습니다.

 

넷째, 체계적인 반복으로 이웃을 탐색하는 알고리즘에는 반복지역탐색(iterated local search: ILS), 가변이웃탐색(variable neighborhood search: VNS), 유도지역탐색(guided local search: GLS) 등이 있습니다.

 

 

 

 

긴 글 읽어주셔서 감사합니다.

 

---

 

 

[References]

 

 

[1] Y. Kim. (2017). 메타휴리스틱스, Metaheuristics